山东大学网络教育《数据结构》( A 卷)

《数据结构》模拟卷

一、选择题

1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。

A. O(n)

B. O(n/2)

C. O(1)

D. O(n2)

2.带头结点的单链表first为空的判定条件是：（ B ）。

A. first == NULL;

B. first->link == NULL;

C. first->link == first;

D. first != NULL;

3. 从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构

4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为

对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ），在被调用程序中可直接操纵实际参数。

A. 空间

B. 副本

C. 返回地址

D. 地址

5. 以下数据结构中，哪一个是线性结构（ D ）。

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

6. 以下属于逻辑结构的是（ C ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表

7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长

度为（ C ）的值除以9。

A. 20

B. 18

C. 25

D. 22

8.在有向图中每个顶点的度等于该顶点的（ C ）。

A. 入度

B. 出度

C. 入度与出度之和

D. 入度与出度之差

9.在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于

O(nlog2n)。

A. 起泡排序

B. 希尔排序

C. 归并排序

D. 快速排序

10.当α的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。

1

A. 较慢

B. 较快

C. 相同

D.不同

二、填空题

1.二维数组是一种非线性结构，其中的每一个数组元素最多有___2___个直接前驱（或直

接后继）。

2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，

A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_「(K+1)／3」_行的元素。

3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针__域的值。

4.在一个链式栈中，若栈顶指针等于NULL则为__空栈__。

5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，

它们都需要利用栈保存调用后的__返回___地址。

6.在一棵树中，_叶子_结点没有后继结点。

7.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f

的层数为__3__。假定根结点的层数为0。

8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差

的绝对值不超过__1____。

9.n (n﹥0) 个顶点的无向图最多有_n（n-1）/2__条边，最少有___0___条边。

10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_

稠密_索引，若对应数据对象表中的若干个表项，则称此索引为__稀疏__索引。

三、判断题

1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对)

2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间

的逻辑顺序(错)

3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对)

4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高(错)

5.一个广义表的表尾总是一个广义表(对)

6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后

再按条件把它逐层向下调整，直到调整到合适位置为止(对)

7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为

O(h) (错)

2

8.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有

关(错)

9.直接选择排序是一种稳定的排序方法(错)

10.闭散列法通常比开散列法时间效率更高(错)

四、运算题

1.设有一个10 10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]

存放于B[0]中，那么A[8][5]存放于B中什么位置。

解：根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B 中的存放位置为I * (I + 1) / 2 + J，因此，A[8][5]在数组B中位置为

8 * (8 + 1) / 2 + 5 = 41。

2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，

请重新编写出正确的while循环。

int count ( ListNode * Ha, ElemType x )

{ // Ha为不带头结点的单链表的头指针

int n = 0;

while ( Ha->link != NULL ) {

Ha = Ha->link;

if ( Ha->data == x ) n++;

}

return n;

}

解：while ( Ha != NULL ) {

if ( Ha->data == x ) n++;

Ha = Ha->link;

}

3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

3

4

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列：

解：后序序列：C, B, F, E, I, J, H, G, D, A

4. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于

一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

元素值

比较次数

4. 解：元素值 比较次数

5. 设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July,

Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = ?i / 2?，其中，i 是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。 (1) 试画出相应的散列表；

(2) 计算等概率下搜索成功的平均搜索长度； 解： H(Jan) = ?10/2? = 5，成功.

H(Feb) = ?6/2? = 3，成功.

H(Mar) = ?13/2? = 6，成功.

H(Apr) = ?1/2? = 0，成功.

H(May) = ?13/2? = 6，= 7，成功， H(June) = ?10/2? = 5，= 6，= 7，=8，成功. H(July) = ?10/2? = 5，= 6，= 7，= 8，= 9，成功.

34 56 58 63 94 34 56 58 63 94

02 1 3 4 4

H(Aug) = ?1/2? = 0，= 1，成功. H(Sep) = ?19/2? = 9，= 10，成功.

H(Oct) = ?15/2? = 7，= 8，= 9，= 10，= 11，成功.

H(Nov) = ?14/2? = 7，= 8，= 9，= 10，= 11，= 12，成功.

H(Dec) = ?4/2? = 2，成功.

(1)相应的散列表

0 1 2 3 4 5 6 7 8 9 10 11 12 13

(1) (2) (1) (1) (1) (1) (2) (4) (5) (2) (5) (6)

(2) 搜索成功的平均搜索长度为

1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12

五、算法设计题

已知二叉树中的结点类型用BinTreeNode表示，被定义为:

struct BTreeNode …… 此处隐藏：2166字，全部文档内容请下载后查看。喜欢就下载吧 ……