数据结构(Java版)样卷及答案第3版网络

1、数据结构（java版）课程样卷一. 填空题（20分，每空2分）1. 声明抽象数据类型的目的是_(unit1)_。2. 右侧数据存储结构声明为_(unit2)_。3. 中缀表达式a+b*(c-d*(e+f)/g+h)-(i+j)*k的后缀表达式为abcdef+*g/-h+*+ij+k*-_(unit4)_。4. 设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有_36_unit4_个元素。5. 已知二维数组a108采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a45的存储地址是_1148 unit5_。6. 已知一棵完全二叉树的根（第0个）结点层次

2、为1，则第100个结点的层次为_。7. 中根遍历序列和后根遍历序列相反的二叉树是_。8. 由256个权值构造一棵哈夫曼树，则该二叉树共有_结点。9. 由n个顶点组成的无向连通图，最多可以有_条边。10. 10个元素的排序数据序列采用折半查找的平均查找长度是（写出算式）_。二. 问答题（50分，每题5分）1. 已知目标串为aabcbabcaabcaababc，模式串为abcaababc，写出模式串改进的next数组；画出kmp算法的匹配过程，给出字符比较次数。2. 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什

3、么？什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？3. 已知一棵二叉树的中根次序遍历序列为cbdfegamlnkjoprqihs，后根次序遍历序列为cfgedbmnlkrqpojisha，画出这棵二叉树并进行中序线索化。4. 设一段正文由字符集a,b,c,d,e,f,g,h组成，其中每个字符在正文中的出现次数依次为23,5,17,4,9,31,29,18，采用huffman编码对这段正文进行压缩存储，画出所构造的huffman树，并写出每个字符的huffman编码。说明huffman编码

4、的特点和作用。5. 构造以下带权无向图的最小生成树，给出该最小生成树的代价。说明prim算法和kruskal算法的差别。6. 画出以下带权有向图采用dijkstra算法以e为源点的单源最短路径所选择的边，并写出各路径长度。7. 散列表已知关键字序列为16,74,60,43,54,90,46,31,29,88,71,64,50，散列表长度为11，采用除留余数法的散列函数为hash(k)=k % 11，画出采用链地址法构造的散列表，计算（写出算式）。8. 什么是二叉排序树？二叉排序树画出由关键字序列25,27,30,12,11,18,14,20,15,22构造的一棵二叉排序树，计算。执行删除结点1

