计算机公共基础知识Ever计算机笔试---公共基础知识计算机二级考试公共基础知识大纲一、数据结构与算法二、程序设计基础三、软件工程基础四、数据库设计基础计算机二级考试公共基础知识试卷分析数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术一、基本数据结构与算法算法⒈算法的基本概念2.算法复杂度的概念和意义对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。在计算机中，算法是指______。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是（07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指(08年4月)A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(4)算法的时问复杂度是指(2010年3月)A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指(09年9月)A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是(06年9月)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对1：数据的存储结构是指（2005年4月）A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示2.下列叙述中正确的是（2009年3月）A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构数据结构分为线性结构和非线性结构，带链的队列属于[线性结构]。4.下列数据结构中，属于非线性结构的是A）循环队列B)带链队列C)二叉树D）带链栈5。下列叙述中正确的是（）。（2008年9月）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间6。下列关于栈的叙述正确的是（2008年4月）A）栈按“先进先出”组织数据B)栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为【A，B，C，D，E，F，5，4，3，2，1】。（2010年3月）假设用一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【19】个元素。（2009年3月）设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有【15】个元素。（2010年3月）1：在深度为7的满二叉树中,叶子结点的个数为（2006年4月）A)32B)31C)64D)632：在深度为7的满二叉树中，度为2的结点个数为【63】。(07年4月）3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（07年9月）A）219B）221C）229D）2314：某4二叉树中度为2的结点有18个，则该二叉树中有【19】个叶子结点。（2005年4月）5：一棵二叉树第六层（根结点为第一层）的结点数最多为【32】个（2005年9月）A1:设二叉树如下：（2010年3月）对该二叉树进行后序遍历的结果为【】EDBGHFCABCFDEGH2:对如下二叉树（2006年4月）进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA(1)对于长度为n的线性表，在最坏情况下，下列各排