PDF《南京航空航天大学》

科目代码:922 科目名称:数据结构与操作系统(专业学位) 第1页共4页南京航空航天大学

2017 年硕士研究生入学考试初试试题( A 卷)科目代码:

922 科目名称: 数据结构与操作系统(专业学位) 满分:

150 分 注意: ①认真阅读答题纸上的注意事项;

②所有答案必须写在答题纸上,写在本试题纸或草稿纸上均无 效;

③本试题纸须随答题纸一起装入试题袋中交回! 数据结构部分(75 分) 1.

(5 分)已知带权图如下所示,用Kruskal 算法产生最小生成树,并说明算法思想. 2. (10 分)为一个家谱管理程序设计一种数据结构,以一个四代人,11 个家庭成员为例, (A 有3个孩子 A

1、A

2、A3;

A1 有2个孩子 A

11、A12;

A2 无子,A3 有3个孩子 A

31、A

32、 A33;

A11 有1个孩子 A111;

A32 有1个孩子 A321;

其余尚无子) ,画出家谱示意图,给出 所设计的存储结构示意图,并给出在该存储结构上输出第 k 代所有人员的算法思想. 3. (10 分)设有

8 个字符(a, b, c, d, e, f, g, h) ,其权值为(48,15,20,12,6,61,8,10) , 给出进行 Huffman 编码所用的数据结构和求解过程数据结构中数据的最后结果. 4. (10 分)已知输入数据序列为 (58,68,42,10,88,32,70,52,55,46 ),给出建立

3 阶B- 树示意图,再给出删除 55,70 后的 B-树. 5. (10 分)试用 Dijkstra 算法,求下图中从 V1 到其余各顶点的最短路径,给出实现算法 所用的数据结构和求解过程中每一步的状态. V2 V4 V5 V6 V1 V3

7 2

5 8

6 10

3 10 V2 V6 V3 V4 V1 V5

2 1

5 8

9 4

18 3 科目代码:922 科目名称:数据结构与操作系统(专业学位) 第2页共4页6. (10 分)设A、B 为递减有序(元素值为整型)的单链表,编写函数,利用原结点将它们 合并成一个递增有序的单链表,相同元素值只保留一个结点.先给出算法思想,再写出相 应代码. 7.(10 分)设二叉树 T,用二叉链表结构存储.编写函数,对于每个元素值为 x 的结点, 删去以它为根的子树,并释放相应的空间.要求先给出算法思想,再写出相应代码. 8.(10 分)设有 n 个学生成绩(0-100 整数)的顺序结构线性表 L,编写函数,将该线性表 中调整为成绩及格(大于等于 60)在不及格之前,要求 T(n)=O(n), S(n)=O(1).先给出算 法思想,再写出相应代码. 操作系统部分(75 分) 1. 单选题(10 分,每题

1 分) (1) .在下列系统中,( )是实时系统. A.计算机激光照排系统 B.军用反导弹系统 C.办公自动化系统 D.计算机辅助设计系统 (2). 引入多道程序的目的在于( ). A.充分利用 CPU,减少 CPU 等待时间 B.提高实时响应速度 C.有利于代码共享,减少主、辅存信息交换量 D.解放 cpu 对外设的管理 (3) .已经获得除( )以外的所有运行所需资源的进程处于就绪状态 A.存储器 B.打印机 C.CPU D.磁盘空间 (4) .采用时间片轮转法调度是为了( ). A.多个终端都能得到系统的及时响应 B.先来先服务 C.优先级较高的进程得到及时调度 D.需CPU 最短的进程先做 (5) .在一段时间内只允许一个进程访问的资源,称为( ) . A.共享资源 B.临界区 C.临界资源 D.共享区 (6).并发性是指若干事件在( )发生 . A.同一时刻 B.同一时间间隔内 C.不同时刻 D.不同时间间隔内 (7) .管道通信是以( )进行写入和读出. A.消息为单位 B.自然字符流 C.文件 D.报文 (8) .操作系统中有一组特殊的程序.它们不能被系统中断,在操作系统中称为( ) A.初始化程序 B.原语 C.子程序 D.控制模块 科目代码:922 科目名称:数据结构与操作系统(专业学位) 第3页共4页(9). 在分段管理中( ). A.以段为单位分配,每段是一个连续存储区 B.段与段之间必定不连续 C.段与段之间必定连续 D.每段是等长的 (10).通道是一种( ). A.I/O 端口 B.数据通道 C.I/O 专用处理机 D.软件工具 2. 简答题(20 分,每题