数据结构习题及答案(5)

（注：原题为选择题：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15）

三、单项选择题（每小题1分，共11分）

（ C ）1． 不含任何结点的空树 是一棵树也是一棵二叉树 。

（ C ）2．二叉树是非线性数据结构，所以 顺序存储结构和链式存储结构都能存储 。

（ C ）3. 〖01年计算机研题〗 具有n(n>0)个结点的完全二叉树的深度为 ? log2(n) ?+1 。

注1：?x ?表示不小于x的最小整数；? x?表示不大于x的最大整数，它们与[ ]含义不同！ 注2：选（A）是错误的。例如当n为2的整数幂时就会少算一层。似乎? log2(n) +1?是对的？ （ A ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 唯一的 。 5. 【94程P11】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

树是结点的有限集合，它A 根结点，记为T。其余的结点分成为m（m≥0）个 B 的集合T1，T2，?，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。 供选择的答案

A： ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上

B: ①互不相交 相交

C： ①权 ② 维数 ③ 次数（或度） ④ 序 答案：ABC＝1，1，3

6. 【95程P13】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。 供选择的答案

A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点

② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点

的树形结构

B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟

C～D： ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟

⑤ 最左的兄弟 ⑥ 最右的兄弟

答案：A= B= C= D＝ 答案：ABCDE＝2，1，1，3

四、简答题（每小题4分，共20分）

1. 【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

2. 设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题： C的结点类型定义如下： (1)对下列二叉树B，执行下列算法traversal(root)，试指出其struct node {char data; 输出结果；答：ABCEDFG

struct node *lchild, rchild; (2)假定二叉树B共有n个结点，试分析算法traversal(root)

}; 的时间复杂度。（每问4分，两问共8分）

C算法如下： A void traversal(struct node *root) B D {if (root) 二叉树B C F G {printf(“%c”, root->data); E traversal(root->lchild); printf(“%c”, root->data);

traversal(root->rchild);

}

}

3.【严题集6.27③】给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，

试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 D

A C F

H I

B E G

4.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。 中序遍历序列：55 40 25 60 28 08 33 54

28

28 25 33 40 60 08 54 55 N

5N0 08 54 4 40 6 60 54

55

2 25

233 3五、阅读分析题（每题5分，共20分）

1. （P60 4-26）试写出如图所示的二叉树分别按先序、 中序、后序遍历时得到的结点序列。 答：DLR：A B D F J G K C E H I L M

LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A

2. （P60 4-27）把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左

子树，新添连线结点一律归入右子树。

3.【严题集6.17③】阅读下列算法，若有错，改正之。

BiTree InSucc(BiTree q){ //已知q是指向中序线索二叉树上某个结点的指针， //本函数返回指向*q的后继的指针。 r=q->rchild; if(!r->rtag) while(!r->rtag)r=r->rchild; return r; }//ISucc

4.【严题集6.21②】画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。

六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）

1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。

2. 写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 3．【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

4. 【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。

5. 【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。

6. 【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

第7章 图 自测卷解答

一、单选题（每题1分，共16分）

（ 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. 图

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题及答案(5)在线全文阅读。