2016年南京工业大学828数据结构与操作系统真题

2016年硕士研究生入学考试初试试题（A卷）

科目代码：828科目名称：数据结构与操作系统满分：150分

注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；

③本试题纸须随答题纸一起装入试题袋中交回！

第一部分：数据结构（共90分）

一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）

1.下面关于线性表的描述中，错误的是。

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行的插入和删除操作

C.线性表采用链式存储，不必占用一片连续的存储单元

D.线性表采用链式存储，便于插入和删除操作

2.在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的

语句是。

A.HL=p；p→next=HL；

B.p→next=HL；HL=p；

C.p→next=HL；p=HL；

D.p→next=HL→next；HL→next=p；

3.设有一个顺序栈，元素A，B，C，D，E，F依次进栈，如果6个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少为。

A.3

B.4

C.5

D.6

4.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为。

A.O（m）

B.O（n）

C.O（m+n）

D.O（m×n）

5.在按行优先顺序存储的三元组表中，下列陈述错误的是。

A.同一行的非零元素，是按列号递增次序存储的。

B.同一列的非零元素，是按行号递增次序存储的

C.三元组表中三元组行号是非递减的

D.三元组表中三元组列号是非递减的

6.具有10个叶结点的二叉树有个度为2的结点。

A.8

B.9

C.10

D.11

7.在线索二叉树中，t所指结点没有左子树的充要条件是。

A.t→left=NULL

B.t→ltag=TRUE

C.t→ltag=TRUE且t→left=NULL

D.以上都不对

8.在结点数为n的堆中插入一个结点时，复杂度为。

A.O（n）

B.O（n2）

C.O（log2n）

D.O（log n2）

9.设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中没有右孩子的结点有个。

A.n-1

B.n

C.n+1

D.n+2

10.在一个无向图中，所有顶点的度数之和等于所有边数的倍。

A.1/2

B.1

C.2

D.4

11.在如下图所示的图中，从顶点a 出发，按深度优先遍历，则可能得到一种顶点的序列为。

A.a ，b ，e ，c ，d ，f

B.a ，c ，f ，e ，b ，d

C.a ，e ，b ，c ，f ，d

D.a ，e ，d ，f ，c ，

b

12.在下图所示的无向图中，从顶v1开始采用Prim 算法生成最小生成树，算法过程中产生的顶点次序为。

A.v1，v4，v3，v6，v5，v2

B.v1，v4，v3，v5，v6，v2

C.v1，v3，v5，v6，v2，v4

D.v1，v3，v5，v6，v4，v2

13.下面关于工程计划的AOE 网的叙述中，不正确的是。

A.关键活动不按期完成就会影响整个工程的完成时间。

B.任何一个关键活动提前完成，那么整个工程将会提前完成。

C.所有关键活动都提前完成，那么整个工程将会提前完成。

D.某些关键工程若提前完成，那么整个工程将会提前完成。

14.不可能生成下图所示的二叉排序树的关键字的序列是。

A.45312

B.42531

C.45213

D.42315V1

V2

V3V4V5V66772213

8

46

4

25

3

1

A.哈希函数构造得越复杂越好，因为这样随机性好，冲突小

B.除留余数法是所有哈希函数中最好的

C.不存在特别好与坏的哈希函数，要视情况而定

D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可

二、综合应用题（5小，共60分）；

16.（本题12分）利用指针表示的线性表（链表）表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：A（x）=amtem+am-1xem-1+…+a1xe1

其中，系数ai≠0，指数ei满足em＞em-1＞…＞e2＞e1＞=0。

要求：1、定义多项式每一项的结构，这里假设多项式的系数和指数都为整数。

2、定义两个多项式的相加和相乘运算函数。

3、在main函数中，构建两个多项式，并测试相加和相乘运算。

17.（本题10分）一段电文中只包含6个字母，所包含字母统计信息为：6个a、3个b、7个c、4个d、8个e、1个f。通过构造哈夫曼树设计出这段电文中的每个字符（a，b，c，d，e，f）的哈夫曼编码（01编码），并计算整段电文的编码长度，具体要求如下：

（1）画出哈夫曼树的构造过程（包括每一步的扩充过程）；

