自考 2365计算机软件基础（二）课后 习题(3)

指针，试编写相应的入队和出队算法。

【答案】：

typedef struct snode{int data； struct snode *link；} NODE； NODE *rear； /* 定义结点的类型和指向队尾的指针*/ void addqueue (int x){

NODE *p；

p = (NODE *)malloc(sizeof(NODE))；/* 申请结点空间 */

p->data = x； p->link = rear->next； rear->next = p； /* 在队尾插入结点 */ }

rear = p； /* 修改队尾指针 */

int delequeue( ) { /*从链队中出列，返回出队的数据元素 */ NODE *p； if (rear->link==rear)

{ printf(“queue is empty!\\n”)； return(-1)； } else { p=rear->link； /* p指向头结点 */

q=p->link； /* q指向被删除结点 */ if(q==rear) rear=p； /* 队列中仅有一个结点时，先修改尾指针*/ p->link=q->link； x=q->data；

free(q)； return(x)； /* 删除结点并返回 */ }

}

17．已知二维数组Am，m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为LOC（a11），请写出LOC（aij）的计算公式。如果采用列优先顺序存放呢？

【答案】：

按行优先顺序存放：LOC(aij)=LOC(a11)+((i-1)*m + (j-1))*K； 按列优先顺序存放：LOC(aij)=LOC(a11)+((j-1)*m + (i-1))*K；

18．用三元组表表示下列稀疏矩阵：

0 0 0 0 0 0 0

0 0

0 3

0 0 0 0 0 0 0

0 0 0 6 0 0 0

0 0 0 0 0 0 0

0 8 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 5 0 0

0 0 0 0 0 0

0 9 0 0 0 3

-2 0 0 0 0 0

（1） 0 0 0 0 0 0 0 0 2 0

0 （2） 0 0 5 0

【答案】： （1） （2）

列下标66535元素值4-2953行下标61246

11

行下标833578列下标826481元素值538652

19．下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

6 4 6

（1）

【答案】：

0 0

2 0 0 0

12 0 0 0 0 0

0 4

1 0

0 0 8 0

0 0 0 7

0 9 0 0

0 0 6 0

1 1 3 4 5

2 3 1 4 3

2

4 1 2 3 3 4

5 1 4 2 5 3

5 1 9 8 6 7

12 3 4 6

（2）

6 1 16

（1）： 3

0 （2）： 0 0

0 0 6 0

16 0 0 0

20．什么样的二叉树不是树？一棵度为2的树与一棵二叉树有何区别？ 【答案】：

空树是二叉树，但不是树。树一定是非空的。 在一棵度为2 的树中至少有一个结点的度为2；但在一棵二叉树中每个结点的度可以都

小于2，比如单枝树。

21．试分别画出具有3个结点的树和有3个结点的二叉树的所有不同形态。 【分析】：无序树的子树没有顺序之分，而二叉树的子树分为左子树和右子树。 【答案】：具有3个结点的树 ：

12

有3个结点的二叉树：

22．设一棵完全二叉树具有1000个结点，问此完全二叉树 （1）有多少个叶子结点？

（2）有多少个度为2的结点？

（3）有多少个结点只有非空左子树？ （4）有多少个结点只有非空右子树？

【分析】：有1000个结点的完全二叉树共有10层，在第10层有1000-（2-1）=1000-511=489个结点；都是叶子结点，它们共有244+1个双亲结点在第9层，其中有一个双亲结点只有一个孩子，其他共244个双亲结点的度均为2，所以在第9层还有256-245=11个结点的度为0，既为叶子结点。 【答案】： （1）有500个叶子结点。

（2）有255+244=499个度为2的结点； （3）有1个结点只有非空左子树； （4）没有结点只有非空右子树；

23．下面是有关二叉树的叙述，哪些是正确的？

（1）二叉树中每个结点的两棵子树的高度差不大于1。 （2）二叉树中每个结点的两棵子树的高度差等于1。 （3）二叉树中每个结点的两棵子树是有序的。

（4）二叉树中每个结点的两棵非空或有两棵空子树。

（5）二叉树中每个结点的关键字值大于左子树（若存在的话）上所有结点的关键字值，

且小于其右非空子树（若存在的话）上所有结点的关键字值。 （6）二叉树中所有结点个数是2k-1 –1，其中k是树的深度。

（7）二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 【答案】：

（1）错误。AVL树中每个结点的两棵子树的高度差不大于1。 （2）错误。

（3）正确。

（4）错误。二叉树中有些结点可以有一棵空子树，一棵非空子树。 （5）错误。二叉排序树满足所叙述的条件。

（6）错误。二叉树中所有结点个数至多是2k –1 。

（7）错误。二叉树中的结点，可以没有非空左子树，但有非空右子树。

24．用链式结构存储二叉树，试写出下列算法： （1）按层次输入所有结点； （2）输出所有叶子结点。

【答案】：

/* 先定义二叉树的二叉链表结构*/

13

9

typedef struct node {int data； struct node *lchild，*rchild；} NODE； （1）按层次输入所有结点：

【分析】： 本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。 void layorder(NODE *root){

/* 设q是一个队列，函数initqueue(q)、addqueue(q，x)、delqueue(q)、empty(q)在2.4.2队列中已实现 */

initqueue(q)； /* 初始化一个队列 */ if (root!=NULL) {

printf(“%d”，root->data)； /* 输出结点值 */ addqueue(q，root)；

/* 根结点入队 */

while( NOT empty(q)) { /* 如果队列不空 */ p=delqueue(q)； /* 对头元素出队 */ }

if (p->lchild!=NULL) { printf(“%d”，p->lchild->data)； /* 输出左孩子的值 */ addqueue(q，p->lchild)； /* 左孩子入队 */ }

if (p->rchild!=NULL)

{ printf(“%d”，p->rchild->data)； /* 输出右孩子的值 */ addqueue(q，p->rchild)； /* 右孩子入队 */ }

} }

（2）输出所有叶子结点： 【分析】： ： 本算法为先根遍历的递归算法。如果树不空，分三步进行：第一步，判断根结点是否为叶子结点，若是，则输出；第二步，调用该算法输出根结点的左子树上的所有叶子结点；第三步，调用该算法输出根结点的右子树上的所有叶子结点； 【答案】： typedef struct node {int data； struct node *lchild，*rchild；} NODE； void printleaf(NODE *root){

if (root!=NULL){ if((root->lchild==NULL)&&(root->rchild==NULL))

printf(“%d”，root->data)； /* 如根结点是叶子结点，则输出 */

printleaf(root->lchild)； /* 输出左子树上的所有叶子结点 */

printleaf(root->rchild)； /* 输出右子树上的所有叶子结点 */

} }

25．已知一棵具有n个结点的完全二叉树被顺序存储于一维数组btree中，试编写一个算法打印出编号为i的结点的双亲和所以孩子。

14

【答案】：

#define N 100

int btree[N] /* 定义完全二叉树的存储结构 */

void print_parent_child(int n，int i){ /*n为结点个数 */ if(n==0) { printf(“ Tree is empty!”)； return；} /* 空树 */

else if((i<1)||(i>n)) {printf(“ order i error!”)； return；} /* 编号出错 */

else if(i==1) /* 根结点无双亲 */

{ printf(“ No parents\\n”)；

if(2*i<=n)printf(“Lchild is:%d\\n”，btree[2*i])； if(2*i+1<=n)printf(“Rchild is:%d\\n”，btree[2*i+1])； }

else { printf(“Parent is:%d\\n”，btree[i/2])；

/*双亲*/

if(2*i<=n)printf(“Lchild is:%d\\n”，btree[2*i])；/*左孩子*/ if(2*i+1<=n)printf(“Rchild is:%d\\n”，btree[2*i+1])；/*右孩子*/ }

}

26．试写出如下所示的二叉树分别按先序、中序、后序遍历得到的结点序列。 A

B F

D J G

K

C H

E I L

M 【答案】：

先序序列：ABDFJGKCEHILM 中序序列：BFJDGKACHELIM 后序序列：JFKGDBHLMIECA

27．把如图所示的树转化为二叉树。

B

A C D J E F G 【答案】：

K

E L

B A C D I J H I K L M F H G M 15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库自考 2365计算机软件基础（二）课后 习题(3)在线全文阅读。