简答题


1.    利用两个栈 S1、S2 模拟一个队列时，如何用栈运算实现队列的入队、出队及判断队空 运算。请简述算法思想。
2.    下图所示为一个二叉树的顺序存储结构，其中空白表示结点不存在。请回答下列问题：
1    2    3    4    5    15



(1)  请画出该二叉树。
(2)  请给出该二叉树的中序序列和后序序列。
3.    从空的平衡二叉排序树开始，按顺序插入关键字 27, 31, 49, 38, 41, 67，请给出最终的平 衡二叉树。假设 6 个关键字的查找概率相等，求该树的平均查找长度。
4.    已知下图：

V1

V4


V0    V2    V6


V5

V3

(1)   请画出该图的邻接表。
(2)   请给出以 V0 为起始结点的深度优先遍历序列和广度优先遍历序列。
5.    有 n  个顶点的无向连通图至少有多少条边？有 n  个顶点的有向强连通图至少有多少条 边？  请举例说明。
6.    判断序列（100，55，73，76，39，80，21，95）是否为堆？如果不是，请将其调整为 堆，并以图示的方式画出调整的过程。

三、 算法设计题


1.    假设算术表达式中只有圆括号，请设计一个算法 int match(char *exp, int &pos)，利用栈 判断一个算术表达式 exp（用字符串表示）中的圆括号是否匹配。若匹配，函数返回 1， 否则，函数返回 0。
 
2.    已知一个带有表头结点的单链表的结点结构为
 
data    link
 
。假设该链表只给出了头
 
指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第
k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返
回 1；否则，只返回 0。