2017年合肥工业大学计算机与信息学院850计算机科学与技术学科专业基础综合之数据结构考研题库
● 摘要
一、填空题
1． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
2． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
3． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。 【答案】
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
4． 以下是用类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: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p
5． 设二维数组A 的行和列的下标范围分别为和每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为
【答案】
当其值为处的元素为_____。 【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。
6． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
7． 在单链表中设置头结点的作用是_____。
【答案】方便运算
8． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
9． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的
数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。
【答案】①1; 1; f （m ，n －1）; n ②9
10．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
二、判断题
11．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ） 【答案】
【解析】队列只在下端（队尾）增加，在上端（队头）减少。
12．对于有n 个结点的二叉树，其高度为（ ）
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
13．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
14．通常使用队列来处理函数或过程的调用。（ ） 【答案】
【解析】经常使用栈来处理函数或过程的调用。
15．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 【答案】
函数，函【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个
数本身包含了模式串的局部匹配信息。
16．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
17．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×