搜索
二级公共基础知识内容归纳二级公共基础知识•第一章数据结构与算法•第二章程序设计基础•第三章软件工程基础•第四章数据库设计基础第一章数据结构与算法•数据结构•算法复杂度•线性结构与非线性结构•栈•队列•树与二叉树•查找与排序数据结构一般说来，数据结构分为逻辑结构和存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。循环队列属于存储结构。数据的逻辑结构有线性结构和非线性结构两大类。常用的存储表示方法有4种：顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置页相邻的存储单元中。•（1）下列叙述中正确的是A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D)上述三种说法都不对2010.9•下列叙述中正确的是A)顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的B)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C)顺序存储结构能存储有续表，链式存储结构不能存储有序表D)链式存储结构比顺序存储结构节省存储空间2008.9•(3)线性表的存储结构主要分为顺序存储结构和链式存储结构.队列是一种特殊的线性表,循环队列是队列的顺序存储结构.2007.9•（1）数据结构分为逻辑结构与存储结构，线性链表属于存储结构。2007.4•线性表是逻辑结构。•（5）数据结构分为逻辑结构和存储结构，循环队列属于【存储】结构。2005.9•（5）下列叙述中正确的是•A）程序执行的效率与数据的存储结构密切相关•B）程序执行的效率只取决于程序的控制结构•C）程序执行的效率只取决于所处理的数据量•D）以上三种说法都不对2007.9•（6）下列叙述中正确的是•A）数据的逻辑结构与存储结构必定是一一对应的•B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构•C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构•D）以上三种说法都不对2007.9•（4）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率2005.9算法复杂度•算法复杂度包括时间复杂度和空间复杂度。其中时间复杂度是指执行算法所需要的计算工作量。空间复杂度是算法所需空间的度量。•(2)算法的时间复杂度是指•A)算法的执行时间•B)算法所处理的数据量•C)算法程序中的语句或指令条数•D)算法在执行过程中所需要的基本运算次数2010.3•(4)算法的空间复杂度是指A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数2009.9•（7）下列叙述中正确的是________。•A）一个算法的空间复杂度大，则其时间复杂度也必定大•B）一个算法的空间复杂度大，则其时间复杂度必定小•C）一个算法的时间复杂度大，则其空间复杂度必定小•D）上述三种说法都不对2006.9•（2）算法复杂度主要包括时间复杂度和【空间】复杂度。2005.9线性与非线性结构•线性数据结构：队列，线性表，栈等等。常用的结构数据模型有关系型、网状型和树型。•（2）下列叙述中正确的是A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构2011.3•(1)下列数据结构中，属于非线性结构的是A)循环队列B)带链队列C)二叉树D)带链栈2009.9•(2)支持子程序调用的数据结构是A)栈B)树C)队列D)二叉树2009.3栈•栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端叫做“栈顶”，不允许插入和删除的一端叫做“栈底”栈的修改只能在栈顶进行，按照后进先出的原则，具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。•（1）下列关于栈叙述正确的是A）栈顶元素最先能被删除B）栈顶元素最后才能被删除C）栈底元素永远不能被删除D）以上三种说法都不对2011.3•（2）下列叙述中正确的是A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D）上述三种说法都不对2010.9在判断出栈元素时，栈底元素最后出栈。•（1）一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素)的顺序为【1DCBA2345】。2010.9•1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A)12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA2008.9•（3）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A．e3,e1,e4,e2B．e2,e4,e3,e1C．e3,e4,e1,e2D．任意顺序2007.4•(2)下列数据结构中,能够按照“先进后出”原则存取数据的是A)循环队列B)栈C)队列D)二叉树2009.9•.(1)下列叙述中正确的是A)栈是先进先出的线性表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）只有根结点的二叉树是线性结构2006.4•（3）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2005.9队列•队列是一种特殊的线性表，循环队列是队列的顺序存储结构。队列是限定了插入和删除操作的线性表。它只允许在表的一端进行插入操作（队尾），而在另外一端进行删除操作（队头），队列的修改可以在两端进行，按照先进先出的原则。•(1)一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为【ABCDEF54321】。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)循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D)循环队列中元素的个数是由队头指针和队尾指针共同决定2008.9树形结构•树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。树是结点的集合，它的根结点数目是有且只有一个。树根结点没有前件。•（2）树是结点的集合，它的根结点数目是A．有且只有1B．1或多于1C．0或1D．至少2•二叉树是一种特殊树型结构，它的特点是每一个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。（一）在二叉树的第i层上至多有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)10B)8C)6D)42009.3•（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A）219B）221C）229D）2312007.9•（3）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）A）3B）4C）6D）72011.3•(2)深度为5的满二叉树有16个叶子结点。2008.4•7）在深度为7的满二叉树中，叶子结点的个数为A）32B）31C）64D）632006.4•（4）一棵二叉树第六层（根结点为第一层）的结点数最多为【32】个。2005.9二叉树遍历•二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：•（1）前序遍历（DLR）：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。•（2）中序遍历（LDR）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历（LRD）：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。•（2）一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为【2】。•（1）已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为A．GEDHFBCAB．DGEBHFCAC．ABCDEFGHD．ACBFEDHG2007.4•(3)设二叉树如下：对该二叉树进行后序遍历的结果为【3】。2010.3•(01)对右例二叉树进行中序遍的结果是【1】。2008.9ABCDEFXYZ•(4)对下列二叉树进行中序遍历的结果为_[4]_______2007.9•F•/\•CE•/\\•ADG•//\•BHP•6）对如下二叉树•进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA2006.4•对长度为n的线性表，在最坏的情况下，快速排序需要的比较次数为n(n-1)/2;冒泡排序所需要的比较次数为n(n-1)/2；直接插入排序所需要的比较次数为n(n-1)/2；堆排序所需要的比较次数为O(nlog2n)。在待排序序列基本有序的情况下，采用插入排序所使用时间最少。对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数为n。•（1）有序线性表能进行二分查找的前提是该线性表必须是【顺序】存储的。2011.3•（2）在长度为n的线性表中，寻找最大项至少需要比较【【log2n】】次。2010.9•(1)下列叙述中正确的是•A)对长度为n的有序链