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

一、填空题

1． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

2． 中缀式对应的前缀式为_____，若运算结果为_____。

【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

3． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

4． 实现字符串拷贝的函数strcpy 为：

【答案】

5． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

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

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

置串 判串 返回联接

为空串；

是否相等的函数；

之后的串；

第 2 页，共 49 页

则后缀式的

length （st ） 返回串st 的长度；

sub （S , i , 1） 返回S 中第i 个字符； empty （st ） 判串空函数

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

注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）

取栈顶操作符 操作符取出后，出栈

将pre 的最后一个字符（操作数）加入到中缀式exp 的最后

若ch 是操作数且栈非空，则形成部分中缀表达式

栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符

如ch 是运算符，则入操作符栈s 判栈8是否为空

若读出ch 是操作数且栈为空，则按出错处理

7． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，

第 3 页，共 49 页

关键字最多。

8． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

置空链表，然后将原链表结点逐个插入到有序表中

当链表尚未到尾，p 为工作指针

查P 结点在链表中的插入位置，这时q 是工作指针

将P 结点链入链表中

是q 的前驱，u 是下个待插入结点的指针

【答案】（1）（2）（3）（4）（5）

9． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

10．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

二、算法设计题

11．已知关键字序列

（1）试写出一算法将

（2）利用（1）的算法写一个建大根堆的算法。 【答案】（1）算法如下：

第 4 页，共 49 页

是大根堆。

调整为大根堆；