文档介绍：2010计算机专业基础综合试题
其中:原题命中15分!直接命中72分!间接命中39分!
一、选择题
1. (2010年试题第1题)若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是( D )
A. d,c,e,b,f,a ,b,d,a,e,f
C. b,c,a,e,f,d ,f,e,d,c,b
(翔高辅导书)《模拟试题(十)》第2题有A,B,C,D,E 5个元素按次序入栈,在各种可能的出栈次序中,以元素C,D最先出栈的序列中,下列正确的一组是( B )
CDABE CDBEA
CDABE CDAEB
命中情况:均是考查对堆栈的基本操作,并且都在基本操作的基础上添加了限制条件。
命中类型:直接命中(2分)
2. (2010年试题第3题)下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是( D )
(翔高辅导书)《习题精编》第44页综合应用题题第1题设一棵二叉树如下图所示:
(4)试画出该二叉树的一棵后序线索二叉树。
命中情况:均是考查线索二叉树的概念,并且都是后序线索二叉树。
命中类型:直接命中(2分)
3. (2010年试题第4题)在下图所示的平衡二叉树中,插入关键宇48后得到一棵新平衡二叉树。在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是( C )
、48 、48 、53 、90
(翔高辅导书)《习题精编》第48页综合应用题第3题设结点序列F={18,36,30,42,45,48,60},用平衡二叉树插入算法将F中的结点依次插入,建立一棵平衡二叉树,试画出这棵树的建立的过程。
命中情况:均是考查平衡二叉树的建立,如何旋转达到平衡。
命中类型:间接命中(2分)
4. (2010年试题第5题)在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点;10个度为1的结点,则树T的叶结点个数是( B )
(翔高辅导书)《习题精编》第42页单项选择题第2题树L中度为1,3,5,7和9的结点个数分别为10,8,6,4,2,则树L中的叶子的个数是( A )
命中情况:均是考查树的基本概念。
命中类型:直接命中(2分)
5. (2010年试题第6题)对n(n≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是( A )
(翔高辅导书)《模拟试题(三)》第4题关于哈夫曼树,下列说法正确的是( C )
,权值相同的叶子结点都在同一层上
,权值较大的叶子结点一般离根结点较远
,路径上权值较大的结点离根较远
,当两个字符聘频率相同时,其编码也相同,对于这种情况就作特殊处理
命中情况:均是考查哈夫曼树的基本概念。
命中类型:间接命中(2分)
6.(2010年试题第7题)若无向图G=(V,E)中合有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是( C )
(翔高辅导书)《习题精编》第73页单项选择题第3题一个有n个顶点的连通无向图最少有( C )条边。
A. n B. n+1 C. n-1 D. n/2
命中情况:均是考查图的连通性。
命中类型:间接命中(2分)
7. (2010年试题第8题)对下图进行拓扑排序,可以得到不同拓扑序列的个数是(B)
A. 4 B. 3 C. 2 D. 1
(翔高辅导书)《模拟试题(五)》第7题下列4组含C1~C7的结点序列中,( D )是下图所示的有向图的拓扑排序。
,C2,C6,C7,C5,C4,C3 ,C2,C6,C3,C4,C5,C7
,C4,C2,C3,C5,C6,C7 ,C7,C4,C1,C2,C6,C7
命中情况:均是考查拓扑排序的相关知识,并且都涉及到多种拓扑排序结果。
命中类型:直接命中(2分)
8. (2010年试题第9题)已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素,则关键字的比较次数最多是( B )
A. 4 B. 5 D. 7
(翔高辅导书)《模拟试题(五)》第