二级公共基础知识

《二级公共基础知识》由会员分享，可在线阅读，更多相关《二级公共基础知识（56页珍藏版）》请在装配图网上搜索。

1、鬼华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099全国计算机二级c语言上机基本就考南开 100题，考试分填空、 改错、编程题3种题型，其中，填空与改错各30分，编程题考40分， 同学们只要把这100题掌握透了。通过上机考试肯定没有问题。全国计算机三级（包括网络技术、数据库技术、信息管理技术） 上机基本就考南开100题，考试考一道函数编程题，同学们只要把这 100题掌握透了。通过上机考试也肯定没有问题。另为了让更多的同学顺利通过等级考试，华夏培训在线录制了二 级c语言教程（适合二三级零基础考生）、二级c语言上机包过教程、 三级网络技术上机包过教程，其下 载网址如下：二级c语言

2、上机包过教程下 载如下：http:/www.hxpxzx.eom/a/gb2312/xiazaizho ngxi n/2011/0128/89.html三级网络技术上机包过教程下载如下：http:/www.hxpxzx.cOm/a/gb2312/xiazaizho ngxi n/2011/0128/91.html二级c语言零基础 入门教程下载如下：http:/www.hxpxzx.eom/a/gb2312/jisuanjide ngji/2011/0129/98.html这套教程有什么神奇之处呢？1. 教你分门别类解题！对题库从抽题、题目分析，再到具体语句 逐条敲入、编译，查看结果等所有步骤进

3、行了全程录象，与真实考试 环境一致！2. 告诉你最通俗的解题方法，可以帮助你最大 程度的少走弯路， 本教程解题思路绝对比市面 上出版的教程解题方法通俗易懂易记！（非 常适合零基础同学 或考前冲刺热身用）这套原创视频自2010年录制已来，已让近千人顺利通过了等考， 并真正步入了编程的大门。华夏培训在线教程 推广期间推出“分享日志，免费赠送教程配套 模拟软件活动”，活动方法如下，转载（ ）日志一次并 将内送QQ好友后，发转载截图至华夏培训在线邮 箱hxpxzx，就可获得模拟软件一份，该模拟软件 基本可100% 命中上机考题，一盘在手，考试无忧！。最后欢迎同学加入全国计算机二三级上机 交流群：652

4、03099,加 群之前需转发日志一次，假如你有问题也 可以在笔者新开设的新浪博好消息！华夏培训在线录有史上最通俗易懂的全国计算机二级C语言教程、二级 C语言上机包过教程、三级网络技术上机包过教程（含数据库技术、信息管理技术），该教程基本可100%命中对应上机试题，同学可到华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容发送给30个QQ好友就客上留言 ，祝你等考路上一路顺风!可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri

5、 1.1算法一、 算法的基本概念算法:是指解题方案的准确而完整 的描述。 算法不等于 程序，也不等计算方法，程序可以作为算法 的一种描述。（算法也可以用流程图、专门的描述语言、自然语言来描述。）1、算法的基本特征:（1 ）可行性，针对实际问题而设计的算法，执行后能够得 到满意的结果。（2）确定性，算法中每一步骤都必须 有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能 在有限的时间内做完，即能在执行有限个步骤后 终止，包括合理的执行时 间的含义；（4）拥有足够的情报，要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法 才最有效的；而当提供的情报不够时，

6、算法可能无效。2、算法的基本要素算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。（1）算法中对数据的 运算和操作：在计算机系统中，基本的运算和操作有以下4类： 算术运算：主要包括加、减、乘、除等运算； 逻辑运算：主要包括“与”、“或”、“非”等运算； 关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； 数据传输：主要包括赋值、输入、输出等操作。（2 ）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺 序、选择、循环3种基本控制结构组合而成。3、算法设计的基本方

7、法（1）列举法列举法的基本思想是，根据提岀的问题，列举所有可能的情况，并用问题中给定的条件检验哪些 是需 要的，哪些是不需要的。（2）归纳法归纳就是通过观察一些简单而特殊的情况，最后总结岀一般性的结论。（3）递推递推是指从已知的初始条件岀发，逐次推岀所要求的各中间结果和最后结果。（4）递归人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分 解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是 当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。（5

