831
华南理工大学
2013年攻读硕士学位研究生入学考试试卷
（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：计算机技术(专硕)
共4页
数据结构
一．选择题（每小题2分，共20分）
1.一个非空二叉树的中序序列是DBEACGF，后序序列是DEBGFCA，则其前序序
列是____。A）ABCDEFGB）ABDEFGCC）ABEFGDED）ABDECFG
2.顺序存储的循环队列，存储空间大小为n，队头结点下标为front，队尾结点下标
为rear。则此循环队列中的元素个数为______。A）n+front-rearB)rear-front+1C)(rear-front)%nD)(n+rear-front+1)%n3.下列排序方法中，平均情况下的时间复杂度是O(nlogn)且稳定的方法是___。
A）归并排序B）快速排序C）简单插入排序D）堆排序4.深度为5的5阶B树，第4层（根结点为第1层）共有最少______个关键字。
A）66B）53C）20D）795.已知广义表((c),(a),(d),((d,f)))，则以下说法正确的是_____。
A）表长为4，表头为(c)，表尾为((d,f))
B）表长为4，表头为(c)，表尾为((a),(d),((d,f)))C）表长为5，表头为(c)，表尾为f
D）表长为5，表头为©，表尾为((d),((d,f))
6.向一棵空的二叉排序树中逐个插入5,28,4,16,32,21,3,9，则查找9的查找长度为
______。A）1B)2C)3D)4
7.设有一个AOE网，有3条关键路径，共有15个关键活动，下面的说法_____是
正确的。
A）提前完成这15个关键活动之外的活动可以缩短工期B）这三条关键路径长度相同
C）提前完成这3条关键路径中的任何一个关键活动都能缩短工期D）改变这15个关键活动之外的活动不会影响工期
8.一个有向图，有n个顶点，e条边，则对其邻接表以下说法正确的是_____。
A）邻接表中有n个头结点和2e个表结点，求顶点的度很快
B）邻接表中有n个头结点和e个表结点，求顶点的度要遍历整个邻接表
第1页
C）邻接表中有n个头结点和2e个表结点，求顶点的度要遍历整个邻接表D）邻接表中有n个头结点和e个表结点，求顶点的度很快9.求单源最短路径的迪杰斯特拉算法的时间复杂度为_____。A）O(n3)B）O(nlogn)C）O(n2)D）O(n2logn)10.对完全二叉树中结点按层序依次存在数组中：3，17，23，5，34，98，2，运行建堆算法，则得到的大顶堆在数组中的存储映像为____。A）98，34，23，5，17，3，2B）98，34，23，17，5，3，2C）98，34，23，17，5，2，3D）98，23，34，5，17，3，2二．解答题（共30分）1．算法的时间复杂度与算法输入有关。请分析快速排序方法在（1）随机的输入数据；（2）已排序的输入数据两种情况下的时间复杂度。假设选枢轴的方式是选第一个元素。对归并排序，这两种情况有没有区别？为什么？（6分）2．举例说明Huffman编码的构造过程。为什么要求不定长编码需为前缀编码？证明为什么Huffman编码为前缀编码。（8分）3．在哈希方法中，哈希函数为H(K)=K%13，解决冲突的办法是线性探测再散列。散列空间的地址编号为0~17。请对关键字{13，15，9，24，21，10，18，44，22，6，11，19}构造哈希表，并求查找成功时的平均查找长度。这种解决方法会引起什么问题？有哪些方法可以避免这类问题？（8分）4．叙述进行对有向图进行拓扑排序的算法，以及判断图中是否有环的方法。给出以下有向图的两种拓扑序列，如果有环，则给出环。拓扑排序有什么应用？（8分）BACDEF三．算法设计题（共25分）1．两个单链表中存储整型数，且每个链表都是有序的（从小到大）。编写程序实现两个链表合成一个有序链表的算法。要求用尽量快的算法，并给出时间复杂度。（10分）2．编写程序完成二叉树层序遍历算法（从上至下、从左至右逐层访问）。二叉树为二叉链表方式存储。（15分）GH第2页操作系统
一、单项选择题(每小题1分，共10分)
1.CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采
用()。A.覆盖技术B.并行技术C.缓冲技术D.虚存技术
2.按（）分类，可将设备分为块设备和字符设备。
A.信息交换单位B.从属关系C．操作特性D.共享属性3.虚拟存储器的最大容量由（）。
A.内存和外存容量之和决定B.由CPU的地址位数决定C．由内存容量决定D.是任意的4.在操作系统中，并发性是指若干事件（）发生。
A．在同一时刻B.并行C．依次在不同的时间间隔D.在同一时间间隔内5.位图可用于（）。
A．文件目录的查找B.文件的保护C．内存空间的共享D.磁盘/内存空间的管理6.（）允许在一台主机上同时连接多个终端，多个用户可以通过各自的终
端同时交互地使用计算机。A．批处理系统B.分时系统C.实时系统D.网络系统7.实时操作系统必须在（）处理完来自外部的事件。
A.响应时间B.周转时间C．规定时间D.调度时间8.如果系统中有n个进程，则就绪队列中最多有（）进程。
A．n-1B.1C.nD.n+1
9.某系统中有三个并发进程，都需要同类资源4个，试问该系统不会发生死锁
的最少资源数目是（）。A．9B.10C．11D.1210.采用（），不会产生外部碎片。
A．分页式存储管理B.固定分区式存储管理C．分段式存储管理D.段页结合式存储管理
第3页
二、名词解释（每小题5分，共15分）
1.系统调用（systemcall）2.虚拟机(virtualmachine)
3.可信计算基(trustedcomputingbase)
三、（5分）在某计算机系统中，其屏幕显示器分辨率为1280×960，若要存储一屏
256彩色的图像，需要多少字节存储空间？四、（10分）一种在磁盘上连续分配并且可以避免空洞的方案是，每次删除一个文
件后就紧缩一下磁盘。由于所有的文件都是连续的，复制文件时需要寻道和旋转延迟以便读取文件，然后全速传送。在写回文件时要做同样的工作。假设寻道时间为5ms，旋转延迟为4ms，传送速率为8MB/s，而文件平均长度是8KB，把一个文件读入内存并写回磁盘上的一个新位置需要多长时间？运用这些数字，计算紧缩16GB磁盘的一半需要多长时间？
五、（10分）一个系统有4个进程和5个可分配资源，当前分配和最大需求如下：
已分配资源最大需求量可用资源102111121300X12进程A
2011022210进程B
1101021310进程C
1111011221
进程D
若保持该状态是安全状态，X的最小值是多少？并给出理由。六、（10分）设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个物理块，试问逻辑地址至少有多少位？内存空间有多大？七、（15分）有m个理发师，m把理发椅和n把供等候理发的顾客坐的椅子。如果
没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师进行理发；如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。请使用信号量机制，编写描述理发师和顾客的行为的程序，要求不能带有竞争条件。
第4页
