全真试题（三）
本试卷分两部分，第一部分为选择题，1页至3页，第二部分为非选择题，4页至12页，共12页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1.下面程序段的时间复杂度是（ ）
for (i=0; i＜n; i++)
for (j=1; j＜m; j++)
A[i][j]=0;
A.O (n) B.O(m+n-1) C.O(m+n) D.O(m*n)
2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）
A.p=p-＞next; B.p-＞next =p-＞next -＞next ;
C.p-＞next =p; D.p=p-＞next-＞next;
3.在头指针为head且表长大于1的单循环链表中，指针p 指向表中某个结点，若p-＞next-＞next=head，则（ ）
A.p指向头结点 B.p指向尾结点
C.*p的直接后继是头结点 D.*p的直接后继是尾结点
4.判定“带头结点的链队列为空”的条件是（ ）
A.Q.front ==NULL B.Q.REAR==NULL
C.Q.front==Q.rear D.Q.front!=Q.rear
5.设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）
A.联接 B.求子串 C.字符定位 D.子串定位
6.广义表A=(a,(b),(),(c,d,e))的长度为（ ）
A.4 B.5 C.6 D.7
7.一棵含18个结点的二叉树的高度至少为（ ）
A.3 B.4 C.5 D.6
8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ ）
A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA
9.无向图中一个顶点的度是指图中（ ）
A.通过该项点的简单路径数 B.与该顶点相邻接的顶点数
C.通过该顶点的回路数 D.与该顶点连通的顶点数
10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为（ ）
A.a c e f b d
B.a c b d f e
C.a c b d e f
D.a c d b f e
11.在下列排序方法中，平均时间性能为O(nologn)且空间性能最好的是（ ）
A.快速排序 B.堆排序 C.归并排序 D.基数排序
12.已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是（ ）
A.{25，36，48，72，23，40，79，82，16，35}
B.{25，36，48，72，16，23，40，79，82，35}
C.{25，36，48，72，16，23，35，40，79，82}
D.{16，23，25，35，36，40，48，72，79，82}
13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ ）
A.21 B.23 C.41 D.62
14.索引非顺序文件的特点是（ ）
A.主文件无序，索引表有序 B.主文件有序，索引表无序
C.主文件有序，索引表有序 D.主文件无序，索引表无序
15.倒排文件的主要优点是（ ）
A.便于进行插入和删除运算 B.便于进行文件的恢复
C.便于进行多关键字查询 D.节省存储空间第二部分 非选择题（共70分）
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。
16.抽象数据类型的特点是将 和 封装在一起，从而实现信息隐藏。
17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。
18.在队列中，允许进行插入操作的一端称为,允许进行删除操作的一端称为 。
19.如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”的判定条件是 。
20.设S1=“good”，S2=,”，S3=“book”，则S1，S2和S3依次联接后的结果是 。
21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是 。
22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为 。
23.能够成功完成拓扑排序的图一定是一个 。
24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用
较为适当。
25.假设哈希表的表长 m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为 。
三、解答题（本大题共4小题，每小题5分，共20分）
26.假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符的在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码。
27.已知一个图如下所示，其顶点按a.b.c.d.e.f顺序存放在邻接表的顶点表中，请画出该图的邻接表，
使得按此邻接表进行深度优先遍历时得到的顶点序列为a.c.b.e.f.d，进行广度优先遍历时得到的顶点序列为a c b d f e。
28.已知两个4×5的稀疏矩阵的三元组表分别如下：
0
1
4
16
1
2
2
18
2
3
4
-25
3
4
2
28
0
1
1
32
1
2
2
-22
2
2
5
69
3
3
4
25
4
4
2
51
请画出这两个稀疏矩阵之和的三元组表。
29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。
（1）画出该二叉排序树
（2）画出删去该树中元素值为90的结点之后的二叉排序树。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：
typedef sturct{
DataType data[MaxSize];
int front [2],length[2];
} Queue2;
对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容,
实现第i个循环队列的入队操作。
int EnQueue (Queue2 *Q,int i,DataType x)
{ // 若第i个队列不满，则元素x入队列，并返回1，否则返回0
if (i＜0 || i＞1)return 0;
if ( (1) )
return 0;
Q-＞data[ (2) ]=x;
Q-＞length[ (3) ]++;
return 1;
}
31.某二叉树的线索链表存储结构如图（b）所示，其中 p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：
（1）写出执行函数调用f(p)的输出结果；
（2）简述函数f 的功能。
void f (BinThrTree t)
{
while (t)
{
printf(t-＞date);
if (t-＞lchild)
t=t-＞lchild;
else
t=t-＞rchild;
}
}
（1）
（2）
32.下列函数FindCycle (G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点Vi的简单回路。数据cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点Vk的下一个顶点Vj。请在空缺处填入合适的内容，使其成为一个完整的算法。
已知邻接表的顶点表结点结构为：
vertex
firstedge
边表结点EdgeNode结构为：
adjvex
next
int cycle_ path[MaxNurm];
int FindCycle (ALGraph * G,int i)
{ //若回路存在，则返回1,否则返回0
int j;
for (j=0; j＜G-＞n; j++) cycle_path[j]=-1;
return DFSPath (G,i,i );
}
int DFSPath (ALGraph *G,int j,int i )
{
EdgeNode * p;
Int cycled=0;
for (p=G-＞adjlist[j].firstedge; p &&! cycled; p=p-＞next)
{
cycle_path[j]=p-＞adjvex;
if ( (1) )cycled=1; //已找到回路
else
if (cycle_path[p-＞adjvex]==-1) cycled= (2) ;
}
return (3) ;
}
33.阅读下列函数algo，并回答问题。
（1）假设整型数组A[1..8]中的元素依次为（3，8，9，1，7，4，2，6）。执行函数调用algo（A，8）时，外层while的循环体执行多少次？函数的返回值是多少？
（2）简述函数algo（L，n）的功能。
int algo (int L[ ],int n)
{
int i=0,j,s=1,t=n;
while (i! =(n+1)/2)
{
int x =L[s];
i=s; j=t;
while (i＜j)
{
while (i＜j &&L[j]＞=x)j--;
L[i]=L[j];
while (i＜j &&L[i]＜=x)i++;
L[j]=L[i];
}
L[i]=x;
if (x＜(n+1)/2) s=i+1;
else t =i-1;
}
if (i ==0) return 0;
else return L[i];
}
(1)
(2)
五、算法设计题（本题共10分）
34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为0（n）的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：
（7，10，10，21，30，42，42，42，51，70）
经算法操作后变为（7，10，21，30，42，51，70）
本试卷分两部分，第一部分为选择题，1页至3页，第二部分为非选择题，4页至12页，共12页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1.下面程序段的时间复杂度是（ ）
for (i=0; i＜n; i++)
for (j=1; j＜m; j++)
A[i][j]=0;
A.O (n) B.O(m+n-1) C.O(m+n) D.O(m*n)
2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）
A.p=p-＞next; B.p-＞next =p-＞next -＞next ;
C.p-＞next =p; D.p=p-＞next-＞next;
3.在头指针为head且表长大于1的单循环链表中，指针p 指向表中某个结点，若p-＞next-＞next=head，则（ ）
A.p指向头结点 B.p指向尾结点
C.*p的直接后继是头结点 D.*p的直接后继是尾结点
4.判定“带头结点的链队列为空”的条件是（ ）
A.Q.front ==NULL B.Q.REAR==NULL
C.Q.front==Q.rear D.Q.front!=Q.rear
5.设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）
A.联接 B.求子串 C.字符定位 D.子串定位
6.广义表A=(a,(b),(),(c,d,e))的长度为（ ）
A.4 B.5 C.6 D.7
7.一棵含18个结点的二叉树的高度至少为（ ）
A.3 B.4 C.5 D.6
8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ ）
A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA
9.无向图中一个顶点的度是指图中（ ）
A.通过该项点的简单路径数 B.与该顶点相邻接的顶点数
C.通过该顶点的回路数 D.与该顶点连通的顶点数
10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为（ ）
A.a c e f b d
B.a c b d f e
C.a c b d e f
D.a c d b f e
11.在下列排序方法中，平均时间性能为O(nologn)且空间性能最好的是（ ）
A.快速排序 B.堆排序 C.归并排序 D.基数排序
12.已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是（ ）
A.{25，36，48，72，23，40，79，82，16，35}
B.{25，36，48，72，16，23，40，79，82，35}
C.{25，36，48，72，16，23，35，40，79，82}
D.{16，23，25，35，36，40，48，72，79，82}
13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ ）
A.21 B.23 C.41 D.62
14.索引非顺序文件的特点是（ ）
A.主文件无序，索引表有序 B.主文件有序，索引表无序
C.主文件有序，索引表有序 D.主文件无序，索引表无序
15.倒排文件的主要优点是（ ）
A.便于进行插入和删除运算 B.便于进行文件的恢复
C.便于进行多关键字查询 D.节省存储空间第二部分 非选择题（共70分）
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。
16.抽象数据类型的特点是将 和 封装在一起，从而实现信息隐藏。
17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。
18.在队列中，允许进行插入操作的一端称为,允许进行删除操作的一端称为 。
19.如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”的判定条件是 。
20.设S1=“good”，S2=,”，S3=“book”，则S1，S2和S3依次联接后的结果是 。
21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是 。
22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为 。
23.能够成功完成拓扑排序的图一定是一个 。
24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用
较为适当。
25.假设哈希表的表长 m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为 。
三、解答题（本大题共4小题，每小题5分，共20分）
26.假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符的在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码。
27.已知一个图如下所示，其顶点按a.b.c.d.e.f顺序存放在邻接表的顶点表中，请画出该图的邻接表，
使得按此邻接表进行深度优先遍历时得到的顶点序列为a.c.b.e.f.d，进行广度优先遍历时得到的顶点序列为a c b d f e。
28.已知两个4×5的稀疏矩阵的三元组表分别如下：
0
1
4
16
1
2
2
18
2
3
4
-25
3
4
2
28
0
1
1
32
1
2
2
-22
2
2
5
69
3
3
4
25
4
4
2
51
请画出这两个稀疏矩阵之和的三元组表。
29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。
（1）画出该二叉排序树
（2）画出删去该树中元素值为90的结点之后的二叉排序树。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：
typedef sturct{
DataType data[MaxSize];
int front [2],length[2];
} Queue2;
对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容,
实现第i个循环队列的入队操作。
int EnQueue (Queue2 *Q,int i,DataType x)
{ // 若第i个队列不满，则元素x入队列，并返回1，否则返回0
if (i＜0 || i＞1)return 0;
if ( (1) )
return 0;
Q-＞data[ (2) ]=x;
Q-＞length[ (3) ]++;
return 1;
}
31.某二叉树的线索链表存储结构如图（b）所示，其中 p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：
（1）写出执行函数调用f(p)的输出结果；
（2）简述函数f 的功能。
void f (BinThrTree t)
{
while (t)
{
printf(t-＞date);
if (t-＞lchild)
t=t-＞lchild;
else
t=t-＞rchild;
}
}
（1）
（2）
32.下列函数FindCycle (G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点Vi的简单回路。数据cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点Vk的下一个顶点Vj。请在空缺处填入合适的内容，使其成为一个完整的算法。
已知邻接表的顶点表结点结构为：
vertex
firstedge
边表结点EdgeNode结构为：
adjvex
next
int cycle_ path[MaxNurm];
int FindCycle (ALGraph * G,int i)
{ //若回路存在，则返回1,否则返回0
int j;
for (j=0; j＜G-＞n; j++) cycle_path[j]=-1;
return DFSPath (G,i,i );
}
int DFSPath (ALGraph *G,int j,int i )
{
EdgeNode * p;
Int cycled=0;
for (p=G-＞adjlist[j].firstedge; p &&! cycled; p=p-＞next)
{
cycle_path[j]=p-＞adjvex;
if ( (1) )cycled=1; //已找到回路
else
if (cycle_path[p-＞adjvex]==-1) cycled= (2) ;
}
return (3) ;
}
33.阅读下列函数algo，并回答问题。
（1）假设整型数组A[1..8]中的元素依次为（3，8，9，1，7，4，2，6）。执行函数调用algo（A，8）时，外层while的循环体执行多少次？函数的返回值是多少？
（2）简述函数algo（L，n）的功能。
int algo (int L[ ],int n)
{
int i=0,j,s=1,t=n;
while (i! =(n+1)/2)
{
int x =L[s];
i=s; j=t;
while (i＜j)
{
while (i＜j &&L[j]＞=x)j--;
L[i]=L[j];
while (i＜j &&L[i]＜=x)i++;
L[j]=L[i];
}
L[i]=x;
if (x＜(n+1)/2) s=i+1;
else t =i-1;
}
if (i ==0) return 0;
else return L[i];
}
(1)
(2)
五、算法设计题（本题共10分）
34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为0（n）的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：
（7，10，10，21，30，42，42，42，51，70）
经算法操作后变为（7，10，21，30，42，51，70）
