華工數(shù)據(jù)結(jié)構(gòu)A卷

《數(shù)據(jù)結(jié)構(gòu)》試卷第1頁共7頁姓名姓名學(xué)號學(xué)院專業(yè)座位號(密封線內(nèi)不答題)……………………密………………封………線……線………_____________________…《數(shù)據(jù)結(jié)構(gòu)》試卷選擇題（從下列答案選項(xiàng)中選出一個(gè)正確答案，每小題2分，共22分)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。邏輯存儲邏輯和存儲物理若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用（ ）存儲方式節(jié)省時(shí)間。單鏈表雙鏈表順序表單循環(huán)鏈表已知模式串t=“abcaabbcabcaabdab”，該模式串的next數(shù)組值為（ ）。-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1-1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ琣11為第一個(gè)元素，其存儲地址為1，每個(gè)元素占1個(gè)地址空間，則a85的地址為（ ）。13331840一棵含有101個(gè)結(jié)點(diǎn)的完全二叉樹存儲在數(shù)組bt[102]中，其中bt[0]不用，若bt[k]是葉子結(jié)點(diǎn)，則k的最小值是（ ）。51504948稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。二維數(shù)組和三維數(shù)組三元組表和散列表三元組表和十字鏈表散列表和十字鏈表對順序存儲的18個(gè)數(shù)據(jù)元素（A[1]~A[18]）的有序表做二分查找，則查找A[3]的比較序列的下標(biāo)為( )。1，2，39，5，2，39，5，39，4，2，3用鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中的結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)，這種說法（ ）。正確錯(cuò)誤下列排序算法中，某一趟排序結(jié)束后未必能選出一個(gè)元素放在最終位置上的是（ ）。堆排序冒泡排序直接插入排序快速排序在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最小不平衡子樹之根為A,并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則應(yīng)作（ ）型調(diào)整使其平衡。LLLRRLRR在解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)依此從該緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)是一個(gè)（ ）結(jié)構(gòu)。堆棧隊(duì)列順序表鏈表填空題（每空2分，共18分）以下程序段的時(shí)間復(fù)雜度是________________________，其中n為正整數(shù)。inti=1;while(i<=n)i=i*2;對順序存儲結(jié)構(gòu)的線性表，設(shè)表長為n；在等概率假設(shè)條件下，插入一個(gè)數(shù)據(jù)元素需平均移動表中元素______________個(gè)；在最壞情況下需移動表中元素______________個(gè)。設(shè)樹T的度為4，其中度為1、2、3、4的結(jié)點(diǎn)的個(gè)數(shù)分別為4、3、2、1，則樹T的葉子結(jié)點(diǎn)的個(gè)數(shù)是。判定一個(gè)環(huán)形隊(duì)列qu（最多元素為MaxSize）為空的條件是__________________________________________，判定環(huán)形隊(duì)列qu為滿隊(duì)列的條件是__________________________________________。設(shè)森林T中有4棵樹，結(jié)點(diǎn)個(gè)數(shù)依次為n1,n2,n3,n4，當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點(diǎn)的右子樹上有________________________個(gè)結(jié)點(diǎn)。設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a，b，c，d，e，f依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q。若這6個(gè)元素出隊(duì)列的順序?yàn)閎，d，c，f，e，a，則棧S的容量至少應(yīng)該是________________。用head和tail函數(shù)，取出廣義表L=((x,y,z),(a,b,c,d))中元素b的運(yùn)算是_____________________________________________________________________。解答下列問題（共30分）（本題6分）已知一顆二叉樹的中序遍歷序列為DCEFBHGAKJLIM,后序遍歷序列為DFECHGBKLJMIA，問：能不能唯一確定一顆二叉樹？若能，畫出該二叉樹。（本題8分）設(shè)有一組關(guān)鍵字序列：（29，18，25，47，58，12，51，10）要按照關(guān)鍵字值遞增的次序進(jìn)行排序。若采用初始增量為4的希爾排序，寫出第一趟排序的結(jié)果：若采用以第一個(gè)元素為基準(zhǔn)元素的快速排序法，寫出第一趟排序的結(jié)果：若采用二路歸并排序，寫出第一趟排序的結(jié)果:（本題8分）以下面給出的數(shù)據(jù)序列作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼樹，并計(jì)算其帶權(quán)路徑長度WPL。{4，5，6，7，10，12，15，18，23}（本題8分）設(shè)有一組關(guān)鍵字（100，20，21，35，3，78，99，45），采用哈希函數(shù)H(K)=K%7，采用開放地址的線性探查法處理沖突，試在０至8的哈希地址空間中，對該關(guān)鍵字序列構(gòu)造哈希表，并求出在等概率情況下查找成功的平均查找長度ASL。算法填空（每空2分，共14分）下面是一個(gè)二叉樹中序遍歷的非遞歸算法，請?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。voidInorder(BTNode*b)//二叉樹中序遍歷非遞歸算法{BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL) {p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; ； } if(top>-1) { p=St[top]; top--; printf(“%c”,p->data); ； } } printf(“\n”); } }設(shè)二叉排序樹采用二叉鏈表存儲，以下遞歸算法從大到小輸出二叉排序樹結(jié)點(diǎn)值（data），請將算法補(bǔ)充完整。InOrderBST(BTNode*b)//二叉排序樹從大到小輸出{if(b!=NULL) {InOrderBST(); printf(“%c”,); InOrderBST(); }}下面是一個(gè)堆排序算法，請?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。其中sift為篩選算法，原型為：voidsift(RecTypeR[],intlow,inthigh);voidHeapSort(RecTypeR[],intn)//堆排序算法{ inti; RecTypetemp; for(i=;i>=1;i--)//循環(huán)建立初始堆 sift（R,i,n） for(i=n;i>=2;i--) { temp=R[1]; R[1]=R[i]; R[i]=temp; sift（）;//重建堆 }}算法設(shè)計(jì)題(本題10分)設(shè)計(jì)一個(gè)算法Reverse，利用環(huán)形隊(duì)列和順序棧的基本運(yùn)算將指定隊(duì)列中的內(nèi)容逆置。（本題6分）設(shè)計(jì)一個(gè)算法MatToList，將無向圖的鄰接矩陣g轉(zhuǎn)換為鄰接表G，相關(guān)類型定義如下：//鄰接矩陣相關(guān)定義#defineMAXV<最大頂點(diǎn)個(gè)數(shù)〉typedefstruct{ intno; InfoTypeinfo;}VertexType;typedefstruct{ intedges[MAXV][MAXV]; intn,e; VertexTypevexs[MAXV];}MGraph;//鄰接表相關(guān)定義typedefstructAnode{ intadjvex; struct