数据结构作业及答案 （C语言版）.

Presentation on theme: "数据结构作业及答案 （C语言版）."— Presentation transcript:

1 数据结构作业及答案 （C语言版）

2 目 录 1、第2章 线性表 2、第3章 栈和队列 3、第6章 树和森林 4、第7章 图 5、第8章 集合与查找 6、第9章 索引与散列

3 第2章 线性表作业及答案1-1 1、已知有一个单链表L，设计一个算法，通过一趟遍历，在L中确定值最大的结点，返回指向该结点的指针。(注：遍历是指从头至尾访问单链表中的每一个结点且指访问一次) LNode *Max(LinkList head) { if (headnext==NULL) return NULL; //空表 LNode *pmax=headnext; //pmax从第一个结点开始 LNode *p=headnextnext; //p从第二个结点开始 while (p!=NULL) { if (pdata > pmaxdata) pmax=p; p=pnext; } return pmax; 【解答】设LNode为单链表结点结构，LinkList为LNode*，head为单链表的头指针

4 第2章 线性表作业及答案1-2 2、设计一个算法，在非递减有序的单链表L中删除值相同的多余结点
第2章 线性表作业及答案1-2 2、设计一个算法，在非递减有序的单链表L中删除值相同的多余结点 void delete_duplicate(LinkList head) { LNode *p=headnext; LNode *temp=NULL; while (p!=NULL && pnext!=NULL) { if (pdata == pnextdata) { temp=pnext; pnext=tempnext; delete temp; } else p=pnext; 【解答】设LNode为单链表结点结构，LinkList为LNode*，head为单链表的头指针

5 第3章 栈和队列作业及答案2-1 假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag==0和tag==1来区别当队头指针front和队尾指针rear相等时，队列的状态是“空”还是“满”。试编写与此结构相应的入队(EnQueue)和出队(DeQueue)算法。要求先写明结构，再写算法 #define MAXQSIZE 100 typedef struct { ElemType *base; int front, rear, tag; } SqQueue; int IsEmpty(SqQueue Q) { return(Q.front==Q.rear && Q.tag==0); } int IsFull(SqQueue Q) { return(Q.front==Q.rear && Q.tag==1); 【解答】

6 第3章 栈和队列作业及答案2-2 Status EnQueue(SqQueue &Q, ElemType e) {
第3章 栈和队列作业及答案2-2 Status EnQueue(SqQueue &Q, ElemType e) { assert(!IsFull(Q)); Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; Q.tag=1; //标志改1，表示队列非空 return OK; } Status DeQueue(SqQueue &Q, ElemType &e) { assert(!IsEmpty); e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; Q.tag=0; //标志改0，表示队列不满

7 第6章 树和森林作业及答案4-1 1、编写递归算法，统计二叉树中度为2的结点个数 【解答】
第6章 树和森林作业及答案4-1 1、编写递归算法，统计二叉树中度为2的结点个数 int degree2(BiTree root) { if (!root) return 0; //叶结点 if (rootlchild && rootrchild) //度为2的结点 return 1+degree2(rootlchild) +degree2(rootrchild); else return degree2(rootlchild) //度为1的结点 } 【解答】

8 第6章 树和森林作业及答案4-2 2、给定权值集合{ 15, 3, 14, 2, 6, 9, 16, 17 }，构造相应的Huffman树，并计算它的带权路径长度(要求画出Huffman树的构造过程) 【解答】 15 3 14 2 6 9 16 17 F : 15 F : 14 6 9 16 17 5 2 3 15 F : 14 6 9 16 17 5 2 3 11

9 第6章 树和森林作业及答案4-3 15 F : 14 6 9 16 17 5 2 3 11 20 15 F : 14 6 9 16 17 5 2 3 11 20 29 F : 6 9 16 17 5 2 3 11 20 33 15 14 29

10 第6章 树和森林作业及答案4-4 此树的带权路径长度WPL=229 F : F : 15 14 29 6 9 5 2 3 11 20 16
第6章 树和森林作业及答案4-4 15 14 29 6 9 5 2 3 11 20 16 17 33 49 F : 15 14 29 6 9 5 2 3 11 20 16 17 33 49 82 F : 此树的带权路径长度WPL=229

11 第7章 图作业及答案5-1 1、用数学归纳法证明有n个顶点的完全无向图有n(n-1)/2条边 【证明】
第7章 图作业及答案5-1 1、用数学归纳法证明有n个顶点的完全无向图有n(n-1)/2条边 【证明】 (1) 当n=1时，一个顶点时，边数为0，成立。 (2) 当n=2时，两个顶点，边数为1，成立。 (3) 设n=k时成立，即k个顶点的完全无向图有k(k-1)/2条边，则n=k+1时，第k+1个顶点到其他k个顶点的边数共k条，于是总边数为 k(k-1)/2+k=(k+1)k/2。  结论成立。

12 第7章 图作业及答案5-2 2、对于如图所示的有向图，试画出从顶点①出发进行深度优先搜索得到的深度优先生成树 1 2 4 3 5 【解答】 1 2 3 4 5 结果不唯一

13 第8章 集合与查找作业及答案6-1 将关键字{ DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN }依次插入到一棵初始为空的AVL树中，画出每插入一个关键字后的AVL树，需要平衡时标明平衡旋转的类型和结果(注：按字典顺序比较) DEC FEB NOV DEC DEC FEB DEC FEB NOV 左单旋 DEC FEB NOV OCT DEC FEB NOV OCT JUL SEP DEC FEB NOV OCT JUL 左单旋 DEC FEB NOV OCT JUL SEP

14 第8章 集合与查找作业及答案6-2 DEC FEB NOV OCT JUL SEP AUG DEC FEB NOV OCT JUL SEP
第8章 集合与查找作业及答案6-2 DEC FEB NOV OCT JUL SEP AUG DEC FEB NOV OCT JUL SEP AUG APR 右单旋 DEC FEB NOV OCT JUL SEP AUG APR DEC FEB NOV OCT JUL SEP AUG APR MAR

15 第8章 集合与查找作业及答案6-3 DEC FEB NOV OCT JUL SEP AUG APR MAR MAY FEB NOV OCT
第8章 集合与查找作业及答案6-3 DEC FEB NOV OCT JUL SEP AUG APR MAR MAY FEB NOV OCT JUL SEP AUG APR MAR MAY 左单旋 DEC FEB NOV OCT JUL SEP AUG APR MAR MAY DEC JUN 先左后右 FEB NOV OCT JUL SEP AUG APR MAR MAY DEC JUN

16 第8章 集合与查找作业及答案6-4 FEB NOV OCT JUL SEP AUG APR MAR MAY DEC JUN JAN FEB
第8章 集合与查找作业及答案6-4 FEB NOV OCT JUL SEP AUG APR MAR MAY DEC JUN JAN FEB NOV OCT JUL SEP AUG APR MAR MAY DEC JUN JAN

17 第9章 索引与散列作业及答案7-1 给定关键字序列{ 11, 78, 10, 1, 3, 2, 4, 21 }，分别用顺序查找、折半查找、二叉排序树、平衡二叉树、散列表(用线性探查法和链地址法)实现查找，画出它们对应的存储结构(顺序查找的顺序表，折半查找的二叉判定树，二叉排序树、平衡二叉树以及两种散列表)，并求出每一种查找在等概率下查找成功时的ASL。其中，散列表为HT[11]，散列函数为H(key)=key%11 【解答】(1) 顺序查找的顺序表(一维数组)如图所示， 1 2 3 4 5 6 7 8 9 10

18 第9章 索引与散列作业及答案7-2 可以得到顺序查找的平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=(8+1)/2=4.5
第9章 索引与散列作业及答案7-2 可以得到顺序查找的平均查找长度为：ASL=( )/8=(8+1)/2=4.5 (2) 先按关键字排序，折半查找的判定树如图所示， 4 2 1 3 11 10 21 78 从图可以得到折半查找的平均查找长度为： ASL=(1+2*2+3*4+4*1)/8=21/8=2.625

19 第9章 索引与散列作业及答案7-3 (3) 二叉排序树和平衡二叉树如图所示，
第9章 索引与散列作业及答案7-3 (3) 二叉排序树和平衡二叉树如图所示， 11 10 78 1 21 3 2 4 ( a) 二叉排序树 (b) 平衡二叉树 从图可以得到二叉排序树查找的平均查找长度为：ASL=(1+2*2+3*2+4*1+5*2)/8=25/8=3.125 平衡二叉树的成功平均查找长度为：ASL=(1*1+2*2+3*3+4*2)/8=22/8=2.75

20 第9章 索引与散列作业及答案7-4 (4) 线性探查法解决冲突的散列表如图所示，
第9章 索引与散列作业及答案7-4 (4) 线性探查法解决冲突的散列表如图所示， 从图可以得到线性探查法的平均查找长度为 ASL=( )/8=19/8=2.375 (5) 链地址法解决冲突的散列表如图所示，

21 第9章 索引与散列作业及答案7-5 从图可以得到链地址法的平均查找长度为：ASL=(1*6+2*2)/8=10/8=1.25 1 2 3 4
第9章 索引与散列作业及答案7-5 1 2 3 4 5 6 7 8 9 10 ^ 78 11 21 从图可以得到链地址法的平均查找长度为：ASL=(1*6+2*2)/8=10/8=1.25

22 The End