计算机二级考试公共基础知识.docx

计算机等级考试公共基础知识计算机二级考试公共基础知识□ 数据结构与算法□ 程序设计基础□ 软件工程基础□ 数据库设计基础计算机二级考试公共基础知识试卷分析一、基本数据结构与算法算法1 .算法的基本概念2 .算法复杂度的概念和意义算法的定义♦对解题方案准确而完整的描述称为算法.2.算法的基本特征一个算法应该具有以下五个重要的特征：♦算法与计算机程序算法—是一组逻辑步骤程序——用计算机语言描述的算法算法举例：n个数排序4 .算法的两个基本要素：5 ,算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：■时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量・空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分一、算法♦对解题方案准确而完整的描述称为算法算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

♦算法评价：■时间复杂度：执行这个算法所需要的计算工作量■空间复杂度：执行这个算法所需要的内存空间算法习题：(1)在计算机中，算法是指.A.查询方法 B.加工方法C.解题方案的准确而完整的描述 D.排序方法⑵下列叙述中正确的是（07年4月）A）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关（3）算法的有穷性是指（08年4月）A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用（4）算法的时问复杂度是指（2010年3月）A）算法的执行时间B）算法所处理的数据量算法程序中的语句或指令条数D）算法在执行过程中所需要的基本运算次数（5）算法的空间复杂度是指（09年9月）A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数（6）下列叙述中正确的是（06年9月）A） 一个算法的空间复杂度大，则其时间复杂度也必定大B） 一个算法的空间复杂度大，则其时间复杂度必定小C） 一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对二、数据结构计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率,并且节省计算机的存储空间，这是进行数据处理的关键问题。

