數(shù)據(jù)結(jié)構(gòu)作業(yè)(3)及數(shù)據(jù)結(jié)構(gòu)試題及答案

檢索的作業(yè)9.6假定值A(chǔ)到H存儲(chǔ)在一個(gè)自組織線性表中，開(kāi)始按照升序存放。對(duì)于9.2小節(jié)建議的三種自組織啟發(fā)式規(guī)則，按照下面順序訪問(wèn)線性表，給出結(jié)果線性表和需要的比較總數(shù)。DHHGHEGHGHECEHG頻率計(jì)數(shù)自組織線性表啟發(fā)式規(guī)則：ABCDEFGH比較次數(shù)D:DABCEFGH4H:DHABCEFG8H:HDABCEFG2G:HDGABCEF8H:HDGABCEF1E：HDGEABCF7G:HGDEABCF3H:HGDEABCF1G:HGDEABCF2H:HGDEABCF1E:HGEDABCF4C:HGEDCABF7E:HGEDCABF3H:HGEDCABF1G:HGEDCABF2比較總數(shù)=54(2)移至前端自組織線性表啟發(fā)式規(guī)則：ABCDEFGH比較次數(shù)D:DABCEFGH4H:HDABCEFG8H:HDABCEFG1G:GHDABCEF8H:HGDABCEF2E：EHGDABCF7G:GEHDABCF3H:HGEDABCF3G:GHEDABCF2H:HGEDABCF2E:EHGDABCF3C:CEHGDABF7E:ECHGDABF2H:HECGDABF3G:GHECDABF4比較總數(shù)=59(3)轉(zhuǎn)置自組織線性表啟發(fā)式規(guī)則：ABCDEFGH比較次數(shù)D:ABDCEFGH4H:ABDCEFHG8H:ABDCEHFG7G:ABDCEHGF8H:ABDCHEGF6E：ABDCEHGF6G:ABDCEGHF7H:ABDCEHGF7G:ABDCEGHF7H:ABDCEHGF7E:ABDECHGF5C:ABDCEHGF5E:ABDECHGF5H:ABDEHCGF6G:ABDEHGCF7比較總數(shù)=959.8編寫(xiě)一個(gè)算法，實(shí)現(xiàn)頻率計(jì)數(shù)自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實(shí)現(xiàn)。特別是編寫(xiě)一個(gè)函數(shù)FreqCount，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線性表的最后，其頻率計(jì)數(shù)是1。算法思想：按順序訪問(wèn)記錄，每訪問(wèn)一條記錄，該記錄的訪問(wèn)數(shù)加1，如果該記錄的訪問(wèn)數(shù)已經(jīng)大于它前面記錄的訪問(wèn)數(shù)，這條記錄就在線性表中與前面的記錄交換。偽代碼：template<classElem>voidFreqCount(ElemA[],intcount[]){intn=0;while((intval=GETNEXT())!=DONE){for(i=0;i<n;i++)if(A[i]==val)break;elseif(i==n){A[n]=val;count[n++]=1;}else{count[i]++;while((i>0)&&(count[i]>count[i-1])){swap(A[i],A[i-1]);swap(count[i],count[i-1]);}}}}9.9編寫(xiě)一個(gè)算法，實(shí)現(xiàn)移至前端自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實(shí)現(xiàn)。特別是編寫(xiě)一個(gè)函數(shù)MoveToFront，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線性表的開(kāi)始位置。算法思想：按順序訪問(wèn)記錄，每找到一個(gè)記錄就把它放到線性表的最前面，而把其他記錄后退一個(gè)位置。偽代碼：template<classElem>voidMoveToFront(ElemA[]){intn=0;while((intval=GETNEXT())!=DONE){for(i=0;i<n;i++)if(A[i]==val)break;if(i==n)A[n]=val;while(i>0)swap(A[i],A[0]);}}9.10編寫(xiě)一個(gè)算法，實(shí)現(xiàn)轉(zhuǎn)置自組織線性表啟發(fā)式規(guī)則，假定線性表使用數(shù)組實(shí)現(xiàn)。特別是編寫(xiě)一個(gè)函數(shù)transpose，它把要檢索的值作為輸入，并且相應(yīng)地調(diào)整線性表。如果值不在線性表中，就把它添加到線性表的最后。算法思想：按順序訪問(wèn)記錄，把找到的記錄與它在線性表中的前一條記錄交換位置。偽代碼：template<classElem>voidtanspose(ElemA[]){intn=0;while((intval=GETNEXT())!=DONE){for(i=0;i<n;i++)if(A[i]==val)break;if(i==n)A[n]=val;While(i!=0)swap(A[i],A[i-1]);}}*設(shè)散列函數(shù)為h(K)=Kmod7,閉散列表的地址空間為0,…,6,開(kāi)始時(shí)散列表為空,用線性探查法解決沖突,請(qǐng)畫(huà)出依次插入鍵值23,14,9,6,30,12,18后的散列表。h(23)=2h(14)=0h(9)=2h(6)=6h(30)=2h(12)=5h(18)=401411822339430512669.16使用閉散列，利用雙散列方法解決沖突，把下面的關(guān)鍵碼插入到一個(gè)有13個(gè)槽的散列表中（槽從0到12編號(hào)）。使用的散列函數(shù)H1和H2在下面定義。給出插入8個(gè)關(guān)鍵碼值后的散列表。一定要說(shuō)明如何使用H1和H2進(jìn)行散列。函數(shù)Rev(k)顛倒10進(jìn)制數(shù)k各個(gè)位的數(shù)字，例如，Rev(37)=73，Rev(7)=7。H1(k)=kmod13。H2(k)=(Rev(k+1)mod11)。關(guān)鍵碼：2,8,31,20,19,18,53,27H1(2)=2H2(2)=3放在位置2H1(8)=8H2(8)=9放在位置8H1(31)=5H2(31)=1放在位置5H1(20)=7H2(20)=1放在位置7H1(19)=6H2(19)=2放在位置6H1(18)=5H2(18)=3放在位置5，但位置5已經(jīng)有數(shù)據(jù)，5+3=8，位置8也有數(shù)據(jù)8+3=11，放在位置11H1(53)=1H2(53)=1放在位置53H1(27)=1H2(27)=5放在位置1，但位置1已經(jīng)有數(shù)據(jù)，1+5=6，位置6也有數(shù)據(jù)，6+5=11，位置11也有數(shù)據(jù)，11+5=3，放在位置3015322327453161972088910111812圖的作業(yè)11.3(a)畫(huà)出圖11.26所示圖的相鄰矩陣表示。1234561020210351234561020210353152051110151132103123456(b)畫(huà)出這個(gè)圖的鄰接表表示。1->2(10)->4(20)->6(2)->\2->1(10)->3(3)->4(5)->\3->2(3)->5(15)->\4->1(20)->2(5)->5(11)->6(10)->\5->3(15)->4(11)->6(3)->\6->1(2)->4(10)->5(3)->\11.4對(duì)于圖11.26所示的圖，給出從頂點(diǎn)1開(kāi)始DFS樹(shù)。12345612345611.5對(duì)于圖11.26所示的圖，給出從頂點(diǎn)1開(kāi)始BFS樹(shù)12345612345611.8對(duì)于圖11.26中的圖，給出從頂點(diǎn)4出發(fā)，使用Dijkstra最短路徑算法產(chǎn)生的最短路徑表。請(qǐng)像圖11.18所示那樣，每處理一個(gè)頂點(diǎn)時(shí)給出相應(yīng)D值。123456初始∞∞∞0∞∞處理4205∞01110處理2155801110處理3155801110處理5155801110處理6155801110處理1155801110頂點(diǎn)4到頂點(diǎn)1的最短路徑為15；頂點(diǎn)4到頂點(diǎn)2的最短路徑為5；頂點(diǎn)4到頂點(diǎn)3的最短路徑為8；頂點(diǎn)4到頂點(diǎn)4的最短路徑為0；頂點(diǎn)4到頂點(diǎn)5的最短路徑為11；頂點(diǎn)4到頂點(diǎn)6的最短路徑為10。11.12編寫(xiě)一個(gè)算法確定一個(gè)有|V|個(gè)頂點(diǎn)的有向圖是否包含回路。算法的時(shí)間代價(jià)應(yīng)該是Θ（|V|+|E|）。算法思想：用廣度優(yōu)先拓?fù)渑判虻姆椒?，首先訪問(wèn)所有的邊，計(jì)算指向每個(gè)頂點(diǎn)的邊數(shù)，將所有沒(méi)有先決條件的頂點(diǎn)放入隊(duì)列，然后開(kāi)始處理隊(duì)列，當(dāng)從隊(duì)列中刪除一個(gè)頂點(diǎn)時(shí)，把它打印出來(lái)，同時(shí)將其所有相鄰頂點(diǎn)的先決條件計(jì)數(shù)減1，當(dāng)某個(gè)相鄰頂點(diǎn)的計(jì)數(shù)為0時(shí)，就將其放入隊(duì)列，如果還有頂點(diǎn)未被打印，而隊(duì)列已經(jīng)為空，則圖中包含回路。偽代碼：voidtopsort(Graph*G,Queue){intCount[G->n()];intv,w;for(v=0;v<G->n();v++)Count[v]=0;for(v=0;v<G->n();v++)for(w=G->first(v);w<G->n;w=G->next(v,w))Count[w]++;for(v=0;v<G->n();v++)if(Count[v]==0;)Q->enqueue(v);while(Q->length()!=0){Q->dequeue(v);printout(v);for(w=G->first(v);w<G->n();w=G->next(v,w)){Count[w]--;if(Count[w]==0)Q->enqueue(w);}}}11.13編寫(xiě)一個(gè)算法確定一個(gè)有|V|個(gè)頂點(diǎn)的無(wú)向圖是否包含回路。算法的時(shí)間代價(jià)應(yīng)該是Θ（|V|）。算法思想：用深度優(yōu)先搜索的方法，如果遇到已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)，則說(shuō)明該無(wú)向圖包含回路。偽代碼：voidDFS(intmap[][],inta,intdep){{if(dep>1&&a==v){Printout("有環(huán)路");return;}for(i=0;i<N;i++){if(map[a][i]==1)DFS(map,i,dep++);}}voidmain(){DFS(map,v,1);}11.15對(duì)于圖11.26所示的圖，給出使用Floyd的每對(duì)頂點(diǎn)間最短路徑算法的結(jié)果。0-path123456010∞20∞210035∞∞123456010∞20∞210035∞∞∞30∞15∞205∞01110∞∞1511032∞∞10301234561-path123456010∞20∞210035∞12123456010∞20∞210035∞12∞30∞15∞205∞01110∞∞151103212∞10301234562-path1234560101315∞210035∞121234560101315∞210035∞12133081515155801110∞∞1511032121510301234563-path1234560101315282100351812123456010131528210035181213308151515580111028181511032121510301234564-path1234560101315262100351612123456010131526210035161213308151515580111026161511032121510301234565123456-path1234560101315262100351612010131526210035161213308151515580111026161511032121510301234561234566-path12345601013125210035161201013125210035161213308151512580111051615110321215103012345611.18對(duì)于圖11.26中的圖，給出從頂點(diǎn)3開(kāi)始使用Prim的MST算法時(shí)各個(gè)邊的訪問(wèn)順序，并給出最終的MST。各個(gè)邊的訪問(wèn)順序：（3,2）（2,4）（2,1）（1,6）（6,5）最終MST：2424 1356135611.19對(duì)于圖11.26中的圖，給出使用Kauskal的MST算法時(shí)各個(gè)邊的訪問(wèn)順序，每當(dāng)把一條邊添加到MST時(shí)，等價(jià)類(lèi)數(shù)組的結(jié)果是什么（如圖6.7那樣顯示數(shù)組內(nèi)容）？135642135642初始狀態(tài)135642135642處理邊（1,6）1465214652處理邊（2,3）3264132641處理邊（5,6）314625314625處理邊（2,4）35354242處理邊（1,2） 13561356等價(jià)類(lèi)數(shù)組結(jié)果：123456初始狀態(tài)-1-1-1-1-1-1處理邊(1，6)-1-1-1-1-11處理邊(2，3)-1-12-1-11處理邊(5，6)-1-12-111處理邊(2，4)-112-111處理邊(1，2)-112111數(shù)據(jù)結(jié)構(gòu)試卷（十一）

一、選擇題(30分)1．設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。 (A)2n (B)n (C)n/2 (D)n(n-1)2．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（）條邊。 (A)n (B)n-1 (C)2n (D)2n-13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。 (A)40，42，60，55，80，85 (B)42，45，55，60，85，80 (C)42，40，55，60，80，85 (D)42，40，60，85，55，804．（）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。 (A)先序遍歷 (B)中序遍歷 (C)后序遍歷 (D)層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。 (A)2i+1 (B)2i (C)i/2 (D)2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為（）。 (A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(n3/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0 (B)head->next==0 (C)head->next==head (D)head!=08．設(shè)某棵二叉樹(shù)的高度為10，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有（）。 (A)20 (B)256 (C)512 (D)10249．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。 (A)1 (B)2 (C)3 (D)410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。 (A)top=top+1; (B)top=top-1; (C)top->next=top; (D)top=top->next;

二、判斷題(20分)1．不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（）2．當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（）3．設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（）4．完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（）5．哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。（）6．對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問(wèn)到該圖中的所有頂點(diǎn)。（）7．先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。（）8．由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。（）9．線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（）10.帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。（）

三、填空題(30分)1.

設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_(kāi)________=p；s->right=p->right；__________=s；p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。2.

設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有________條無(wú)向邊。3.

設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個(gè)元素開(kāi)始進(jìn)行篩選。4.

解決散列表沖突的兩種方法是________________和__________________。5.

設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個(gè)。6.

高度為h的完全二叉樹(shù)中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。7.

設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。8.

設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是__________________________________。9.

設(shè)一棵二叉樹(shù)的前序序列為ABC，則有______________種不同的二叉樹(shù)可以得到這種序列。10.

下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(i<j){while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(____________________)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}_________________;}

四、算法設(shè)計(jì)題(20分)1.

設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。2.

設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。3.

設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。

數(shù)據(jù)結(jié)構(gòu)試卷（十一）

一、選擇題1．B 2．B 3．C 4．B 5．B6．A 7．C 8．C 9．B 10．D

二、判斷題1．對(duì) 2．對(duì) 3．對(duì) 4．對(duì) 5．對(duì)6．對(duì) 7．對(duì) 8．錯(cuò) 9．錯(cuò) 10．錯(cuò)

三、填空題1.

s->left=p，p->right2.

n(n-1)，n(n-1)/23.

n/24.

開(kāi)放定址法，鏈地址法5.

146.

2h-1，2h-17.

(12，24，35，27，18，26)8.

(12，18，24，27，35，26)9.

510.

i<j&&r[i].key<x.key，r[i]=x

四、算法設(shè)計(jì)題1.

設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}2.

設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0';}}3.

設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}數(shù)據(jù)結(jié)構(gòu)試卷（十二）

