数据结构试题试卷

南京工业大学 数据结构 试题（B）卷（闭）

2005--2006 学年第 二 学期 使用班级 地信0401-02 班级 学号 姓名

题号 得分 一 二 三 四 五 总分 一、选择题（15×2’＝30’）

1. 算法的计算量的大小称为计算的 。 A． 效率 B． 复杂性 C． 现实性 D． 难度

2. 从逻辑上可以把数据结构分为 两大类。 A． 动态结构、静态结构 B． 顺序结构、链式结构 C． 线性结构、非线性结构 D． 初等结构、构造型结构

3. 以下数据结构中， 是非线性数据结构。 A． 树 B． 线性表 C． 队 D． 栈

4. 下面说法错误的是 。

(1) 算法原地工作的含义是指不需要任何额外的辅助空间

(2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3) 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 (4) 同一个算法，实现语言的级别越高，执行效率就越低 A． （1） B． （1）（2） C． （3） D． （1）（4）

5. 下述哪一条是顺序存储结构的优点？ A． 存储密度大 B． 插入运算方便 C． 删除运算方便 D． 可方便地用于各种逻辑结构的存储表示

6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 最节省时间。 A． 单链表 B． 单循环链表 C． 带尾指针的单循环链表 D． 带头结点的双循环链表

7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂

度为 (1<=i<=n+1)。 。 A． O(0) B． O(1) C． O(n) D． O(n2)

南京工业大学 第 1 页 共 3 页

8. 下面关于串的的叙述中，哪一个是不正确的？ 。 A． 串是字符的有限序列 B． 空串是由空格构成的串 C． 模式匹配是串的一种重要运算 D． 串既可以采用顺序存储，也可以采用链式存储

9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数

组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为 A． BA+141 B． BA+180 C． BA+222 D． BA+225

10. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数

为 。 A． 二叉树的度为2 B． 一棵二叉树的度可以小于2 C． 二叉树中至少有一个结点的度为2 D． 二叉树中任何一个结点的度都为2

11. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 。 A． 9 B． 11 C． 15 D． 条件不足，无法

12. ．一棵完全二叉树上有1001个结点，其中叶子结点的个数是 A． 250 B． 500 C． 254 D． 以上都不对

13. 一个n个顶点的连通无向图，其边的个数至少为 。 A． n-1 B． n C． n+1 D． nlogn

14. 下列哪一种图的邻接矩阵是对称矩阵？ 。 A． 有向图 B． 无向图 C． AOV网 D． AOE网

15. 如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称

该排序算法是不稳定的。 就是不稳定的排序方法。 A． 起泡排序 B． 归并排序 C． 直接插入排序 D． 简单选择排序

二、填空题（10×2’＝20’）

1． 抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内部结构如

何变化，只要它的_（3）_不变，都不影响其外部使用。

2． 栈是____（4）___的线性表，其运算遵循___（5）____的原则。

3． 高度为8的完全二叉树至少有___（6）___个叶子结点。

南京工业大学 第 2 页 共 3 页

4． 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的

___（7）___；对于有向图来说等于该顶点的___（8）___。

5． 文件可按其记录的类型不同而分成两类，即___（9）___和__（10）____文件。

三、简答题（4×6’＝24’）

1． 描述以下3个概念的区别：头指针、头结点、首元结点。

2． 什么是队列的假溢现象？如何来解决这种现象？

3． 用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序

列。

4． 对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其

中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？

四、下面的邻接表表示一个给定的无向图（16’）

1．给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；(8’) 2．给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。(8’)

五、编程理解题（10’）

用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。 selectsort(head) p=head;

while (p （1） ) {q=p; r= (2)_______ while( (3)______ ) {if ( (4)_______ ) q=r; r= (5)_______ ; }

tmp=q->data; q->data=p->data; p->data=tmp;

p= (6)_______ ; 南京工业大学 第 3 页 共 3 页