全国计算机二级公共基础知识考题分析.ppt

1、全国计算机等级考试二级公共基础知识，第一章数据结构和算法第二章编程基础第三章软件工程基础第四章数据库设置修订基础，第一章数据结构和算法，【例1】算法的时间复杂度取决于() a )问题的规模b )处理的数据的初始状态c )问题的难易度D)A )和b )【解答】d )【解析】在相同问题的规模下，算法的时间复杂性不仅与问题的规模有关，还与输入数据有关，即输入数据的全部可取值的范围和各种数据和数据集的输入本质上，摘要是指通过观察简单特殊的情况，最后总结出一般结论的算法设定修正方法。 【解答】归纳法【解析】归纳法的基本思想是，列举少量的特殊情况，经过分析，最后找出一般的关系。 本质上，总结是指通过观察简

2、单特殊的情况，最后总结一般性的结论。 页面1、页面2、【例3】如果算法p调用另一个算法q，而算法q调用算法p，则称为。 【回答】间接递归调用【解析】某算法明确调用自己的情况下称为直接递归，用别的算法将自己称为间接递归调用的情况下称为间接递归调用。 在示例4的数据结构中，数据结构在逻辑上分成() a )内部结构和外部结构b )线性结构和非线性结构c )紧凑结构和非紧凑结构d )动态结构和静态结构b )【解析】逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间一对一的关系，非线性结构表示数据元素之间一对多或多对一的关系。 页3、【例5】线性结构中要素间存在关系，树型结构中要素间存在一对多

3、的关系。 【答案】一对一的【解析】线性结构主要指要素间的一对一的关系，树结构指要素间的一对多的关系。 图6示出了对数据结构的两个基本运算是() a )插入和检索b )分类和分解c )插入和删除d )复制和修正【解答】c )【解析】一个数据结构中的要素节点有动态变化的可能性。 您可以根据需要或在处理过程中向单个数据结构添加新节点(称为插入运算)。 或者，可以删除数据结构的节点(称为删除运算)。 插入和删除是对数数据结构的两个基本运算。 另外，对数数据结构的运算包括搜索、分类、合并、分解、复制、修改等。 关于第4页、【例7】线性表，以下()的情况下请用连锁表表示。 a )总是需要随机访问的要素b

4、)总是插入和删除操作c )表中的要素必须占据连续的存储空间d )表中的要素的数量不变【解答】链表没有被依次存储，即在进行插入和删除操作时不需要移动大量的要素，因此， 在需要频繁进行插入和删除操作时应该采用的【例8】对于按长度为的顺序存储的线性表，随机插入删除要素时，移动的要素的平均个数为。 删除一个要素，平均移动的要素个数为(n1 n2 0)/n=(n1)/2。 当插入一个元素时，平均移动元素的数目为(n n1 n2 1)/n=(n 1)/2，而总移动元素的数目为n/2。 第5页和第9页的初始输入序列为1、2、3、4、5时，在一个堆栈中生成输出序列，并且在堆栈中不能生成以下的()序列。a)1、

5、2、3、4、5b)5、3、4、1、2c)4、3、2、1、5d)3、4、5、2、1【例10】判断一个堆栈ST (最多的要素是MaxSize )为空的条件是() 停止！ (1b )停止=1c )停止！=MaxSize1 D)STtop=MaxSize1【解答】b )【解析】从顺序堆栈的构造可以看出，本问题的解答是b )。 页面6、【例子11】一个队列的入队序列如果是、则队列的输出序列是() 从队列的先进先出特征可以看出，入队序列可以是、队列可以从【例12】循环队列中删除元素，通常是在检索元素之后。 【回答】从移动队列的指针【解析】队列的特征中，删除要素是在队列头进行的操作，所以首先取出队列头要素并

6、保存，然后移动队列头指针，使移动后的指针成为新的队列头指针。 页面7、【例13】可以用带表头节点的链表表示线性表，也可以用无表头节点的链表表示，前者的主要优点是() a )能够加快表的扫描的b )统一空表和非空表的处理的c )节省内存空间的d )能够提高对表元素的访问速度的【回答】b )【解析】在开头节点的链表中显示线性表时，使用空表和插入空链表时，只需将插入元素的指针字段指向报头节点的指针字段，将报头节点的指针字段指向新的元素，在非空链表中插入元素时，只要进行同样的操作，就可以插入。 如果链表中只有一个元素，则删除操作与常规的链表删除操作相同，只要修改指针指向下一个元素的指针所指向的元素即可

7、。 【例14】在双向链路表中，各节点具有2个指针域，一方指代前驱节点，另一方指代前驱节点。 【解答】后续节点【解析】从双向链接表的数据结构可知，双向链接表的各节点有两个指针域，这两个指针分别指向其前驱节点和后续节点。 页面8，【例15】关于二叉树的以下说法正确的是() a )二叉树的度是2 B )一个二叉树的度可以小于2 C )二叉树的任何节点的度也是2 D )任何二叉树中的至少一个节点的度是2【回答】b )【解析】从二叉树的几个概念可知a )选项，c )选项和d ) A)2h B)2h1 C)2h1 D)h 1【解答】b )【解析】在节点最少的情况下，除了根节点层只有一个节点之外，其馀的h

