全国计算机等级考试 公共基础知识高恩婷 编辑

全国计算机等级考试公共基础知识高恩婷编辑1笔试，与程序设计语言（C、VB、VF等）笔试部分合为一张试卷。2公共基础知识占笔试试卷的30分。310道选择题、5道填空题。考试方式主要内容基本数据结构与算法程序设计基础软件工程基础数据库设计基础一.基本数据结构与算法1.算法的基本概念：算法复杂度（时间、空间）2.数据结构的定义：数据的逻辑结构与存储结构；数据结构的图形表示；线性结构、非线性结构的概念3.线性表的定义：线性表的顺序存储结构及插入、删除运算4.栈和队列的定义：栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念：二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历7.顺序查找与二分法查找算法;基本排序算法(交换类排序，选择类排序，插入类排序)大纲要求例题：1.算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度D．算法只能被有限的用户使用2.下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关3.算法的空间复杂度是指A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句货指令条数D.算法在纸箱过程中所需要的临时工作单元数4.算法的时间复杂度是指A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数1.算法的基本概念2.数据结构的定义:数据的逻辑结构与存储结构；数据结构的图形表示；线性结构、非线性结构的概念根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图•数据的逻辑结构——只抽象反映数据元素的逻辑关系•数据的存储（物理）结构——数据的逻辑结构在计算机存储器中的实现数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.下列叙述中正确的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间2.下列数据结构中，属于非线性结构的是A.循环队列B.带链队列C.二叉树D.带链栈3.数据的存储结构是指______。A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据3.线性表例题：1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的链式存储结构。2.下列叙述中正确的是A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.上述三种说法都不对数据结构逻辑结构存储（物理）结构线性结构非线性结构顺序结构链式结构3.线性表的顺序存储结构和线性表的链式存储结构分别是______。A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构4.用链表表示线性表的优点是______。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取4.栈和队列栈的定义和特点：定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）队列的定义及特点：定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)栈中元素个数=bottom-top+1队列中元素个数=（rear-front+maxqsize）%maxqsize。其中maxqsize为队列的容量例题：1.如果进栈序列为e1，e2，e3，e4，则可能的出栈序列是A．e3，e1，e4，e2B．e2，e4，e3，e1C．e3，e,4，e1，e2D．任意顺序2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后依次出栈，则元素出栈的顺序是A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA这一题注意与上一个例子区别！！！3.一个队列的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入队，然后依次出队，则元素出队的顺序是12345ABCDE。4.下列关于栈的叙述正确的是A.栈按“先进先出”的原则组织数据B.栈按“先进后出”的原则组织数据C.只能在栈底插入数据D.不能删除数据栈——先进后出、栈顶可以插入删除、栈底不可以插入删除5.支持子程序调用的数据结构是A.栈B.树C.队列D.二叉树例题：6.假设用一个长度为50的数组（下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有20个元素7.设某循环队列的容量为50，如果头指针front=45（指向对头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有15个元素。8.对于循环队列，下列叙述中正确的是A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针9.下列叙述中正确的是A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C.再循环队列中，只需要对为指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是有队头指针和队尾指针共同决定的5.单链表、双向链表、循环链表例题：1.设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有24个元素。实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6、7、8…29这24个空间存有元素。2.在单链表中，增加头结点的目的是______。A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现6.树、二叉树二叉树的遍历：前序：根——左——右中序：左——根——右后序：左——右——根例题：1.对如图所示的二叉树进行前序遍历的结果是：A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZD.ABCDEFXYZ2.上图所示二叉树进行中序遍历的结果是DYBEAFCZX3.上图所示二叉树进行后序遍历的结果是YDEBFZXCA4.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。A.cedbaB.acbedC.decabD.deabc6.树、二叉树例题：1.在树形结构中，树根节点没有前件（前驱）2.某二叉树中度为2的节点有18个，则该二叉树中有19个叶子节点。因为：二叉树中，叶子节点数比度为2的节点数多1个，即n0=n2+13.在深度为7的满二叉树中，度为2的节点个数为63。二叉树性质：一棵深度为k的满二叉树有2k-1个节点。所以：该树中共有27-1=127个节点又因为：叶子节点数比度为2的节点数多1个，即n0=n2+1所以有：n0+n2=2n2+1=127n2=634.深度为5的满二叉树有16个叶子节点。5.某二叉树中度为2的节点有18个，则该二叉树中有19个叶子节点。因为：二叉树中，叶子节点数比度为2的节点数多1个，即n0=n2+16.一棵二叉树中共有70个叶子节点与80个度为1的节点，则该二叉树中的总节点数为219。(叶子节点数比度为2的节点数多1个)7.在一棵二叉树上第5层的结点数最多是______。2n-1A.8B.16C.32D.158.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。A.349B.350C.255D.351根据完全二叉树的第二个性质可知：当一二叉树的总结点为n时，其父结点的个数就为Int(n/2).而我们不难可知道；在二叉树中，叶子结点就应该等于所有结点与父结点之差。故本题最简单的解法即为：699—Int(699/2)=699—349=3507.查找、排序•查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素•查找方法评价–查找速度–占用存储空间多少–算法本身复杂程度–平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~顺序查找折半查找/二分查找ASL（平均查找长度）大，（n+1)/2小，log2（n+1)-1表结构有序表、无序表有序表存储结构顺序存储结构线性链表顺序存储结构例题：•对长度为n的线性表排序，在最坏的情况下，比较次数不是n（n-1）/2的排序方法是A．快速排序B．冒泡排序C．直接插入排序D．堆排序2.在长度为n的有序线性表中进行二分查找，在最坏的情况下需要比较的次数是A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)3.下列叙述中正确的是A.对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为n/2C.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为log2nD.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为nlog2n4.在长度为n的线性表中，寻找最大项至少需要比较1次。5.希尔排序法属于哪一种类型的排序法______。A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法6.对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为___。A.N+1B.NC.(N+1)/2D.N/27.在下列几种排序方法中，要求内存量最大的是______。A.插入排序B.选择排序C.快速排序D.归并排序二.程序设计基础1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法，对象、方法、属性及继承与多态性大纲要求例：1.算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度D．算法只能被有限的用户使用2.下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关3.下列叙述中，不符合良好程序设计风格要求的是A.程序的效率第一，清晰第二B.程序的可读性好C.程序中要有必要的注释D.输入数据前要有提示信息1.程序设计方法与风格例：1.在结构化程序设计中，模块划分的原则是A．各模块应包括尽量多的功能B．各模块的规模应尽量大C．各模块之间的联系应尽量紧密D．模块内具有高内聚度，模块间具有低耦合度2.为了使模块尽可能独立，要求A．模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强B．模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱C．模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱D．模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强3.结构化程序设计主要强调的是A．程序的规模B．程序的效率C．程序设计语言的先进性D．