2013年9月二级C题库(选择)解读.doc

2013年9月计算机等级考试（二级C）选择题题库 考点一 数据结构与算法 1.下列叙述中正确的是（???）。 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 解题思路：线性链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，因此一般要多于顺序存储结构，选项B）正确。答案：D 2.下列叙述中正确的是（???）。 A）栈是一种先进先出的线性表 B）队列是一种后进先出的线性表 C）栈与队列都是非线性结构 D）以上三种说法都不对 本题答案为:D 题目解析:栈是一种先进后出的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构，因此本题答案为D）。 .一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（???）。 A）16 B）10 C）6 D）4 本题答案为:A 题目解析:根据二叉树的性质3：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个，所以本题中度为2的结点是5-1＝4个，所以度为1的结点的个数是25-5-4＝16个，选择A）。 在长度为n的有序线性表中进行二分法查找，最坏情况下需要比较的次数是（???）。 A）O(n) B）O(n2) C）O(log2n) D）O(nlog2n) 本题答案为:C 题目解析:当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较log2n 次，而顺序查找需要比较n次，因此本题答案为C）。5.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（???）。 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA 本题答案为:B 题目解析:栈按后进先出的原则组织数据，因此入栈最晚的最先出栈，因此本题答案为B）。 6.下列叙述中正确的是（???）。 A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）在栈中，栈中元素不会随栈底指针与栈顶指针的变化而动态变化 本题答案为:C 题目解析:栈是先进后出的数据结构，在对栈操作的整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来完成，因此本题答案C）。 7.下列数据结构中，属于非线性结构的是（???）。 A）循环队列 B）带链队列 C）二叉树 D）带链栈 本题答案为:C 题目解析:树是简单的非线性结构，因此二叉树作为树的一种属于非线性结构，答案C）正确。 8.下列叙述中正确的是（???）。 A）算法就是程序 B）设计算法时只需要考虑数据结构的设计 C）设计算法时只需要考虑结果的可靠性 D）以上三种说法都不对 本题答案为:D 题目解析:算法是指解题方案的准确而完整的描述，算法既不等于程序，也不等于计算方法，因此A）错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构，因此B）和C）错误。 9.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（???）。 A）10 B）8 C）6 D）4 本题答案为:D 题目解析:根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子结点总比度为2的结点多一个，因此本题中度为2的结点为1-1＝0个，据此可以知道本题目中的二叉树的每一个结点都有一个分支，所以共7个结点共7层，即深度为7，选择D）。 10.下列关于二叉树的叙述中，正确的是（???）。答案：B A）叶子结点总是比度为2的结点少一个 B）叶子结点总是比度为2的结点多一个 C）叶子结点数是度为2的结点数的两倍 D）度为2的结点数是度为1的结点数的两倍 解题思路：根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个，因此答案为B）。 11.下列关于栈的叙述正确的是（???）。 A）栈按“先进先出”组织数据 B）栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据 本题答案为:B 题目解析:栈是只允许在同一端进行插入和删除运算的线性表，按“先进后出”组织数据，因此本题答案为B）。 12.下列叙述中正确的是（???）。答案：A A）顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节