二.数据结构♦1. 逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构.数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系例：1 .一年四季的数据结构B=（D,R）D=｛春，夏,秋，冬｝R=｛（春，夏）,（夏，秋）,（秋,冬）｝2 .家庭成员的数据结构B=（D,R）D={父亲，儿子，女儿}R={(父亲，儿子),(父亲，女儿)}♦常见的逻辑结构有：线性结构、树形结构和图形结构.2结构(^J理结构)计算机在实际进行薪据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同如：一年四季家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现常见的存储结构有：■ 顺序存储结构■ 链式存储结构■ 索引存储结构■ 3.数据的运算■ 检索■ 插入■ 删除■ 更新■ 排序常见的数据结构1.线性表(Linear List)线性表是由n (n^O)个数据元素a(, a2>•••> a a”组成的一个有限序列线性表的顺序存储结构顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。

顺序表的插入和删除运算♦ 顺序表的插入运算♦ 顺序表的删除运算线性表的链式存储结构♦ 线性表的链式存储结构称为线性链表♦ 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的各数据元素的先后关系是由各结点的指针域指示♦ 链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：应用举例i ** i '线性链表的存储结构设线性表为(a” a2» a)>山，as)线性链表的插入和删除运算♦ 单链表的插入运算♦ 单链表的删除运算双向链表的存储结构提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋双向链表可以克服单链表的单向性的缺点在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋线性表的存储结构有两种♦顺序存储结构2.栈和队列栈和队列都是特殊的线性表♦ 栈（Stack）及其基本运算♦ 队列（Queue）及其基本运算♦ 循环队列及其基本运算栈（Stack）是一种特殊的线性表其特点是插入和删除运算都只能性表的一端进行♦ 栈是按照“先进后出''或"后进先出”的原则组织数据的线性表♦ 栈的物理存储结构可以用顺序结构，也可以用链表结构。

♦ 下面讨论顺序存储结构中栈元素的插入和删除运算■顺序栈的进栈和出栈运算■栈的基本运算有三种：入栈、退栈和读栈顶元素队列（Queue）是一种特殊的线性表其特点是所有的插入都在表的一端进行，所有的删除运算都在表的另一端进行♦ 队列是按照“先进先出'’或"后进后出”的原则组织数据的线性表♦ 队列的物理存储结构可以用顺序结构，也可以用链式结构♦ 顺序队列的运算♦ 循环队列把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端♦ 循环队列的运算常见数据结构的逻辑结构♦ 线性表 线性结构♦ 栈 是特殊的线性表♦队列也是一种操作受限的特殊的线性表♦ 树（树型结构）是一种重要的非线形数据结构数据存储结构方面的考题1：数据的存储结构是指 （2005年4月）A）存储在外存中的数据 B）数据所占的存储空间量C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示2 .下列叙述中正确的是（2009年3月）A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3 .数据结构分为线性结构和非线性结构，带链的队列属于[ ].4 .下列数据结构中，属于非线性结构的是A）循环队列 B）带链队列C）二叉树 D）带链栈5.下列叙述中正确的是（）.（2008年9月）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间9.设某循环队列的容量为50,如果头指针front=45（指向队头元素的前一位置），尾指针 rear=10（指向队尾元素），则该循环队列中共有12】个元素。

2010年3月）♦线性结构与非线性结构线性表、栈和队列都是线性结构一个数据结构不是线性结构，则称其为非线性结构3.树与二叉树树型结构是一种重要的非线性结构♦ 树的概念♦ 二叉树的概念♦ 二叉树的存储♦ 二叉树的遍历树的概念♦ 树的定义：n个结点的有限集n>=0）树型结构的常用术语树型结构的常用术语二叉的定义：二叉树是一种有序的树形结构它与一般树形结构的区别是：♦ 每个结点最多有两棵子树；♦ 子树有左右之分，次序不能任意颠倒二叉树的性质【性质1】在二叉树的第i层上最多有2“个结点（i'l）【性质2】深度为h的二叉树最多有2L1个结点（h ND♦ 满二叉树：如果一个深度为h的二叉树拥有2勾1个结点，则将它称为满二叉树♦ 完全二叉树：有一棵深度为h,具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为l~n的结点位置一一对应，则称这棵二叉树为完全二叉树性质3】二叉树上叶子结点数比度为2的结点数多1【性质4】具有n个结点的完全二叉树的深度为Llog,(n+1)」其中，Llogzn」的结果是不大于 log2n的最大整数树型结构方面的考题1：在深度为7的满二叉树中，叶子结点的个数为(2006年4月)A)32 B)31 C)64 D)632：在深度为7的满二叉树中，度为2的结点个数为【】.(07年4月)3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为(07年9月)A)219 B)221 C)229 D)2314；某二叉树中度为2的结点有18个，则该二叉树中有」L个叶子结点。

2005年4月)5:一棵二叉树第六层(根结点为第一层)的结点数最多为【】今(2005年9月)二叉树的存储♦ 在计算机中，二叉树通常采用链式存储结构二叉树的遍历♦ 遍历指不重复地访问二叉树中的所有结点♦ 二叉树的遍历的次序与树型结构上的大多数运算有联系♦遍历的方式有三种(1)先(前)序遍历(DLR)(2)中序遍历(LDR)(3)后序遍历(LRD)二叉树的遍历♦ 遍历指不重复地访问二叉树中的所有结点1)先(前)序遍历(DLR)若二叉树为空，则结束遍历操作；否则■ 访问根结点；,先序遍历左子树；■ 先序遍历右子树2)中序遍历(LDR)若二叉树为空，则结束遍历操作；否则■ 中序遍历左子树；■ 访问根结点；■ 中序遍历右子树中序遍历的结果：EBAFHGCD(3)后序遍历(LRD)若二叉树为空，则结束遍历操作；否则■ 后序遍历左子树；■ 后序遍历右子树；■ 访问根结点后序遍历的结果：EBHGFDCA♦先序序歹ABDGCEFH♦中序序歹（J： DGBAECHF♦后序序列：GDBEHFCA1：设二叉树如下：（2010年3月）对该二叉树进行后序遍历的结果为【3】5.查找技术查找是数据处理的重要内容♦ 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。

♦ 若找到了满足条件的结点，称查找成功；否则称查找失败.♦ 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数♦ 通常根据不同的数据结构，采用不同的查找方法：■顺序查找■二分查找顺序查找♦线性表中最简单的查找方法♦方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。