全真试题（二）
本试卷分两部分，第一部分为选择题，1页至2页，第二部分为非选择题，3页至10页，共10页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ ）
A.顺序存储结构 B.链式存储结构
C.索引存储结构 D.散列存储结构
2,在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ ）
A.n-i+1 B.n-i C.i D.i-1
3,对于只在表的首.尾两端进行插入操作的线性表，宜采用的存储结构为（ ）
A.顺序表 B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表 D.单链表
4,若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为（ ）
A.4 B.5 C.6 D.7
5,为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ）
A.插入 B.删除 C.串联接 D.子串定位
6,已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7)后得到（ ）
A.P=“SCIENCE” B.P=“STUDY” C.S=“SCIENCE,D.S=“STUDY”
7,三维数组h[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为（ ）
A.356 B.385 C.360 D.362
8,如右图所示广义表是一种（ ）
A.线性表 B.纯表 C.结点共享表 D.递归表
9,下列陈述中正确的是（ ）
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分
10,n个顶点的有向完全图中含有有向边的数目最多为（ ）
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
11,已知一个有向图如右所示，
则从顶点a出发进行深度优先遍历，
不可能得到的DFS序列为（ ）
A.a d b e f c B.a d c e f b
C.a d c b f e D.a d e f c b
12,在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是（ ）
A.快速排序 B.堆排序 C.归并排序 D.基数排序
13,不可能生成右图所示二叉排序树的关键字序列是（ ）
A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5
14,AVL树是一种平衡的二叉排序树，树中任一结点的（ ）
A.左.右子树的高度均相同 B.左.右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度
15,在VSAM文件的控制区间中，记录的存储方式为（ ）
A.无序顺序 B.有序顺序 C.无序链接 D.有序链接第二部分 非选择题（共70分）
二.填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。
16,若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。
17,在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是 和 。
题17图
18,假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。
19,串S=“I am a worker”的长度是 。
20,假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为 。
21,在n个结点的线索二叉链表中，有 个线索指针。
22,若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 。
23,对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为 。
24,由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到 。
25,若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是 。
三.解答题（本大题共4小题，每小题5分，共20分）
26,已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵（注：矩阵元素的行列下标均从1开始）。
27,已知树T的先序遍历序列为ABCDEFGHIJKL后序遍历序列为CBEFDJIKLHGA。请画出树T。
28,对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。
初始堆,
第1趟,
第2趟,
第3趟,
29,在关键字序列（07，12，15，18，27，32，41，92）中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。
四.算法阅读题（本大题共4小题，每小题5分，共20分）
30,以下函数中，h是带头结点的双向循环链表的头指针。
（1）说明程序的功能 ；
（2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。
int f (DlistNode * h)
{
DlistNode * p,* q;
int j=1;
p=h-＞nest;
q=h-＞prior;
while(p != q && p-＞prior != q)
if (p-＞data==q-＞data)
{
p=p-＞next;
q=q-＞prior;
}
else j =0;
return j;
}
31,设栈S=（1，2，3，4，5，6，7），其中7为栈顶元素。请写出调用algo（&S）后栈S的状态。
void algo (Stack *S)
{
int i =0;
Queue Q; Stack T;
InitQueue(&Q); InitStack(&T);
while (!StackEmpty(S))
{
if ((i=!i) !=0) Push(&T,Pop(&S));
else EnQueue(&Q,Pop(&S));
}
while (! Queue Empty(Q))
Push(&S,DeQueue(&Q));
while (!StackEmpty(T))
Push (&S,Pop(&T));
}
32,已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：
# define MaxNum 50 //图的最大顶点数
# define INFINITY INT_MAX //INT_MAX为最大一整数，表示∞
typedef struce{
char vexs[MaxnNum]; //字符类型的顶点表
int edges[MaxNum][MaxNum]; //权值为整型的邻接矩阵
int n,e; //图中当前的顶点数和边数
} MGraph; //邻接矩阵结构描述
typedef struct node{
int adjvex; //邻接点域
int weight; //边的权值
struct node *next; //链指针域
} EdgeNode *next; //边表结点结构描述
typedef struct{
char vertex; //顶点域
EdgeNode* firstedge; //边表头指针
} VertexNode; //顶点表结点结构描述
typedef struct{
VertexNode adjlist[MaxNum]; //邻接表
int n,e; //图中当前的顶点数和边数
} ALGraph; //邻接表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。
void convertM(MGraph * G1,ALGraph *G2)
{
int i,j;
EdgeNode *p;
G2-＞n=G1-＞n;
G2-＞e=G1-＞e;
for (i=0; i＜G1-＞n; i++ )
{
G2-＞adjlist[i].vertex=G1-＞vexs[i];
G2-＞adjlist[i].firstedge= (1) ;
}
for (i=0; i＜G1-＞n; i++ )
for (j=0; j＜G1-＞n; j++ )
if (G1-＞deges[i][j]＜INFINITY
{
p=(Edge Node *)malloc (sizeof (EdgeNode));
p-＞weight= (2) ;
p-＞adjvex=j;
p-＞next=G2-＞adjlist[i].firstedge;
(3) ;
}
}
33.阅读下列算法，并回答下列问题：
（1）该算法采用何种策略进行排序？
（2）算法中R[n+1]的作用是什么？
typedef struct {
KeyType key;
infoType otherinfo;
}nodeType;
typedef nodeType SqList [MAXLEN];
void sort (SqList R,int n)
{
// n 小于MAXLEN-1
int k,i;
for (k=n-1; k＞=1; k--)
if (R[k].key＞R[k+1].key)
{
R[n+1]=R[k];
for (i=k+1; R[i].key＜R[n+1].key; i++)
R[i-1]=R[i];
R[i-1]=R[n+1];
}
}
三.算法设计题（本题共10分）
34,假设二叉树T采用如下定义的存储结构：
typedef struct node{
DateType data;
Struct node * lchild,*rchild,*parent;
} PBinTree;
其中，结点的lchild域和rchild域已分别填有指向其左.右孩子结点的指针，而parent域中的值为空指针（拟作为指向双亲结点的指针域）。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。
本试卷分两部分，第一部分为选择题，1页至2页，第二部分为非选择题，3页至10页，共10页；选择题30分，非选择题70分，满分100分。考试时间150分钟。
第一部分 选择题（共30分）
一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。
1、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ ）
A.顺序存储结构 B.链式存储结构
C.索引存储结构 D.散列存储结构
2,在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ ）
A.n-i+1 B.n-i C.i D.i-1
3,对于只在表的首.尾两端进行插入操作的线性表，宜采用的存储结构为（ ）
A.顺序表 B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表 D.单链表
4,若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为（ ）
A.4 B.5 C.6 D.7
5,为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ）
A.插入 B.删除 C.串联接 D.子串定位
6,已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7)后得到（ ）
A.P=“SCIENCE” B.P=“STUDY” C.S=“SCIENCE,D.S=“STUDY”
7,三维数组h[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为（ ）
A.356 B.385 C.360 D.362
8,如右图所示广义表是一种（ ）
A.线性表 B.纯表 C.结点共享表 D.递归表
9,下列陈述中正确的是（ ）
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分
10,n个顶点的有向完全图中含有有向边的数目最多为（ ）
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
11,已知一个有向图如右所示，
则从顶点a出发进行深度优先遍历，
不可能得到的DFS序列为（ ）
A.a d b e f c B.a d c e f b
C.a d c b f e D.a d e f c b
12,在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是（ ）
A.快速排序 B.堆排序 C.归并排序 D.基数排序
13,不可能生成右图所示二叉排序树的关键字序列是（ ）
A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5
14,AVL树是一种平衡的二叉排序树，树中任一结点的（ ）
A.左.右子树的高度均相同 B.左.右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度
15,在VSAM文件的控制区间中，记录的存储方式为（ ）
A.无序顺序 B.有序顺序 C.无序链接 D.有序链接第二部分 非选择题（共70分）
二.填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。
16,若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。
17,在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是 和 。
题17图
18,假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。
19,串S=“I am a worker”的长度是 。
20,假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为 。
21,在n个结点的线索二叉链表中，有 个线索指针。
22,若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 。
23,对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为 。
24,由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到 。
25,若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是 。
三.解答题（本大题共4小题，每小题5分，共20分）
26,已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵（注：矩阵元素的行列下标均从1开始）。
27,已知树T的先序遍历序列为ABCDEFGHIJKL后序遍历序列为CBEFDJIKLHGA。请画出树T。
28,对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。
初始堆,
第1趟,
第2趟,
第3趟,
29,在关键字序列（07，12，15，18，27，32，41，92）中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。
四.算法阅读题（本大题共4小题，每小题5分，共20分）
30,以下函数中，h是带头结点的双向循环链表的头指针。
（1）说明程序的功能 ；
（2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。
int f (DlistNode * h)
{
DlistNode * p,* q;
int j=1;
p=h-＞nest;
q=h-＞prior;
while(p != q && p-＞prior != q)
if (p-＞data==q-＞data)
{
p=p-＞next;
q=q-＞prior;
}
else j =0;
return j;
}
31,设栈S=（1，2，3，4，5，6，7），其中7为栈顶元素。请写出调用algo（&S）后栈S的状态。
void algo (Stack *S)
{
int i =0;
Queue Q; Stack T;
InitQueue(&Q); InitStack(&T);
while (!StackEmpty(S))
{
if ((i=!i) !=0) Push(&T,Pop(&S));
else EnQueue(&Q,Pop(&S));
}
while (! Queue Empty(Q))
Push(&S,DeQueue(&Q));
while (!StackEmpty(T))
Push (&S,Pop(&T));
}
32,已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：
# define MaxNum 50 //图的最大顶点数
# define INFINITY INT_MAX //INT_MAX为最大一整数，表示∞
typedef struce{
char vexs[MaxnNum]; //字符类型的顶点表
int edges[MaxNum][MaxNum]; //权值为整型的邻接矩阵
int n,e; //图中当前的顶点数和边数
} MGraph; //邻接矩阵结构描述
typedef struct node{
int adjvex; //邻接点域
int weight; //边的权值
struct node *next; //链指针域
} EdgeNode *next; //边表结点结构描述
typedef struct{
char vertex; //顶点域
EdgeNode* firstedge; //边表头指针
} VertexNode; //顶点表结点结构描述
typedef struct{
VertexNode adjlist[MaxNum]; //邻接表
int n,e; //图中当前的顶点数和边数
} ALGraph; //邻接表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。
void convertM(MGraph * G1,ALGraph *G2)
{
int i,j;
EdgeNode *p;
G2-＞n=G1-＞n;
G2-＞e=G1-＞e;
for (i=0; i＜G1-＞n; i++ )
{
G2-＞adjlist[i].vertex=G1-＞vexs[i];
G2-＞adjlist[i].firstedge= (1) ;
}
for (i=0; i＜G1-＞n; i++ )
for (j=0; j＜G1-＞n; j++ )
if (G1-＞deges[i][j]＜INFINITY
{
p=(Edge Node *)malloc (sizeof (EdgeNode));
p-＞weight= (2) ;
p-＞adjvex=j;
p-＞next=G2-＞adjlist[i].firstedge;
(3) ;
}
}
33.阅读下列算法，并回答下列问题：
（1）该算法采用何种策略进行排序？
（2）算法中R[n+1]的作用是什么？
typedef struct {
KeyType key;
infoType otherinfo;
}nodeType;
typedef nodeType SqList [MAXLEN];
void sort (SqList R,int n)
{
// n 小于MAXLEN-1
int k,i;
for (k=n-1; k＞=1; k--)
if (R[k].key＞R[k+1].key)
{
R[n+1]=R[k];
for (i=k+1; R[i].key＜R[n+1].key; i++)
R[i-1]=R[i];
R[i-1]=R[n+1];
}
}
三.算法设计题（本题共10分）
34,假设二叉树T采用如下定义的存储结构：
typedef struct node{
DateType data;
Struct node * lchild,*rchild,*parent;
} PBinTree;
其中，结点的lchild域和rchild域已分别填有指向其左.右孩子结点的指针，而parent域中的值为空指针（拟作为指向双亲结点的指针域）。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。
