《数据结构应用题总结》由会员分享，可在线阅读，更多相关《数据结构应用题总结（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构应用题总结试写出二叉树的先序遍历，中序遍历，后序遍历序列先序遍历:中序遍历:ijiiJ-+a*b-cd/efa+bc-d-e/fabed 噫 + e f / -iliiJ后序遍历：-+/a*efb-cdiliiJ层次遍历：将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45各.棵树分别转换成二叉树；Q将每棵转换后 的二叉树依次连接成为右子这是刚开始的森林1=/上面3个是树转二叉树转换成森林抹线：1将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的无右孩子二
2、叉树；2.将孤立的二 叉树转换成树构造Huffman树哥=5, 29? 7, & 14, 23。3, 11深度优先遍历深度遍历 vm V2 =V4 = V8 nV5 nV3 nV6 nV7V3r-V2V8广度遍历广度遍历：vm V2 =V3 n V4 =V5 亨V6 ；V7 =V8最小生成树普里姆(Prim)算法:克鲁斯卡尔(Kruskal)算法:拓扑排序在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当 图中不存在无前驱的顶点为止（2）拓。序列拓扑序列拓扑序列拓扑序列】Cl C2-C3-C4-C5 C7 C9 拓扑序列：Cl
3、-C2-C3-C4-C5-C7-C!.rio.-T1! i-CIOCllC6(H-)拓扑序列* Cl -C2-C3-C4-C5-C7-O-C10-CI1-C6-C12 -CS拓扑序列：Cl -C2-C3-C 4 -C 5-C7-C 9-C10-Cll-C-C12拓扑序列，C1-C2-CS-C4-C5-C7-O-CIO-Cll-C6-C12-C8 或 ：C&-C10-C11-C6-C1-C12-C4-C2-C3-C5 -C7-CB个网的拓扑序列不是唯-的关键路径见笔记11哈希表的建立，处理冲突方法例 表长为11的哈希表中己填有关键字为17, 60, 29的记录, II(key)=key MOD
4、11,现有第4个记录，其关键字为38, 按三种处理冲突的方法，将它填入表中012 3 4 5 6 7 S 9 10TssTjaTeo 17I2? IjsI突突突冲咳 狎冲冲不冲(1) H(3 8)=38 MOD 11-5Hi=(5+1) MOD 11=6 压l(5+2) MOD 11-7 任=(5+3) MOD 11=8()H (38)3 8 MOD 11=5Hi=(5-nl2) MOD 11=6 冲突H2=(5 I2) MOD 11=4 不冲突(3) H(38户38 MOD 11-5 冲突 设伪随机数序列为9,则， 111=(5+9) MOD 11=3 不冲突开放定址法：例 己知一组关键字(
5、19,14,23,1,08,20,84,27,55,11,10,79) 哈希函数为：H(kevkey MOD 13,哈希表隹为m=16, 设每个记录的查找版率相等(1)用线性探测再散列处理冲突，EpHi=(H10in )=1 冲突，111=(1+1) MOD 16=2尸 1H(68 户3H(207H(84 户&冲突，HL=(10+1)MOD16=11 冲突，H2=(l (2)MOD16=12 抻突，m=(l+L)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=Q十4)MOD165 押突，H5=(1+5)MOD16=6 冲突，H6=(1+6
6、)MOD16=7 冲突，H7=(1+7)MOD16=S 冲突，HS=(1+S)MOB16=9 ASL=(lfrF2+3*3+4+9)712=2.5冲突，H1=(6+1)MOD16=7冲突，H2-(5+2)MOD16=8汗突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3冲突，II3=(1+3)MOD16=4冲突，H1=(3+1)MOD16=4冲突，H2=(3+2)MOD16=S珥55尸3关键字(19,14,23,1,68,20,84,27,55,11,10,79)用链地址法处理冲突:ASL=(1*6+2*4+3+4)/12=1.75112二叉排序树的建立左边都是小的，右边都
7、是大于等于的13堆排序1）堆排序需解决的两个问题：如何由一个无序序列建成一个堆?如何在输出堆顶元素之后，调整剩余元素，使之 成为一个新的堆？2）第二个问题解决方法一一筛选方法：输出堆顶元素之后，以堆中最后一个元素 替代之；然后将根结点值与左、右子树的根结点 值进行比较，并与其中小者进行交换；重复上述 操作，直至叶子结点，将得到新的堆，称这个从 堆顶至叶子的调整过程为“筛选”输出二 13 27 38 49 50 65 76 973）第一个问题解决方法方法：从无序序列的第n/2个元素（即此无 序序列对应的完全二叉树的最后一个非终端结点)起，至第一个元素止，进行反复筛选例含8个元素的无序序列(49, 38, 65, 97, 76, 13, 27, 50)12345678493865977613275049386597 76132750
