数据结构习题解析与实验指导

普通高等院校十四五应用型人才培养系列教材

“”

数据结构习题解析与实验指导

周瑞英张颖章昊主编

◎

内容简介

本书是数据结构语言版张颖等主编中国铁道出版社有限公司出版的配套教

《(C)》(,)

材主要包括习题解析与实验指导两篇其中习题解析篇选取了近年数据结构的考研真题

,,10

和对应主教材的章节习题实验指导篇则是针对重要知识点设置上机实验题目及其解析主要

;,

包括语言预备知识结构体指针函数算法效率分析与对比基于顺序表单链表的学生

C(、、)、、/

成绩管理基于循环链表的约瑟夫环问题基于栈的后缀算术表达式求值基于链队列的舞伴

、、、

配对问题以及树图排序算法等内容本书内容丰富讲解深入浅出引导读者系统地掌握

,、、。,,

数据结构的基础知识精选的习题具有典型性帮助读者举一反三开拓解题思路最后通过上

;,,;

机实验及其解析提升编程的思维方法和能力

,、。

本书适合作为普通高等院校数据结构课程的上机实验指导教材也可作为编程爱好者

“”,

的自学用书

。

图书在版编目CIP数据

()

数据结构习题解析与实验指导周瑞英张颖章昊

/,,

主编北京中国铁道出版社有限公司

.—:,2022.4

普通高等院校十四五应用型人才培养系列教材

“”

ISBN978-7-113-28948-5

数周张章数据

Ⅰ.①…Ⅱ.①…②…③…Ⅲ.①

结构高等学校教学参考资料

--Ⅳ.①TP311.12

中国版本图书馆数据核字第号

CIP(2022)039839

书名:数据结构习题解析与实验指导

作者:周瑞英张颖章昊

策划:魏娜编辑部电话:

(010)63549508

责任编辑:陆慧萍徐盼欣

封面设计:刘颖

责任校对:孙玫

责任印制:樊启鹏

出版发行:中国铁道出版社有限公司北京市西城区右安门西街号

(100054,8)

印刷:三河市国英印务有限公司

版次:年月第版年月第次印刷

202241202241

开本:印张:字数:千

787mm×1092mm1/1617.25429

书号:

ISBN978-7-113-28948-5

定价:元

46.00

版权所有侵权必究

凡购买铁道版图书如有印制质量问题请与本社读者服务部联系调换电话

,,。:(010)51873174

打击盗版举报电话

:(010)63549461

数据结构是计算机科学与技术及相关专业的核心基础课程是一门理论与实践并

“”,

重的课程该课程理论性较强原理和算法比较抽象对于具有程序设计基础的学生来

。,,

说做习题尤其做算法设计题时往往困难重重有时甚至无从下手这在编者多年的教学

,,,

中感受颇深本书的编写宗旨是力图通过大量的典型习题解析和实验指导帮助学生快

。,

速掌握并灵活运用数据结构的基本理论和算法辅助教师讲授课程和指导学生实践

,。

本书既是数据结构语言版的配套教材同时又自成体系可作为参加自学考

《(C)》,,

试研究生入学考试计算机国家等级考试的复习参考书

、、。

本书根据数据结构课程的实际教学情况在长期的教学实践中整理和设计了大量

“”,

的习题和实验本书由两篇组成第篇是习题解析全面覆盖了数据结构知识体系的

。,1,

各知识点共分章每章按照两个模块编写习题答案及解析第篇是实验指导包

,9,:、;2,

含个实验题目每个实验按照实验目的实验要求实验分析代码实现实验结果编

22,、、、、

写代码实现全部采用语言另外根据多年的教学经验鉴于学生普遍缺少动态数组

,C。,,

等知识故特别增加了语言预备知识实验

,C。

习题答案及解析和实验代码实现只供学习者作为参考切不可完全依赖于它如果

,。

在未做习题之前就先看答案那就与编者的初衷背道而驰了为此编者特将答案及解

,。,

析与题目相分离希望学习者在深入思考后再查看答案解析另外各实验题目的算法

,。,

实现有多种本书提供的实验代码实现并不一定是唯一的学习者可以针对实验要求多

,。

加思考设计出不同的程序并加以比较和分析

,,。

本书得到全国高等院校计算机基础教育研究会课题新工科背景下的应用型本科计

“

算机专业课程体系建设河北省教育厅第二批河北省新工科研究与

”(2020-AFCEC-396)、

实践项目应用型本科计算机专业通专融合课程体系构建河北省省

“”(2020GJXGK057)、

属高校基本科研业务费项目后疫情时代双线混合教学中高校教师教学胜任力提升策略

“

研究华北理工大学轻工学院年校级教育教学改革研究与实践项目

”(JSQ2021011)、2020

探索基于的混合教学模式之路计算机科学与技术专业课程的教改实践

“OBE———”

项目的资助

(qgjg202010)。

尽管编者在写作过程中非常认真和努力但由于编者水平有限书中难免存在疏漏

,,

