三、 选择类排序法 １、 简单选择排序法
基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。
简单选择排序法在最坏情况下需要比较n(n-1)/2/次。 ２、 堆排序法 方法：（1）首先将一个无序序列建成堆。
（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆。反复做第（2）步，真到剩下的子序列为空为止。适用规模较大的线性表，在最坏情况下，堆排序需要比较的次数为O（nlog2n）。 1.7查找技术 一、顺序查找
顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
顺序查找的效率是很低的。以下两种情况只能采用顺序查找： 如果线性表无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 二、二分法查找
二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，但允许相邻元素值相等）。
设有序线性表的长度为n，被查元素为x，则对分查找的方法如下： 将x与线性表的中间项进行比较：
若中间项的值等于x，则说明查到，查找结束；
若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；
若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。 1.8排序技术
一、交换类排队序法
所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。 1、 冒泡排序法 基本过程如下：
首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。放最大值
然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序。放最小值。
重复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序。
假设线性表的长为n，则在最坏情况下，冒泡排序需要经过n/2遍的葱馨往后的扫描和n/2遍的从后往前的扫描，需要的比较的次数为n(n-1)/2。 2、 快速排序法
快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
基本思想如下：
从线性表中选取一个元素，设T，将线性表后面小于T的元素移到前，而前大于T的元素移支后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。
如此反复，则此时的线性表就变成了有序表。
步骤：首先，在表的第一个，中间一个与最后一个元素中选取中项，设为P（K），并将P（K）赋给T，再将表中的第一个元素移到P（K）的位置上。
然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：
（4） 将j逐渐减小，并逐次比较P（j）与T，直到发现一个P(j) （5） 将i逐渐减小，并逐次比较P（i）与T，直到发现一个P(i)>T为止，将P(i)移到P(j)位置上。 上述两个操作交替进行，直到指针i与j 指向同一个位置（即i=j）为止，此时将P(i)的位置上。 分割需要记忆，用栈来实现。 二、 插入类排序法 1、 简单插入排序法 所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。 一般来说，假设线性中前j-1元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下： 道德将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。效率与冒泡法相同 在最坏情况下，简单插入排序需要n(n-1)/2次比较。 2、 希尔排序法 基本思想如下： 将整个无序序列分割成若干小的子序列分别进行插入排序。 子序列的分割方法如下： 将相隔某个增量H的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当H减到1时，进行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,…[log2n],其中n为待排序序列的长度。 其效率与增量序列有关。在最坏情况下，需要的比较次数为O（Ｎ１.５）。 三、 选择类排序法 １、 简单选择排序法 基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。 简单选择排序法在最坏情况下需要比较n(n-1)/2/次。 ２、 堆排序法 方法：（1）首先将一个无序序列建成堆。 （2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆。反复做第（2）步，真到剩下的子序列为空为止。适用规模较大的线性表，在最坏情况下，堆排序需要比较的次数为O（nlog2n）。 习题一 一、选择题 1、算法的时间复杂度是指（ ） A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 2、算法的窨复杂度是指（ ） A、算法程序的长度 B、算法程序中的指令条数 C、算法程序所占的存储空间 D、算法执行过程中所需要的存储空间 3、下列叙述中正确的是（ ） A、线性表是线性结构 B、材与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构 4、数据的存储结构是指（ ） A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据 5、下列关于队列的叙述中正确的是（ ） A、在队列中只能插入数据 B、在队列中只能删除数据 C、队列是先进先出的线性表 D、队列是先进后出的线性表 6、下列关于栈的叙述中正确的是（ ） A、在栈中只能插入数据 B、在栈中只能删除数据 C、栈是先进先出的线性表 D、栈是先进后出的线性表 7、设有下列二叉树： 对此二叉树中序遍历的结果为 A、ABCDEF B、DBEAFC C、ABDECF D、DEBFCA 8、在深度为5的满二叉树中，叶子结点的个数为（ ） A、32 B、31 C、16 D、15 9、对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ ） A、 n+1 B、n C、(n+1)/2 D、n/2 10、设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点数为（ ） A、8 B、7 C、6 D、5 二、填空题 1、在长度为n 的有序线性表中进行二分查找，需要的比较次数为 。 2、设一棵完全二叉共有700个结点，则在该二叉树中有 个叶子结点。 3、设一棵二叉树中序遍历结果为DBEAFC ，前序遍历结果为ABDECF，则后序遍历结果为 。 4、在最坏情况下，冒泡排序的时间复杂度为 。 5、在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有 个元 第2章 程序设计基础 2．1 程序设计方法与风格 就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。 一般来讲。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应该强调得意和清晰，程序必须是可以理解的。 要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、 源程序文档化 2、 源程序文档化应考虑如下几点： （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结构化程序设计 一、结构化程序设计的原则 结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。 1、 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。 2、 逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。 3、 模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 4、 限制使用goto语句 使用goto语句经实验证实：（1）滥用GOTO语句确实有害，应昼避免； （2）完全避免使用GOTO语句也并非是个明智的方法，有些地方使用GOTO语句，会使程序流程更清楚、效率更高； （3）争论的焦点不应该放在是否取消GOTO语句，而应该放在用什么样的程序结构上。 其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。 二、结构化程序的基本结构与特点 1、顺序结构：顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序。 2、选择结构：选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。 3、重复结构：重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一
计算机二级公共基础知识
