用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25

(1)【◆题库问题◆】：[单选] 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25，84，21，47，15，27，68，35，20⑵20，15，21，25，47，27，68，35，84⑶15，20，21，25，35，27，47，68，84⑷15，20，21，25，27，35，47，68，84则所采用的排序方法是（）。
A．选择排序
B．希尔排序
C．归并排序
D．快速排序

【◆参考答案◆】：D

(2)【◆题库问题◆】：[判断题] 在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。
A．正确
B．错误

【◆参考答案◆】：正确

(3)【◆题库问题◆】：[判断题] 链表的物理存储结构具有同链表一样的顺序。
A．正确
B．错误

【◆参考答案◆】：正确

【◆答案解析◆】：链表的存储结构特点是无序，而链表的示意图有序。

(4)【◆题库问题◆】：[单选] 若邻接表中的有奇数个表结点，则一定（）
A．图中有奇数个顶点
B．图中有偶数个顶点
C．图为无向图
D．图为有向图

【◆参考答案◆】：D

(5)【◆题库问题◆】：[问答题,简答题] 说明线性表、栈与队的异同点。

【◆参考答案◆】：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

(6)【◆题库问题◆】：[名词解释] 子串

【◆参考答案◆】：
串中任意个连续的字符组成的子序列称作该串的子串。

(7)【◆题库问题◆】：[单选] 在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（）
A．O（1）
B．O（log2n）
C．O（n2）
D．O（nlog2n）

【◆参考答案◆】：D

(8)【◆题库问题◆】：[判断题] 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[名词解释] 基数排序

【◆参考答案◆】：
采用多关键字排序思想，借助"分配/收集"两种操作对但逻辑关键字进行排序。

(10)【◆题库问题◆】：[填空题] 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为（）；末尾元素A57的第一个字节地址为（）；若按行存储时，元素A14的第一个字节地址为（）；若按列存储时，元素A47的第一个字节地址为（）。

【◆参考答案◆】：288B1282 (8+4)×6+1000=1072(6×7＋4)×6＋1000）＝1276