一、单项选择题(本大题共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.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( )
A.356 B.358 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.ALV树是一种平衡的二叉排序树，树中任一结点的( )
A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度
15.在VSAM文件的控制区间中，记录的存储方式为( )
A.无序顺序 B.有序顺序
C.无序链接 D.有序链接
二、填空题(本大题共10小题，每小题2分， 若有两个空格，每个空格1分，共20分)
16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。
17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。
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的先序遍历序列为ABCDEFGHJKL，后序遍历序列为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->next;
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(!QueueEmpty(Q))
Push(&S,DeQueue(&Q));
while(!StackEmpty(T))
Push(&S,Pop(&T))；
}
32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：
#define MaxNum 50//图的最大顶点数
#define INFINITY INT_MAX //INT_MAX为最大整数，表示∞
typedef struct{
char vexs[MaxNum];//字符类型的顶点表
int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵
int n,e;//图中当前的顶点数和边数
}MGraph;//邻接矩阵结构描述
typedef struct node {
int adjvex;//邻接点域
int weight;//边的权值
struct node *next;//链指针域
} EdgeNode;//边表结点结构描述
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->edges[i][j]<INFINITY)
{
p=(EdgeNode *) malloc(sizeof(EdgeNode));
p->weight= (2) ;
p->adjvex=j;
p->next=G2->adjlist[i].firstedge;
(3) ;
}
}
(1)
(2)
(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 {
DataType data;
struct node *lchild,*rchild,*parent;
}PBinTree;
其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。
http://kao.xuezhishi.net/schooling/study/2007-01-26/9342.html
