2018年北京师范大学生命科学学院978数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 有向图G=(V, E) ，其中
权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
2． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
:_____:
{_____)
(_____、
:_____；_____；p ＝u ；
【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中
(2)p!＝NULL //当链表尚未到尾，p 为工作指针
(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针
(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中
(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针
3． 在哈希函数中，p 值最好取_____。 ，用三元组表示弧及弧上的
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
4． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
【解析】折半查找时每个的次数如表所示:
表
平均查找次数为。
5． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
6． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
7． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
8． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行
(2)q //将当前结点作为头结点后的第一元素结点插入
9． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
10．对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
11．栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
12．深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
13．已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
14．索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
15．已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
二、单项选择题
16．某计算机的控制器采用微程序控制方式, 微指令中的操作控制字段采用字段直接编码法, 共有33个微命令, 构成5个互斥类, 分别包含7、3、12、5和6个微命令, 则操作控制字段至少有 （ ）。
A.5位
B.6位
C.15位
D.33位
【答案】C 。
33个微命令分成5个互斥类(即5个字段) , 根据每个类中微命令的多少可以分别确定【解析】
字段的长度为3、2、4、3、3位, 又因为采用直接编码方式, 所以它们之和
作控制字段的位数。
17．对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
也就是操