严蔚敏数据结构-第四章 串

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。

严蔚敏 数据结构C 语言版答案详解第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)操作结果：销毁复数C Get(C,k,&e)操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

数据结构教材出版社：清华大学出版社作者：严蔚敏吴伟民ISBN ：978-7-302-02368-5目录第1章绪论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析第2章线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加第3章栈和队列3.1 栈3.2 栈的应有和举例3.3 栈与递归的实现3.4 队列3.5 离散事件模拟第4章串4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例第5章数组和广义表5.1 数组的定义5.2 数组的顺序表现和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的储存结构5.6 m元多项式的表示5.7 广义表的递归算法第6章树和二叉树6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换6.4.3 树和森林的遍历6.5 树与等价问题6.6 赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树）6.6.2 赫夫曼编码6.7 回溯法与树的遍历6.8 树的计数第7章图7.1 图的定义和术语7.2 图的存储结构7.2.1 数组表示法7.2.2 邻接表7.2.3 十字链表7.2.4 邻接多重表7.3 图的遍历7.3.1 深度优先搜索7.3.2 广度优先搜索7.4 图的连通性问题7.4.1 无向图的连通分量和生成树7.4.2 有向图的强连通分量7.4.3 最小生成树7.4.4 关节点和重连通分量7.5 有向无环图及其应用7.5.1 拓扑排序7.5.2 关键路径7.6 最短路径7.6.1 从某个源点到其余各顶点的最短路径7.6.2 每一对顶点之间的最短路径第8章动态存储管理8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法8.3.1 可利用空间表的结构8.3.2 分配算法8.3.3 回收算法8.4 伙伴系统8.4.1 可利用空间表的结构8.4.2 分配算法8.4.3 回收算法8.5 无用单元收集8.6 存储紧缩第9章查找9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.1.3 静态树表的查找9.1.4 索引顺序表的查找9.2 动态查找表9.2.1 二叉排序树和平衡二叉树9.2.2 B树和B+树9.2.3 键树9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法9.3.4 哈希表的查找及其分析第10章内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.3 希尔排序10.3 快速排序10.4 选择排序10.4.1 简单选择排序10.4.2 树形选择排序10.4.3 堆排序10.5 归并排序10.6 基数排序10.6.1 多关键字的排序10.6.2 链式基数排序10.7 各种内部排序方法的比较讨论第11章外部排序11.1 外存信息的存取11.2 外部排序的方法11.3 多路平衡归并的实现11.4 置换一选择排序11.5 最佳归并树第12章文件12.1 有关文件的基本概念12.2 顺序文件12.3 索引文件12.4 ISAM文件和VSAM文件12.4.1 ISAM文件12.4.2 VSAM文件12.5 直接存取文件（散列文件）12.6 多关键字文件12.6.1 多重表文件12.6.2 倒排文件附录A 名词索引附录B 函数索引参考书目。

串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版习题集解析部分第4章串——《数据结构题集》-严蔚敏.吴伟民版源码使⽤说明链接☛☛☛课本源码合辑链接☛☛☛习题集全解析链接☛☛☛相关测试数据下载链接☛本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼04 串⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04源码测试数据存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04\Data⼀、基础知识题4.1❶简述空串和空格串（或称空格符串）的区别。

4.2❷对于教科书4.1节中所述串的各个基本操作，讨论是否可由其他基本操作构造⽽得，如何构造？4.3❶设s = ‘I AM A STUDENT’，t = ‘GOOD’，q = ‘WORKER’。

求：StrLength(s)，StrLength(t)，SubString(s, 8, 7)，SubString(t, 2, 1)，Index(s, ‘A’)，Index(s, t)，Replace(s, ‘STUDENT’, q)，Concat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8)))。

4.4❶已知下列字符串a = ‘THIS’,　f = ‘A SAMPLE’,　c = ‘GOOD’,　d = ‘NE’,b = ‘ ’.s = Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))),t = Replace(f, SubString(f, 3, 6), c),u = Concat(SubString(c, 3, 1), d),g = ‘IS’,v = Concat(s, Concat(b, Concat(t, Concat(b, u)))),试问：s，t，v，StrLength(s)，Index(v, g)，Index(u, g)各是什么？4.5❶试问执⾏以下函数会产⽣怎样的输出结果？void demonstrate(){StrAssign(s, ‘THIS IS A BOOK’);Replace(s, SubString(s, 3, 7), ‘ESE ARE’);StrAssign(t, Concat(s, ‘S’));StrAssign(u, ‘XYXYXYXYXYXY’);StrAssign(v, SubString(u, 6, 3));StrAssign(w, ‘W’);printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));}//demonstrate4.6❷已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