一、選擇題(30分)1.

字符串的長(zhǎng)度是指（）。 (A)串中不同字符的個(gè)數(shù) (B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù) (D)串中不同數(shù)字的個(gè)數(shù)2.

建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（） (A)O(n) (B)O(1) (C)O(n2) (D)O(log2n)3.

兩個(gè)字符串相等的充要條件是（）。 (A)兩個(gè)字符串的長(zhǎng)度相等 (B)兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等 (C)同時(shí)具備(A)和(B)兩個(gè)條件 (D)以上答案都不對(duì)4.

設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。 (A)99 (B)97 (C)91 (D)935.

在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（）。 (A)O(n) (B)O(1og2n) (C)O(nlog2n) (D)O(n2)6.

設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。 (A)A[1]，A[2]，A[3]，A[4] (B)A[1]，A[14]，A[7]，A[4] (C)A[7]，A[3]，A[5]，A[4] (D)A[7]，A[5]，A[3]，A[4]7.

設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為（）。 (A)8 (B)7 (C)6 (D)58.

設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。 (A)5 (B)6 (C)7 (D)89.

設(shè)無(wú)向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。 (A)aedfcb (B)acfebd (C)aebcfd (D)aedfbc10.

隊(duì)列是一種（）的線性表。 (A)先進(jìn)先出 (B)先進(jìn)后出 (C)只能插入 (D)只能刪除

