最简单《数据结构》 期末考试试卷（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.二维数组中元素aij的地址Loc（aij）的计算公式为 。 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 for(int j=0;j int (2) table[j]= table[j+1]; =temp;(3) exchange=true; } } } } 此程序的主要功能是： （4） 2、编写基于顺序表的折半查找算法，找到则返回下标，没找到返回-1 public int binarySearch（int[] value，int key）{