《公共基础_1_c语言_考点冲刺》由会员分享，可在线阅读，更多相关《公共基础_1_c语言_考点冲刺（38页珍藏版）》请在金锄头文库上搜索。
1、公共基础知识,基本数据结构与算法,新航线培训中心 http:/,考点1 -算法,一、算法基本概念算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述，它是指令的有限序列，使得给定类型的问题通过有限的指令序列，在有限的时间内被求解。 1.算法的基本特性 有穷性即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。,新航线培训中心 http:/,考点1 -算法,确定性算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。 可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差 。
2、,新航线培训中心 http:/,考点1 -算法,输入和输出（拥有足够的情报）算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。,新航线培训中心 http:/,考点1 -算法,二、算法复杂度 算法的时间复杂度算法的空间复杂度,新航线培训中心 http:/,练习,算法的时间复杂度是指A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数,参考答案：C【解析】 算法的复杂度主要包括算法的时间复杂度和空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量,即算法
3、执行过程中所需要的基本运算的次数;算法的空间复杂度一般是指执行这个算法所需要的内存空间。,新航线培训中心 http:/,练习,算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)执行算法需要的内存空间,参考答案：D【解析】 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度是指执行这个算法所需要的内存空间。,新航线培训中心 http:/,考点2 数据结构的基本概念,一、什么是数据结构1 数据结构的定义数据结构是指互相之间存在着一种或多种关系的数据元素的集合。,数据元素是数据
4、的基本单位，即数据集合中的个体。数据元素亦称节点或记录。有时一个数据元数可由若干数据项组成。数据项是数据的最小单位。,数据元素,新航线培训中心 http:/,2 数据的逻辑结构 是指反映数据元素之间的逻辑关系的数据结构。 数据的逻辑结构有两个要素： 数据元素的集合，记作D 数据之间的前后关系，记作R 则数据结构B=（D，R）,考点2 数据结构的基本概念,新航线培训中心 http:/,考点2 数据结构的基本概念,3 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。,新航
5、线培训中心 http:/,考点2 数据结构的基本概念,二、线性结构与非线性结构,A , B , C , ，X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,线性结构,新航线培训中心 http:/,考点2 数据结构的基本概念,非线性结构（图形结构）,新航线培训中心 http:/,考点2 数据结构的基本概念,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),新航线培训中心 http:/,练习,数据结构作为计算机的一门
6、学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及 _.A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储,参考答案：A【解析】 数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题:数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;对各种数据结构进行的运算。,新航线培训中心 http:/,考点4 栈和队列,一、栈,进栈出栈(先进后出),栈顶,栈底,新航线培训中心 http:/,练习,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是A)AB
7、CED B)DCBEA C)DBCEA D)CDABE,参考答案：B【解析】 栈操作原则上“后进先出“,栈底至栈顶依次存放元素A、B、C、D,则表明这4个元素中D是最后进栈,B、C处于中间,A最早进栈,所以出栈时一定是先出D,再出C,最后出A。,新航线培训中心 http:/,考点4 栈和队列,队列 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。 特点：先进先出,a1，a2,a3,a4an-1,an,队 列 示 意 图,队头,队尾,新航线培训中心 http:/,考点4 栈和队列,循环队列：就是将队列存储空间最后一个位置绕到第一个位置，形成逻辑上的环状空间，
8、供队列循环使用。 循环队列中实际元素个数： （Rear - Front +N） mod N ，其中 Rear为队尾，Front为队头 N 为循环队列最多可以存放元素个数，mod为取余运算,设某循环列队的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_个元素,（10-45+50）%50 =15,新航线培训中心 http:/,考点5 线性链表,线性表的链式存储结构称为线性链表。,链式存储结构,线性链表表示法:,新航线培训中心 http:/,考点6 树与二叉树,一、树的基本概念由一个或多个结点组成的有限集合。仅有一个根结点，
9、结点间有明显的层次结构关系。,新航线培训中心 http:/,考点6 树与二叉树,结点：树中的元素，包含数据项及若干指向其子树的分支。 结点的度：结点拥有的子树数。 叶子：度为零的结点，也称终端结点。 结点的层次：从根结点开始算起，根为第一层。 深度： 树中结点的最大层次数。,4,新航线培训中心 http:/,考点6 树与二叉树,二、二叉树及其基本性质 二叉树是另一种树型结构，它的特点是每个结点最多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。,特别要注意：二叉树不是树的特殊情况。,a,a,b,b,两棵不同的二叉树,新航线培训中心 http:/
10、,满二叉树,特点：每一层上都含有最大结点数。,考点6 树与二叉树,新航线培训中心 http:/,完全二叉树,特点：除最后一层外，每一层都取最大结点数， 最后一层结点都集中在该层最左边的若干位置。,考点6 树与二叉树,新航线培训中心 http:/,A、 二叉树的第i层上至多有2 i-1（i 1）个结点。,二叉树的基本性质,第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。,考点6 树与二叉树,新航线培训中心 http:/,A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为k的二叉树中至多含有2k-1个结点。,二叉树的基本性质,此树的深度k=
11、4，共有24-1=15个节点。,考点6 树与二叉树,新航线培训中心 http:/,A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为k的二叉树中至多含有2k-1个结点。 C、 若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1,二叉树的基本性质,n0=8 n2=7,考点6 树与二叉树,新航线培训中心 http:/,A、二叉树的第i层上至多有2 i-1（i 1）个结点。 B、深度为k的二叉树中至多含有2k-1个结点。 C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1 D、 具有n个结点的二叉树，其深度至少为lo
12、g2n+1，其中log2n表示取log2n的整数部分。,二叉树的基本性质,考点6 树与二叉树,新航线培训中心 http:/,二叉树遍历定义及遍历算法遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。,考点6 树与二叉树,遍历算法 （1）前（先）序遍历：首选访问根结点，然后遍历左子树，最后遍历右子树。 （2）中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。 （3）后序遍历：首选遍历左子树，然后遍历右子树，最后访问根结点。,新航线培训中心 http:/,遍历算法,先序遍历：D L R 中序遍历：L D R 后序遍历：L R D,A,D,B,C,T1,T2,T3,D L R,
13、以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,考点6 树与二叉树,新航线培训中心 http:/,练习,若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca,参考答案：D【解析】 前序遍历的第一个结点a为树的根节点;中序遍历中a的左边的结点为a的左子树,a的右边的结点为a的右子树;再分别对a的左右子树进行上述两步处理,直到每个结点都找到正确的位置。,新航线培训中心 http:/,练习,已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 A)acbed B)decab C)deabc D)cedba,参考答案：D【解析】 依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成,右子树为空;又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成。,新航线培训中心 http:/,考点7 查找技术,二分法查找,查找23的过程如下图：,mid=(low+high)/2取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),
