《数据结构与算法》期末考试试卷(A卷)(2)

数据结构与算法

9. 当待排序序列基本有序时，以下排序方法中，( )最不利于其优势的发挥。

A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序

10. 若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要

比较( )次。

A.9 B.7 C.5 D.3

二、 填空题（每空1分，共20分）

1. 线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称为线性表的 ，n=0的线性表称为 。

2. 顺序表中逻辑上相邻的数据元素，其物理位置 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置 相邻。

3. 队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为 ，允许删除的一端称为 。

4. 一个串的任意连续字符组成的子序列称为串的 ，该串称为 。

5. 深度为4的平衡二叉树中至少有 个结点，至多有 个结点。

三、 上机实践题（每题20分，共40分）

答题要求提交如下资料：

1) 将代码复制到答卷中“【代码】：”处。

2) 运行结果中必须显示个人的名字，并截图复制到答卷中的“【运行效果图】：”处。如：

3) 提交完整的程序文件，并按题号分目录（如3.1、3.2）存放。

1. 编写一个顺序表类，实现对顺序表（顺序表长度为10，节点值为随机数字）就地逆置的操作。所谓逆置，就是把（a1,a2, ,an）变成（an,an-1, ,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。

2. 编写一个排序方法类，实现用插入排序方法对单链表（链表长度为5，节点值为随机数字）