廣東工業(yè)大學(xué)-數(shù)據(jù)結(jié)構(gòu)試卷

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