一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1.以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（ ）。
A. C++ 中调用 printf 函数
B. C++ 中调用用户定义的类成员函数
C. C++ 中构造一个 class 或 struct
D. C++ 中构造来源于同一基类的多个派生类
答案：A
【解析】printf是C语言中就可以使用的函数，而c++中定义类或结构体，对象调用成员函数，构造派生类，都是面向对象语言才能支持的操作。
2.有 6 个元素，按照 6 、 5 、 4 、 3 、 2 、 1 的顺序进入栈 S ，请问下列哪个出栈序列是非法的
（ ）。
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
答案：C
【解析】入栈出栈序列问题，解题方法为：如果数值a出栈，那么在a前入栈的元素要么已出栈，要么顺序地排列在栈中。
C选项中，当4出栈时，4前入栈的6,5一定都在栈中，情况为：栈底-6-5。所以接下来不可能是6出栈，只能是5出栈。
3.运行以下代码片段的行为是（ ）。
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;
A. 将 x 的值赋为 201
B. 将 y 的值赋为 101
C. 将 q 指向 x 的地址
D. 将 p 指向 y 的地址
答案：D
【解析】p是指向x的指针，也就是x的地址。q是指向y的指针，也就是y的地址。把q赋值给p，也就是让p从指向x的指针变为指向y的指针。
4.链表和数组的区别包括（ ）。
A. 数组不能排序，链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定，链表大小可动态调整
D. 以上均正确
答案：C
【解析】A 选项，数组可以排序；B 选项，链表不能存 储比数组更多的信息；C 选项正确
5.对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S 、出栈 S 、进队列 Q 、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1 、 e2 、 e3 、 e4 、 e5 和 e6 进栈，队列 Q 依次有数据 e2 、 e4 、 e3 、e6 、 e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
A. 2
B. 3
C. 4
D. 6
答案：B。【解析】栈的特点是后进先出，队列的特点是先进先出。依题意模拟 过程，括号中表示栈中数据的个数：e1 入栈(1)，e2 入栈(2)，e2 出 栈(1)，e3 入栈(2)，e4 入栈(3)，e4 出栈(2)，e3 出栈(1)，e5 入栈(2)， e6 入栈(3)，e6 出栈(2)，e5 出栈(1)，e1 出栈(0)。栈的容量至少为 3
6.对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 + 、 - 、 * 是运算符。
A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d
答案：B。【解析】中缀表达式转换为前缀表达式的方法：①将 所有运算按照优先级加上小括号，(a+((b-c)*d)) ②将运算符移到对应小括号前，+(a*(-(b c) d) ③去掉小括号，+a*-bcd
7.假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%,29% 。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为（ ）位。
A. 1
B. 2
C. 2 或 3
D. 3
答案：B
考察哈夫曼树和哈夫曼编码。构建哈夫曼树的方法为：每次选取两个权值最小的结点，加上双亲结点构成一棵树。
初始一共有5个结点，每个结点的权值分别为：a:10,b:15,c:30,d:16,e:29
选择权值最小的两个结点a和b，设结点f是a、b的双亲，权值25。
选择权值最小的两个结点f和d，设结点g是f、d的双亲，权值41。
选择权值最小的两个结点c和e，设结点h是c、e的双亲，权值59。
选择权值最小的两个结点g和h，设结点i是g、h的双亲，权值100。
构成的树如下图所示。
在哈夫曼树中，从根结点开始，每向下走一层编码多1位。根据构造出来的哈夫曼树可知，d的编码是两位。
8.一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
A. 8 、 18
B. 10 、 18
C. 8 、 19
D. 10 、 19
答案：C
【解析】9 的父结点是 4，兄弟结点是 8，左儿子结点 是 18，右儿子结点是 1
9.考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A. N-1
B. N
C. N+1
D. N^2
答案：B
【解析】n 个点有向连通图，至少有 n 条边，连成一 圈，邻接矩阵中非零元素即为边数最少为
10.以下对数据结构的表述不恰当的一项为：（ ）。
A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则为后进先出，队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
D. 栈与队列存在本质不同，无法用栈实现队列。
答案：D【解析】使用两个栈，一个栈存放入队的操作，另一 个栈用来出队，即可用栈实现队列
11.以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中， next 域为结点的直接后继， prev 域为结点的直接前驱）：（ ）。
A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
答案：D
观察选项可知，四个选项为这四个语句的不同排列：
s->prev=p;
s->next=p->next;
p->next=s;
p->next->prev=s;
这里发生变化，又可能给其它量赋值的就是p->next。
使p->next发生变化的语句为：p->next=s;
而s->next=p->next;与p->next->prev=s;中用到的都应该是变化前的p->next，指向的是原来p的下一个结点。
所以p->next=s;应该放在最后，选D。
12.以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的
答：选B
考察排序的稳定性。选择排序是不稳定的，冒泡、插入、归并都是稳定的。
13.八进制数 32.1 对应的十进制数是（ ）。
A. 24.125
B. 24.250
C. 26.125
D. 26.250
答：选C
进制转换问题，八进制转十进制的方法为：按位权展开。
整数部分：3 ∗ 8 1 + 2 ∗ 8 0 = 26 3*8^1+2*8^0=263∗81+2∗80=26
小数部分：1 ∗ 8 − 1 = 0.125 1*8^{-1}=0.1251∗8−1=0.125
因此八进制32.1为十进制26.125，选C。
14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有
（ ）个内容互不相同的子串。
A. 12
B. 13
C. 14
D. 15
所有子串共有 16 个，刨去重复的子串"a", "b", "ab"，余下 13 个不重复的子串。
15.以下对递归方法的描述中，正确的是：（ ）
A. 递归是允许使用多组参数调用函数的编程技术
B. 递归是通过调用自身来求解问题的编程技术
C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D. 递归是将用某种高级语言转换为机器代码的编程技术
答案：B。
选项A：不清楚什么叫“多组参数调用函数”，任意一个带参函数，都可以用多组参数来调用。
选项B：论述正确。
选项C：面向对象编程（或者说“类”）是面向对象和数据而不是功能和逻辑的编程语言模型。
选项D：编译是将用某种高级语言转换为机器代码的编程技术