开放定址法

(1)【◆题库问题◆】：[名词解释] 开放定址法

【◆参考答案◆】：
指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

(2)【◆题库问题◆】：[填空题] 已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。栈的ADT函数有：voidmakeEmpty（SqStacks）；置空栈voidpush（SqStacks，ElemTypee）；元素e入栈ElemTypepop（SqStacks）；出栈，返回栈顶元素intisEmpty（SqStacks）；判断栈空队列的ADT函数有：voidenQueue（Queueq，ElemTypee）；元素e入队ElemTypedeQueue（Queueq）；出队，返回队头元素intisEmpty（Queueq）；判断队空

【◆参考答案◆】：void QueueInvent(Queue q){ElemType x; makeEmpty(SqStack s);while(!isEmpty(Queue q)){x=deQueue(Queue q);push(SqStack s, ElemTypex);}while(!isEmpty(SqStack s)){x=pop(SqStack s); enQueue(Queue q, ElemType x);}}

(3)【◆题库问题◆】：[单选] 具有线性结构的数据结构是（）。
A．图
B．树
C．广义表
D．栈

【◆参考答案◆】：D

(4)【◆题库问题◆】：[单选] 若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
A．顺序表
B．单链表
C．双链表
D．单循环链表

【◆参考答案◆】：A

(5)【◆题库问题◆】：[判断题] 对任何数据结构链式存储结构一定优于顺序存储结构
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[判断题] 线性表中每个元素都有一个直接前驱和一个直接后继
A．正确
B．错误

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[判断题] 若让元素1，2，3依次进栈，则出栈次序1，3，2是不可能出现的情况。
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[单选] 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A．希尔排序
B．冒泡排序
C．插入排序
D．选择排序

【◆参考答案◆】：C

(9)【◆题库问题◆】：[单选] 每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。
A．堆排序
B．归并排序
C．插入排序
D．快速排序

【◆参考答案◆】：D

(10)【◆题库问题◆】：[填空题] 如果n个顶点的图是一个环，则它有（）棵生成树。（以任意一顶点为起点，得到n-1条边）

【◆参考答案◆】：n