2017年暨南大学信息科学技术学院830数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
2． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
4． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
则
的地址为
若
的地址为将代入得33。
5． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
6． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
7． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
，）则 的地址为_____。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
8． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。
void leafchain（BiTree Abt）
{p={BiTree）malloc （sizeof （BiTNode ））; If （!p ）{print£（“OVERFLOW\n”; exit （1）; }
head=p; top=0; if （bt ）
{top++; stack[top]=bt; while （top ）
{t=stack[top]; top--;
if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++; stack[top]= （5） ; } } }
（8） ; （9） ; } } 【答案】
p->Rchild=t:t->Lchild=p:p=t: p->Rchild=head:head->Lchild=p
9． 已知如下程序段：
t->Rchild!=null:t->Rchild:
t->Lchild!=null:
t->Lchild:
语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。
【答案】（1）n ＋1 （2）n
（3）n （n ＋3）/2 （4）n （n ＋l ）/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会
执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。
10．在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
二、选择题
11．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序 【答案】C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。
12．下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储 【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
13．现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 【答案】D