二、判斷題(20分)1.

如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱(chēng)這兩個(gè)關(guān)鍵字為同義詞。（）2.

設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（）3.

分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（）4.

二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（）5.

向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。（）6.

如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（）7.

非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）8.

不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（）9.

圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。（）10.

稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。（）

三、填空題(30分)1．

設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_(kāi)____________________________。2．

下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk){if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;}elseif(t->data>k)bstinsert(t->lchild,k);else__________________________;}3．

設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next;_________________;。4．

設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。5．

設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_(kāi)_________。6．

完全二叉樹(shù)中第5層上最少有__________個(gè)結(jié)點(diǎn)，最多有_________個(gè)結(jié)點(diǎn)。7．

設(shè)有向圖中不存在有向邊<Vi,Vj>，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。8．

設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_(kāi)____________________________。9．

設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有___________條邊。10．

設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。

四、算法設(shè)計(jì)題(20分)1.

設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。2.

設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。

數(shù)據(jù)結(jié)構(gòu)試卷（12）參考答案

一、選擇題1．C 2．C 3．C 4．B 5．B6．C 7．B 8．C 9．A 10．A

二、判斷題1．對(duì) 2．錯(cuò) 3．對(duì) 4．錯(cuò) 5．錯(cuò)6．對(duì) 7．對(duì) 8．對(duì) 9．對(duì) 10．對(duì)

