数据结构总复习和作业2019

考试时间：第10周周日(5月10日)九、十节考试教室安排：考试方式：闭卷笔试考试成绩＝卷面(80％)＋平时作业(20％)考试题型(参考）：1、判断对错、选择、填空2、综合应用3、算法设计数据结构答疑安排：大黑楼A802或A718周三(5月6日)下午1:30～5:00第一章绪言基本概念和术语（掌握）数据结构，数据，数据元素，数据项逻辑结构与存储结构算法分析（掌握）算法定义算法特性：算法评价：–时间复杂度与空间复杂度（了解）第二章线性表逻辑结构（掌握）存储结构（掌握）顺序存储结构链式存储结构–单链表–双向链表–循环链表–双向循环链表–静态链表（了解）基本操作（掌握）插入删除查找应用------一元多项式相加（掌握）时间复杂度第三章栈和队列---操作受限的线性表栈特点（掌握）：FILO(LIFO)存储结构（掌握）：顺序栈与链栈基本操作（掌握）：入栈与出栈应用（掌握）：回文、括号匹配、表达式求值3队列特点（掌握）：FIFO（LILO）存储结构（掌握）：–顺序队列–链队列循环队列（掌握）基本操作（掌握）–入队–出队应用（了解）：迷宫，优先队列等队空、队满条件第四章数组线性结构存储结构顺序存储结构（掌握）：次序约定（算法实现不要求）压缩存储（掌握）–对称矩阵–对角矩阵–三角矩阵–稀疏矩阵算法：求转置矩阵（了解）三元组表行逻辑链接的顺序表带行指针向量的单链表十字链表第五章树逻辑结构：按分支关系定义的层次结构定义（掌握）：深度、度、叶子等满二叉树、完全二叉树二叉树性质（掌握）：5存储结构树（掌握）–双亲表示法–孩子表示法（孩子链表与多重链表）–孩子兄弟表示法（二叉链表）二叉树（掌握）–顺序存储结构–二叉链表–三叉链表树、森林与二叉树转换（掌握）遍历–按层次、先序、中序、后序–遍历递归（掌握）与非递归算法（了解）–遍历算法应用（掌握）»由先序序列建立二叉链表»统计叶子结点»求二叉树深度»已知先序和中序序列，构造二叉树应用Huffman树（掌握）–定义，WPL–构造方法–有n个叶子结点的Huffman树共有2n-1个结点–应用»Huffman编码与译码»最佳判定树第六章图定义（掌握）：图、有向图、度、连通、完备图等存储结构邻接矩阵（掌握）邻接表与逆邻接表（掌握）十字链表（了解）邻接多重表（了解）遍历：深度优先与广度优先（掌握遍历策略及算法）深度优先生成树、广度度优先生成树构成特点(与顶点度关系)应用（掌握求解过程，不要求写算法）最小生成树（Prim与Kruscal）拓扑排序最短路径（Dijkstra）第七章查找静态查找表顺序查找（掌握）折半查找（掌握）分块查找（了解）动态查找表（了解）二叉排序树–定义–构造方法–生成、插入、删除与查找–中序遍历二叉排序树可得到结点有序序列比较、ASL哈希查找（掌握）定义、基本思想Hash函数构造方法处理冲突方法哈希表构造哈希查找过程与ASL第八章排序掌握排序的基本概念和性能分析方法，排序策略插入排序直接插入排序（掌握）折半插入排序（掌握）希尔排序（了解）交换排序冒泡排序（掌握）快速排序（了解）选择排序简单选择排序（掌握）堆排序（掌握，不考算法）归并排序：2-路归并排序（了解）基数排序：链式基数排序（了解）排序方法思想每趟排序结果排序方法性能分析评价本章了解的排序方法不要求掌握算法作业1.线性表从键盘读入n个整数（升序），请编写算法实现：CreateList()：建立带表头结点的单链表；PrintList()：显示单链表(形如:H-10-20-30-40);InsertList()：在有序单链表中插入元素x；ReverseList()：单链表就地逆置；DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。思考题：你能将上述算法改为双向循环链表吗？作业1L3124^5qp^tempq单链表就地逆置L1324^5p^tempqq单链表就地逆置L2134^5^tempqptempq单链表就地逆置L5214^3qp^tempq单链表就地逆置L4523^1^voidListReverse_L(LinkList&L){LinkListp,q,u;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;}}单链表就地逆置L3124^5qp^pretempq单链表就地排序L1324^5p^pretempqq单链表就地排序L1234^5^tempqqppre单链表就地排序L1234^5^tempqqppre单链表就地排序L1234^5^tempqqppre^单链表就地排序L1234^5qppre^单链表就地排序L1235^4^单链表就地排序LinkListSortList(LinkListL)//链表就地排序{LNode*p,*pre,*q,*temp;p=L-next;if(p==NULL)returnL;//空表,不用排序，返回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;}returnL;}作业2•若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc元素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.rearQ.front==(Q.rear+1)%Mij11-1Loc(a)=Loc(a)+*2(2n+2-i)ijilij11-1Loc(a)=Loc(a)+1*2iijl•设A为n阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩阵元素aij的地址计算公式。存放下三角阵时，任一矩阵元素aij（1≤i≤n,1≤j≤i）的地址计算公式为：存放上三角阵时，任一矩阵元素aij（1≤i≤n,i≤j≤n）的地址计算公式为：a1100……..0a21a220……..0an1an2an3……..ann………………….0作业2a11a12a13……..a1n0a22a23……..a2n000……..ann……………an-1n-1an-1n400000503008000000000700200000A566114215233268447512三元组表ijv0123456写出矩阵三元组表，十字链表作业2114^512^^^447^^233268^215^^^十字链表^请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。作业3已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。EACBDIJHFGK层次：EAFBHDGICKJ后序---CDBAGJKIHFE森林转换成一棵二叉树作业3ABCDGHIJKEFLBACDFGEHIJKL二叉树还原成森林ABCDGHIJKEFLMNACHBFDMEGNJIKL设二叉树的后序遍历序列为：DCFEBHJKIGA，中序序列为：CDBEFAHGJIK，请构造这棵二叉树。作业3AGJHIKDCBEF二叉树的中序遍历序列为：DBHEIAFJKCG，层次遍历序列为：ABCDEFGHIJK，请画出该二叉树ACJFGKHDBEI作业3假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL10.390.610.180.210.090.090.290.320.120.170.030.06AEGBDFWPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101B:001C:100D:0001E:11F:0000G:01算法设计题二叉树采用二叉链表存储，试设计算法实现：CreateBT(BiTree&T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；如输入：AB#D##CE#F###则建立如下图所示二叉树的二叉链表ExchangeBT(BiTreeT):设计递归算法实现二叉树中所有结点的左右孩子交换；CountLeaf(BiTreeT,TElemTypex,int&count):统计以值为x的结点为根的子树中叶子结点的数目；DispBiTree(BiTreeT,intlevel):按树状打印二叉树。作业3//输入先序序列，创建二叉树的二叉链表voidCreateBT(BiTree&T){charch;scanf(%c,&ch);if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T-data=ch;CreateBT(T-lchild);CreateBT(T-rchild);}}BCFAED//交换二叉树中结点的左右孩子voidExchangeBT(BiTreeT){BiTreetemp;if(T){temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;ExchangeBT(T-lchild);ExchangeBT(T-rchild);}}BiTreeSearchTree(BiTreeT,charX){BiTreebt;if(T){if(T-data==X)returnT;bt=SearchTree(T-lchild,X);if(bt==NULL)bt=SearchTree(T-rchild,X);returnbt;}returnNULL;}voidLeafCount(BiTreeT,int&count){if(T){if((T-lchild==NULL)&&(T-rchild==NULL))count++;LeafCount2(T-lchild,count);LeafCount2(T-rchild,count);}}BCFAED//按树状打印输出二叉树的元素,level表示结点的层次voidDispBiTree(BiTreeT,intlevel){inti;if(T){DispBiTree(T-rchild,level+1);for(i=0;ilevel;i++)printf(#);printf(%c\n,T-data);DispBiTree(T-lchild,level+1);}}BCFAED打印得到：#C###F##EA##D#B已知带权有向图如下,要求：画出图邻接矩阵；给出图的一个拓扑有序序列；求从顶点a出发到其余个顶点的最短路径abcdehfg