8、）减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。（6）回溯法在工程上，有些实际问题很难归纳岀一组简单的递推公式或直观的求解步骤，并且也不能进行无限的 列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿 着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。 华夏培训在线 提供计算机二级 公共基础知识、二级c语言真题、二级c语言上机 真题、二级c语言笔 试真题、二级c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术 笔

9、试真题、 三级网络技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南二、算法的复杂度算法复杂度：算法时间复杂度和算法空间复杂度。1、算法的时间复杂度算法的时间复杂度，是指执行 算法所需要的计算 工作量。（不直接衡量时间）算法的工作量用算法所执行的基本运算次数来度量，只依赖于问题的规模，它是问题的规模函数。即： 算法的工作量=f（ n）（1）平均性态（平均时间复杂度）所谓平均性态是指各种特定输入下的基本 运算次数的加权平均值来度量算法的工作量。（2）最坏情况复杂性所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。2、算法的空间

10、复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。包括算法程序占用的空间、输入数据所占用 的空间及算法执行过程中所需要的额外空间。1.2数据结构的基本概念数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：（丨）数据集合中个数据元素之间所 固有的逻辑关系，即数据的逻辑结构；（2 ）在对数据 元素进行处理时，各数据元素在计算机中的 存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。讨论以上问题的目的是为了提高数据处理的效率，即:（丨）提高数据处理的速度；（2）尽量节省在数据处理过程中所占用的计算机 存储空间。一、什么是数据结构数据结构是指反映数据元素之间的关系的数据元素集合

11、的表示，包括数据的逻辑结构和储存结构。1、数据的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系 的数据结构。一个数据的逻辑结构应包含以下两方面信息：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。可以用二元关系表示为：B=（ D，R）其中B表示数据结构，D表示数据元素的集合，R表示D中各数据元素之间的前后关系。例：一年四季的数据结构可以表示为：B=（ D，R）D=春，夏，秋，冬R=（春夏），（夏，秋），（秋，冬）例：家庭成员的数据结构可以表示为：B=（ D，R）D=父亲，儿子，女儿R=（父亲，儿子），（父亲，女儿）数据的逻辑结构包括集合、线形结构、树形结构和图 好消息！华夏

12、培训在线录有史上最通俗易懂的全国计算机二级形结构四种。C语言教程、二级 C语言上机包过教程、三级网络技术上机包过教程（含数据库技术、信息管理技术），该教程基本可100%命中对应上机试题，同学可到华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容发送给30个QQ好友就可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 2、数据的存储结构数据的存储结构是指数据的逻辑结构在计算机存储空间种的存放形式。常用的存储结构有顺序、链接、

13、索引等存储结构。一种数据的逻辑结构根据需要可以表示成多种存储结构，一种存储结构也可以表示多种逻辑结构。二、数据结构的图形表示例：一年四季数据结构的图形表示方框表示数据元素值，称为结点；有向线段从前件结点指向后件结点，表示为各数据元素之间的前后 件关系。没有前件的结点称为根结点；没有后件的结点称为终端结点(也称为叶子结点)。三、线性结构与非线性结构线性结构：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。常见的线性结构有 线性表、栈、队列。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见的非线性结构有树、二叉树、 图等。线性结构与非线性结构都可以是空的数据结构。对于

14、空的数据结构，如果对该数据结构的运算是按线 性结构的规则来处理的，则属于线性结构；否则属于非线性结构。1 . 3线性表及顺序存储结构一、线性表的基本概念线性表是n ( n 0)个元素构成的有限序列(a1，a2，an)。非空线性表有如下一些结构特征：(1) 有且只有一个根结点al，它无前件；(2) 有且只有一个终端结点an，它无后件；(3) 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结 点的个数n称为线性表的长度。当n=0时称为空表。二、线性表的顺序存储结构线性表的顺序表指的是用一组地址连续 的存储单元依次存储 线性表的数据元素。a1a2a3ai-1aian

