2、业精于勤，荒于嬉；行成于思，毁于随——韩愈
请将所有答案做在答题纸上，在试题纸上做解答按零分处理
数据结构的算法试题可使用C或C++语言的风格描述
一．单项选择题 (本大题共10小题，每小题2分，共20分)
将答案选项与题目编号写在答题纸上，错选或未选均无分
1. 将长度为 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 ( )
A. O( n ) B. O( 1 )
C. O( m ) D. O( m + n )
2. 设数组 data[ m ] 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 的值为 ( )
A. front = front + 1 B. front = ( front + 1 ) % ( m - 1 )
C. front = ( front - 1 ) % m D. front = ( front + 1 ) % m
3. 一个非空广义表的表头 ( )
A. 不可能是子表 B. 只能是子表
C. 只能是原子 D. 可以是原子或子表
4. 堆排序在最坏的情况下的时间复杂度是 ( )
A. O( log2 n ) B. O( log2 n2 )
C. O( nlog2 n ) D. O( n2 )
5. 设 G1 = ( V1, E1) 和 G2 = ( V2, E2 ) 为两个图，如果V1 ? V2，E1 ? E2，则称 ( )
A. G1是G2 的子图 B. G2 是G1 的子图
C. G1 是 G2 的连通分量 D. G2 是 G1 的连通分量
6. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( )
A. 4 B. 5 C. 6 D. 7
7. 设一个有n 个顶点和 e 条弧的有向图用邻接表表示，则删除与某顶点vi 相关的所有弧的时间复杂度是
A. O( n ) B. O( e ) C. O( n + e ) D. O( n* e)
8. 算法指的是
A. 计算机程序 B. 解决问题的计算方法
C. 排序算法 D. 解决问题的有限运算序列
9. 若派生类的成员函数不能直接访问基类中继承来的某个成员，则该成员一定是基类中的
A. 私有成员 B. 公有成员
C. 保护成员 D. 保护成员或私有成员
10. 在C++程序中，对象之间的相互通信通过
A. 继承实现 B. 调用成员函数实现
C. 封装实现 D. 函数重载实现
二． 填空题 ( 本大题共16小题，除第26小题5分外，其余每小题2分，共35分)
不写解答过程，将正确答案与题目编号写在答题纸上
11. 仅允许在同一端进行插入删除的线性表称为
12. 在一个长度为 n 的顺序表中第 i 个元素 ( 1 ? i ? n ) 之前插入元素时，需向后移动 元素个数是
13. 在串S ="structure" 中，以 t 为首字符的子串有 个
14. 在拓扑排序中，拓扑序列的第一个顶点必定是 的顶点
15. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的
16. 在含n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为
17. 设用S 和 X 分别表示进栈和出栈操作
， 则对输入序列a, b, c, d和e 进行一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为
18. 对表长为n 的顺序表进行分块查找，若以顺序查找确定块，且每块的长度为s， 则在等概率查找的情况下，查找成功时的平均查找长度为
19. 已知一棵完全二叉树中共有768 个结点，则该树中共有 个叶子结点
20. 设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中B[0] 存储矩阵中第一个元素a1,1, 则B[31] 中存放的元素是
( 注：矩阵元素下标从1起计)
21. C++支持的两种多态性分别是 多态性和 多态性
22. 定义类的动态对象数组时，系统只能够自动调用该类的 构造函数对其进行初始化
23. 初始化类模板时，相对于它的每个参数要提供
24. 面向对象程序设计的 机制提供了重复利用程序资源的一种途径
25. 删除一个动态对象时，将自动调用该对象所属类的 函数
26. 在下面的程序横线处补填上适当的内容（写到答题纸上），以使该程序有如下的结果输出：
Creating B
end of B
end of A
具体的程序如下：
# include
class A
｛
public：
A( ) { }
( 1 ) ｛ cout<<＂end of A＂<
class B：public A
｛
public：
B( ){ ( 2 ) }
~ B( ) ｛ cout<<＂end of B＂<
void main( )
｛
A *pa=new B；
delete pa；
｝
三. 解答题（本大题共9小题，每小题5分，共45分）
解答过程及结果与题目编号写在答题纸上
27. 在如图所示的链表中，若在指针p 所指的结点后插入数据域值相继为 a, b 的两个结点，可用两个语句实现该操作，依次写出它们
28. 由五个分别带权值为9，2，5，7，14 的叶子结点构成哈夫曼树，写出该树的带权路径长度并示明计算的步骤
29. 设a1, a2, a3 是不同的关键字且a1 > a2 > a3，可组成6种不同的输入顺序
画出其中哪几种输入顺序所构成的二叉排序树的高度为3
30. 画出如下广义表的存储表示
L = (( e, f ), ( a, ( b ) ), ( ( c, d ) ), ( a, ( b ) ) )
31. 在一棵高度为h 的满三叉树中，结点的总数是多少？写出计算的步骤和结果
（15分）
32. 已知一个无向图的顶点集为 { a, b, c, d, e } , 其邻接矩阵如下所示：
0 1 0 0 1
1 0 0 1 0
0 0 0 1 1
0 1 1 0 1
1 0 1 1 0
(1) 画出该图的图形；
(2) 根据此邻接矩阵，从顶点 b 出发进行深度优先遍历和广度优先遍历，写出相应遍历的顶点序列
33.
已知树T的先序（先序）序列为ABCDEFGHIJKL，后序遍历序列为CBFGEHDKJLIA，请画出树T
34. 对关键字序列( 72, 87, 61, 23, 100, 15, 7, 60 ) 进行堆排，结果应按关键字递减次序排列
请写出排序过程中得到的初始堆和前三趟的序列状态
四. 算法和程序阅读题（本大题共2小题，第35小题12分，第36小题8分，共20分）
答案与题目编号写在答题纸上
35. 阅读下列函数 arrange ( )
int arrange ( int a[], int low, int high, int x ) {
// low 和 high 分别为数据区的下界和上界
int i, j, t;
i = low; j = high;
while ( i < j ) {
while ( i< j && a[j] >= x ) j--;
while ( i < j && a[i] < x ) i++;
if ( i < j ) {
t = a[j]; a[j] = a[i]; a[i] = t; }
}
if ( a[i] < x ) return i;
else return i - 1;
}
(1) 说明该算法的功能；
(2) 写一个调用上述函数实现下列功能的算法：对一个整型数组 b[n＋１]（其中１．．n放置数据）中的元素进行重新排列，将所有负数调整到数组的低下标端，将所有的正数调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数
36. 读下面的程序，在答题纸上写出程序输出结果
# include
class A
｛
public：
virtual void func( )｛ cout<<"func in class A"<
class B
｛
public：
virtual void func( )｛ cout<<"func in class B"<
class C：public A，public B
｛
public：
void func( ) ｛ cout<<"func in class C"<
void main( )
｛
C c；
A& pa=c；
B& pb=c；
C& pc=c；
pa.func( )；
pb.func( )；
pc.func( )；
｝；
五. 算法设计（本题共15分）
37. 设在一棵二叉树中不存在数据域值相同的结点，试编制一个递归算法，找出存储数据为给定值x的结点，并输出其所在的层次及其所有的祖先
要求该算法的空间复杂度限定为O( 1 )，在编制的算法中应有适当的注释语句
算法中二叉树采用如下定义的存储结构：
typedef struct node {
char data;
struct node *lchild, *rchild;
} BiTreeNode, *BiTree;
下图为算法执行的参考数据模型：
若给定值x为e，结点在 3 层 祖先：b a
若给定值x为c，结点在 2 层 祖先：a
六. 应用设计题(本大题共2小题，第38小题15分，第39小题10分，共25分)
38. 根据堆的特性，写出"小根堆"抽象数据类型的定义（请用MinRootHeap命名ADT），其中基本操作的安排应充分考虑到堆的特点及所能提供的应用
39. 为实现一个包含本科生及研究生异质对象的学生数组，请设计相应的类，并画出它们的
标记图形符号和异质数组的图示
类中应包含必要的数据成员和成员函数，但不必实现成员函数体
假设本科生应包括学号(number)、姓名(name)、性别(sex)、年龄(age)、院系(department)等的信息资料，研究生应包括学号(number)、姓名(name)、性别(sex)、年龄(age)、专业(specialty)、导师(hierophant)、统招生或自费生(source)等的信息资料
2003 年北京工业大学硕士研究生入学考试试题
2、业精于勤，荒于嬉；行成于思，毁于随——韩愈