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

全国计算机等级考试全国计算机等级考试 公共基础知识公共基础知识高恩婷高恩婷 编辑编辑1 笔试笔试，与程序设计语言（，与程序设计语言（C、VB、VF等）等）笔试部分合为一张试卷。笔试部分合为一张试卷。2 公共基础知识占笔试试卷的公共基础知识占笔试试卷的30分分。3 10道选择题、道选择题、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.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，则可能的出栈序列是，则可能的出栈序列是Ae3，e1，e4，e2Be2，e4，e3，e1Ce3，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、829这这24个空间存有元素。个空间存有元素。2.在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是_。A.方便运算的实现方便运算的实现B.使单链表至少有一个结点使单链表至少有一个结点C.标识表结点中首结点的位置标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现 6.树、二叉树树、二叉树二叉树的遍历：二叉树的遍历：前序：根前序：根左左右右中序：左中序：左根根右右后序：左后序：左右右根根例题：例题：1.对如图所示的二叉树进行前序遍历的结果是：对如图所示的二叉树进行前序遍历的结果是：A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZD.ABCDEFXYZ 2.上图所示二叉树进行中序遍历的结果是上图所示二叉树进行中序遍历的结果是 DYBEAFCZX 3.上图所示二叉树进行后序遍历的结果是上图所示二叉树进行后序遍历的结果是 YDEBFZXCA4.已知二叉树后序遍历序列是已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，它的前序遍历，它的前序遍历序列是序列是_。A.cedbaB.acbedC.decabD.deabc 6.树、二叉树树、二叉树例题：例题：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=127n2=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=350 7.查找、排序查找、排序查找查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素或数据元素查找方法评价查找方法评价 查找速度查找速度 占用存储空间多少占用存储空间多少 算法本身复杂程度算法本身复杂程度 平均查找长度平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的值进行比较的关键字的个数的期望值叫查找算法的例题：例题：对长度为对长度为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程序的易读性程序的易读性 4.结构化程序设计的基本原则结构化程序设计的基本原则不包括不包括A.多态性多态性B.自顶向下自顶向下C.模块化模块化D.逐步求逐步求精精多态性是面向对象程序设计语言的特点。多态性是面向对象程序设计语言的特点。2.结构化程序设计结构化程序设计5.信息隐蔽的概念与下述哪一种概念直接相关信息隐蔽的概念与下述哪一种概念直接相关_。A.软件结构定义软件结构定义B.模块独立性模块独立性C.模块类型划分模块类型划分D.模拟耦合度模拟耦合度3.面向对象的程序设计方法、对象、方法、属面向对象的程序设计方法、对象、方法、属性及继承与多态性性及继承与多态性1.下列选项中下列选项中不属于不属于面向对象程序设计特征的是面向对象程序设计特征的是A继承性继承性B多态性多态性C类比性类比性D封装性封装性2.在面向对象方法中，实现信息隐蔽是依靠在面向对象方法中，实现信息隐蔽是依靠A.对象的继承对象的继承B.对象的多态对象的多态C.对象的封装对象的封装D.对象的分类对象的分类3.面向对象方法中，集成是指面向对象方法中，集成是指A.一组对象所具有的相似性质一组对象所具有的相似性质B.一个对象具有另一个对象的性质一个对象具有另一个对象的性质C.各对象之间的共同性质各对象之间的共同性质D.类之间共享属性和操作的机制类之间共享属性和操作的机制4.下面对对象概念描述错误的是下面对对象概念描述错误的是_。A.任何对象都必须有继承性任何对象都必须有继承性B.对象是属性和方法的封装体对象是属性和方法的封装体C.对象间的通讯靠消息传递对象间的通讯靠消息传递D.操作是对象的动态性属性操作是对象的动态性属性5.5.在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送_。A.A.调用语句调用语句B.B.命令命令C.C.口令口令D.D.消息消息三三.软件工程基础软件工程基础1.软件工程基本概念，软件生命周期概念，软件工具软件工程基本概念，软件生命周期概念，软件工具与软件开发环境与软件开发环境2.结构化分析方法，数据流图，数据字典，软件需求结构化分析方法，数据流图，数据字典，软件需求规格说明书规格说明书3.结构化设计方法，总体设计与详细设计结构化设计方法，总体设计与详细设计4.软件测试的方法，白盒测试与黑盒测试，测试用例软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系设计，软件测试的实施，单元测试、集成测试和系统测试统测试5.程序的调试，静态调试与动态调试。程序的调试，静态调试与动态调试。大纲要求大纲要求例题：例题：1.需求分析阶段的任务是确定需求分析阶段的任务是确定A软件开发方法软件开发方法B软件开发工具软件开发工具C软件开发费用软件开发费用D软件系统功能软件系统功能2.算法的有穷性是指算法的有穷性是指A算法程序的运行时间是有限的算法程序的运行时间是有限的B算法程序所处理的数据量是有限的算法程序所处理的数据量是有限的C算法程序的长度算法程序的长度D算法只能被有限的用户使用算法只能被有限的用户使用 2.下列叙述中正确的是下列叙述中正确的是 A算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量 C数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关3.软件的生命周期可分为多个阶段，一般分为定义阶段、开发阶段、维护阶段。编软件的生命周期可分为多个阶段，一般分为定义阶段、开发阶段、维护阶段。编码和测试属于码和测试属于 开发开发 阶段。阶段。4.软件工程三要素包括方法、工具、过程，其中软件工程三要素包括方法、工具、过程，其中 过程过程 支持软件开发的各个环节的支持软件开发的各个环节的控制和管理。控制和管理。方法方法提供了提供了“如何做如何做”的技术；工具的技术；工具支持软件的开发、管理、文档生成；支持软件的开发、管理、文档生成；过程过程支持软件开发的各个环节的控制和管理。支持软件开发的各个环节的控制和管理。1.软件工程、软件生命周期、软件工具与开发环境软件工程、软件生命周期、软件工具与开发环境5.软件是指软件是指A.程序程序B.程序和文档程序和文档C.算法加数据结构算法加数据结构D.程序、数据与相关文档的完整集合程序、数据与相关文档的完整集合6.下面描述中，不属于软件危机表现的是下面描述中，不属于软件危机表现的是A.软件过程不规范软件过程不规范B.软件开发生产率低软件开发生产率低C.软件质量难以控制软件质量难以控制D.软件成本不断提高软件成本不断提高7.软件生命周期是指软件生命周期是指A.软件产品从提出、实现、使用维护到停止使用退役的过程软件产品从提出、实现、使用维护到停止使用退役的过程B.软件从需求分析、设计、实现到测试完成的过程软件从需求分析、设计、实现到测试完成的过程C.软件的开发过程软件的开发过程D.软件的运行维护过程软件的运行维护过程8.在软件开发中，下面任务不属于设计阶段的是在软件开发中，下面任务不属于设计阶段的是_。A.数据结构设计数据结构设计B.给出系统模块结构给出系统模块结构C.定义模块算法定义模块算法D.定义需求并建立系统模型定义需求并建立系统模型 9.在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是的阶段是_。(D)A.概要设计概要设计B.详细设计详细设计C.可行性分析可行性分析D.需求分析需求分析2.结构化分析方法，数据流图，数据字典，软件需求结构化分析方法，数据流图，数据字典，软件需求规格说明书规格说明书程序流程图是人们对解决问题的方法、思路、算法的一种描述。其中：程序流程图是人们对解决问题的方法、思路、算法的一种描述。其中：图框图框各种操作的类型各种操作的类型图框中的文字和符号图框中的文字和符号操作的内容操作的内容流程线流程线操作的先后顺序操作的先后顺序带箭头的线段带箭头的线段数据流（数据流程图中），控制流（程序流程图中）数据流（数据流程图中），控制流（程序流程图中）例题：例题：1.程序流程图中带有箭头的线段表示的是程序流程图中带有箭头的线段表示的是A.图元关系图元关系B.数据流数据流C.控制流控制流D.调用关系调用关系2.数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是成。下列图符名标识的图符不属于数据流图合法图符的是_。(A)A.控制流控制流B.加工加工C.数据存储数据存储D.源和潭源和潭例题：例题：3.为了避免流程图在描述程序逻辑时的不灵活性，提出了用方框图来代替传统为了避免流程图在描述程序逻辑时的不灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为的程序流程图，通常也把这种图称为APAD图图BN-S图图C结构图结构图D数据流图数据流图4.在结构化分析使用的数据流图（在结构化分析使用的数据流图（DFD）中，利用）中，利用 数据字典数据字典 对其中的图形元素对其中的图形元素进行确切解释。进行确切解释。数据字典用来定义数据流图中各个成分的具体含义。数据字典用来定义数据流图中各个成分的具体含义。5.在软件开发中，在需求分析阶段可以使用的工具是在软件开发中，在需求分析阶段可以使用的工具是A.N-S图图B.DFD图图 C.PAD图图 D.程序流程图程序流程图数据流图简称数据流图简称DFD，采用图形方式来表达系统的逻辑功能、数据在系统内部的，采用图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具及用于表示逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示方法。软件模型的一种图示方法。6.软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是：性等特性，其中最重要的是：无歧义性无歧义性7.在软件开发中，需求分析阶段产生的主要文档是在软件开发中，需求分析阶段产生的主要文档是A.可行性分析报告可行性分析报告B.软件需求规格说明书软件需求规格说明书C.概要设计说明书概要设计说明书D.集成测试计划集成测试计划需求分析的工作包括：需求获取、需求分析、编写需求规格说明书、需求评审需求分析的工作包括：需求获取、需求分析、编写需求规格说明书、需求评审8.软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及需求规格说明书以及_。A.阶段性报告阶段性报告B.需求评审需求评审C.总结总结D.都不正确都不正确 3.结构化设计方法（总体、详细）结构化设计方法（总体、详细）1.软件生命周期分为定义阶段、开发阶段、维护阶段。详细设计属于软件生命周期分为定义阶段、开发阶段、维护阶段。详细设计属于A.定义阶段定义阶段B.开发阶段开发阶段C.维护阶段维护阶段D.上述三个阶段上述三个阶段2.下面描述中，符合结构化程序设计风格的是下面描述中，符合结构化程序设计风格的是_。A.使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B.模块只有一个入口，可以有多个出口模块只有一个入口，可以有多个出口(可以有可以有0个入口个入口)C.注重提高程序的执行效率注重提高程序的执行效率D.不使用不使用goto语句（只是限制使用）语句（只是限制使用）4.软件测试的方法软件测试的方法软件测试的目的：暴露错误，评价程序的可靠性。软件测试的目的：暴露错误，评价程序的可靠性。软件测试过程（软件测试过程（4步）：单元测试、集成测试、确认测试、系统测试步）：单元测试、集成测试、确认测试、系统测试两种基本测试方法：两种基本测试方法：黑箱测试黑箱测试是根据程序规格说明所规定的功能来设计测试用例，不考虑程是根据程序规格说明所规定的功能来设计测试用例，不考虑程序的内部结构和处理过程。包括：等价类划分、边界分析、错误猜测、序的内部结构和处理过程。包括：等价类划分、边界分析、错误猜测、因果图因果图白盒测试白盒测试的基本原则：保证所测模块中每一个独立路径至少执行一次；的基本原则：保证所测模块中每一个独立路径至少执行一次；所有判断的每一个分支至少执行一次；每一循环都在边界条件和一般条所有判断的每一个分支至少执行一次；每一循环都在边界条件和一般条件下至少个执行一次；验证所有内部数据结构的有效性。件下至少个执行一次；验证所有内部数据结构的有效性。“白盒白盒”法是法是穷举路径测试。包括穷举路径测试。包括:逻辑覆盖、基本路径测试逻辑覆盖、基本路径测试测试用例是软件测试的核心。测试用例是为了有效发现软件缺陷而编写的包含测试用例是软件测试的核心。测试用例是为了有效发现软件缺陷而编写的包含测试目的、测试步骤、期望测试结果的特定集合。测试目的、测试步骤、期望测试结果的特定集合。例题：例题：1.下列叙述中正确的是下列叙述中正确的是A.软件测试的主要目的是发现程序中的错误软件测试的主要目的是发现程序中的错误B.软件测试的主要目的是确定程序中错误的位置软件测试的主要目的是确定程序中错误的位置C.为了提高软件测试的效率，最好有程序编制者自己来完成软件测试的工作为了提高软件测试的效率，最好有程序编制者自己来完成软件测试的工作D.软件测试是证明软件没有错误软件测试是证明软件没有错误2.软件测试分为白箱（盒）测试和黑箱（盒）测试。等价类划分法属于软件测试分为白箱（盒）测试和黑箱（盒）测试。等价类划分法属于 黑箱黑箱（盒）测试（盒）测试 。3.软件测试分为白箱（盒）测试和黑箱（盒）测试。基本路径测试属于软件测试分为白箱（盒）测试和黑箱（盒）测试。基本路径测试属于 白箱白箱（盒）测试（盒）测试 。4.在两种基本测试方法中，在两种基本测试方法中，白盒白盒 测试的原则之一是帮正所测模块中每一个测试的原则之一是帮正所测模块中每一个独立路径至少要执行一次。独立路径至少要执行一次。5.测试用例包括输入值集和测试用例包括输入值集和 输出输出 值集。值集。6.检查软件产品是否符合需求定义的过程称为检查软件产品是否符合需求定义的过程称为_。A.确认测试确认测试B.集成测试集成测试C.验证测试验证测试D.验收测试验收测试5.程序的调试程序的调试例题：例题：1.软件调试的目的是软件调试的目的是A.发现错误发现错误B.改正错误改正错误C.改善软件的性能改善软件的性能D.验证软件的正确性验证软件的正确性2.下列不属于软件调试技术的是下列不属于软件调试技术的是_。A.强行排错法强行排错法B.集成测试法集成测试法C.回溯法回溯法D.原因排除法原因排除法 四四.数据库设计基础数据库设计基础1.数据库的基本概念：数据库，数据库管理系统，数据库系统数据库的基本概念：数据库，数据库管理系统，数据库系统 2.数据模型：实体联系模型及数据模型：实体联系模型及E-R图，从图，从E-R图导出关系数据图导出关系数据模型。模型。3.关系代数运算：包括集合运算及选择、投影、连接运算，数关系代数运算：包括集合运算及选择、投影、连接运算，数据库规范化理论。据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。物理设计的相关策略。大纲要求大纲要求1.数据库的基本概念数据库的基本概念1.数据库应用系统中的核心问题是数据库应用系统中的核心问题是A数据库设计数据库设计B数据库系统设计数据库系统设计C数据库维护数据库维护D数据库管理员培训数据库管理员培训 2.数据库系统的核心是数据库系统的核心是 数据库管理系统数据库管理系统 。3.数据库管理系统是数据库管理系统是A.操作系统的一部分操作系统的一部分B.在操作系统支持下的系统软件在操作系统支持下的系统软件C.一种编译系统一种编译系统D.一种操作系统一种操作系统4.在学生管理的关系数据库中，存取一个学生信息的数据单位是在学生管理的关系数据库中，存取一个学生信息的数据单位是A.文件文件B.数据库数据库C.字段字段D.记录记录5.层次型、网状型、关系型数据库划分的原则是层次型、网状型、关系型数据库划分的原则是A.记录长度记录长度B.文件大小文件大小C.联系的复杂程度联系的复杂程度D.数据间的联系方式数据间的联系方式6.下列叙述中正确的是下列叙述中正确的是_。A.数据库是一个独立的系统，不需要操作系统的支持数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致数据库系统中，数据的物理结构必须与逻辑结构一致 7.关系表中的每一横行称为一个关系表中的每一横行称为一个_。A.元组元组B.字段字段C.属性属性D.码码8.在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是据库系统阶段。其中数据独立性最高的阶段是_。A.数据库系统数据库系统B.文件系统文件系统C.人工管理人工管理D.数据项管理数据项管理9.数据处理的最小单位是数据处理的最小单位是_。A.数据数据B.数据元素数据元素C.数据项数据项D.数据结构数据结构E-R图三要素：图三要素：实体实体矩形框表示；属性矩形框表示；属性椭圆形表示；实体间的联系椭圆形表示；实体间的联系菱形框表示菱形框表示例如：例如：1.将将E-R图转换到关系模式时，实体与联系都可以表示成图转换到关系模式时，实体与联系都可以表示成A属性属性B关系关系C键键D域域 2.在在E-R图中，用来表示实体之间联系的图形是图中，用来表示实体之间联系的图形是A.矩形矩形B.椭圆形椭圆形C.菱形菱形D.平行四边形平行四边形3.在在E-R图中，矩形表示图中，矩形表示 实体实体 。4.在数据库设计中，将在数据库设计中，将E-R图转换成关系数据模型的过程属于图转换成关系数据模型的过程属于A.需求分析阶段需求分析阶段B.概念设计阶段概念设计阶段C.逻辑设计阶段逻辑设计阶段D.物理设计阶段物理设计阶段5.在关系数据库中，用来表示实体间联系的是在关系数据库中，用来表示实体间联系的是 关系关系 。6.在数据库技术中，实体集之间的联系可以是一对一，一对多或多对多的，那么在数据库技术中，实体集之间的联系可以是一对一，一对多或多对多的，那么“学学生生”和和“可选课程可选课程”的联系为的联系为 多对多多对多 。2.数据模型数据模型关系代数运算：关系代数运算：并并交交投影投影选择选择自然连接自然连接笛卡儿积笛卡儿积3.关系代数运算关系代数运算例题：例题：1.有有3个关系个关系R、S和和T,如下如下由关系由关系R和和S通过运算得到关系通过运算得到关系T，则所使用的运算为，则所使用的运算为A.并并B.自然连接自然连接C.笛卡儿积笛卡儿积D.交交2.有有3个关系个关系R、S和和T,如下如下由关系由关系R和和S通过运算得到关系通过运算得到关系T，则所使用的运算为，则所使用的运算为A.并并B.选择选择C.投影投影D.交交3.在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是A.并并B.交交C.投影投影D.笛卡儿积笛卡儿积4.有有3个关系个关系R和和T,如下如下由关系由关系R通过运算得到关系通过运算得到关系T，则所使用的运算为，则所使用的运算为A.并并B.选择选择C.投影投影D.交交5.关系数据库管理系统能实现的专门关系运算包括关系数据库管理系统能实现的专门关系运算包括_。A.排序、索引、统计排序、索引、统计B.选择、投影、连接选择、投影、连接C.关联、更新、排序关联、更新、排序D.显示、打印、制表显示、打印、制表6.在关系数据库中，用来表示实体之间联系的是在关系数据库中，用来表示实体之间联系的是_。A.树结构树结构B.网结构网结构C.线性表线性表D.二维表二维表 7.按条件按条件f对关系对关系R进行选择，其关系代数表达式为进行选择，其关系代数表达式为_。A.R|X|RB.R|X|R C.f(R)D.f(R)1.下列叙述中下列叙述中错误错误的是的是A.在数据库系统中，数据的物理结构必须与逻辑结构一致在数据库系统中，数据的物理结构必须与逻辑结构一致B.数据库技术的根本目标是要解决数据的共享问题数据库技术的根本目标是要解决数据的共享问题C.数据库设计是指在已有数据库管理系统的基础上建立数据库数据库设计是指在已有数据库管理系统的基础上建立数据库D.数据库系统需要操作系统的支持数据库系统需要操作系统的支持2.在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，数据定数据定义语言义语言 负责数据的模式定义与数据的物理存取构建。负责数据的模式定义与数据的物理存取构建。数据定义语言负责：数据的模式定义与数据的物理存取构建；数据定义语言负责：数据的模式定义与数据的物理存取构建；数据操纵语言负责：数据的操纵，如：查询、增、删、改数据操纵语言负责：数据的操纵，如：查询、增、删、改数据控制语言负责：数据完整性、安全性的定义与检查，以及并发控制、故障恢复数据控制语言负责：数据完整性、安全性的定义与检查，以及并发控制、故障恢复等等4.数据库设计中，用数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的据库设计的 概念设计阶段概念设计阶段 。5.数据库设计中反映用户对数据要求的模式是数据库设计中反映用户对数据要求的模式是A.内模式内模式 B.概念模式概念模式C.外模式外模式D.设计模式设计模式模式的模式的3个级别反映了模式的个级别反映了模式的3个不同环境，以及对他们的不同要求。个不同环境，以及对他们的不同要求。内模式内模式最低层，反映了数据在计算机物理结构中的实际存储形式最低层，反映了数据在计算机物理结构中的实际存储形式概念模式层概念模式层中层，反映了设计者的数据全局逻辑要求中层，反映了设计者的数据全局逻辑要求外模式外模式最高层，反映了用户对数据的要求最高层，反映了用户对数据的要求4.数据库设计方法和步骤数据库设计方法和步骤6.数据库设计的数据库设计的4个阶段：需求分析，概念设计，逻辑设计和个阶段：需求分析，概念设计，逻辑设计和 物理设计物理设计 。7.下列模式中，能够给出数据库物理存储结构与物理存取方法的是下列模式中，能够给出数据库物理存储结构与物理存取方法的是_。A.内模式内模式B.外模式外模式C.概念模式概念模式D.逻辑模式逻辑模式