《计算机等级考试二级公共基础知识归纳(附真题2005[1][1].9-2011.3)课件》由会员分享，可在线阅读，更多相关《计算机等级考试二级公共基础知识归纳(附真题2005[1][1].9-2011.3)课件（94页珍藏版）》请在金锄头文库上搜索。
1、二级公共基础知识内容归纳,二级公共基础知识,第一章 数据结构与算法 第二章 程序设计基础 第三章 软件工程基础 第四章 数据库设计基础,第一章 数据结构与算法,数据结构 算法复杂度 线性结构与非线性结构 栈 队列 树与二叉树 查找与排序,数据结构,一般说来，数据结构分为逻辑结构和存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。循环队列属于存储结构。数据的逻辑结构有线性结构和非线性结构两大类。常用的存储表示方法有4种：顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置页相邻
2、的存储单元中。,（1）下列叙述中正确的是A) 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B) 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C) 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D) 上述三种说法都不对 2010.9,下列叙述中正确的是A)顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的B)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C)顺序存储结构能存储有续表，链式存储结构不能存储有序表D)链式存储结构比顺序存储结构节省存储空间 2008.9,(3) 线性表的存储结构主要分为顺序存储结构和链式存储结构.
3、队列是一种特殊的线性表,循环队列是队列的顺序存储结构.2007.9 （1）数据结构分为逻辑结构与存储结构，线性链表属于存储结构 。 2007.4 线性表是逻辑结构。 （5）数据结构分为逻辑结构和存储结构，循环队列属于 【存储】 结构。2005.9,（5）下列叙述中正确的是 A）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对 2007.9,（6）下列叙述中正确的是 A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C）程序设
4、计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 D）以上三种说法都不对 2007.9,（4）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 2005.9,算法复杂度,算法复杂度包括时间复杂度和空间复杂度。其中时间复杂度是指执行算法所需要的计算工作量。空间复杂度是算法所需空间的度量。,(2)算法的时间复杂度是指 A)算法的执行时间 B)算法所处理的数据量 C)算法
5、程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 2010.3 (4)算法的空间复杂度是指A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数2009.9,（7）下列叙述中正确的是_。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 2006.9 （2）算法复杂度主要包括时间复杂度和 【空间】 复杂度。 2005.9,线性与非线性结构,线性数据结构：队列，线性表，栈等等
6、。常用的结构数据模型有关系型、网状型和树型。,（2）下列叙述中正确的是A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构 2011.3 (1)下列数据结构中，属于非线性结构的是A)循环队列B)带链队列C)二叉树D)带链栈 2009.9 (2)支持子程序调用的数据结构是A)栈B)树C)队列D)二叉树 2009.3,栈,栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端叫做“栈顶”，不允许插入和删除的一端叫做“栈底”栈的修改只能在栈顶进行，按照后进先出的原则，具有记忆作用，对栈的插入与删除操作中
7、，不需要改变栈底指针。,（1）下列关于栈叙述正确的是A）栈顶元素最先能被删除B）栈顶元素最后才能被删除C）栈底元素永远不能被删除D）以上三种说法都不对 2011.3 （2）下列叙述中正确的是A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D）上述三种说法都不对 2010.9,在判断出栈元素时，栈底元素最后出栈。,（1）一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中
8、间退栈的元素)的顺序为【1DCBA2345】。2010.9 1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A)12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA 2008.9 （3）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 Ae3,e1,e4,e2 Be2,e4,e3,e1 Ce3,e4,e1,e2 D任意顺序 2007.4,(2)下列数据结构中,能够按照“先进后出”原则存取数据的是A)循环队列B)栈C)队列D)二叉树2009.9 .(1)下列叙述中正确的是A)栈是先
9、进先出的线性表B)队列是先进后出的线性表C)循环队列是非线性结构D)有序线性表即可以采用顺序存储结构,也可以采用链式存储结构 2009.3,1 假设一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有 20 个元素。 2009.3,4）按照“后进先出”原则组织数据的数据结构是A）队列B）栈C）双向链表D）二叉树 2006.45）下列叙述中正确的是A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构
10、2006.4,（3）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 2005.9,队列,队列是一种特殊的线性表，循环队列是队列的顺序存储结构。队列是限定了插入和删除操作的线性表。它只允许在表的一端进行插入操作（队尾），而在另外一端进行删除操作（队头），队列的修改可以在两端进行，按照先进先出的原则。,(1)一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为 【ABCD
11、EF54321】 。 2010.3 (2)设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有 【15】 个元素。2010.3 (3)设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有_24_个元素。2008.4 (3)对于循环队列，下列叙述中正确的是A)队头指针是固定不变的B)队头指针一定大于队尾指针C)队头指针一定小于队尾指针D)队头指针可以大于队尾指针,也可以小于队尾指针 09.9,2.下列叙述中正确的是A)循环队列有队头和队
12、尾两个指针，因此，循环队列是非线性结构B)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D)循环队列中元素的个数是由队头指针和队尾指针共同决定 2008.9,树形结构,树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。树是结点的集合，它的根结点数目是有且只有一个。树根结点没有前件。,（2）树是结点的集合，它的根结点数目是 A有且只有1 B1或多于1 C0或1 D至少2,二叉树是一种特殊树型结构，它的特点是每一个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。（一）在二叉树的第i层上至
13、多有2的i-1次方个结点；（二）深度为k的二叉树至多有2的k次方减1个结点；（三）对任何一棵二叉树T，如果其终端结点数为n1，度为2的结点数为n2，则n1=n2+1。（四）具有n个结点的完全二叉树的深度为k+1，其中k是log2n的整体部分。,（3）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二义树共有【25】个结点。2010.9 （1）某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有 【14】 个结点。2009.9 (3)某二叉树有5个读为2的结点,则该二叉树中的叶子结点数是A)10 B)8 C)6 D)4 2009.3 （8）一棵二叉树中共有70个叶子结点与80个
14、度为1的结点，则该二叉树中的总结点数为 A）219 B）221 C）229 D）231 2007.9,（3）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）A）3B）4C）6D）7 2011.3 (2)深度为5的满二叉树有16个叶子结点。2008.4 7）在深度为7的满二叉树中，叶子结点的个数为A）32 B）31C）64D）63 2006.4 （4）一棵二叉树第六层（根结点为第一层）的结点数最多为 【32】 个。2005.9,二叉树遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种： （1）前序遍历（DLR）：若二叉树为空，则
15、结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 （2）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。,（2）一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 【
16、2】 。 （1）已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为 AGEDHFBCA BDGEBHFCA CABCDEFGH DACBFEDHG 2007.4,(3)设二叉树如下：对该二叉树进行后序遍历的结果为 【3】 。2010.3,(01)对右例二叉树进行中序遍的结果是【1】 。2008.9,(4) 对下列二叉树进行中序遍历的结果为_4_ 2007.9 F / C E / A D G / / B H P,6）对如下二叉树 进行后序遍历的结果为A) ABCDEFB) DBEAFCC) ABDECFD) DEBFCA 2006.4,对长度为n的线性表，在最坏的情况下，快速排序需要的比较次数为n(n-1)/2;冒泡排序所需要的比较次数为n(n-1)/2；直接插入排序所需要的比较次数为n(n-1)/2；堆排序所需要的比较次数为O(nlog2n)。在待排序序列基本有序的情况下，采用插入排序所使用时间最少。对长度为n的线性表进行顺序查找，在最坏的情况下所需
