2014年计算机二级公共基础知识总结第一章(7)

　　查看汇总：2014年计算机二级公共基础知识总结汇总

　　例题详解

　　一、选择题

　　【例1】算法的时间复杂度取决于_______。(考点2)

　　A)问题的规模 B)待处理的数据的初态

　　C)问题的难度 D)A)和B)

　　解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。

　　答案：D)

　　【例2】在数据结构中，从逻辑上可以把数据结构分成_______。(考点3)

　　A)内部结构和外部结构 B)线性结构和非线性结构

　　C)紧凑结构和非紧凑结构 D)动态结构和静态结构

　　解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B)。

　　答案：B)

　　【例3】以下_______不是栈的基本运算。(考点5)

　　A)判断栈是否为素空 B)将栈置为空栈

　　C)删除栈顶元素 D)删除栈底元素

　　解析：栈的基本运算有：入栈，出栈(删除栈顶元素)，初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。

　　答案：D)

　　【例4】链表不具备的特点是_______。(考点6)

　　A)可随机访问任意一个结点 B)插入和删除不需要移动任何元素

　　C)不必事先估计存储空间 D)所需空间与其长度成正比

　　解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A)。

　　答案：A)

　　【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是_______。(考点8)

　　A)ACBED B)DEABC

　　C)DECAB D)EDBAC

　　解析：后序遍历的顺序是"左子树-右子树-根结点";中序遍历顺序是"左子树-根结点-右子树";前序遍历顺序是"根结点-左子树-右子树"。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案为D)。

　　答案：D)

　　【例6】设有一个已按各元素的值排好序的线性表(长度大于2)，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是_______。(考点9)

　　A)s=b B)s>b C)s

　　解析：对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为[log2n]+1。当n≥2时，显然n+1>[log2n]+1。

　　答案：B)

　　【例7】在快速排序过程中，每次划分，将被划分的表(或子表)分成左、右两个子表，考虑这两个子表，下列结论一定正确的是_______。(考点11)

　　A)左、右两个子表都已各自排好序

　　B)左边子表中的元素都不大于右边子表中的元素

　　C) 左边子表的长度小于右边子表的长度

　　D)左、右两个子表中元素的平均值相等

　　解析：快速排序基本思想是：任取待排序表中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。

　　答案：B)

　　二、填空题

　　【例1】问题处理方案的正确而完整的描述称为_______。(考点1)

　　解析：计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

　　答案：算法

　　【例2】一个空的数据结构是按线性结构处理的，则属于_______。(考点4)

　　解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属于线性结构，否则属于非线性结构。

　　答案：线性结构

　　【例3】设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数为_______。(考点7)

　　解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加1。

　　因此树的结点数为1×4+2×2+3×1+4×1+1=16。叶子结点数目等于树结点总数减去度不为0的结点数之和，即16-(4+2+1+1)=8。

　　答案：8

　　【例4】二分法查找的存储结构仅限于_______且是有序的。(考点10)

　　解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)。

　　答案：顺序存储结构

　　相关推荐：

　　计算机等级考试合格标准

　　2014年计算机等考上机六大注意事项

　　考试吧：2014年3月计算机等考真题及答案解析专题