下载文档原格式
数据结构（C语言版）（第2版）课后习题答案李冬梅目录第1章绪论............................................. 错误!未定义书签。
第2章线性表........................................... 错误!未定义书签。
第3章栈和队列......................................... 错误!未定义书签。
第4章串、数组和广义表................................. 错误!未定义书签。
第5章树和二叉树....................................... 错误!未定义书签。
第6章图................................................ 错误!未定义书签。
第7章查找............................................. 错误!未定义书签。
第8章排序............................................. 错误!未定义书签。
第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。
即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。
它依赖于计算机。
存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。
它由基本的数据类型构成，并包括一组相关的服务（或称操作）。
它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。
4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。
A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。
”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。
一、单项选择题：1、树形结构不具备这样的特点：（）A. 每个节点可能有多个后继（子节点）B. 每个节点可能有多个前驱（父节点）C. 可能有多个内节点（非终端结点）D. 可能有多个叶子节点（终端节点）2、二叉树与度数为2的树相同之处包括（）。
A. 每个节点都有1个或2个子节点B. 至少有一个根节点C. 至少有一个度数为2的节点D. 每个节点至多只有一个父节点3、一棵完全二叉树有999 个结点，它的深度为（）。
A．9 B．10 C．11 D．124、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）A. s->next=p;p->next=s;B. s->next=p->next;p->next=s;C. s->next=p->next;p=s;D. p->next=s;s->next=p;5、对于一棵具有n个结点、度为5的树来说，（）A. 树的高度至多是n-3B. 树的高度至多是n-4C. 树的高度至多是nD. 树的高度至多是n-56、在顺序队列中，元素的排列顺序（）。
A. 由元素插入队列的先后顺序决定B. 与元素值的大小有关C. 与队首指针和队尾指针的取值有关D. 与数组大小有关7、串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储 B．数据元素是一个字符C．可以链式存储 D．数据元素可以是多个字符若8、顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除1个元素，再插入2 个元素后，front和 rear的值分别为（）。
A．5 和1 B．2和4 C．1和5 D．4 和29、一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（）。
A．250 B．500 C．254 D．50110、已知一个有向图如下图所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（）。
严蔚敏 数据结构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 试画出与下列程序段等价的框图。
数据结构C语言版第版习题答案—严蔚敏简化版 The following text is amended on 12 November 2020.第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8 B． C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的 B．部分地址必须是连续的C．一定是不连续的 D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．n B．2n-1 C．2n D．n-1答案：A解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
数据结构c语言版考试题及答案一、单项选择题（每题2分，共20分）1. 在C语言中，以下哪个选项不是合法的数组声明？A. int a[10];B. int b[2][3];C. int c[];D. int d[0];答案：D2. 链表与数组相比，以下哪个特点是链表独有的？A. 随机访问B. 动态存储分配C. 连续存储D. 固定大小答案：B3. 在C语言中，以下哪个函数用于创建一个单链表节点？A. mallocB. callocC. reallocD. free答案：A4. 栈的后进先出（LIFO）特性是指？A. 最后插入的元素最先被删除B. 最先插入的元素最先被删除C. 最后插入的元素最后被删除D. 最先插入的元素最后被删除答案：A5. 在二叉树中，叶子节点是指？A. 没有子节点的节点B. 只有一个子节点的节点C. 有两个子节点的节点D. 既没有左子节点也没有右子节点的节点答案：A6. 哈希表解决冲突的常用方法不包括？A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法答案：D7. 在图的遍历中，深度优先搜索（DFS）使用的是？A. 栈B. 队列C. 链表D. 数组答案：A8. 快速排序算法的时间复杂度在最好情况下是？A. O(n^2)B. O(n)C. O(nlogn)D. O(logn)答案：C9. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于根节点的值B. 右子树上所有节点的值大于根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等答案：D10. 以下哪个算法不是排序算法？A. 冒泡排序B. 选择排序C. 插入排序D. 深度优先搜索答案：D二、填空题（每题2分，共20分）1. 在C语言中，动态分配的内存需要使用________函数来释放。
答案：free2. 一个完全二叉树的第i层（从0开始计数）最多有________个节点。
答案：2^i3. 在图的表示方法中，邻接矩阵适合表示________图，邻接表适合表示________图。
数据结构（C语言版）（第2版）欧阳光明（2021.03.07）课后习题答案李冬梅2015.3目录第1章绪论1第2章线性表5第3章栈和队列16第4章串、数组和广义表33第5章树和二叉树43第6章图55第7章查找69第8章排序83第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。
13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。
16.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此,顺序表也称为随机存取的数据结构。
17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。
单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
18.在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值指示。
19.在n 个结点的单链表中要删除已知结点*p, 需找到它的前驱结点的地址,其时间复杂度为O(n)。
24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。
25. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 ；若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。
26． 由３个结点所构成的二叉树有 5 种形态;二叉树五种基本形态：空~、仅有根结点的~、右子树为空的~、左右子树均非空的~、左子树为空的~。
27.一棵深度为6的满二叉树有 n 1+n 2=0+ n 2= n 0-1=31 个分支结点和 26-1 =32 个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
28设一棵完全二叉树有700个结点，则共有350个叶子结点。
答：最快方法用叶子数＝[n/2]＝350 30.设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
答：最快方法：用叶子数＝[n/2]＝500 ，n 2=n 0-1=499。
另外，最后一结点为2i 属于左叶子，右叶子是空的，所以有1个非空左子树。
完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.31．在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
32. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
33. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20比较大小。
35. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
36. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。
答：错误。
链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
2. 链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
错，前一半正确，但后一半说法错误，那是链式存储的优点。
顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
7. 线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式，顺序存储和链式存储。
后者不要求连续存放。
9. 顺序存储方式只能用于存储线性结构。
错误。
顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。
10. 线性表的逻辑顺序与存储顺序总是一致的。
错，理由同7。
链式存储就无需一致。
11. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。
12. 在表结构中最常用的是线性表，栈和队列不太常用。
错，不一定吧？调用子程序或函数常用，CPU中也用队列。
14. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
15. 栈和链表是两种不同的数据结构。
错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。
18. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
正确（√）21. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）22.二叉树中每个结点的两棵子树的高度差等于1。
（√）23.二叉树中每个结点的两棵子树是有序的。
（×）24.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）25.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（√）29.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
二、问答题：1.简述“软件工程”的工程化的思想。
答：软件工程就是应用一些科学理论和工程上的技术来指导软件开发。
软件工程将研制软件的全过程分为六个阶段：问题说明，需求分析，系统设计，编写程序，测试工作，运行与维护。
软件工程的基本原则是：划分软件生命期，运行计划评审，编制软件文档。
2. 说明对程序进行评价时，“时间”与“空间”之间的关系。
答：时间性和空间性是程序的效率问题。
时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。
时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。
空间效率一般指程序花费的内存空间的问题。
对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。
两者具有一定的矛盾性。
但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。
3. 依照“软件工程”的思想，叙述软件生命周期的不同阶段及各阶段的主要工作内容。
答：在软件工程中，把从软件的计划开始，经历问题的说明（定义），需求分析，设计代码，测试与维护，直到软件报废为止的整个期间，称为软件的生命周期。
在软件生命周期中，除了最后的运行与维护属于运行期，其它都称为开发期。
1）问题说明：对研究的问题进行完整而且适当的说明。
2）需求分析：根据问题说明，确定软件必须具有的功能。
不是具体解决问题，而是明确必须“做什么”。
3）系统设计：将反映用户要求的逻辑模型转换为一个具体的设计方案，使用伪码来描述算法。
4）编写程序：将伪码转换为高级语言的形式。
5）测试工作：检查程序和系统的其他部分是否满足设计要求。
6）运行与维护：将验收后的软件交付用户使用，通过实际运行环境的检验，对不适应的部分进行修改和扩充。
一、线性表的建立：1、建立一个线性链表：2、插入一个结点：在头部：在中间：在尾部：3、删除一个结点：头部中间尾部二、线性链表原代码如下：include <stdio.h>typedef struct node{ int data;struct node *next;}NODE1、建立一个线性链表：create_list( ){ NODE *head,*p;int i,j,k;scanf(“%d”,&i);//链表的结点个数head=NULL;for(j=i;i!=0;i--){scanf(“%d”,&k);if(head==NULL){ head->data=k;p=head; }p->next->data=k;p=p->next;}p->next=NULL;return(head); }2、插入一个结点：在头部插入一个结点p ：insert(NODE*head){ NODE *p ;scanf(“%d”,&p->data)；//要插入的结点p->next=head;head=p;在p与q之间插入结点k：insert(NODE * head){NODE *p,*q,*k;scanf(“%d”,&k->data)；//要插入的结点k->next=q; p->next=k; }在尾部插入一个结点q ：insert(NODE *head){NODE *p,*q; scanf(“%d”,&q->data)；//要插入的结点for(p=head;p->next!=NULL;p=p->next); //到链表的最后一个结点p->next=q;q->next=NULL;}3、删除一个结点：在头部删除一个结点p:delete(NODE*head){NODE *p; p=head;head=head->nex;free(p); }在p与q之间删除结点k：delete(NODE*head){NODE *p,*q,*k;p->next=q;free(k); }在尾部删除一个结点p:delete(NODE*head){ NODE *p,*q;for(q=p=head;p->next!=NULL;q=p,p=p->ne xt); //到链表的最后一个结点q->next=NULL;free(p);三、求二叉树的叶节点的个数：algorithm countleaf( Tree *t, int count ){ if( t != null ){ if( t->lchild == null && t->rchild == null )count++;coutleaf( t->lchild, count );coutleaf( t->rchild, count ); } } 四、求二叉树深度的算法：algorithm depth( Tree *t ){ if( t == null )return( 0 );else{ hl = depth( t->lchild );hr = depth( t->rchild );if( hl > hr )return( hl + 1 );elsereturn( hr + 1 ); }}五、将二叉树的左右孩子交换的算法：algorithm swap( Tree *b ){ Tree *t;if( b == null )return;else{ t = b->lchild;b->lchild = b->rchild;b->rchild = t;swap( b->lchild );swap( b->rchild ); }}六、用两个栈模拟一个队列：algorithm 用两个栈模拟一个队列{ stack s1, s2; // 容量都为n。
