《数据结构习题与解析》清华大学专业教材

清华大学 2000 年试题与分析试题部分一、请回答下列关于图的一些问题：1 ．有 n 个顶点的有向连通图最多有多少条边？最少有多少条边？2 ．表示一个有 1000 个顶点， 1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否是稀疏矩阵？3 ．对于一个有向图，不用拓扑排序，如何判断图中有否存在环？二、斐波那契数列 F n 定义如下：F 0 =0,F 1 =1, F n = F n-1 + F n-2 n=2,3, …请就此斐波那契数列，回答下列列问题：1 ．在递归计算 F n 的时候，需要对较小的 F n-1 ， F n-2 ，…， F 1 ， F 0 精确计算多少次？2 ．如果用大 O 表示法，试给出递归计算 F n 时递归函数的时间复杂度是多少？三、有一种简单的排序算法，叫做计算排序（ Count Sorting ）。

这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结构存放以另一个新的表中。

必须注意的是，表中所有待排序的关键字互不相同。

计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比刻记录的关键字小。

假设对某一个记录，统计出计数值为 C ，那么，这个记录在新的有序表中的合适的存放位置即为 C 。

1 ．给出适用于计数排序的数据表定义。

2 ．使用 Pascal 或 C 语言编写实现计数排序的算法。

3 ．对于有 n 个记录的表，关键字比较次数是多少？4 ．与简单选择排序相比，这种方法是否更好？为什么？四、在一棵表示有序集 S 的二次搜索树（ Binary Search Tree ）中，任意一条从根到叶子结点的路径将 S 分为 3 部分：在该路径左边结点中的元素组成集合 S1 ；在该路径上的结点中的元素组成集合 S2；在该路径右边结点中的元素组成集合 S3 。

S=S1 ∪ S2 ∪ S3 。

对于任意的a ∈ S1 ， b ∈S2 ， c ∈ S3 ，是否总有a ≤ b ≤ c ？为什么？五、请回答下列关于堆的一些问题：1 ．堆的存储表示是顺序的，还是链式的？2 ．设有一个最小堆，即堆中任意结点的关键字均小于它的左子女和右子女的关键字。

习题1参考答案一、单项选择题1. A2. C3. D4. B5. C、A6. C、B7. B8. D9. B 10. B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4. 时间，空间5. 前趋，一，后继，多6. 有多个7. 一对一，一对多，多对多8. O(2n)9. O(n)10. O(2n)11. O(log3n)12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。

13. 事后统计，事前估计三、算法设计题1. O(2n)2. O(2n)3. O(n3)4. O(n)5. O(n)习题2参考答案一、单项选择题1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A二、填空题1．线性2．n-i+1 3．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇14．2、3；15．O(1)三、简答题1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。

若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。

2．线性表具有两种存储结构即顺序存储结构和链接存储结构。

线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。

第1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

习题1 参考答案1至8题答案略。

9.（1）【解】该逻辑结构为线性结构，其图形表示如下：（2）【解】该逻辑结构为树型结构，其图形表示如下：（3）【解】该逻辑结构为图型结构，其图形表示如下：（4）【解】该逻辑结构为线性结构，其图形表示如下：10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType 类型。

每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。

可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。

根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。

所以，现用抽象数据类型bookList 表示问题模型，其逻辑结构与基本操作的定义如下： （1）逻辑结构bookList=( D, {r} )D={b i | b i 为bookType 类型的元素，i=1,2,3, ....., n ，n ≥0} r ={ <bk i ,b i+1>| i=1,2,…, n -1, n ≥0 } （2）基本操作 ①初始化操作函数：InitBookList(&BL)。

……初始条件：图书表BL 不存在。

操作结果：构造一个空的图书表BL 。

②求图书表长度操作函数：bookListLength(BL)。

初始条件：图书表BL 已存在。

操作结果：返回图书表BL 中所包含的数据元素（图书）的个数。

③取图书表中元素操作函数：getBook(BL, i, &b)。

初始条件：图书表BL 已存在，且1≤i ≤bookListLength(BL)。

操作结果：用b 返回图书表BL 中的第i 个数据元素的值。

④按编号查找操作函数：locateById(BL, id)。

初始条件：图书表BL 已存在，id 是给定的一个图书编号。

操作结果：返回图书表BL 中图书编号为id 的数据元素的位序，若这样的数据元素不存在，则返回0。

李春葆数据结构习题与解析（修订版）清华⼤学出版社⼀、绪论选择题1.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的 1 以及它们之间的 2 和运算等的学科。

1 A.数据元素 B.计算⽅法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为 (K, R)，其中K是 1 的有限集，R是K上的 2 有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和⾮紧凑结构C.线性结构和⾮线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是⼀种 1 的存储结构，线性表的链式存储结构是⼀种 2 的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的⽬的是 1 ，算法分析的两个主要⽅⾯是 2 。

