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

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

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

注意:

③本试题纸须随答题纸一起装入试题袋中交回！（可使用科学计算器）

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

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

1.等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目

为。

A.n

B.（n-1）/2

C.n/2

D.（n+1）/2

2.在单链表中，若要删除由指针q所指向结点的后结点，则执行的语句是。

A.p=q→next；p→next=q→next；delete p；

B.p=q→next；q→next=p；delete p；

C.p=q→next；q→next=p→next；delete p；

D.q→next=q→next→next；q→next=q delete p；

3.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下

列命令。

A.x=top；top=top→ntxt

B.top=top→ntxt；x=top→data；

C.x=top→data；

D.x=top→data；top=top→ntxt；

4.在一个大小为M=50的顺序表示一个循环队列中，如果当前的尾指针rear=10，头指针front=20，则当前循环队列的元素个数为。

A.10

B.11

C.40

D.41

5.下面说法不正确的是。

A.广义表的表头总是一个广义表

B.广义表的表尾总是一个广义表

C.广义表难以用顺序存储结构表示

D.广义表可以是一个多层次的结构

6.一棵具有20个叶结点的完全二叉树最多有个结点。

A.38

B.39

C.40

D.41

7.n个结点的线索二叉树上含有的线索数为。

A.2n

B.n-1

C.n+1

D.n

8.具有128个结点的完全二叉树的深度为。

A.6

B.7

C.8

D.9

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

A.O（n）

B.O（n2）

C.O（log2n）

D.O（log n2）

10.用5个权值{10，3，7，8，1}构造的哈夫曼树的带权路径长度是。

A.58

B.62

C.63

D.65

11.G是一个非连通无向图，共有37条边，则图G至少有个顶点。

A.9

B.10

C.11

D.12

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

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

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

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

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

13.分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是。

A.（100，80，90，60，120，110，130）

B.（100，120，110，130，80，60，90）

C.（100，60，80，90，120，110，130）

D.（100，80，60，90，120，130，110）

14.一棵高度为k 的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有个结点。

A.2k-1-1

B.2k-1+1

C.2k-1

D.2k+1

15.下面关于哈希查找的说法正确的是。

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

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

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

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

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

16.（本题15分）假设一个字符串s 中允许包含两种括号：圆括号和方括号。试设计一个算法，采用顺序栈（用数组表示的栈）判断该字符串中的括号是否正确配对。

具体要求如下：

1、定义栈STACK ，栈中所存放元素的类型为字符型。

2、定义栈STACK 的各种操作，包括pop （），top （），push （char ），empty （）等。

3、定义函数int check(char*s)：判断s 中的括号是否正确配对，如果正确配对，返回1，否返回0。

4、在主函数中难所编写函数的正确性。

17.（本题15分）在n ×n （5﹤n ﹤15）的象棋棋盘的某一位置上放置一个马，然后采用象棋中“马走日字”的规则，判断这个马是否能不重复地走完n ×n 个格子，如果能走，则给出一条马所走的轨迹。

输入格式；

输入一行，共3个整数n ，x ，y ，n （﹤n ﹤15）表示棋盘的大小，（x ，y ）表

示马开始的位置。

输出格式；

如果能走遍棋盘，则输出n*n 行，每行两个整数，表示每一步马的位置：如果

不能走遍，则输出-1。

18.（本题15分）网络G 的邻接矩阵如下，试画出该图，并利用Kruska 算法原理画出它的一棵最小生成树（要求画出最小生成树的生成过程，不需要编程）。

G=⎥⎥⎥⎥⎥⎥⎦

⎤⎢⎢⎢⎢⎢⎢⎣⎡0012300504

150122010334230

（1）画出在下图中依次插入30、26、85后的B-树。

（2）分别画出在下图中删除45、12、50后的B-树。

45

245390

31237506170100

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

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

1.现代操作系统的两个基本特征是和资源共享。

A.多道程序设计

B.中断处理

C.程序的并发执行

D.实现分时与实时处理

2.当用户程序执行访管指令时，中断装置将使处理器工作。

A.维持在目态

B.从目态转换到管态

C.维持在管态

D.从管态转换到目态

3.产生系统死锁的原因可能是由于。

A.进程释放资源

B.一个进程进入死循环

C.多个进程竞争，资源出现了循环等待

D.多个进程竞争共享型设备

4.某进程在运行过程中需要等待赍磁盘上读入数据，此时该进程的状态将。

A.从就绪变为运行

B.从运行变为就绪

C.从运行变为阻塞

D.从阻塞变为就绪

5.分区管理方式中，当内存碎片容量大于某一作业所申请的内存容量时。

A.可以为这一作业分配内存

B.不可以为这一作业分配内存

C.拼接盾，可以为这一作业分配内存

D.一定能够为这一作业分配内存

6.分页式存储管理中，地址转换工作是由完成的。

A.硬件

B.地址转换程序

C.用户程序

D.装入程序

7.数据库文件的逻辑结构形式是。

A.字符流式文件

B.档案文件

C.记录式文件

D.只读文件

8.索引式文件组织的一个主要优点是。

A.不需要链接指针

B.能实现物理块的动态分配

C.回收实现比较简单

D.用户存取方便

9.在现代操作系统中采用缓冲技术的主要目的是。

A.改善用户编程环境

B.提高CPU的处理速度

C.提高CPU和设备之间的并行程度

D.实现与设备无关性

10.系统调用的目的是。

A.请求系统服务

B.终止系统服务

C.申请系统服务

D.释放系统资源

二、计算（综合）题（每题10分，共40分）

11.（本题10分）设有n个缓冲区构成的循环缓冲区，每个缓冲区能容纳一个整数，写进程Writer把整数逐个存入缓冲区，读进程Reader则逐个从缓冲区中读出并打印输出，要求打印的与输入的完全一样，即个数、次序、数值一样。请完成下列问题：

（1）写进程与读进程间具体的制约关系如何？

（2）用PV操作写出这两个进程的同步算法程序。

12.（本题10分）有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法。今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：

作业名到达时间估计运行时间优先数

J110:1020分钟5

J210:2030分钟3

J310:3025分钟4

J410:5020分钟6

（1）列出所有作业进入内存时间及结束时间。

（2）计算平均周转时间。

13.（本题10分）假设某系统有某类资源12个，有P1、P2，P3三个进程来共享，已知P1、P2，P3所需该类资源总数分别为8、6、9，它们申请资源的次序和数量如下表所示：

序号进程申请量

1P34

2P12

3P24

4P11

5P32

6P22

......

系统采用银行家算法分配资源，请完成下列问题：

（1）哪几次申请被满足会使系统进入不安全状态？请应说明理由。

（2）执行完序号为6的申请后，各进程的状态和各进程占用的资源数如何？

14.（本题10分）在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：（1）按FIFO调度算法将产生的缺页中断次数，依次淘汰的页号和缺页中断率各为多少？（2）按LRU调度算法将产生的缺页中断次数，依次淘汰的页号和缺页中断率各为多少？