好文档 - 专业文书写作范文服务资料分享网站

数据结构习题集与实验指导

天下 分享 时间: 加入收藏 我要投稿 点赞

v1.0 可编辑可修改 if(d>p) p=d; /*向上回朔时,要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; } p=p+1; return(p); } 法二:

int Get_Sub_Depth(Bitree T,int x)写按层次顺序(同一层自左至右)遍历二叉树的算法。 或:按层次输出二叉树中所有结点;

解:思路:既然要求从上到下,从左到右,则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法,用while语句不断循环,直到队空之后自然退出该函数。

技巧之处:当根结点入队后,会自然使得左、右孩子结点入队,而左孩子出队时又会立即使得它的左右孩子结点入队,……以此产生了按层次输出的效果。 level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r;

f=0; r=0; /*置空队*/ r=(r+1)%max;

q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max);

p=q[f]; /*出队*/

printf(\打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空,则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空,则右子树进队*/ }

return(0);

3131

v1.0 可编辑可修改 } 法二:

void LayerOrder(Bitree T)已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中,试编写一个算法打印出编号为i的结点的双亲和所有的孩子。

答:首先,由于是完全二叉树,不必担心中途会出现孩子为null的情况。 其次分析:结点i的左孩子为2i,右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;); 但其双亲是i/2,需先判断i为奇数还是偶数。若i为奇数,则应当先i-- ,然后再除以2。 If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;); 5.编写算法判别给定二叉树是否为完全二叉树。

答:int IsFull_Bitree(Bitree T)相比,作了一个修改,不管当前结点

是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针.

6.假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为,,,,,,,。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。

解:方案1;哈夫曼编码

先将概率放大100倍,以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10},按哈夫曼规则:【[(2,3),6], (7,10)】, ……19, 21, 32

(100) (40) (60)

0 1 0 1 19 21 32 (28) 19 (17)

(11)

21 32 0 3232

0 1 1 7 10 6 (5)

0 1 0 1 v1.0 可编辑可修改 2 3

方案比较:

字母编号 对应编码 1 2 3 1100 00 11110 出现频率 字母编号 对应编码 出现频率 1 2 3 4 000 001 010 011 方案1的WPL=2+++4+++5+=++= 方案2的WPL=3+++++++=3 结论:哈夫曼编码优于等长二进制编码 第六章 图 一、单选题

( C )1. 在一个图中,所有顶点的度数之和等于图的边数的 倍。

A.1/2 B. 1 C. 2 D. 4

( B )2. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 倍。

A.1/2 B. 1 C. 2 D. 4

( B )3. 有8个结点的无向图最多有 条边。

A.14 B. 28 C. 56 D. 112

( C )4. 有8个结点的无向连通图最少有 条边。

A.5 B. 6 C. 7 D. 8

( C )5. 有8个结点的有向完全图有 条边。

A.14 B. 28 C. 56 D. 112

( B )6. 用邻接表表示图进行广度优先遍历时,通常是采用 来实现算法的。

A.栈 B. 队列 C. 树 D. 图

( A )7. 用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。

A.栈 B. 队列 C. 树 D. 图

3333

v1.0 可编辑可修改 ( C )8. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是

?0?1??1??1?1??0?1?111101?001001??000100??100110?011010??001101?100010??A.0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D. 0 3 6 1 5 4 2

( D )9. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按深度优先遍历的结点序列是

A. 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4

2 5 6( B )10. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是

A. 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4

2 5 6

(建议:0 1 2 3 4 5 6)

( C )11. 已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是

A. 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4

5 6

( D )12. 已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是

A.0 1 3 2 B. 0 2 3 1

( A )13. 已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是

A.0 3 2 1 B. 0 1 2 3

( A )14. 深度优先遍历类似于二叉树的

3434

v1.0 可编辑可修改 A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

( D )15. 广度优先遍历类似于二叉树的

A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

( A )16. 任何一个无向连通图的最小生成树

A.只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 (注,生成树不唯一,但最小生成树唯一,即边权之和或树权最小的情况唯一)

二、填空题

1. 图有 邻接矩阵 、 邻接表 等存储结构,遍历图有 深度优先遍历 、 广度优先遍历 等方法。 2. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 出度 。

3. 如果n个顶点的图是一个环,则它有 n 棵生成树。 (以任意一顶点为起点,得到n-1条边)

4. n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为 O(n) 。 5. n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 O(n+e) 。 6. 设有一稀疏图G,则G采用 邻接表 存储较省空间。 7. 设有一稠密图G,则G采用 邻接矩阵 存储较省空间。 8. 图的逆邻接表存储结构只适用于 有向 图。

9. 已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。

10. 图的深度优先遍历序列 不是 惟一的。

11. n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为 O(n) ;若采用邻接表存储时,该算法的时间复杂度为 O(n+e) 。

12. n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为 O(n) ;若采用邻接表存储,该算法的时间复杂度为 O(n+e) 。

13. 图的BFS生成树的树高比DFS生成树的树高 小或相等 。

14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n) ;用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。

15. 若要求一个稀疏图G的最小生成树,最好用 克鲁斯卡尔(Kruskal) 算法来求解。 16. 若要求一个稠密图G的最小生成树,最好用 普里姆(Prim) 算法来求解。

17. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。

18. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。

222

2

三、简答题

1.已知如图所示的有向图,请给出该图的:

3535

数据结构习题集与实验指导

v1.0可编辑可修改if(d>p)p=d;/*向上回朔时,要挑出左右子树中的相对大的那个深度值*/d=depth(root->rchild);if(d>p)p=d;}p=p+1;return(p);}法二:intGet_Sub_Depth(BitreeT,intx)写按层次顺序(同一层自左至右)遍历二叉树的算法。或:按层
推荐度:
点击下载文档文档为doc格式
5nyv1117md23x6i11fyp2nsft0iv0l00r4h
领取福利

微信扫码领取福利

微信扫码分享