计算机2级公共基础知识1

《计算机2级公共基础知识1》由会员分享，可在线阅读，更多相关《计算机2级公共基础知识1（43页珍藏版）》请在金锄头文库上搜索。

1、计算机等级考试 公共基础知识,第2页,计算机二级考试公共基础知识大纲,数据结构与算法程序设计基础软件工程基础数据库设计基础,这四个方面在试卷中出现的情况是：选择题10个（10分），总分值占到了试卷卷面分的10，是一个不小的比例。,第3页,算法 算法的基本概念2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,第4页,对解题方案准确而完整的描述称为算法。,算法是程序设计的核心, 算法的基本概念,2

2、. 算法的基本特征 一个算法应该具有以下五个重要的特征：,有穷性、 确定性、 可行性 有零个或多个输入、 有一个或多个输出,拥有足够的情报,第5页,3. 算法的两个基本要素：,基本运算和操作算术运算关系运算逻辑运算数据传输,控制结构 顺序选择循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法,第6页,4. 算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量 一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法

3、在执行过程中临时占用的存储空间,第7页,(1) 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性是指 (08年4月) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用,(c),(B),算法习题:,(A),(4)

4、 下列叙述中正确的是 (06年9月) A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 (5)算法分析的目的是 A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进,(D),(D),1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表、数组,栈、广义表,队列、串,树形结构,图形结构,数据结构的三个方面,

5、数据结构可描述为 Group=（D，R）,第10页,二. 数据结构,数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。,第11页,1. 逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例：1. 一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏) ,

6、(夏，秋),(秋，冬)2. 家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子) ,(父亲，女儿),B表示数据结构 D是数据元素的有限集 R是D上关系的有限集,第12页,常见的逻辑结构有： 线性结构、树形结构和图形结构。, 线性结构 结构中的每个元素之间存在一个对一个的关系； 树形结构 结构中的每个元素之间存在一个对多个的关系； 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。,第13页,2. 存储结构（物理结构）存储结构指数据结构在计算机存储空间中的具体实现。 常见的存储结构有：顺序存储结构链式存储结构索引存储结构,

7、一种数据结构可以根据需要表示成一种或多种存储结构。,第14|92页,常见的数据结构,数据结构分类： 线性结构与非线性结构两大类型,线性结构：一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。,常见的线性结构有：线性表、栈、队列、线性链表等,常见的非线性结构有:树、二叉树、图等,非线性结构：一个数据结构不是线性结构。,第15页,栈和队列,栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。栈（Stack）及其基本运算队列（Queue

8、）及其基本运算循环队列及其基本运算,第16页,1 .栈,栈是限定仅在表尾进行插入或删除操作的线性表。 栈顶表尾。 栈底表头。 空栈不含元素的空表。,进栈,出栈,栈s=(a1,a2,an),后进先出或先进后出（LIFO）,第17页,2、队列 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO）表。,先进先出后进后出（LIFO）,队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。,第18页,数据存储结构方面的考题,1：数据的存储结构是指 （2005年4月）A) 存储在外存中的数据 B) 数据所占的存储

9、空间量C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示 2. 下列叙述中正确的是 （2009年3月） A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3. 数据结构分为线性结构和非线性结构，带链的队列属于 。 4. 下列数据结构中，属于非线性结构的是 A）循环队列 B) 带链队列 C) 二叉树 D）带链栈,答案：D。,答案：D。,答案：线性结构。,答案：c,第19页,5.下列关于栈的叙述正确的是 （2008年4月） A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据

10、C）只能在栈底插入数据 D）不能删除数据,答案：B。,6. 一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（2010年3月）,答案：A，B，C，D，E，F，5，4，3，2，1,队列的特点：“先进先出”或“后进后出”。,7.栈和队列的共同特点是A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点8.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序9.栈底至栈顶依次存

11、放元素A、B、C、D，在第五个元素E入栈前， 栈中元素可以出栈，则出栈序列可能是A) ABCED B) DCBEA C) DBCEA D) CDABE,第21页,树型结构是一种重要的非线性结构。树的概念二叉树的概念二叉树的存储二叉树的遍历,树与二叉树,第22页,树的概念,树的定义：是一种简单的非线性结构。 n个结点的有限集。（n=0）,A,B,D,F,E,C,G,H,I,J,K,M,结点： 根结点：没有前件的结点，只有一个称为根结点。 简称树的根。 父结点：结点的前件称该结点的父结点。（相对而言）,A,只有一个结点的树,第23页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,

12、M,子结点：结点的后件，称为该结点的子结点。可以有多个。 叶子结点 没有后件的结点；Q：图中叶子结点有几个？ 结点的度 一个结点的子树的个数；(有几个分叉) Q：结点A、G的度数？ Q：度数为0、1、2、3的结点分别有几个？树的度 树中所有结点度的最大值；Q：右图中树的度？,7,3,2,7,1,2,2,3,第24页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推；Q：图中结点F的层次？树的深度 树中所有结点层次的最大值；Q：图中树的深度？,第25页,二叉树的概念,定义：二叉树是一种有序的树形结构。它与一般树

13、形结构的区别是：每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。称左子树和右子树,二叉树的5种基本形态,第26页,树与二叉树的区别,A树和二叉树的结点个数最少都可为0。 B树中结点的最大度数没有限制，二叉树结点最大度数为2。 C树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。,3个结点的树,3个结点的 二叉树,第27页,二叉树的性质,【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）,第28页,【性质2】深度为h的二叉树最多有2h -1个结点（h 1）,第29页,【性质3】二叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,第30页,满二叉树和完全二叉树

14、,满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。最后一层的结点均为0度。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。则称这棵二叉树为完全二叉树。完全二叉树中度数为1的结点的个数为0或1。,第31页,满二叉树,完全二叉树,12,13,8,9,10,11,4,5,6,7,1,2,3,第32页,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉树,深度为4的完全二叉树,8,4,5,6,7,1,2,3,第33页,【性质4】具有n个结点的完全二叉树的深度为 log2 (n+1) 其中，log2n 的结果是不大于log2n的最大整

15、数,深度为4的满二叉树,深度为4的完全二叉树,log2(8+1) = ln9/In2=4 log2 (15+ 1) =In16/In2=4,第34页,性质5：具有n个结点的完全二叉树的深度为,例：n=2 k=2n=6 k=3n=7 k=3n=8 k=4n=12 k=4,第35页,1：在深度为7的满二叉树中,叶子结点的个数为（2006年4月）A)32 B)31 C)64 D)63 2：在深度为7的满二叉树中，度为2的结点个数为【 】 。(07年4月）3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 （07年9月） A）219 B）221 C）229 D）2311.满二叉树的定义和【性质1】 在二叉树的第i层上最多有2i-1个结点。 2.【性质3】二叉树上叶子结点数比度为2的结点数多1。 3. “【性质3】二叉树上叶子结点数比度为2的结点数多1”和二叉树的定义。70+80+69（度为2的结点数）,