三、填空題1.

(49，13，27，50，76，38，65，97)2.

t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.

p->next=s4.

head->rlink，p->llink5.

CABD6.

1，167.

08.

(13，27，38，50，76，49，65，97)9.

n-110.

50

四、算法設(shè)計(jì)題1.

設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}2.

設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結(jié)構(gòu)試卷（13）

一、選擇題(30分)1．下列程序段的時(shí)間復(fù)雜度為（）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A)O(m*n*t) (B)O(m+n+t) (C)O(m+n*t) (D)O(m*t+n)2．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（）個(gè)元素。 (A)n-i (B)n+l-i (C)n-1-i (D)i3．設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為（）。 (A)N1-1 (B)N2-1 (C)N2+N3 (D)N1+N34．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(1og2n)5．設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（）。 (A)p->right=s；s->left=p；p->right->left=s；s->right=p->right； (B)s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C)p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；6．下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（）。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)冒泡排序7．設(shè)輸入序列1、2、3、…、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（）。 (A)n-i (B)n-1-i (C)n+l-i (D)不能確定8．設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。 (A)小于等于m的最大奇數(shù) (B)小于等于m的最大素?cái)?shù) (C)小于等于m的最大偶數(shù) (D)小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（）個(gè)。 (A)4 (B)5 (C)6 (D)710.設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/211.設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（）。 (A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/212.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（）次比較。 (A)1 (B)2 (C)3 (D)413.設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（）。 (A)6 (B)11 (C)5 (D)6.514.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ǎ?(A)1，2，3，4 (B)2，3，4，1 (C)1，4，2，3 (D)1，2，4，315.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（）。 (A)4 (B)5 (C)6 (D)7二、填空題(30分)1．

設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1)s->next=___________；2)p->next=s；3)t=p->data；4)p->data=___________；5)s->data=t；2．

