最简单《数据结构》
期末考试试卷(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, 采用压缩存储方式,以行序为主存储,A 11为第一元素,其存储地址为1,每个元素占1个地址空间,则A 33地址为( )
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
exchange=false;
for(int j=0;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分)
最简单《数据结构》
期末考试试卷(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, 采用压缩存储方式,以行序为主存储,A 11为第一元素,其存储地址为1,每个元素占1个地址空间,则A 33地址为( )
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
exchange=false;
for(int j=0;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分)