数据结构课后答案 - 北邮

习题1

1. 填空题

（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。

答案：数据结构 逻辑结构 存储结构 （2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。 答案：数据元素 （3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。

答案：集合 线形结构 树结构 图结构

（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。 答案：顺序存储结构 链式存储结构

（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。 答案：有穷性 确定性 可行性

（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算法的好坏。

答案：时间 空间

（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。

答案：1 logn n nlogn n2 2n 指数

（8）STL提供的标准容器有顺序容器、（___________）和（___________）。 答案：排序容器 哈希容器

（9）算法可认为是STL的精髓，所有算法都是采用（___________）的形式提供的。 答案：函数模版

（10）通常认为STL由空间管理器、迭代器、泛函、适配器、（___________）和（___________）等六部分构成，其中前面四部分服务于后面两部分。 答案：容器 算法

2. 选择题

（1）以下结构中，（ ）属于线性结构。 A. 树 B. 图 C. 串 D. 集合 （2）算法描述的方法有很多种，常常将（ ）称为算法语言。 A. 自然语言 B. 流程图 C. 伪代码 D. 程序设计语言 （3）现实生活中的家族谱，可认为是一种（ ）结构。

A. 树 B. 图 C. 集合 D. 线性表 （4）手机中存储的电话号码簿，可认为是一种（ ）结构。 A. 树 B. 图 C. 集合 D. 线性表 （5）NP问题是（ ）。

A. 非多项式时间问题，即非P问题 B. 非确定性多项式时间问题

C. P问题的子集 D. 与P问题不相交的 （6）以下（ ）不属于STL的顺序容器。 A. 向量（vector） B. 列表（list） C. 队列（queue） D.双端队列（deque） （7）下面带有@标记的语句的频度(n>10)是（ ）。

