南京航空航天大学-922数据结构与操作系统【2018】考研真题
免费
2023-06-21
999+
141.43KB
4 页
侵权投诉
科目代码：922 科目名称：数据结构与操作系统(专业学位) 第 1 页 共 4 页
南京航空航天大学
2018 年硕士研究生入学考试初试试题᷉ A卷 ᷊
科目代码: 922 满分: 150 分
科目名称: 数据结构与操作系统(专业学位)
注意: 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无
效；本试题纸须随答题纸一起装入试题袋中交回！
数据结构部分
1．5 分设 n*n 的矩阵 A[1..n（1..n]为三角特殊矩阵，其逆对角线以上为 0，逆对角线以
及逆对角线以下的所有元素按行序压缩存储在一维数组 B[1..n*(n+1)/2]中， 根据 i、j
在满足何种条件下，计算元素 Aij 的存储位置，给出推导过程。
2．10 分给出下图所示树的二种存储结构示意图。
1带双亲的孩子链表表示法
2孩子兄弟表示法
并说明这二种存储结构的优缺点。
3．10 分给定 n 个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这 n 个
村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄
到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解
答下图所示的实例，给出算法执行示意图。
4．10 分详细解释哈希表的工作原理。以此为例，将关键字序列51，83，43，15，62，
59，74，61存储在长度为 10 的哈希表中，使用哈希函数 H(key) = Key % 10 ，并采用链
地址法解决冲突，画出哈希表示意图。
A
E
D
C
I
K
G
B
H
FJ
V3
V2
V4
V1
3
46
10
2
科目代码：922 科目名称：数据结构与操作系统(专业学位) 第 2 页 共 4 页
5．10 分设有一批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一秒钟收
到一个新的数据元素加入 S。现要求在每次接收一个新元素之前，找出 S 中现有的最小元素
并将其输出从 S 中删除。试选择或构造一种适当的数据结构并设计一个算法，尽可能高
效地完成上述任务。例如S=(59（31（29（18（78（26（48（10（65（35)，新接受的数据为 39，12，
46….。以此为例说明算法执行过程示意图。
6．10 分设一个带头结点的单链表 L，数据元素为整数，其中大部分为正数，少数为负
数，编写函数，采用高效的算法调整链表，实现将负数结点移到链表尾部，并返回调整后
链表中的第一个负数结点位置。先给出算法思想，再写相应代码。
7.10 分设二叉树 T，用二叉链表结构存储，元素值为整数且互不相同。编写非递归函
数，对给定的 2 个整数，若 2 个都不是 T 的元素，输出）2若 1 个不是 T 的元素，输出）1
若 2 个都是 T 的元素，输出两者所在的层数的间隔数。先给出算法思想，再写出相应代码。
8．10 分设有 N 个顶点的有向无环图 G，以邻接矩阵方式存储。编写函数，对 G 中的每
个顶点进行遍历，若顶点 V 到顶点 W 存在一条有向边弧，则要求顶点 V 在顶点 W 之前访
问。先给出算法思想，再写出相应代码。
操作系统部分
1.填空题2 分 x5=10 分)
1.操作系统的两大特征是 。
2.单道系统中，假设一批作业同时到达，若想平均周转时间最短，采用( )
调度算法。
3.时间片轮转调度算法中，如果时间片无穷大，该算法变成了 调度算法。
4.在某系统中有 5 个并发进程，都需要同类资源 6 个，问该系统肯定不会发生死锁
时最少资源数是 。
5. 对于首次适应算法、最佳适应算法和循环首次适应算法，可以保留高地址部分
的大空闲区的算法是 。
2.简答题4 分 x5=20 分
1 画出引入挂起和激活机制后，进程状态转换图。
2 处理机调度分为哪三级？各自的主要任务是什么？
3 内存管理中连续分配有何缺点，为何要引入离散分配？
4 相对于顺序文件和索引文件，索引顺序文件有何优点？如果在一个索引顺序文件中
含有 N 个记录，如何设计索引顺序文件，令检索指定关键字记录的平均查找次数最少？
5 装入时动态链接和运行时动态链接有何区别？哪种更节约内存？
标签： #南京航空航天大学
摘要：
展开>>
收起<<
科目代码：922科目名称：数据结构与操作系统(专业学位)第1页共4页南京航空航天大学 2018年硕士研究生入学考试初试试题 ÉA卷 Ê科目代码:922满分:150分科目名称:数据结构与操作系统(专业学位)注意:7认真阅读答题纸上的注意事项；8所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；9本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分1．5分设n*n的矩阵A[1..n（1..n]为三角特殊矩阵，其逆对角线以上为0，逆对角线以及逆对角线以下的所有元素按行序压缩存储在一维数组B[1..n*(n+1)/2]中，根据i、j在满足何种条件下，计算元素Aij的存储位置，...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