設(shè)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結(jié)點(diǎn)。3．

設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)_______隊(duì)列元素。4．

對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_(kāi)_________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才可以完成。5．

在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮應(yīng)最好選擇_________排序，如果從節(jié)省存儲(chǔ)空間的角度來(lái)考慮則最好選擇________排序。6．

設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹(shù)的平均查找長(zhǎng)度是_______________________________。7．

設(shè)一棵二叉樹(shù)的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹(shù)的前序序列為_(kāi)___________________。8．

設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為_(kāi)_______________。9．

設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_(kāi)______________________。10．

設(shè)無(wú)向圖G（如右圖所示），則其最小生成樹(shù)上所有邊的權(quán)值之和為_(kāi)________________。

三、判斷題(20分)1．

有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。()2．

對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。()3．

子串“ABC”在主串“AABCABCD”中的位置為2。()4．

若一個(gè)葉子結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。()5．

希爾排序算法的時(shí)間復(fù)雜度為O(n2)。()6．

用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無(wú)關(guān)而與圖中邊數(shù)有關(guān)。()7．

中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。()8．

入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。()9．

順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。（）10．堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。（）

五、算法設(shè)計(jì)題(20分)1．

設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。2．

設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。3．

設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。

數(shù)據(jù)結(jié)構(gòu)試卷（13）參考答案

