数据结构与算法期末练习题(含答案)

}

p=p->next; } }

return degree; }

六 简单应用题

1、已知一个非空二元树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A

试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?

2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。

3、画出由下面的二叉树转换成的森林。

4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：

A 1 2 3 PATH 1 2 3

A 1 2 (0)(0) A 3 1 2 (1)(1) A 3 1 2 (2)(2) A 3 1 2 (3)(3) 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。

weight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

5 29 7 8 14 23 3 11 -- -- -- -- -- -- -- Parent 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rchild

weight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Parent Lchild Rchild

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

6、考虑右图：

(1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分)

(3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)

答案如下：

七 编写算法题

1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x)

2、设计递归函数，求一棵二叉树的深度。 int depth (bitreptr root)

3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct

{ int data[ maxsize][maxsize]; int dem,e; }sqgraph;

sqgraph crt (sqgraph g)

4、设计函数，将不带表头结点的单链表清除。

5、设计递归函数，求一棵非空的二叉树的深度。

6、设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。

7、试编写一个算法，能由大到小遍历一棵二元树。

8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树?

9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。

10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。

11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。

该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode {

ElemType data;

Struct LNode* next; }List, LNode;

函数定义：void invert(List & L)

12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下

typedef struct BiTNode{ DataType data;

Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree;

函数定义：CountLeaf (BiTree T, int & LeafNum)

13、写出二叉树前根遍历的递归算法

已知二叉树结点定义为： struct node{

elemtp data;

struct node *lc,*rc; );

Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点

void preorder(bitreptr P) {

If(P!=0) {

printf(P->data); preorder(P->lc); preorder(P->rc);

}

}

14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK;