数据结构试卷选题.doc

一、选择题
1.计算机算法指的是（ ）
A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
2．算法必须具备的三个特性是（ ）
A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
3．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.
4. 下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
5．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
6．以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
7. 下列数据中，（ ）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆
8．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
9.下述哪一条是顺序存储结构的优点？
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
10.下面关于线性表的叙述中，错误的是哪一个？
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
11.线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项
12.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
13. 链表不具有的特点是（ ）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
14．非空的循环单链表head的尾结点p↑满足（ ）。
A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head
15．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
16．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
17. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
18. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，
D. 4，3，1，2， E. 3，2，1，4，
19. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
20. 设abcdef以所给的次序进栈，若在进栈时允许退栈,则下面得不到的序列为（ ）。
A．fedcba B. bcafed C. dcefba D. cabdef
21. 若一个栈V[1..100]，目前栈顶指针top为20，则x进栈的正确操作是( )。
A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1
22. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A、Ｂ和Ｃ
23. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
24. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
25. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
26. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
27. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
28. 栈和队都是（ ）
A．顺序存储的线性结构 B. 链式存储的非线性结构
C. 限制存取点的线性结构 D. 限制存取点的非线性结构
30. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。
A. 808 B. 818 C. 1010 D. 1020
31. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
32.．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定
33．具有10个叶结点的二叉树中有（ ）个度为2的结点，
A．8 B．9 C．10 D．ll
34. 有关二叉树下列说法正确的是（ ）
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
35．二叉树的第I层上最多含有结点数为（ ）
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
36. 一个具有1025个结点的二叉树的高h为（ ）
A．11 B．10 C．11至1025之间 D．10至1024之间
37．在下列存储形式中，哪一个不是树的存储形式？（ ）
A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法
38．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
39．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
40．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
A．acbed B．decab C．deabc D．cedba
41. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：
A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对
42．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：
A、 E B、 F　 C、 G　 D、 H
43．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A．所有的结点均无左孩子 B．所有的结点均无右孩子
C．只有一个叶子结点 D．是任意一棵二叉树
44．在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点　 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
45．由3 个结点可以构造出多少种不同的二叉树？（ ）
A．2 B．3 C．4 D．5
46．下述编码中哪一个不是前缀码（ ）。
A．（00，01，10，11） B．（0，1，00，11）
C．（0，10，110，111） D．（1，01，000，001）
47．下面几个符号串编码集合中，不是前缀编码的是（ ）。
A．{0,10,110,1111} B．{11,10,001,101,0001}
C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}
48．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
49．一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
50．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n
51．n个结点的完全有向图含有边的数目（　　　）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
52．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4
53． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；如果是无向图，则共有（③）条边。
①．A．9 B．3 C．6 D．1 E．以上答案均不正确
②．A．5 B．4 C．3 D．2 E．以上答案均不正确
③．A．5 B．4 C．3 D．2 E．以上答案均不正确
54．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。
A． B． C． D．+
55. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
56．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
57. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个

第17题图 第18题图
58.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。
①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确
②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确

59．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ ）。
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
60. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧<Vi，Vj> B．G中有一条从Vi到Vj的路径
C．G中没有弧<Vi,Vj> D．G中有一条从Vj到Vi的路径

二、判断题
1. 数据元素是数据的最小单位。( )
2. 记录是数据处理的最小单位。 ( )
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )
4．算法的优劣与算法描述语言无关，但与所用计算机有关。( )
5．程序一定是算法。( )
6．数据的物理结构是指数据在计算机内的实际存储形式。( )
7. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
8. 链表中的头结点仅起到标识的作用。( )
9. 顺序存储结构的主要缺点是不利于插入或删除操作。( )
10．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )
11. 对任何数据结构链式存储结构一定优于顺序存储结构。( )
12．顺序存储方式只能用于存储线性结构。( )
13. 线性表的特点是每个元素都有一个前驱和一个后继。( )
14. 循环链表不是线性表. ( )
15. 线性表只能用顺序存储结构实现。( )
16. 线性表就是顺序存储的表。( )
17．为了很方便的插入和删除数据，可以使用双向链表存放数据。( )
18. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )
19. 栈是实现过程和函数等子程序所必需的结构。（ ）
20. 栈与队列是一种特殊操作的线性表。（ ）
21. 栈和队列都是限制存取点的线性结构。（ ）
22. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
23. 通常使用队列来处理函数或过程的调用。（ ）
24. 循环队列通常用指针来实现队列的头尾相接。（ ）
25. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
26. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ）
27. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）
28. 数组不适合作为任何二叉树的存储结构。（ ）
29. 数组是同类型值的集合。（ ）
30. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
31. 二叉树是度为2的有序树。
32. 完全二叉树一定存在度为1的结点。
33. 二叉树的遍历结果不是唯一的.
34．对一棵二叉树进行层次遍历时，应借助于一个栈。
35．由一棵二叉树的前序序列和后序序列可以唯一确定它。
36．完全二叉树中，若一个结点没有左孩子，则它必是树叶。
37. 二叉树只能用二叉链表表示。
38. 给定一棵树，可以找到唯一的一棵二叉树与之对应。
39. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
40．树形结构中元素之间存在一个对多个的关系
41．完全二叉树的存储结构通常采用顺序存储结构。
42．将一棵树转成二叉树，根结点没有左子树；
43．二叉树是一般树的特殊情形。
44．树与二叉树是两种不同的树型结构。
43. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。
44. 二叉树中序线索化后，不存在空指针域。
46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。
47. 哈夫曼树无左右子树之分。
48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。( )
51．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）
52．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=。（ ）
53. 有e条边的无向图，在邻接表中有e个结点。（ ）
54. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ）
55. 强连通图的各顶点间均可达。（ ）
56．邻接多重表是无向图和有向图的链式存储结构。（ ）
57. 十字链表是无向图的一种存储结构。（ ）
58. 无向图的邻接矩阵可用一维数组存储。（ ）
59．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ）
60. 有向图的邻接矩阵是对称的。（ ）
61．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）
62．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）
63．任何无向图都存在生成树。（ ）
64. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ）
65．带权无向图的最小生成树必是唯一的。（ ）
66. 最小代价生成树是唯一的。（ ）
67．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
68．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（ ）
69．拓扑排序算法仅能适用于有向无环图。（ ）
70. 关键路径是AOE网中从源点到终点的最长路径。（ ）

