《数据结构(Java版)叶核亚(第4版)》样卷及答案

-1-《数据结构（Java版）》课程样卷教材：《数据结构（Java版）（第4版）》，叶核亚编著，电子工业出版社，2015年7月出版。试题范围：第1～9章，掌握基础原理，熟悉经典算法，问答题形式考核。编程题重点是：1.单/双链表；2.二叉树/树，递归算法。这是必须掌握的，即使部分学生掌握不了递归算法，也必须考。不考内容：6.3线索二叉树求父母、插入、删除算法（没写），7.5.2Floyd，8.5.3平衡二叉树，第10章。可作为课程设计题。试卷范围和难度不超过样卷。4-0模拟样卷一、填空题（16分=2分×8题）1.声明抽象数据类型的目的是________________________________________。2.以下数据存储结构声明为_________________________________________。∧table∧NodeT∧…∧…3.已知java.lang.String类声明以下成员方法：publicStringreplaceAll(Stringpattern,Stringstr)//将所有与pattern匹配的子串替换为str下列语句的执行结果是________________________________________。Stringtarget=aababbabac,pattern=ab,str=aba;System.out.println(\+target+\.replaceAll(\+pattern+\,\+str+\)=\+target.replaceAll(pattern,str)+\);4.A+B*(C-D*(E+F)/G+H)-(I+J)*K的后缀表达式为______________________。5.已知二维数组a[10][8]采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a[4][5]的存储地址是__________________________。6.由n个顶点组成的无向连通图，最多有_____________________条边。7.排序关键字序列（升序）{5,17,20,32,43,55,61,61*,72,96}，采用二分法查找算法，查找96的元素比较序列是____________________；查找35的元素比较序列是____________________。8.关键字序列{93,17,56,42,78,15,42*,25,19}，采用希尔排序（升序）算法，第一趟排序后的序列是_________________________________________。二、问答题（50分=5分×10题）1.已知目标串为aabcbabcaabcaababc，模式串为abcaababc，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。-2-2.画出以下稀疏矩阵非零元素三元组的十字链表存储结构。00065000180000000000000000000000004300860005900000000150032000087A3.已知一棵二叉树的遍历序列如下，画出这棵二叉树并进行中序线索化。中根遍历序列：CBDFEGAMLNKJOPRQIHS；后根遍历序列：CFGEDBMNLKRQPOJISHA4.设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18}，采用Huffman编码对这段正文进行压缩存储，画出所构造的Huffman树，并写出每个字符的Huffman编码。说明Huffman编码的特点和作用。5.已知以下无向图7G中各顶点按{A,B,C,D,E,F,G,H}次序存储。分别画出采用深度优先搜索（从A开始）和广度优先搜索（从D开始）遍历图时栈或顺序循环队列（容量为6）的动态变化示意图，说明栈或队列的作用。012345GHBECFDA676.什么是图的最小生成树？构造以下带权无向图的最小生成树，给出该最小生成树代价。说明Prim算法和Kruskal算法的差别。GF（a）带权无向图411161519BACDE71312520106（b）最小生成树，代价为45（c）Prim算法不断扩充T，T顶点扩充次序为AGBC……（d）Kruskal算法不断合并树，依次选择边(B,G),(A,G),(C,D),(E,F)……GF411BACDE125106GF4BACDE5106GF4BACDE12567.画出以下带权有向图采用Dijkstra算法以E为源点的单源最短路径所选择的边，写出各路径长度。59133738181120158ADCBFE23198.设散列表采用链地址法，初始容量length为10；散列函数采用除留余数法hash(key)=key%length；装填因子为0.75，散列数组容量以2倍扩充。由关键字序列{16,75,60,43,54,90,46,31,27,88,64,50}构造散列表，分别画出扩容前和最终状态图，计算成功ASL。9.画出由关键字序列{50,16,74,60,43,16,90,46,31,29,88,71,64,13,65}构造的一棵二叉排序树，计算成功ASL。执行删除结点50、插入50，再画出操作后的二叉排序树。-3-10.什么是堆序列？堆序列在堆排序算法中起什么作用？将关键字序列{29,10,25,26,58,12,31,18,47}分别建成一个最大堆和一个最小堆，写出堆序列，画出对应的完全二叉树；写出每一趟堆排序结果。若有关键字重复元素，做标记以区别。三、程序阅读和改错题（18分=6分×3题）1.SortedCirDoublyListT排序循环双链表类增加以下成员方法，回答问题。①以下merge(list)方法功能是什么？方法体中，while、if等语句功能是什么？②已知两条排序循环双链表this和list的序列为{26,37,61,81}和{18,53,75,86,90}，画出两者的存储结构，以及执行merge(list)方法后的状态，标明各变量的位置。publicvoidmerge(SortedCirDoublyListTlist)//方法功能是什么？{DoubleNodeTp=this.head.next;DoubleNodeTq=list.head.next;while(p!=this.head&&q!=list.head)//循环语句功能是什么？if((p.data).compareTo(q.data)0)p=p.next;else{q.prev=p.prev;p.prev.next=q;p.prev=q;q=q.next;q.prev.next=p;}if(q!=list.head)//选择语句功能是什么？{q.prev=this.head.prev;this.head.prev.next=q;list.head.prev.next=this.head;this.head.prev=list.head.prev;}list.head.prev=list.head;//为什么要这两句？list.head.next=list.head;}2.阅读程序，回答以下问题。publicstaticStringBuffertrim(StringBuffers)//将s中所有空格删除，返回操作后的s串{inti=0;while(is.length()&&s.charAt(i)!='')//i记住第1个空格下标i++;for(intj=i;js.length();j++)if(s.charAt(j)!='')s.setCharAt(i++,s.charAt(j));//非空格字符向前移动到空格字符位置returns;}①对于以下调用语句，运行结果是什么？正确的运行结果是什么？StringBufferstr=newStringBuffer(abcdefxyz);System.out.println(trim(\+str+\)=+trim(str));②trim()方法怎样实现所求功能？算法存在什么错误？③如何改正？-4-3.已知TreeT类表示父母孩子兄弟链表存储的树，回答以下问题。①设一棵树（森林）的广义表表示如下，画出所构造的树以及树的存储结构图，输出树的横向凹入表示法。树（森林）的广义表表示：G(A(C(E,F),B,D)),H(J(L),I,K)②以下levelorder()方法的功能是什么？对于上述树（森林），运行结果是什么？③levelorder()方法存在什么错误？如何改正？publicvoidlevelorder(){LinkedQueueTreeNodeTque=newLinkedQueueTreeNodeT();for(TreeNodeTp=this.root;p!=null;p=que.poll()){System.out.print(p.data+);for(p=p.child;p!=null;p=p.sibling)que.add(p);}System.out.println();}四、程序设计题（16分=8分×2题）1.SinglyListT单链表类增加以下成员方法，画出操作示意图。//删除this中所有与pattern匹配的子表，BF模式匹配查找到再删除publicvoidremoveAll(SinglyListTpattern)2.实现以下对二叉链表存储的二叉树类BinaryTreeT操作的方法。//判断二叉树bitree是否二叉排序树TextendsComparable?superTbooleanisSorted(BinaryTreeTbitree)-5-4-0样卷答案一、填空题（16分=2分×8题）1.使数据类型的定义和实现分离，使一种定义有多种实现。2.见《数据结构（Java版）（第4版）习题解答》第7页习2-6。3.aababbabac.replaceAll(ab,aba)=aabaabababaac4.ABCDEF+*G/-H+*+IJ+K*-，见《数据结构（Java版）（第4版）习题解答》第27页习4-5。5.mat+(i*n+j)*4=1000+(4*8+5)*4=11486.n*(n-1)/27.{43,61*,72,96}；{43,17,20,32}。解释见《习题解答》第54页习8-9。8.见《数据结构（Java版）（第4版）习题解答》第57页习9-4。二、问答题（50分=5分×10题）1.模式串abcaababc改进的next数组为j012345678模式串abcaababc110jppp中最长相同的前后缀子串长度k-100011212kp与jp比较≠≠=≠=≠==改进的next[j]-100-110200KMP算法匹配过程如下，字符比较次数为20。target≠patterncaba（b）第2次匹配，t1=p0，……，t4≠p3，比较4次，next[3]=-1cabbabact0t1p0p1ab＝aacp5aat14bp2t2bt3t4t5t6t7t8t9t10t11t12t13p3p4acbp8p6p7abt17ct15t16target≠patterncaba（a）第1次匹配，t0=p0，t1≠p1，比较2次，next[1]=0cabbabact0t1p0p1ab＝aacp5aat14bp2t2bt3t4t5t6t7t8t9t10t11t12t13p3p4acbp8p6p7abt17ct15t16＝＝target≠patterncaba（c）第3次匹配，t5=p0，……，t11≠p6，比较7次，next[6]=2cabbabact0t1p0p1ab＝aacp5aat14bp2t2bt3t4t5t6t7t8t9t10t11t12t13p3p4acbp8p6p7abt17ct15t16＝＝＝＝＝targetpatterncaba（d）第4次匹配