for(int i=0;i

for(int j=i+1;j

@cout<

A. n*(n-1)/2

B. n*n/2

n?2n?1n?2分析：??1??n?1?i?(n?1)n?0j?i?1i?02

i3. 分析以下程序段的时间复杂度。 （1）for (i=l; i<=n; i++) {

k++;

for (j=1; j<=n; j++)

m += k;

} （3）i=1;

while (i<=n)

i *= 2;

（5）k=100,i=10; do { if (i

i++;

}while (i

while (y*y*y <= n)

y++;

（8）int i=0;

while(i

C. n*(n+1)/2 D. 不确定

（2）for (i=l; i<=n; i++)

k++;

for (j=1; j<=n; j++) m += k; （4）i=1;

while (i<=n)

i += 2;

（6）for (i=0; i<100; i++) for (j=0; j

sum += j;

答案：

(1) (2) (3) (4)

O(n) O(n) O(logn) O(n)

2

(5) O(1) (6) O(1)

(7) O(n1/3) (8) O(n)

4. 将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与

给定值的最大公约数、最小公倍数、枚举所有因子等。 解：

#include \#include %using std::vector;

//定义自然数类 class NaturalNumber{ public: };

//返回欧几里德算法求解最大公约数

unsigned long int NaturalNumber :: EUCLID(NaturalNumber & nn) { }

//返回最大公约数

unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn)

unsigned long int m = (num > nn.num) ? num : nn.num; //较大的自然数赋值给m unsigned long int n = (num < nn.num) ? num : nn.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0){ }

return n;

m = n; n = r; r = m % n; //……其它外部接口

unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 NaturalNumber(unsigned long int n=0):num(n){}

unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector & factors); unsigned long int GetNumber(){return num;}

//求所有因子，存储在factors

中，函数返回因子个数

private:

{ }

//返回最小公倍数

unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { }

int NaturalNumber :: GetFactors( vector & factors ) { }

void main() { }

NaturalNumber p(1);

int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector f; int t = p.GetFactors(f); int t=0;

int m = sqrt((double)num);

vector bigfactors; for (unsigned long int i=1;i

if ( m*m == num ) { t++; factors.push_back(m);}

vector ::iterator it=bigfactors.end(); if (bigfactors.size()) do {

it--;

factors.push_back(*it);

if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);} unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; return EUCLID(nn);

}while (it!=bigfactors.begin()); return t;

习题2

1. 填空题

（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s;

（2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。 答案：n/2 (n-1)/2

（3）表长为0的线性表称为（___________）。 答案：空表

（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。 答案：申请 释放

（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组 O(1) O(n) 顺序

（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。 答案：指针 O(1) 表长的一半 O(n) 链 循环链

（7）静态链表一般采用（___________）存储的链表结构。 答案：数组 （8）对于32位计算机环境，若单链表中的数据类型为整性，则其存储密度为（___________），而若为双链表，则存储密度为（___________）。若采用顺序表存储数据，则其存储密度为（___________）。 答案：50% 33% 1

（9）向量是最常用的容器，STL中向量使用（___________）实现，因此向量具有（___________）表的所有特点，可以快速随机存取任意元素。 答案：数组 顺序

（10）操作系统在运行之初，有一块很大的连续内存块供用户程序申请，通常称之为内存池或（___________）。

答案：堆

（11）循环链表与单链表的区别仅仅在于其尾结点的链域值不是（___________），而是一个指向（___________）的指针。 答案：NULL(或空指针) 头结点 2. 选择题

（1）线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式存储结构是一种（ ）的存储结构。 A. 随机存取 索引存取 C. 随机存取 顺序存取

B. 顺序存取 随机存取 D. 索引存取 散列存取

（2）在双向链表p所指结点之前插入s所指结点的操作是（ ）。 A. p->left=s; s->right=p; p->left->right =s; s->left=p->left; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;

3 5 6 矩阵行数：7 矩阵列数：6 4 2 3 13 5 14 非零元素个数：8

（2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。 ?0??3 原矩阵 ?0??0?000020?100??0? 5??0??

Row 0 1 2 2 行数：4 Col 2 0 2 3 Item 2 3 -1 5 Col Number[col] Position[col] 0 1 0 1 0 1 2 2 1 3 1 3 列数：4 非零元素个数：4

（3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。

三元组表： Row 0 1 Col 2 0 Item 2 3 2 2 行数：4 列数：4 2 3 -1 5 非零元素个数：4

十字链表：

441001221301022111032222-123530

3. 算法设计

（1）设计上三角矩阵存储类，实现如下接口：

① 对于上三角矩阵A[N][N]，可按行优先压缩存储和按列优先压缩存储。

② 对于给定的一维数组B[M]，可根据行优先压缩存储或列优先压缩存储还原原始的上三角矩阵。

（2）针对24位真彩色BMP图像文件，编写程序实现如下功能： ① 读取24位真彩色BMP图像文件。

② 将原图像转换为24位灰度图像，并进行保存。转按公式如下： Grey=0.3*Red+0.59*Blue+0.11*Green

③ 将24位灰度图像转换为8位灰度图像，并进行保存。

④ 将8位灰度图像分别进行4－邻域和8－邻域平滑，并分别进行保存。

习题5

1. 填空题

（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。 答案：129

（2）3个结点可构成（___________）棵不同形态的二叉树。 答案：5 （3） 设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）

个叶子。

答案：31

（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。 答案：2 n-1 1 n 1 n-1

（5）深度为k的二叉树，至多有（___________）个结点。

答案：2-1 （6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。 答案：2n-1

（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。

答案：2-1 k+1 （9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为（）。 答案：24

（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。 答案：384 （11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。 答案：68

（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。

答案：128

（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。 答案：ABCDEF

（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。 答案：EACBDGF 2

2. 选择题

（1）在一棵度为3的树中，度为3的结点的个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。 A. 4 B. 5 （2）下列陈述中正确的是（ ）。 A. 二叉树是度为2的有序数

B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点

D. 二叉树中最多只有两棵子树，并且有左右之分 （3）在K叉树中，如果结点M有3个兄弟，而且N是M的双亲，则N的度是（ ） A. 3 B. 4 C. 5 D. 1

（4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。 A. 2h B. 2h－1 C. 2h+1 （5）高度为5的完全二叉树至少有（ ）个结点。

D. h+1

C. 6

D. 7

k+1k

A. 16 B. 32 C. 31 D. 5 （6）具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0） A. 8 B. 7 C.6 D. 5 （7）对一个满二叉树，m个树叶，n个结点，深度为h，则（ 无 ）。 A. n=h+m

B. h+m=2n

C. m=h-1 D. n=2h-1

（8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。 A. n2 +1=n0 B. n0 +1=n2 C. 2n2 +1=n0 D. n2 =2n0 +1

（9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca （10）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A. n在m右方 B. n是m祖先 C. n在m左方 D.n是m子孙 （11）一棵二叉树的广义表表示为a（b（c，d），e（f（g））），则得到的层序遍历序列为（ ）。

A. abcdefg B. cbdaegf C. cdbgfea D. abecdfg

（12）若二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。 A. 前序 B. 中序

C. 后序

D. 层序

说明：显然，如果按前序或后序遍历，当访问某结点时，交换其左右孩子，则可完成要求。进行层序遍历时，当结点出队时，交换左右孩子，也可以完成题目要求。因此该题有3个答案，谈不上哪个最合适。建议该题目将“最合适”改为“不合适”，这样答案应该是唯一的。 （13）对二叉树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。 A. 前序 B. 中序 C. 后序 D. 层序

（14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。

A. n-1 B. n C. n+1 D. n+2

（15）利用3，6，8，12，5，7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。

A.3 B. 4 C.5 D. 6

（16）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。 A. n-1 B. [n/m]-1 C. [(n-1)/(m-1)] D. [n/(m-1)]-1

说明：在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树。因此有： (1) Ｎ＝n+nm

(2) N = 1 + mnm

3. 试分别画出具有3个结点的树和二叉树的所有不同形态。 答案：树：

二叉树：

4． 试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； 答案: 右斜树

（2）中序序列和后序序列相同； 答案：左斜树

（3）前序序列和后序序列相同。 答案：只有根结点的树

5．一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从0开始对全部结点进行编号，试问：

（1）各层的结点个数是多少？

答案：n层的结点个数为kn-1

（2）编号为i的结点的父结点（若存在）的编号是多少？ 答案：|(i-1)/k| (|·|表示取下整)

（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？ 答案：k*i+m

（4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 答案：i%k!=0 i+1

（5）叶子结点数n0和非叶子结点数nk之间满足的关系。 答案：nk*(k-1)=n0-1

6．若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。 答案：gdbehfca

本文来源：https://www.bwwdw.com/article/64qt.html