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

《数据结构（Java版）》课程样卷

教材：《数据结构（Java版）（第4版）》，叶核亚编著，电子工业出版社，2015年7月出版。 试题范围：第1～9章，掌握基础原理，熟悉经典算法，问答题形式考核。

编程题重点是：1.单/双链表； 2.二叉树/树，递归算法。这是必须掌握的，即使部分学生掌握不了递归算法，也必须考。

不考内容：6.3 线索二叉树求父母、插入、删除算法（没写），7.5.2 Floyd，8.5.3 平衡二叉树，第10章。可作为课程设计题。

试卷范围和难度不超过样卷。

4-0 模拟样卷

一、 填空题（16分=2分×8题）

1. 声明抽象数据类型的目的是________________________________________。 2. 以下数据存储结构声明为_________________________________________。

table∧…∧∧Node…∧ 3. 已知java.lang.String类声明以下成员方法：

public String replaceAll(String pattern, String str) String target=\

System.out.println(\ target.replaceAll(pattern,str)+\

//将所有与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. 已知目标串为\，模式串为\，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。

- 1 -

2. 画出以下稀疏矩阵非零元素三元组的十字链表存储结构。

?0?0??59???0?0??0??18000320015?0000000??000860043??0000000? 0000000??0000000?00065000??A7?8

3. 已知一棵二叉树的遍历序列如下，画出这棵二叉树并进行中序线索化。

中根遍历序列：CBDFEGAMLNKJOPRQIHS； 后根遍历序列：CFGEDBMNLKRQPOJISHA

4. 设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依次为

{23,5,17,4,9,31,29,18}，采用Huffman编码对这段正文进行压缩存储，画出所构造的Huffman树，并写出每个字符的Huffman编码。说明Huffman编码的特点和作用。

5. 已知以下无向图G7中各顶点按{A,B,C,D,E,F,G,H}次序存储。分别画出采用深度优先搜索（从A开始）和广度优先搜索（从D开始）遍历图时栈或顺序循环队列（容量为6）的动态变化示意图，说明栈或队列的作用。

10A2CB3D5FH74EG6

6. 什么是图的最小生成树？构造以下带权无向图的最小生成树，给出该最小生成树代价。说明Prim算法和Kruskal算法的差别。

A7B12419C56G13151620DF10E11A6F10GE11DB12C4A6GEB4FA6GF10E B124C55DC5D（c）Prim算法不断扩充T，（d）Kruskal算法不断合并树，依次 （a）带权无向图（b）最小生成树，代价为45T顶点扩充次序为AGBC……选择边(B,G),(A,G),(C,D),(E,F)……7. 画出以下带权有向图采用Dijkstra算法以E为源点的单源最短路径所选择的边，写出各路径长度。

A20B938152337C18511E8

19D13F

8. 设散列表采用链地址法，初始容量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，再画出操作后的二叉排序树。

- 2 -

10. 什么是堆序列？堆序列在堆排序算法中起什么作用？将关键字序列{29, 10, 25, 26, 58, 12, 31, 18, 47}分别建成一个最大堆和一个最小堆，写出堆序列，画出对应的完全二叉树；写出每一趟堆排序结果。若有关键字重复元素，做标记以区别。

三、 程序阅读和改错题（18分=6分×3题）

1. SortedCirDoublyList排序循环双链表类增加以下成员方法，回答问题。 ① 以下merge(list)方法功能是什么？方法体中，while、if等语句功能是什么？ ② 已知两条排序循环双链表this和list的序列为{26,37,61,81}和{18,53,75,86,90}，画出两者的存储结构，以及执行merge(list)方法后的状态，标明各变量的位置。

public void merge(SortedCirDoublyList list) //方法功能是什么？ {

DoubleNode p=this.head.next;

DoubleNode q=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. 阅读程序，回答以下问题。

public static StringBuffer trim(StringBuffer s) {

int i=0;

while (i

for (int j=i; j

if (s.charAt(j)!=' ')

s.setCharAt(i++, s.charAt(j)); //非空格字符向前移动到空格字符位置 return s; }

//将s中所有空格删除，返回操作后的s串

① 对于以下调用语句，运行结果是什么？正确的运行结果是什么？

StringBuffer str = new StringBuffer(\ a bc d e f xyz\System.out.println(\

② trim()方法怎样实现所求功能？算法存在什么错误？ ③ 如何改正？

- 3 -

3. 已知Tree类表示父母孩子兄弟链表存储的树，回答以下问题。

① 设一棵树（森林）的广义表表示如下，画出所构造的树以及树的存储结构图，输出树的横向凹入表示法。

树（森林）的广义表表示：G(A(C(E,F),B,D)),H(J(L),I,K)

② 以下levelorder()方法的功能是什么？对于上述树（森林），运行结果是什么？ ③ levelorder()方法存在什么错误？如何改正？

public void levelorder() {

LinkedQueue> que=new LinkedQueue>(); for (TreeNode p=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. SinglyList单链表类增加以下成员方法，画出操作示意图。

//删除this中所有与pattern匹配的子表，BF模式匹配查找到再删除 public void removeAll(SinglyList pattern)

2. 实现以下对二叉链表存储的二叉树类BinaryTree操作的方法。

//判断二叉树bitree是否二叉排序树

> boolean isSorted(BinaryTree bitree)

- 4 -

4-0 样卷答案

一、 填空题（16分=2分×8题）

1. 使数据类型的定义和实现分离，使一种定义有多种实现。 2. 见《数据结构（Java版）（第4版）习题解答》第7页习2-6。

3. \4. ABCDEF+*G/-H+*+IJ+K*-，见《数据结构（Java版）（第4版）习题解答》第27页习4-5。 5. mat+(i*n+j)*4=1000+(4*8+5)*4=1148 6. n*(n-1)/2

7. {43,61*,72,96}；{43,17,20,32}。解释见《习题解答》第54页习8-9。 8. 见《数据结构（Java版）（第4版）习题解答》第57页习9-4。

二、 问答题（50分=5分×10题）

1. 模式串\改进的next数组为 j 模式串 \p0p1?pj?1\中最长相同的前后缀子串长度k p与p比较 改进的next[j] kj0 a -1 -1 t7cbp7t8acp81 b 0 ≠ 0 t9a2 c 0 ≠ 0 t10b3 a 0 = -1 t11ct12a4 a 1 ≠ 1 t13a5 b 1 = 0 t14bt15a6 a 2 ≠ 2 t16b7 b 1 = 0 t17c8 c 2 = 0 KMP算法匹配过程如下，字符比较次数为20。

t0targetpatternat1at2bcp2t3cap3t4bap4t5abp5t6bap6＝ap0≠bp1（a）第1次匹配，t0=p0，t1≠p1，比较2次，next[1]=0t0targetat1at2bt3ct4bt5aap4t6bbp5t7cap6t8abp7t9acp8t10bt11ct12at13at14bt15at16bt17c＝＝＝cp2patternap0bp1p3（b）第2次匹配，t1=p0，……，t4≠p3，比较4次，next[3]=-1≠a

t0targetat1at2bt3ct4bpatternt5at6bt7ct8at9at10bt11ct12abp7t13acp8t14bt15at16bt17c＝＝＝＝＝＝bp5t10bbp1ap0bp1cp2ap3ap4p6（c）第3次匹配，t5=p0，……，t11≠p6，比较7次，next[6]=2t0targetat1at2bt3ct4bt5at6bt7ct8apatternt9aap0t11ct12at13at14bt15at16bt17c＝≠a＝＝＝＝＝bp7cp2ap3ap4bp5ap6（d）第4次匹配，t11=p2，……，t17=p8，比较7次，匹配成功，与模式串匹配的子串序号为9

2. 见《数据结构（Java版）（第4版）习题解答》第34页习5-9。

- 5 -

＝cp8

3. 见《数据结构（Java版）（第4版）习题解答》第37页习6-19、第42页图6.9。 【评分标准】构造二叉树3分，中序线索化2分。 4. 见《数据结构（Java版）（第4版）习题解答》第44页习6-31、6-34。 5. 见《数据结构（Java版）（第4版）习题解答》第48页习7-15。 6. 见《数据结构（Java版）（第4版）习题解答》第50页习7-11、7-15。 7. 见《数据结构（Java版）（第4版）习题解答》第52页习7-15。 8. 见《数据结构（Java版）（第4版）习题解答》第55页习8-12。 9. 见《数据结构（Java版）（第4版）习题解答》第56页习8-19。 10. 堆序列概念见教材；构造的堆见《数据结构（Java版）（第4版）习题解答》第59页习9-10。

三、 程序阅读和改错题（18分=6分×3题）

1. ① merge(list)方法功能是：归并两条排序循环双链表，将list中所有结点归并到this中，合并后设置list空。

方法体中，while语句功能是：p、q分别遍历this和list排序循环双链表，比较p、q结点值有大小，若q结点值较小，将q结点插入到p结点之前。当遍历完一条循环双链表时，while循环结束。

while之后的if语句功能是：若q!=list.head，表示遍历this结束，要将list中剩余结点（q结点开始）链接到this尾，并使this与list的最后结点连接成为环形。

合并后设置list为空，否则两条循环双链表将共用某些结点，会造成混乱。 ② 算法描述如下图所示，与第4版图9.17算法同。

prevdatanextthis.head①list.head②③p26q18⑤37④q537586906181(a) 比较p、q结点值，若p结点值小，则继续比较p的后继；否则（≥），将q结点插入在p之前pthis.head④⑥list.head⑤(b) 重复执行(a)，归并结点；当p==this.head且q!=list.head时，将q结点插入在this的最后结点之后； 并使this与list的最后结点连接成为环形。设置list为空循环双链表1853758690263761①81②q③

2. 见《数据结构（Java版）（第4版）习题解答》第21页【实验题3-11】。 3. ① 先根次序遍历树，输出树的横向凹入表示法： GHG A AJIK C E CBDL F B EF D （a）森林H J L I K - 6 -

childdatarootAC∧∧BG∧siblingH∧∧J∧D∧∧L∧∧I∧K∧parent

∧E∧F∧（b）森林的父母孩子兄弟链表② 功能是按层次遍历树。上述森林的运行结果如下：

层次遍历树： G A C B D E F

③ levelorder()算法存在的错误是，只遍历了一棵树，无法遍历森林。改正如下。

public void levelorder() //按层次遍历树（森林），从根开始依次遍历森林中的每棵树 {

System.out.print(\层次遍历树（森林）： \

LinkedQueue> que = new LinkedQueue>(); //创建一个空队列 for (TreeNode q=this.root; q!=null; q=q.sibling) //遍历森林 {

for (TreeNode p=q; p!=null; p=que.poll())

//遍历一棵树，根没有进队

{ System.out.print(p.data+ \

for (p=p.child; p!=null; p=p.sibling) //所有孩子结点入队 que.add(p); }

if (q.sibling!=null)

System.out.print(\，\ }

System.out.println(); }

上述森林的运行结果如下，结果正确，从根开始依次遍历森林中的每棵树。

层次遍历树（森林）： G A C B D E F ，H J I K L

四、 程序设计题（16分=8分×2题）

1. 单链表删除所有匹配子表操作的算法描述如图所示，该算法使用BF模式匹配查找到匹配子表，可

一次删除匹配子表。

frontthis.headapattern.headbstartabcpa∧q==nullbc∧＝＝ab（a）当一次匹配成功时，删除从start结点开始的一条匹配子表frontthis.headapattern.headbstartabc∧∧＝c

p=null＝＝ab（b）start再次从front的后继结点开始寻找匹配子表并删除removeAll()方法声明如下，删除所有与pattern匹配的子表。

//删除this中所有与pattern匹配的子表，BF模式匹配查找到再删除。 public void removeAll(SinglyList pattern)

- 7 -

＝c{

if (pattern.isEmpty()) return;

Node start=this.head.next, front=this.head; while (start!=null)

{ Node p=start, q=pattern.head.next;

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; } } }

2. 实现以下对二叉链表存储的二叉树类BinaryTree操作的方法。

public class BinaryTree_isSorted {

private static BinaryNode bfront;

//判断一棵二叉树是否为二叉排序树，T必须实现Comparable接口 public static> boolean isSorted(BinaryTree bitree) {

bfront=null;

return isSorted(bitree.root); }

//判断以p为根的子树是否为二叉排序树，bfront引用p在中根遍历次序下的前驱结点。 //按中根次序遍历一棵二叉树，若各元素按升序排序，则是一棵二叉排序树。 //二叉链表存储的二叉树，中根次序遍历是递归算法。

private static> boolean isSorted(BinaryNode p) {

if (p==null)

return true;

if (!isSorted(p.left)) //判断p的左子树 return false;

if (bfront!=null && p.data.compareTo((T)bfront.data)<0) return false;

bfront=p;

return isSorted(p.right); } }

//判断p的右子树

- 8 -

本文来源：https://www.bwwdw.com/article/vi7v.html