算法與數(shù)據(jù)結構考試試卷

《算法與數(shù)據(jù)結構》考試一試卷東莞理工學院（本科）試卷（A卷）2009-2010學年第二學期《算法與數(shù)據(jù)結構》試卷（A卷）一、填空題（每題2分，共18分）:1、對于給定的n個元素,能夠結構出的邏輯結構有會合,，業(yè)專和四種。級年2、數(shù)據(jù)結構中評論算法的兩個重要指標是和。3、在次序存儲結構中，邏輯上相鄰的數(shù)據(jù)元素，其物理地點，在單鏈表中，邏輯上相鄰的數(shù)據(jù)元素，其物理地點。4、棧是操作受限的線性表，其操作數(shù)據(jù)的基來源則是，允許進行插入和刪除操作的一端稱為。:5、設有一個二維數(shù)組A[10][10]，若每個元素占6個基本存儲單元，A[0][0]的地點是別)系1000，若按行優(yōu)先（以行為主）次序存儲，則元素A[6][8]的存儲地點是；若按列優(yōu)先（以列為主）次序存儲，則元素A[6][8]的存儲地點是。6、設有一棵深度為n的完全二叉樹，該二叉樹起碼有個結點，至多有個結點。7、若采用毗鄰矩陣存儲一個圖所需要的存儲單元取決于圖的；無向圖的(毗鄰矩陣一定是。:8、在進行排序時，最基本的操作是和。號9、在查找時，若采用折半查找，要求線性表，而哈希表的查找，要求學線性表。二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共1、設有長度為n的數(shù)組a,假定已經(jīng)賦值，下面程序段的時間復雜度是（: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

分））。業(yè)專級年

《算法與數(shù)據(jù)結構》考試一試卷}（A）O(n)（B）O(n2)（C）O(㏒2n)（D）O(n㏒2n)2、設有以head為頭結點的非空單循環(huán)鏈表，鏈表中只有一個結點條件是（）。（A）head->next=head；（B）head->next=head->next；（C）head->next->next=head；（D）head->next->next=head->next；3、設有一個大小為Max的循環(huán)行列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《算法與數(shù)據(jù)結構》考試一試卷9、設有一組記錄的重點字為{19,41,23,38,28,54,84,27}，用鏈地點法結構哈希表，哈希函數(shù)為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分）②根據(jù)您畫出的毗鄰鏈表寫出其廣度優(yōu)先搜尋生成樹（假定從極點3出發(fā)）；（2分）③給出按Kruskal算法獲得的最小生成樹。（2分）175510289344333、將重點字序列（18，22，13，37，4，9，25，15，20）插入到初態(tài)為空的二叉排序樹中，請畫出成立二叉排序樹T；然后畫出刪除13之后的二叉排序樹T1；再畫出插入13之后的二叉排序樹T2。3/7《算法與數(shù)據(jù)結構》考試一試卷4、線性表的重點字會合{51，25，18，39，42，69，35，33，17，56，47，13，8}，共有13個元素，已知散列函數(shù)為：H（k）=kMOD11，采用鏈地點辦理矛盾，請給出對應的散列表結構。5、已知重點字會合{15，29，33，40，17，39，18，21，12，45，52，43，9}，請給出:采用增量序列為5,3,1的希爾排序法，對該序列做非遞減排序時的每一趟結果。業(yè)專級年四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應語句以實現(xiàn)算法功能。每個空白只能填一個語句。1、設有鏈行列，其數(shù)據(jù)結構定義如下。然后進行出隊操作，將出隊的隊首元素的數(shù)據(jù)通過指針變量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業(yè)專級年別(:號

《算法與數(shù)據(jù)結構》考試一試卷2、設T是指向二叉樹根結點的指針變量,對二叉樹進行中序遍歷的非遞歸算法。數(shù)據(jù)結構定義如下：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出發(fā)，遞歸地深度優(yōu)先搜尋圖G。datafirstarcadjvexinfonextarctypedefemnu{FALSE,TRUE}BOOLEAN;#defineMAX_VEX_NUM30/*最大極點數(shù)*/BOOLEANVisited[MAX_VEX_NUM];voidDFS(ALGraph*G,intv){LinkNode*p;5/7《算法與數(shù)據(jù)結構》考試一試卷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、用頭插入法創(chuàng)立單鏈表，以輸入最大整數(shù)32767作為結束，鏈表的頭結點head作為返回值的算法函數(shù)。（6分）數(shù)據(jù)結構定義如下：typedefstructLnode{intdata;/*數(shù)據(jù)域，保留結點的