算法与数据结构考试试卷

《算法与数据结构》考试一试卷东莞理工学院（本科）试卷（A卷）2009-2010学年第二学期《算法与数据结构》试卷（A卷）一、填空题（每题2分，共18分）:1、对于给定的n个元素,能够结构出的逻辑结构有会合,，业专和四种。级年2、数据结构中评论算法的两个重要指标是和。3、在次序存储结构中，逻辑上相邻的数据元素，其物理地点，在单链表中，逻辑上相邻的数据元素，其物理地点。4、栈是操作受限的线性表，其操作数据的基来源则是，允许进行插入和删除操作的一端称为。:5、设有一个二维数组A[10][10]，若每个元素占6个基本存储单元，A[0][0]的地点是别)系1000，若按行优先（以行为主）次序存储，则元素A[6][8]的存储地点是；若按列优先（以列为主）次序存储，则元素A[6][8]的存储地点是。6、设有一棵深度为n的完全二叉树，该二叉树起码有个结点，至多有个结点。7、若采用毗邻矩阵存储一个图所需要的存储单元取决于图的；无向图的(毗邻矩阵一定是。:8、在进行排序时，最基本的操作是和。号9、在查找时，若采用折半查找，要求线性表，而哈希表的查找，要求学线性表。二、单项选择题（请将答案写在题目后的括号中。每题2分，共1、设有长度为n的数组a,假定已经赋值，下面程序段的时间复杂度是（:for(i=0;i<n-1;i++)名{k=i;姓for(j=i+1;j<n;j++)if(a[k]>a[j])k=j;if(k!=i){temp=a[i];a[i]=a[k];a[k]=temp;}1/7

分））。业专级年

《算法与数据结构》考试一试卷}（A）O(n)（B）O(n2)（C）O(㏒2n)（D）O(n㏒2n)2、设有以head为头结点的非空单循环链表，链表中只有一个结点条件是（）。（A）head->next=head；（B）head->next=head->next；（C）head->next->next=head；（D）head->next->next=head->next；3、设有一个大小为Max的循环行列Q，判断该行列为满的条件是（）。（A）Q.rear-Q.front==Max（B）Q.rear-Q.front-1==Max（C）Q.rear==Q.front（D）(Q.rear+1)%Max==Q.front4、二叉树是非线性结构，因此（）（A）不能用次序存储结构存储（B）不能用链式存储结构存储（C）既能用链式存储结构存储，也能用次序存储结构存储（D）既不能用链式存储结构存储，也不能用次序存储结构存储5、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是（）。（A）gdehickjfba（B）gdhiecfkjba（C）dghieckjfba（D）gdhieckjfba6、在一个有向图中，所有极点的出度之和等于所有极点的入度之和的倍，所有极点的度之和等于所有极点的出度之和的倍。（）（A）1/2，1（B）1，2（C）2，1（D）1，47、对于有n个极点e(e>n)条边的带权无向图，以下对于该图的最小生成树的描绘正确的是（）。（A）最小生成树是唯一的。（B）最小生成树中所有边上的权值之和是唯一的。（C）最小生成树有n条边。（D）最小生成树有n个极点e-1条边。8、设相重点会合{21，12，46，40，32，29，65，53}，采用冒泡排序法进行一趟排序操作后的结果是（）。（A）12，21，46，40，32，29，53，65（B）12，21，40，46，32，29，53，65（C）12，21，40，32，46，29，53，65（D）12，21，40，32，29，46，53，652/7《算法与数据结构》考试一试卷9、设有一组记录的重点字为{19,41,23,38,28,54,84,27}，用链地点法结构哈希表，哈希函数为H(key)=keyMOD13，哈希地点为2的链表中有个记录。（）(A)3（B）4（C）2（D）1三、剖析题（每题6分，共30分）1、设有一棵树，采用双亲表示法的存储结构如右图，请解决以下问题：①画出该树的逻辑结构（2分）0A-1（1分）②给出对该树进行先序遍历的遍历序列1B0③画出将该树变换的二叉树（2分）2C0④给出对变换后的二叉树的后序遍历序列（1分）3D04E15F16G27H28I29J310K411M42、对于下列图中的带权无向图，请解决以下问题：①画出该图的毗邻链表；（2分）②根据您画出的毗邻链表写出其广度优先搜寻生成树（假定从极点3出发）；（2分）③给出按Kruskal算法获得的最小生成树。（2分）175510289344333、将重点字序列（18，22，13，37，4，9，25，15，20）插入到初态为空的二叉排序树中，请画出成立二叉排序树T；然后画出删除13之后的二叉排序树T1；再画出插入13之后的二叉排序树T2。3/7《算法与数据结构》考试一试卷4、线性表的重点字会合{51，25，18，39，42，69，35，33，17，56，47，13，8}，共有13个元素，已知散列函数为：H（k）=kMOD11，采用链地点办理矛盾，请给出对应的散列表结构。5、已知重点字会合{15，29，33，40，17，39，18，21，12，45，52，43，9}，请给出:采用增量序列为5,3,1的希尔排序法，对该序列做非递减排序时的每一趟结果。业专级年四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、设有链行列，其数据结构定义如下。然后进行出队操作，将出队的队首元素的数据通过指针变量x带回。别)typedefstructQnode系{ElemTypedata;structQnode*next;}QNode;typedefstructlink_queue{QNode*front,*rear;(}Link_Queue;:intDelete_LinkQueue(LinkQueue*Q,ElemType*x)号{QNode*p;学if(Q->front==Q->rear)return0;/*队空*/p=Q->front->next;/*取队首结点*/;:Q->front->next=p->next;名if(p==Q->rear);姓free(p);return1;}4/7业专级年别(:号

《算法与数据结构》考试一试卷2、设T是指向二叉树根结点的指针变量,对二叉树进行中序遍历的非递归算法。数据结构定义如下：typedefstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild;}BTNode;#defineMAX_NODE50voidInorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,bool=1;if(T==NULL)printf(“BinaryTreeisEmpty!n”);else{do{while(p!=NULL){;p=p->Lchild;}if(top==0)bool=0;else{p=stack[top];top--;visit(p->data);;}};}}3、图的毗邻链表的结点结构如下列图所示。下面算法是从极点v出发，递归地深度优先搜寻图G。datafirstarcadjvexinfonextarctypedefemnu{FALSE,TRUE}BOOLEAN;#defineMAX_VEX_NUM30/*最大极点数*/BOOLEANVisited[MAX_VEX_NUM];voidDFS(ALGraph*G,intv){LinkNode*p;5/7《算法与数据结构》考试一试卷Visited[v]=TRUE;Visit[v];/*置接见标志，接见极点v*/;while(p!=NULL){if(!Visited[p->adjvex]);;}}4、冒泡排序算法。#defineFALSE0#defineTRUE1VoidBubble_Sort(Sqlist*L){intj,k,flag;for(j=0;j<L->length;j++)/*共有n-1趟排序*/{flag=TRUE;for(k=1;k<=L->length-j;k++)/*一趟排序*/if(){flag=FALSE;L->R[0]=L->R[k];L->R[k]=L->R[k+1];L->R[k+1]=L->R[0];}if()break;}}五、编写算法（共14分）1、用头插入法创立单链表，以输入最大整数32767作为结束，链表的头结点head作为返回值的算法函数。（6分）数据结构定义如下：typedefstructLnode{intdata;/*数据域，保留结点的