和不足之处恳请广大读者批评指正

,。

编者

年月

202111

第1篇习题解析………………………1

第1章数据结构概述…………

2

习题………………

1.12

答案及解析………

1.28

第2章线性表…………………

14

习题………………

2.114

答案及解析……………………

2.222

第3章栈和队列………………

43

习题………………

3.143

答案及解析……………………

3.249

第4章串………………………

61

习题………………

4.161

答案及解析……………………

4.263

第5章数组和广义表…………

68

习题………………

5.168

答案及解析……………………

5.271

第6章树和二叉树……………

75

习题………………

6.175

答案及解析……………………

6.282

第7章图………………………

98

习题………………

7.198

答案及解析……………………

7.2107

第8章查找……………………

120

习题……………

8.1120

答案及解析……………………

8.2124

第9章排序……………………

131

习题……………

9.1131

答案及解析……………………

9.2134

Ⅰ

数据结构习题解析与实验指导

第2篇实验指导………………………141

实验语言预备知识………

0C142

实验亿级累加和问题………

1153

实验数组循环移位问题……………………

2155

实验基于顺序表的学生成绩管理………

3160

实验基于顺序表的学生信息管理………

4169

实验顺序表的合并…………

5178

实验创建单链表……………

6182

实验基于单链表的学生成绩管理………

7187

实验循环链表的合并………

8196

实验基于循环链表的约瑟夫环问题……

9200

实验单链表倒序查找……………………

10204

实验单链表原地逆置……………………

11210

实验栈的应用：进制转换………………

12214

实验栈的应用：表达式求值……………

13219

实验基于链队列的舞伴配对问题………

14227

实验基于循环队列的就医管理…………

15233

实验串应用：恺撒密码…………………

16240

实验模式匹配算法……………………

17BF242

实验二叉树遍历…………

18245

实验哈夫曼编码与译码…………………

19250

实验基于算法的最短路径求解………………

20Dijkstra256

实验二叉排序树算法……………………

21262

实验哈希函数的构造……………………

22268

Ⅱ

数据结构的基本概念和相关术语

೫

重点数据的逻辑结构、存储结构以及两者之间的关系

೫

算法基本概念、算法时间复杂度分析和空间复杂度分析

೫

抽象数据类型的定义和使用

难点೫

算法的时间复杂度分析和空间复杂度分析

೫

1.1习题

一、单选题

算法是

1.()。

计算机程序解决问题的计算方法

A.B.

排序算法解决问题的有限运算序列

C.D.

算法分析的两个主要方面是

2.()。

空间复杂度和时间复杂度正确性和简单性

A.B.

可读性和文档性数据复杂性和程序复杂性

C.D.

数据在计算机存储器内表示时物理地址与逻辑地址不相同的称为

3.,,()。

存储结构逻辑结构

A.B.

链式存储结构顺序存储结构

C.D.

数据在计算机内有链式和顺序两种存储方式在存储空间使用的灵活性上链式存储比顺

4.,,

序存储要

()。

低高相同不确定

A.B.C.D.

顺序存储结构中数据元素之间的逻辑关系是由表示的

5.()。

线性结构非线性结构

A.B.

存储位置指针

C.D.

2

第1章数据结构概述

根据数据元素之间关系的不同特性以下解释错误的是

6.,()。

集合中任何两个结点之间都有逻辑关系但组织形式松散

A.,

线性结构中结点形成对的关系

B.11

树状结构具有分支层次特性其形态有点像自然界中的树

C.、,

图状结构中的各个结点按逻辑关系互相缠绕任何两个结点都可以邻接

D.,

关于逻辑结构以下说法错误的是

7.,()。

逻辑结构是独立于计算机的

A.

运算的定义与逻辑结构无关

B.

同一逻辑结构可以采用不同的存储结构

C.

一些表面上很不相同的数据可以有相同的逻辑结构

D.

逻辑结构是数据组织的某种本质性的东西

E.“”

有以下程序段

8.:

for(i=n-1;i>=0;i--)

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

if(A[j]>A[j+1])

A[j]与A[j+1]对换;

其中n为正整数则最后一行的语句频度在最坏情况下是

,()。

O(n)O(n2)O(n3)O(nn)

A.B.C.D.log2

下面程序片段的算法时间复杂度是

9.()。

intsum1(intn)

{inti,p=1,s=0;

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

{p*=i;

s+=p;

}

returns;

}

O(n)O(n)OnO(n)

A.2B.C.()D.log2

下面程序片段的算法时间复杂度是

10.()。

intsum2(intn)

{intp,s=0;

inti,j;

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

{p=1;

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

p*=j;

s+=p;

}

returns;

}

3

数据结构习题解析与实验指导

n

O(n2)O()OnO(n)

A.B.2C.()D.log2

下面程序片段的算法时间复杂度是

11.()。

intfun(intn)

{inti=1,s=1;

while(s<n)

s+=++i;

returni;

}

O(n2)O(n)OnO(n)

A.B.C.()D.log2

