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

重慶工商大學(xué)試卷考試科目： 數(shù)據(jù)結(jié)構(gòu) 試卷適用專業(yè)(班) 2004考核方式：開卷(丿閉卷(V)2005-2006學(xué)年度2學(xué)期一．選擇題(單項(xiàng)選擇，每小題2分，共計(jì)20分)1、 已知某數(shù)據(jù)的邏輯結(jié)構(gòu)S=(D,R),其中D={a,b,c,d,e,f},R=〈a,b〉，〈b,c〉，〈c,d〉，〈d,e〉，〈e,f〉},請指出它們屬于下面的哪種結(jié)構(gòu) :集合 B.線性結(jié)構(gòu) C.樹形結(jié)構(gòu) D.圖形結(jié)構(gòu)2、 若線性表最常用的運(yùn)算是存取第i個(gè)元素及其前趨的值，則采 存儲(chǔ)方式節(jié)省時(shí)間。A.單鏈表 B.雙鏈表 C.單循環(huán)鏈表 D.順序表TOC\o"1-5"\h\z3、 單鏈表中，若*p結(jié)點(diǎn)不是末尾結(jié)點(diǎn)，在其后插入*s的操作是 。A.s—〉next二p;p—〉next二s; B.s—〉next二p—〉next;p—〉next二s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;4、 經(jīng)過以下棧運(yùn)算后，x的值是 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);A.a B.b C.1 D.05、 最適合用作鏈?zhǔn)疥?duì)列的鏈表 。帶隊(duì)首指針和隊(duì)尾指針的循環(huán)單鏈表帶隊(duì)首指針和隊(duì)尾指針的非循環(huán)單鏈表只帶隊(duì)首指針的非循環(huán)單鏈表只帶隊(duì)首指針的循環(huán)單鏈表TOC\o"1-5"\h\z6、 串是一種特殊的線性表，其特殊性體現(xiàn) 。A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符7、 對(duì)稱矩陣壓縮存儲(chǔ)是為了 。A.方便運(yùn)算 B.節(jié)省空間C.提高運(yùn)算速度 D.以上都不是8、 高度為h的二叉樹上至多有 個(gè)結(jié)點(diǎn)(h三1)。A.2h—1 B.2h—1 C.2h+1 D.2h9、 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中 。A.從源點(diǎn)到匯點(diǎn)的最長路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長的回路 D.最短的回路10、 在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找,可能要探測多個(gè)位置,在查找成功的情況下，所探測的這些位置上的鍵 。A.一定都是同義詞 B.一定都不是同義詞C.都相同 D.不一定都是同義詞二、填空題(每題1分，共計(jì)10分)TOC\o"1-5"\h\z1、具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度 。2、 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0,當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為 。3、 設(shè)有兩個(gè)串p和q,其中q是p的子串，把q在p中首次出現(xiàn)的位置作為子串q在p中的位置的算法稱為 。4、 數(shù)組A[0..5,0..6](即數(shù)組A[6][7])的每個(gè)元素占5個(gè)單元，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)內(nèi)存單元中，則元素a[5][5]的地址為 。5、 已知廣義表A=(a,b，(c,d),(e,(f,g))),則式子tail[head[tail[tail(A)]]]的值為 。6、 對(duì)任何二叉樹，若度為2的結(jié)點(diǎn)數(shù)為n2，則葉子數(shù)n0= 。7、 若以｛4,5,6,7,8｝作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是 。8、 普里姆(Prim)算法適用于求 的網(wǎng)的最小生成樹。9、 有一個(gè)有序表R[1-13]=｛1,3,9,12,32,41,45,62,75,77,82,95,100｝,當(dāng)用二分查找法查找值為82的結(jié)點(diǎn)時(shí)，經(jīng) 次比較查找成功。10、 在各種查找方法中，其平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的查找方法 。三、應(yīng)用題(每題10分,共計(jì)40分)1、已知一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖1所示。(小計(jì)10分)(1)畫出此棵二叉樹。(4分)1 2 3 4 5 6 7 8 9 10 11 12 13 14ABFCGJDEHIK圖1.某二叉樹的順序存儲(chǔ)結(jié)構(gòu)(2)寫出該二叉樹的先根遍歷和后根遍歷的序列。(6分)2、設(shè)無向圖有6個(gè)結(jié)點(diǎn),依次輸入的9條邊為(1,2),(1,3),(1,5),(1,6),(2,3),(3,4)(3,5),(4,5),(5,6)。畫出無向圖G。(4分)畫出G的鄰接表(6分)3、將整數(shù)序列｛4,5,7,2,1,3,6｝中的數(shù)依次插入一棵空的二叉排序樹中。(10分)1)畫出相應(yīng)的二叉排序樹。(6分)2)求等概率情況下查找成功的平均查找長度。(4分)4、以關(guān)鍵字序列{10，2，13，15，12，14}為例，用堆排序方法進(jìn)行排序。寫出每趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。(請按小根堆進(jìn)行排序)(小計(jì)10分)四、算法閱讀題(每題10分，共計(jì)20分)。1、已知二叉樹的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedefstructnode{ElemTypedata;//數(shù)據(jù)元素structnode*lchild; //指向左孩子structnode*rchild; //指向右孩子}BTNode;閱讀下列二叉樹算法,回答問題。intfun1(BTNode*b){intnum1,num2;if(b==NULL)return0;elseif(b->lchild==NULL&&b->rchild==NULL)return1;else{num1=fun1(b->lchild);num2=fun1(b->rchild);return(num1+num2);}}(1)該算法執(zhí)行二叉樹運(yùn)算的什么功能？(6分)(2)若存在二叉樹如圖2所示二叉樹，試問執(zhí)行上述算法后，其執(zhí)行結(jié)果是多少？(4分)2、已知L是一個(gè)遞增有序表，x的數(shù)據(jù)類型與L中元素類型一致。執(zhí)行以下算法，問:voidfun2(SeqList&L,DataTypex){inti=0,j;while(i<L.length&&L.data[i]<x)i++;for(j=L.length;j>=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.length++;}(1)該算法執(zhí)行什么功能？(6分)(2)假設(shè)初始有序表L={1,3,5,8,9},x=7。執(zhí)行上述算法后，該有序表發(fā)生什么變化？(4分)五、算法設(shè)計(jì)題(在下列算法的橫線內(nèi)填上適當(dāng)?shù)恼Z句或表達(dá)式。每空2分,共10分)已知單鏈表的結(jié)點(diǎn)數(shù)據(jù)類型如下：typedefstructLnode{ElemTypedata;StructLnode*next;}LinkList;設(shè)計(jì)一個(gè)算法，將一個(gè)帶頭結(jié)點(diǎn)的數(shù)據(jù)域依次為al,a2,……，an(n23)的單鏈表的的所有結(jié)點(diǎn)逆置(即第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域變?yōu)閍n，最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域變?yōu)閍l)，生成一個(gè)新的單鏈表。voidReverse(LinkList*&head){LinkList*p=head->next;head->next=(1) ; //采用前插法生成新的單鏈表while(p!= (2) ) //掃描所有結(jié)點(diǎn){q=p-〉next; //q指向*p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)p->next= (3) ;//總是將*p作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)head->next二(4 ;二5 ;}

05--06學(xué)年第2學(xué)期《數(shù)據(jù)結(jié)構(gòu)》試卷A參考答案及評(píng)分標(biāo)準(zhǔn)一、 選擇題（每小題2分，共計(jì)20分）BDBABBBAAD二、 填空題（每小題1分，共計(jì)10分）1、O（1） 2、4和2 3、模式匹配 4、1175 5、（d）6、n2+1 7、69 8、邊稠密 9、4 10、哈希（散列）查找三、 應(yīng)用題（每小題10分，共計(jì)40分）1、（1）二叉樹圖形如下圖1：圖1二叉樹TOC\o"1-5"\h\z畫正確11個(gè)結(jié)點(diǎn)，得分 4分。畫正確7-10個(gè)結(jié)點(diǎn)，得分 3分。畫正確4-6個(gè)結(jié)點(diǎn)，得分 2分畫正確2-3畫正確2-3個(gè)結(jié)點(diǎn)，得分 1分⑵先根遍歷序列是：ABCDEFGHIJK⑵先根遍歷序列是：ABCDEFGHIJK后根遍歷序列是：DECBHIGKJFA3分3分2、2、2）6（分）圖3.鄰接矩陣3、（1）生成的二叉排序樹如下圖所示：（6分）圖4.二叉排序樹評(píng)分標(biāo)準(zhǔn)：從插入的第二個(gè)結(jié)點(diǎn)開始計(jì)分，每正確插入一個(gè)結(jié)點(diǎn)，得1分（2）查找成功的平均查找長度是：ASL=（1X1+2X2+3X3+4X1）/7=18/7=2.574、（10分）初始狀態(tài)：10，2，13，15，12，14TOC\o"1-5"\h\z第1趟：（2，10，13，15，12，14） 2分第2趟：2，（10，12，13，15，14） 2分第3趟：2，10，（12，14，13，15） 2分第4趟：2，10，12，（13，14，15） 2分第5趟：2，10，12，13，（14，15） 2分第6趟：2，10，12，13，1