数据结构习题解析第

严蔚敏数据结构课后习题及答案解析

数据结构是计算机科学中的重要基础课程，严蔚敏老师的《数据结构》教材更是被广泛使用。对于学习者来说，课后习题的练习和答案解析对于巩固知识、加深理解至关重要。下面我们就来详细探讨一些严蔚敏《数据结构》课后的典型习题及其答案解析。

首先，让我们来看一道关于线性表的习题。

习题：已知一个线性表（38，25，74，63，52，48），假定采用散列函数 H(Key) ＝ Key mod 7 计算散列地址，并散列存储在散列表 A06中，采用线性探测法解决冲突。试求出在等概率情况下查找成功的平均查找长度。

答案解析：首先计算每个元素的散列地址：

38 mod 7 ＝ 3

25 mod 7 ＝ 4

74 mod 7 ＝ 4 （冲突，线性探测到 A5）

63 mod 7 ＝ 0

52 mod 7 ＝ 3 （冲突，线性探测到 A4）

48 mod 7 ＝ 6 查找成功时，38 比较 1 次，25 比较 1 次，74 比较 2 次，63 比较 1

次，52 比较 2 次，48 比较 1 次。

平均查找长度 ＝ （1 ＋ 1 ＋ 2 ＋ 1 ＋ 2 ＋ 1）／ 6 ＝ 7 ／ 6

接下来，看一道关于栈的习题。

习题：若进栈序列为 1，2，3，4，进栈过程中可以出栈，则可能得到的出栈序列有哪些？

答案解析：出栈序列可能有多种情况。比如：

1、 1 进 1 出，2 进 2 出，3 进 3 出，4 进 4 出，得到序列 1 2 3 4 。

2、 1 进 1 出，2 进 3 进 3 出，2 出，4 进 4 出，得到序列 1 3 2 4 。

3、 1 进 1 出，2 进 2 出，3 进 4 进 4 出，3 出，得到序列 1 2 4 3 。

4、 1 进 2 进 2 出 1 出 3 进 3 出 4 进 4 出，得到序列 2 1 3 4 。

5、 1 进 2 进 2 出 3 进 3 出 1 出 4 进 4 出，得到序列 2 3 1 4 。

WORD格式 可编辑

专业知识 整理分享 第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素

⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素

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

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

【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系

⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。

【解答】问题规模

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

【解答】Ο(1)，Ο(nlog2n)

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

2. 选择题

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

A 线性结构 B 非线性结构 C 存储位置 D 指针

【解答】C，D

【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 WORD格式 可编辑

一、基础知识题

6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】 设度为m的树中度为0,1,2,„,m的结点数分别为n0, n1, n2,„, nm，结点总数为n，分枝数为B，则下面二式成立

n= n0+n1+n2+„+nm (1)

n=B+1= n1+2n2 +„+mnm+1 (2)

由(1)和(2)得叶子结点数n0=1+

即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8

6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则

n= n0+ n1+ n2

n=2n0+n1-1

1002=2n0+n1

由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.

注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，„„。虽然解法也对，但步骤多且复杂，极易出错。

6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。

【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。

6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。 【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。

李春葆数据结构习题与解析（修订版）

清华⼤学出版社

⼀、绪论

选择题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.每种数据结构都具备三个基本运算：插⼊、删除和查找，这种说法。