自考02365《计算机软件基础(二)》习题解答.pdf

1 计算机软件基础 二 习题解答 第 1 章 概论复习题答案 1 怎样的计算机被称为裸机 什么是虚拟计算机 解答 对于一台只有硬件构成 通常包括 中央处理器 cpu 储存器 输入和输出设 备 而没有安装任何软件的计算机被称为裸机 而虚拟计算机则是指以硬件为物质基 础 加装软件后的扩充后的计算机系统 2 计算机软件资源的作用如何 在你使用的计算机上有那些软件资源 解答 计算机软件资源的作用是只有在软件资源的支持下 用户所使用的计算机才 能极大程度上满足用户需要的虚拟计算机 软件资源有 汇编程序 各种高级语言 各 种语言的解释或编译程序 各种标准程序库 操作系统 数据库系统软件 计算机网络 软件 各种应用软件等 3 汇编语言和高级语言有什么不同 解答 汇编语言是面向机器的语言 即不同型号的计算机的汇编语言是各不相同的 进行程序设计时必须了解所使用的计算机的结构性能和指令系统 而且编好的程序也只 是针对一类机器 不能通用 高级语言是面对过程的语言 用户不必了解具体机器的细 节就能编写程序 方便了程序的设计 提高了效率 同时也便于人们的交流 4 我们知道计算机只能执行机器指令 为什么它能运行汇编语言和高级语言编写的程序 解答 计算机之所以能运行汇编语言编写的程序是因为计算机系统中装有汇编程序 汇编程序的作用是将源程序翻译成用机器语言组成的目标程序 从而计算机能运行汇编 语言编写的程序 计算机之所以能运行高级语言编写的程序是因为计算机系统中装有解 释程序或编译程序 它们将用高级语言编写的程序翻译成用机器语言组成的目标程序 从而计算机能运行高级语言编写的程序 5 你学习过那些高级语言 试分析它们的特点和适用的范围 解答 fortran 语言主要用于科学和工程计算 pascal 语言则具有良好的程序结构 cobol 语言则是面向事务处理的 lisp 语言是人工智能语言 c 语言则是通用的程序设计语言 c 语言是面向对象的程序设计语言 6 计算机软件的定义是什么 解答 计算机软件是指 计算机程序 实现程序功能所采用的方法 规则以及相关联 的文档和在机器上运行它所需要的数据 7 操作系统的作用是什么 解答 操作系统控制和管理计算机的硬件 软件资源 实现对处理机 存储器 I O 设备 文件等四类资源的管理 同时操作系统还作为用户和计算机系统之间的接口 方 便了人机交互 2 8 计算机操作系统在发展中经历了那些阶段 试简述它们的特点 解答 主要经历了 手工操作阶段 成批处理系统阶段 执行程序阶段 多道程序 系统和分时系统阶段 手工操作阶段的特点 计算机的全部资源归一个用户的一个程序 独占操作过程有人工来干预 成批处理系统阶段 相对于手工操作阶段 它提高了计算 机资源的利用率和增强了系统的处理能力 但由于处理机和 I O 设备是串行工作的 大 部分时间被消耗在输入输出上 处理机的大部分时间处于等待状态 故处理机和 I O 设 备的速度不匹配的矛盾成为进一步提高计算机的效率的关键 执行程序阶段 使系统实 现了模块化结构 易于设计 修改和扩充 但由于计算机本身的顺序性 计算机并不能 完全消除对外设传输的等待 多道程序系统 它需要一个调度算法来解决 cpu 的分配问 题 需要有一个储存管理程序来解决多道程序在内存中的定位 分配和免遭破坏 需要 有一个设备管理程序来解决外设的分配 释放和信息交换 此外还需要有一个文件管理 程序来解决以文件形式存放于外存中的程序和数据 分时系统阶段 分时系统阶段采用 划分时间片的方法来接受和处理各个用户从终端输入的命令 由于计算机运行的高速性 和并行性 使每个用户感觉不到别的用户的存在 好像独占整台机器 9 计算机应用软件有那些 解答 主要有以下三大领域 事务处理软件 工程和科学计算软件 实时应用软件 随着计算机技术的发展一些新的领域异军突起 如 嵌入式应用软件 微型机工具软件 人工智能软件 3 第 2 章 数据结构复习题答案 一 选择题 1 线性表 L 在 情况下适用于使用链式结构实现 A 需经常修改 L 中的结点值 B 需不断对 L 进行删除和插入 C L 中含有大量的结点 D L 中结点结构复杂 答案 应选 B 2 线性表在采用链表存储时其地址 A 必须是连续的 B 部分地址是连续的 C 一定不是连续的 D 连续不连续都可以 答案 应选 D 3 数组 Q n 用来表示一个循环队列 f 为当前队列头元素的前一个位置 r 为队尾元素的 位置 假定队列中元素的个数小于 n 计算队列中元素的公式为 A r f B n f r n C n r f D n r f n 答案 应选 D 4 若入栈序列为 1 2 3 4 在入栈的过程中允许出栈 则 不可能是一个出栈序 列 A 1 4 3 2 B 2 3 4 1 C 3 1 4 2 D 3 4 2 1 答案 应选 C 5 一个二维数组 M 行下标的范围是 1 到 8 列下标的范围是 0 到 9 每个数组元素用相邻 的 5 个字节存储 存储器按字节编址 设存储数组元素 M 1 0 的第一个字节的地址是 98 且按列存储 则 M 3 7 的第一个字节的地址是 A 135 B 233 C 290 D 388 答案 应选 D 6 由 3 个结点所构成的二叉树有 种形态 由 3 个结点构成的树有 种形态 A 3 B 4 C 5 D 6 答案 应选 C 和 A 7 不含任何结点的空树 A 是一棵树 B 是一棵二叉树 C 是一棵树也是一棵二叉树 D 既不是一棵树也不是一棵二叉树 答案 应选 B 8 一棵深度为 k 的满二叉树中结点的个数是 A 2 k 1 B 2k C 2k 1 D 2k 1 答案 应选 A 9 一棵具有 257 个结点的完全二叉树 它的深度为 4 A 8 B 9 C 7 D 10 答案 应选 B 10 二叉树是非线性数据结构 所以 A 它不能用顺序存储结构存储 B 它不能用链式存储结构存储 C 用顺序存储结构和链式存储结构都能存储 D 顺序存储结构和链式存储结构都不能存储 答案 应选 C 11 把一棵树转换为二叉树后 这棵二叉树的形态是 A 唯一的 B 有多种 C 有多种 但根结点都没有左孩子 D 有多种 但根结点都没有右孩子 答案 应选 A 12 在表长为 n 的链表中进行线性查找 它的平均查找长度为 A ASL n B ASL n 1 2 C ASL 1 D ASL log2 n 1 1 答案 应选 B 二 填空题 1 数据的基本单位是 它可以由 组成 答案 数据元素 数据项 2 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是 答案 顺序存储结构 3 顺序表结构适宜于进行 存取 链表适宜于进行 存取 答案 随机存取 顺序存取 4 栈是一种特殊的线性表 允许插入和删除运算的一端为 不允许插入和删除运算的 一端为 答案 栈顶 栈底 5 是被限定为只能在表的一端进行插入运算 在表的另一端进行删除运算的 线性表 答案 队列 6 三元组表中的每个结点对应与稀疏矩阵的一个非零元素 它包含有三个数据项 分别表 示该元素的 和 答案 行下标 列下标 元素值 7 对于一棵非空二叉树 它的根结点作为第一层 则它的第 i 层最多能有 个结点 n 5 答案 2 i 1 8 把一棵树转化为二叉树以后 这棵二叉树的根结点没有 答案 右子树 9 在数据的存放无规律而言的线性表中进行检索的最佳方法是 答案 线性检索 10 有一个表长为 m 的散列表 初始状态为空 现将 n nlink return i 3 给定一个 n 项元素的线性表 V 写一个算法 将元素排列的次序颠倒过来 要求仍占用 原来的空间 并且用顺序表和单链表两种方法表示 分析 将 V 1 与 V n 交换 V 2 与 V n 1 交换 V n 2 与 V n 2 1 交换 答案 顺序表结构下的实现 define M 1000 int v M int n void invert int temp for i 0 ilink u link p 将删除的结点插入到另一个链表中 p u head p 新链表的头指针 4 试设计实现在单链表中删除值相同的多余结点的算法 答案 typedef struct snode char data struct snode link NODE void purge lklist NODE head NODE p q r p head link p 指向当前检查结点的位置 先将其初始化 if p NULL return 空表返回 while p linkt NULL 当前结点不是尾结点 q p while q link NULL 删除值与 p 所指结点的值相同的结点 if q link data p data 若有值相同的结点 q r q link q link q link link 删除多余结点 free r else q q link 找下一个可以的多余结点 p p link 更新检查结点 5 描述以下三个概念的区别 头指针 头结点 首元元素结点 答案 头指针 是指向单链表的第一个结点的指针 头结点 在链表的首元元素结点之前附设的一个结点 首元元素结点 是指用于存储线性表中第一个数据的结点 6 写出计算线性链表长度的算法 分析 根据单链表的特性 从单链表第一个结点开始访问 只要是非空结点 计数 一次 直到所有结点访问一遍 答案 typedef struct snode char data struct snode link NODE 8 int length NODE head NODE p int i p head i 0 初始化 while p NULL i p p link return i 7 设有一个线性链表 其结点为正整数 且按值从小到大链接 试写出一个算法 将此线 性链表分解成两个线性链表 其中一个链表中的结点值均为奇数 而另一个链表中的结点值 均为偶数 且这两个链表均按值从小到大链接 分析 在链表 head 中依次取元素 s data 若取出的元素是奇数 把它插入到奇数链 表 ahead 中 若取出的元素是偶数 把它插入到偶数链表 bhead 中 继续取下一个元素 直 到链表的尾部 头指针 ahead 和 bhead 分别指向奇数链表和偶数链表 答案 typedef struct snode int data struct snode link NODE void examp7 NODE head ahead bhead NODE p q s ahead NODE malloc sizeof NODE 建立奇数链表的头结点 p ahead 工作指针 p 初始化 bhead NODE malloc sizeof NODE 建立偶数链表的头结点 q bhead 工作指针 q 初始化 s head link free head s 为原表中的工作指针 释放原表中的头结点 while s NULL if s data 2 0 是偶数 q link s q q link else 是奇数 p link s p p link s s link 取下一个结点 p link NULL 置奇数表的表尾 q link NULL 置偶数表的表尾 8 假设有一个循环单链表的长度大于 1 且表中既无头结点也无头指针 已知 S 为指向链 表中某结点的指针 试编写算法 在链表中删除 S 指针所指结点的前驱结点 分析 设置一个指针 p 指向 S 结点的前驱结点的前驱结点 答案 typedef struct snode char data struct snode link NODE NODE s void deleteprior NODE p q p s while p link link s p p link 让 p 指向 s 结点的前驱结点的前驱结点 9 q p link q 指向被删除结点 p link q link 删除 free q 9 已知指针 ha 和 hb 分别指向两个单链表的头结点 且头结点的数据域中存放链表的长度 试写出一个算法将这两个链表连接在一起 并要求算法以尽可能短的时间内完成运算 分析 令表 hb 的首元结点连在表 ha 中的最后一个结点之后 首先想将工作指针 p 从 ha 的首元结点开始遍历到表 ha 中的最后一个结点 hc 指向连接后的链表的头结点 答案 typedef struct snode char data struct snode link NODE NODE ha hb hc void example9 NODE p int i hc ha hc 指向连接后的链表的头结点 p ha link i 1 用于表 ha 中结点的计数器 while idata p p link ha data 是表 ha 的长度 p link hb link 连接表 hb 的首元结点 hc data ha data hb data 连接后的链表的长度 10 对于下面的每一步 画出栈元素和栈顶指针示意图 1 栈空 2 在栈中入栈一个元素 A 3 在栈中入栈一个元素 B 4 出栈中一个元素 5 在栈中入栈一个元素 C 6 出栈中一个元素 7 出栈中一个元素 答案 1 2 3 4 5 6 7 11 设有编号为 1 2 3 4 的四辆列车 顺序进入一个栈式结构的车站 具体写出这四辆 列车开出车站的所有可能的顺序 答案 1 2 3 4 1 2 4 3 1 3 1 4 1 3 4 2 1 4 3 2 2 1 3 4 2 1 3 3 2 3 1 4 2 3 4 1 2 4 3 1 3 2 1 4 3 2 4 1 3 4 2 1 4 3 2 1 12 说明栈和队列的异同点 A B A A A A C 10 答案 相同点 栈和队列都是线性表结构 不同点 栈是限定在线性表的一端进行插入和删除的操作 而队列的插入和删除在线性 表的两端进行 13 顺序队的 假溢出 是怎样产生的 如何知道循环队是空还是满 答案 队列的尾指针已经到了数组的上界 此时如果还要执行入队运算 就要发生 上溢 但是数组中还有空位置 这种现象称为 假溢出 在循环队中 当 rear front 时 表示队空 当 rear 1 M front 时 表示队满 14 设循环队列的容量为 40 序号从 0 到 39 现经过一系列的入队和出队运算后 有 1 front 11 rear 19 2 front 19 rear 11 问在这两种情况下 循环队 列中的各有多少个元素 答案 1 8 个 2 32 15 假设一数组 squ m 存放循环队列的元素 若要使 m 个分量都得到利用 则需要另一个 标志 tag 以 tag 为 0 或 1 来区分队尾指针和队头指针值相同时队列的状态是 空 还是 满 试编写与此结构相应的入队和出队的算法 答案 define M 100 int squ M front rear tag 队列中加一个标志域 tag int addque int x 入队运算 if tag 1 否则返回给用户不合 格订单信息 2 出版社分类统计 读入一批订单和出版社档案文件 按出版社分类统计 生成各出 版社的订单 8 对于写小说明的三种方式 在实际使用的时候 哪种情况下选用哪种方式 试举例说明 解答 除自然语言外 结构化分析方法写小说明的常用方法还有 结构化英语 判定 表和判定树 在表达一个基本加工逻辑时 结构化英语 判定表和判定树常常被交叉 使用 互相补充 判定树易学易懂且表达的是直观的图形表示 一目了然 易于同用 户讨论 判定表最易进行逻辑验证 因为它考虑了全部可能的情况 结构化英语最易 作为文档表示 且便于修改 在实际使用的时候 对于不太复杂的判断条件 或用判 定表有困难时 使用判定树较好 对于较复杂的判定 组合条件较多 则使用判定表 较好 而在一个加工逻辑中 如同时存在顺序 判定和循环时 使用结构化英语较好 下面就以商店业务处理系统中 检查发货单 为例 分别用三种方式表示 1 结构化英语 图书预订系统的顶层数据流图 出版社档案文件 对 出 版 社订单 正确订单 一批订单 订货存根文件 订货存根 书目 地址 待处理订单文件 顾客档案文件 用户信 用状况 不 合 格 订 单 订单 图书目录文件 书名 出版社 价格 检 验 订 单 顾客 按出版社 汇总统计 出版社 44 IF the invoice exceeds 500 THEN IF the account has any invoice more than 60 days overdue THEN the confirmation pending resolution of the debt ELSE issue confirmation and invoice ENDIF ELSE IF the account has any invoice more than 60 days overdue THEN issue confirmation invoice and write message on credit action report ELSE issue confirmation and invoice ENDIF ENDIF 2 判定表 1 2 3 4 条 件 发货单金额 500 500 500 500 赊欠情况 60 天 60 天 60 天 60 天 操 作 不发出批准书 发出批准书 发出发货单 发出赊欠报告 3 判定树 9 软件设计的目的是什么 设计阶段产生的主要工作结果是什么 解答 软件设计是一个把软件需求变换成软件表示的过程 它主要确定系统 怎样做 即将用户的要求转换成一个具体的软件系统的设计方案 设计阶段产生的主要工作结果是概要设计说明书和详细设计说明书 采用结构化设计方 法时主要包括模块结构图和模块的功能说明 采用面向对象设计方法时 设计阶段产生 的主要工作结果是一组相关的类 每个类都是一个独立的模块 既包含完整的数据结构 又包含完整的控制结构 这些类模块通过层次结构和类组合结构组成完整的应用框架 10 总体设计和详细设计有什么不同 为什么设计要分两步完成 检 查 发 货 单 发批准书 发货单 金额 500 金额 500 欠款 60 天 欠款 60 天 欠款 60 天 欠款 60 天 不发批准书 发批准书 发货单 发批准书 发货单和欠款报告 45 解答 从工程管理的角度看 软件设计分为总体设计和详细设计 每一步骤考虑的详 细程度有所不同 总体设计是在软件需求说明书的基础上建立软件的系统结构 包括数 据结构和模块结构 而详细设计是过程设计 通过对结构表示进行细化 得到软件的详 细的数据结构和算法 将软件设计分为总体设计和详细设计两个步骤 体现了软件设计中 抽象 的原则 总 体设计建立起整个系统的体系结构框架和系统中的全局数据结构 它从系统全局的角 度 考虑处理方式 运行方式 以及系统维护等方面的问题 奠定了整个系统实现的基 础 没有总体设计 直接考虑程序设计 就不能全局把握软件系统的结构和质量 造成 实现活动处于一种无序状态 程序划分不合理 导致系统处于一种不稳定的状态 11 模块化的优点是什么 从块内联系和块间联系的角度出发 应该选取怎样的模块结 构 解答 软件系统的层次结构正是模块化的具体体现 将整个软件设计成若干功能单一 结构清晰 相对独立的模块 其优点是 1 简化程序设计的复杂度 2 提高系统的可靠性 使错误发生在模块内部 而不易扩散 3 提高系统的开发效率 4 提高系统的可维护性 5 减少系统开发的工作量 对相同的功能可以通过模块调用实现 模块的设计应具有强内聚 弱耦合的特点 在软件系统结构中 模块的作用范围应在 控制范围之内 尽可能减少高扇出结构 模块的大小要适中 功能要单一 并且模块 的功能应是可预测的 模块的接口要简单 清晰 传递的参数数量不能太多 类型不 要太复杂 12 确定下列模块之间的连接形式 指出它们的块间联系的类型和紧凑性 1 打开文件 打印表头 2 修改文件中的记录 并读取下一个记录 3 编制各种报表 日报表 月报表 年报表 4 检索一个文件并读出某个记录 5 读出 A 之后 把 A 写入 C 把 A 加到 B 中并验证 B 解答 1 设根据打印表头的控制信息决定打印报表的种类 则模块 1 和模块 3 之间是控制耦合 连接程度高 2 设读出文件中的某个记录中包含 A 数据项 则模块 4 和模块 5 之间 是数据耦合 连接程度低 3 其余模块之间为非直接耦合 无连接 13 现有模块 A 和 B 其中 A 用于紧急处理 主要功能是 保留现场 关闭文件 中断程 序运行 而 B 模块用来求解一个线性方程组 并对求得的各未知量求平均值 主要功能是 建立系数矩阵 矩阵求逆 解出未知量 求出平均值 试问模块 A 与模块 B 相比较 哪个 模块的块内联系更紧密 为什么 解答 B 模块的块内联系更紧密 因为 B 模块是一种顺序内聚 而 A 模块是一种时 间内聚 所以 B 模块的块内联系比 A 模块更紧密 14 完成图书预订系统的数据流图的设计工作 46 15 软件测试有哪些基本原则 解答 软件测试的基本原则是 1 最好由一个独立的部门或组织来测试软件系统 2 测试用例应该由输入数据和预期的输出结果两部分组成 3 不仅要选用合理的输入数据 还应该选用不合理的输入数据作为测试用 例 4 除了检查程序是否做了它应该做的工作外 还要检查程序是否做了它不应 该做的事情 5 长期保留所有测试用例 直到这个软件系统被废弃不用为止 6 在对程序做了修改之后要进行再测试 7 重点测试容易出错的程序段 16 白盒法和黑盒法有什么不同 它们各用于什么地方 解答 白盒测试法把程序看成是装在一个透明的白盒子中 既完全了解程序的结 构和处理过程 并以此为基础设计测试用例 检查程序中的每条路径是否都能按照 预定的要求正确工作 模块测试以白盒测试为主 辅之以黑盒测试 同时白盒测试 也适用于对软件详细设计阶段的软件文档进行测试 黑盒法把程序看成一个黑盒子 即完全不考虑程序的内部结构和处理过程 只检查程序的功能是否能按照规格说明 书正常使用 程序是否能够适当的接受输入数据 产生正确的输出信息 并且保持 外部信息的完整性 黑盒测试主要用于联合测试和验收测试 除了测试程序外 还 适用于对需求分析阶段的软件文档进行测试 17 设一个要被测试的源程序如下 float solut x y z float x y z if x 3 if x 4 z 3 z z 1 return z 试设计测试用例 满足条件组合覆盖标准 图书预订系统 输入 分类统计订单 输出对出版社订单 检验订单 输出不合格订单 47 解答 本题共有八中可能的条件组合 它们是 1 x 3 y 2 5 x 4 z 3 2 x3 3 x 3 y 2 7 x 4 z3 y 2 8 x 4 z 3 可以选择以下四组测试数据 使得上述八种组合至少出现一次 输入 输出 覆盖标准 x 2 y 1 z 2 x 2 y 1 z 2 覆盖 1 5 两种组合 x 2 y 2 z 4 x 2 y 2 z 5 覆盖 2 6 两种组合 x 4 y 1 z 4 x 4 y 1 z 5 覆盖 3 8 两种组合 x 4 y 2 z 2 x 4 y 2 z 2 覆盖 4 7 两种组合 18 软件测试有哪几个步骤 简述每一步的目标和特点 解答 软件测试可分为以下三个步骤进行 模块测试 联合测试 验收测试 模块测试的目标是发现模块内部可能的各种错误 这些错误通常是在编码阶段产生 的错误 因此为模块测试设计测试用例时多以白盒测试为主 联合测试是把各模块连接起来进行测试 测试的依据是模块说明书 联合测试可以 查找与接口有关的错误 这一步的目标是发现设计阶段产生的错误 验收测试是把 软件系统当作单一的实体进行的测试 验收测试的过程和结果应当是客观的且符合 实际 因此验收测试应在软件投入后的实际环境下进行 并由用户主持进行 测试 用例应为实际数据 验收的依据是系统说明书 这一步的目标是发现分析阶段的错 误 19 软件维护的含义是什么 有哪几种类型的维护 解答 软件维护是指软件投入运行后 解决发生的各种故障 错误 增加其功 能 使之适应新的环境等软件工程活动 主要分为以下四种类型的维护 1 改正性维护 为排除故障 使系统能正常运行 需要进行诊断和改正错误 这样的维护工作称为改正性维护 2 适应性维护 为适应各种环境的变化而修改软件的维护工作 称之为适应性 维护 3 完善性维护 为满足用户的新需要 而对软件进行的修改和扩充 这样的维 护工作称之为完善性维护 4 预防性维护 为了改进软件未来的易维护性和可靠性 或者为了给未来的改 进提供更好的基础而对软件进行的修改 称之为预防性维护 20 什么是 易维护性 为什么 易维护性 是软件的一个重要的质量标准 解答 软件的易维护性是指软件易阅读 易发现和纠正错误 易修改扩充的能力 软件的易维护性是衡量软件的一个重要标准 这是因为随着软件规模的扩充和复杂 性的增加 用于软件维护的成本不断的上升 同时由于合理的改错和修改要求不能 及时满足而引起用户的不满 由于维护的副作用 在软件中引入新的错误而降低软 件的可靠性等等 这些都说明软件维护的问题显得越来越重要 软件易维护性的三 个特性 可测试性 可理解性和可修改性都是衡量软件质量的基本特性 因此软件 的易维护性是软件的一个重要的质量标准 48 实验一至实验四的实验环境要求 TURBOC 2 0 上机步骤 以 WINDOWS 98 为例 1 进入 WINDOWS 98 2 进入 MSDOS 方式 3 执行 命令 PDOS95 进入汉字系统 4 进入 TURBOC 2 0 的集成环境 实验一 一 实验名称 线性表的插入和删除 二 实验目的与要求 掌握线性表在链接存储结构下的插入与删除运算 其数据是用随机数的方法来得到随机 数 三 程序清单 include include typedef struct ss int x struct ss next node 插入一个结点 node insert node head int a node p1 new p1 head next new node malloc sizeof node new x a new next NULL head next new new next p1 return head 删除一个结点 node dele node head int a node p1 p2 p1 head next p2 head if head next NULL printf shibai return head else while a p1 x p1 p1 next if a p1 x free p1 if a p1 x free p1 return head 显示链表 void display node head node p1 printf 链表如下 n p1 head next while p1 printf d p1 x p1 p1 next printf n 主函数 main 49 int w n i node head head node malloc sizeof node head next NULL printf 输入数据的个数 scanf d for i 1 i n i w rand 用函数 rand 随机产生一个整数 head insert head w display head printf 插入一个数 scanf d head insert head w display head printf 删除一个数 scanf d head dele head w display head getch 实验二 一 实验名称 二叉排序树 二 实验目的与要求 掌握二叉树的链式存储结构 二叉树的遍历方法和二叉排序树的查找方法 三 程序清单 include typedef struct node int key struct node lchild rchild BSTNode 插入一个结点 BSTNode insertBST BSTNode Tptr int key BSTNode f p Tptr while p if p key key return Tptr f p p keykey p lchild p rchild p BSTNode malloc sizeof BSTNode p key key p lchild p rchild NULL if Tptr NULL Tptr p else if keykey f lchild p else f rchild p return Tptr 50 建立二叉排序树 BSTNode CreateBST BSTNode T NULL int key scanf d while key T insertBST T key scanf d return T 遍历二叉排序树 void inorder BSTNode T if T inorder T lchild printf d T key inorder T rchild 查找 BSTNode serchBST BSTNode T int key if T NULL key T key return T if keykey return serchBST T lchild key else return serchBST T rchild key 主函数 main BSTNode BSTree p int a BSTree CreateBST inorder BSTree printf n printf 输入待查找的关键字 scanf d p serchBST BSTree a if p NULL printf No find n else printf d n p key 实验三 一 实验名称 排序 二 实验目的与要求 掌握选择排序法 冒泡排序法和快速排序法 三 程序清单 选择排序 void xzsort int p int n int i j min t for i 0 i n 1 i min i for j i 1 jp j min j 51 if i min t p min p min p i p i t 冒泡排序 void mpsort int p int n int i j t for i 0 i n 1 i for j 0 jp j 1 t p j p j 1 p j p j t 快速排序 void kssort int p int low int high int pivotpos if low high pivotpos partition p low high kssort p low pivotpos 1 kssort p pivotpos 1 high int partition int p int i int j int pivot p i w