数据结构的作业PPT学习教案

1、会计学1 数据结构的作业数据结构的作业 第二章作业：第二章作业： 1.指出以下算法中的错误和低效（即费时）之处，并将指出以下算法中的错误和低效（即费时）之处，并将 它改为一个既正确又高效的算法。它改为一个既正确又高效的算法。 Proc DeleteK(VAR a:sqlist; i,k:integer); 从顺序存储结构的线性表从顺序存储结构的线性表a中删除自第中删除自第i个元素起的个元素起的K个元素个元素 If (ia.last) then error (Argument invalid) else for count:=1 to k do 【for j:=a.last downto i+1

2、 do a.elemj-1:=a.elemj; a.last:=a.last-1 】 ENDP; deleteK 2.设顺序表设顺序表Va中的数据元素递增有序。试写一算法，将中的数据元素递增有序。试写一算法，将X插入到插入到 顺序表的适当位置上，以保持该表的有序性。顺序表的适当位置上，以保持该表的有序性。 第1页/共19页 3.用单链表实现用单链表实现Locate(L,x)函数。（可参考函数。（可参考P26算法算法 2.5) 4.上机题：设单链表上机题：设单链表Va中的数据元素递增有序。试编中的数据元素递增有序。试编 写程序，将数据写程序，将数据X插入单链表插入单链表Va，要求插，要求插 入后

3、保持该表的有序性。入后保持该表的有序性。 5.写出双向链表删除第写出双向链表删除第i个结点的算法。个结点的算法。 6.写出求双向循环链表长度的算法。（注：头结点写出求双向循环链表长度的算法。（注：头结点 不算）不算） 第2页/共19页 第三章作业：第三章作业： 1.上机题：编写程序，判别表达式中（、）是否配对出现上机题：编写程序，判别表达式中（、）是否配对出现 。 2.写出下列程序段的输出结果（栈的元素类型为：写出下列程序段的输出结果（栈的元素类型为：char). var s:stack; x,y:char; begin x:=c; y:=k; push(s,x); push(s, a); p

4、ush(s,y); x:=pop(s); push(s, t); push(s,x); x:=pop(s); push(s, s); while not empty(s) do 【y:=pop(s); write(y)】; writeln(x); end; 第3页/共19页 第四章作业第四章作业: 1.用用4.1.2提供的提供的7种串的基本操作来实现种串的基本操作来实现insert(s,pos,t)和和 delete(s,pos,len)操作操作. 2.上机题：编写程序，完成静态存储串时的上机题：编写程序，完成静态存储串时的insert(s,pos,t) 或或delete(s,pos,len)

