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

一、填空题

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

initstack(S)置S 为空栈； push(S，X) 元素X 入栈； pop(S)出栈操作； gettop(S)返回栈顶元素； sempty(S)判栈空函数； setnull(St)置串St 为空串； length(st)返回串st 的长度；

equal(S1，S 2) 判串S 1并S 2是否相等的函数； concat(S1，S 2) 返回联接S 1和S 2之后的串； sub(S，i ，1) 返回S 中第i 个字符； empty(st)判串空函数

FUNCinvert(pre:string ；V ARexp :string) :boolean ；

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

)

_____；_____；

_____THEN_____

IF_____THEN_____

(_____，_____)；

(_____，_____)；

_____

_____THEN

注意:每个空格只填一个语句。

【答案】(1)initstack(S)//栈s 初始化为空栈 (2)setnull(exp)//串exp 初始化为空串 (3)chinopset//判取出字符是否是操作符

(4)push(s，ch)//如ch 是运算符，则入操作符栈s (5)sempty(s)//判栈s 是否为空

(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理 (7)exp

(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式 (9)exp

(10)gettop(s)//取栈顶操作符 (11)pop(s)//操作符取出后，出栈

(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后

2． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

3． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

4． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

5． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。

【答案】2(n－1)

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。

6． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

7． 建立索引文件的目的是_____。

【答案】提高查找速度

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

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；

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

9． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

("图有回路") ;

【答案】

其含义为数据data 入栈，出栈和测试栈是否空(不空返

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

10．阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。