15、线性表的顺序存储结构具备如下两个基本特征：(1) 线性表中的所有元素所占的存储空间是连续的；(2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表第i个元素ai的存储位置为华夏培训在线 提供计算机二级 公共基础知识、二级c语言真题、二级c语言上机 真题、二级c语言笔 试真题、二级c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术 笔试真题、 三级网络技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南ADR (ai) =ADR (al) + (i-1 ) x k ( K表示每个元素占用的字节

16、数)线性表的顺序存储结构是一种随机存取的存储结构。在线性表的顺序存储结构下，可以对线性表做的运算：插入、删除、查找、排序、分解、合并、复制、逆转。三、顺序表的插入运算线性表的插入运算是指在表的第i (1 i n+l)个位置上，插入一个新结点x,使长度为n的线性表(al, ，ai-1 , ai, ，an)变成长度为n+1的线性表(al，ai-1，x， ai，an)插入运算的基本步骤是：将结点，an各后移一位以便腾岀第i个位置；将x置入该空位； 表长加1。算法分析： 合法的插入位置共n+1个，即第1个位置到到第n+1个位置。 最坏情况是插入到第1个位置，共需要移动n个元素。 最好情况是插入到第n+

17、1个位置，不需要移动元素。 在插入位置等概率情况下，平均移动元素的个数为：(n + ( n - 1) + ( n -2) + 2 + 1+0 ) / ( n+1) =n / 2。 在第i个位置上插入需要移动n-i+1次。四、顺序表的删除运算线性表的删除运算是指将表的第i (1 ifront 时 为 rear-front 当s=0时，为零。 当 rear=front 且 s=1 时，为 m。 当 rearvfront 时 为 m- （front - rear）循环队列主要有两种基本运算：入 队运算和退队运算入队运算：指在循环队列的队尾加入一个新元素，首先rear=rear+1，当rear=m+1

18、时，置rear=1，然后 将新元素插入到队尾指针指向的位置。当S=1，rear=fro nt，说明队列已满，不能进行入队运算，称为“上 溢”退队运算：指在循环队列的排头位置 退岀一个元素并赋给指定 的变量。首先front=front+1，并当 front=m+1时，置front=1，然后将排头指针指向的元素赋给指定的变量。当循环队列为空S=0，不能进行 退队运算，这种情况成为“下溢”。1 . 5线性链表一、线性单链表的基本概念1、线性链表单链表数据域 指针域华夏培EADAhttpWwW.hxpxZl提供啊算机二级 公共基础知识、二级c语言真题JnUlL语言上机 真题、二级c语言笔 试真题、二级

19、c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术 笔试真题、 三级网络技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南开100题、二级c语言南开100题以及二级c语言上机软件、二级 c语言教程、三级网络技术教程免费下载 。PDF 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri 宠华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099单链表不同于顺序表，链表的各结点占用的存储空间之间可以是连续的，也可以是不连续的。因此链 表中结

20、点的逻辑次序和物理次序不一定 相同，通过 指针来反映结点之间的逻辑关系。head0 a1aian可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 宠华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 宠华臺培训在线欢迎加入全国计算机二三级 C上机交流群：652030992、带链的栈anan-1:topaiNULL可免费获取本软件，详情查询：PD

21、F 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 宠华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099链表的头指针就是 链栈的栈顶指针，插入和删除操作都只能在栈顶进行。3、带链的队列带链的队列实际上是一个同时带有头指针和尾指针的带头结点的单链表，头指针front指向链队的头 结点，尾指针rear指向链队的尾结点。an NULLrearfront链队一般不会岀现队满的情况。二、线性链表的基本运算1、在线性链表中查找指定元素在线性链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能 从链

22、表的头指针出发，顺链域Next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机 存取结构。在链表中，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的 存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x作比较。2、线性链表的插入线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到ai-1，与ai之间。因此，我 们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*q，并令结点，p的指针域指向新 结点，新结点的指针域指向结点ai* p

23、3、线性链表的删除x线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。三级网络技术上机包过教程（含数据库技术、信息管理技术）.Jz口 口 屯入 /| 十、 Jz口 口 1 ./|丿匕 厂I 人 J 十入 十、，该教程基本可100%命中对应上机试题，同学可到华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容发送给30个QQ好友就*3m ai可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 三、循环链表及其

24、基本运算在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而 线性单链表做不到这一点。由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从 而使空表的运算统一。顺序表与链表的比较顺序表的优缺点。优点： 空间利用率高。 可以实现随机存取。缺点： 插入、删除操作中要大量移动结点，时间性能差。 需要事先确定顺序表的大小，估计小了会发生溢岀现象，估计大了又将造成空间的浪费。 链表的优缺点。优点： 插入、删除操作中无需移动结点，时间性能好。 因为是动态分配存储空间，所以只要有空闲空间就不会发生溢岀现象。缺点：因为每个结点都要额外设置

25、指针域，因此空间利用率低。双链表：1 . 6树与二叉树一、树的定义树是由n ( n 0)个结点组成的有限集合。若n =0，称为空树；若n0，贝,(1) 有一个特定的称为根(root)的结点。它只有直接后件，但没有直接前件；(2) 除根结点以外的其他结点可以划分为m (m 0)个互不相交的有限集合TO，T1，Tm-1， 每个集合Ti (i=0，1，m-l)又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件, 但可以有0个或多个直接后件。ABCDE树型结构具有如下特点：(1) 每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树 的根；(2) 每一个结点可

26、以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点；(3) 一个结点所拥有的后件个数称为树的结点度；(4) 树的最大层次称为树的深度。华夏培训在线 提供计算机二级 公共基础知识、二级c语言真题、二级c语言上机 真题、二级c语言笔 试真题、二级c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术 笔试真题、 三级网络技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南叉树的定义及其基本性质1、什么是二叉树二叉树（binary tree）是由n （0）个结点的有限集合构成，此集合或者为空集，或者

27、由一个根结点 及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树 或空的右子树。二叉树不是树的特殊情况，它们是两个概念。（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有 序树（树为无序树），其子树的顺序不能颠倒。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点 既没有左子树也没有右子树时，该结点即是叶子结点）2、二叉树的基本性质性质1:在二叉树的第k层上至多有2k-1个结点（k

28、 1）。 性质2:深度为m的二叉树至多有2m-1个结点。012m-1 m2 + 2 + 2 + 2 =2 -1性质3:对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个 如果叶子结点n,度为2的结点数为n2，则n=n2+1。证明：设度为1的结点数目为n 1，二叉树的结点总数为n，有n=no + n1 + n2设m表示分支数，具有n个结点的二叉树的分支总数为n-1。则有m=n - 1而所有这些分支不是来自于 度为1的结点就是来自于 度为2的结点，即每一个度为1的结点发岀一个 分支，每一个度为2的结点发岀两个分支。于是有m=n1 + 2n2联立上面三个等式可以得到no=n2+1证

29、毕性质4：具有n个结点的二叉树的深度至少为log2n+ 1，其中log 2n表示log2n的整数部分。3、满二叉树与完全二叉树（l）满二叉树好消息！华夏培训在线录有史上最通俗易懂的全国计算机二级C语言教程、二级 C语言上机包过教程、三级网络技术上机包过教程（含数据库技术、信息管理技术），该教程基本可100%命中对应上机试题，同学可到华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容发送给30个QQ好友就可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:

30、/www.fi neprin 鬼华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099满二叉树：若二叉树中的结点，或者度为2 ,或者度为0，并且度为0的结点（叶结点）都集中在最 i-.- .i 下面一层，具有这种特点的二1叉树称为满二叉树。ABCHI J K L M N O深度为m的满二叉树有2m-i个结点，总结点数一定为奇数（2）完全二叉树完全二叉树：若二叉树中最多只有最下 面两层的结点的度可以小于2,并且最下面那一层的结点（叶 结点）从左到右依次紧密排列，这样的二叉树称为完全二叉树。满二叉树是完全二叉树，但完全二叉树不一定是满 二叉树。完全二叉树总结点数为n，若n为奇数，则叶

31、子结点数为（n+1）/2；若n为偶数，则叶子结点数为n/2性质5：具有n个结点的完全二叉树深度为log2n+ 1或log 2（ n+1）。性质6：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从 左到右），则对任一编号为k （ K k1，则其双亲是结点i/2;（2）如果2k n，则其左孩子是结点编号是2k，否则，结点k为叶子结点，无左孩子；华夏培训在线 提供计算机二级 公共基础知识、二级c语言真题、二级c语言上机 真题、二级c语言笔 试真题、二级c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术 笔试真题、 三级网络

32、技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南开100题、二级c语言南开100题以及二级c语言上机软件、二级 c语言教程、三级网络技术教程免费下载 。PDF 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri 鬼华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099（3）如果2k+1 n,则其右孩子是结点编号是2k+1 ;否则结点k无右孩子，4、二叉树的存储结构开100题、二级c语言南开100题以及二级c语言上机软件、二级 c语言教程、三级网络技术教程免费下载 。PDF

33、 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri 鬼华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099开100题、二级c语言南开100题以及二级c语言上机软件、二级 c语言教程、三级网络技术教程免费下载 。PDF 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri 鬼华臺培训在线欢迎加入全国计算机二三级 C上机交流群：65203099四、二叉树的遍历所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。1、前序遍历 （根左右）前序遍

34、历是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先 访问根结点，然后遍历左子树，最后遍历右子树。2、中序遍历（左根右）中序遍历是首先遍历左子树，然后访间根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然 先遍历左子树，然后访问根结点，最后遍历右子树。3、后序遍历一（左右根）后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然前序遍历的结果是 中序遍历的结果是 后序遍历的结果是先遍历左子树，然后遍历右子树，最后访问根结点FCADBEGHPACBDFEHGPABDCHPGEF好消息！华夏培训在线录有史上最通俗易懂的全国计算机二

35、级C语言教程、二级 C语言上机包过教程、三级网络技术上机包过教程（含数据库技术、信息管理技术），该教程基本可100%命中对应上机试题，同学可t连华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容 发送给30个QQ好友就可免费 获取本软件，详情查询:前序遍历的结果是：ABCDFGHE 中序遍历的结果是：BADGFHCE 后序遍历的结果是：BGHFDECA1 7查找技术一、顺序查找顺序表查找算法:从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等表示查 找成功，若表中所有元素与被查元素都不相等，则查找

36、失败。在查找成功时，最好的情况，查找长度为1;最坏的情况，查找长度为n；平均查找长度为（1+2+3+ +n） /n= （ n+1） /2。在两种情况下只能用顺序查找：线性表为无序表、链式存储结构的有序表二、二分法查找在长度为n的有序顺序表中查找x的过程：将x与中间项进行比较：若x等于中间项的值，查找成功，查找结束。若x小于中间项的值，则在中间项以前的部分以相同的方法进行查找；若x大于中间项的值，则在中间项以后的部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0 （说明线性表中没有这个元素）为止。例：对有序表(18， 20， 25， 34,48,62， 74， 85)用二分查找法

37、查找74,所需的比较次数为（A 1次B 2次C 3次D 4次【分析】第1趟：18202534+48627485+1low1mid1high第2趟：1820253448627485TTlowmidThigh第3趟：182025344862J85fmid1highlow【解答】Cl二分法查找只适用于顺序存储的有序表（从小到大）。l 对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。华夏培训在线 提供计算机二级 公共基础知识、二级c语言真题、二级c语言上机 真题、二级c语言笔 试真题、二级c语言上机题库、二级 c语言历年真题和计算机三级网络技术、三级网络技术 真题、三级网络技术

38、 笔试真题、 三级网络技术上机 真题、三级网络技术上机题库、三级数据库技术上机题库、三级信息管理技术上机题库、三级网络技术南开100题、二级c语言南开100题以及二级c语言上机软件、二级 c语言教程、三级网络技术教程免费下载 。PDF 文件以Fin ePri nt pdfFactory Pro试用版创建 http:/www.fi nepri 可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http

39、:/www.fi neprin 1 8排序技术一、交换类排序法冒泡排序与快速排序法属于交换类的排序方法1、冒泡排序法冒泡排序法的基本过程：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中， 前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两 相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有 的位置。然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个 元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描

40、过程中， 不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性 表中最小元素应有的位置。原始序列：第一遍（从前往后）（从后往前）第二遍（从前往后）（从后往前）对剩下的线性表重复上述过程，直到 剩下的线性表变空为止，此时的线性表已经变为有序。51731694286 1531674286 目 1 1 53267468 9 1 1 3 2 5 6 4 6 7 冋 9 10234566789假设线性表的长度为n，则在最坏的情况下，冒跑排序需要经过n/2遍的从前往后的扫描和n/2遍的从 后往前的扫描，需要的比较次数为n（ n-1）/22、快速排序法快速排序法的基本

41、思想如下：从线性表中选取一个元素，设为T,将线性表后面小于T的元素移到前面，而前面大于T的元素移到 后面，以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表 中的所有元素均不小于To如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直 做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。原始序列83406313843596573979611第1趟后：154063136135795739839684第2趟后：131563136135795739839684第3趟后：131539406135576379839684第4趟后：1315353

42、96140576379839684第5趟后：131535395740616379839684第6趟后：131535394057616379839684第7趟后：131535394057616379838496第7趟后没有长度大于1的未排子序列，排序结束。快速排序在最坏情况下时间复杂性：n（n-1）/2 ，最好情况为nlogzn。二、插入排序法1、简单插入排序法简单插入排序法思想：第i趟排序将序列的第i+1个数据元素插入到一个大小为i、并且已经按值有序好消息！华夏培训在线录有史上最通俗易懂的全国计算机二级C语言教程、二级 C语言上机包过教程、三级网络技术上机包过教程（含数据库技术、信息管理技术）

43、，该教程基本可100%命中对应上机试题，同学可到华夏培训在线官方网站直接在线免费听课并下载上机题库，华夏培训在线另将免费赠送与教程配套的上机考试软件，同学只要转发日志并将日志内容发送给30个QQ好友就可免费获取本软件，详情查询：PDF 文件以Fin ePri nt pdfFactory Pro试用版创建http:/www.fi neprin 宜华皐培训在线欢迎加入全国计算机二三级 C上机交流群：65203099的子序列的合适位置，得到一个大小为i+1、且仍然保持按值有序的子序列，这里i=1，2，3，n-1 o原始序列:51731694286第一遍15731694286第二遍1573169428

44、6第三遍13571694286对于具有n个数据元素的序列而言，插入排序法的总的排序趟数为n-1 o最坏情况下，元素之间的比较次数为n (n-1) /2,最好情况下(已经从小到大有序)，元素之间的比较次数为n-1。2、希尔排序法希尔排序法的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时, 进行一次插入排序，排序就完成。增量序列一般取ht=n/2 k例：下面是十二个数希尔排序的过程：h=6071924133108821844630529h=307182413050882194

45、463312911h=107050813182463192982314411 1 1 1 1 1 1结果：050708131819242931446382希尔排序的效率与所选取的增量序列有关。如果选取ht=n/2k，则在最坏情况下，希尔 排序所需要的比较次数为O (n 1.5)o - - - - - - - - - - - - - = - - - - - - - - *w*L L “ ” ” I r 宀=1 _ a - m i!j _ !n Q a _ 、L2、堆排序法堆排序对于较小规模的 线性表并不合适，但对于较大规模的线性表来说是很有效的。在最坏情况下， 堆排序需要比较的次数为O （nIo

46、g2n）。第二章程序设计基础2.1程序设计设计方法和风格当今主导的程序设计风格是“清晰第一，效率第二”的观点。如何形成良好的程序设计风格1、源程序文档化（1）符号名的命名：应具有一定的实际含义，以便于对程序功能的理解。（2）程序注释：正确注释能帮组读者理解程序。程序注释一般分为序言性注释和功能性注释。（3）视觉组织：利用空格、空行、缩进使得程序层次分明。2、数据说明的方法（1）数据说明的次序规范化。（2）说明语句中变量安排有序化。（3）使用注释来说明复杂数据的结构。3、语句的结构程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应注意如下: （1 ）在一行内只写一条语

47、句；（2 ）程序编写应优先考虑清晰性；（3）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二；（4）首先要保证程序正确，然后才要求提高，速度；（5）避免使用临时变量而使程序的可读性下降；（6）避免不必要的转移；（7）尽可能使用库函数；（8）避免采用复杂的条件：（9）尽量减少使用“否定”条件的条件语句；（10）数据结构要有利于程序的简化；（11）要模块化，使模块功能尽可能简单化；（12）利用信息隐蔽性，确保每一个模 块的独立性（13）从数据岀发去构造程序；（14）不要修补不好的程序，要重新编写；4、输入和输岀好消息！华夏培训在线录有史上最通俗易懂的全国计算机二级C语言教程、二级 C语言上机包过教程、