公共基础知识历年真题按知识点.pdf

公共基础知识历年真题按知识点第一章1.1下列叙述中正确的是_ _ _ _ _ _ _。A）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一-对应的D）算法的时间复杂度与空间复杂度一定相关20 0 7 年 4月选择题第1 题参考答案：B【解析】根据时间复杂度和空间复杂度的定义可知，算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间关系的，是独立于计算机中的，数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。算 法 的 有 穷 性 是 指。A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用20 0 8 年 4月选择题第5题参考答案：A【解析】算法具有6个特性。有 穷 性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有限时间内完成，即运行时间是有限的。确 定性：算法中每一条指令必须有确切的含义，读者理解时不会产生歧义。可 行 性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。输 入：一个算法有零个或多个输入，这些输入取自某个特定的对象的集合。输出：一个算法有一个或多个输出。算 法 的 时 间 复 杂 度 是 指。A）算法的执行时间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的基木运算次数2010年 3 月选择题第2 题参考答案：D【解析】算法的时间复杂度是指算法需要消耗的时间资源，是独立于机器的，选 项 D）正确；相同的算法在不同的机器上运行时间可能不同，选项A）错误；算法所处理的数据量与算法无关，选 项 B）错误；程序的长短与程序执行时需要消耗的时间资源没有必然的关系，比如个条件语句可以很长，但只需判断一次，而一个循环语句可能只有几行，但可以执行很多次，故选项C）错误。算 法 的 空 间 复 杂 度 是 指。A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量O 算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数2009年 9 月选择题第4 题参考答案：A【解析】算法的空间复杂度是指：算法执行过程中所需的存储空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。1.2下列叙述中正确的是一.A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对20 0 7 年 9月选择题第6题参考答案：D【解析】数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系，故 A）选项错误。存储结构分为顺序存储结构与链式存储结构，其中顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据，故 B）选项错误。数组的存储方式连续是指其在计算机中的存储方式，它可以用来处理非线性结构，故 C）选项错误。下 列 叙 述 中 正 确 的 是。A）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量0数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关2 0 0 7 年 4月选择题第1 题参考答案：B【解析】根据时间复杂度和空间复杂度的定义可知，算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间关系的，是独立于计算机中的，数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。下列数据结构中，属于非线性结构的是_ _ _ _ _ _ _ _。A ）循环队列B）带 链 队 列 C）二叉树D）带链栈2 0 0 9 年 9月选择题第1 题参考答案：C【解析】根据数据结构中各数据元素之间前后关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系。根据各种结构的定义知二叉树是一种非线性结构。下 列 叙 述 中 正 确 的 是。A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构2 0 1 1 年 3月选择题第2题参考答案：B【解析】线性结构指的是数据元素之间存在着 一对一 线性关系的数据结构，这样的结构中只有一个根结点，如循环链表和双向链表；非线性结构指的是数据元素之间存在着一对多“非线性关系的数据结构，这样的结构中可能有一个根结点，如树形结构，也可能有多个根结点，如网状结构。故本题答案为B）。1.3下 列 叙 述 中 正 确 的 是。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间2 0 0 8 年 9月选择题第4题参考答案：A【解析】顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间，所以选项D）错误。顺序存储结构可以存储如二叉树这样的非线性结构，所以选项B）错误。链式存储结构也可以存储线性表，所以选项0错误。下列 叙 述 中 正 确 的 是。A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对2 0 1 0 年 9月选择题第1 题参考答案：B【解析】线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于顺序存储结构，答案为B）。下 列 叙 述 中 正 确 的 是。A）栈是 先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构2 0 0 9 年 3月选择题第1 题参考答案：D【解析】栈是 先进后出”的线性表；队列是“先进先出 的线性表；循环队列是队列的一种顺序存储结构，因此是线性结构；有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。1.4下 列 关 于 栈 的 叙 述 正 确 的 是。A）栈按“先进先出 组织数据B）栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据2 0 0 8年4月选择题第7题参考答案：B【解析】在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。因而栈是按照“先进后出 或 后进先出 的原则组织数据的。一个栈的初始状态为空。现 将 元 素1、2、3、4、5、A、B、C、D、E依次入栈，然后依次出栈，则 元 素 出 栈 的 顺 序 是。A）1 2 3 4 5 A B CDEB）EDCB A 5 4 3 2 1C）A B CDE1 2 3 4 5D）5 4 3 2 1 EDCB A2 0 0 8年9月选择题第1题参考答案：B【解析】栈的特点是先进后出，所以全部入栈后再全部出栈所得的序列顺序必然与入栈序列的顺序相反。下列叙述中正确的是_ _ _ _ _ _ _。A）栈是 先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构2 0 0 9年3月选择题第1题参考答案：D【解析】栈是 先进后出”的线性表；队列是“先进先出”的线性表；循环队列是队列的种顺序存储结构，因此是线性结构；有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。支 持 子 程 序 调 用 的 数 据 结 构 是。A）栈 B）树 C）队 列 D）二叉树2 0 0 9 年 3月选择题第2题参考答案：A【解析】栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为A）o下列数据结构中，能够按照“先进后出”原则存取数据的是 oA）循环队列B）栈0队列D）二叉树2 0 0 9 年 9月选择题第2题参考答案：B【解析】栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。栈顶元素总是后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。栈是按照“先进后出 或 后进先出”的原则组织数据的。下列叙述中正确的是_ _ _ _ _ _ _。A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D）上述三种说法都不对2 0 1 0 年 9月选择题第2题参考答案：C【解析】栈是限定在-端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当有新元素进栈时，栈顶指针向上移动；当有元素出栈时，栈顶指针向下移动。在栈中栈底指针不变，栈中元素随栈顶指针的变化而动态变化，故答案为C）。下 列 关 于 栈 叙 述 正 确 的 是。A）栈顶元素最先能被删除B）栈顶元素最后才能被删除C）栈底元素永远不能被删除D）以上三种说法都不对2 0 1 1 年 3月选择题第1 题参考答案：A【解析】栈是限定在一端进行插入与删除的特殊线性表。允许进行插入和删除操作的一端称为栈顶（t o p）,另一端为栈底（b o t t o m）；栈底固定，而栈顶浮动。栈按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据时从栈顶开始弹出数据（最后一个进入数据被第一个读出来）。所以栈顶的元素最先被删除，本题答案为A）。下列对队列的叙述正确的是 oA）队列属于非线性表B）队列按“先进后出”原则组织数据C）队列在队尾删除数据D）队列按 先进先出 原则组织数据2 0 0 7 年 4月选择题第5题参考答案：D【解析】队列是一种操作受限的线性表。它只允许在线性表的一端进行插入操作，另一端进行删除操作。其中，允许插入的一端称为队尾（r e a r）,允许删除的一端称为队首（f r o n t）o队列具有先进先出的特点，它是按“先进先出”的原则组织数据的，故本题答案为 D）。下 列 叙 述 中 正 确 的 是。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况0 在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定2 0 0 8 年 9月选择题第2题参考答案：D【解析】循环队列是线性表的一种，所以选项A）错误。循环队列的入队和出队需要队尾指针和队头指针共同完成，所以选项B）和 C）错误。对于循环队列，下列叙述中正确的是_ _ _ _ _ _ _ _。A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针可以大于队尾指针，也可以小于队尾指针2 0 0 9 年 9月选择题第3题参考答案：D【解析】循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针，故答案为D）。假设用一个长度为5 0 的数组（数组元素的下标从0到 4 9）作为栈的存储空间，栈底指针b o t t o m 指向栈底元素，栈顶指针t o p 指向栈顶元素，如果b o t t o m=4 9,t o p=3 0（数组下标），则栈中具有【1】一个元素。2 0 0 9 年 3月填空题第1 题参考答案：2 0【解析】与一般的线性表一样，在程序设计语言中，用一维数组S（l,m）作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的栈中的元素个数等于（栈底指针一栈顶指针+1）,即 4 9-3 0+1 =2 0,一个栈的初始状态为空。首先将元素5,4,3,2,1 依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的 顺 序 为【1】。2 0 1 0 年 9月填空题第1 题参考答案：1 D C B A2 3 4 5【解析】栈是限定只在一端进行插入与删除的线性表，栈按照”先进后出”或后进先出”的原则组织数据。当 5 4 3 2 1 入栈后，此时执行退栈操作，出栈的元素 是 1,然后AB C D 入栈，再招所有元素退栈，故退栈顺序为：1 D C B A2 3 4 5。一个队列的初始状态为空.现将元素A,B,C,D,E,F,5,4,3,2,1 依次入队,然后再依次退队,则元素退队的顺序为【1】。2 0 1 0 年 3月填空题第1 题参考答案：A,B,C,D,E,F,5,4,3,2,1【解析】队列是先进先出的数据结构，所以出队列的顺序与进度列的顺序一致。线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循 环 队 列 是 队 列 的【3】存储结构。2 0 0 7 年 9月填空题第3题参考答案：链式【解析】数据结构包括数据的逻辑结构和存储（物理）结构，其中逻辑结构分为线性结构和非线性结构，存储结构包括顺序结构和链式结构。在循环队列中，队尾的指针指向对首元素，是队列的链式存储结构。设某循环队列的容量为5 0,头指针f r o n t =5（指向队头元素的前一位置），尾指针r e a r=2 9（指向队尾元素），则该循环队列中共有一 3 个元素。2 0 0 8 年 4月填空题第3题参考答案：2 4【解析】实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6,7,8,.,2 9 这 2 4 个空间存有元素，即队列中有2 9 5 =2 4个元素。设某循环队列的容量为5 0,如果头指针f r o n t=4 5（指向队头元素的前一位置），尾指针r e a r=1 0（指向队尾元素），则该循环队列中共有【2】个元素。2 0 1 0 年 3月填空题第2题参考答案：1 5【解析】计算队列中元素个数的公式为：（r e a d-f r o n t+M AXQ S I Z E）%M AXQ S I Z E,其中M AXQ S I Z E 为队列的容量，所以该队列中的元素为（1 0-4 5+5 0）%5 0=1 5。1.5下 列 叙 述 中 正 确 的 是。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构0 顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间2 0 0 8 年 9月选择题第4题参考答案：A【解析】顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间，所以选项D）错误。顺序存储结构可以存储如二叉树这样的非线性结构，所以选项B）错误。链式存储结构也可以存储线性表，所以选项C）错误。下 列 叙 述 中 正 确 的 是。A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对2 0 1 0 年 9月选择题第1 题参考答案：B【解析】线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于顺序存储结构，答案为B）。1.6下列数据结构中，能够按照“先进后出 原则存取数据的是 oA)循环队列B)栈0队列D)二叉树2 0 0 9 年 9月选择题第2题参考答案：B【解析】栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。栈顶元素总是后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。栈是按照”先进后出或后进先出”的原则组织数据的。某二叉树中有n个度为2的节点，则该二叉树中的叶子节点数为_ 。A)n+1B)n-1C)2 nD)n/22 0 0 7 年 4月选择题第7题参考答案：A【解析】对于任何一棵二叉树T，如果其终端节点(叶子)数为n l,度 为 2的节点数为n 2,则 n l=n 2 +l。所以该二叉树的叶子结点数等于n+1。一棵二叉树中共有7 0 个叶子节点与80 个度为1的节点，则该二叉树中的总节点数为_ OA)2 1 98)2 2 10 2 2 9D)2 3 12 0 0 7 年 9月选择题第8 题参考答案：A【解析】在任意一棵二叉树中，若终端节点(叶子)的个数为n l,则度为2的节点数n 2=n l l o 本题中度为0的节点即叶子节点，故总节点数=度 为 0的 节点数+度为1 的节点数+度 为 2的节点数=7 0+8 0+6 9=2 1 9。某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是。A)1 0 B)8 0 6 D)42 0 0 9 年 3月选择题第3题参考答案：C【解析】对于任何一棵二叉树T,如果其终端结点(叶子)数为n l,度 为 2的结点数为n 2,则 n l=n 2+l。所以该二叉树的叶子结点数等于5+1=6。某二叉树共有7个结点，其中叶子结点只有1 个，则该二叉树的深度为(假设根结点在第 1 层)oA)3B)4C)6D)72 0 1 1 年 3月选择题第3题参考答案：D【解析】叶子结点个数=度 为 2的结点个数+1,在此题中叶子结点个数为1,说明度为2的结点数为0,即二叉树中不存在度为2的结点，只有度为1 的结点和叶子结点，那么此二叉树就是一棵单支树，树中结点个数即为树的深度，所以答案为D)。对下列二叉树:进行前序遍历的结果为。A)D Y BE AF CZ XB)Y D E BF Z X CAO ABD Y E CF X ZD)ABCD E F X Y Z2 0 0 7 年 4月选择题第6题参考答案：C【解析】二叉树前序遍历的含义是：首先访问根结点，然后按前序遍历根结点的左子树，最后按前序遍历根结点的右子树，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是：ABD Y E CF X Z。某二叉树有5个度为2的结点以及3个度为1 的结点，则该二叉树中共有【1】_个结点。2 0 0 9 年 9月填空题第1 题参考答案：1 4【解析】在二叉树中，度 为 0的结点数是度为2的结点数加1,故二叉树中结点数的总和为度为0的结点数、度 为 1 的结点数及度为2的结点数三者相加，得出结果为1 4 个结点。一棵二叉树有1 0 个度为1 的结点，7个度为2的结点，则 该 二 叉 树 共 有【3】个结点。2 0 1 0 年 9月填空题第3题参考答案：2 5【解析】在二叉树中，根据性质3,度 为 0的结点是度为2的结点个数+1,故二叉树中结点总和为度为0的结点数、度 为 1 的结点数以及度为2的结点数三者相加，即 8+1 0+7,共 2 5 个结点。在深度为7的满二叉树中，度 为 2的节点个数为【1】2 0 0 7 年 4月填空题第1 题参考答案：6 3【解析】根据二叉树的性质，棵深度为k的满二叉树有2 k-l 个节点，所以深度为7的满二叉树有2 7 1 =1 2 7 个节点；又因为在任意一棵二叉树中，若终端节点的个数为n 0,度 为 2的节点数为n 2,则 n 0=n 2 +l,即所以总节点数为n 0+n 2=2 n 2 +l =1 2 7,所以 n 2=6 3,即度为2的节点个数为6 3,所 以【1】应填入6 3。深度为5的满二叉树有【2】一个叶子结点。2 0 0 8年 4月填空题第2题参考答案：1 6一【解析】在满二叉树中，叶子结点数目的计算公式为2 n l,其 中 n为树的深度。对下列二叉树进行中序遍历的结果为【4】参考答案：ACBD F E HG P【解析】二叉树中序遍历的含义是：首先按中序遍历根结点的左子树，然后访问根结点，最后按中序遍历根结点的右子树，中序遍历二叉树的过程是一个递归的过程。根据题目中给;I；的二叉树的结构可知中序遍历的结果是：ACBD F E HG P,对下列二叉树进行中序遍历的结果 是 一【1】2 0 0 8年 9月填空题第1 题参考答案：D BX E AY F Z C【解析】二叉树中序遍历的顺序为先遍历左子树，然后访问根结点，最后遍历右子树。设二叉树如下：汽回 0/回 0/回 回 回对该二叉树进行后序遍历的结果为【3】。2 0 1 0 年 3月填空题第3题参考答案：E D BG HF CA【解析】后序遍历二叉树的定义为：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树，访问根结点。根据该规则，遍历结果应为E D BG HF CA。一棵二叉村的中序遍历结果为D BE AF C,前序遍历结果为ABD E CF,则后序遍历结果为 2 2 0 1 1 年 3月填空题第2题参考答案：D E BF CA【解析】依据前序遍历序列可确定根结点为A,再依据中序遍历序列可知其左子树由D BE 构成，右子树为F C；由 A 的左子树的前序遍历序列可知其根结点为B,由中序遍历序列可知其左子树为D,右子树为E；由A 的右子树的前序遍历序列可知其根结点为C,由中序遍历序列可知其左子树为F,右子树为空。因此此二叉树的后序遍历序列为D E BF CA。1.7在长度为n 的线性表中，寻找最大项至少需要比较 2 次。2010年 9 月填空题第2 题参考答案：1【解析】在线性表中，如果元素按从小到大的顺序排列且查找从后向前进行时，比 较 1次即能找到最大值，这时查找比较次数最少，故至少比较次数为1 次。1.8冒泡排序在最坏情况下的比较次数是_ _ _ _ _ _ _ _。A)n(n+l)/2B)nlog2nC)n(n1)/2D)n/22007年 9 月选择题第7 题参考答案：C【解析】冒泡排序的基本思想是对当前未排序的全部节点自上而下依次进行比较和调整，让键值较大的节点下沉，键值较小的节点往上冒。也就是说，每当两相邻节点比较后发现它们的排列与排序要求相反时，就将它们互换。对 n 个节点的线性表采用冒泡排序，冒泡排序的外循环最多执行n-l 遍。第一遍最多执行n-l 次比较，第二遍最多执行n2次比较，依次类推，第 n1遍最多执行1 次比较。因此，整个排序过程最多执行n(n 1)/2 次比较。对长度为n 的线性表排序，在最坏情况下，比较次数不是n(n1)/2 的排序方法是A)快速排序B)冒泡排序C)直接插入排序D)堆排序2008年 4 月选择题第6 题参考答案：D【解析】在最坏情况下，快速排序、冒泡排序和直接插入排序需要的比较次数都是n（n-1）/2,堆排序需要比较的次数为n l o g 2 n。下列排序方法中，最坏情况下比较次数最少的是_ _ _ _ _ _ _ _。A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序2 0 0 9 年 3月选择题第4题参考答案：D【解析】冒泡排序、简单选择排序和直接插入排序在最坏情况下比较次数都是n（n 1）/2”,堆排序在最坏情况下比较次数最少，是“O（n l o g 2 n）”。第二章2.1下列叙述中，不 符 合 良 好 程 序 设 计 风 格 要 求 的 是。A）程序的效率第一，清晰第二B）程序的可读性好C）程序中要有必要的注释D）输入数据前要有提示信息2 0 0 7 年 9月选择题第4题参考答案：A【解析】当今主导的程序设计风格是清晰第一，效率第二”的观点。结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，而实际应用中，人们更重视程序的可理解性。2.2下列 选 项 中 不 属 于 结 构 化 程 序 设 计 原 则 的 是。A）可 封 装 B）自顶向下C）模 块 化 D）逐步求精2009年 9 月选择题第6 题参考答案：A【解析】模块化、自顶向下、逐步求精都是结构化程序设计的原则；可封装是面向对象程序设计原则。在软件开发中，需 求 分 析 阶 段 产 生 的 主 要 文 档 是。A）软件集成测试计划B）软件详细设计说明书。用户手册D）软件需求规格说明书2011年 3 月选择题第5 题参考答案：B【解析】结构化程序设计方法主要由以下三种逻辑结构组成：D 顺序结构：顺序结构是一种线性、有序的结构，它依次执行各语句模块；2）循 环（重复）结构：循环结构是重复执行一个或几个模块，直到满足某一条件为止；3）选 择（分支）结构：选择结构是根据条件成立与否选择程序执行的通路。故本题答案为B）o符合结构化原则的三种基本控制结构是：选择结构、循环结构和【3】一。2009年 3 月填空题第3 题参考答案：顺序结构【解析】结构化程序设计的3 种基本逻辑结构为顺序结构、选择结构和循环结构。顺序结构是一种简单的程序设计结构，它是最基本、最常用的程序设计结构；选择结构又称为分支结构，包括简单分支和多分支选择结构；循环结构也叫重复结构，它根据给定的条件，判断是否需要重复执行某一相同的程序段。仅由顺序、选择（分支）和重复（循环）结构构成的程序是【4】程序。2 0 1 0 年 9月填空题第4题参考答案：结构化【解析】结构化程序是程序设计的先进方法和工具。在 1 9 9 6 年，B o e hm 和 J a c o p in i证明了程序设计语言仅使用三种基木控制结构足以表达出其他形式结构的程序设计方法。这三种基本控制结构就是顺序结构、选 择（分支）结构、循 环（重复）结构，故本题答案为结构化程序。2.3下面 选 项 中 不 属 于 面 向 对 象 程 序 设 计 特 征 的 是。A）继承性B）多态性C）类比性D）封装性2 0 0 7 年 4月选择题第4题参考答案：C【解析】面向对象程序设计的3个主要特征是：封装性、继承性和多态性。在面向对象方法中，实 现 信 息 隐 蔽 是 依 靠。A）对象的继承B）对象的多态C）对象的封装D）对象的分类2 0 0 7 年 9月选择题第3题参考答案：C【解析】封装是一种信息屏蔽技术，目的在于将对象的使用者和对象的设计者分开。用户只能见到对象封装界面上的信息，不必知道实现的细节。封装一方面通过数据抽象，把相关的信息结合在一起，另一方面也简化了接口。在面向对象方法中，不属于“对象”基 本 特 点 的 是。A）一致性B）分类性0多态性D）标识唯一性2 0 0 8 年 9月选择题第7题参考答案：A【解析】对象是面向对象方法中最基本的概念，它的基本特点有：标识唯一性、分类性、多态性、封装性和模块独立性。故本题答案为A）。定义无符号整数类为U I n t,下面可以作为类U I n t实 例 化 值 的 是。A）-3 6 9 B）3 6 9C）0.3 6 9D）整数集合合，2,3,4,5）2 0 1 1 年 3月选择题第1 0 题参考答案：B【解析】无符号整型un s ign e d in t,占 1 6 位，范围是 6 5 5 3 5。故本题答案为B）。面向对象方法中，继承是指。A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质C）各对象之间的共同性质D）类之间共享属性和操作的机制2 0 1 0 年 9月选择题第6题参考答案：D【解析】继承是面向对象方法的一个重要特征。广义地说，继承是指能够直接获得已有的性质和特征，不必重复定义它们。在面向对象的软件技术中，继承是指子类自动地共享基类中定义的数据和方法的机制，故答案为D）。第 二 早3.1软件是指。A）程序B）程序和文档C）算法加数据结构D）程序、数据与相关文档的完整集合2 0 0 7 年 9月选择题第1 题参考答案：D【解析】软件是程序、数据与相关文档的集合，相对于计算机硬件而言，软件是逻辑产品而不是物理产品，是计算机的无形部分。软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软件的是A）编 译 程 序 B）操 作 系 统 C）教务管理系统D）汇编程序2 0 0 9 年 3月选择题第5题参考答案：C【解析】软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）。应用软件是为解决某特定领域的应用而开发的软件；系统软件是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件；支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具性软件。编译程序、操作系统和汇编程序都属于系统软件；教务管理系统属于应用软件。软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于系统软件的是 oA）编辑软件B）操作系统C）教务管理系统D）浏览器2010年3月选择题第3题参考答案：B【解析】编辑软件、教务管理软件属于应用软件，操作系统属于系统软件，浏览器属于支撑软件，故本题答案选B。下面描述中，不属于软件危机表现的是_。A）软件过程不规范B）软件开发生产率低C）软件质量难以控制D）软件成本不断提高2010年9月选择题第4题参考答案：A【解析】软件危机是计算机软件在它的开发和维护过程中所遇到的一系列严重问题。主要表现在以下几个方面：软件需求的增长得不到满足；软件开发成本和进度无法控制；软件质量难以保证；软件可维护性差；软件的成本不断提高：软件开发生产率的提高赶不上硬件的发展和应用需求的增长。故答案选A）。软件生命周期可分为定义阶段,开发阶段和维护阶段。详细 设 计 属 于。A）定义阶段B）开发阶段C）维护阶段D）上述三个阶段2010年3月选择题第6题参考答案：B【解析】软件定义阶段的基本任务是确定软件系统的工程需要，分为软件系统的可行性研究和项目需求分析。软件开发阶段包括概要设计、详细设计、实现、组装测试和确认测试 5个阶段。维护阶段主要是软件的使用、系统维护和系统更新换代。软 件 生 命 周 期 是 指。A）软件产品从提出、实现、使用维护到停止使用退役的过程B）软件从需求分析、设计、实现到测试完成的过程C）软件的开发过程D）软件的运行维护过程2 0 1 0 年 9月选择题第5题参考答案：A【解析】通常将软件产品从提出、实现、使用维护到使用、退役的过程称为软件生命周期。故答案为A）。软 件 是【4】、数据和文档的集合。2 0 1 0 年 3月填空题第4题参考答案：程序【解析】本题考查软件的定义，软件是程序、数据和文档的集合。软件工程三要素包括方法、工具和过程，其中，_【3】_支持软件开发的各个环节的控制和管理。2 0 0 8 年 9月填空题第3题参考答案：过程【解析】软件工程包括三个要素：方法、工具和过程。软件工程方法为软件开发提供了如何做 的技术。工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件生命周期可分为多个阶段，一般分为定义阶段、开发阶段和维护阶段。编码和测试属 于.4 阶段。2 0 0 7 年 4月填空题第4 题参考答案：开发【解析】软件生命周期（S D L C,软件生存周期）是软件的产生直到报废的生命周期，周期内有问题定义、可行性分析、总体描述、系统设计、编码、调试和测试、验收与运行、维护升级到废弃等阶段，其中的编码和测试属于开发阶段。3.2数 据 流 图 中 带 有 箭 头 的 线 段 表 示 的 是。A）控制流B）事件驱动0模块调用D）数据流2 0 0 8 年 9月选择题第5题参考答案：D【解析】在数据流图中，矩形表示数据的外部实体，圆角的矩形表示变换数据的处理逻辑，双横线表示数据的存储，箭头表示数据流。在软件开发中，需 求 分 析 阶 段 可 以 使 用 的 工 具 是。A）N-S 图B）D FD 图C）P A D 图D）程序流程图2 0 0 8 年 9月选择题第6题参考答案：B【解析】数据流图简称D FD 图，采用图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示方法。所 以 D FD 图可以用于需求分析阶段。数据流程图（D FD 图）是。A）软件概要设计的工具B）软件详细设计的工具0结构化方法的需求分析工具D）面向对象方法的需求分析工具2 0 1 0 年 3月选择题第5题参考答案：C【解析】数据流图是结构化分析方法中使用的工具，它以图形的方式描绘数据在系统中流动和处理的过程。软件结构图是软件概要设计的工具，而详细设计是对概要设计的每个模块进行细化，U M L 是面向对象的需求分析的工具。在软件开发中，需 求 分 析 阶 段 产 生 的 主 要 文 档 是。A）可行性分析报告B）软件需求规格说明书C）概要设计说明书D）集成测试计划2 0 0 8 年 4月选择题第4题参考答案：B【解析】需求分析阶段的工作主要包括需求获取、需求分析、编写需求规格说明书和需求评审4个方面。产生的主要文档为软件需求规格说明书，它可以为用户、分析人员和设计人员之间的交流提供方便，可以直接支持目标软件系统的确认，又可以作为控制软件开发进程的依据。在软件开发中，需 求 分 析 阶 段 产 生 的 主 要 文 档 是。A）软件集成测试计划B）软件详细设计说明书C）用户手册D）软件需求规格说明书2011年 3 月选择题第4 题参考答案：D【解析】软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的的重要文档，故本题答案为D)。在结构化分析使用的数据流图(DFD)中，利用【5】对其中的图形元素进行确切解释。2007年 4 月填空题第5 题参考答案：数据字典【解析】数据字典(Data D ictio n ary,简 称 DD)就是用来定义数据流图中的各个成分的具体含义。数据字典的任务是对于数据流图中出现的所有被命名的图形元素在数据字典中作为一个词条加以定义，使得每一个图形元素的名字都有一个确切的解释。软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是一【1】2007年 9 月填空题第1 题参考答案：无歧义性【解析】软件需求规格说明书是需求分析阶段的最后成果，是软件开发中的重要文档之-包括正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等。其中最重要的特性是无歧义性，即需求规格说明书应该是精确的、无二义的，需求说明书越精确，则以后出现错误、混淆、反复的可能性越小。软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中【3】_阶段产生”软件需求规格说明书”。2009年 9 月填空题第3 题参考答案：需求分析【解析】需求分析阶段的工作主要包括需求获取、需求分析、编写需求规格说明书和需求评审等4 方面，产生的主要文档为软件需求规格说明书，它可以为用户、分析人员和设计