从逻辑上可以把数据结构分为两大类

12.()。

动态结构静态结构顺序结构链式结构

A.、B.、

线性结构非线性结构初等结构构造型结构

C.、D.、

线性结构的顺序存储结构是一种的存储结构线性结构的链式存储是一种的存

13.(①),(②)

储结构

。

随机存取顺序存取索引存取散列存取

A.B.C.D.

算法的时间复杂度取决于

14.()。

问题的规模待处理数据的初态

A.B.

和机器的运行速度

C.ABD.

下面程序的时间复杂度为

15.()。

for(i=0;i<m;i++)

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

A[i][j]=i*j;

O(m2)O(n2)O(mn)(mn)

A.B.C.×D.+

在下面的程序段中对的赋值语句的频度为

16.,x()。

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

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

n

O()OnO(n2)O(n)

A.2B.()C.D.log2

采用顺序存储结构表示数据时相邻的数据元素的存储地址

17.,()。

一定连续一定不连续

A.B.

不一定连续部分连续部分不连续

C.D.,

与数据元素本身的形式内容相对位置个数无关的是数据的

18.、、、()。

存储结构存储实现逻辑结构运算实现

A.B.C.D.

以下数据结构中是非线性数据结构

19.,()。

树字符串队列栈

A.B.C.D.

某算法的语句执行频度为(nnnn2)其时间复杂度表示

20.3+log2++8,()。

O(n)O(n)On2O(n)

A.B.log2C.()D.log2

以下程序段中语句的语句频度为

21.“n++;”()。

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

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

4

第1章数据结构概述

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

x++;

nnnnnn

(+1)(2+1)(+1)(+1)

A.B.

22

nnnnnn

(+1)(2+1)(+1)(+2)

C.D.

66

以下程序段中语句的语句频度为

22.“m++;”()。

intm=0,i,j;

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

for(j=1;j<=2*i;j++)

m++;

n(n)nnn2

A.+1B.C.+1D.

设一维数组中有n个数组元素则读取第i个数组元素的平均时间复杂度为

23.,()。

O(n)O(n)O()O(n2)

A.B.log2C.1D.

下面算法将一维数组a中的n个数逆序存放到原数组中空间复杂度为

24.,()。

for(i=0;i<n;i++)

b[i]=a[n-i-1];

for(i=0;i<n;i++)

a[i]=b[i];

O()O(n)O(n)O(n2)

A.1B.C.log2D.

下面算法将一维数组a中的n个数逆序存放到原数组中空间复杂度为

25.,()。

for(i=0;i<n/2;i++)

{t=a[i];

a[i]=a[n-i-1];

a[n-i-1]=t;

}

O()O(n)O(n)O(n2)

A.1B.C.log2D.

下列叙述中正确的是

26.()。

一个算法的空间复杂度大则其时间复杂度也必定大

A.,

一个算法的空间复杂度大则其时间复杂度必定小

B.,

一个算法的时间复杂度大则其空间复杂度必定小

C.,

上述三种说法都不对

D.

树状结构是数据元素之间存在的一种

27.()。

一对一关系多对多关系多对一关系一对多关系

A.B.C.D.

设数据结构ADR其中DRrr

28.=(,),={1,2,3,4},={},={<1,2>,<2,3>,<3,4>,

则数据结构A是

<4,1>},()。

线性结构树结构图集合

A.B.C.D.

链式存储结构中的数据元素之间的逻辑关系是由表示的

29.()。

线性结构非线性结构存储位置指针

A.B.C.D.

某算法仅含程序段和程序段程序段的执行次数为n3程序段的执行次数为

30.12,13,2

5

数据结构习题解析与实验指导

.n3则该算法的时间复杂度为

001,()。

O(n)O(n2)O(n3)O()

A.B.C.D.1

以下说法正确的是

31.()。

数据结构的逻辑结构独立于其存储结构

A.

数据结构的存储结构独立于该数据结构的逻辑结构

B.

数据结构的逻辑结构唯一地决定了该数据结构的存储结构

C.

数据结构仅由其逻辑结构和存储结构决定

D.

设有如下遗产继承规则丈夫和妻子可以互相继承遗产子女可以继承父亲和母亲的遗

32.:,

产子女间不能相互继承则表示该遗产继承关系最合适的数据结构应该是

,,()。

树图线性表集合

A.B.C.D.

年第题设n是描述问题规模的非负整数下面程序片段的时间复杂度

33.【20111】,

是

()。

x=2;

while(x<n/2)

x=2*x;

O(n)O(n)O(nn)O(n2)

A.log2B.C.log2D.

年第题求整数nn阶乘的算法如下其时间复杂度是

34.【20121】(≥0),()。

intfact(intn){

if(n<=1)

return1;

returnn*fact(n-1);

}

O(n)O(n)O(nn)O(n2)

A.log2B.C.log2D.

年第题下列程序段的时间复杂度

35.【20141】()。

count=0;

for(k=1;k<=n;k*=2)

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

count++;

O(n)O(n)