计算机专业（基础综合）模拟试卷291
单选题
1.若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。(D)
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
解析：4个选项所给序列的进、出栈操作序列分别为：
选项A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop
选项B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop
选项C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop
选项D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。
2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。(C)
A. b，a，c，d，e
B. d，b，a，c，e
C. d，b，c，a，e
D. e，c，b，a，d
解析：根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。
假设L代表从左端入队，R代表从右端入队，出队都是从左端L出。四个选项所给序列的进队操作序列分别为：
选项A：aL(或aR)，bL，cR，dR，cR
选项B：aL(或aR)，bL，cR，dL，eR
选项C：不可能出现
选项D：aL(或aR)，bL，cL，dR，cL
3.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。
(D)
A.
B.
C.
D.
解析：线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息。解题思路较简单。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b：结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。所以正确选项为D。
4.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是( )。
(C)
A. 13、48
B. 24、48
C. 24、53
D. 24、90
解析：题目中，插入48以后，树根结点的平衡因子由-1变为-2，失去平衡。这属于RL(先右后左)型平衡旋转，需做两次(先右旋后左旋转)旋转操作。过程如下图所示：
5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是( )。(B)
A. 41
B. 82
C. 113
D. 122
解析：根据二叉树的性质3的推广公式：N0=1+N2+2N3+…+(m-1)Nm可直接在将数据带入公式，即N0=1+N2+2N3+3N4=1+1×1+2×10+3×20=82。树T的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。
6.对n(n≥2)个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。(A)
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
解析：哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A错误；哈夫曼树中没有度为1的结点，选项B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q与其兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
7.若无向图G=(V，E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是( )。(C)
A. 6
B. 15
C. 16
D. 21
解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意6个结点构成完全连通子图G1，需n(n-1)／2=6×(6-1)／2=15条边，然后再添加一条边将第7个结点与GI连接起来，共需16条边。本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况
本文档预览：3000字符，共22173字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
