最新《数据结构与算法》期末练习题(含答案)
《数据结构与算法》期末练习
一选择题
1．以下与数据的存储结构无关的术语是（ D ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
2. 算法的时间复杂度取决于（ A ）
A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu
3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
4. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ）
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）
5．对于有n 个结点的二叉树, 其高度为（ D ）
A．nlog2n B．log2n C．?log2n?|+1 D．不确定
6．从下列有关树的叙述中,选出正确的叙述（ C ）
A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B．当K≥1时高度为K的二叉树至多有2k-1个结点。
C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
D．在二叉树中插入结点,该二叉树便不再是二叉树。
7．设无向图的顶点个数为n，则该图最多有（ B ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
8．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
9．下列排序算法中，其中（ D ）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 希尔排序，归并排序
D. 归并排序，冒泡排序
10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84
11. 则采用的排序是 ( A )。
A. 选择
B. 冒泡
C. 快速
D. 插入
12．以下数据结构中，哪一个是线性结构（ D ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
13．下面关于线性表的叙述中，错误的是哪一个？（ B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
14. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。
A. 5 1 2 3 4
B. 4 5 1 3 2
C. 4 3 1 2 5
D. 3 2 1 5 4
15. 设n为正整数.下列程序段中前置以@的语句的频度为（ B ）。
i = 1; k = 0;
do{
@ k+= 10*i;
i++;
}While(i <= n-1);
A. n –1
B. n
C. n + 1
D. n - 2
16. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）
A．?logn?+1 B．logn+1 C．?logn? D．logn-1
17．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。
A. 不确定
B. n-i+1
C. i
D. n-i
18．n个结点的完全有向图含有边的数目（ D ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
19．稳定的排序方法是（ B ）
A．直接插入排序和快速排序 B．折半插入排序和起泡排序
C．希尔排序和四路归并排序 D．树形选择排序和shell排序
20．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。
A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
21．以下那一个术语与数据的存储结构无关？（ A ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表
22．下面关于串的的叙述中，哪一个是不正确的？（ B ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
23. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。
A. a，c，b，d
B. b, c，d，a
C. c, d，b, a
D. d, c，a，b
24.关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ）
A．①②③ B．②③④ C．②④ D．①④
25．高度为 K的二叉树最大的结点数为（ C ）。
A．2k B．2k-1 C．2k -1 D．2k-1-1
26．从下列有关树的叙述中,选出正确的叙述（ C ）
A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B．当K≥1时高度为K的二叉树至多有2k-1个结点。
C．用树的前序遍历和中序遍历可以导出树的后序遍历。
D．哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。
27. 关键路径是事件结点网络中（ A ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
28．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。
A．逆拓扑有序 B．拓扑有序 C．无序的
29．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)
30. 一个向量的第一个元素的地址是begin，每个元素的长度是k ，则第i个元素的地址是( D )
A. begin+(k-1)i
B. begin+(k-2)i
C. begin+ki
D. begin+(i-1)k
31. 有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过( C )次与63比较。
A. 12
B. 6
C. 4
D. 5
32. 一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为( D )。
A.（31，46，70，53，77，82）
B.（46，77，53，31，70，82）
C.（46，31, 82，53，77，70）
D. (46 ，53，31，70，77，82)
33. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A. i
B. n-i
C. n+1
D. n-i+1
34. 不带表头的单链表，头指针为head ，判断其是否为空的条件是( A )
A. head==0
B. head->next==null
C. head==head
D. head->next==head
35. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是( A )。
A) q->next=s; s->next =p B) s->next=p->next; q->next=s;
C) p->nexr=s; s->next=p ; D) p->next=s; s->next=q;
36. 非空循环链表head 的尾结点 *p 满足下列( C )条件
A) head->next==p; B) head==p; C) p->next==head; D) p->next==0
37. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。
A. ecdab B) cebda C) daecb D) abcde
38. 设栈s的类型为sqstack ，判定栈空的条件是( C )。
A. s==NULL B) s->top==0 C) s.top==0 D) s.top==NULL
39. 深度为5 的二叉树至多有个( B )结点。
A. 12
B. 31
C. 14
D. 15
40. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。
A) defbca B) fedbca C) abcdef D) fedcba
41. 一个有n个顶点的有向图最多有( B )弧。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/2
42. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。
A) n(n+1) B) n-1 C) n+1 D) n(n-1)
43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( B )。
A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 2
44. 一个向量的第一个元素的地址是100，每个元素的长度是 2 ，则第五个元素的地址是( C )
A) 102 B) 110 C) 108 D) 120
45. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear ，则队列中元素个数为( A )。（maxlen 为循环顺序表的长度） A. (rear-front+maxlen) % maxlen B. (rear-front) % maxlen C. rear-front+1 D. front-rear+1
46. 一个有n 个顶点的图最少有( D )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0
47. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。 A) 4 B) 5 C) 6 D) 7
48. 设栈s 的类型为sqstack ，最多可容纳maxlen 个元素，则判定栈满的条件是( B )。 A. s==maxlen-1 B) s.top==maxlen-1 C) s->top==maxlen-1 D) s.top==0
49. 一个顺序队列q 的类型为sqqueue,队头、尾指针分别为front,rear ，最多可容纳maxlen 个元素，则队空的条件是( C )。
A) front==rear B) rear==0 C) q.front==q.rear D) rear==maxlen-1
50. 在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B )
A.O(1)
B.O(n)
C.O(nlogn)
D.O(n*n)
51. 链栈与顺序栈相比，比较明显的优点是( D )
A.插入操作更加方便
B.删除操作更加方便
C.不会出现下溢的情况
D.不会出现上溢的情况
52. 二叉树中第5层上的结点个数最多为( C )
A.8
B.15
1 2 3 4
C.16
D.32
53. 下列编码中属前缀码的是( A )
A.{1,01,000,001}
B.{1,01,011,010}
C.{0,10,110,11}
D.{0,1,00,11}
54. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）
A．深度优先搜索算法B．广度优先搜索算法
C．求最小生成树的prim算法D．拓扑排序算法
55. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B )
A.O(1)
B.O(logn)
C.O(n)
D.O(n logn)
56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )
A. (n-1)/2
B. n/2
C. (n+1)/2
D. n
57. 对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41
B.23和39
C.15和44
D.25和51
58. 关于线性表的说法,下面选项正确的是（B ）
A 线性表的特点是每个元素都有一个前驱和一个后继
B 线性表是具有n(n>=0)个元素的一个有限序列
C 线性表就是顺序存储的表
D 线性表只能用顺序存储结构实现
59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（A ）
A (n-1)/2
B n/2
C n
D n-1
60. 设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（ D ）
A p->RLink=s; s->LLink=p;
p->RLink->LLink=s; s->RLink=p->RLink;
B p->RLink=s; p->RLink->LLink=s;
s->LLink=p; s->RLink=p->RLink;
C s->LLink=p; s->RLink=p->RLink;
p->RLink=s; p->RLink->LLink=s;
D s->LLink=p; s->RLink=p->RLink;
p->RLink->LLink=s; p->RLink=s;
61. 栈和队列都是（A ）
A 限制存取位置的线性结构
B 链式存储的非线性结构
C 顺序存储的线性结构
D 限制存取位置的非线性结构
62. 单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（A ）
A O(n)
B O(1)
C O(n*n)
D O(n*logn)
63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（C ）
A n-k
B n-k+1
C |log k n|+1
D |log k n| 其中|k|表示下取整
64. 下列序列中( B )不是堆。
A. 12 36 53 68 48 60 75
B. 12 48 53 68 36 60 75
C. 12 48 36 60 75 68 53
D. 12 36 60 53 48 68 75
65. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。
A. 直接插入排序
B. 简单选择排序
C. 快速排序
D. 希尔排序
66. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem 为栈空间，出栈的元素存放在x中。
A. s.top:=s.top+1;
B. x:=s.elem[s.top];
x:=s.elem[s.top]; s.top:=s.top+1;
C. s.top:=s.top-1;
D. x:=s.elem[s.top];
x:=s.elem[s.top]; s.top:=s.top-1;
67. 已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作( A )；要在p结点后插入s结点应执行操作( D )。
A. p→next:=p→next→next;
B. p→next→next:= →.next;
C. p→next:=s; s→next:=p→next;
D. s→next:=p→next; p→next:=s;
68. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。
A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆
69. 下面给出的四种排序法中( D )排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 快速排序
70. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
二填空题
1、在单链表L中，指针p所指结点有后继结点的条件是：
p->next!=null
2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是：
(请在表达式中用点(.)将数隔开)
23.12.3*2-4/34.5*7/++108.9/+
3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是
60
4、深度为9的完全二叉树具有的个结点
256
5、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是
ABDEGCF
6、先根遍历树林正好等同于按__ _遍历对应的二叉树.
先序
7、构造n个结点的强连通图，至少有_______条弧。
n
8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为
6,9,11,12
9、在单链表指针为p的结点之后插入指针为s的结点的操作是：s->next=p->next;p->next=s;
10、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。
N-1
11、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为
4
13、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始）
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
1 0 1 0 1
1 0 0 1 0
该图的顶点数为该图的边数为顶点3的度为。
5 6 2
14、后根遍历树林正好等同于按__(6) _遍历对应的二叉树。
中序
15、n个结点的完全有向图含有边的数目__(7)
n*（n－l）
16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。时间复杂度
17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。
SXSSXXSSXSSXXX
18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结
点个数是________。
2
19、如图所示的有向无环图可以排出________种不同的拓扑序列。
12
20、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。
75, 66, 48, 29, 31, 37
21、对长度为20的有序表进行二分查找的判定树的高度为________。
5
22、n个顶点的连通无向图，其边的条数至少为________________________。
n-1
23、排序(sorting)有哪几种方法_______________，_____________，____________，
_____________，____________。
直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等
24、下面程序段的时间复杂度为______________。（用O估计）
FOR i:=1 TO n DO
FOR j:=i TO n DO
s=s+j;
O（n*n）
25、非线性结构包括______________和_________________。
树，图
26、在线性表的___________存储结构上进行插入或删除操作要移动元素。
顺序存储结构
27、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front
和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，
队空的条件是_____________________________。
Front=rear, rear+1=front
28、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀
表达式是____________________________。
+*a-bc/de , abc-*de/+
a的最早开始时间和最晚开始时间，则当且
29、在AOE-网中，设e(i)和l(i)分别表示活动i
a为关键活动。
仅当_________________时，i
e(i)==l(i)
30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。
存在回路，123456798
31、二叉排序树的特点是其序列是有序的。
中序遍历
三简答题
1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性；
（3）散列法(hashing)；（4）索引文件。
2、堆与二元查找树的区别?
3、快速分类法的基本思想是什么?
4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？
5、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？
6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。
7、对于一个队列，若入队的顺序为a,b,c, 则所有可能的出队序列是什么？
8、已知一个图如下，试画出其逆邻接链表。
9、若一个栈的输入序列是1,2,3……，n, 其输出序列为p1,p2,……pn,
若p1=n，则pi为多少？
10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？
11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。
12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？
13、栈的存储方式有哪两种？
14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：
单链表和单循环链表的结点结构为
双向链表的结点结构为
15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
16、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。
17、内存中一片连续空间（不妨假设地址从1到m ）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。
18、设某二叉树的前序遍历序列为：ABCDEFGHI ，中序遍历序列为：BCAEDGHFI 。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。
19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。
20、 试证明：若借助栈由输入序列1,2,…,n 得到输出序列为P 1,P 2,…,P n （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 四 算法阅读 1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); } 该算法被调用后得到的输出结果为： 2、void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ 3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) ListInsert(La,1,a[i]); （2）List Delete(La,1,e); ListInsert(La,ListLength(La)+1,e); （3）ClearList(La); For (i=0;i<5;i++) ListInsert(La,i+1,a[i]); 4、int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能； (2)该算法的时间复杂度是多少？ 5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode{ TElemType data; struct BiTNode *LChild, *RChild; }BiTNode, *BiTree; Status A(BiTree T) { Queue Q; InitQueue(Q); ENQueue(Q,T); While(not QueueEmpty(Q)) { DeQueue(Q,e); If(e==NULL) break; Else { Print(e.data); ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); } } } 6.阅读下列函数algo,并回答问题： (1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q) 后的队列q； (2)简述算法algo的功能。 void algo(Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } 五算法填空 1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。 typedef struct node { int data; struct node *next; } lklist; void del( lklist rear, int &x); { lklist p,q; q=rear-> next; if (__________) printf( “it is e mpty!\n” ); else { p=q->next; x=p->data; _________________ ; if (___________) rear=q; ; }; }; 2、堆分配存储方式下，串连接函数。 typedef struct { char * ch； int len； } HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ { int i; char *temp; f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］; for ( ;i temp［i］=t.ch［i-s->len］; s->len+=t.len; fr s->ch=temp; return(1); } 3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<"Memory allocation failare!"< exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 4、L 为一个带头结点的循环链表。函数f30的功能是删除L 中数据域data 的值大于c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) { LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) { pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else { pre=p; (3) ; } return Lc; } 5、已知图的邻接链表的顶点表结点结构为 边表结点EdgeNode 的结构为 下列算法计算有向图G 中顶点v i 的入度。请在空缺处填入合适的内容，使其成为一个完整 的算法。 int FindDegree(ALGraph *G,int i)//ALGraph 为图的邻接表类型 { int dgree, j; EdgeNode *p; degree= (1) ; for(j=0;j p=G->adjlist ［j ］. firstedge; while ( (2) ) { if( (3) ) { degree++; break; } p=p->next; } } return degree; } 六简单应用题 1、已知一个非空二元树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A 试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么? 2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。 3、画出由下面的二叉树转换成的森林。 4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表： 5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。 weight Parent Lchild Rchild weight Parent Lchild Rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6、考虑右图： (1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分) (3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排 列)(6分) 答案如下： 七编写算法题 1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x) 2、设计递归函数，求一棵二叉树的深度。 int depth (bitreptr root) 3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct { int data[ maxsize][maxsize]; int dem,e; }sqgraph; sqgraph crt (sqgraph g) 4、设计函数，将不带表头结点的单链表清除。 5、设计递归函数，求一棵非空的二叉树的深度。 6、设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，删去A 中序号为奇数的结点。 7、试编写一个算法，能由大到小遍历一棵二元树。 8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树? 9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。 10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。 11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。 该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode { ElemType data; Struct LNode* next; }List, LNode; 函数定义：void invert(List & L) 12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{ DataType data; Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree; 函数定义：CountLeaf (BiTree T, int & LeafNum) 13、写出二叉树前根遍历的递归算法 已知二叉树结点定义为： struct node{ elemtp data; struct node *lc,*rc; ); Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点 void preorder(bitreptr P) { If(P!=0) { printf(P->data); preorder(P->lc); preorder(P->rc); } } 14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点