数据结构复习题目

三、解答题

16．对如图5.32所示的树，画出其孩子兄弟链表存储结构． 孩子兄弟链表如下图所示： A ∧ D B E ∧ C ∧ F G H ∧ 17．对B E F 图 5.32 A C G a b c H D d e f g 如图5.33所示的二叉树，分别写出其前序、中序、后序遍历序列． 前序遍历序列：abdehcfgi，中序遍历序列：dbheafcig后序遍历序列：h i a dhebfigca． 图 5.33 b d 18．已知一棵二叉树的中序遍历序列为cbafehgd，后序遍历序列为cbfhgeda，画出此二叉树． c e 由后序遍历序列可知该二叉树根节点为a，进而由中序遍历序列知a的左孩子为b，f g b的左孩子为c，没有右孩子，由中序遍历序列和后序遍历序列的规则继续类推可得a的右孩子为d，d的左孩子为e，没有右孩子，e的左孩子为f，右孩子为g，g的左孩h 子为h，没有右孩子．得二叉树如右图所示： A 19．画出如图5.34所示二叉链表树的中序线索二叉树． 易知中序遍历序列为CHBAFEGD，故中序线索二叉树如 B ∧ D ∧ 下图所示： A B C F E G 55 D ∧ C ∧ H ∧ ∧ F ∧ 图 5.34 E ∧ G ∧ 100 45 20．用分别以8，11，13，5，17，25，21作为权值的叶结点，构造一棵哈夫曼树，并求该二叉树的带权路径长度WPL． 哈夫曼树如图所示：易得带权路径长度 WPL?(5?8)?4?(11?13?17)?3?(21?25)?2?267． 21．假设用于通信的电文仅由8种字母a、b、c、d、e、f、g、h组成，字母在电文中出现的频率分别为0.10、0.07、0.16、0.05、0.19、0.23、0.12、0.08．试为这8个字母设计哈夫曼编码． 构造哈夫曼树如图所示： a的编码为1101，b的编码为0011，c的编码为111， d的编码为0010，e的编码为01，f的编码为10， g的编码为000，h的编码为1100．

13 30 25 24 21 17 11 100 13 5 8 43 24 12 5 12 7 57 19 23 18 8 10 34 16

四、算法设计题

22．以二叉链表作为存储结构，试利用指针数组实现编写非递归的前序遍历二叉树的算法．

void Preorder(BinTree bt) { }

BinNode *s[n]; top ? ?1; do

{ }

}

if (top !? ?1) }

while (top !??1 && bt !? null);

{

//取父结点指针 //访问右子树

bt ? s[top]; top ? top ?1; bt ? bt ?> rchild; while (bt !? null) { printf(“%c”,bt ?> data); top ? top + 1; s[top] ? bt;

//存父结点指针 //访问左子树

bt ? bt ?> lchild;

//访问根结点和子树根结点

23．以二叉链表作为存储结构，其根结点指针为bt，试写从根开始按层遍历二叉树的算法．

typedef struct int hp, tp;

BinTNode *dt[maxlen]; }lqueue;

void Layar(BinTree bt) {

lqueue lq; if (bt != null){ } }

lq.hp = 0; lq.rp = 0; lq.dt[1] = bt; do

{ }

lq.hp = (lq.hp % maxlen) + 1; bt = lq.dt[lq.hp]; printf(“m”,bt ?> data); if (bt -> lchild != null) { }

if (bt -> rchild != null) { }

while (lq.hp != lq.rp);

lq.rp = (lq.rp % maxlen) + 1; lq.dt[rp] = bt.rchild; lq.rp = (lq.rp % maxlen) + 1; lq.dt[rp] = bt.lchild; {

printf(“\\n”);

24．以中序线索二叉链表为存储结构，试写查找某结点*p的中序前趋结点的算法．

BinThrNode *InorderPred(BinThrNode *p) {

BinThrNode *q; if (p ?> ltag ?? 1)

//若p左子树为空

return p ?> lchild;

//返回左线索所指的中序前趋

else {

q ? p ?> lchild;

//左子树非空，从p的左子树开始查找

while (q ?> ltag ?? 0)

q ? q ?> rchild;

//右子树非空，延右链查找

return p;

}

} 第6章 图

练习题

一、单项选择题

1．在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边

A．n B．n?1 C．n?1 D．n/2 2．无向图的邻接矩阵是一个

A．对角矩阵 B．对称矩阵 C．上三角矩阵 D．零矩阵 3．采用邻接表存储的图的深度优先遍历算法类似于二叉树的

A．按层遍历 B．前序遍历 C．中序遍历 D．中序遍历 4．采用邻接表存储的图的宽度优先便利算法类似于二叉树的

A．按层遍历 B．前序遍历 C．中序遍历 D．中序遍历 5．设无向连通图G中顶点数为n，则图G中最少有多少条边

A．n(n?1) B．n?1 C．n?1 D．2n 6．若图G为n个顶点的有向图，则图G中最多有多少条边

A．n(n?1) B．n?1 C．n(n?1) D．n(n?1)/27．在一个图G中所有顶点度数之和等于边数的

A．3倍

B．

12倍 C．4倍

D．2倍 8．在具有n个顶点的无向完全图G中边的总数为

A．n?1 B．n(n?1)/2 C．n(n?1)

D．n?1

9．在具有6个顶点的无向图G中至少应有多少条边才能确保是一个连通图 A．8 B．7 C．6 D．5 10．一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是

A．n?1

B．n?1

C．n2

D．(n?1)2

C）B）B）A）B）A）D）B）D）C）

（ （ （ （ （ （ （

（ （ （

二、填空题

11．邻接表是图的链式存储结构．

12．一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图． 13．一个带权的无相连通图的最小生成树有一棵或多棵． 14．n个顶点的连通图最多有n(n?1)/2条边．

15．设图G有n个顶点和e条边，进行深度优先搜索的时间复杂度至多为O(n?e)，进行广度优先搜索的时间复杂度至多为O(n?e)．

16．在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于1．

17．已知图G的邻接表如图6.25所示，其从顶点v1出发的深度优先搜索序列为v1、v3、v4、v5、v2，其从顶点v1出发的广度优先搜索序列为v1、v3、v2、v4、v5． 18．已知一个有向图G的邻接矩阵表示，计算第i个结点的入度的方法是计算第i列非零元素的个数．

19．图的生成树不是唯一的，一个连通图的生成树是一个极小连通子图，n个顶点的生成树有n ? 1条边．

20．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为n，所有邻接表中的结点总数是2e．

V1 V2 ∧ V3 V4 ∧ V5 3 4 2 2 5 ∧ 4 ∧ 4 ∧ 图6.25 一个图的邻接表

三、应用题

?0?121．已知一个图的邻接矩阵为?1??0??0对应的图如下图所示：

1011111011011010?1?1?，假设顶点是v0，v1，?，画出对应的图． ?1?0??v2

v1

v3

v4 2 v5

1 5 6 3 图6.27 一个有向图

22．对于如图6.27所示的有向图，试给出：

（1）图的邻接矩阵； （2）邻接表和逆邻接表； （3）强联通分量．

4 ?0?1?0图的邻接矩阵为??0?1??0V1 V2 V3 V4 ∧ V5 V6 4 1 4 0000110100001010100010010?0?1??，邻接表、逆邻接表、强联通分量如下图所示： 0?0?0??V1 V2 6 ∧ V3 V4 4 ∧ V5 V6 3 ∧ 5 2 5 ∧ 1 2 2 5 2 ∧ 1 3 3 ∧ 5 ∧ 6 ∧ 2 6 ∧ 5 ∧ 5 1 6 2 3 4