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

华北计算技术研究所2006年专业课试题

参考答案

一、 填空题（15分）

1. 数据结构是相互之间存在一种或多种特定关系的下列四种基本结构： 集合 、 线性结构 、 树状结构 和 图状结构（或网状

结构） 。

2. 在顺序表中插入或删除一个元素，需要平均移动 表中一半（或n/2个） 元素，具体移动的元素个数与表长和该元素在表中的位置有关。

3. 个字符的串称为空串，它的长度为。

4. 矩阵压缩存储的基本思想是：的多个元素只分配一个存储空间， 零元素 不分配空间。

5. 深度为k 的二叉树至多有个结点，至少有个结点。

6. 图的深度优先搜索遍历类似于树的遍历；图的广度优先搜索遍历类似于树的 按层次 遍历。

二、 选择题（20分）

1. 时间复杂性最好，即执行时间最短的是：

（A ） O(n) （B ）O(log2n) （C ）O(nlog2n) （D ）O(n2)

2. 具有6个顶点的无向图至少有

（A ） 15 （B ）7 （C ）6 （D ）5

3. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是：

（A ）希尔排序 （B ）起泡排序 （C ）插入排序 （D ）选择排序

4. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别

为： C 。

（A ） 1和5 （B ）2和4 （C ）4和2 （D ）5和1

5. 设栈的长度为3，入栈序列为A 、B 、C 、D 、E 、F ，不可能产生的出栈序列是： D 。

（A ） A ，B ，C ，D ，E ，F （B ） B ，A ，D ，C ，F ，E

（C ） C ，B ，A ，F ，E ，D （D ） D ，C ，B ，A ，F ，E