数据结构（本科）形成性考核册参考答案
2008年05月05日 gerrrrr
数据结构
作业一
一、单项选择题
1. 一个数组元素a 与( A )的表示等价。
A. *(a+i) B. a+i C. *a+i D. &a+I
2．执行下面程序段时，执行S语句的次数为( D )。
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++) S;
A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2
3. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( B )，以节省参数值的传输时间和存储参数的空间。
A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型
4. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( D )。
A. O(n) B. O(m+n) C. O(n2) D. O(m*n)
5. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（ C ）。
A. O(n) B. O(n2) C. O(n3) D. O(1)
6. 多维数组实际上是由嵌套的（ A ）实现的。
A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量
7. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ C ）个元素。
A. n-i B. n-i+1 C. n-i-1 D. i
8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。
A. O(n) B. O(n/2) C. O(1) D. O(n2)
9. 设有一个n′n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A存放于B中（ C ）处。
A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2
10. 不带头结点的单链表first为空的判定条件是（ A ）。
A. first == NULL; B. first->link == NULL;
C. first->link == first; D. first != NULL;
11. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ D ）。
A.s->link=p; p->link=s; B. p->link=s; s->link=p;
C.s->link=p->link; p=s; D. s->link=p->link; p->link=s;
12. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ D ）。
A.s = rear; rear = rear->link; delete s;
B.rear = rear->link; delete rear;
C.rear = rear->link->link; delete rear;
D.s = rear->link->link; rear->link->link = s->link; delete s;
二、填空题
1. 数据结构包括逻辑结构、(存储结构)和数据的运算三个方面。
2. 基本数据类型是计算机已经实现了的(数据结
构)。
3. 面向对象的特征应包括对象、类、(继承)、消息通信。
4. 模板类是一种数据抽象，它把(数据类型)当作参数，可以实现类的复用。
5. 在程序运行过程中不能扩充的数组是(静态)分配的数组。这种数组在声明它时必须指定它的大小。
6. 若设一个n′n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[j]的存储地址为(LOC(0,0)+(i*n+j)*d)。
7. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的(2n-I-1)*I/2+J)位置。
8. 若设串S = “documentHash.doc\0”，则该字符串S的长度为(16)。
9. 在链表中进行插入和（删除）操作的效率比在顺序存储结构中进行相同操作的效率高。
10. 单链表中逻辑上相邻的结点而在物理位置上（不一定）相邻。
11. 若设L是指向带表头的单链表, 语句 L->link=L->link->link的作用是（删除）单链表中的第一个结点。
三、判断题（对/错）
1. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。错
2. 只有用面向对象的计算机语言才能描述数据结构算法。错
3. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。错
4. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。对
5. 用字符数组存储长度为n的字符串，数组长度至少为n+1。对
6. 在线性链表中删除中间的结点时，只需将被删结点释放。错
7. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。对
8. 在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。对
四、运算题
1. 对于一个n′n的矩阵A的任意矩阵元素a[j]，按行存储时和按列存储时的地址之差是多少。（设两种存储时的开始存储地址均为LOC(0, 0)，元素所占存储单元数均为d）
按行存储时与按列存储时，计算A[j]地址的公式分别为
LOC( i, j ) = LOC(0, 0) + ( i*n + j ) * d
及LOC’( i, j ) = LOC(0, 0) + ( j*n + i) * d
两者相减，得
LOC(i,j) – LOC’(i,j) = LOC(0,0)+(i*n+j)*d–LOC(0,0)–(j*n+i)*d
=(i-j)*(n-1)*d
2. 设有一个10′10的矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
根据题意，矩阵A中当元素下标I与J满足I≥J时，
任意元素A[I][J]在一维数组B中的存放位置为
I * (I + 1) / 2 + J，
因此，A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41。
3. 设有一
个二维数组A[11][6]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是1000，每个数组元素占4个存储字，则A[8][4]的地址在什么地方。
对于二维数组，若第一、第二维的元素个数为m和n，每个元素所占存储字数为d，首地址为LOC(0, 0)，则对于任一数组元素A[j]，它的存储地址为：
LOC(i, j) = LOC(0, 0) + (i * n + j) * d
根据题意，LOC(8, 4) = LOC(0, 0) + (8 * 6 + 4) * 4 = 1000 + 52 * 4 = 1208。
4. 假定一棵二叉树的广义表表示为A(B(,D(G)),C(E,F))，分别写出对它进行前序、中序、按层遍历的结果。
前序：A,B,D,G,C,E,F
中序：B,G,D,A,E,C,F
按层：A,B,C,D,E,F,G
5. 已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。
中根序列：c,b,d,e,a,g,i,h,j,f
后根序列：c,e,d,b,i,j,h,g,f,a
先根序列：a,b,c,d,e,f,g,h,i,j
五、算法分析题
1. 指出算法的功能并求出其时间复杂度。
void matrimult ( int a[M][N], int b[N][L], int c[M][L] )
{ //M、N、L均为全局整型常量
int i, j, k;
for ( i = 0; i < M; i++ )
for ( j = 0; j < L; j++ ) c[j] = 0;
for ( i = 0; i < M; i++ )
for ( j = 0; j < L; j++ )
for ( k = 0; k < N; k++ )
c[j] += a[k] * b[k][j];
}
功能为：矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。
时间复杂性为：O(M×N×L)。
2. 设字符串String具有下列操作：
int Length ( ) const; //计算字符串的长度
char getData ( k ); //提取字符串第k个字符的值
若字符串Tar的值为“a b a b c a b c a c b a b”，Pat的值为“a b c a c”时，给出算法执行后函数返回的结果。
#include “String.h”
int unknown ( String& Tar, String& Pat ) const {
for ( int i = 0; i <= Tar.Length( ) – Pat.Length( ); i++ ) {
int j = 0;
while ( j < Pat.Length( ) )
if ( Tar.getData (i+j) == Pat.getData (j) ) j++;
else break;
if ( j == Pat.Length( ) ) return i;
}
return -1;
}
算法执行的结果是：函数返回值等于5。该算法即字符串的模式匹配。
3. 设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。
int AA(LNode *Ha)
{ //Ha为指向带表头附加结点的单链表的表头指针
int n=0;
LNode *p=Ha->link;
while(p) {
n++;
p=p->link;
}
return(n);
}
算法功能：计算单链表的长度或计算单链表中结点的个数。
4. 写出下列程序段的输出结果:
void main(){
stack S;
char x,y;
S.InitStack( );
x="c";y="k";
S.Push(x); S.Push("a"); S.Push(y);
S.Pop(S,x); S.Push("t"); S.Push("s");
while(!S.IsEmpty(
)) { S.Pop(y); cout<
运行结果：stack
六、算法设计题
1. 设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。
函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：
Length( ) 求表的当前长度；
maxLength( ) 求表的最大允许长度；
getData(int k) 提取第k个元素的值；
setData(int k, int val) 修改第k个元素的值为val。
template
void merge(SeqList
答：
template
void merge(SeqList
int m=A.Length(), n=B.Length(), mpn=m+n;
if(mpn>C.maxLength()){
cerr<<“合并后表的长度超出表C的最大允许长度”<
}
int i=0, j=0, k=0, av=A.getData(i), bv=B.getData(j);
while(i
if(av>=bv){C.setData(k++, bv); bv=B.getData(++j);}
}
if(i
while(k
2. 假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。
void rangeDelete ( ListNode * L, ElemType min, ElemType max )
{
ListNode *q = L, *p = L->link;
}
答：
while ( p != NULL) {
if(p->data >= min && p->data <=max) {
q->link=p->link; delete p; p=q->link;
}
else {q=p; p=p->link;}
}
3. 请分别写出在循环队列上进行插入和删除操作的算法。
循环队列定义如下：
struct CyclicQueue {
ElemType elem[M]; //M为已定义过的整型常量，表示队列长度
int rear,front ; // rear指向队尾元素后一个位置，front 指向队头元素
int tag ;
// 当 front=rear且tag=0时，队列空，当front=rear且tag=1时，队列满
};
bool EnCQueue( CyclicQueue& Q, ElemType x )
{
// Q 是一个循环队列，最多可存储M个元素，若队列不满，
//将x插入至队尾并返回 true；否则返回 false。
}
bool DelCQueue( CyclicQueue& Q, ElemType& x )
{
// Q 是一个循环队列，若队列不空，则删除队头元素并由 x 带回，
//且返回 tru
e，否则返回 false
}
答：
// 将x插入至队尾
if (Q.rear == Q.front && Q.tag == 1) return false;
Q.elem[Q.rear] = x;
Q.rear = (Q.rear+1) % M;
if (Q.rear == Q.front) Q.tag = 1;
return true;
// 删除队头元素
if (Q.front == Q.rear && Q.tag == 0) return false;
x = Q.elem[Q.front];
Q.front = (Q.front+1) % M;
if (Q.front == Q.rear) Q.tag = 0;
return true;
作业二
一、 单项选择题
1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ C ）。
A. O(1) B. O(n)
C. O(n2) D. O(nlog2n)
2. 带表头的双向循环链表的空表满足（ B ）。
A. first＝NULL; B. first->rLink==first
C. first->lLink==NULL D. first->rLink==NULL
3. 栈的插入和删除操作在( A )进行。
A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的( A )位置。
A. 前一个 B. 后一个 C. 当前 D. 后面
5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。
A. front+1 == rear B. rear+1 == front
C. front == 0 D. front == rear
6. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。
A. x=top->data; top=top->link; B. top=top->link; x=top->data;
C. x=top; top=top->link; D. x=top->data;
7. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( D )分别设在这块内存空间的两端。
A. 长度 B. 深度 C. 栈顶 D. 栈底
8. 在系统实现递归调用时需利用递归工作记录保存（ C ），当递归调用程序执行结束时通过它将控制转到上层调用程序。
A. 调用地址 B. 递归入口 C. 返回地址 D. 递归出口
9. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ D ），它很容易被改写为非递归过程。
A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归
10. 设有一个广义表A (a)，其表尾为（ C ）。
A．a B．( ( ) ) C．（） D．(a)
11. 对于一组广义表A( ), B(a,b), C(c,(e,f,g))
, D(B,A,C), E (B, D)，其中的E是（ D ）。
A. 线性表 B. 纯表 C. 递归表 D. 再入表
12. 在一棵树中，( C )没有前驱结点。
A. 树枝结点 B. 叶子结点 C. 树根结点 D. 空结点
13. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( A )个结点。
A. 2i B. 2i+1 C. 2i-1 D. 2n
二、填空题
1. 链表与顺序表、索引表、散列表等都是数据逻辑结构的（存储）表示。
2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为（先进先出）表。
3. 向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。
4. 向一个循环队列中插入元素时，需要首先移动（队尾）指针，然后再向所指位置写入新元素。
5. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（1）个结点。
6. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（局部变量）。
7. 非空广义表的除第一个元素外其他元素组成的表称为广义表的（表尾）。
8. 广义表的深度定义为广义表括号的（重数）。
9. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为（3）。假定树根结点的层数为0。
10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有（6）个。
11． 一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（6）个。
12. 在一棵高度为h的理想平衡二叉树中，最多含有（2h+1-1）个结点。假定树根结点的高度为0。
三、判断题（对/错）
1．在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear。错
2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。对
3将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。对
4. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。对
5. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置完成删除操作。错
6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。对
. 在一棵二叉树中，假定每个结点只
有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。对
7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。对
8． 于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。错
9．对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。对
四、运算题
1. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。
序号： 0 1 2 3 4 5 6 7 8 9 10
a b c d e f g h i j k
-1 0 1 1 3 0 5 6 6 0 9
data:
parent:
叶子结点数： 5
单分支结点数：3
两分支结点数：2
三分支结点数：1
2. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
34 56 58 63 94
2 1 3 4 4
元素
比较次数
3. 假定一个线性序列为 (38,42,55,15,23,44,30,74,48，26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按照结点值从小到大的次序写出。
左子树为空的所有单支结点：15,23,42,44
右子树为空的所有单支结点：30
4. 假定一组记录为(40,28,16,56,50,32,30,63,44,38)，按次序插入每个记录生成一棵AVL树，请回答插入时造成不平衡的结点个数。
插入时造成不平衡的结点个数：4
5. 已知图G=(V,E)，其中V={a,b,c,d,e}，E={
结点 a b c d e
出度 1 1 2 1 2
入度 2 2 1 1 1
6. 已知一个图的顶点集V和边集G分别为：
V={1,2,3,4,5,6};
E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,6,5>};
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从小到大的次序链接的，试写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答（1）：1,2,4,5,3,6
（2）：1,2,3,4,5,6
五、算法分析题
1. 请写出下面算法的功能.
void unknown(Queue &Q) {
Stack S; int d;
S.InitStack( );
wh
ile(!Q.IsEmpty( )) {
Q.DeQueue(d); S.Push(d);
}
while(!S.IsEmpty( )) {
S.Pop(d); Q.EnQueue(d);
}
}
利用"栈"作为辅助存储,将队列中的元素逆置（即相反次序放置）。
2. 下面是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法, 若相等则返回1，否则返回0。请按标号补充合适的内容。
int symmetry ( DoublelList* DL ) {
DoublelNode * p = DL->rLink, *q = DL->lLink;
while (p != q)
if ( p->data == q->data ) {
p = p->rLink;
___(1)___;
if(p->lLink==q) ___(2)___;
}
else ___(3)___;
return 1;
}
(1) q = q->lLink (2) return 1 (3) return 0
3. 设有一个求解汉诺塔（Hanoi）的递归算法如下：
void HANOI ( int n, int peg1, int peg2, int peg3 ) {
if(n==1) cout<
HANOI(n-1, peg1, peg3, peg2);
cout<
}
}
当使用HANOI( 3,1,2,3)进行调用时，执行过程中else子句的cout语句得到的结果为：
1→2
1→3
2→3
4. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉树BT中查找值为X的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适内容。
BinTreeNode* ParentPtr(BinTreeNode* BT, BinTreeNode* PT, ElemType& X)
{
if(BT==NULL) return NULL;
else if(BT->data==X) return PT;
else {
if(PT=ParentPtr(BT->left,BT,X)) __(1)_____;
if _________________(2)_______________ return PT;
else ___(3)____;
}
}
(1) return PT
(2) (PT=ParentPtr(BT->right,BT,X))
(3) return NULL 或return 0
六、算法设计题
1. 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + …… + an-1 x + an 通常使用的方法是一种递推的方法。它可以描述为如下的递推形式：
pn (x) = x * pn-1 (x) + an (n>0)
此处
Pn-1 (x) = a0 xn-1 + a1 xn-2 + …… + an-2 x + an-1
P0=an
这也是问题的递归形式。多项式的递归求解形式为：
poly(x, 0) = A[0]
poly(x, n) = x * poly(x, n-1) + A[n], n > 0
试编写一个递归函数，计算这样的多项式的值。
float poly ( float x, float A[], int n ) {
}
答：
float poly ( float x, float A[ ], int n ) {
if ( ! n ) return A[0];
else return x * poly( x, A, n-1 ) + A[n];
}
2. 已知二叉树中的结点类型BinTreeNode定义
为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定树根的层次为0，参数BT初始指向这棵二叉树的根结点。
int BTreeHeight(BinTreeNode* BT);
答：
int BTreeHeight(BinTreeNode* BT)
{
if(BT==NULL)
//对于空树，返回-1并结束递归
return –1;
else
{
//计算左子树的高度
int h1=BTreeHeight(BT->left);
//计算右子树的高度
int h2=BTreeHeight(BT->right);
//返回树的高度
if(h1>h2) return h1+1;
else return h2+1;
}
}
说明：函数体中的两个else可以没有
3. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeLeafCount(BinTreeNode* BT);
答：
int BTreeLeafCount(BinTreeNode* BT)
{
if(BT==NULL) return 0;
else if(BT->left==NULL && BT->right==NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}
说明：函数体中的两个else可以没有
作业三
一、 单项选择题
1. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为( D )。假定树根结点的编号为0。
A. ?(n-1)/2? B. ?n/2? C. én/2ù D. ?n/2?-1
2. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的( A )结点。
A. 兄弟 B. 父子 C. 祖先 D. 子孙
3. 已知一棵树的边集表示为{
A. 2 B. 3 C. 4 D. 5
4. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( C )。
A 1 B 2 C 3 D 4
5. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为( C )。
A. 5.5 B. 5 C. 39/8 D. 19/4
6. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( A )的值向上取整。
A. log2(n+1) B. log2n C. n/2 D. (n+1)/2
7. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索
第15个元素的搜索长度为( B )。
A. 3 B. 4 C. 5 D. 6
8. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( C )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
9. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( C )种旋转类型。
A. 2 B. 3 C. 4 D. 5
10. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1íV2，E1íE2，则称 ( A )。
A．G1是G2的子图 B．G2是G1的子图
C．G1是G2的连通分量 D．G2是G1的连通分量
11. n个顶点的连通图中至少含有 ( A )。
A．n-1条边 B．n条边 C．n(n-1)/2条边 D．n(n-1)条边
12. 对于具有e条边的无向图，它的邻接表中有 ( D ) 个边结点。
A．e-1 B．e C．2(e-1) D．2e
13. 在n个顶点的有向无环图的邻接矩阵中至少有 ( C ) 个零元素。
A．n B．n(n-1)/2 C．n(n+1)/2 D．n(n-1)
二、填空题
1．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左子女元素的下标为（2i+1）。
2．在一个最大堆中，堆顶结点的值是所有结点中的（最大值）。
3. 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为(20.5)。
4. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向(右子树)继续搜索。
5. 在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（1）。
6. 根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行（右单旋转）调整。
7. n (n﹥0) 个顶点的连通无向图各顶点的度之和最少为（2(n-1)）。
8. 设图G = (V, E)，V = {1, 2, 3, 4}, E = {<1, 2>, <1, 3>, <2, 4>, <3, 4>}，从顶点1出发，对图G进行广度优先搜索的序列有（2）种。
9. n个顶点的连通无向图的生成树含有(n-1)条边。
10. 一般来说,深度优先生成树的高度比广度优先生成树的高度要（高）。
11. 第i (i = 1, 2, …, n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做（直接插入）排序。
三、判断题（对/错）
1. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。错
2. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。对
3. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。对
4.用邻接矩阵存储一个图时，在不考虑压缩存储的
情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。对
5. 存储有向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。错
6. 有回路的有向图不能完成拓扑排序。对
7. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。错
8. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。对
四、运算题
1. 已知一个图的顶点集V和边集G分别为：
V={1,2,3,4,5,6};
E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,6,5>};
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从大到小的次序链接的，试按照遍历算法写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答（1）：1,3,4,6,5,2
（2）：1,3,2,4,5,6
2. 已知一个带权图的顶点集V和边集G分别为：
V={0,1,2,3,4,5,6};
E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,
(4,5)6,(4,6)6,(5,6)12};
试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。
顶点： 0 1 2 3 4 5 6
路径长度： 0 16 10 14 25 21 31
3. 已知一个AOV网络的顶点集V和边集G分别为：
V={0,1,2,3,4,5,6,7};
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。
拓扑序列：1,3,6,0,2,5,4,7
4. 已知一个AOE网络的顶点集V和边集G分别为：
V={0,1,2,3,4,5};
E={<0,1>5,<0,2>8,<1,2>7,<1,3>10,<1,4>6,<2,4>3,<3,4>9,<3,5>15,<4,5>12};
若存储它采用邻接表，则按主教材中介绍的求关键路径的方法，依次写出所有的关键活动（用边表示），并求出关键路径长度（提示：先画出对应的图形，然后再运算）。
所有关键活动：<0,1>5,<1,3>10,<3,4>9,<4,5>12
关键路径长度：36
5. 如果某个文件经内排序得到80个初始归并段，试问
(1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？
答（1）归并路数： 5 （2）需要归并躺数：2
答案解释：
(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = élogkmù
= élogk80ù = 3得：k3≥80。由此解得k≥5，即应取的归并路数至少为5。
(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = élogkmù = élog1480ù = 2。即至少需2趟归并可完成排序。
五、算法分析题
1. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。
void BTC(BinTreeNode* BT)
{
if(BT!=NULL) {
if( BT->left!=NULL && BT->right!=NULL)
if(BT->left->data>BT->right->data) {
BinTreeNode* t=BT->left;
BT->left=BT->right;
BT->right=t;
}
BTC(BT->left);
BTC(BT->right);
}
}
算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。
2. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g)),t(e))，rt,bt,dt和et指针变量分别保存指向r,b,d和e结点的指针值，则：
执行BTM(rt)调用后，得到的函数值为___(1)_____;
执行BTM(bt)调用后，得到的函数值为___(2)_____;
执行BTM(dt)调用后，得到的函数值为___(3)_____;
执行BTM(et)调用后，得到的函数值为__(4)______;
char BTM(BinTreeNode* BT)
{
static char max=0;
if(BT!=NULL) {
char k1,k2;
k1=BTM(BT->left);
k2=BTM(BT->right);
if(k1>max) max=k1;
else if(k2>max) max=k2;
else if(BT->data>max) max=BT->data;
}
return max;
}
(1) ’t’
(2) ’g’
(3) ’g’
(4) ’e’
3. 在a[10]数组中数据{16,35,42,73,54,58,80}为一个最小堆，n为整型变量，其值为7，则执行DH(a,n)调用下面算法后数组a中的数据变为_____________________________。
int DH(int HBT[], int& n)
{
if(n==0) {cerr<<"null!"<
n--;
int x=HBT[n];
int i=0;
int j=2*i+1;
while(j<=n-1) {
if(j
if(x<=HBT[j]) break;
HBT=HBT[j];
i=j; j=2*i+1;
}
HBT=x;
return temp;
}
{35,54,42,73,80,58}
4. 假定p1和p2是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。
int SS(ListNode* p1, ListNode* p2)
{
while(p2!=NULL) {
ListNode* r=p1;
While(r!=NULL) {
if(p2->data==r->data) break;
r=r->link;
}
if(r==NULL) return 0;
p2=p2->link;
}
return 1;
}
判断p2单链表所代表的集合是否为p1单链表所代表的集合的子集合，若是则返回1否则返回0。
5. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。
int JB(BinTreeNode* bt, ElemType& x)
{
if(bt==NULL) return 1;
else {
if(JB(bt->left,x)==0) return 0;
if(bt->data
if(JB(bt->right,x)==0) return 0;
else return 1;
}
}
算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。
六、算法设计题
1. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。
int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2);
答：
int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)
{
//若两棵树均为空则返回1表示相等
if(T1==NULL && T2==NULL) return 1;
//若一棵为空一棵不为空则返回0表示不等
else if(T1==NULL || T2==NULL) return 0;
//若根结点值相等并且左、右子树对应相等则两棵树相等
else if(T1->data==T2->data && BTreeEqual(T1->left, T2->left) &&
BTreeEqual(T1->right, T2->right) )
return 1;
//若根结点值不等或左、右子树对应不等则两棵树不等
else
return 0;
}
2. 已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结
点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的根结点指针。算法中参数BT初始指向待复制二叉树的根结点。
BinTreeNode* BTreeCopy(BinTreeNode* BT);
答：
BinTreeNode* BTreeCopy(BinTreeNode* BT)
{
if(BT==NULL) return NULL;
else {
//得到新结点
BinTreeNode* pt=new BinTreeNode;
//复制根结点值
pt->data=BT->data;
//复制左子树
pt->left=BTreeCopy(BT->left);
//复制右子树
pt->right=BTreeCopy(BT->right);
//返回新树的树根指针
return pt;
}
}
说明：函数体中的else可以没有
3. 假定元素类型为ElemType的一维数组R[n]中保存着按关键码升序排列的n个记录，记录的关键码域key的类型为KeyType，试按照下面的函数声明编写一个非递归算法，从一维数组R[n]中折半搜索出关键码等于K的记录，若搜索成功则返回记录位置（即元素下标），否则返回-1。
int BinSearch(ElemType R[], int n, KeyType K);
答：
int BinSearch(ElemType R[], int n, KeyType K)
{
int low=0, high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(K==R[mid].key) return mid;
else if(K
}
return -1;
}
说明：函数体中第一个else可以没有.
作业四
一、 单项选择题
1. 与邻接矩阵相比，邻接表更适合于存储 ( C )。
A．无向图 B．连通图 C．稀疏图 D．稠密图
2. 设无向图的顶点个数为n，则该图最多有（ B ）条边。
A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)
3. 图的深度优先搜索类似于树的（ A ）次序遍历。
A. 先根 B. 中根 C. 后根 D. 层次
4. 采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ C ）数。
A. 非零 B. 非整 C. 非负 D. 非正
5. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( C )。
A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序
6. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是( C )。
A. 3 B. 4 C. 5 D. 6
7. 一个对象序列的排序码为{46, 79, 56, 38, 40, 84}，采用
快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为( C )。
A. {38, 46, 79, 56, 40, 84} B. {38, 79, 56, 46, 40, 84}
C. {40, 38, 46, 79, 56, 84} D. {38, 46, 56, 79, 40, 84}
8. 5阶B树中, 每个结点最多允许有（ C ）个关键码。
A. 2 B. 3 C. 4 D. 5
9. 在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（ B ）个结点。
A. h-1 B. h C. h+1 D. h+2
10. 既希望较快的搜索又便于线性表动态变化的搜索方法是（ D ）。
A. 顺序搜索 B. 折半搜索 C. 散列搜索 D. 索引顺序搜索
11. 在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（ C ）值相同。
A. 关键码 B. 非关键码 C. 散列函数 D. 某个域
12. 采用线性探查法解决冲突时所产生的一系列后继散列地址（ C ）。
A. 必须大于原散列地址 B. 必须小于原散列地址
C. 可以大于或小于原散列地址 D. 不能超过散列表长度的一半
二、填空题
1．每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做（二路归并）排序。
2． 堆排序中，对n个记录建立初始堆需要调用（n/2）次调整算法。
3. 对n个数据对象进行堆排序，总的时间复杂度为（O(nlog2n)）。
4. 快速排序在最坏情况下的时间复杂度为（O(n2)）。
5. 给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟快速排序处理，得到的右子表中有（3）个对象。
6. 在索引表中，每个索引项至少包含有（关键码）域和地址域这两项。
7. 在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为（稀疏）索引。
8. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为（500）。
9. 在线性表的散列存储中，装载因子 a 又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则 a 等于（n/m）。
10. 已知一棵3阶B树中含有50个关键码，则该树的最大高度为（5）。
11. 在一棵m阶B树上，每个非根结点的关键码数最多为（m-1）个。
三、判断题（对/错）
1. 如果有向图中各个顶点的度都大于2，则该图中必有回路。错
2. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大
小排列到一个拓扑有序的序列中。错
3. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。对
4. 堆排序是一种不稳定的排序算法。对
5. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m 互质。对
6. 一棵 m 阶 B 树中每个结点最多有 m-1 个关键码，最少有 ém/2ù-1个关键码。错
7. 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。错
9. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树与原树高度查同。对
四、运算题
1. 已知一个数据表为{36,25,25*,62,40,53}，请写出在进行快速排序的过程中每次划分后数据表的变化。
(0) [36 25 25* 62 40 53]
(1) [25* 25] 36 [62 40 53]
(2) 25* 25 36 [53 40] 62
(3) 25* 25 36 40 53 62
2. 已知有一个数据表为{30,18,20,15,38,12,44,53,46,18*,26,86}，给出进行归并排序的过程中每一趟排序后的数据表变化。
(0) [30 18 20 15 38 12 44 53 46 18* 26 86]
(1) [18 30][15 20][12 38][44 53][18* 46][26 86]
(2) [15 18 20 30][12 38 44 53][18* 26 46 86]
(3) [12 15 18 20 30 38 44 53][18* 26 46 86]
(4) [12 15 18 18* 20 26 30 38 44 46 53 86]
3. 设散列表的长度m=11，散列函数为H(K)=K mod m，采用链地址法解决冲突，待依次插入的关键码序列为{1,13,12,34,38,33,27,22}。根据构成的开散列表回答：
(1) 在等概率的情况下，搜索成功时的平均搜索长度；
(2) 在等概率的情况下，搜索失败时的平均搜索长度。
答(1) (1*4+2*3+3)/8=13/8
(2) (3+4+2+1+1+3+1+1+1+1+1)/11=19/11
4. 设有150个表项要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需表项的平均比较次数不超过2次。试问散列表需要设计多大？
提示：设a是散列表的装载因子，则有
散列表长度m至少为：225
答案说明：
已知要存储的表项数为n=150，搜索成功的平均搜索长度为ASLsucc ￡ 2，则有
，解得
又有 ，则 m 3 225
5
五、算法分析题
1. 已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的图中计算所有顶点的出度，并保存在数组Degree[]中。请按标号填补合适内容。
template
void Graph
{
int i;
Edge *p=NULL;
for(i=0; i
for(i=0; i
___(3)___;
}
}
答(1) 0
(2) p=p->li
nk
(3) Degree[p->dest]++
2. 下面是进行快速排序的一次划分的算法，请按标号填补合适的内容。
void Exchange(int s[], int i, int j) {
int temp =s; s=s[j]; ___(1)___;
}
int Partition(int seq[], int low, int high) {
int pivotpos=low, pivot=seq[low], i;
for(i=low+1; i<=high; i++)
if(___(2)___){
pivotpos++;
if(pivotpos!=i) Exchange(seq, pivotpos, i);
}
___(3)___;
return pivotpos;
}
答(1) s[j]=temp
(2) seq
3. 下面给出一个排序算法，它属于数据表类dataList的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。请按标号填补合适内容。
template
void ___(1)___::unknown(){
T temp; int i,j,k;
for(i=0; i
for(j=i+1; j<___(2)___; j++)
if(Vector[j].key
temp=Vector; Vector = Vector[k]; Vector[k] = temp;
}
}
}
答(1) dataList
(2) currentSize
(3) k=j
4. 下面给出一个排序算法，它属于数据表类dataList的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。若Vector中数据的初始排序码序列为{30, 20,40,10,60,50}，针对最外层的while循环，给出每次循环执行后的排序码序列。
template
void dataList
int low=0, high=CurrentSize-1, i, j;
int exchange;
while(low
for(i=low; i
T temp=Vector; Vector=Vector[i+1];
Vector[i+1]=temp;
j=i; //记忆右边最后发生交换的位置j
}
high=j; //比较范围上界缩小到j
}
}
(0) {30 20 40 10 60 50}
(1) {20 30 10 40 50 60}
(2) {20 10 30 40 50 60}
(3) {10 20 30 40 50 60}
六、算法设计题
1. 已知二叉搜索树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，若树中不存在item结点则进行插
入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。
Int Insert(BinTreeNode*& BST, const ElemType& item);
答：
int Insert(BinTreeNode*& BST, const ElemType& item)
{
if(BST==NULL){
BinTreeNode* p=new BinTreeNode;
p->data=item;
p->left=p->right=NULL;
BST=p;
return 1;
}
else if(item==BST->data) return 0;
else if(item
return Insert(BST->left, item);
else
Insert(BST->right, item);
}
说明：函数体中的三个else可以没有
2. 有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个数据互不相同的表进行排序，并将排序结果存放到另一个新表中。针对表中的每个数据，计数算法都要扫描一趟表，统计出表中有多少个数据比它小。假设针对某个数据，统计出的计数值为c，则这个数据在新表中的合适存放位置应为c。
在下面的函数模板countsort中，数组src中存放的是要排序的数据；数组dest用于存放排序的结果；size为这两个数组的大小。请补充完整countsort的函数体中遗漏部分，使其能够完成计数排序任务。
template
void countsort(T src[], T dest[], int size){
int i, j, c;
for(i=0; i
dest[c]=src;
}
}
答：
c=0;
for(j=0; j