2017年大连大学教育部先进设计与智能计算重点实验室836数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
2． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性 3．
【答案】5
4． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
； （“图有回路”）
第 2 页，共 54 页
=_____
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
5． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
6． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为
8． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
第 3 页，共 54 页
的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11
）（12）
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后
若ch 是操作数且栈非空，则形成部分中缀表达式
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
9． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ） { if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
第 4 页，共 54 页