廣東工業(yè)大學(xué)試卷用紙，共6頁(yè)，第4頁(yè)廣東工業(yè)大學(xué)考試試卷(B)課程名稱:廣東工業(yè)大學(xué)考試試卷(B)課程名稱:數(shù)據(jù)結(jié)構(gòu)試卷滿分100分考試時(shí)間:年月日(第周星期)題號(hào)一二三四五總分評(píng)卷得分評(píng)卷簽名復(fù)核得分復(fù)核簽名一．單項(xiàng)選擇題（共16分，每題2分）1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,S)，D={a,b,c,d,e,f}，S={<a,b>,<a,c>,<b,d>,<b,e>,<c,e>,<c,f>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。 [A]線性結(jié)構(gòu) [B]樹(shù)型結(jié)構(gòu) [C]集合結(jié)構(gòu) [D]圖型結(jié)構(gòu)2．假設(shè)以數(shù)組A[60]存放循環(huán)隊(duì)列的元素，如果當(dāng)前的尾指針rear=15，頭指針front＝32，則當(dāng)前循環(huán)隊(duì)列的元素個(gè)數(shù)是（）。[A]43[B]16[C]17[D]423．廣義表A=(a,b,(c,d))，執(zhí)行Head(Head(Tail(Tail(A))))的結(jié)果是（）。[A](c)[B](d)[C]c[D]d4．下列有關(guān)二叉樹(shù)的正確陳述是（）。[A]二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2[B]一棵二叉樹(shù)的度可以小于2[C]二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2[D]二叉樹(shù)的度為25．若將一棵樹(shù)t轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹(shù)h，則t的后根遍歷是h的（）。[A]前序遍歷[B]中序遍歷[C]后序遍歷[D]層次遍歷6．在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（）。[A]G中有弧<Vi，Vj>[B]G中有一條從Vi到Vj的路徑[C]G中沒(méi)有弧<Vi，Vj>[D]G中有一條從Vj到Vi的路徑學(xué)院：專業(yè)：學(xué)號(hào)：姓名：裝訂線7．散列表的地址區(qū)間為0-17，散列函數(shù)為H(K)=Kmod17，采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是（）。[A]8[B]9[C]10[D]118．ISAM文件和VASM文件屬于（）。[A]索引非順序文件[B]順序文件[C]索引順序文件[D]散列文件二．填空題（共12分，每空1分）1．線性表L=（a1,a2,…,an）采用順序存儲(chǔ)表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素需要移動(dòng)元素的平均次數(shù)是___________。2．在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為_(kāi)__________，另一端稱為_(kāi)__________。3．模式串P=’ababc’的next函數(shù)值序列為_(kāi)__________。4．深度為6的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有___________個(gè)。5．線索二叉樹(shù)的左線索指向其___________，右線索指向其___________。6．已知無(wú)向圖G=（V,E），其中V={a,b,c,d,e}，E={(a,b),(a,d),(a,c),(d,c),(b,e)}，若從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為a,b,e,c,d，則采用的是___________遍歷方法。7．動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有___________和___________運(yùn)算，而后者不包含這兩種運(yùn)算。8．簡(jiǎn)單選擇排序的平均時(shí)間復(fù)雜度是___________，堆排序的平均時(shí)間復(fù)雜度是___________。三．解答題（共40分）1．（6分）假設(shè)電文中僅由a到e共5個(gè)字母組成，字母在電文中出現(xiàn)的頻率依次為0.2，0.15，0.32，0.28，0.05請(qǐng)畫(huà)出由此構(gòu)造的哈夫曼樹(shù)（要求樹(shù)中所有結(jié)點(diǎn)的左右孩子必須是左大右?。⒂?jì)算該哈曼夫樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。2．（8分）設(shè)對(duì)稱矩陣A=（1）若將A中包括主對(duì)角線的下三角元素按行的順序壓縮到數(shù)組S中，即S為1030002050下標(biāo)：12345678910請(qǐng)求出A中任一元素的行列下標(biāo)[i,j](1<=i,j<=4)與S中元素的下標(biāo)K之間的關(guān)系；（2）若將A[i,j]（1<=i,j<=4）視為稀疏矩陣，畫(huà)出其三元組表。3．（10分）若帶權(quán)無(wú)向圖G的鄰接矩陣如右圖所示，頂點(diǎn)集是{V1,V2,V3,V4,V5}，（1）畫(huà)出圖G的鄰接表，要求每個(gè)頂點(diǎn)的表結(jié)點(diǎn)序號(hào)都是按照從小到大的次序鏈接；（2）畫(huà)出圖G的最小生成樹(shù)。4．（8分）從空樹(shù)開(kāi)始構(gòu)造一棵平衡二叉排序樹(shù)，依次插入的關(guān)鍵字為（11,13,15,17,19,20），請(qǐng)按下圖要求畫(huà)出該樹(shù)的部分生成過(guò)程。插入11,13,15后插入17后插入19后插入20后5．（8分）對(duì)序列（3,87,12,61,70,97,26,45）執(zhí)行升序排序。試根據(jù)堆排序原理，填寫(xiě)完整下列各步驟結(jié)果。建立大頂堆結(jié)構(gòu)：________________________交換與調(diào)整：（1）87,70,26,61,45,12,3,97；（2）________________________；（3）61,45,26,3,12,70,87,97；（4）45,12,26,3,61,70,87,97；（5）26,12,3,45,61,70,87,97；（6）________________________；（7）3,12,26,45,61,70,87,97；四．算法閱讀題（共24分）1．（6分）閱讀算法f1，并回答問(wèn)題。（1）設(shè)線性表L=(2,3,6,5,4)，并采用帶頭結(jié)點(diǎn)的單鏈表儲(chǔ)存，寫(xiě)出執(zhí)行算法f1(L)后的L；（2）簡(jiǎn)述算法f1(L)對(duì)線性表L的操作意義。voidf1(LinkList&L){LinkListp,s;p=L->next;L->next=NULL;while(p!=NULL){s=p->next;p->next=L->next;L->next=p;p=s;}}2．（6分）假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針rear指向隊(duì)尾元素（注意不設(shè)頭指針），算法f2實(shí)現(xiàn)相應(yīng)的出隊(duì)列操作。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為完整的算法。Statusf2(LinkList&rear,ElemType&x){LinkListfront;if(①)returnERROR;else{front=②;rear->next->next=front->next;if(front==rear)rear=③;x=front->data;free(front);returnOK;}}KHKHFEABGICD設(shè)二叉樹(shù)bt如右圖所示，請(qǐng)寫(xiě)出執(zhí)行intc=0;f3(bt,c);之后c的結(jié)果；簡(jiǎn)述算法f3的功能。voidf3(BiTreebt,int&x){if(bt){if(bt->lchild||bt->rchild)x++;f3(bt->lchild,x);f3(bt->rchild,x);}}4．（6分）圖的鄰接表存儲(chǔ)結(jié)構(gòu)的類型定義如下：typedefstructArcNode{intadjvex;//該弧所指向的頂點(diǎn)的位置ArcNode*nextarc;//指向下一條弧的指針}ArcNode;//定義弧的結(jié)點(diǎn)typedefstruct{VertexTypedata;//頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧}VNode,AdjList[MAX_VERTEX_NUM];//定義頂點(diǎn)數(shù)組typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)intkind;}ALGraph;//鄰接表類型算法f4(G,v)是以頂點(diǎn)v為起點(diǎn)，對(duì)圖進(jìn)行深度優(yōu)先遍歷。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為完整的算法。voidf4(ALGraphG,intv){AcrNode*p;visited[v]=1;visit(v);p=①;while(p){v=p->adjvex;if(!visited[v])②