（2）根据哈夫曼树，确定每一个字母的编码；

（3）计算整段电文的编码长度。

18.（本题14分）对于表达式（a/b+(c-d)）-e*f；

（1）画出该表达式的二叉树表示形式。

（2）根据该表达式的二叉树表示形式，写出该二叉树的逆波兰式（后缀表示法）。

（3）描述利用逆波兰式求该表达式值的过程（利用栈结构，不需要编程）。

19.（本题12分）如下图所示的有向网络，利用Di jkstra算法求从顶点v1到其他各顶点的最短路径。要求先填写表格，然后根据表格求出v1到各个顶点的最短距离和最短路径。

步骤S W D[2]D[3]D[4]D[5]P[1]P[2]P[3]P[4]P[5]

初态{1}-20100∞60x11x1

1

2

3

4v1到v2的最短距离为：最短路径为：。

v1到v3的最短距离为：最短路径为：。

v1到v4的最短距离为：最短路径为：。

v1到v5的最短距离为：最短路径为：。

20.（本题12分）设有三阶B-树（如下图所示）

1、画出依次插入18、33、97后的B-树

2、分别画出删除66、16、43后的B-树

第二部分：操作系统（共60分）

一、单项选择题（第小题2分、共24分）

1.把逻辑地址转变为内存的物理地址的过程称做。

A.编译

B.连接

C.运行

D.重定位

2.一个文件系统的逻辑分区。

A.不能管理大于物理硬盘容量

B.能管理2个相同的物理硬盘

C.能管理2个不相同的物理硬盘

D.能管理多个不相同的物理硬盘

3.一个作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比是。

A.0.5

B.1

C.2

D.3

4.在由9个生产者，6个消费者，共享容量为8的缓冲器组成的生产者-消费者问题中，互斥使用缓冲器的信号量mutex的初值应该为。

A.8

B.6

C.9

D.1

5.下列算法中用于磁盘磁盘移臂调度的是。

A.时间片轮转法

B.LRU算法

C.最短寻找时间优先算法

D.优先级高者优先算法

6.CPU交替执行操作系统和应用程序，根据运行程序对机器指令的使用权限而将CPU置为不同的状态。用户程序只能在下运行。

A.管态

B.目态

C.处理机状态转换

D.核心态

7.死锁预防是保证系统不进入死锁状态的静态策略，其解决办法是破坏产生死锁的四个必要条件之一。下列方法中哪是一个破坏了“循环等待”条件。

A.银行家算法

B.资源有序分配策略

C.剥夺资源法

D.一次性分配策略8.缓冲技术中，将多个缓冲区统一起来，就构成了缓冲池，缓冲池存在于。

A.ROM

B.寄存器组

C.主存

D.外存

9.分区管理要求对每一个作业都分配的内存单元。

A.地址连续

B.若干地址不连续的

C.若干连续的帧

D.若干不连续的帧

10.当前的许多计算机系统中都采用三级存储结构，处于内存和处理机之间的高速小容量存储器称为。

A.实存储器

B.虚存储器

C.外存储器

D.高速缓存

二、计算（综合）题（3小题，共36分）

11.（本题10分）有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1，进程P2需用资源S1和S2；进程P3需用资源S2和S3。

（1）若对资源分配不加，会发生什么情况？为什么？

（2）为保证进程正确工作，应采用怎样的资源分配策略？为什么？

12.（本题10分）设公共汽车上，司机和售票员的活动分别如下：

司机的活动：启动车辆；正常行车；到站停车。

售票员的活动：关车门；售票；开车门。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V 操作实现它们的同步。

13.（本题10分）一个页式存储管理系统使用PLFO、OPT和LRJ页面替换算法，如果一个作业的页面走向为：

（1）2、3、2、1、5、2、4、5、3、2、5、2

（2）4、3、2、1、4、3、5、4、3、2、1、5

（3）1、2、3、4、1、2、5、1、2、3、4、5

当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。

14.（本题10分）假定磁盘有200个柱面，编号0-199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。

（1）先来先服务算法FCFS；

（2）最短查找时间优先算法SSTF；

（3）扫描算法SCAN；

（4）电梯高度。