[IT认证]二级公共基础课件8.ppt
《[IT认证]二级公共基础课件8.ppt》由会员分享,可在线阅读,更多相关《[IT认证]二级公共基础课件8.ppt(226页珍藏版)》请在三一办公上搜索。
1、,二,级,公,共,基,础,考试简介,考试简介,0,0,数据结构,数据结构,1,1,本章内容,1.1 算法基本特征,可行性,确定性,有穷性,足够的情报,行,定,穷,情,在设计一个算法时,必须考虑它的可行性,算法中的每个步骤必须是明确定义的,不允许模棱两可,算法必须在有限的时间内做完,执行有限个步骤后终止,是指算法要有一定的输入数据和必须要有输出结果,算法:是指解题方案的准确而完整的描述。,1,1.1 算法基本特征,2008.4算法的有穷性是指A)算法程序的运行时间是有限的B)算法程序所处理的数据是有限的C)算法程序的长度是有限的D)算法只能被有限的用户使用,算法的空间复杂度:是指执行算法所需要的
2、内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间。,算法的时间复杂度:是指执行算法所需要的计算工作量,可以用算法所执行的基本运算次数度量。工作量=f(n)n是问题的规模,1.2 时间和空间复杂度,1,1.2 时间和空间复杂度,2010.3算法的时间复杂度是指 A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数,2,1.2 时间和空间复杂度,2009.9算法的空间复杂度是指 A)算法在执行过程中所需要的计算机存储空间 B)算法在执行过程中所需要的临时工作单元数 C)算法所处理的数据量 D)算法程序中的语句或指
3、令条数,3,1.2 时间和空间复杂度,2011.9下列叙述中正确的是 A)算法就是程序 B)设计算法时只需要考虑数据结构的设计 C)设计算法时只需要考虑结果的可靠性 D)以上三种说法都不对,4,1.2 时间和空间复杂度,2006.9下列叙述中正确的是 A)一个算法的空间复杂度大,时间复杂度必定大 B)一个算法的空间复杂度大,时间复杂度必定小 C)一个算法的时间复杂度大,空间复杂度必定小 D)以上三种说法都不对,2 数据结构,数据结构:是指相互有关联的数据元素的集合。数据结构的研究目的:节省时间、节省空间。,线性结构:线性表,栈,队列非线性结构:树,图,顺序存储链式存储,插入,删除,查找,排序,
4、数据的逻辑结构包含两个要素:数据元素的集合,记为 D D中各数据元素之间的前后件关系,记为 R 数据结构 B 表示为:B=(D,R),D=di|1=i=6=d1,d2,d3,d4,d5,d6,R=(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6),2 数据的逻辑结构,数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。一种数据结构的逻辑结构根据需要可以表示成多种存储结构。采用不同的存储结构,其数据处理的效率是不同的。,顺序存储,链式存储,2 数据的存储结构,1,2 数据结构,2005.4数据的存储结构是指 A)存储在外存中的数据 B)数据所占的存储空间量
5、C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示,2,2 数据结构,2007.4下列叙述中正确的是 A)算法的效率只与问题的规模有关,与数据的存储结构无关 B)数据的逻辑结构与存储结构是一一对应的 C)算法的时间复杂度与空间复杂度一定相关 D)算法的时间复杂度是指执行算法所需要的计算工作量,3,2 数据结构,2007.9下列叙述中正确的是 A)程序执行的效率与数据的存储结构密切相关 B)程序执行的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对,线性结构(线性表):有且只有一个根结点,它无前件 有且只有一个终端(叶子)结点,它无后
6、件 除根结点和叶子结点外,其他结点有且只有一个前件,也有且只有一个后件,非线性结构:,3.1 线性与非线性结构,线性表链式存储结构,双向链表,线性表顺序存储结构,3.2 线性表,5,9,2,6,1,1,5,9,2,6,后移,插入,4,3.3 顺序线性表的插入,1,3.3 顺序线性表的删除,2012.3在长度为 n 的顺序存储的线性表中删除一个元素,最坏情况下需要移动表中的元素个数为。,n-1,顺序查找:对于长度为 n 的线性表,平均要进行n/2 次比较,在最坏情况下进行 n 次比较。,顺序查找适用于无序表或链式线性表(不管无序还是有序)。,3.4 顺序查找,1,3.4 顺序查找,2006.9在
7、长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为 A)63B)64 C)6D)7,求极值:对于长度为 n 的线性表,要比较 n-1 次。,3.5 求极值,1,3.5 求极值,2010.9在长度为n的线性表中,寻找最大项至少需要比较 次。,n-1,二分查找:适用于顺序存储的有序表,对长度为 n 的线性表,在最坏情况下进行 log2n 次比较。,注意:即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。,3.6 二分查找,1,3.6 二分查找,2011.3有序线性表能进行二分查找的前提是该线性表必须是 存储的。,顺序,2,3.6 二分查找,2005.9下列数据结构中,能用二分
8、法查找的是 A)顺序存储的有序线性表 B)线性链表 C)二叉链表 D)有序线性链表,3,3.6 二分查找,2005.42008.92010.3在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是 A)O(n)B)O(n2)C)O(log2n)D)O(n log2n),线性链表:即线性表的链式存储结构。在线性链表中,各数据结点的存储空间可以不连续,各数据元素的存储顺序与逻辑顺序可以不一致。,3.7 线性链表,在线性链表中进行插入与删除,不需要移动链表中的元素。,3.7 线性链表的操作,1,3.7 线性链表,2010.9下列叙述中正确的是 A)线性表的链式存储结构与顺序存储结构所需要的
9、存储空间是相同的 B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D)上述三种说法都不对,2,3.7 线性链表,2005.42011.9关于线性链表的叙述,正确的是 A)各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致 B)各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续 C)进行插入与删除时,不需要移动表中的元素 D)以上三种说法都不对,nlog2n,nlog2n,堆 排 序,n(n-1)/2,n(n-1)/2,选择排序,选择类,n1.5,nlog2n,希尔排序,n(n-1)/
10、2,n(n-1)/2,插入排序,插入类,n(n-1)/2,n(n-1)/2,快速排序,n(n-1)/2,n(n-1)/2,冒泡排序,交换类,最坏情况,平均时间,排 序,3.8 排序,1,3.8 排序,2009.3下列排序中最坏情况下比较次数最少的是 A)冒泡排序B)简单选择排序 C)直接插入排序D)堆排序,2,3.8 排序,2008.4对长度n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是 A)快速排序B)冒泡排序 C)直接插入排序D)堆排序,3,3.8 排序,2005.42007.9冒泡排序在最坏情况下的比较次数是 A)n(n-1)/2B)nlog2n C)n(n+1)
11、/2D)n/2,4,3.8 排序,2006.4对长度为10的线性表进行冒泡排序,在最坏的情况下需要进行比较的次数为。,45,栈是限定在一端进行插入和删除的线性表。原则是:先进后出(或后进先出)。栈具有记忆功能。,栈底指针 bottom,栈顶指针 top,栈空 top=0,入栈,栈满,出栈,0,4 栈,1,4 栈,2008.9一个栈的初始状态为空。首先将元素1、2、3、A、B、C依次入栈,然后再依次出栈,则元素出栈的顺序为:。,CBA321,2,4 栈,2010.9一个栈的初始状态为空。首先将元素5、4、3、2、1 依次入栈,然后退栈一次,再将元素A、B、C、D依次入栈,之后将所有元素全部退栈,
12、则所有元素退栈(包括中间退栈的元素)的顺序为:。,1DCBA2345,3,4 栈,2011.3下列关于栈叙述正确的是 A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除 C)栈底元素永远不能被删除 D)以上三种说法都不对,4,4 栈,2008.4下列关于栈的叙述正确的是 A)栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C)只能在栈底插入数据 D)不能删除数据,5,4 栈,2005.9下列关于栈的描述正确的是 A)在栈中只能插入元素而不能删除元素 B)在栈中只能删除元素而不能插入元素 C)栈是特殊的线性表,只能在一端插入删除元素 D)栈是特殊的线性表,只能在一端插入元素,而在另一端
13、删除元素,6,4 栈,2010.9下列叙述中正确的是 A)在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化 B)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化 C)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化 D)上述三种说法都不对,7,4 栈,2009.3用长度为50的数组(元素的下标从0到49)作为栈的存储空间,指针bottom和top分别指向栈底和栈顶元素,如果bottom=49,top=30(数组下标),则栈中有 个元素。,20,8,4 栈,2009.3支持子程序调用的数据结构是 A)栈B)树 C)队列D)二叉树,队列是指允许在一端进行插入,而在另一端进行删除
14、的线性表。原则是:先进先出(或后进后出)。,队头指针 front,队尾指针 rear,入队,出队,5.1 队列,1,5.1 队列,2006.42007.42009.9下列对队列的叙述正确的是 A)队列属于非线性表 B)队列按“先进后出”原则组织数据 C)队列在队尾删除数据 D)队列按“先进先出”原则组织数据,2,5.1 队列,2010.3一个队列的初始状态为空。现将A、B、C、3、2、1 依次入队,然后依次退队,则元素退队的顺序为:。,ABC321,5.2 循环队列,入队(%求余)rear=(rear+1)%6,队满 s=1 入队后rear=front,出队,队空 s=0 出队后rear=fr
15、ont,循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间。,利用模运算,计算循环队列元素个数方法:,若frontrear元素个数=n-(front-rear)其中n是循环队列的容量。,1,5.2 循环队列,2009.9对于循环队列,叙述正确的是 A)队头指针是固定不变的 B)队头指针一定大于队尾指针 C)队头指针一定小于队尾指针 D)队头指针可以大于,也可以小于队尾指针,2,5.2 循环队列,2008.42010.32012.3设某循环队列容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有 个元
16、素。,15,3,5.2 循环队列,2008.9下列叙述中正确的是 A)循环队列有队头和队尾两个指针,因此,循环队列是非线性结构 B)在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况 C)在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况 D)循环队列中元素的个数是由队头指针和队尾指针共同决定,常用术语 父结点、子结点 根结点、叶子结点 结点的度、树的度 树的深度 子树,树是 n(n 0)个元素的有限集合。它有且仅有一个称为根的元素;其余元素是互不相交的子树。,6.1 树,非空二叉树只有一个根结点,每个结点最多有两棵子树,分别称为左子树和右子树。,在二叉树的第 k 层上,最
17、多有 2k-1 个结点;深度为 m 的二叉树最多 有 2m-1 个结点;度为 0 的结点(叶子)比度为 2 的结点多一个;有 n 个结点的二叉树深 度至少为 log2n+1。,6.2 二叉树,1,6.2 二叉树,2005.42007.42009.32011.9某二叉树有5个度为2的结点,则该二叉树中的叶子结点数为。,6,2,6.2 二叉树,2009.92010.9某二叉树有10个度为1的结点,7个度为2的结点,则该二叉树共有 个结点。,25,3,6.2 二叉树,2007.9某二叉树有70个叶子结点,80个度为1的结点,则该二叉树共有 个结点。,219,4,6.2 二叉树,2012.3某二叉树共
18、25个结点,其中5个是叶子结点,则度为1的结点数为。,16,5,6.2 二叉树,2011.3某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(根结点在第1层)。,7,完全二叉树:只缺少最后一层右边的若干结点。,满二叉树:每一层上的结点数均达到最大值。,1,2,6.3 特殊二叉树,1,6.3 满二叉树,2006.42007.42008.4深度为5的满二叉树叶子结点个数为。,16,2,6.3 满二叉树,2005.9一棵二叉树第6层(根结点为第1层)的结点数最多为。,32,前序遍历:访问根结点 前序遍历左子树 前序遍历右子树,中序遍历:中序遍历左子树 访问根结点 中序遍历右子树,后序遍
19、历:后序遍历左子树 后序遍历右子树 访问根结点,ABDGECF,DGBEAFC,GDEBFCA,1,2,3,6.5 二叉树的遍历,1,6.5 二叉树的遍历,2010.3对右图二叉树进行后序遍历的结果为。,EDBGHFCA,2,6.5 二叉树的遍历,2007.4对右图二叉树前序遍历的结果为 A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ,3,6.5 二叉树的遍历,2007.92008.9对右图二叉树中序遍历的结果为。,DBXEAYFZC,4,6.5 二叉树的遍历,2011.3二叉树的中序遍历结果为:DBEAFC,前序遍历结果为:ABDECF,则后序
20、遍历结果为。,DEBFCA,链式存储,链式存储,带链的队列,带链的栈,线性链表,链式存储,运算,存储结构,遍历,-,二叉树,-,-,树,非线性结构,入队、退队,循环队列,队列,入栈、出栈,一维数组,栈,插入、删除查找、排序,顺序表,线性表,线性结构,顺序存储,逻辑结构,数据结构,7 数据结构,1,7 数据结构,2006.92011.9数据结构分为线性结构与非线性结构,带链的栈属于。,线性结构,2,7 数据结构,2005.9数据结构分为逻辑结构和存储结构,循环队列属于。,存储结构,3,7 数据结构,2008.9下列叙述中正确的是 A)线性链表是线性表的链式存储结构 B)栈与队列是非线性结构 C)
21、双向链表是非线性结构 D)只有根结点的二叉树是线性结构,4,7 数据结构,2011.3下列叙述中正确的是 A)有一个以上根结点的数据结构不一定是非线性结构 B)只有一个根结点的数据结构不一定是线性结构 C)循环链表是非线性结构 D)双向链表是非线性结构,5,7 数据结构,2009.9下列数据结构中,属于非线性结构的是 A)循环队列B)带链队列 C)二叉树D)带链栈,6,7 数据结构,2007.92012.3线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种线性表。循环队列是队列的 存储结构。,顺序,7,7 数据结构,2009.32012.3下列叙述中正确的是 A)栈是“先进先出”的
22、线性表 B)队列是“先进后出”的线性表 C)循环队列是非线性结构 D)有序线性表既可以采用顺序存储结构,也可以采用链式存储结构,8,7 数据结构,2007.9下列叙述中正确的是 A)数据的逻辑结构与存储结构必定是一一对应的 B)由于计算机存储空间是向量式的存储结构,因此数据的存储结构一定是线性结构 C)程序设计语言中的数组一般是顺序存储结构,因此,利用数组只能处理线性结构 D)以上三种说法都不对,9,7 数据结构,2008.9下列叙述中正确的是 A)顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的 B)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构 C)顺序存储结
23、构能存储有序表,链式存储结构不能存储有序表 D)链式存储结构比顺序存储结构节省存储空间,10,7 数据结构,2005.9下列叙述中正确的是 A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可能有多种存储结构,且各种存储结构影响数据处理的效率 D)一个逻辑数据结构可能有多种存储结构,各种存储结构不影响数据处理的效率,2,程序设计,程序设计,2,本章内容,程序设计风格是指编写程序时所表现出的特点和逻辑思想。它会深刻影响软件的质量和可维护性。,符号命名,要有含义,序言功能,应加注释,空格缩进,容易分析,数据说明,规范次序,效率第二,
24、清晰第一,保证正确,提高效率,功能单一,信息隐蔽,输入数据,给出提示,合法检查,结束标志,限用goto,模块独立,1 程序设计风格,1,1 程序设计风格,2007.9下列不符合良好程序设计风格的是 A)程序的效率第一,清晰第二 B)程序的可读性好 C)程序中要有必要的注释 D)输入数据前要有提示信息,2,1 程序设计风格,2006.9下列不符合良好程序设计风格的是 A)源程序要文档化 B)数据说明的次序要规范化 C)避免滥用goto语句 D)模块设计要保证高耦合、高内聚,结构化程序设计常采用顺序、选择(分支)和循环三种基本结构。,2 结构化程序设计,条件,条件,顺序,分支,循环,自顶向下,逐步
25、求精,模块化,限用goto,先考虑总体,后考虑细节;先考虑全局目标,后考虑局部目标,对复杂问题,先设计一个目标作为过渡,然后逐步细化,把程序要解决的总目标分解为一个一个的模块,限制使用goto语句,程序的质量与goto语句数量成反比,2 结构化程序设计,1,2 结构化程序设计,2009.32010.9仅由顺序、选择(分支)和循环结构构成的程序是 程序。,结构化,2,2 结构化程序设计,2006.42008.42009.9下列选项中不属于结构化程序设计原则的是 A)可封装B)自顶向下 C)模块化D)逐步求精,3.1 面向对象的程序设计,属性年龄学历,方法吃饭购物,属性年龄:18学历:大学,方法吃
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- IT认证 IT 认证 二级 公共 基础 课件
链接地址:https://www.31ppt.com/p-4593927.html