一、選擇題1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A

二、填空題1.

p->next，s->data2.

503.

m-14.

6，85.

快速，堆6.

19/77.

CBDA8.

69.

(24，65，33，80，70，56，48)10.

8

三、判斷題1．錯(cuò) 2．對(duì) 3．對(duì) 4．對(duì) 5．錯(cuò)6．錯(cuò) 7．對(duì) 8．對(duì) 9．錯(cuò) 10．對(duì)四、算法設(shè)計(jì)題1．

設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }2．

設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]%2==0)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]%2==1)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}3．

設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head){if(head==0||head->next==0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}數(shù)據(jù)結(jié)構(gòu)試卷（十四）

一、選擇題(24分)1．下列程序段的時(shí)間復(fù)雜度為（）。i=0，s=0；while(s<n){s=s+i；i++；} (A)O(n1/2) (B)O(n1/3) (C)O(n) (D)O(n2)2．設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 (A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（）。(A)s->next=p->next；p->next=-s； (B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p； (D)p->next=s；s->next=q；4．設(shè)輸入序列為1、2、3、4、5、6，則通過(guò)棧的作用后可以得到的輸出序列為（）。(A)5，3，4，6，1，2 (B)3，2，5，6，4，1(C)3，1，2，5，4，6 (D)1，5，4，6，2，35．設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為（）。 (A)10 (B)19 (C)28 (D)556．設(shè)一棵m叉樹(shù)中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹(shù)中共有（）個(gè)葉子結(jié)點(diǎn)。 (A) (B) (C) (D)7.二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。 (A)< (B)> (C)= (D)!=8.設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為（）。 (A)129 (B)219 (C)189 (D)2299.設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（）次線性探測(cè)。 (A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/210.設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（）個(gè)結(jié)點(diǎn)。 (A)2n (B)n+l (C)2n-1 (D)2n+l11.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過(guò)（）趟插入排序可以得到有序序列。 (A)6 (B)7 (C)8 (D)912.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y

二、填空題(48分，其中最后兩小題各6分)1.

設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。2.

快速排序算法的平均時(shí)間復(fù)雜度為_(kāi)___________，直接插入排序算法的平均時(shí)間復(fù)雜度為_(kāi)__________。3.

設(shè)二叉排序樹(shù)的高度為h，則在該樹(shù)中查找關(guān)鍵字key最多需要比較_________次。4.

設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_________個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。5.

設(shè)一棵m叉樹(shù)脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有_________個(gè)空指針域。6.

設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語(yǔ)句序列為：q=p->next；p->data=q->data；p->next=___________；feee(q)；7.

數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類(lèi)型：___________、__________和___________。8.

設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_(kāi)________；用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_(kāi)________。9.

設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k%7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是________。10.

設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_(kāi)____________________。11.

設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_(kāi)_____________________。12.

設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，則該圖的一個(gè)拓?fù)湫蛄袨開(kāi)________________________。13.

下面程序段的功能是建立二叉樹(shù)的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*lchild;________________;}bitree;voidcreatebitree(bitree*&bt){scanf(“%c”,&ch);if(ch=='#')___________;else{bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;________;createbitree(bt->rchild);}}14.

下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*next;}lklist;voidlklistcreate(_____________*&head){for(i=1;i<=n;i++){p=(lklist*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else{q->next=p;____________;}}}

三、算法設(shè)計(jì)題(22分)1．

設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。2．

設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。3．

設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。

數(shù)據(jù)結(jié)構(gòu)試卷（14）參考答案

一、選擇題1．A 2．D 3．B 4．B 5．B 6．D7．A 8．D 9．D 10．C 11．B 12．D

二、填空題1.

4，102.

O(nlog2n)，O(n2)3.

n4.

1，25.

n(m-1)+16.

q->next7.

線性結(jié)構(gòu)，樹(shù)型結(jié)構(gòu)，圖型結(jié)構(gòu)8.

O(n2)，O(n+e)9.

8/310.

(38，13，27，10，65，76，97)11.

(10，13，27，76，65，97，38)12.

12465313.

structnode*rchild，bt=0，createbitree(bt->lchild)14.

lklist，q=p

三、算法設(shè)計(jì)題1.

設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}2.

設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}3.