5、操作。操作。 3.课堂练习：执行以下程序段，写出运行结果。课堂练习：执行以下程序段，写出运行结果。 proc p; creat(s,this is a book); replace(s,substr(s,3,7),ese are); creat(t,concat(s,s); creat(u,xyxyxyxyxyxy); creat(v,substr(u,6,3); creat(w,w); writeln(t,v,replace(u,v,w) endp; p 第4页/共19页 第五章作业：第五章作业： 1.假设有二维数组假设有二维数组a:array1.6,0.7 of elemtp; 每个数据元

6、每个数据元 素占素占6个字节个字节,存储器按字节编址。存储器按字节编址。a的基地址为的基地址为1000,则则 ： (1) 数组数组a的体积；的体积； (2)数组数组a的最后一个元素的第一个字节的地址；的最后一个元素的第一个字节的地址； (3)按行存储时，按行存储时，a2,4的第一个字节的地址；的第一个字节的地址； (4)按列存储时，按列存储时，a5,7的第一个字节的地址；的第一个字节的地址； 第5页/共19页 第六章作业：第六章作业： 1.一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？ 2.试分别画出具有试分别画出具有3个结点的树和个结点的树和3个结点的二叉树的所有个结

7、点的二叉树的所有 不同形态。不同形态。 3.已知一棵度为已知一棵度为k的树中有的树中有n1个度为个度为1的结点，的结点，n2个度为个度为2 的结点，的结点，nk个度为个度为k的结点，问该树中有多少个的结点，问该树中有多少个 叶子结点。叶子结点。 4.对题对题2所得的所得的3个结点的二叉树的个结点的二叉树的5种不同形态，分别写种不同形态，分别写 出先序、中序、后序的遍历序列。出先序、中序、后序的遍历序列。 第6页/共19页 5.一棵含有一棵含有n个结点的个结点的k叉树，可能达到的最大深度和最小叉树，可能达到的最大深度和最小 深度各为多少？深度各为多少？ 6.上机题：按先序次序建立以下二叉树，然后

8、分行输出它上机题：按先序次序建立以下二叉树，然后分行输出它 的先序、中序、后序序列。的先序、中序、后序序列。 A B FC J M 第7页/共19页 7.写出下列各树的先根序列写出下列各树的先根序列,后根序列后根序列,并且画出对应的二并且画出对应的二 叉树叉树. A A B C A BC A B CD EF G H IJK 8.画出第画出第7题的森林相应的二叉树题的森林相应的二叉树. 9.画出和下列已知序列对应的树画出和下列已知序列对应的树T: 树的先根次序访问序列为树的先根次序访问序列为:GFKDAIEBCHJ,而且而且 树的后根次序访问序列为树的后根次序访问序列为:DIAEKFCJHBG。

9、 第8页/共19页 10.画出和下列二叉树相应的森林画出和下列二叉树相应的森林: AA B C A BC A B D C H E K F G J M I 11.假设用于通讯的电文仅由假设用于通讯的电文仅由8个字母组成个字母组成,字母在电文中字母在电文中 出出 现的频率分别为现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、 0.21、0.10。试为这。试为这8种字母设计哈夫曼编码。种字母设计哈夫曼编码。 第9页/共19页 第七章作业：第七章作业： 1.请给出下图的请给出下图的: (1)每个顶点的入度和出度每个顶点的入度和出度. (2)强连通分量强连通分量 (3)邻接矩阵

10、邻接矩阵 (4)邻接表邻接表 (5)逆邻接表逆邻接表 (6)十字链表十字链表 1 3 6 5 42 2.写出以数组为存储结构写出以数组为存储结构,函数函数firstadj(G,v) 的算法的算法. 3.写出以数组为存储结构写出以数组为存储结构,函数函数nextadj(G,v,w) 的算法的算法. 第10页/共19页 4.上机题上机题:建立下图建立下图(以数组或邻接表为存储结构以数组或邻接表为存储结构),然后输出图然后输出图 的深度优先序列、广度优先序列。的深度优先序列、广度优先序列。 A C EGF B H D 5.对下图用普里姆算法、克鲁斯卡尔算法构造最小生成树对下图用普里姆算法、克鲁斯卡尔

11、算法构造最小生成树 . （画出构造过程）。（画出构造过程）。 3 1 4 5 2 3 7 9 4 6 6 3 第11页/共19页 6.请列出下图中全部可能的拓朴有序序列请列出下图中全部可能的拓朴有序序列. 1 2 5 3 6 4 7.对于下图所示的对于下图所示的AOE网网,计算各事件的计算各事件的ve(i)和和vl(i),各活各活 动的动的e(i) 和和l(i);列出关键活动和关键路径列出关键活动和关键路径. 1 2 3 4 6 5 a1=6 a2=6 a3=1 a5=2 a6=7 a7=4 a4=2 第12页/共19页 8. 用迪杰斯特拉用迪杰斯特拉(Dijkstra)算法求下图中从顶点算法

12、求下图中从顶点1到其它各到其它各 顶点的最短路径，画出各步的状态。顶点的最短路径，画出各步的状态。 1 1 2 3 4 5 6 10 5 3 1 2 9.用弗洛伊德（用弗洛伊德（Floyd）算法求下图所示有向图中各顶点）算法求下图所示有向图中各顶点 之间的最短路径。之间的最短路径。 A B C 6 10 2 1 8 第13页/共19页 第九章作业第九章作业: 1.画出对长度为画出对长度为10的有序表进行折半查找的判定树的有序表进行折半查找的判定树,并求并求 出等概率时查找成功的平均查找长度出等概率时查找成功的平均查找长度. 2.有一含有有一含有5个记录的有序序列及权值如下个记录的有序序列及权值

13、如下 ： 关键字：关键字：A B C D E 权值：权值： 1 8 2 5 6 (1) 画出对以上有序序列进行折半查找的判定树，并计算画出对以上有序序列进行折半查找的判定树，并计算 它的它的PH值。值。 (2)构造它的次优查找树并加以适当调整，计算它的构造它的次优查找树并加以适当调整，计算它的PH值值 。 第14页/共19页 3.有关键字序列有关键字序列5，37，90，53, 60表表; (1)构造它的二叉排序树构造它的二叉排序树;(画出构造过程画出构造过程) (2)构造它的平衡二叉排序树构造它的平衡二叉排序树;(画出构造、调整过程）画出构造、调整过程） 4.某系部学生的学号由某系部学生的学号

14、由6位十进制组成：位十进制组成：C1C2C3C4C5C6 。 其中其中c1c2为入学年份的后两位；为入学年份的后两位；c3为专业号；为专业号；c4c5c6为为 同一系部的学生的顺序编号。假设某系部在校生为同一系部的学生的顺序编号。假设某系部在校生为500 人，请用直接定址法为该系部学生设计一个哈希表。人，请用直接定址法为该系部学生设计一个哈希表。 第15页/共19页 5.有学生的生日数据如下：有学生的生日数据如下： 年年.月月.日日 75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 . 请以生日日期为关键字，设计一个长请以生日日期为关键

15、字，设计一个长 度为度为1000的哈希表，使其冲突尽量少的哈希表，使其冲突尽量少 。 第16页/共19页 6.上机题：建立一棵二叉排序树，输入序列为（上机题：建立一棵二叉排序树，输入序列为（45，24， 53，12，24，90），然后中序遍历此树，得到一个关键），然后中序遍历此树，得到一个关键 字的有序序列。字的有序序列。 7.在地址空间为在地址空间为013的散列区中的散列区中,对以下关键字序列构造对以下关键字序列构造 两个哈希表两个哈希表: (Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) (1)用线性探测开放定址法处理冲突用线性探测开放

16、定址法处理冲突; (2)用链地址法处理冲突用链地址法处理冲突; (3)求出以上两个哈希表在等概率情况下，查找成功、查求出以上两个哈希表在等概率情况下，查找成功、查 找不成功时的平均查找长度（用公式计算）。找不成功时的平均查找长度（用公式计算）。 设哈希函数为设哈希函数为H(key)=| key的第一个字母在字母表的序号的第一个字母在字母表的序号/2 | 第17页/共19页 第十章作业第十章作业: 1.有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下: (32,54,12,24,32,47) (1)请用直接插入排序算法对其进行排序请用直接插入排序算法对其进行排序.(画出每趟排序示图画出每趟排序示图) (2)请用希尔排序算法对其进行排序请用希尔排序算法对其进行排序.(画出每趟排序示图画出每趟排序示图,d=2,1) (3)请用快速排序算法对其进行排序请用快速排序算法对其进行排序.(画出每趟排序示图画出每趟排序示图) (4)请用树型选择排序算法对其进行排序请用树型选择排序算法对其进行排序.(画出排序示图画出排序示图