《数据结构（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
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
public void merge(SortedCirDoublyList
DoubleNode
DoubleNode
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 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 2. 实现以下对二叉链表存储的二叉树类BinaryTree //判断二叉树bitree是否二叉排序树 - 4 -
相关推荐：
loading