最简单《数据结构》
期末考试试卷（A卷）
班级学号姓名成绩
（本卷需要草稿纸）
一、选择题（每题2分，共30分）
1.在以下的叙述中，正确的是（ )。
A.线性表的顺序存储结构优于链表存储结构
B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D.线性表的链表存储结构优于顺序存储结构
2.从表中任一结点出发，都能扫描整个表的是（）。
A.单链表
B.顺序表
C.循环链表
D..静态链表
3.在一个长度为n的顺序存储的线性表中，向第i个元素（0≤i≤n-1）位置插入一个新元素时，需要从后向前依次后移( )个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
4.若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为( )。
A. p=p.next.next
B. p.next=p.next.next
C. q.next=p.next
D. q.next=q.next.next
5.设一数列的输入顺序为1,2,3,4,5,6，出栈操作不可能排成的输出序列为( )。
A.3,2,5,6,4,1
B.1,5,4,6,2,3
C.2,4,3,5,1,6
D.4,5,3,6,2,1
6.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
7.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。
A. 2
B. 1
C. 0
D. -1
8.对线性表进行二分查找时，要求线性表必须( )
A.以顺序方式存储
B.以顺序方式存储，且结点按关键字值有序排列
C.以链接方式存储
D.以链接方式存储，且结点按关键字值有序排列
9.下列各种结构的物理存储必须占用连续的存储空间的是 ( )
A．数组 B.栈 C.二叉树 D.链表
10. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，A11为第一元素，其存储地址为1，每个元素占1个地址空间，则A33地址为( )
A.13
B.33
C.18
D.40
11. 用二分查找法查找具有N个结点的顺序表时，查找每个结点的平均比较次数是( )
A.O(N2 )
B.O(Nlog2N)
C.O(N)
D.O(log2N)
12.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
13. 对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为（）
A. n/2
B. (n+1)/2
C. (n-1)/2
D.n/4
14. 根据数据集合{23,44,36,48,52,73,64,58}建立散列表，采用h(K)=K%7计算散列地址，则同义词元素的个数最多为（）个。
A.1
B. 2
C. 3
D. 4
15. 以下数据结构中哪个是非线性结构（）
A.队列
B. 栈
C. 顺序表
D. 二叉树
二、填空题（每空2分，共20分）
1.插入排序算法主要有、和希尔排序。
2.散列技术的两个关键问题是和。
3.队列的插入操作在进行，删除操作在进行。
4.一维数组采用存储结构。
5.二维数组中元素a ij的地址Loc（a ij）的计算公式为。
6.顺序查找优点是。
缺点是。
三、简答题（每题5分，共10分）
1.已知一棵二叉树的先根和中根遍历序列如下，画出据此构造的二叉树并写出后根遍历序列。
先根遍历序列：ABCIDEHFJG
中根遍历序列：BICAHEJFGD
2.假设用于通信的电文仅由ABCDEFGH 8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。
试为这8个字母设计哈夫
曼编码。
四、程序填空与编写程序(每题10分，共20分)
1、程序填空，并写出程序的主要功能（1、
2、3空2分，4空4分）public static void bubbleSort(int[] table){
boolean (1)
for(int i=1;i<table.lenth&&exchange;i++){
exchange=false;
for(int j=0;j<table.length-i;j++){
if(table[j]>table[j+1]){
int (2)
table[j]= table[j+1];
=temp;(3)
exchange=true;
}
} } }
此程序的主要功能是：（4）2、编写基于顺序表的折半查找算法，找到则返回下标，没找到返回-1 public int binarySearch（int[] value，int key）{
}
五、算法分析应用题（每题10分，共20分）
1.以数组{503，87，512，61，908，170，897，275，653，426}为例，手工执行排序算法，写出每一趟排序结束时的数组状态。
（1）直接插入算法（5分）
（2）冒泡排序算法（5分）
2、以数组{17，82，55，86，99，01，56，34，13，80}建立一棵二叉排序树（5分），再将其调整为平衡二叉树（5分）。