厦门大学数据结构与算法（陈海山）期末习题答案解析(3)

mn ? n + 1 ? ?

k

k

0

0

k

k

叶子结点为

3-5 对于任意非空二叉树，要设计出其后序遍历的非递归算法而不使用栈结构，最适合的方法是对该二叉树采用( )存储结构。

(A) 二叉链表 (B) 三叉链表 (C) 索引 (D) 顺序

B

解析：三叉链表比二叉链表多一个指向父结点的指针

3-6 一棵二叉树的叶子结点在其先序、中序和后序序列中的相对位置( )。

(A) 肯定发生变化 (B) 可能发生变化 (C) 不会发生变化 (D) 无法确定 B

解析：举例子说明即可

3-7 设二叉树T按照二叉链表存储，试分析下列递归算法的主要功能。 int F(BiTree T) {

if (!T) return 0;

if (!T->Lchild && !T->Rchild) return 1; return F(T->Lchild)+F(T->Rchild); }

求二叉树T的叶子结点数 int F(BiTree T) {

if (!T) return 0;

if (!T->Lchild && !T->Rchild) return 1; return F(T->Lchild)+F(T->Rchild)+1; }

求二叉树T的结点数

3-8 已知二叉树T的先序序列为ABCDEF，中序序列为CBAEDF, 则T的后序序列为( )。

(A) CBEFDA (B) FEDCBA (C) CBEDFA (D) 不确定

A

3-9 简述由先序序列和中序序列构造二叉树的基本操作方法。

1）取先序遍历序列的第一个值，用该值构造根结点，，然后在中序遍历序列中查找与该元素相等的值，这样就可以把序列分为三部分：左子树（如果有）、根结点和右子树（如果有）。 2）将两个序列都分成三部分，这样就分别形成了根结点的左子树和右子树的先序遍历和后序遍历的序列。

3）重复1）和2）步骤，直至所有结点都处理完就可以完整构成一颗二叉树了。

3-10 已知二叉树的先序序列为ebadcfhgikj，中序序列为abcdefghijk，试画出该二叉树。

e

b f a d h c g i k j 3-11 已知二叉树T的中序序列和后序序列分别为 (中序) 3, 7, 11, 14, 18, 22, 27, 35 (后序) 3, 11, 7, 14, 27, 35, 22, 18 试画出二叉树T。 18 14 22 7 35 3 11 27

3-12 已知二叉树T按照二叉链表存储，设计算法，计算T中叶子结点的数目。

int F(BiTree T) {

if (!T) return 0;

if (!T->Lchild && !T->Rchild) return 1; return F(T->Lchild)+F(T->Rchild); }

3-13 已知二叉树T按照二叉链表存储，设计算法，交换T的左子树和右子树。 递归：

Int ExchangeBTree(BiTree T) {

temp=(BiTree) malloc(sizeof(BiTNode)); if(!T) return;

if(!T->lchild&&!T->rchild) return; temp=T->lchild;

T->lchild=T->rchild; T->rchild=temp;

ExchangeBTree(T->lchild); ExchangeBTree(T->rchild);

}

3-14 先序后继线索化算法是根据二叉链表建立先序后继线索二叉链表，其基本原则是在前驱空指针域中写入后继线索，即将右子树的( )指针写入左子树的最后一个叶子结点右指针域。

(A) 线索 (B) 根结点 (C) 前驱结点 (D) 后继结点

C

3-15 设计算法，在先序线索二叉树中，查找给定结点p在先序序列中的后继。

线索二叉树：根据某次遍历, 在二叉树中的相关空指针域都写入线索(后继线索或前驱线索)，即成为线索二叉树。

线索二叉树可理解为已经线索化的二叉树。 先序后继：先序遍历中得到的后继(先序前驱, 中序后继, 中序前驱, 后序后继, 后序前驱)。 线索二叉树的存储结构 typedef struct Node {

Type data；//数据元素域

struct Node *Lchild；//左孩子域 struct Node *Rchild；//右孩子域

int Tag；//0: 分支结点, 1: 叶子结点 } BiTNode，*BiTree； findBirthNode(BiTNode p) {

If(p->tag==0)//p的左子树非空,指向左子树 Return p->Lchild;

Else //p为空，后驱则是右子树 Return p->Rchild; }

3-16 设计一种二进制编码，使传送数据 a，act，case，cat，ease，sea，seat，state，tea的二进制编码长度最短。 要求描述：

(1)数据对象；a,c,t,s,e (2)权值集；8,3,5,5,6 (3)哈夫曼树；略

(4)哈夫曼编码。00,010,011,10,11

3-17 按照“逐点插入方法”建立一个二叉排序树，树的形状取决于( )。

(A) 数据序列的存储结构 (B) 数据元素的输入次序

(C) 序列中的数据元素的取值范围

(D) 使用的计算机的软、硬件条件

B

显然D错误，A也错误因为大小是相对的，对于C，1，3,5 和1，10,100相对位置一样，假若插入次序也一样的话，树的形状也不会变得，所以选B

3-18 用利用逐点插入法建立序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)对应的二叉排序树以后，查找元素35要在元素间进行( )次比较。

(A) 3 (B) 4 (C) 5 (D) 8 B

1 2 3 4

20 30

35

43

45

50 72 65 85 75

3-19 在平衡二叉树中，插入关键字46后得到一颗新的平衡二叉树。在新的平衡

二叉树中，关键字37所在结点的左、右孩子结点中保存的关键字是( )。

(A) 18，46 (B) 25，46 (C) 25，53 (D) 25，69

C

3-20 用依次插入关键字的方法，为序列{ 5, 4, 2, 8, 6, 9 }构造一棵平衡二叉树(要求分别画出构造过程中的各棵不平衡二叉树)。

每次都将平衡树平衡

3-21 给定n个整数，设计算法实现： (1) 构造一棵二叉排序树； (2) 从小到大输出这n个数。

int SearchBST(BiTree T, int key, BiTree &p) {

//在T中递归查找关键字值=key的数据元素 if (!T) return 0; //查找不成功

if (key==T->key) return 1; //查找成功 p=T; //p记录双亲结点

if (keykey) return SearchBST(T->lchild, key, p);

return SearchBST(T->rchild, key, p); } //SearchBST

// 二叉排序树的插入算法

void InsertBST(BiTree &T, int a[n]) //数组保存n个整数 {

BiTree p=T; //p指向双亲结点 Int i;

For(i=0;i

if (SearchBST(T->lchild, a[i], p)) return 0; //查找成功 BiTree s=(BiTree) malloc(sizeof (BiTnode)); //申请结点 s->key=a[i];

s->lchild=s->rchild=NULL;

if (!T->lchild) T->lchild=s; //s为根结点

else if (a[i]key) p->lchild=s; //s为p的左孩子 else p->rchild=s; //s为p的右孩子

}

} //InsertBST

//用中序遍历即可从大到小输出

习题4 排序

4-1 在下列排序算法中，时间复杂度最好的是( )。

(A) 堆排序 (B) 插入排序 (C) 冒泡排序 (D) 选择排序

A

4-2 如果顺序表中的大部分数据元素按关键字值递增有序，则采用( )算法进行升序排序，比较次数最少。

(A) 快速排序 (B) 归并排序 (C) 选择排序 (D) 插入排序 D

4-3 对 …… 此处隐藏：2306字，全部文档内容请下载后查看。喜欢就下载吧 ……