《算法與數(shù)據(jù)結(jié)構(gòu)》考試試卷

姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線東莞理工學(xué)院（本科）試卷（A 卷）2009 -2010 學(xué)年第二學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)試卷（A 卷）一、填空題（每小題2分，共18分）1、 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合, ， 和 四種。2、 數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 和 。3、 在順序存儲結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素，其物理位置 ，在單鏈表中，邏輯上相鄰的數(shù)據(jù)元素，其物理位置 。4、 棧是操作受限的線性表，其操作數(shù)據(jù)的基本原則是 ，允許進(jìn)行插入和刪除操作的一端稱為 。5、 設(shè)有一個二維數(shù)組A1010，若每個元素占6個基本存儲單元，A00的地址是1000，若按行優(yōu)先（以行為主）順序存儲，則元素A68的存儲地址是 ；若按列優(yōu)先（以列為主）順序存儲，則元素A68的存儲地址是 。6、 設(shè)有一棵深度為n的完全二叉樹，該二叉樹至少有 個結(jié)點，至多有 個結(jié)點。7、 若采用鄰接矩陣存儲一個圖所需要的存儲單元取決于圖的 ；無向圖的鄰接矩陣一定是 。8、 在進(jìn)行排序時，最基本的操作是 和 。9、 在查找時，若采用折半查找，要求線性表 ，而哈希表的查找，要求線性表 。二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）1、設(shè)有長度為n的數(shù)組a,假設(shè)已經(jīng)賦值，下面程序段的時間復(fù)雜度是（ ）。for (i=0; i<n-1; i+) k=i ;for (j=i+1; j<n; j+)if (ak>aj) k=j ; 授課：XXX if (k!=i) temp=ai; ai=ak ; ak=temp ; （A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、 設(shè)有以head為頭結(jié)點的非空單循環(huán)鏈表，鏈表中只有一個結(jié)點條件是（ ）。（A） head->next=head ； （B） head->next=head->next ；（C） head->next->next=head ； （D） head->next->next=head->next； 3、設(shè)有一個大小為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.front 4、二叉樹是非線性結(jié)構(gòu)，因此（ ）（A） 不能用順序存儲結(jié)構(gòu)存儲 （B） 不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲 （C） 既能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲，也能用順序存儲結(jié)構(gòu)存儲 （D） 既不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲，也不能用順序存儲結(jié)構(gòu)存儲5、設(shè)有一棵二叉樹，其先序遍歷序列是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)條邊的帶權(quán)無向圖，以下關(guān)于該圖的最小生成樹的描述正確的是（ ）。姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線（A） 最小生成樹是唯一的。（B） 最小生成樹中所有邊上的權(quán)值之和是唯一的。（C） 最小生成樹有n條邊。（D） 最小生成樹有n個頂點e-1條邊。8、 設(shè)有關(guān)鍵集合21，12，46，40，32，29，65，53，采用冒泡排序法進(jìn)行一趟排序操作后的結(jié)果授課：XXX是（ ）。（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，659、設(shè)有一組記錄的關(guān)鍵字為19, 41, 23, 38, 28, 54, 84, 27，用鏈地址法構(gòu)造哈希表，哈希函數(shù)為H(key)=key MOD 13，哈希地址為2的鏈表中有 個記錄。（ ）(A) 3 （B） 4 （C） 2 （D） 1三、分析題（每題6分，共30分）1、 設(shè)有一棵樹，采用雙親表示法的存儲結(jié)構(gòu)如右圖，請解決以下問題：01234567891011A -1B 0C 0D 0E 1F 1G 2H 2I 2J 3K 4M 4 畫出該樹的邏輯結(jié)構(gòu) （2分） 給出對該樹進(jìn)行先序遍歷的遍歷序列 （1分） 畫出將該樹轉(zhuǎn)換的二叉樹 （2分） 給出對轉(zhuǎn)換后的二叉樹的后序遍歷序列 （1分）2、 對于下圖中的帶權(quán)無向圖，請解決以下問題： 畫出該圖的鄰接鏈表； （2分） 根據(jù)您畫出的鄰接鏈表寫出其廣度優(yōu)先搜索生成樹（假設(shè)從頂點3出發(fā)）； （2分） 給出按Kruskal算法得到的最小生成樹。 （2分）15243571033498授課：XXX3、 將關(guān)鍵字序列（18，22，13，37，4，9，25，15，20）插入到初態(tài)為空的二叉排序樹中，請畫出建立二叉排序樹T；然后畫出刪除13之后的二叉排序樹T1；再畫出插入13之后的二叉排序樹T2。姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線4、 線性表的關(guān)鍵字集合51，25，18，39，42，69，35，33，17，56，47，13，8，共有13個元素，已知散列函數(shù)為：H（k） = k MOD 11，采用鏈地址處理沖突，請給出對應(yīng)的散列表結(jié)構(gòu)。5、 已知關(guān)鍵字集合15，29，33，40，17，39，18，21，12，45，52，43，9，請給出采用增量序列為5, 3, 1的希爾排序法，對該序列做非遞減排序時的每一趟結(jié)果。四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應(yīng)語句以實現(xiàn)算法功能。每個空白只能填一個語句。1、設(shè)有鏈隊列，其數(shù)據(jù)結(jié)構(gòu)定義如下。然后進(jìn)行出隊操作，將出隊的隊首元素的數(shù)據(jù)通過指針變量x帶回。typedef struct Qnode ElemType data ;struct Qnode *next ;QNode ;typedef struct link_queue QNode *front , *rear ;Link_Queue ;int Delete_LinkQueue(LinkQueue *Q, ElemType *x) QNode *p ;if (Q->front=Q->rear) return 0 ; /* 隊空 */p=Q->front->next ; /* 取隊首結(jié)點 */ ; Q->front->next=p->next ; 授課：XXXif (p=Q->rear) ; free(p) ; return 1 ; 2、設(shè)T是指向二叉樹根結(jié)點的指針變量,對二叉樹進(jìn)行中序遍歷的非遞歸算法。數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild ;BTNode ; #define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線 while (p!=NULL) ; p=p->Lchild ; if (top=0) bool=0 ; else p=stacktop ; top- ; visit( p->data ) ; ; ; 3、 圖的鄰接鏈表的結(jié)點結(jié)構(gòu)如下圖所示。下面算法是從頂點v出發(fā)，遞歸地深度優(yōu)先搜索圖G。adjvex info nextarc表結(jié)點data firstarc頂點結(jié)點typedef emnu FALSE , TRUE BOOLEAN ;授課：XXX#define MAX_VEX_NUM 30 /* 最大頂點數(shù) */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v) LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置訪問標(biāo)志，訪問頂點v */ ; while (p!=NULL) if (!Visitedp->adjvex) ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,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->R0=L->Rk ; L->Rk=L->Rk+1 ; L->Rk+1=L->R0 ; if ( ) break ; 五、編寫算法（共14分）1、用頭插入法創(chuàng)建單鏈表，以輸入最大整數(shù)32767作為結(jié)束，鏈表的頭結(jié)點head作為返回值的算法函數(shù)。 （6分）數(shù)據(jù)結(jié)構(gòu)定義如下：授課：XXXtypedef struct Lnode int data; /*數(shù)據(jù)域，保存結(jié)點的值 */struct Lnode *next; /*指針域*/LNode; /*結(jié)點的類型 */2、設(shè)T是指向二叉樹根結(jié)點的指針變量，用非遞歸方法統(tǒng)計樹中葉子結(jié)點數(shù)和非葉子結(jié)點數(shù)的算法函數(shù)。 （8分）數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild ;BTNode ; （注：可編輯下載，若有不當(dāng)之處，請指正，謝謝!） 授課：XXX