数据结构专升本模拟题及参考答案

算法的易懂性和文档性

5. 下面程序段的时间复杂性的量极为（ ）。 Int fun(int n) { int i=1,s=1; While(s

C．O(n) D．O( ) 6. 线性表是（ ）。

A．一个有限序列，可以为空 B．一个有限序列，不能为空

C．一个无限序列，可以为空 D．一个无限序列，不能为空

7. 带头结点的单链表L为空的判定条件是（ ）。

A．L= =NULL B．L-〉next= =NULL

C．L-〉next= =L D．L! =NULL

8. 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。

．

O(n/2)

A．（n+1）/2 B．n/2 C．n D．n+1 9. 一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ ）。

A．98 B．100 C．102 D．106 10. 如果某链表中最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。

A．单链表 B．双向链表

C．单循环链表 D．顺序表

二、填空题

1. 高度为2的二叉树的结点数至少有________个，高度为3的二叉树的结点数至少有________个。 2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找关键字值20，需做的关键字比较次数为________。

3.在有n个顶点的无向图中，每个顶点的度最大可达________。

4．已知广义表A=（（a，b，c），（d，e，f）），则广义表运算head（tail（tail（A）））= 。

5、数组（Array）是n（n≥1）个 的有序组合，数组中的数据是按顺序存储在一块 的存储单元中。

6. 采用顺序存储结构表示三元组表（Triple Table），来实现对稀疏矩阵的一种压缩存储形式，就称为 ，简称 表。

7. 运算是矩阵运算中最基本的一项，它是将一个m x n的矩阵变成另外一个n x m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题

1、对于下图所示的二叉树，画出二叉链表存储结构图。

2、请画出下图所示的树所对应的二叉树。

3. 已知一个无向图如下图所示，要求分别用Prim和

B A C D E

Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。

4. 已知完全二叉树的第8层有8个结点，则其叶子结点是多少？

5. 画出如图所示中树的二叉树的表示形式。

作业题（四）

一、单项选择题

1. 将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（ ）。 A

．

n