《计算机二级考试公共基础知识无纸化考试要点和真题》由会员分享，可在线阅读，更多相关《计算机二级考试公共基础知识无纸化考试要点和真题（13页珍藏版）》请在金锄头文库上搜索。
1、公共基础知识在无纸化考试中考10 个选择题，共10分第一章：数据结构和算法1、算法：（1）算法的复杂度包括 时间复杂度和空间复杂度。（2）时间复杂度用算法的基本运算次数来度量（3）空间复杂度指执行这个算法所需要的内存空间。 考点一：时间复杂度和空间复杂度 习题：（1）算法的时间复杂度是指（D）本题选D课本46面选择1原题A）算法的执行时间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的基本运算次数（2）算法的空间复杂度是指（A）。本题选A课本46选择2原题A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行
2、过程中所需要的临时工作单元数（ 3）下列叙述中正确的是 本题选 DA）算法就是程序B）设计算法时只需要考虑数据结构的设计C） 设计算法时只需要考虑结构的可靠性 D） 以上三种说法都不对（4）算法的有穷性是指 本题选 A 课本2面A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用2、数据结构线性结构：只有一个根节点、最多一个前件，最多一个后件 考点二：线性结构和非线性结构的区别，习题：（1）.下列数据结构中，属于非线性结构的是（C）。A.循环队列B.带链队列C.二叉树D.带链栈（2）下列叙述中正确的是本题选 B 课本14面线性结
3、构 只有一个根结点 每个结点最多一个前件，一个后件A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构3、线性表4、栈和队列栈限定在一端进行插入和删除的线性表。特点是先进后出或后进先出。队列是允许在一端进行插入而在另一端进行删除的线性表。特点是先进先出或后进后出 考点三：栈和队列，栈先进后出，队列先进先出，习题：（1）下列关于栈叙述正确的是（A）A）栈顶元素最先能被删除B）栈顶元素最后才能被删除C）栈底元素永远不能被删除 D）以上三种说法都不对本题选A考点课本20面：栈的特点，先进后出，所以栈顶元素最先能被
4、删除 下列数据结构中,能够按照”先进后出”原则存取数据的是（B）。本题选B课本20面A.循环队列B.栈C.队列D.二叉树（3）下列对队列的叙述正确的是 （D）。A）队列属于非线性表B）队列按先进后出的原则组织数据C）队列在队尾删除数据 D）队列按先进先出原则组织数据4）下列叙述中正确的是B）队列是一种后进先出的线性表A）栈是一种先进先出的线性表D）以上三种说法都不对C）栈与队列都是非线性结构5）下列叙述中正确的是A ）栈是“先进先出”的线性表C）循环队列是非线性结构本题选 D 以上三种说法都不对B ）队列是“先进后出”的线性表D ）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构本题选
5、 D 考点 栈 先进后出、队列先进先出、循环队列是线性结构（6）一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出 栈的顺序是A）12345ABCDE B） EDCBA54321 C） ABCDE12345 D） 54321EDCBA本题选 B 课本20面 栈的特点，先进后出（7）支持子程序调用的数据结构是本题选 AA ）栈B ）树 C）队列 D ）二叉树（8）下列叙述中正确的是A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的
6、变化而动态变化D）上述三种说法都不对本题选C（9）下列关于栈的叙述中正确的是本题选 B 课本20面A）栈按“先进先出”组织数据B）栈按“先进后出”组织数据C）只能在栈底插入数据 D）不能删除数据（10）下列对队列的叙述正确的是 。A）队列属于非线性表B）队列按”先进后出”的原则组织数据C）队列在队尾删除数据D）队列按先进先出原则组织数据本题选 D 课本 46 面 选择 5 队列的顺序存储结构一般采用循环队列的形式 循环队列中元素个数计算公式。 尾指针头指针时 尾指针-头指针例如：容量为15 的循环队列中，头指针为6，尾指针为9，循环队列中共有（ ）个元素。答:9-6=3 尾指针头指针时 尾指针
7、-头指针+容量.例如：容量为15 的循环队列中，头指针为6，尾指针为3，循环队列中共有（ ）个元素。答:3-6+15=12 栈中元素个数的计算。栈顶-栈底+1 例如：已知栈顶指针为8，栈底指针为1，栈中共有8 个元素。 考点四：循环队列 习题：（1）下列叙述中正确的是A） 循环队列是队列的一种链式存储结构 B） 循环队列是一种逻辑结构C）循环队列是非线性结构D）循环队列是队列的一种顺序存储结构本题选D,考点课本P22页，队列的顺序存储结构一般采用循环队列的形式（2）对于循环队列，下列叙述中正确的是本题选D课本22面A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针
8、D）队头指针可以大于队尾指针，也可以小于队尾指针（3）下列叙述中正确的是本题选D课本22面A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队的中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队的中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定5、链表（1）下列叙述中正确的是A）程序执行的效率与数据的存储结构密切相关B）程序执行的效率只取决于程序的控制结构C）程序执行的效率只取决于所处理的数据量D）以上三种说法都不对本题选 A 课本 13 面（2）下列叙述中正确的是A）数据的逻辑结构与存储结构必定是一一对应
9、的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对本题选 D（3）下列关于线性链表的叙述中，正确的是A）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C）进行插入与删除时，不需要移动表中的元素。D）以上三种说法都不对本题选C考点课本24面链式存储方式存储空间不连续，逻辑关系不一致，所以A,B是错误的 课本 29 面， 30 面，插入和删除不需要移动表中元素。（4）下列叙述中正确的是A
10、）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对本题选B链式存储结构多一个指针域（5）下列叙述中正确的是A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间本题选 A 课本16面和课本24面6、树与二叉树性质 1：第 k 层上最多 2k-1 个结点。性质3：度为0
11、的节点（叶子结点）总是比度为2的节点多一个 考点五：二叉树性质1 和性质 3 习题：（1）一棵二叉树共有 25个结点，其中 5个是叶子结点，则度为1 的结点数为A） 4B） 10C） 6D）16本题选D考点课本P34面性质3，二叉树中度为0的节点永远比度为2的节点多一个所以 n0=5 n2=4 n1=n-n0-n2=25-5-4=16（2）下列关于二叉树的叙述中，正确的是A）叶子结点总是比度为2的结点少一个B）叶子结点总是比度为2的结点多一个C）叶子结点数是度为2的结点数的两倍D）度为2的结点数是度为1的结点数的两倍本题选 B 课本34面 性质3，度为0的节点（叶子节点）总是比度为2的节点多一
12、个（3）某二叉树有 5 个度为 2 的结点，则该二叉树中的叶子结点数是A ） 10 B） 8 C） 6 D） 4本题选 C 课本34面 二叉树性质3度为0的节点总是比度为2的节点多一个（4）某二叉树中有n个度为2的结点则该二叉树中的叶子结点数为本题选A课本34面 A） n+1 B ） n-1 C） 2n D） n/2（5）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层） A） 3B） 4 C） 6 D） 7本题选 D(6) 棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为本题选A 70+80+69=219A) 219 B) 221
13、C) 229 D) 231 二叉树的遍历。前序(根左右)中序(左根右) 后序(左右根)遍历方法注意上课笔记。 考点六：二叉树的遍历习题：1)对下列二叉树进行前序遍历的结果为A) DYBEAFCZX B) YDEBFZXCA C) ABDYECFXZ D) ABCDEFXYZ 本题选 C 课本 38 面 考遍历按上课所讲的要点解7、查找二分法查找只适用于顺序存储的有序表。最坏情况下二分查找只需要比较Log2n次，顺序查找比较n次 考点七:查找比较次数，习题：(1) 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是(C)A) O(n) B) O(n2 ) C) O(log2n) D
14、) O(nlog2n)(2) 下列叙述中正确的是A) 对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB) 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)C) 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)D) 对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n) 本题选 A 课本 39 面 二分法只适用与顺序存储的有序表，有序链表不能二分法查找8、排序1、冒泡排序法、简单插入排序法、简单选择排序法德比较次数为n(n-l)/2。2、 希尔排序的比较次数为 n1.53、堆排序的比较次数为 nLog2n 考点八：
15、排序比较次数习题(1) 下列排序方法中，最坏情况下比较次数最少的是( D )。A )冒泡排序 B )简单选择排序 C)直接插入排序D )堆排序 本题选D课本48面堆排序的比较次数是nlog尹 其他3种都是n(n-1)/2(2) 冒泡排序在最坏情况下的比较次数是(A)A)n(n +1)/2B)nlog? C)n(n-1)/2 D)n/2(3) 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是本题选C课本40面A) O(n) B) O(n2) C) O(log2n) D) O(nlog2n)(4) 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是本题选D课本45面 A)快速排序B)冒泡排序C)直接插入排序D)堆排序、程序设计方法与风格。1、程序设计方法经过了结构化程序设计和面向对象的程序设计阶段2、程序设计风格：清晰第一，效率第二3 、符号名