三、填空
1．数据的物理结构包括 的表示和 的表示。
2．数据的逻辑结构是指 。
3．数据结构中评价算法的两个重要指标是
4． 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出。
5．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
6．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;
7．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
8．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
9.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
10. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________
11. 在单链表L中，指针p所指结点有后继结点的条件是：__
12. 在单链表p结点之后插入s结点的操作是：_______。
13．栈是_______的线性表，其运算遵循_______的原则。
14．_______是限定仅在表尾进行插入或删除操作的线性表。
15. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
16．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。
17. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。
18．________又称作先进先出表。
19. 队列的特点是_______。
20．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
21. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。
22．区分循环队列的满与空，只有两种方法，它们是______和______。
23．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_______。
24．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
25.数组的存储结构采用_______存储方式。
26.设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。
27.整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。
27.有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。
28.已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。
29．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。
30．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。
31．线索二元树的左线索指向其______，右线索指向其______。
32．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
33．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。
34．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。
35.判断一个无向图是一棵树的条件是______。
36．具有10个顶点的无向图，边的总数最多为______。
37．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。
38. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______
39. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
40．在有n个顶点的有向图中，每个顶点的度最大可达______。
41．设G为具有N个顶点的无向连通图，则G中至少有______条边。
42．N个顶点的连通图的生成树含有______条边。
43．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。
44. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
45. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
46. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。
47. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。

48．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
49．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。

四、问答题
1. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？
2. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？
3．线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
4．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
5．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？
6．线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。
7. 试述头结点,首元结点,头指针这三个概念的区别.
8．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
9. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。
10. 设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。

11. ① 试找出满足下列条件的二叉树
1）先序序列与后序序列相同 2）中序序列与后序序列相同
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
② 已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。
12．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
N

P

G

H

J

M

O

L

I

K

E

D

F

B

A

C

L

J

G

I

A

B

E

F

K

C

D

H

M

O

N

P

13．对下图所示二叉树分别按前序﹑中序﹑后序遍历，
给出相应的结点序列，同时给二叉树加上中序线索。

14. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。
15.假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。
16.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3，21,10。试为这8个字母设计哈夫曼编码。
17.给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。
18. 以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。
19．解答问题。设有数据逻辑结构为：
B = (K, R), K = {k1, k2, …, k9}
R={<k1, k3>, <k1, k8>, <k2, k3>,<k2, k4>, <k2, k5>, <k3, k9>,<k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>}
（1）．画出这个逻辑结构的图示。（3分）
（2）．相对于关系r, 指出所有的开始接点和终端结点。（2分）
（3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。（4分）
（4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。（6分）
20． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
21．下面的邻接表表示一个给定的无向图
（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；
（2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。
3

6

7

5

8

9

4

2

1

3

10

5

7

8

4

2

1

6

9

21题图 20题图 22题图
22．给出图G：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。
23．如下所示的连通图，请画出以顶点①为根的深度优先生成树；

8
9

7

1

2

4

5

6

3

10

23题图

24．已知无向图如下所示：
（1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表；
（3）．画出从V1开始深度优先搜索生成树。

第24题图 E

A

B

G

C

D

F

5

3

6

1

4

1

3

2

5

25．考虑右图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，
求它的最小生成树

26．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
1

2

6

5

4

3

20

10

11

6

6

18

10

14

5

9

26题图
27．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。

1