1. 以下哪种功能没有涉及C++语言面向对象特性的支持？

A. C++中调用printf函数

B. C++中调用用户定义的类成员函数。

C. C++中构造一个class或struct。

D. C++中构造来源于同一基类的多个派生类。

题解思路

类成员函数属于面向对象，class与struct属于面向对象，基类里的派生类也属于面向对象，只有printf和面向对象没有关系。

---

2. 对表达式a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A. *+a-bcd

B. +a*-bcd

C. abc-d*+

D. abc+-d

题解思路

将最先运算的b-c提出运算符至b前，去括号变成a+-bc*d。 再将其次运算的*d提出运算符至-bc前,变成a+*-bcd。 最后将最后运算的a+提出运算符至最前,变成+a*-bcd。

---

3. 假设字母表{a,b,c,d,e}在字符串中出现的频率分别为10%,15%,30%,16%,29%，若用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度为（ ）。

A. $1$

B. $2$

C. $2$ 或 $3$

D. $3$

题解思路

先将10和15构成25的两子树，再将25和16构成41的两子树，然后将29和30构成59的两子树，最后将41和59构成100的两子树，根据哈夫曼编码方式可得d是2。

---

4. 一棵有n个节点的二叉树用数组进行存储和表示，已知根节点存储在数组的第一个位置。若存在第九个位置的节点存在兄弟节点和两个子节点，则它的兄弟节点和右子节点的位置分别是（ ）。

A. $8、18$

B. $10、18$

C. $8、19$

D. $10，19$

题解思路

我们要知道，如果i是奇数，数组第i个位置的节点就是右孩子，它的兄弟节点在第i-1个位置，右孩子在第i*2个位置，根据此公式可以看出来选C。

---

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

A. $N-1$

B. $N$

C. $N+1$

D. $N^2$

题解思路

N个顶点的有向连通图一定是一个有环图，且每一个点都在环上，不然一定会存在两个点无法到达。故选B。

---

6. 以下对数据结构的表述不恰当的一项为（ ）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B. 栈的访问原则为后进先出，队列的访问原则是先进先出。

C. 队列常常被用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。

题解思路

栈和队列虽然不同，但是两个栈可以模拟一个队列。

---

14. 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 （ ）个内容互不相同的子串。

A. $12$ B. $13$ C. $14$ D. $15$

题解思路

字符串 abcab的字串有a,b,c,ab,bc,ca,abc,bca,cab,abca,bcab,abcab,空共13个，故选B。

---