数据结构是计算机专业的一门核心专业基础课程，在整个专业教学中占有十分重要的地 位。主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的 方法、存储数据结构的方法以及在各种存储数据结构上执行操作的算法。

1.对比顺序表和单链表

1)顺序表的存储密度大，单链表的存储密度低。

2)顺序表是预分配存储空间，单链表是按需分配存储空间。

3)顺序表支持随机读取，单链表不支持随机读取。

2.简述算法的特点。

1)有穷性:能在有限步后和有限时间内执行结束。

2)确定性:对于相同的输入执行相同路径，每条指令理解起来不会产生二义性。

3)可行性:每条指令所表示的操作可由已实现操作的有限次运算来完成。

3.简述串的存储方式。

串的存储表示分为两大类:顺序存储表示和链式存储表示。其中顺序存储表示又包括两种:定长顺序存储表示和堆分配存储表示。定长顺序存储表示用固定长度的数组来存储每一个串。堆分配存储表示也是用一组地址连续的存储单元来依次存放串值的字符序列。

4.简述逻辑结构和存储结构。

逻辑结构与数据的存储无关，是独立于计算机的，逻辑上可以把数据结构分成线性结构和非线性结构，线性结构主要包括线性表、栈、队列和串，非线性结构主要包括树和图。数据结构在计算机中的表示称为数据的存储结构或物理结构，包括数据元素的表示和关系的表示。

5.什么是队列的“假溢出”，如何解决?

假溢出指的是用固定大小的数组实现队列时，头尾指针只增加不减小，导致被删除元素的空间无法重新利用，当尾指针达到数组未尾时，即使头部有空闲空间，也无法再进行入队操作。可以使用循环队列解决“假溢出”。

6.算法效率的度量有哪方面?

算法效率的度量是通过时间复杂度和空间复杂度来描述的。评估一个算法的时间开销有两种方法，分别是事后统计法和事前分析估算法，通常人们采用事前分析估算法。

7.简述堆排序的过程。

1)一个大顶堆。

2)把堆顶记录与堆中最后一个记录交换。

3)将剩下的记录调整为新的大顶堆。

4)重复步骤(2)(3)，直到堆中只剩一个记录为止。

8.什么是“同义词”?什么是“哈希冲突”?

若不同的关键字通过散列函数映射到同一个哈希地址，则称它们为“同义词”，通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

9.构造哈希函数的常见方法有哪些?

1)直接地址法

2)数字分析法

3)平方取中法

4)折叠法

5)除留余数法

6)随机数法

10.简述装填因子。

装填因子的作用是为了描述表的填满程度，装填因子等于表中填入的记录数和哈希表长度的比值。装填因子越大，哈希表的存储效率越高，另一方面，装填因子越大，产生冲突的可能性越大，查找效率就越低。

11.影响哈希冲突次数的主要因素有哪些?

1)采用的哈希函数。

2)采用的处理冲突的方法。

3)哈希表的填满程度。