2017江苏南京航空航天大学数据结构与操作系统考研真题.doc

2017江苏南京航空航天大学数据结构与操作系统考研真题
数据结构部分（75分）
1．（5分）已知带权图如下所示，用Kruskal算法产生最小生成树，并说明算法思想。

2．（10分）为一个家谱管理程序设计一种数据结构，以一个四代人，11个家庭成员为例，
（A有3个孩子A1、A2、A3；A1有2个孩子A11、A12；A2无子，A3有3个孩子A31、A32、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到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态。

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．CPUD．磁盘空间
（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.控制模块
（9）.在分段管理中()。
A．以段为单位分配，每段是一个连续存储区B．段与段之间必定不连续
C．段与段之间必定连续D．每段是等长的
（10）.通道是一种()。
A.I／O端口B．数据通道C．I／O专用处理机D．软件工具
2.简答题（20分，每题4分）
（1）.系统型线程和用户型线程有何区别？
（2）.多级反馈队列调度算法是如何工作的？
（3）.分段式系统和分页式系统有何区别？
（4）.引入缓冲的目的是什么，有哪些常见的缓冲模式？
（5）.SPOOLING技术如何实现，在操作系统中起何作用？
3.（9分）设有三道作业，它们的提交时间及执行时间由下表给出:

（1）周转时间和带权周转时间的区别是什么，为何引入带权周转时间？（2分）
（2）试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平
均周转时间。（7分）
4.（9分）某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。系统共有这四类资源为:A类3个、B类14个、C类12个、D类12个。进程对资源的需求和分配情况如下：

（1）现在系统是否处于安全状态？（4分）
（2）如果进程P2提出需要A类资源0个、B类资源4个、C类资源2个和D类资源0个，系统能否去满足它的请求？（5分）
5.（9分）某分页系统，每个页面长为1KB，某时刻该用户进程的页表如下：

（1）请写出分页系统的地址转换过程（3分）
（2）计算两个逻辑地址：0AC5H、1AC5H对应的物理地址（16进制表示）。（3分）
（3）已知主存的一次存取为2us，对于快表的查询时间可以忽略，则访问上述两个逻辑地
址分别耗费多少时间？（3分）
6