数据结构总复习和作业.ppt

考试时间：第10周周日(5月10日) 九、十节 考试教室安排： 考试方式：闭卷笔试 考试成绩卷面(80)平时作业(20) 考试题型(参考）： 1、判断对错、选择、填空 2、综合应用 3、算法设计 数据结构答疑安排： 大黑楼 A802或A718 周三(5月6日)下午1:305:00 InsertList()：在有序单链表中插入元素x； ReverseList()：单链表就地逆置； DelList()：在有序单链表中删除所有值大于mink且小 于maxk的元素。 选作：使用文本菜单完成功能选择及执行。思考题： 你能将上述算法改为双向循环链表吗？ 作业1 L 3 1 2 4 5 q p temp q 单链表就地逆置 L 1 3 2 4 5 p temp q q 单链表就地逆置 L 2 1 3 4 5 temp q ptemp q 单链表就地逆置 L 5 2 1 4 3 q p temp q 单链表就地逆置 L 4 5 2 3 1 void ListReverse_L(LinkList p=L-next; if(p=NULL|p-next=NULL) /空链链表或只有一个结结点 return; q=L-next-next; /q指向第二个结结点 p-next=NULL; while(q) u=q-next; q-next=L-next; L-next=q; q=u; 单链表就地逆置 L 3 1 2 4 5 q p pretemp q 单链表就地排序 L 1 3 2 4 5 p pretemp q q 单链表就地排序 L 1 2 3 4 5 temp q q ppre 单链表就地排序 L 1 2 3 4 5 temp q q ppre 单链表就地排序 L 1 2 3 4 5 temp q q ppre 单链表就地排序 L 1 2 3 4 5 q ppre 单链表就地排序 L 1 2 3 5 4 单链表就地排序 LinkList SortList(LinkList L) /链表就地排序 LNode *p,*pre,*q,*temp; p=L-next; if(p=NULL) return L; /空表,不用排序，返回 q=p-next; p-next=NULL; while(q!=NULL) pre=L; p=L-next; while(p!=NULL) /查找插入位置 if(q-datap-data) pre=p; p=p-next; elsebreak; temp=q-next; /插入 pre-next=q; q-next=p; q=temp; return L; 作业2 若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出 栈序列。 可能的出栈序列：(14种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列：(10种) dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 元素a、b、c、d、e、f依次通过栈， 若出栈顺序是c、b、d、f、e、a，则栈S的容量至少是（ ） 3 表达式后缀形式，前缀形式 ab*cde/-f*+a*b+(c-d/e)*f 循环队列队满和队空的判别条件。 Q.front=Q.rear Q.front= =( Q.rear+1)%M 设A为n阶对称矩阵，采用压缩存储存放于一维数组 Fn(n+1)/2中（从F0开始存放），请分别给出存放上三角阵 时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩 阵元素aij的地址计算公式。 存放下三角阵时，任一矩阵元素aij（1in, 1ji） 的地址计算公式为： 存放上三角阵时，任一矩阵元素aij（1in,ijn） 的地址计算公式为： a11 0 0 0 a21 a22 0 0 an1 an2 an3 ann . 0 作业2 a11 a12 a13 a1n 0 a22 a23 a2n 0 0 0 ann an-1n-1an-1n 5 6 6 1 1 4 2 1 5 2 3 3 2 6 8 4 4 7 5 1 2 三元组表 i j v 0 1 2 3 4 5 6 写出矩阵三元组表，十字链表 作业2 114 512 447 233 268 215 十字链表 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 作业3 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列 是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和 后序遍历序列。 E A C B D I J H F G K 层次：E A F B H D G I C K J 后序-C D B A G J K I H F E 森林转换成一棵二叉树 作业3 B A C D F G E H I J K L 二叉树还原成森林 A C H B F D M EG N JI K L 设二叉树的后序遍历序列为：DCFEBHJKIGA，中序 序列为：CDBEFAHGJIK，请构造这棵二叉树。 作业3 二叉树的中序遍历序列为：DBHEIAFJKCG，层次遍历 序列为：ABCDEFGHIJK，请画出该二叉树 作业3 假设用于通信的电文由7个字母组成A,B,C,D,E,F,G，字母 在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、 0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权 路径长度WPL 1 0.390.61 0.180.21 0.090.09 0.290.32 0.120.17 0.030.06 A E G B D F WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56 A:101 B:001 C:100 D:0001 E:11 F:0000 G:01 算法设计题 二叉树采用二叉链表存储，试设计算法实现： CreateBT(BiTree scanf(“%c“, if (ch = #) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; CreateBT(T-lchild); CreateBT(T-rchild); BC F A E D /交换换二叉树树中结结点的左右孩子 void ExchangeBT(BiTree T) BiTree temp; if(T) temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; ExchangeBT(T-lchild); ExchangeBT(T-rchild); BiTree SearchTree(BiTree T,char X) BiTree bt; if(T) if(T-data=X)return T; bt=SearchTree(T-lchild,X); if(bt=NULL) bt=SearchTree(T-rchild,X); return bt; return NULL; void LeafCount (BiTree T, int LeafCount2( T-lchild, count); LeafCount2( T-rchild, count); BC F A E D /按树树状打印输输出二叉树树的元素,level表示结结点的层层次 void DispBiTree(BiTree T,int level) int i; if(T) DispBiTree(T-rchild, level + 1); for(i = 0; i data); DispBiTree(T-lchild, level + 1); BC F A E D 打印得到： #C #F #E A #D #B 已知带权有向图如下, 要求： 画出图邻接矩阵； 给出图的一个拓扑有序序列； 求从顶点a出发到其余个顶点的最短路径 a bc deh fg 21 6 93 2 24 30 5 8 7 21 0 2 6 9 0 30 1 0 5 0 2 8 0 7 3 0 24 0 21 0 拓扑有序序列： a, b, d, f, e, c, g, h 作业4 无向图邻接表存储结构如图所示： 画出该无向图； 写出在该邻接表上，从顶点1出发所得到的深度优先遍历 (DFS)和广度优先遍历(BFS)序列。 作业4 1 3 2 4 7 5 86 DFS：1，3，4，7，8，6，5，2 BFS：1，3，2，4，7，6，5，8 对下标为19的有序表进行二分法查找， (1)画出折半查找的判定树； (2)计算其ASL; (3)比较4次查找成功的结点共有 个。 5 27 1368 49 ASL=(1+2*2+3*4+4*2)/9=25/9 2 作业5 设有关键字序列25，40，33，47，12，66，72，87，94，22，5， 58 散列表长为12，散列函数为h(key)=key%11，用线性探测再散列处 理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败 的平均查找长度 ASL=(1*6+2+3*2+5+6+9)/12=34/12 作业5 36 0 5 361010730 941266253347227240 113126113 11 87 1 5 5 58 9 设有关键字序列25，40，33，47，12，66，72，87，94，22，5， 58 散列表长为12，散列函数为h(key)=key%11，用二次探测再散列处 理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败 的平均查找长度 ASL=(1*6+2+3*3+4+5)/12=26/12 作业5 36 0 5 361010730 9412 66 253347227240 11 3 125113 11 87 1 5 4 58 3 ASL=(1*7+2*3+3*2)/12=19/12 6633 0 1 2 3 4 5 6 7 8 9 10 11 12 22 47 94 58 12 25 72 40 87 5 作业5 设有关键字序列25，40，33，47，12，66，72，87，94，22，5， 58 散列表长为12，散列函数为h(key)=key%11，用线性探测再散列处 理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败 的平均查找长度 36 0 5 361010730 已知待排序序列为50，86，72，41，45，93，57，46， 请写出按下列排序方法进行升序排序时的第一趟排序结果 ： 第一趟直接插入排序：50，86，72，41，45，93，57，46 第一趟冒泡排序： 50，72，41，45，8