当前位置：问答库＞考研试题

一、填空题

1．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

2． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4; 2

3． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。 4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

5． 设数组储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

6． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）

第 2 页，共 52 页

的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

而快速排序算法需要比较的次数达到最大，时间复杂度为

7．

=_____

【答案】5

8． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15

【解析】当时，而，时，

9． 索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

10．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

要使前者快于后者，n 至少为

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

二、算法设计题

11．设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred （前驱指针），data （数据）和next （后继指针）域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate （L ，x ）运算时，令元素值为x 的结点中freq 域的值増1, 并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate （L , x ）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

【答案】算法如下：

第 3 页，共 52 页

12．请运用快速排序思想，设计递归算法实现求n （n>l）个不同元素集合中的第

【答案】算法如下：

13．叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179，208，93，306，55，859，984，9，271，33）

【答案】算法如下：

第 4 页，共 52 页

小元素。