R)decab C)deabc D)cedba 3.链表不具有的特点是( A)不必事先估计存储空间 B)可随机访问任一元素 ) 所需空间与线性 算法的时间复杂度是指( A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令 5. A)队列 B)循环队列 C)栈 D)师序表 6。数据结构中，与所使用的计算机无关的是数据的() A)存储结构 B)物理结构 C)逻辑结构 D)物理和存储结构 下列数据结构中， 按先进后出原则组织数据的是() A)线性链表 B)栈 C)循环链表 D)顺序表 8.线性表L=(a1,a2,a3,ai,an,下列说法正确的是（) A)每个元素都有 ·个直接前件和直接后件 B)线性表中至少要有一个元素 C)表中诸元素的排列顺序必须是由小到大或由大到小 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接 后件 由两个栈共享一个存储空间的好处是( A)减少存取时间，降低下溢发生的机号 B)节省存储空间，降低上溢发生的机率 C)减少存取时间，降低上滋发生的机南 D)节省存储空间，降低下溢发生的机率 10.树是结点的集合， 的根结点数目是() A)有且只有1 12.B)1或多于1 13.C)0或1 14.D)至少2
26 B）decab C）deabc D）cedba 3. 链表不具有的特点是( ) A）不必事先估计存储空间 B）可随机访问任一元素 C）插入删除不需要移动元素 D）所需空间与线性表长度成正比 4. 算法的时间复杂度是指( ) A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 5. 下列数据结构具有记忆功能的是（ ） A）队列 B）循环队列 C）栈 D）顺序表 6. 数据结构中，与所使用的计算机无关的是数据的（ ） A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构 7. 下列数据结构中，按先进后出原则组织数据的是（ ） A）线性链表 B）栈 C）循环链表 D）顺序表 8. 线性表 L＝（a1,a2,a3,.ai,.an），下列说法正确的是（ ） A）每个元素都有一个直接前件和直接后件 B）线性表中至少要有一个元素 C）表中诸元素的排列顺序必须是由小到大或由大到小 D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接 后件 9. 由两个栈共享一个存储空间的好处是（ ） A）减少存取时间，降低下溢发生的机率 B）节省存储空间，降低上溢发生的机率 C）减少存取时间，降低上溢发生的机率 D）节省存储空间，降低下溢发生的机率 10. 树是结点的集合，它的根结点数目是（ ） 11. A）有且只有 1 12. B）1 或多于 1 13. C）0 或 1 14. D）至少 2
二、填空题 1、算法的基本特征是可行性、确定性。 和拥有足够的情报。 2、在深度为5的满二叉树中，叶子结点的个数为 3、最简单的交换排序方法是 4、设一棵二叉树中有3个叶子结点，8个度为1的结点，则该二叉树中总的结点数为 5、对于输入为N个数进行快速排序算法的平均时间复杂度是 第2章程序设计基础 自从世界上第一台电子计算机诞生开始，特别是近20年来计算机技术的飞速发展与 泛应用己远远超出人们对它的预料。计算机的应用也日益普及和深入，并逐步渗透到人类生 活的各个领域，以致于有些不了解计算机的人把它看得非常神秘。其实计算机只不过是一种 具有一定存储能力、在程序控制下自动工作的电子设备。所以要使计算机发挥巨大的作用， 就必须为它编写种类不同的程序，而为了能使计算机识别这些程序，就需要有一种特定的编 程语言，它是人与计算机进行信息交流的工具。 2.1程序设计风格与方法 就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计 之
27 二、填空题 1、算法的基本特征是可行性、确定性、 和拥有足够的情报。 2、在深度为 5 的满二叉树中，叶子结点的个数为 3、最简单的交换排序方法是 4、设一棵二叉树中有 3 个叶子结点，8 个度为 1 的结点，则该二叉树中总的结点数为 5、对于输入为 N 个数进行快速排序算法的平均时间复杂度是 第 2 章 程序设计基础 自从世界上第一台电子计算机诞生开始，特别是近 20 年来计算机技术的飞速发展与广 泛应用已远远超出人们对它的预料。计算机的应用也日益普及和深入，并逐步渗透到人类生 活的各个领域，以致于有些不了解计算机的人把它看得非常神秘。其实计算机只不过是一种 具有一定存储能力、在程序控制下自动工作的电子设备。所以要使计算机发挥巨大的作用， 就必须为它编写种类不同的程序，而为了能使计算机识别这些程序，就需要有一种特定的编 程语言，它是人与计算机进行信息交流的工具。 2.1 程序设计风格与方法 就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计
阶段。一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是 由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体 而言应该强调得意和清晰， 程序必须是可以理解的 要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、源程序文档化 源程序文档化应考虑如下几点： (1)符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解 (2)程序注有 克的注释能 多帮助读者理解程序 (3)视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧 使程序层次清晰。 2、数据说明的方法 在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。 般应注意如下几点： (☑)数据说明的次序规范化鉴于程序理解、阅读和维护的需要，使数据说明次序固定， 可以使数据的发生容易查找，也有利于测试、排错和维护。 (2)说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺 序为好。 (3)使用注释来说明复杂数据的结构。 3 语句的结构 程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般 应注意如下： （1)在一行内只写一条语句： (2)程序绵写应代先考虑洁渐性 (3)除非对效率有特殊要求，程序编写要做清晰第一，效率第二： (4)首先要保证程序正确，然后才要求提高速度： (5)避免使用临时变量而使程序的可读性下降： (6)避免不必要的转移： (7)尽可能使用库函数 (8)避免采用复杂的条件语句 (9)尽量减少使用 否定”条件的条件语句 (10)数据结构要有利于程序的简化： (11)要模块化，使模块功能尽可能单一化： (12)利用信息隐敲，确保每一个模块的独立性： (13)从数据出发去构造程序： (14)不要修补不好的程序，要重新编写 4、输入和输出 无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应 该考虑如下原则： (1)对所有的输入数据都要检拾验数据的合法性 (2)检查输入项的各种重要组合的合理性 (3)输入格式要简单，以使得输入的步骤和操作尽可能简单 (4)输入数据时，应允许使用自由格式： (5)应允许缺省值： (6)输入一批数据时，最好使用输入结束标志
28 阶段。一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是 由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体 而言应该强调得意和清晰，程序必须是可以理解的。 要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、源程序文档化 源程序文档化应考虑如下几点： （1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。 （2）程序注释：下克的注释能够帮助读者理解程序。 （3）视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧 使程序层次清晰。 2、数据说明的方法 在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。 一般应注意如下几点： （1）数据说明的次序规范化鉴于程序理解、阅读和维护的需要，使数据说明次序固定， 可以使数据的发生容易查找，也有利于测试、排错和维护。 （2）说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺 序为好。 （3）使用注释来说明复杂数据的结构。 3、 语句的结构 程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般 应注意如下： （1）在一行内只写一条语句； （2）程序编写应优先考虑清晰性； （3）除非对效率有特殊要求，程序编写要做清晰第一，效率第二； （4）首先要保证程序正确，然后才要求提高速度； （5）避免使用临时变量而使程序的可读性下降； （6）避免不必要的转移； （7）尽可能使用库函数； （8）避免采用复杂的条件语句； （9）尽量减少使用“否定”条件的条件语句； （10）数据结构要有利于程序的简化； （11）要模块化，使模块功能尽可能单一化； （12）利用信息隐蔽，确保每一个模块的独立性； （13）从数据出发去构造程序； （14）不要修补不好的程序，要重新编写； 4、输入和输出 无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应 该考虑如下原则： （1）对所有的输入数据都要检验数据的合法性； （2）检查输入项的各种重要组合的合理性； （3）输入格式要简单，以使得输入的步骤和操作尽可能简单； （4）输入数据时，应允许使用自由格式； （5）应允许缺省值； （6）输入一批数据时，最好使用输入结束标志；
(7)在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请 求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。 (8)当程 设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性 给所有的输入出加注释，并设计输出报表格式。 2.2结构化程序设计 2.2.1结构化程序设计的原则 结构化程序设计方法的主要原则可以概括为自项向下，逐步求精，模块化，限制使用 got0语句。 牛、皮先者忠作，后专店细：先移忠全同阳标后专志局寄目素不 开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。 2、逐步求精 对复杂问题，应设计一些子目标作过渡，逐步细化。 3、横块化 个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解 为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 4、限制使用got0语句 使用g0t0语句经实验证实： (1)激用G0TO语句确实有害，应昼群免： (2)完全避免使用G0T0语句也并非是个明智的方法，有些地方使用G0T0语句，会使 程序流程更清楚、效率更高： (3)争论的焦点不应该放在是否取消G0T0语句，而应该放在用什么样的程序结构上。 其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。 2.2.2结构化程序的基本结构与特点 1、顺序结构 顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照 程序语句行的自然顺序，一条语句一条语句地执行程序程序。如图21所示
29 （7）在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请 求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。 （8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性； 给所有的输入出加注释，并设计输出报表格式。 2.2 结构化程序设计 2.2.1 结构化程序设计的原则 结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用 goto 语句。 1、自顶向下 程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一 开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。 2、逐步求精 对复杂问题，应设计一些子目标作过渡，逐步细化。 3、模块化 一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解 为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 4、限制使用 goto 语句 使用 goto 语句经实验证实： （1）滥用 GOTO 语句确实有害，应昼避免； （2）完全避免使用 GOTO 语句也并非是个明智的方法，有些地方使用 GOTO 语句，会使 程序流程更清楚、效率更高； （3）争论的焦点不应该放在是否取消 GOTO 语句，而应该放在用什么样的程序结构上。 其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。 2.2.2 结构化程序的基本结构与特点 1、 顺序结构 顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照 程序语句行的自然顺序，一条语句一条语句地执行程序程序。如图 2-1 所示
图2-1顺序结构 图2-2选择结构 2、选择结构 选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定 的条件，判断应该选择哪一条分支来执行相应的语句序列。如图22所示。 3、重复结构 重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类 似的程序段，利用重复结构可简化大量的程序行。分为两类： (1)当型循环结构：先判断后执行，程序易于理解、使用和维护：如图2-3所示。 (2)直到型循环结构：先执行后判断，编程工作的效率，降低软件开发成本。如图24 所示。 子 图2-3当型循环结构 图2-4直到型循环结构 2.2.3结构化程序设计原则和方法的应用 要注意把握如下要素： ()使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 ②用的控制结构只准许有一个入口和 一个出口 (3)程序语句组成容易识别的块，每块只有一个入口和一个出口： ()复杂结构应该嵌套的基本控制结构进行组合嵌套来实现： (⑤)语言中所没有的控制结构，应该采用前后一致的方法来模拟： (6)严格控制G0O语句的使用。其意思是指： ①用一个非结构化的程序设计语言去实现一个结构化的构造 ②若不使用G0I0语句会使功能模糊：
30 2、选择结构 选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定 的条件，判断应该选择哪一条分支来执行相应的语句序列。如图 2-2 所示。 3、重复结构 重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类 似的程序段，利用重复结构可简化大量的程序行。分为两类： （1）当型循环结构：先判断后执行，程序易于理解、使用和维护；如图 2-3 所示。 （2）直到型循环结构：先执行后判断，编程工作的效率，降低软件开发成本。如图 2-4 所示。 2.2.3 结构化程序设计原则和方法的应用 要注意把握如下要素： ⑴使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 ⑵选用的控制结构只准许有一个入口和一个出口； ⑶程序语句组成容易识别的块，每块只有一个入口和一个出口； ⑷复杂结构应该嵌套的基本控制结构进行组合嵌套来实现； ⑸语言中所没有的控制结构，应该采用前后一致的方法来模拟； ⑹严格控制 GOTO 语句的使用。其意思是指： ①用一个非结构化的程序设计语言去实现一个结构化的构造； ②若不使用 GOTO 语句会使功能模糊； 真 假 真 假 图 2-3 当型循环结构 图 2-4 直到型循环结构 A B A B 真 假 图 2-1 顺序结构 图 2-2 选择结构