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

《数据结构(Java版)样卷及答案第3版网络》由会员分享，可在线阅读，更多相关《数据结构(Java版)样卷及答案第3版网络（15页珍藏版）》请在装配图网上搜索。

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,71,63,95,9

9、0,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中，增加以下成员方法： （8

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

11、e; 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算法匹配过程如下，字符比较次数为20。2.

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

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 72 5.6, v

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

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

17、g数组指定分段的划分，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.next; while

18、 (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 T data; /

19、数据域，存储数据元素 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 TreePNode(

20、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

21、,); private String toString(TreePNode p, String tab) /算法同树的孩子兄弟链表，方法体省略 以横向凹入表示构造树或森林public class TreeP_String /以横向凹入表示构造树或森林，prelist数组存储树或森林的横向凹入表示字符串序列 /非递归算法，逐个结点添加方式，没有直接调用返回、插入结点方法 public static TreeP create(String prelist) TreeP tree = new TreeP(); /创建空树 if (prelist.length=0) return tree; /返回空

22、树 tree.root = new TreePNode(prelist0); /创建根结点 TreePNode p = tree.root; int len=0; /p结点的前缀t个数 for (int i=1; iprelist.length; i+) /创建元素为prelisti结点 /添加到tree森林的最后一棵树中，结点值去除了所有t前缀 int j=0; while (jprelisti.length() & prelisti.charAt(j)=t) j+; /统计prelisti串中t前缀个数 String str = prelisti.substring(j); /去除prel

23、isti串中若干前缀t if (j=len+1) /prelisti比p.data多一个t前缀 /插入作为p的第一个孩子 p.child = new TreePNode(str, p, null, null); p = p.child; len+; continue; while (len j) /prelisti比p.data的t少，p向上寻找插入位置 p=p.parent; /p向上一层 len-; p.sibling = new TreePNode(str, p.parent, null, null); /插入作为p结点的兄弟 p = p.sibling; return tree; 采用树的父母孩子兄弟链表存储一棵城市森林如图所示。15