搜索
南京工业大学2017年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！（可使用科学计算器）第一部分：数据结构（共90分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。每小题2分，共30分）1.等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为。A.nB.（n-1）/2C.n/2D.（n+1）/22.在单链表中，若要删除由指针q所指向结点的后结点，则执行的语句是。A.p=q→next；p→next=q→next；deletep；B.p=q→next；q→next=p；deletep；C.p=q→next；q→next=p→next；deletep；D.q→next=q→next→next；q→next=qdeletep；3.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列命令。A.x=top；top=top→ntxtB.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.10B.11C.40D.415.下面说法不正确的是。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构表示D.广义表可以是一个多层次的结构6.一棵具有20个叶结点的完全二叉树最多有个结点。A.38B.39C.40D.417.n个结点的线索二叉树上含有的线索数为。A.2nB.n-1C.n+1D.n8.具有128个结点的完全二叉树的深度为。A.6B.7C.8D.99.在结点数为n的最大堆中插入一个结点时，复杂度为。A.O（n）B.O（n2）C.O（log2n）D.O（logn2）10.用5个权值{10，3，7，8，1}构造的哈夫曼树的带权路径长度是。A.58B.62C.63D.6511.G是一个非连通无向图，共有37条边，则图G至少有个顶点。A.9B.10C.11D.1212.下面关于工程计划的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-1B.2k-1+1C.2k-1D.2k+115.下面关于哈希查找的说法正确的是。A.哈希函数构造得越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可二、综合应用题（4小题，共60分）16.（本题15分）假设一个字符串s中允许包含两种括号：圆括号和方括号。试设计一个算法，采用顺序栈（用数组表示的栈）判断该字符串中的括号是否正确配对。具体要求如下：1、定义栈STACK，栈中所存放元素的类型为字符型。2、定义栈STACK的各种操作，包括pop（），top（），push（char），empty（）等。3、定义函数intcheck(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=001230050415012201033423019.（本题15分）设有三阶B-树（如下图所示）（1）画出在下图中依次插入30、26、85后的B-树。（2）分别画出在下图中删除45、12、50后的B-树。第二部分：操作系统（共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则逐个从缓冲区中读出并打印输出，要求打4524539031237506170100印的与输入的完全一样，即个数、次序、数值一样。请完成下列问题：（1）写进程与读进程间具体的制约关系如何？（2）用PV操作写出这两个进程的同步算法程序。12.（本题10分）有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法。今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：作业名到达时间估计运行时间优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟6（1）列出所有作业进入内存时间及结束时间。（2）计算平均周转时间。13.（本题10分）假设某系统有某类资源12个，有P1、P2，P3三个进程来共享，已知P1、P2，P3所需该类资源总数分别为8、6、9，它们申请资源的次序和数量如下表所示：序号进程申请量1P342P123P244P115P326P22......系统采用银行家算法分配资源，请完成下列问题：（1）哪几次申请被满足会使系统进入不安全状态？请应说明理由。（2）执行完序号为6的申请后，各进程的状态和各进程占用的资源数如何？14.（本题10分）在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：（1）按FIFO调度算法将产生的缺页中断次数，依次淘汰的页号和缺页中断率各为多少？（2）按LRU调度算法将产生的缺页中断次数，依次淘汰的页号和缺页中断率各为多少？