排序时第一趟结束时的序列：
1）希尔排序（第一趟排序的增量为5） 2）快速排序(选第一个记录为枢轴(分隔)) 3）链式基数排序（基数为10）
31、若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9，并且采用链地址方法处理冲
突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。
32、已知二叉树采用二叉链表存储结构，链结点的构造为lchild | data | rchild ，根结点的指针为T。
下面是利用中序遍历的方法统计二叉树中度为1的结点的个数的算法，算法中设置了一顺序存储结构的堆栈STACK [1:M]，栈顶指针为top，请在算法的空缺处填入适当内容，使之能正常工作。
33、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？
34、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07} ,
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。
35、关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }请计算在二分法查找、二叉排序树两种的
情况下等概率下查找成功的平均查找长度。
36、广义表A=（a,b,(c,d),(e,(f,g))）,计算下面式子的值Head(Tail(Head(Tail(Tail(A)))))
37、下图是用邻接表存储的图，画出此图，并写出从C点开始按深度优先、广度优先遍历该图的结
果。
38、用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求
在等概率情况下查找成功的平均查找长度。
39、判断下列序列是否为堆，如果不是请调整为堆，如果是请判断是什么类型的堆（101，88，46，
70，34，39，45，58，66，10）
40、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。 41、找出所有满足下列条件的二叉树
21
a) 它们在先序遍历和中序遍历时,得到的结点访问序列相同； b) 它们在后序遍历和中序遍历时,得到的结点访问序列相同； c) 它们在先序遍历和后序遍历时,得到的结点访问序列相同。
42、已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点。
a)在P结点后插入S结点的语句序列是______ b)在P结点前插入S结点的语句序列是______ c)在表首插入S结点的语句序列是______ d)在表尾插入S结点的语句序列是______ (1) P->next=S;
(2) P->next=P->next->.next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NIL; (7) Q=P;
(8) WHILE P->next<>Q P=P->next;
(9) WHILE P->next!=NULL P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P;
43、已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA，请画出树T。
22
44、对关键字序列（72，87，61，23，94，16，5，58）进行堆排序、快速排序、直接选择排序，使
之关键字递增有序，请写出每个排序的前三趟结果。 45、请画出广义表D的图形表示D=(D,(a,b),((a,b),c),( ))
46、若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个1度顶点？
47、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针 p ，能否将
p 所指结点的数据元素与其确实存在的直接前驱交换 ? 请对每一种链表作出判断，若可以，写出程序段；否则说明理由。
单链表和单循环链表的结点结构为
date next 双向链表的结点结构为
prior date
(1) 单链表 (2) 单循环链表 (3) 双向链表
47、已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，
48，32，50，68)。要求：
(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2)若要用该散列表查找元素68，给出所需的比较次数。
48、已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升
序排序，并给出每一趟的排序结果。
49、已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
A B C D E F next 50、设有一个关键码的输入序列
{ 55, 31, 11, 37, 46, 73, 63, 02, 07 }
(1)从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树 的形态。 若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。
(2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。
51、求下列广义表运算的结果：
1) HEAD(p,h,w); 2) TAIL (b,k,p,h); 3) HEAD ((a,b),(c,d)); 4) TAIL (a,b),(c,d);
23
5) HEAD（TAIL（（(a,b),(c,d)））） 6) TAIL（HEAD((a,b),(c,d))）
52、画出下列广义表的图形表示：
1) D（A（）），B（e），C（a,L(b,c,d)） 2) J1(J2,(J1,a,J3(J1)),J3(J1))
53、完成下列要求：
1） 请画出下列广义表的存储结构
（(((a),b)),(((),(d)),(e,f))） 2）请写出下面链表表示的广义表
54、一棵二叉树如图：
1) 写出对此树进行中序、先序、后续遍历时得到的结点序列。 2) 画出树的后序线索二叉树。
55、具有3个节点的树和具有3个节点的二叉树它们的所有不同形态有哪些？ 56、将下列森林转化为二叉树。
24
57、已知一个图如下所示，写出其临接矩阵，并从顶点a出发按深度优先搜索、按广度优先搜索，
则可以得到所有顶点序列为什么？
58、试问在直接插入排序、希尔排序、快速排序、归并排序、二分法排序、直接选择排序中，哪些
排序是稳定的？哪些是不稳定的，哪个排序平均比较次数最少？哪个排序要求内存容量最多？ 59、哈希表中使用哈希函数H（key）=3 * key % 11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为： d1=H (key )
di=( di-1 +7 * key ) % 11 （I=2,3?..）
试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。
60、什么是内部排序？什么是排序方法的稳定性？说出你所学过的三个稳定算法，一个不稳定算法。 61、何为队列上溢？一般用什么方法解决，简述之。 62、载入下图所示的有权图G，回答下列问题：
1） 给出从结点v1出发按深度优先搜索遍历图所得的结点序列； 2） 给出图的拓扑序列；
3） 给出从结点v1到结点v8的最短路径和关键路径。
63、对于下图，请给出
1） 对应的邻接矩阵，并给出A,B,C三个顶点的入度和出度； 2） 邻接表表示和逆邻接表表示； 3） 求其连同分量；
25