1 A.找出数据结构的合理性 B.研究算法中的输⼊和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和⽂档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和⽂档性D.数据复杂性和程序复杂性6.计算机算法指的是 1 ，它必须具备输⼊、输出和 2 等5个特性。

1 A.计算⽅法 B.排序⽅法 C.解决问题的有限运算序列 D.调度⽅法2 A.可执⾏性、可移植性和可扩充性 B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是⼀致的，这种说法。

A.正确B.不正确8线性表若采⽤链式存储结构时，要求内存中可⽤存储单元的地址。

A.必须连续的B.部分地址必须连续的C.⼀定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.⼆维数组是其数据元素为线性表的线性表C.栈的操作⽅式是先进先出D.队列的操作⽅式是先进后出10.每种数据结构都具备三个基本运算：插⼊、删除和查找，这种说法。

数据结构（C语言版）清华大学出版社课后题1-5章答案第一章选择题1.A2.B3.C4.D5.B6.C第二章选择题1.A2.D3.D4.C5.A6.C7.B8.B9.D 10.D应用题1．应该选用链接存储表示。

如果才用顺序表示法，必须在一个连续的可用空间中为这N 个表分配空间。

初始时候因为不知道哪个表增长得快，必须平均分配空间。

在程序运行过程中，有的表占用的空间增长得快，有的表占用空间增长得慢，有的表很快就使用完了分配给它的空间，有的表才占用了少许空间，在进行元素的插入时候就必须成片的移动其他表的空间，以空出位置进行插入；在元素删除时为填补空白，也可能移动许多元素。

这个处理过程及其繁琐和低效。

如果采用链接存储，一个表的空间可以连续也可以不连续。

表的增长通过动态分配内存得以解决，只要存储器未满，就不会发生表溢出；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储需求，非常灵活方便。

对于N个表（包括表的总数可能变化）共存的情形，处理十分简单快捷，插入、删除时间复杂度为O（1）。

所以才用链接存储表示较好。

2．一般来说，链式存储结构克服了顺序存储结构的三个缺点。

首先，插入、删除操作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受到内存空间的限制。

其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

3.顺序结构时ai与ai+1的物理位置相邻，链表结构时两者的位置不要求一定相邻。

7.在顺序表中插入和删除一个节点需平均移动全表一半的节点。

具体的移动次数取决于所插入和删除的节点的位置i和全表的长度n这两个因素。

算法设计题1.分析：遍历整个顺序表，用k记录在x~y之间元素的个数，k的初始值为0。

对于当前遍历到的元素，若其值在x~y之间，则前移k个位置；否则执行++k。

这样每个不在x~y之间的元素仅仅移动一次，所以效率较高。

数据结构（C 语言描述）第2版教材后各章习题参考解答徐孝凯第1章 绪论1.1 单项选择题1. A2. D3. C4. B5. A6. B7. C8. A9. D10. B11. D1.2 是非判断题1.是2.否3.否4.是5.是6.否7.是8.否9.否10.是1.3 算法分析题指出下列各算法的功能并求出其时间复杂度。

1．判断参数n 是否为一个素数（质数），若是则返回整数1，否则返回0。

该算法的时间复杂度为O (n )。

2．计算i i n!=∑1的值。

时间复杂度为O(n )。

3．计算i i n!=∑1的值。

时间复杂度为O(n 2)。

4．求出满足不等式1+2+3+ +i ≥n 的最小i 值。

时间复杂性为O(n )。

5．打印出一个具有n 行的乘法表，第i 行（1≤i ≤n ）中有n-i+1个乘法项，每个乘法项为i 与j （i ≤j ≤n ）的乘积。

时间复杂性为O(n 2)。

6．给二维数组a[m][n]中的每一个元素赋值，每个a[i][j]的值为表达式i*i+j*j+1的值。

此算法的时间复杂性为O (m*n)。

7．矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。

时间复杂性为O (M*N*L)。

1.4 算法设计题1. 初始化一个由pq 指针参数所指向的二次多项式中的三个数据成员a 、b 和c ，每个数据成员的初始值依次为参数aa 、bb 和cc 的值。

void initQuadratic (struct Quadratic* pq, double aa, double bb, double cc) {(*pq).a=aa;(*pq).b=bb;(*pq).c=cc;}2. 做两个多项式加法，即使对应的系数相加，返回相加结果。

struct Quadratic add(struct Quadratic* pq1, struct Quadratic* pq2){struct Quadratic qq;qq.a=(*pq1).a+(*pq2).a;qq.b=(*pq1).b+(*pq2).b;qq.c=(*pq1).c+(*pq2).c;return qq;}3. 根据给定x 的值计算多项式的值并返回。