1、数据结构部分数据结构部分一、选择题（每题一、选择题（每题 2 分，共分，共 20 分）分）1、将线性表 La 和 Lb 头尾连接，要求时间复杂度为 O(1)，且占用辅助空间尽量小，应该使用哪种结构？ ()A. 单链表B.单循环链表C.带尾指针的单循环链表D. 带头结点的双循环链表2、在一个链队列中，front 和 rear 分别为头指针和尾指针，则插入一个结点 s 的操作为（ ）。A. front=front-nextB.s-next=rear;rear=sC.rear-next=s;rear=s;D. s-next=front;front=s;3、设一个堆栈的入栈顺序是 1、2、3、4、5。
2、若第一个出栈的元素是 4，则最后一个出栈的元素必定是： ()A.1B.3C.5D.1 或者 54、由分别带权为 9、2、5、7 的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为： ()A.23B.37C.44D.465、如果 AVL 树的深度为 5（空树的深度定义为 0），则此树最少有多少个结点？()A. 12B.20C.33D. 646、若无向图 G =（V，E）中含 10 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是： ()A. 45B.37C.36D. 97、有一个有序表为1, 3, 9, 12, 32, 41,45, 62, 75, 77, 82, 95, 10
3、0，当用二分法查找值 82 的结点时，（ ）次比较后查找成功。A. 8B.1C.4D. 28、给定散列表大小为 17，散列函数为 H(Key)=Key%17。采用平方探测法处理冲突：hi(k)=(H(k)i2)%17将关键字序列 6, 22, 7, 26, 9, 23 依次插入到散列表中。那么元素 23 存放在散列表中的位置是：()A. 0B.2C.6D. 159、在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？()A. O(logN)B.O(N)C.O(NlogN)D. O(N2)1
4、0、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是： ()A. 4B.3C.2D. 1二、综合题（每题二、综合题（每题 10 分，共分，共 50 分）分）1、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H中序遍历序列： B F D A G E H C。（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。2、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。(2)
5、输出最小值后，如何得到次小值（并画出相应结果图）。3、采用哈希函数 H（k）=3*k mod 13 并用线性探测开放地址法处理冲突，在数列地址空间0.12中对关键字序列 22,41,53,46,30,13,1,67,51。（1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。4、用一个数组 S（设大小为 MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用 C 设计公用的入栈操作 push（i，x），其中 i 为 0 或 1，用于表示栈号，x 为入栈值。5、对于下图完成下列指定操作。（1）从顶点 A 出发，求它的深度优先生成树。（
6、2）从顶点 E 出发，求它的广度优先生成树。（3）根据普利姆(Prim) 算法，求它的最小生成树。三、算法设计题（每题三、算法设计题（每题 10 分，共分，共 20 分）分）1、 编写一个函数，输出二叉树中从每个叶子结点到根结点的路径。2、一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点 v 出发的深度优先遍历的非递归过程。操作系统部分操作系统部分四、简答题（每小题四、简答题（每小题 5 分，共分，共 30 分）分）1. 处理机调度进程主要通过调度程序来完成，调度程序主要有三种策略：低级调度（也称为短程调度或者短期调度），中级调度（也称为中程调度、中期调度或者激活操作），高级调度（也
7、称为作业调度或者长程调度）。请说明上述三种调度策略的区别。2. 在解决进程同步问题时，经常使用信号量机制，最基本的信号量有整型信号量和记录型信号量，请简要说明对这两种信号量的操作过程。3. 假设系统中有 4 个相同类型的资源 R， 这些资源被 3 个进程共享， 每个进程最多需要 2 个资源 R，请问该系统有没有可能发生死锁？并说明原因。4. 分页内存管理和分段内存管理的区别有什么？5. 计算机操作系统的目录是对相关文件信息进行说明的一个集合，通过目录对文件实施管理和操作。请说明操作系统目录主要包含哪些内容？6. 简述计算机 I/O 系统的组成。哪些部分是操作系统提供的 I/O 功能。五五、应用
8、题应用题（每小题（每小题 10 分，共分，共 30 分）分）1. 某虚拟存储器的用户进程共分为 5 页，内存为 64KB，页面大小为 4KB，系统为该进程分配了 3 个内存块（帧）。假定某时刻用户页表如下：页号块号页面调入内存时间2515:0101015:303414:55则逻辑地址 0A5C（H）、7B32（H）和 12D1（H）所对应的物理地址是什么？写出地址转换过程。2. 某生产线有三道工序，分别是原料输入、产品加工和产品包装处理，这三道工序共享一个物品放置区。三道工序之间的关系如下：（1）原料输入工序把原料送到放置区，供产品加工工序使用；（2）产品加工工序从放置区取出原料进行加工，把加工后的产品送入放置区；（3）包装处理工序把放置区中的产品包装后输出来完整的产品。请利用信号量机制，写出同步上述工序的基本思想，并用伪代码写出实现过程。3. 假设某磁臂在磁盘上刚处理完 60 号柱面的请求，目前正在 65 号柱面读信息，有下表中等待访问磁盘的序列：请求序列12345678将要访问的柱面号3619241571216664100请按两种磁盘调度算法 SCAN 算法 （也称电梯调度算法） 和最短寻道时间优先调度算法，回答以下两个问题：（1）分别给出请求序列的柱面号处理次序；（2）比较两种算法的优缺点。
