2018年东南大学计算机科学与工程学院935计算机专业基础之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
2． 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。
A. 仅修改队头指针
B. 仅修改队尾指针
C. 队头、队尾指针都可能要修改
D. 队头、队尾指针都要修改
【答案】C
【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。
3． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）.
A. 时间片轮转调度算法
B. 短进程优先调度算法
C. 先来先服务调度算法
D. 高响应比优先调度算法
【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间. 最高响应比优先调度算法是最先执行响应比最高的进程(响应比＝1＋等待时间/估计运行时间). 该算法综合了先来先服务(FCFS)和短作业优先(SJF)算法，
FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短.SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间.
4． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也
2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。
5． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.
6． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）
A.h , c , a , b , d , e , g , f
B.e , a , f , g , b , h , c , d
C.d , b , c , a , h , e , f , g
D.a , b , c , d , h , e , f , g
【答案】D
【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。
7． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
A.1
B.2
C.3
D.4
E.5
【答案】C
【解析】动态存储管理系统中有以下三种:首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
8． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点
C.X 的左子树中最右的结点
D.X 的左子树中最右的叶结点
【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
9． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。