全真试题（四）
本试卷分两部分，第一部分为选择题，1页至2页，第二部分为非选择题，3页至12页，共12页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1.下列各式中，按增长率由小至大的顺序正确排列的是（ ）
A.,n!,2n,n3/2 B.n3/2,2n,nlogn,2100 C.2n,logn,nlogn,n3/2 D.2100,logn,2n,nn
2.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ ）
A.s-＞next=p-＞next; p-＞next=s; B.p-＞next=s; s-＞next=p-＞next
C.p-＞next=s-＞next; s-＞next=p; D.s-＞next=p;p-＞next=s-＞next;
3.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（ ）
A.各自的头结点 B.各自的尾结点
C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点
4.栈的两种常用存储结构分别为（ ）
A.顺序存储结构和链式存储结构 B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构 D.链式存储结构和散列存储结构
5.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队的当前长度为（ ）
A.5 B.6 C.16 D.17
6.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为（ ）
typedef struct node{
char date[8];
struct node * next;
} LinkStrNode;
A.1/4 B.1/2 C.2/3 D.3/4
7.应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模式匹配，在匹配成功时，进行的字符比较总次数为（ ）
A.7 B.9 C.10 D.12
8.二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为（ ）
A.574 B.576 C.578 D.580
9.对广义表L=((a,b),c,d)进行操作tail (head (L))的结果是（ ）
A.(c,d ) B.(d ) C.b D.(b)
10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（ ）
A.ABCDEF B.ABCEFD C.ABFCDE D.ABCDFE
11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）
A.O(n) B.O(e) C.O(n+e) D.O(n2)
12.在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ ）
A.4，4，3 B.4,3,3 C.3，4，4 D.3，3，4
13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ）
A.冒泡排序 B.直接选择排序 C.堆排序 D.归并排序
14.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）
A.1.0 B.2.9 C.3.4 D.5.5
15.在下列各种文件中，不能进行顺序查找的文件是（ ）
A.顺序文件 B.索引文件 C.散列文件 D.多重表文件第二部分 非选择题（共70分）
二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。
16.抽象数据类型是指数据逻辑结构及与之相关的 。
17.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的 结点。
q=p;
while (q-＞next!=p)q=p-＞next;
18.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为 。
19.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的 运算。
20.假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为 。
21.在含100个结点的完全二叉树中，叶子结点的个数为 。
22.在无向图中，若从顶点a到顶点b存在,则称a与b之间是连通的。
23.如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。
24.索引顺序查找适宜对 的顺序表进行查找。
25.文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及 。
三、解答题（本大题共4小题，每小题5分，共20分）
26.画出下图所示二叉树的中序线索链表的存储表示。
27.已知图G=（V，E），其中：
V={a,b,c,d,e},
E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。
（1）画出图G；
（2）画出图G的邻接表。
28.已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。
void MergeSortDC(SeqList R,int low,int high)
{//用分治法对R[low.,high]进行二路归并排序
int mid;
if (low＜high＝{ //区间长度大于1
mid=(low+high)/2 //分解
MergeSortDC(R,low,mid); //递归地对R[low..mid]排序
MergeSortDC(R,mid+1,high); //递归地对R[mid+1..high]排序
Merge(R,low,mid,high); //组合，将两个有序区归并为一个有序区
}
}// MergeSortDC
29.由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L,intc)
{
LinkList Lc,p,pre;
pre=L;
p= (1) ;
Lc=(LinList)malloc(sizeof(ListNode));
Lc-＞next=Lc;
while (p!=L)
if (p-＞data＞c)
{
pre-＞next=p-＞next;
(2) ;
Lc-＞next=p;
p=pre-＞next;
}
else
{
pre=p;
(3) ;
}
return Lc;
}
31.设栈S=（1，2，3，4，5，6，7）其中7为栈顶元素。
（1）写出调用f31(&S)后的S；
（2）简述函数f31中第1个循环语句的功能。
void f31 (Stack * S)
{
Queue Q;
Stack T;
int i=0;
InitQueue(&Q);
InitStack(&T);
while (!StackEmpty(S))
if ((i=!i)!=0) Push(&T,Pop(S));
else EnQueue(&Q,Pop(S));
while (!StackEmpty(&T))
Push(S,Pop(&T));
while(!QueueEmpty(&Q))
Push(S,DeQueue(&Q));
}
32.图的邻接矩阵表示描述如下：
#define MaxNum 20 //图的最大顶点数
typedef struct{
char vexs[MaxNum]; //字符类型的顶点表
int edges[MaxNum][MaxNum]; //邻接矩阵
int n,e; //图的顶点数和边数
}MGraph; //图的邻接矩阵结构描述阅读下列算法，并回答问题：
（1）对于下列图G的邻接矩阵，写出函数调用F32（&G,3）的返回值；
（2）简述函数f32的功能；
（3）写出函数f32的时间复杂度。
int f32(MGraph *G,int i)
{
int d=0,j;
for (j=0; j＜G-＞n; j++)
{
if (G-＞edges[i][j])d++;
if( G-＞edges[j][i])d++;
}
return d;
}
33.阅读下列算法并回答问题：
（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33（L，8）之后的L[1..8]中的元素值；
（2）简述函数f33的功能。
void f33(intR[ ],int n)
{
int x =R [1];
int low =1,high=n;
while (low＜high)
{
while (low＜high && R[high]＞0)
high--;
if (low＜high＝
{
R[low++]=R[high];
while (low＜high && R[low] ＜0)
low++;
R[high--]=R[low];
}
}
R[low]=x;
}
五、算法设计题（本题共10分）
34.假设二叉链表作为二叉树的存储结构，其特点结构为：
lchild
data
Rchild
依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为0。
void f34(BinTree T,int level,int *lmin,int *lmax);
本试卷分两部分，第一部分为选择题，1页至2页，第二部分为非选择题，3页至12页，共12页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1.下列各式中，按增长率由小至大的顺序正确排列的是（ ）
A.,n!,2n,n3/2 B.n3/2,2n,nlogn,2100 C.2n,logn,nlogn,n3/2 D.2100,logn,2n,nn
2.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ ）
A.s-＞next=p-＞next; p-＞next=s; B.p-＞next=s; s-＞next=p-＞next
C.p-＞next=s-＞next; s-＞next=p; D.s-＞next=p;p-＞next=s-＞next;
3.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（ ）
A.各自的头结点 B.各自的尾结点
C.各自的第一个元素结点 D.一个表的头结点，另一个表的尾结点
4.栈的两种常用存储结构分别为（ ）
A.顺序存储结构和链式存储结构 B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构 D.链式存储结构和散列存储结构
5.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队的当前长度为（ ）
A.5 B.6 C.16 D.17
6.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为（ ）
typedef struct node{
char date[8];
struct node * next;
} LinkStrNode;
A.1/4 B.1/2 C.2/3 D.3/4
7.应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模式匹配，在匹配成功时，进行的字符比较总次数为（ ）
A.7 B.9 C.10 D.12
8.二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为（ ）
A.574 B.576 C.578 D.580
9.对广义表L=((a,b),c,d)进行操作tail (head (L))的结果是（ ）
A.(c,d ) B.(d ) C.b D.(b)
10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（ ）
A.ABCDEF B.ABCEFD C.ABFCDE D.ABCDFE
11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）
A.O(n) B.O(e) C.O(n+e) D.O(n2)
12.在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ ）
A.4，4，3 B.4,3,3 C.3，4，4 D.3，3，4
13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ）
A.冒泡排序 B.直接选择排序 C.堆排序 D.归并排序
14.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）
A.1.0 B.2.9 C.3.4 D.5.5
15.在下列各种文件中，不能进行顺序查找的文件是（ ）
A.顺序文件 B.索引文件 C.散列文件 D.多重表文件第二部分 非选择题（共70分）
二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。
16.抽象数据类型是指数据逻辑结构及与之相关的 。
17.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的 结点。
q=p;
while (q-＞next!=p)q=p-＞next;
18.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为 。
19.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的 运算。
20.假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为 。
21.在含100个结点的完全二叉树中，叶子结点的个数为 。
22.在无向图中，若从顶点a到顶点b存在,则称a与b之间是连通的。
23.如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。
24.索引顺序查找适宜对 的顺序表进行查找。
25.文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及 。
三、解答题（本大题共4小题，每小题5分，共20分）
26.画出下图所示二叉树的中序线索链表的存储表示。
27.已知图G=（V，E），其中：
V={a,b,c,d,e},
E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。
（1）画出图G；
（2）画出图G的邻接表。
28.已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。
void MergeSortDC(SeqList R,int low,int high)
{//用分治法对R[low.,high]进行二路归并排序
int mid;
if (low＜high＝{ //区间长度大于1
mid=(low+high)/2 //分解
MergeSortDC(R,low,mid); //递归地对R[low..mid]排序
MergeSortDC(R,mid+1,high); //递归地对R[mid+1..high]排序
Merge(R,low,mid,high); //组合，将两个有序区归并为一个有序区
}
}// MergeSortDC
29.由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L,intc)
{
LinkList Lc,p,pre;
pre=L;
p= (1) ;
Lc=(LinList)malloc(sizeof(ListNode));
Lc-＞next=Lc;
while (p!=L)
if (p-＞data＞c)
{
pre-＞next=p-＞next;
(2) ;
Lc-＞next=p;
p=pre-＞next;
}
else
{
pre=p;
(3) ;
}
return Lc;
}
31.设栈S=（1，2，3，4，5，6，7）其中7为栈顶元素。
（1）写出调用f31(&S)后的S；
（2）简述函数f31中第1个循环语句的功能。
void f31 (Stack * S)
{
Queue Q;
Stack T;
int i=0;
InitQueue(&Q);
InitStack(&T);
while (!StackEmpty(S))
if ((i=!i)!=0) Push(&T,Pop(S));
else EnQueue(&Q,Pop(S));
while (!StackEmpty(&T))
Push(S,Pop(&T));
while(!QueueEmpty(&Q))
Push(S,DeQueue(&Q));
}
32.图的邻接矩阵表示描述如下：
#define MaxNum 20 //图的最大顶点数
typedef struct{
char vexs[MaxNum]; //字符类型的顶点表
int edges[MaxNum][MaxNum]; //邻接矩阵
int n,e; //图的顶点数和边数
}MGraph; //图的邻接矩阵结构描述阅读下列算法，并回答问题：
（1）对于下列图G的邻接矩阵，写出函数调用F32（&G,3）的返回值；
（2）简述函数f32的功能；
（3）写出函数f32的时间复杂度。
int f32(MGraph *G,int i)
{
int d=0,j;
for (j=0; j＜G-＞n; j++)
{
if (G-＞edges[i][j])d++;
if( G-＞edges[j][i])d++;
}
return d;
}
33.阅读下列算法并回答问题：
（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33（L，8）之后的L[1..8]中的元素值；
（2）简述函数f33的功能。
void f33(intR[ ],int n)
{
int x =R [1];
int low =1,high=n;
while (low＜high)
{
while (low＜high && R[high]＞0)
high--;
if (low＜high＝
{
R[low++]=R[high];
while (low＜high && R[low] ＜0)
low++;
R[high--]=R[low];
}
}
R[low]=x;
}
五、算法设计题（本题共10分）
34.假设二叉链表作为二叉树的存储结构，其特点结构为：
lchild
data
Rchild
依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为0。
void f34(BinTree T,int level,int *lmin,int *lmax);
