《数据结构》试卷选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分)1.在数据结构中，与所使用的计算机无关的是数据的（）结构。

A.逻辑B.存储C.逻辑和存储D.物理2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。

A.单链表B.双链表C.顺序表D.单循环链表3.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。

A.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1B.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C.-1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1D.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，4.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。

A.13B.33C.18D.405.一棵含有101个结点的完全二叉树存储在数组bt[102]中，其中bt[0]不用，若bt[k]是叶子结点，则k的最小值是（）。

A.51B.50C.49D.486.稀疏矩阵一般的压缩存储方法有两种，即（）。

A.二维数组和三维数组B.三元组表和散列表C.三元组表和十字链表D.散列表和十字链表7.对顺序存储的18个数据元素（A[1]~A[18]）的有序表做二分查找，则查找A[3]的比较序列的下标为( )。

A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，38.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关，这种说法（）。

A.正确B.错误9.下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是（）。

A.堆排序B.冒泡排序C.直接插入排序D.快速排序10.在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型调整使其平衡。

A.LLB.LRC.RLD.RR11.在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该缓冲区应是一个（）结构。

A.堆栈B.队列C.顺序表D.链表二、填空题（每空2分，共18分）1.以下程序段的时间复杂度是________________________，其中n为正整数。

int i=1;while(i<=n)i=i*2;2.对顺序存储结构的线性表，设表长为n；在等概率假设条件下，插入一个数据元素需平均移动表中元素______________个；在最坏情况下需移动表中元素______________个。

3.设树T的度为4，其中度为1、2、3、4的结点的个数分别为4、3、2、1，则树T的叶子结点的个数是。

4.判定一个环形队列qu（最多元素为MaxSize）为空的条件是__________________________________________，判定环形队列qu为满队列的条件是___________________________________ __ _____。

5.设森林T中有4棵树，结点个数依次为n1, n2, n3, n4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有________________________个结点。

6.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。

若这6个元素出队列的顺序为b，d，c，f，e，a，则栈S的容量至少应该是________________。

7.用head和tail函数，取出广义表L=((x,y,z),(a,b,c,d))中元素b的运算是_____________________________________________________________________。

三、解答下列问题（共30分）1.（本题6分）已知一颗二叉树的中序遍历序列为DCEFBHGAKJLIM, 后序遍历序列为DFECHGBKLJMIA，问：能不能唯一确定一颗二叉树？若能，画出该二叉树。

2.（本题8分）设有一组关键字序列：（29，18，25，47，58，12，51，10）要按照关键字值递增的次序进行排序。

A.若采用初始增量为4的希尔排序，写出第一趟排序的结果：B.若采用以第一个元素为基准元素的快速排序法，写出第一趟排序的结果：C.若采用二路归并排序，写出第一趟排序的结果:3.（本题8分）以下面给出的数据序列作为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度WPL。

{4，5，6，7，10，12，15，18，23}4.（本题8分）设有一组关键字（100，20，21，35，3，78，99，45），采用哈希函数H(K)=K%7，采用开放地址的线性探查法处理冲突，试在０至8的哈希地址空间中，对该关键字序列构造哈希表，并求出在等概率情况下查找成功的平均查找长度ASL。

四、算法填空（每空2分，共14分）1.下面是一个二叉树中序遍历的非递归算法，请在空白处填上适当内容，使其成为一个完整算法。

void Inorder(BTNode *b) //二叉树中序遍历非递归算法{ BTNode *St[MaxSize],*p;int top=-1;if(b!=NULL){p=b;while(top>-1||p!=NULL){ while(p!=NULL){ top++;St[top]=p;；}if(top>-1){ p=St[top];top--;printf(“%c”, p->data);；}}printf(“\n”);}}2.设二叉排序树采用二叉链表存储，以下递归算法从大到小输出二叉排序树结点值（data），请将算法补充完整。

InOrderBST(BTNode *b) //二叉排序树从大到小输出{if(b!=NULL){InOrderBST( );printf(“%c”, );InOrderBST( );}}3.下面是一个堆排序算法，请在空白处填上适当内容，使其成为一个完整算法。

其中sift为筛选算法，原型为：void sift(RecType R[], int low , int high);void HeapSort(RecType R[], int n) //堆排序算法{ int i;RecType temp;for(i= ; i>=1; i--) //循环建立初始堆sift（R, i , n ）for(i=n;i>=2;i--){ temp=R[1];R[1]=R[i];R[i]=temp;sift（）; //重建堆}}五、算法设计题1.(本题10分)设计一个算法Reverse，利用环形队列和顺序栈的基本运算将指定队列中的内容逆置。

2.（本题6分）设计一个算法MatToList，将无向图的邻接矩阵g转换为邻接表G，相关类型定义如下：//邻接矩阵相关定义#define MAXV <最大顶点个数〉typedef struct{ int no;InfoType info;}VertexType;typedef struct{ int edges[MAXV][MAXV];int n, e;VertexType vexs[MAXV];}MGraph;//邻接表相关定义typedef struct Anode{ int adjvex;struct Anode *nextarc;InfoType info;}ArcNode;typedef struct Vnode{ vertex data;ArcNode *firstarc;}VNode;typedef VNode AdjList[MAXV]; typedef struct{ AdjList adjlist;int n,e;}ALGraph;《数据结构》参考答案一、选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分)1.A2.C3.B4.B5.A6.C7.D8.A9.C 10.B 11.B二、填空题（每空2分，共18分）1.O（log2n）2.(1)n/2 (2) n3.114.(1)qu->rear= =qu->front(2)(qu->rear+1)%MaxSize= =qu->front5.n2+n3+n46. 37.head(tail(head(tail(L))))三、解答下列问题（共30分）1.能ABC G J MD E H K LF2.A.(29,12,25,10,58,18,51,47)B.(10,18,25,12,29,58,51,47)C.(18,29,25,47,12,58,10,51)3.10058 4225 33 23 1912 13 15 18 10 96 7 4 5WPL=2994.ASL=(4*1+1*2+1*4+2*5)/8=2.5四、算法填空（每空2分，共14分）1.(1)p=p->lchild;(2)p=p->rchild2.(1)b->rchild(2)b->data(3)b->lchild3.(1)n/2(2) R, 1, i-1五、算法设计题1.（10分）void Reverse(SqQueue *&q){ ElemType x;SqStack st;InitStack(&st);while(!QueueEmpty(q)){ deQueue(q,x);Push(&st, x);}while(!StackEmpty(&st)){ Pop(&st, x);enQueue(q,x);}}2.（6分）void MatToList(Mgraph g, ALGraph *&G){ int i, j, n=g.n;ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));for(i=0; i<n; i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0){ p=(ArcNode *)malloc(sizeof(ArcNode))p->adjvex=j;p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n; G->e=g.e;}。