当前位置：问答库＞考研试题

一、填空题

1． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

2． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

3． 试利用下列栈和串的基本操作完成下述填空题。

initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；

置串 判串 返回联接

empty （st ） 判串空函数

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）

第 2 页，共 62 页

为空串；

是否相等的函数；

之后的串；

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 是操作数且栈为空，则按出错处理

4． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

5． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

第 3 页，共 62 页

6． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

7． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

8． 如下的算法分别是后序线索二叉树求给定结点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;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；;

while （*x==node ）; *x=t; } }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

9． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

10．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

第 4 页，共 62 页