发帖
雷达卡
2010年计算机考研408真题及答案解析
题目一：
若元素 a, b, c, d, e, f 按顺序依次入栈，允许进栈与退栈操作交替进行，但不允许连续三次执行退栈操作。在该限制条件下，以下哪一个出栈序列是不可能得到的？
A. d, c, e, b, f, a
B. c, b, d, a, e, f
C. b, c, a, e, f, d
D. a, f, e, d, c, b
题目二：
某队列支持在两端进行入队操作，但仅允许在一端执行出队操作。若元素 a, b, c, d, e 依次进入该队列后进行出队，则下列哪一个出队序列是不可能实现的？
A. b, a, c, d, e
B. d, b, a, c, e
C. d, b, c, a, e
D. e, c, b, a, d
题目三：
一棵度数为4的树 T 中，包含20个度为4的结点、10个度为3的结点、1个度为2的结点以及10个度为1的结点。则该树 T 的叶结点（即度为0的结点）总数为：
A. 41
B. 82
C. 113
D. 122
题目四：
用 n（n≥2）个权值互不相同的字符构造哈夫曼树。关于该哈夫曼树的描述中，哪一项是错误的？
A. 该树一定是一棵完全二叉树
B. 树中不存在度为1的结点
C. 权值最小的两个结点必定是兄弟结点
D. 任意非叶结点的权值都不小于其下一层任一结点的权值
题目五：
对于一个含有7个顶点的无向图 G = (V, E)，要确保无论顶点如何连接，图 G 始终保持连通状态，则所需最少边数为：
A. 6
B. 15
C. 16
D. 21
题目六：
已知一个长度为16的顺序表 L，其中元素按关键字有序排列。若采用折半查找法查找一个不在 L 中的元素，则最多需要进行多少次关键字比较？
A. 4
B. 5
C. 6
D. 7
题目七：
使用递归方式对顺序表实施快速排序。关于递归调用次数的说法，正确的是：
A．递归次数不受初始数据排列的影响
B．每次划分后优先处理较长的子区间可减少递归次数
C．每次划分后优先处理较短的子区间可减少递归次数
D．递归次数与分区处理顺序无关
题目八：
对一组数据 (2, 12, 16, 88, 5, 10) 进行排序，前三趟的结果如下：
第一趟：2, 12, 16, 5, 10, 88
第二趟：2, 12, 5, 10, 16, 88
第三趟：2, 5, 10, 12, 16, 88
据此判断，可能采用的排序算法是：
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
题目九：
下列哪些措施有助于缩短程序的执行时间？
I. 提高 CPU 时钟频率
II. 优化数据通路结构
III. 对程序进行编译优化
A．仅 I 和 II
B．仅 I 和 III
C．仅 II 和 III
D．I、II 和 III
题目十：
设有四个整数以8位补码形式表示：r1=FEH，r2=F2H，r3=90H，r4=F8H。若将运算结果存入一个8位寄存器中，下列哪项乘法运算会发生溢出？
A．r1 × r2
B．r2 × r3
C．r1 × r4
D．r2 × r4
京公网安备 11010802022788号
