南京工业大学
2013年硕士研究生入学考试初试试题（A 卷）
科目代码：828科目名称：数据结构与操作系统满分：150分
注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；
③本试题纸须随答题纸一起装入试题袋中交回！
第一部分：数据结构（共75分）
一、选择题（每小题2分，共10分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的()和运算的学科。A.结构  B.关系  C.算法  D.操作2、指出下列时间复杂度最坏的级别是。A.对数阶O(log 2n)  B.指数阶O(2n )  C.线性阶O(n)  D.平方阶O(n 2)
3、设S 和队列Q 的初始状态均为空，元素abcdefg 依次进入栈S 。若每个元出栈后立即进入队列Q，且七个元素出队的顺序bdcfeag ，则栈S 的容量至少是（）。A.1  B.2  C.3  D.4
4、已知模式串P=’ABAAB’，其next 函数值是()。A.01112  B.01222  C.01122
D.01123
5、对基本有序表(21,36,40,54,28,64,69,73)进行排序，使用下列哪种方法最好（）。A.简单选择排序  B.直接插入排序  C.冒泡排序  D.归并排序
二、填空题(每小题2分，共10分)
1、线性结构中元素之间存在一对一的关系，图形结构中元素之间存在关系。
2、评价一个算法一般从4个方面进行：正确性、可读性、和。
3、是具有特点的运算受限的线性表，队列是具有特点的运算变限的线性表。
4、动态查我表与静态查表的区别是。
5、一组记录的关键字为(45,79,56,38,40,84)则利用堆排序方法建立的初始大根堆为。
三、计算应用题(共35分)
1、某电文中使用5个字符:a,b,c,d,e 出现的频率依次：为
2、4、5、9、10，试构造一棵对应的哈夫树及哈夫曼编码，并计算其带权路径长度WPL 。(7分)
2、由下列网络的邻接矩阵，画出此带权的图（v1～v6）及BFS 序列，并用Prim 法画出它的最小生成树(从v1出发)(6分)
⎥⎥⎥⎥⎥⎥⎥⎥⎦
⎤
⎢⎢⎢⎢⎢
⎢⎢
⎢⎣⎡03415012223401900201519011700011060120760172220001703、设关键字序列（10,6,4,10,15,12），插入生成平衡二叉排序树（画出平衡调整的过程并指
出每次调整所属的类型）。
4、将关键字序列（7,8,11,18,9,14,16,30）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为H(key)=(key*3)%7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.75。(10分)(1)请画出所构造的散列表。
(2)分别计算等概率情况下查成功的和查不成功的平均查长度ASL 。
四、编程填充题。(每小题10分，共20分)
1、插入排序中插入位置的操作通过二分查法来实现，完成下列改进的插入排序算法（升序）
2、完整下列双冒泡升序排序的算法（上下交替做冒泡排序）。【程序】
void Bubble_Sort(int a[],int n){low=0;high=n-1;
(1);
while(low<high &&change){change=0;
for(
(2))
if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;
change=1;}(3);for((4))
if(a[i]<a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;
change=1;}(5);
}}
第二部分：操作系统（共75分）
一、单项选择题（每小题2分，共30分）
1.下列选项中，在用户态执行的是。
A.命令解释程序
B.缺页中断处理程序
C.进程调度程序
D.时钟中断处理程序
2.两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种关系称为进程间的。
A.同步
B.互斥
C.竞争
D.合作
3.下面叙述中正确的是。
A.操作系统的一个重要概念是进程，因此不同进程所执行的代码也一定不同
B.为了避免发生死锁，各进程只能逐个申请资源
C.操作系统用PCB管理进程，用户进程可以从PCB中读出与本身运行状态有关的信息
D.进程同步是指某些进程之间在逻辑上的相互制约关系
4.设有三个进程共享一个资源，如果每次只允许一个进程使用该资源，则用信号量机制和P、V操作管理时，信号S的可能取值是。
A、1,0,-1,-2
B、2,0,-1,-2
C、1,0,-1
D、3,2,1,0
5.考虑到公乎对待进程和提高系统资源工作的并行度，操作系统会经常调整进程的优先级，通常应提高的
的进程优先级
A.需计算时间长
B.很少使用外设
C.使用CPU时间长
D.启动外设次数多
6.假设有4个进程竞争同类资源，如果每个进程需要3个该类资源，则至少需要供该类资源个能保
证不会因竞争该类资源而发生死锁。
A.5
B.7
C.9
D.12
7.设系中有P1、P2、P3三个进程，并P1、P2、P3的优先次序调度运行，它们的计算时间和操作时间如下：P1：计算60ms—I/O80ms—计算20ms
P2：计算120ms—I/O40ms—计算40ms
P3：计算40ms—I/O80ms—计算40ms
设调度程序执行时间忽略不计，完成这三个进程比单道远行节省的时间是。
A.140ms
B.160ms
C.170ms
D.180ms
8.某系统采用页式存储管理，页的大小为4KB，设内存容量为512M，内存的分配使用情况采用“位示图”表示，则位示图需要字节。
A.4K
B.8K
C.16K
D.32K
9.采用段页式存储管理的系统中，若地址用32位表示，其中10位表示段号，页的大小为4KB，则允许每段的最大页号是。
A.1024
B.1023
C.4096
D.4095
10，用户编写程序时使用的设备与实际使用的设备无关，这种特性称为。
A.设备一致性
B.设备独立性
C.设备虚拟性
D.设备共享性
11.磁盘是共享设备，每一时刻进程与它交换信息。
A.可有任意多个
B.限定n个
C.至少有一个
D.最多有一个
12..某操作系统中采用中断驱动I/O控制方式，设中断时，CPU用1ms来处理I/O中断请求，其他CPU时间全部用来计算。若系统时钟中断频率为100HZ，则CPU的利用率为。
A.60%
B.70%
C.80%
D.91%
13.下述各项中，不是Spooling技术的特点。
A.提高了I/O速度
B.将独占设备模拟成共享设备
C.采用高速缓存(cache)
D.实现了虚拟设备功能
14.下列选项中，不能改善磁盘I/O 性能的是。
A
重排I/O 请求次序  B.在一个磁盘设置多个分区C.预读和滞后写  D.优化文件物理的分布
15.采用直接存取（随机存取）方法来读写磁盘上的物理记录时，效率最低的是
。
A.连续结构文件
B.索引结构文件
C.隐式链接结构文件
D.显式链接结构文件
二、计算（综合）题（共45分）
1.(本题12分)设行车生产车间有两个货架，货架A 以存放8个车架，货架B 可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1加工一个车架放入货架A 中；工人2、3分别加工车轮放入货架B 中(每人每次放入1个车轮)；工人4从货架A 中取一个车架，再从货架B 中取两个车轮，组装成一辆自行车。试用PV 操作实现四个工人的合作。
2.(本题11分)某多道程序设计系统采用可重定位分区内存管理(允许移动在主存中的作业)，供用户使用的主存为200KB ，磁带机5台，采用静态方式分配外围设备，忽略用户作业的I/O 时间、调度时间和移动作业时间，现有如下作亚序列：
作业名进入后备队列时间
运行时间主存需求量磁带机需求哈夫曼编码树的带权路径长度
A 8:3040分钟30K
B 3B 5:5025分钟120KB 1
C 9:0035分钟100KB 2
D 9:0520分钟20KB 3E
9:10
10分钟
60KB
1
假设作业调度采用最高响应比优先算法，进程调度采用时间片轮转算法（均分CPU 时间）请回答下列问题：（1）写出作业调度选中作业的次序。（2）作业平均周转时间是多少分钟？
3.(本题12分)在某一采用固定分配局部置换策略的请求分页系统中，有一进程逻辑地址空间有10个页，分得了4个页框，每页的装入时间、最后访问时间、访问位R 如下表所示（时间用时钟点数表示）。
假设页的大小为4KB （4096B ），当进程执行到时刻300时，要访问逻辑地址6AB8H 的数据，请回答下列问题：
(1)若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。(3分)(2)若采用最近最久未使用(LRU)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。(3分)(3)若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页，示意图如下)。(4分)
页号页框号装入时间最后访问时间访问位R 0100130260011201802001226011023013
300
160
280
1
4.(本题10分)若磁盘的每个磁道分成9个块，现有一文件共有A、B、...、H、I9个记录，每个记录的大小与盘块大小相等，设磁盘转速为27ms/转，每读出一块后需要2ms的处理时间。若忽略其他辅助时间，试问：
（1）如果顺序存放这些记录并顺序读取，处理该文件需要多少时间？
（2）如果顺序读取该文件，记录如何存放处理时间最短？此时处理该文件需要多少时间？

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。