2018 年广西桂林电子科技大学数据结构及操作系统考研真题Part Ⅰ：数据结构部分一、单选题（每小题 2 分，共 10 小题，合计 20 分）1.判定一个队列 QU（最多元素为 m0）为满队列的条件是（A）QU->rear － QU->front = = m0 （B）．QU->rear － QU->front －1= = m0 （C）．QU->front = = QU->rear （D）．QU->front = = QU->rear+12. 链表是一种采用（ ）存储结构存储的线性表（A）顺序 （B）链式 （C）星式 （D）网状3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以4． 线性表Ｌ在（ ）情况下适用于使用链式结构实现。（A）需经常修改Ｌ中的结点值 （B）需不断对Ｌ进行删除插入 （C）Ｌ中含有大量的结点 （D）Ｌ中结点结构复杂5. 若已知一个栈的入栈序列是 1，2，3，…，n，其输出序列为 p1，p2，p3，…，pn，若 p1=n，则pi 为（ ） （A）i （B）n=i （C）n-i+1 （D）不确定6.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则最节 省运算时间的存储方式是（ ）（A) 单链表 （B）双链表 （C）仅有头指针的单循环链表（D） 仅有尾指针的单循环链表7. 树中所有结点的度之和等于所有结点数（ ）（A) 加 0 （B）加 1 （C）减 1 （D）加 n8 在一棵具有 n 个结点的二叉链表中，所有结点的空域个数等于（ ）（A) n （B） n-1 （C） n+1 （D）2n9. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）（A） 空或只有一个结点 （B） 任一结点无左孩子（C） 高度等于其节点数 （D） 任一结点无右孩子 10.有 10 个结点的二叉树中，度为 0 的结点数为 4，则度为 2 的结点数为（ ）。（A）3 （B）4 （C）5 （D）6二、算法应用题（每小题 10 分，共 3 小题，合计 30 分）1、已知散列函数为 H(key)=key%7，散列表长度为 7(散列地址空间为 0..6)，待散列序列为：(25，48，32，50，68)。要求：(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；(2)若要用该散列表查找元素 68，给出所需的比较次数。2、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：1）归并排序， 每归并一次书写一个次序。2）快速排序， 每划分一次书写一个次序。3、已知一个表{jan,feb,mar,apr,may,june,july,aug,sep}，使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。三、算法设计题（2 小题，共 25 分）1、已知两个链表 A 和 B，其元素值递增排列。写出编程将 A 和 B 合并成一个递增有序（相同值只保留一个）的链表 C 的思想，并要求利用原表结点。（10 分）2、编写算法，计算二叉树中分支节点（除叶子节点之外的节点）个数。（15 分）Part Ⅱ：操作系统部分一、单选题（每小题 2 分，共 10 小题，合计 20 分）1. 从资源管理的角度出发，将处理器执行的指令分成两类，其中的特权指令只允许______使用。 A.应用程序 B.联机用户 C.操作系统程序 D.目标程序2. 设计操作系统的主要目的是________。 A.提高系统软件的运行速度 B. 提高系统资源的利用率 C.增强计算机硬件的功能 D. 提高用户软件的运行速度3. 在进程的基本状态转换中，以下状态转换不正确的是____________。A.就绪→运行 B. 运行→就绪 C. 等待→就绪 D.等待→运行4. 为了使系统具有最高的吞吐率，作业调度算法应__________。 A.满足所有用户 B.设计简单一些 C.在较短的时间内能够处理尽可能多的作业 D.借助于进程调度5. 对于 N 并发进程，设互斥信号量为 S=1，则当 S=0 时，表示__________。 A.有一个进程进入了临界区, 没有进程等待进入 B.有一个进程进入了临界区，并有多个进程等待进入 C.没有进程进入临界区 D.有不止一个进程进入了临界区6. 当采用按序分配资源方法预防死锁时，它破坏了产生死锁的四个必要条件中的________...