严蔚敏数据结构各章习题及答案数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ① while(s<="" ②="" ③="">解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束，则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出：x=nn 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ① while(i<=n) i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

log)得：T（n）=O(n2【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

期末复习 第一章 绪论 复习1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。

2、算法分析的两个主要方面是空间复杂度和时间复杂度。

3、数据元素是数据的基本单位。

4、数据项是数据的最小单位。

5、数据结构是带结构的数据元素的集合。

6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。

数据结构算 法数据：计算机处理的信息总称数据项：最小单位 数据元素：最基本单位数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。

概念：数据元素之间的关系 线性结构：一对一非线性结构 树：一对多 图：多对多顺序存储结构 链表存储结构 索引。

散列。

算法描述：指令的有限有序序列有穷性 确定性 可行性 输入 输出 时间复杂度 空间复杂度第二章 线性表 复习1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针2、线性表采用顺序存储，必须占用一片连续的存储单元3、线性表采用链式存储，便于进行插入和删除操作4、线性表采用顺序存储和链式存储优缺点比较。

5、简单算法第三章 栈和队列 复习定义逻辑关系：前趋 后继节省空间 随机存取 插、删效率低 插入 删除1、 栈和队列的异同点。

2、 栈和队列的基本运算3、 出栈和出队4、 基本运算第四章 串 复习存储结构栈的概念：在一端操作的线性表 运算算法栈的特点：先进后出 LIFO初始化 进栈push 出栈pop顺序队列 循环队列队列概念：在两端操作的线性表 假溢出链队列队列特点：先进先出 FIFO基本运算顺序：链队：队空：front=rear队满：front=(rear+1)%MAXSIZE队空：rear 初始化 判空 进队 出队取队首元素第五章 数组和广义表 复习定义：由n(≥1)个字符组成的有限序列 S=”c 1c 2c 3 ……cn ”串长度、空白串、空串。

紧缩格式 非紧缩格式以字节为单位的存储格式 （C 语言用数组或指针表示） 基本运算strlen(s) 串长度 strcat(s1,s2) 联接 strcmp(s1,s2) 比较 strcpy(s1,s2) 复制 strstr(s1,s2) 子串查询模式匹配失败链接值匹配算法单字符链表串 多字符链表串串变量的存储映像：串名、串值对应关系表顺序存储方式压缩存储方式行优先顺序存放列优先顺序存放C语言数组：行优先下标从[0]开始，公式变化稀疏矩阵应用表达式程序调用广义表定义：n(≥0)个元素的有限序列表头：Head(A)= a1概念：长度、深度、原子、子表表尾：Tail(A)=(a2,a3,…,a n)表结点特殊矩阵对称矩阵三角矩阵对角矩阵三元组存储：三元组m n t链表存储：十字链表原子结点第六章 树 复习1、三个结点可以组成2种不同形态的树。

《数据结构（C语言版第2版）》（严蔚敏著）第四章练习题答案第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案：B（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。

（3）串“ababaaababaa”的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval为（）。

A．010104101B．010102101 C．010100011 D．010101011答案：A（5）串的长度是指（）。

A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。

A．808 B．818 C．1010 D．1020答案：B解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。

（7）设有数组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答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r{StrAssign(r,''); //初始化r为空串for(i=Strlen(s);i;i--){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中}}//String_Reverse4.11void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r{StrAssign(r,'');for(i=1;i<=Strlen(s);i++){StrAssign(c,SubString(s,i,1));for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现if(i==j){for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中if(k>Strlen(t)) StrAssign(r,Concat(r,c));}}//for}//String_Subtract4.12int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数{for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串{ //分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串i+=Strlen(V); //当前指针跳到插入串以后n++;}//ifreturn n;}//Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place',T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?4.13int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)if(!StrCompare(SubString(s,i,Strlen(t)),t)){StrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));StrAssign(S,Concat(head,tail)); //把head,tail连接为新串n++;}//ifreturn n,}//Delete_SubString4.14Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new{Initstack(s); //s的元素为Stringtype类型for(i=1;i<=Strlen(str);i++){r=SubString(str,i,1);if(r为字母) push(s,r);else{if(StackEmpty(s)) return ERROR;pop(s,a);if(StackEmpty(s)) return ERROR;pop(s,b);StrAssign(t,Concat(r,b));StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c push(s,c);}}//forpop(s,new);if(!StackEmpty(s)) return ERROR;return OK;}//NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本{for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i];}//StrAssign4.16char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数{for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);if(i>s[0]&&i>t[0]) return 0;else if(i>s[0]) return -t[i];else if(i>t[0]) return s[i];else return s[i]-t[i];}//StrCompare4.17int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T 替换为V,并返回置换次数{for(n=0,i=1;i<=S[0]-T[0]+1;i++){for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);if(k>T[0]) //找到了与T匹配的子串:分三种情况处理{if(T[0]==V[0])for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换S[i+l-1]=V[l];else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移{for(l=S[0];l>=i+T[0];l--)S[l+V[0]-T[0]]=S[l];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}else //新子串长度小于原子串时:先将后部左移{for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)S[l]=S[l-V[0]+T[0]];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}S[0]=S[0]-T[0]+V[0];i+=V[0];n++;}//if}//forreturn n;}//String_Replace4.18typedef struct {char ch;int num;} mytype;void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数{mytype T[MAXSIZE]; //用结构数组T存储统计结果for(i=1;i<=S[0];i++){c=S[i];j=0;while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过if(T[j].ch) T[j].num++;else T[j]={c,1};}//forfor(j=0;T[j].ch;j++)printf("%c: %d\n",T[j].ch,T[j].num);}//StrAnalyze4.19void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r{r[0]=0;for(i=1;i<=s[0];i++){c=s[i];for(j=1;j<i&&s[j]!=c;j++); //判断s的当前字符c是否第一次出现if(i==j){for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t中if(k>t[0]) r[++r[0]]=c;}}//for}//Subtract_String4.20int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=s[0]-t[0]+1;i++){for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);if(j>m) //找到了与t匹配的子串{for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除s[0]-=t[0];n++;}}//forreturn n;}//Delete_SubString4.21typedef struct{char ch;LStrNode *next;} LStrNode,*LString; //链串结构void StringAssign(LString &s,LString t)//把串t赋值给串s{s=malloc(sizeof(LStrNode));for(q=s,p=t->next;p;p=p->next){r=(LStrNode*)malloc(sizeof(LStrNode));r->ch=p->ch;q->next=r;q=r;}q->next=NULL;}//StringAssignvoid StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}//StringCopychar StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t 时返回负数{for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);if(!p&&!q) return 0;else if(!p) return -(q->ch);else if(!q) return p->ch;else return p->ch-q->ch;}//StringCompareint StringLen(LString s)//求串s的长度(元素个数){for(i=0,p=s->next;p;p=p->next,i++);return i;}//StringLenLString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针{p=malloc(sizeof(LStrNode));for(q=p,r=s->next;r;r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for //复制串sfor(r=t->next;r;r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for //复制串tq->next=NULL;return p;}//ConcatLString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start 位置起长为len的子串{p=malloc(sizeof(LStrNode));q=p;for(r=s;start;start--,r=r->next); //找到start所对应的结点指针rfor(i=1;i<=len;i++,r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;} //复制串tq->next=NULL;return p;}//Sub_String4.22void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c之后{p=t.head;while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符cif(!p) //没找到{t.tail->next=s.head;t.tail=s.tail; //把s连接在t的后面}else{q=p->next;r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个for(j=0;j<i;j++) r->ch[j]='#'; //原结点p包含c及其以前的部分for(j=i;j<CHUNKSIZE;j++) //新结点r包含c以后的部分{r->ch[j]=p->ch[j];p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#'}p->next=s.head;s.tail->next=r;r->next=q; //把串s插入到结点p和r之间}//elset.curlen+=s.curlen; //修改串长s.curlen=0;}//LString_Concatint Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0{for(i=0;i<CHUNKSIZE&&p->ch[i]!=c;i++);if(i==CHUNKSIZE) return 0;else return i+1;}//Find_Char4.23int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0{InitStack(S);p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)for(k=1;k<=S.curlen;k++){if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串else if(k>(S.curlen+1)/2){Pop(S,c); //将后半段的字符与栈中的元素相匹配if(p->ch[i]!=c) return 0; //失配}if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块{p=p->next;i=0;}}//forreturn 1; //成功匹配}//LString_Palindrome4.24void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t{if(t.ch) free(t.ch);t.ch=malloc((s1.length+s2.length)*sizeof(char));for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];t.length=s1.length+s2.length;}//HString_Concat4.25int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数{for(n=0,i=0;i<=S.length-T.length;i++){for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);if(k==T.length) //找到了与T匹配的子串:分三种情况处理{if(T.length==V.length)for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换S.ch[i+l-1]=V.ch[l-1];else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移{for(l=S.length-1;l>=i+T.length;l--)S.ch[l+V.length-T.length]=S.ch[l];for(l=0;l<V.length;l++)S[i+l]=V[l];}else //新子串长度小于原子串时:先将后部左移{for(l=i+V.length;l<S.length+V.length-T.length;l++)S.ch[l]=S.ch[l-V.length+T.length];for(l=0;l<V.length;l++)S[i+l]=V[l];}S.length+=V.length-T.length;i+=V.length;n++;}//if}//forreturn n;}//HString_Replace4.26Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前{if(pos<1) return ERROR;if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));for(i=S.length-1;i>=pos-1;i--)S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置for(i=0;i<T.length;i++)S.ch[pos+i-1]=T.ch[pos]; //插入串TS.length+=T.length;return OK;}//HString_Insert4.27int Index_New(Stringtype s,Stringtype t)//改进的定位算法{i=1;j=1;while(i<=s[0]&&j<=t[0]){if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])){ //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个i=i+j-2;j=1;}else{i++;j++;}}//whileif(j>t[0]) return i-t[0];}//Index_New4.28void LGet_next(LString &T)//链串上的get_next算法{p=T->succ;p->next=T;q=T;while(p->succ){if(q==T||p->data==q->data){p=p->succ;q=q->succ;p->next=q;}else q=q->next;}//while}//LGet_next4.29LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针{p=pos;q=T->succ;while(p&&q){if(q==T||p->chdata==q->chdata){p=p->succ;q=q->succ;}else q=q->next;}//whileif(!q){for(i=1;i<=Strlen(T);i++)p=p->next;return p;} //发现匹配后,要往回找子串的头return NULL;}//LIndex_KMP4.30void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度{for(maxlen=0,i=1;i<S[0];i++)//串S2向右移i格{for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动{if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数else k=0; //失配时k归零if(k>maxlen) //发现了比以前发现的更长的重复子串{lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录}}//for}//forif(maxlen){printf("Longest Repeating Substring length:%d\n",maxlen);printf("Position1:%d Position 2:%d\n",lrs1,lrs2);}else printf("No Repeating Substring found!\n");}//Get_LRepSub分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).4.31void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度{if(S[0]>=T[0]){StrAssign(A,S);StrAssign(B,T);}else{StrAssign(A,T);StrAssign(B,S);} //为简化设计,令S和T中较长的那个为A,较短的那个为Bfor(maxlen=0,i=1-B[0];i<A[0];i++){if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正{jmin=1;jmax=i+B[0];}//B有一部分在A左端的左边else if(i>A[0]-B[0]){jmin=i;jmax=A[0];}//B有一部分在A右端的右边else{jmin=i;jmax=i+B[0];}//B在A左右两端之间.//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k; }}//for}//forif(maxlen){if(S[0]>=T[0]){。

第一章绪论一、选择题1.组成数据的基本单位是A数据项B数据类型C数据元素D数据变量2.数据结构是研究数据的以及它们之间的相互关系;A理想结构,物理结构B理想结构,抽象结构C物理结构,逻辑结构D抽象结构,逻辑结构3.在数据结构中,从逻辑上可以把数据结构分成A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科;① A数据元素B计算方法C逻辑存储D数据映像② A结构B关系C运算D算法5.算法分析的目的是;A 找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性6.计算机算法指的是①,它必须具备输入、输出和②等5个特性;① A计算方法B排序方法C解决问题的有限运算序列D调度方法② A可执行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构;2.算法就是程序;3.数据元素是数据的最小单位;4.算法的五个特性为：有穷性、输入、输出、完成性和确定性;5.算法的时间复杂度取决于问题的规模和待处理数据的初态;三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____;2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点;3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________;4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________;5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系;6.算法的五个重要特性是_______、_______、______、_______、_______;7.数据结构的三要素是指______、_______和________;8.链式存储结构与顺序存储结构相比较,主要优点是________________________________;9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构;四、算法分析题1.求下列算法段的语句频度及时间复杂度参考答案：一、选择题1. C 3. C 4. A、B 5. C 、B二、判断题:1、√2、×3、×4、×5、√三、填空题1、线性、树形、图形、集合；非线性网状2、没有；1；没有；13、前驱；1；后继；任意多个4、任意多个5、一对一；一对多；多对多6、有穷性；确定性；可行性；输入；输出7、数据元素；逻辑结构；存储结构8、插入、删除、合并等操作较方便9、顺序存储；链式存储四、算法分析题fori=1; i<=n; i++forj =1; j <=i ; j++x=x+1;分析：该算法为一个二重循环,执行次数为内、外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度Tn=1+2+3+…+n=nn+1/2有1/4≤Tn/n2≤1,故它的时间复杂度为Ｏn2, 即Ｔn与n2 数量级相同; 2、分析下列算法段的时间频度及时间复杂度for i=1;i<=n;i++for j=1;j<=i;j++for k=1;k<=j;k++x=i+j-k;分析算法规律可知时间频度Tn=1+1+2+1+2+3+...+1+2+3+…+n由于有1/6 ≤ Tn/ n3 ≤1,故时间复杂度为Ｏn3第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是A110 B108C100 D1202. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素;A64B63 C D73.线性表采用链式存储结构时,其地址;A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续与否均可以4. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行As->next=p;p->next=s; B s->next=p->next;p->next=s;Cs->next=p->next;p=s; Dp->next=s;s->next=p;5.在一个单链表中,若删除p所指结点的后续结点,则执行Ap->next=p->next->next; Bp=p->next; p->next=p->next->next;Cp->next=p->next; Dp =p->next->next;6.下列有关线性表的叙述中,正确的是A线性表中的元素之间隔是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继7.线性表是具有n个的有限序列n≠0A表元素B字符C数据元素D数据项二、判断题1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同;2.如果没有提供指针类型的语言,就无法构造链式结构;3.线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继,其余的结点只有一个前驱和后继;4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值;5.要想删除p指针的后继结点,我们应该执行q=p->next ；p->next=q->next；freeq;三、填空题1.已知P为单链表中的非首尾结点,在P结点后插入S结点的语句为：_______________________ ;2.顺序表中逻辑上相邻的元素物理位置相邻, 单链表中逻辑上相邻的元素物理位置_________相邻;3.线性表L＝a1,a2,...,an采用顺序存储,假定在不同的n＋1个位置上插入的概率相同,则插入一个新元素平均需要移动的元素个数是________________________4.在非空双向循环链表中,在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;______________________;5.已知L是无表头结点的单链表,是从下列提供的答案中选择合适的语句序列,分别实现：1表尾插入s结点的语句序列是_______________________________2 表尾插入s结点的语句序列是_______________________________1.p->next=s;2.p=L;3.L=s;4.p->next=s->next;5.s->next=p->next;6.s->next=L;7.s->next=null;8.whilep->next= Q p=p-next;9.whilep->next=null p=p->next;四、算法设计题1.试编写一个求已知单链表的数据域的平均值的函数数据域数据类型为整型;2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数;3.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现出库销售m台价格为h的电视机,试编写算法修改原链表;4.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现新到m台价格为h的电视机,试编写算法修改原链表;5.线性表中的元素值按递增有序排列,针对顺序表和循环链表两种不同的存储方式,分别编写C函数删除线性表中值介于a与ba≤b之间的元素;6.设A=a0,a1,a2,...,an-1,B=b0,b1,b2,...,bm-1是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数;若n=m,且ai= bi 0≤i<n ,则A=B；若n<m ,且ai=bi 0≤i<n ,则A<B；若存在一个j, j<m ,j<n ,且ai=bi 0≤i<j , 若aj<bj,则A<B,否则A>B;试编写一个比较A和B的C函数,该函数返回-1或0或1,分别表示A<B或A=B或A>B;7.试编写算法,删除双向循环链表中第k个结点;8.线性表由前后两部分性质不同的元素组成a0,a1,...,an-1,b0,b1,...,bm-1,m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成b0,b1,...,bm-1,a0,a1,...,an-1,分析两种存储方式下算法的时间和空间复杂度;9.用循环链表作线性表a0,a1,...,an-1和b0,b1,...,bm-1的存储结构,头指针分别为ah和bh,设计C函数,把两个线性表合并成形如a0,b0,a1,b1,…的线性表,要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度;10.试写出将一个线性表分解为两个带有头结点的循环链表,并将两个循环链表的长度放在各自的头结点的数据域中的C函数;其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中;11.试写出把线性链表改为循环链表的C函数;12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数;参考答案：一、选择题1. B 3. D 4. B 5. A 7、C二、判断题:参考答案：1、×2、√3、×4、×5、√三、填空题1、s->next=p->next; p->next=s;2、一定；不一定3、n/24、q->prior=p;5、16 32 2 91 7四、算法设计题1、include ""include ""typedef struct node{int data;struct node link;}NODE;int averNODE head{int i=0,sum=0,ave; NODE p;p=head;whilep=NULL{p=p->link;++i;sum=sum+p->data;}ave=sum/i;return ave;}2、include ""include ""typedef struct node{int data; / 假设数据域为整型/struct node link;}NODE;void del_linkNODE head,int x / 删除数据域为x的结点/ {NODE p,q,s;p=head;q=head->link;whileq=head{ifq->data==x{p->link=q->link;s=q;q=q->link;frees;}else{p=q;q=q->link;}}}3、void delNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num-num; elseprintf"无此产品"; ifq->num==0{p->next=q->next; freeq;}}4、include ""include ""typedef struct node {float price;int num;struct node next;}NODE;void insNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num+num;else{s=NODE mallocsizeofNODE;s->price=price;s->num=num;s->next=p->next;p->next=s;}}5、顺序表：算法思想：从0开始扫描线性表,用k记录下元素值在a与b之间的元素个数,对于不满足该条件的元素,前移k个位置,最后修改线性表的长度;void delelemtype list,int n,elemtype a,elemtype b{int i=0,k=0；whilei<n{iflisti>=a&&listi<=b k++;elselisti-k=listi;i++;}n=n-k; / 修改线性表的长度/}循环链表:void delNODE head,elemtype a,elemtype b{NODE p,q;p= head;q=p->link; / 假设循环链表带有头结点/ whileq=head && q->data<a{p=q;q=q->link;}whileq=head && q->data<b{r=q;q=q->link;freer;}ifp=qp->link=q;}6、define MAXSIZE 100int listAMAXSIZE,listBMAXSIZE; int n,m;int compareint a,int b{int i=0;whileai==bi&&i<n&&i<mi++;ifn==m&&i==n return0;ifn<m&&i==n return-1;ifn>m&&i==m return1;ifi<n&&i<mifai<bi return-1;else ifai>bi return1;}7、void delDUNODE head,int i{DUNODE p;{head=head->next;head->prior=NULL;return0;}Else{forj=0;j<i&&p=NULL;j++p=p->next;ifp==NULL||j>i return1;p->prior->next=p->next;p->next->prior=p->proir;freep;return0;}8.顺序存储:void convertelemtype list,int l,int h / 将数组中第l个到第h个元素逆置/ {elemtype temp;fori=h;i<=l+h/2;i++{temp=listi;listi=listl+h-i;listl+h-i=temp;}}void exchangeelemtype list,int n,int m; {convertlist,0,n+m-1;convertlist,0,m-1;convertlist,m,n+m-1;}该算法的时间复杂度为On+m,空间复杂度为O1 链接存储:不带头结点的单链表typedef struct node{elemtype data;struct node link;}NODE;void convertNODE head,int n,int m{NODE p,q,r;int i;p=head;q=head;fori=0;i<n-1;i++q=q->link; /q指向an-1结点/r=q->link;q->link=NULL;whiler->link=NULLr=r->link; /r指向最后一个bm-1结点/head=q;r->link=p;}该算法的时间复杂度为On+m,但比顺序存储节省时间不需要移动元素,只需改变指针,空间复杂度为O1typedef struct node{elemtype data;struct node link;}NODE;NODE unionNODE ah,NODE bh {NODE a,b,head,r,q;head=ah;a=ah;b=bh;whilea->link=ah&&b->link=bh {r=a->link;q=b->link;a->link=b;b->link=r;a=r;}ifa->link==ah /a的结点个数小于等于b的结点个数/{a->link=b;whileb->link=bhb=b->link;b->link=head;}ifb->link==bh /b的结点个数小于a的结点个数/{r=a->link;a->link=b;b->link=r;}returnhead;}该算法的时间复杂度为On+m,其中n和m为两个循环链表的结点个数.10.typedef struct node{elemtype data;struct node link;}NODE;void analyzeNODE a{NODE rh,qh,r,q,p；int i=0,j=0；/i为序号是奇数的结点个数j为序号是偶数的结点个数/ p=a；rh=NODE mallocsizeofNODE；/rh为序号是奇数的链表头指针/qh=NODE mallocsizeofNODE; /qh为序号是偶数的链表头指针/r=rh;q=qh;whilep=NULL{r->link=p;r=p;i++;p=p->link;ifp=NULL{q->link=p;q=p;j++;p=p->link;}}rh->data=i;r->link=rh;qh->data=j;q->link=qh;}11.typedef struct node {elemtype data;struct node link;}NODE;void changeNODE head {NODE p;p=head;ifhead=NULL{whilep->link=NULLp=p->link;p->link=head;}}12.typedef struct node {elemtype data;struct node link;}NODE;void delNODE x,NODE y{NODE p,q;elemtype d1;p=y;q=x;whileq->next=NULL / 把后一个结点数据域前移到前一个结点/ {p->data=q->data;q=q->link;p=q;p->link=NULL; / 删除最后一个结点/freeq;}第三章栈和队列一、选择题1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是;A edcbaBdecbaCdceab Dabcde2.栈结构通常采用的两种存储结构是;A 线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构3.判定一个栈ST最多元素为m0为空的条件是;A ST-〉top=0 BST-〉top==0CST-〉top=m0 DST-〉top=m04.判定一个栈ST最多元素为m0为栈满的条件是;AST->top=0 BST->top==0CST->top=m0-1DST->top==m0-15.一个队列的入列序列是1,2,3,4,则队列的输出序列是;A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,16.循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是Arear-front+m%m B rear-front+1 Crear-front-1Drear-front7.栈和队列的共同点是A 都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点8.表达式ab+c-d的后缀表达式是;Aabcd+-Babc+d- Cabc+d-D-+abcd个元素a1,a2,a3和a4依次通过一个栈,在a4进栈前,栈的状态,则不可能的出栈序是Aa4,a3,a2,a1 Ba3,a2,a4,a1Ca3,a1,a4,a2 Da3,a4,a2,a110.以数组Q0..m－1存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是Arear－qulen Brear－qulen＋mCm－qulen D1＋rear＋m－qulen% m二、填空题1.栈的特点是_______________________,队列的特点是__________________________;2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素,对于栈只能在________插入和删除元素,对于队列只能在_______插入元素和_________删除元素;3.一个栈的输入序列是12345,则栈有输出序列12345是____________;正确/错误4.设栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过一个栈,一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1则栈S至少应该容纳_____个元素;三、算法设计题1.假设有两个栈s1和s2共享一个数组stackM,其中一个栈底设在stack0处,另一个栈底设在stackM-1处;试编写对任一栈作进栈和出栈运算的C函数pushx,i和popi,i=l,2;其中i=1表示左边的栈,,i=2表示右边的栈;要求在整个数组元素都被占用时才产生溢出;2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算写出模拟队列的插入和删除的C函数;一个栈s1用于插入元素,另一个栈s2用于删除元素.参考答案：一、选择题1. C 3. B 4. B 5. B 7、C 8、C 9、C 10、D二、填空题1、先进先出；先进后出2、线性；任何；栈顶；队尾；对头3、正确的4、3三、算法设计题1.define M 100elemtype stackM;int top1=0,top2=m-1;int pushelemtype x,int i{iftop1-top2==1 return1; /上溢处理/elseifi==1 stacktop1++=x;ifi==2stacktop2--=x;return0;}int popelemtype px,int iifi==1iftop1==0 return1; else{top1--;px=stacktop1;return0;}elseifi==2iftop2==M-1 return1; else{top2++;px=stacktop2;return0;}}elemtype s1MAXSIZE,s2MAZSIZE; int top1,top2;void enqueueelemtype x{iftop1==MAXSIZE return1;else{pushs1,x;return0;}}void dequeueelemtype px{elemtype x;top2=0;whileemptys1{pops1,&x;pushs2,x;pops2,&x;whileemptys2{pops2,&x;pushs1,x;}}第四章串一、选择题1.下列关于串的叙述中,正确的是A一个串的字符个数即该串的长度B一个串的长度至少是1C空串是由一个空格字符组成的串D两个串S1和S2若长度相同,则这两个串相等2.字符串"abaaabab"的nextval值为A0,1,01,1,0,4,1,0,1 B0,1,0,0,0,0,2,1,0,1C0,1,0,1,0,0,0,1,1 D0,1,0,1,0,1,0,1,13.字符串满足下式,其中head和tail的定义同广义表类似,如head‘xyz’=‘x’,tail‘xyz’= ‘yz’,则s= ; concatheadtails,headtailtails= ‘dc’; Aabcd Bacbd Cacdb Dadcb4.串是一种特殊的线性表,其特殊性表现在A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCATX,Y返回X和Y串的连接串,SUBSTRS,I,J 返回串S从序号I开始的J个字符组成的字串,LENGTHS返回串S的长度,则CONCATSUBSTRS1,2,LENGTHS2,SUBSTRS1,LENGTHS2,2的结果串是ABCDEF B BCDEFG CBCPQRST DBCDEFEF二、算法设计1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpys1,s2;2.在一般链接存储一个结点存放一个字符方式下,写出采用简单算法实现串的模式匹配的C 语言函数int L_indext,p;参考答案：一、选择题1. A 3. D 4. D 5. D二、算法设计1.顺序存储：include ""define MAXN 100char sMAXN;int S_strlenchar s{int i;fori=0;si='\0';i++;returni;}void S_strcpychar s1,char s2 include "" typedef struct node{char data;struct node link;}NODE;int L_indexNODE t,NODE p{NODE t1,p1,t2;int i;t1=t;i=1;whilet1=NULL{p1=p;t2=t1->link;whilep1->data==t1->data&&p1=NULL{p1=p1->link;t1=t1->link;}ifp1==NULL returni;i++;t1=t2;}return0;}第五章数组和广义表一、选择题1. 常对数组进行的两种基本操作是A建立与删除B索引和修改C查找和修改D查找与索引2.二维数组M的元素是4个字符每个字符占一个存储单元组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素的起始地址相同;AM24BM34CM35DM443.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是;A80B100C240D2704.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A74的起始地址为;ASA+141BSA+144CSA+222DSA+2255.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为;ASA+141BSA+180CSA+222DSA+2256.稀疏矩阵一般的压缩存储方法有两种,即;A 二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点;A正确B错误8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,nn-1/2中,对下三角部分中任一元素ai,ji<=j,在一组数组B的下标位置k的值是;Aii-1/2+j-1Bii-1/2+jCii+1/2+j-1 Dii+1/2+j二、填空题1.己知二维数组Amn采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOCA00,则A00的地址是_____________________;2.二维数组A1020采用列序为主方式存储,每个元素占一个存储单元,并且A00的存储地址是200,则A612的地址是________________;3.有一个10阶对称矩阵A,采用压缩存储方式以行序为主,且A00=1,则A85的地址是__________________;4.设n行n列的下三角矩阵A已压缩到一维数组S1..nn+1/2中,若按行序为主存储,则Aij对应的S中的存储位置是________________;5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A00的存储地址为1000,元素A13的存储地址为___________,该数组共占用_______________个存储单元;三、算法设计1.如果矩阵A中存在这样的一个元素Aij满足条件:Aij是第i行中值最小的元素,且又是第j 列中值最大的元素,则称之为该矩阵的一个马鞍点;编写一个函数计算出1×n的矩阵A的所有马鞍点;只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王;n 和m由键盘输入,打印出最后剩下的猴子号;编写一程序实现上述函数;3.数组和广义表的算法验证程序编写下列程序:1求广义表表头和表尾的函数head和tail;2计算广义表原子结点个数的函数count_GL;3计算广义表所有原子结点数据域设数据域为整型〉之和的函数sum_GL;参考答案：一、选择题1. C 3. C 4. C 5. B 7、B 8、B二、填空题1、locA00+ni+jk2、3323、424、ii+1/2+j+15、1039；72三、算法设计题1.算法思想：依题意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,则该元素Aij便是马鞍点,找出所有这样的元素,即找到了所有马鞍点;因此,实现本题功能的程序如下:include <>define m 3define n 4void minmaxint amn{int i1,j,have=0;int minm,maxn;fori1=0;i1<m;i1++/计算出每行的最小值元素,放入minm之中/{mini1=ai10;forj=1;j<n;j++ifai1j<mini1 mini1=ai1j;}forj=0;j<n;j++/计算出每列的最大值元素,放入maxn之中/{maxj=a0j;fori1=1;i1<m;i1++ifai1j>max j maxj=ai1j;}fori1=0;i1<m;i1++forj=0;j<n;j++ifmini1==maxj{printf"%d,%d:%d\n",i1,j,ai1j;have=1;}ifhave printf"没有鞍点＼n";}2.算法思想:本题用一个含有n个元素的数组a,初始时ai中存放猴子的编号i,计数器似的值为0;从ai开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出ai值退出圈外的猴子的编号,同时将ai的值改为O以后它不再参加报数,计数器值重新置为0;该函数一直进行到n 只猴子全部退出圈外为止,最后退出的猴子就是大王;因此,现本题功能的程序如下:include ""main{int a100;int count,d,j,m,n; scanf"%d %d",&m,&n;/ n>=m/ forj=0;j<n;j++aj=j+1;count=0;d=0;whiled<nforj=0;j<n;j++ifaj=0{count++;ifcount==m{printf"% d ",aj;aj=0;count=0;}}}3.include ""include ""typedef struct node { int tag;union{struct node sublist; char data;}dd;struct node link;}NODE;NODE creat_GLchar s {NODE h;char ch;s++;ifch='\0'{h=NODEmallocsizeofNODE; ifch==''{h->tag=1;h->=creat_GLs;}Else{h->tag=0;h->=ch;}}elseh=NULL;ch=s;s++;ifh=NULLifch==','h->link =creat_GLs; elseh->link=NULL; returnh;}void prn_GLNODE p {ifp=NULL{ifp->tag==1{printf"";ifp-> ==NULL printf" ";elseprn_GLp-> ;}elseprintf"%c",p->;ifp->tag==1printf"";ifp->link=NULL{printf",";prn_GLp->link;}}}NODE copy_GLNODE p{NODE q;ifp==NULL returnNULL;q=NODE mallocsizeofNODE; q->tag=p->tag;ifp->tagq-> =copy_GLp-> ;elseq-> =p->;q->link=copy_GLp->link;returnq;}NODE headNODE p /求表头函数/{returnp->;}NODE tailNODE p /求表尾函数/{returnp->link;}int sumNODE p /求原子结点的数据域之和函数/ { int m,n;ifp==NULL return0;else{ ifp->tag==0 n=p->;elsen=sump->;ifp->link=NULLm=sump->link;else m=0;returnn+m;}}int depthNODE p /求表的深度函数/ {int h,maxdh;NODE q;ifp->tag==0 return0;elseifp->tag==1&&p->==NULL return 1; else{maxdh=0;whilep=NULL{ifp->tag==0 h=0; else{q=p->;h=depthq;}ifh>maxdhmaxdh=h; p=p->link;}returnmaxdh+1;}}main{NODE hd,hc;char s100,p;p=getss;hd=creat_GL&p; prn_GLheadhd;prn_GLtailhd;hc=copy_GLhd;printf"copy after:";prn_GLhc;printf"sum:%d\n",sumhd;printf"depth:%d\n",depthhd;}第六章树和二叉树一、选择题1.在线索化二叉树中,t所指结点没有左子树的充要条件是At-〉left==NULL Bt-〉ltag==1Ct-〉ltag=1且t-〉left=NULLD以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法A正确B错误C不同情况下答案不确定3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法A正确B错误C不同情况下答案不确定4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法A正确B错误C不同情况下答案不确定5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为;A2h B2h-1C2h+1Dh+16.已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac,它的前序遍历序列是;Aacbed BdecabCdeabc Dcedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的A前序B中序C后序D层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是;Abdgcefha Bgdbecfha Cbdgaechf Dgdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值;这种说法A正确B错误C不同情况下答案不确定10.按照二叉树的定义,具有3个结点的二叉树有种;A3B4C5D611.在一非空二叉树的中序遍历序列中,根结点的右边A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点12.树最适合用来表示;A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A不发生改变B发生改变C不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用存储结构;A二叉链表B广义表存储结构C三叉链表D顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则An=h+m Bh+m=2nCm=h-1Dn=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为Auwvts BvwutsCwuvts Dwutsv17.具有五层结点的二叉平衡树至少有个结点;A10B12C15D17二、判断题1.二叉树中任何一个结点的度都是2;2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树;3.一棵哈夫曼树中不存在度为1的结点;4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2三、填空题1.指出树和二叉树的三个主要差别___________,___________,_______________;2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________3.若结点A有三个兄弟包括A本身,并且B是A的双亲结点,B的度是_______________4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域;5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________;6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_________________;7.找出满足下列条件的二叉树1先序和中序遍历,得到的结点访问顺序一样;_________________________2后序和中序遍历,得到的结点访问顺序一样;_________________________3先序和后序遍历,得到的结点访问顺序一样;__________________________8.一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各是多少____________________9.一棵二叉树有67个结点,这些结点的度要么是0,要么是2;这棵二叉树中度为2的结点有______________________个;10.含有100个结点的树有_______________________________________条边;四、问答题1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树;若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:1第k层结点数1≤k≤h;2整棵树结点数;3编号为i的结点的双亲结点的编号;4编号为i的结点的第j个孩子结点若有的编号;2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=k-1n1+13.已知一组元素为50,28,78,65,23,36,13,42,71,请完成以下操作:1画出按元素排列顺序逐点插入所生成的二叉排序树BT;2分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数;3画出在BT中删除23〉后的二叉树;4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数;5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9;1试画出对应的编码哈夫曼树要求左子树根结点的权小于等于右子树根结点的权;2求出每个字符的晗夫曼编码;3求出传送电文的总长度;4并译出编码系列101的相应电文;五、算法设计已知一棵具有n个结点的完全二叉树被顺序存储在一维数组An中,试编写一个算法输出Ai结点的双亲和所有孩子;参考答案：一、选择题1. B 3. A 4. B 5. B 7、A 8、D 9、B 10、C 11、A 12、C 13、A 14、C 15、D 16、C 17 C。

数据结构（ C语言版）（第 2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第 7 章查找 (54)第 8 章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0 ，± 1，± 2，, } ，字母字符数据对象是集合C={‘A’，‘B’， , ，‘Z’，‘ a’，‘ b’， , ，‘z ’} ，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。