8、1层中有两个节点，节点总数为2(h1) 1=2h1，页面9、【例17】 对于a )空或仅一个节点b )完全二叉树c )二叉树d )深度等于其节点数的【回答】d )【解析】深度等于节点数的二叉树，每层只有一个节点，从上至下分别假定a1、a2、an，则后序扫描为这个问题的答案是d )选项。 如果一个二叉树的后续扫描序列是DACBE而中间扫描序列是DEBAC，则该前向扫描序列是() a )根据不同的扫描算法，容易发现前面的扫描序列是EDBAC；页面10、【例19】在下图的二叉树扫描中，其中顺序扫描序列是第一个扫描序列，顺序扫描序列是。【回答】DGBAECHIF ABDGCEFHI GDBEIHFCA

9、【解析】中序扫描：如果二叉树为空，则在(1)中依次扫描左子树；(2)访问根节点；(3)依次扫描右子树。 最初的扫描：二叉树为空时，如果不是空的操作(1)访问根节点(2)依次扫描左子树(3)依次扫描右子树。 后序扫描：二叉树为空时，空操作否则(1)扫描后序左子树(2)依次扫描右子树(3)访问根节点，页面11，【例20】有如右图所示的一棵树，(1)此树的根节点为。 (2)这个树叶的节点是。 (3)节点k3的度为。 (5)这棵树的深度。 (6)节点k3的子节点是。 (7)节点k3的父母节点是。 【回答】k1； k2、k5、k7、k4； 2； 3； 4； k5、k6； k1【解析】树是由n(n0 )个

10、节点构成的有限集合。 在n=0的情况下，存在称为(1)根(root )的特定节点，其称为空树。 它只是直接后项，但没有直接前项(2)除根节点以外的其他节点可以将不相交的有限集合T0，T1，Tm1划分为m(m0)个，每个集合ti (I=0，1，m1)是被称为根子树的树a ) 1，2，3 b ) 9，5，2，3 c ) 9，5，3 d ) 9，4，2，3【回答】d )【解析】第一次(118条问题的回答是d )。 图22设置按照各要素的值顺序排列的线性表(长度大于2 )，对于给定的值k分别利用顺序搜索法和二分搜索法来搜索与k相等的要素，在比较的次数分别为s和b，在搜索失败时，s和b的关系为() 一个

11、单词，一个单词，一个单词。 页13、【例23】已知的规则表为(12、18、24、35、47、50、62、83、90、115、134 )，用二分法查找100时，【解答】3【解析】结构的决策树如下图所示查找100时，为50、90、110 、【例24】在n个记录的顺序表中进行二分法检索，最大的比较次数为。 【回答】log2n 1【解析】相当于扫描完全二叉树的根到叶的长度，即log2n 1。 键码序列(16、9、4、25、15、2、13、18、17、5、8、24 )按照键码增加的顺序排列a)(15、2、4、18、16、5、8、24、17、9、13、25 ) 将无序表的第一元素作为比较标准，将它们依次与

12、下一元素进行比较，如果一个元素小于第一元素，则记录该元素的下标，然后用新的最小元素继续比较，如果还有更小的元素，则记录该下标，比较的本问题显然是，第一扫描结果最小的元素与第一元素交换位置在高速排序中，将针对各个划分的显示(或者子显示)划分成左右两个子显示，并且考虑这两个子显示，以下结论肯定是正确的()a )左右两个子表分别为顺序b )左侧的子表的要素为右侧的子表的要素c以下)左侧的子表的长度为右侧的子表的长度d以下)左侧和右侧的子表的要素的平均值相等的【解答】b )【解析】快进的基本思想是将重新排列的要素设为左右两个子表左侧子表元素的排序代码小于或等于基准元素的排序代码，右侧子表的排序代码大于

13、基准元素的排序代码，然后对整个表进行排序。 图27】n和27】n是用于在对n个元素的系列进行重新排序时重新排列所需的额外存储空间的视图； 堆叠排名的空间复杂度为o(1)。a ) o (log2n ) b (o (1) c (n ) d (nlog2n )【解答】b )【解析】。 时间复杂度在最好的情况下是O(nlog2n )，在平均的情况下是O(nlog2n )，在最坏的情况下是O(nlog2n )。 第16页，【例28】记录的关键字排序50、26、38、80、70、90、8、30、40、20，各回合的排序结束时的结果是： 50、26、30的a )快速排序b )鼓泡排序c )希尔排序【例29】

14、对n个元素的排列进行冒泡排序时，最少的比较次数是。 【答案】n1【解析】初始要素为正顺序时，第一个回合比较n1次，交换数为0，完成排序。 页面17、【例30】按照插入法从小到大的顺序对以下4个表进行排序，比较次数最少的是() a)(94、32、40、90、80、46、21、69)b)(21、32、46、40、80、69、90、94相反，在排序对象的列中存在按不按关键字升序排序的记录的情况下，总比较次数为最大值(n 2)(n1)/2 在a )选项、b )选项、c )选项、d )选项这4个选项中，b )选项几乎是规则的，可知需要比较的次数最少。 第二章编程基础，页面18，【例1】为了确立良好的编程风格，以下叙述正确。 a )符号的命名语法b )程序简单、明确、可读性好的c )程序有无注释d )程序的执行效率【解答】b )【解析】本问题主要考虑程序设定修正应遵循的几个原则，良好的程序设定修正风格可以减少代码错误， 能够减少程序读取时间的程序是人工制作的，为了程序的测试和维护，多读取和跟踪程序，强调程序设定修改的风格整体上很简单明了，程序能够理解(a)1行只写1个句子b )程序制作应该优先效率c )尽量避免暂定变量d的使用)避免不必要的迁移【回答】【b )【解