答：POP3协议。
6. 常见的计算机网络拓扑结构有哪几种？其主要优缺点是什么？ 答：①星形结构是以一个节点为中心的处理系统，各种类型的入网机器均与该中心节点有物
理链路直接相连。优点：（1）可靠性高。（2）方便服务。（3）故障诊断容易。缺点：（1）安装费用高。（2）扩展困难。（3）中央节点的依赖性强。
②总线型拓扑结构是将所有的入网计算机均通过相应的硬件接口直接接入到一条通信线路上。优点：（1）布线容易、电缆用量小。（2）可靠性高。（3）易于扩充。（4）易于安装。缺点：（1）故障诊断困难。（2）故障隔离困难。（3）中继器配置。（4）通信介质或中间某一接口点出现故障，整个网络随即瘫痪。（5）终端必须是智能的。
③环型拓扑结构，是将各台联网的计算机用通信线路连接成一个闭合的环。优点：（1）电缆长度短。（2）适用于光纤。（3）无差错传输。缺点：（1）可靠性差。（2）故障诊断困难。（3）调整网络比较困难。
④树型拓扑结构是总线形结构的扩展，它是在总线网上加上分支形成的，其传输介质可有多条分支，但不形成闭合回路；也可以把它看成是星形结构的叠加。又称为分级的集中式结构。优点：（1）结构比较简单，成本低。（2）网络中任意两个节点之间不产生回路，每个链路都支持双向传输。（3）网络中节点扩充方便灵活，寻找链路路径比较方便。缺点：（1）任何一个故障都会影响整个系统。（2）对根的依赖性太大。
9
第6章 程序设计基础习题
一、 单项选择题
1~5 ADDAB 6~10 DDDA 11~15 ACBCC
二、填空题
1. 2. 3. 4. 5. 6. 7.
解释型 编译型 有穷性
时间复杂度 空间复杂度 对象 继承 可重用性 实例
三、判断改错题
1. √
2. ×（改正：解释性语言程序在运行后不会保留一个机器代码文件，而编译型会。） 3．×（改正：C语言编译系统属于系统软件。） 4．√
四、简答题
1．程序设计语言的主要用途是什么？ 答：程序设计语言，也叫计算机语言，是人和计算机交流信息且计算机和人都能识别的语言，
是程序设计人员和计算机进行信息交流的工具。 2．简述程序设计的基本过程。
答：程序设计通常有5个步骤：程序说明、程序设计、编写代码、测试程序和程序定稿。
（1）程序说明：程序说明也称为程序分析，如明确要解决的问题，确定编程目标，定义想得到的输入/输出数据等。
（2）程序设计：使用程序设计方法设计一个问题和任务的执行方案。 （3）编写代码：使用计算机语言按照程序设计方案书写源程序。
（4）测试程序：通过编译系统调试源程序，发现程序的语法和逻辑错误并将其消除。 （5）程序定稿：最终程序文件由程序代码文件、程序说明书和用户操作手册等组成。程序代码文件和程序说明书便于以后程序的修改和维护。用户操作手册则使用户了解程序的使用以及正确输入数据。
3．算法和程序有什么相同之处，有什么不同之处？
答：算法是对解决问题步骤的描述。程序是用计算机语言编制的能完成特定的功能的代码。
相同：对问题的描述。不同：一个不可执行，一个可执行。 4．文档可以被计算机直接执行吗？它的主要用途是什么？
答：不能，文档的运行要靠应用程序来执行。文档的主要用途是存储用户数据。 5．简述程序的一般执行过程。
答：传统的计算机程序的执行可分为编辑、编译、连接和运行4个过程。（1）编辑：使用系
统提供的可用来编写文本文件的应用软件，即编辑程序，来编辑（创建）源程序文件，如C源程序文件。（2）编译：使用系统提供的可对源程序文件进行代码分析、代码生成和优化的软件，即编译程序，来编译上一步所编辑（创建）的源程序文件。（3）连接：使用系统提供的连接程序，将上一步编译后生成的目标程序代码文件与系统中提供的有关函数等链接起来，生成可执行程序文件。（4）运行：计算机运行可执行程序文件产生
10
计算结果。
6．什么叫时间复杂度？什么叫空间复杂度？ 答：时间复杂度是指一个算法中的语句执行次数。一个程序的空间复杂度是指运行完一个程
序所需内存的大小。
7．输入三个数，比较并输出最小值。要求：用自然语言描述算法。 答：开始：
S1 输入a，b，c；
S2 判断a>b? 是，进行S3，否，进行S4； S3 b?a；
S4 判断a>c? 是，进行S5，否则进行S6； S5 c?a； S6 输出a。
结束。
8．输入三个整数，使得输入的3个整数按大到小的顺序输出。
（1）用自然语言描述算法； （2）用流程图描述算法。
答：算法思想：将3个数两两比较，确定大小。按a、b、c顺序输入，最后按a、b、c顺序
输出，关键要找到最大值，将它赋值给a，中间值赋给b，最小值赋给c。 （1）用自然语言描述算法 开始：
第一步 输入3个整数a、b、c；
第二步 将a与b比较，并把小者赋给b，大的赋给a； 第三步 将a与c比较，并把小者赋给c，大的赋给a； 第四步 将b与c比较，并把小者赋给c，大的赋给b； 第五步 按顺序输出a，b，c。 结束。
（2）用流程图描述算法，如图6.1所示。
开始输入a，b，c是对应的流程图b＞a?否t=a,a=b,b=t是c＞a?否t=a,a=c,c=t是c＞b?否t=b,b=c,c=t输入a，b，c结束
图6.1 流程图描述算法
11
第7章 数据结构与常用算法习题
一、 单项选择题
1~5 BCDDC
6~10 CCCAB
二、填空题
1．非线性结构
2．线性结构，树形结构和图形结构 3．数据元素 数据元素 4．相邻 5．n/2
6．队尾 队头 7．线性结构 8．31 32 9．比较 交换 10．350
（解题技巧：根据完全二叉树的定义，可推论出：完全二叉树的节点的度要么是0，要么是2，要么最多只有一个节点的度为1。且根据性质3，可知：n0+n1+n==700，n0=n2+1。如果没有节点的度为1，那么n0+n2=2n0-1=700，则n0无解；所以必须有一个节点的度为1，那么n0+n2=2n0-1=699，则n0=350。） 11．DEBFCA 12．[log2n]+1 13．1 3 14．双亲 15．n-1 1
16．左右孩子结点的指针 双亲
三、 判断改错题
1. ×（改正：按“先进后出”原则组织数据的数据结构是栈。） 2. √ 3. √
4. ×（改正：某二叉树有n个度为2的节点，则该二叉树中的叶子结点数为n+1。 5. ×（改正：树中所有节点的度之和等于所有结点数加1。）
四、 简答题
1．数据的逻辑结构包含哪些？
答：线性结构，树形结构，图形结构或网状结构 2．线性结构应满足的两个条件是什么？ 答：①所有数据元素的信息；
②各数据元素之间存在一个对一个的关系。 3．非空线性表的结构特征是什么？
答：①存在唯一的一个被称为“第一个”的数据元素；
②存在唯一的一个被称为“最后一个”的数据元素；
③除了第一个之外，表中的每个数据元素均只有一个前驱； ④除了最后一个之外，表中的每个数据元素均只有一个后继。 4．什么是链式存储结构？
12
答：使用指针表示数据元素之间的逻辑关系，各个数据元素的存储位置可以随意，逻辑上相邻的数据元素，不要求在物理位置上也相邻。 5．栈和队列的基本特点是什么？
答：栈：先进后出 队列：先进先出
6．在循环队列中，仅根据头尾指针相等无法判断队列空或满。要解决这个问题应该采取什么方法？
答：通常还需增加一个标志s，s值的定义如下：
?0,表示队列空 s??1, 表示队列非空? 当头尾指针相等，且s=0时，表示队列空；当头尾指针相等，且s=1时，表示队列满。
7．由3个节点构成的二叉树，共有多少种不同的形态？ 答：5
8．常用的数据查找方法有哪些？ 答：顺序查找和折半查找
9．一组记录的关键字为(49, 38, 65, 97, 76, 13, 27, 49)，写出分别按冒泡排序、直接选择排序和简单插入排序的每一趟的排序结果。 答： 冒泡排序：
第1趟：38 49 65 76 13 27 49 97 第2趟：38 49 65 13 27 49 76 97 第3趟：38 49 13 27 49 65 76 97 第4趟：38 13 27 49 49 65 76 97 第5趟：13 27 38 49 49 65 76 97 第6趟：13 27 38 49 49 65 76 97 直接选择排序：
第1趟：13 38 65 97 76 49 27 49 第2趟：13 27 65 97 76 49 38 49 第3趟：13 27 38 97 76 49 65 49 第4趟：13 27 38 49 76 97 65 49 第5趟：13 27 38 49 49 97 65 76 第6趟：13 27 38 49 49 65 97 76 第7趟：13 27 38 49 49 65 76 97
简单插入排序：
第1趟：38 49 65 97 76 13 27 49 第2趟：38 49 65 97 76 13 27 49 第3趟：38 49 65 97 76 13 27 49 第4趟：38 49 65 76 97 13 27 49 第5趟：13 38 49 65 76 97 27 49 第6趟：13 27 38 49 65 76 97 49 第7趟：13 27 38 49 49 65 76 97 10．分别简述冒泡排序、直接选择排序和简单插入排序的基本思想。
答：冒泡排序：从前往后对数据进行多次扫描，在每一次扫描过程中，比较相邻两个元素的
大小。若相邻两个元素中前面的元素大于后面的元素，则将它们互换。
直接选择排序：扫描整个序列，从中选出最小的元素，将它交换到序列的最前面；然后对剩下的序列采用同样的方法，直到序列空为止。
13