5、2、插入12，再画出操作后的二叉排序树。9. 快速排序算法的设计思想是怎样的？写出对关键字序列63,29,72,25,47,58,19,51,19*进行快速排序（升序）的中间过程。10. 什么是堆序列？堆序列在堆排序算法中起什么作用？将关键字序列29,10,25,26,58,12,31,18,47用筛选法分别建成一个最大堆和一个最小堆，写出两个堆序列并画出其对应的完全二叉树。三. 程序阅读和改错题（12分，每题6分）1. 下列removeall()方法欲删除target串中所有与pattern匹配的子串。public static stringbuffer removeall(stringbu

6、ffer target, string pattern) int m=target.length(), n=pattern.length(); int i=target.indexof(pattern), k=i; while (k!=-1) int j=k+n; k=target.indexof(pattern, j); while (k0 & jk | k0 & jm) target.setcharat(i+, target.charat(j+); return target; 对于以下调用语句，运行结果是什么？正确的运行结果是什么？stringbuffer target = new st

7、ringbuffer(ababdabcdabcabc); system.out.println(removeall(target, abc); removeall()方法怎样实现所求功能？ 算法存在什么错误？如何改正？2. 阅读以下程序，回答问题。public statict extends comparable int grade(t according, binarytree bitree) int result= new intaccording.length+1; grade(according, bitree.root, result); return result;private

8、statict extends comparable void grade(t according, binarynode p, int result) if (p!=null) int i=0; while (iaccording.length & pareto(accordingi)0) i+; resulti+; grade(according, p.left, result); grade(according, p.right, result); 上述方法的功能是什么？ 写出执行以下调用语句后的运行结果，并画出所创建的二叉树。integer value=79,82,

9、71,63,95,90,65,75,80,55;binarytree bitree1 = new completebinarytree(value);string str=优秀,良好,中等,及格,不及格;integer according=90,80,70,60;int result=grade(according, bitree1);for (int i=0; iresult.length; i+) system.out.print(stri+resulti+人，);system.out.println(); 四. 程序设计题（18分）1. 在单链表类singlylinkedlist中，增加

10、以下成员方法： （8分）public void removeall(singlylinkedlist pattern) /删除所有与pattern匹配的子表2. 采用父母孩子兄弟链表表示树，声明树的结点类和树类；写出以树的横向凹入表示构造树或森林的构造方法；对于以下树的横向凹入表示，画出树的存储结构。（10分）string prelist=中国,t北京,t江苏,tt南京,tt苏州, 韩国,t首尔,;数据结构（java版）课程样卷答案一. 填空题（20分=2分10）1. 使数据类型的定义和实现分离，使一种定义有多种实现。2. table可声明为数组或顺序表，元素为结点或单链表，声明为以下4种之一

11、：node table; singlylinkedlist table; seqlistnode table;seqlistsinglylinkedlist table;3. abcdef+*g/-h+*+ij+k*-4. 365. 11486. 77. 右单支二叉树（不包括空二叉树和只有根结点的二叉树）8. 5119. n*(n-1)/210. 二. 问答题（50分=5分10）1. 模式串abcaababc改进的next数组为j012345678模式串abcaababc中最长相同的前后缀子串长度k-100011212与比较=改进的nextj-100-110200kmp算法匹配过程如下，字符比

12、较次数为20。2. 栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。深度优先搜索遍历算法需要使用栈作为辅助结构，广度优先搜索遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产

13、生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。3. 4. huffman编码是一种变长的编码方案，满足基本要求：任何一个字符的编码都不是另一个字符编码的前缀。huffman编码用于实现无损的数据压缩。5. 6. 7. 8. 9. 快速排序每趟在数据序列中选择一个基准值作为比较依据，将序列划分成两个子序列，小于基准值的元素

14、序列在前端，大于基准值的元素序列在后端，并确定基准值的最终位置。递归调用再将各子序列进一步划分，直到子序列的长度为1，则完成排序。关键字序列：63 29 72 25 47 58 19 51 19* 0.8, vot=63, 19* 29 51 25 47 58 19 63 72 0.6, vot=19, 19* 29 51 25 47 58 19 63 72 1.6, vot=29, 19* 19 25 29 47 58 51 63 72 1.2, vot=19, 19* 19 25 29 47 58 51 63 72 4.6, vot=47, 19* 19 25 29 47 58 51 63

15、 72 5.6, vot=58, 19* 19 25 29 47 51 58 63 72 10. 将一个数据序列看成是一棵完全二叉树的层次遍历序列，如果任意一个结点的关键字值都小于等于（大于等于）它的孩子结点的关键字值，则该序列为最小（大）堆。最小（大）堆序列中，根结点值最小（大），因此，堆序列的作用是选取最小（大）值。三. 程序阅读题（12分=6分2） 1. 运行结果为“ababddbcdabcabc”，正确的运行结果是“ababdd”。 removeall()方法删除指定stringbuffer串的全部匹配子串操作，算法将待移动若干字符一次移动到位，从而提高算法效率。算法描述如下图所示，说

16、明如下：l 初始状态，设i表示首次匹配子串的首字符下标，如图（a）所示。l 再设j表示i匹配子串之后的字符下标，k表示下次匹配子串的首字符下标，如图（a）所示，将从jk-1之间的若干字符向前移动到i处，完成删除一个匹配子串操作。l 重复上一步操作，如果j=k，表示有两个连续的匹配子串，则没有移动字符，如图（b）所示；直到k=-1，表示其后没有匹配子串，则将从j开始至串尾的若干字符全部向前移动到i处，如图（c）所示。 算法存在错误，删除后没将字符串长度减少，导致仍然输出原长度字符串。改正：方法体return语句前增加以下一句： target.setlength(i);2. 分段统计二叉树的元素个

17、数，according数组指定分段的划分，result数组保存统计结果并返回。 程序运行结果如下，所创建的完全二叉树如图所示。优秀2人，良好2人，中等3人，及格2人，不及格1人，四. 程序设计题（18分=8+10） 以下给出参考程序。1. 删除所有与pattern匹配的子表。public void removeall(singlylinkedlist pattern) if (pattern.isempty() return; node start=head.next, front=head; while (start!=null) node p=start, q=pattern.head.n

18、ext; while (p!=null & q!=null & p.data.equals(q.data) /一次匹配 p=p.next; q=q.next; if (q!=null) /匹配失败，进行下次匹配 front=start; start=start.next; else /匹配成功，删除该匹配子表 front.next = p; start=p; 该算法使用bf模式匹配查找到匹配子表，可一次删除匹配子表。删除一个匹配子表操作描述如下图所示。2. 树的父母孩子兄弟链表结点类public class treepnode/树的父母孩子兄弟链表结点类，泛型t指定结点的元素类型 public

19、 t data; /数据域，存储数据元素 public treepnode parent; /指向父母结点的链 public treepnode child, sibling; /链，分别指向孩子、兄弟结点 /构造结点，参数分别指定元素、父母、孩子和兄弟结点 public treepnode(t data, treepnode parent, treepnode child, treepnode sibling) this.data = data; this.parent = parent; this.child = child; this.sibling = sibling; public

20、treepnode(t data) /构造指定值的叶子结点 this(data, null, null, null); public treepnode() this(null, null, null, null); 树类声明public class treep /树类，泛型t指定结点的元素类型 public treepnode root; /根结点，结点结构是树的父母孩子兄弟链表 public treep() /构造空树 this.root=null; public string tostring() /先根次序遍历树并返回树的横向凹入表示字符串 return 先根次序遍历树： n +tostring(root,); private string tostring(treepnode p, string tab) /算法同树的孩子兄弟链表，方法体省略 以横向凹入表示构造树或森林public class treep_string /以横向凹入表示构造树或森林，prelist数组存储树或森林的横向凹入表示字符串序列 /非递归算法，逐个结点添加方式，没有直接调用返回、插入结点方法 public static treep create(string prelist) t