設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-1];while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}r[j-1]=temp;}數(shù)據(jù)結(jié)構(gòu)（十五）一、

單選題（每題2分，共20分）1.

對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B）方面的內(nèi)容。A．健壯性和可讀性B．并行性C．正確性D．時(shí)空復(fù)雜度2.

在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.

對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4.

一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是(C)A.231 B.321C.312 D.1235.

AOV網(wǎng)是一種（）。A．有向圖B．無(wú)向圖C．無(wú)向無(wú)環(huán)圖D．有向無(wú)環(huán)圖6.

采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（）。A．低于鏈接法處理沖突B.高于鏈接法處理沖突C．與鏈接法處理沖突相同D．高于二分查找7.

若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（）參數(shù)。A．值B．函數(shù)C．指針D．引用8.

在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A．行號(hào)B．列號(hào)C．元素值D．非零元素個(gè)數(shù)9.

快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)10.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)

二、

運(yùn)算題（每題6分，共24分）1.

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為_(kāi)____________________。2.

隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3.

當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。4.

對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)________，在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)___________。5.

設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到3，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_(dá)____＿個(gè)字節(jié)。W中第6行的元素和第4列的元素共占用＿_(dá)______＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿_(dá)_______＿。6.

廣義表A=(a,(a,b),((a,b),c)),則它的深度為_(kāi)___________，它的長(zhǎng)度為_(kāi)___________。7.

二叉樹(shù)是指度為2的____________________樹(shù)。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是_____________。8.

對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。9.

對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_(kāi)____________個(gè)，其中_______________個(gè)用于指向孩子，_________________個(gè)指針是空閑的。10.

若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類(lèi)推，則A[i]元素的左孩子元素為_(kāi)_______,右孩子元素為_(kāi)______________，雙親元素為_(kāi)___________。11.

在線性表的散列存儲(chǔ)中，處理沖突的常用方法有________________________和_____________________________兩種。12.

當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用________________________排序。

三、

運(yùn)算題（每題6分，共24分）1.

已知一個(gè)6′5稀疏矩陣如下所示，

試：（1）

寫(xiě)出它的三元組線性表；（2）

給出三元組線性表的順序存儲(chǔ)表示。2.

設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3.

對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出：(1)從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2)從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)；4.

已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：圖圖6E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。

四、

閱讀算法（每題7分，共14分）1.

intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)

指出該算法的功能；(2)

該算法的時(shí)間復(fù)雜度是多少？2.

寫(xiě)出下述算法的功能：voidAJ(adjlistGL,inti,intn){ QueueQ; InitQueue(Q); cout<<i<<''; visited[i]=true; QInsert(Q,i);while(!QueueEmpty(Q)){ intk=QDelete(Q); edgenode*p=GL[k]; while(p!=NULL) { intj=p->adjvex; if(!visited[j]){ cout<<j<<''; visited[j]=true; QInsert(Q,j); } p=p->next; } }}

五、

算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下標(biāo) elseif(K<[mid].key)______________________________________;//在左子表上繼續(xù)查找 else__________________________________;//在右子表上繼續(xù)查找}