该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单选题（每题 2 分，共 30 分）

1. 以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（ ）。{{ select(1) }}

• C++中调用printf函数
• C++中调用用户定义的类成员函数
• C++中构造一个 class 或 struct
• C++中构造来源于同一基类的多个派生类

2. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（ ）条边。{{ select(2) }}

• 7
• 21
• 42
• 49

3. 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。{{ select(3) }}

• a
• b
• c
• d

4. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。{{ select(4) }}

• 1
• 2
• 3
• 4

5. 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有( )个顶点{{ select(5) }}

• 10
• 12
• 8
• 16

6. 设 $G$ 是有 $n$ 个结点、$m$ 条边（$n \le m$）的连通图，必须删去 $G$ 的（ ）条边，才能使得 $G$ 变成一棵树。{{ select(6) }}

• m - n + 1
• m - n
• m + n + 1
• n - m + 1

7. 有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。{{ select(7) }}

• 9
• 10
• 11
• 12

8. 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。{{ select(8) }}

• $N-1$
• $N$
• $N+1$
• $N^2$

9. 以下对数据结构的表述不恰当的一项为：（ ）{{ select(9) }}

• 图的深度优先遍历算法常使用的数据结构为栈
• 栈的访问原则为后进先出，队列的访问原则是先进先出
• 队列常常被用于广度优先搜索算法
• 栈与队列存在本质不同

10. 考虑一个有向无环图，该图包含4条有向边：($1 , 2$) , ($1, 3$) , ($2, 4$)和($3, 4$) 。以下哪个选项是这个有向无环图的一个有效的拓扑排序?{{ select(10) }}

• 4,2,3,1
• 1,2,3,4
• 1,2,4,3
• 2,1,3,4

11. 有向图中每个顶点的度等于该顶点的( )。{{ select(11) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

12. 元素$R_1,R_2,R_3,R_4,R_5$ 入栈的顺序为 $R_1,R_2,R_3,R_4,R_5$。如果第一个出栈的是 $R_3$，那么第5个出栈的不可能是( ){{ select(12) }}

• $R_1$
• $R_2$
• $R_4$
• $R_5$

13. 双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是（ ）。{{ select(13) }}

• p->rlink->llink = p->rlink; p->llink->rlink = p->llink; delete p;
• p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
• p->rlink->llink = p->llink; p->rlink->llink->rlink = p->rlink; delete p;
• p->llink->rlink = p->rlink; p->llink->rlink->llink = p->llink; delete p;

14. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素 d 已经出栈，则可能的入栈顺序是（ ）。{{ select(14) }}

• a,d,c,b
• b,a,c,d
• a,c,b,d
• d,a,b,c

15. 链表不具有的特点是( )。{{ select(15) }}

• 不必事先估计存储空间
• 可随机访问任一元素
• 插入删除不需要移动元素
• 所需空间与线性表长度成正比

16. 链表和数组的区别包括（ ）。{{ select(16) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可以动态调整
• 以上均正确

17. 一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（ ）。{{ select(17) }}

• 2
• 3
• 4
• 5

18. 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ ）。{{ select(18) }}

• 10
• 11
• 12
• 13

19. 已知一棵二叉树有10 个节点，则其中至多有（ ）个节点有 2 个子节点。{{ select(19) }}

• 4
• 5
• 6
• 7

20. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF, 则其前序遍历序列为（）。{{ select(20) }}

• ABCDEFGHIJ
• ABDEGHJCFI
• ABDEGJHCFI
• ABDEGHJFIC

21. 如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（ ）种不同形态?{{ select(21) }}

• 16
• 15
• 17
• 32

22. 假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码 ?{{ select(22) }}

• 1111,1110,101,100,110,0
• 1010,1001,1000,011,010,00
• 000,001,010,011,10,11
• 1010,1011,110,111,00,01

23. 给定一棵二叉树，其前序遍历结果为：ABDECFG, 中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么 ?{{ select(23) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA