2018年广西桂林电子科技大学数据结构及操作系统考研真题.doc

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.线性表若采用HYPERLINK"https://www.baidu.com/s?wd=%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1Y3mhmdnW9brjTzPjFbPHF-0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6KdThsqpZwYTjCEQLGCpyw9Uz4Bmy-bIi4WUvYETgN-TLwGUv3EnHc1rjf1nWfzP1f4Pjm4P1f4rf"\t"_blank"链式存储结构时，要求内存中可用存储单元的地址:（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）2n
9.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）
（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.有一个进程进入了临界区，并有多个进程等待