數(shù)據(jù)結(jié)構(gòu)試題05(有答案)

吉首大學(xué)試題庫(kù)課程測(cè)試試題(卷) 以下為教師填寫 I、命題院(部)： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱： 數(shù)據(jù)結(jié)構(gòu) III、 測(cè)試學(xué)期：20—20學(xué)年度第學(xué)期TOC\o"1-5"\h\zIV、測(cè)試對(duì)象： 學(xué)院 專業(yè) 級(jí) 班V、問卷頁數(shù)(A4)： 頁VI、答卷頁數(shù)(A4)： 頁VII、考試方式： 閉卷(開卷、閉卷或課程小論文，請(qǐng)?zhí)顚懬宄?VIII、 問卷內(nèi)容：(請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號(hào))、選擇題(20分)1．2．3．組成數(shù)據(jù)的基本單位是()。(A)數(shù)據(jù)項(xiàng)1．2．3．組成數(shù)據(jù)的基本單位是()。(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,<3,4>,<4,1>}，則數(shù)據(jù)結(jié)構(gòu)A是((A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)數(shù)組的邏輯結(jié)構(gòu)不同于下列((A)線性表(B)棧)。(C)圖型結(jié)構(gòu) (D))的邏輯結(jié)構(gòu)。(C)隊(duì)列 (D)集合4．(D)24．(D)2則數(shù)組A的長(zhǎng)度最少為((D)80)。二叉樹中第i(i$1)層上的結(jié)點(diǎn)數(shù)最多有()個(gè)。2i-12i (B)2i (C)2i-1 (D)2i-1設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為()(A)p->next=p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S,—個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()。(A)6 (B)4 (C)3將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中,(A)100 (B)40 (C)55設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)數(shù)為()。(A)3 (B) 4 (C) 5 (D) 1根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。(A)4 (B) 5 (C) 6 (D) 7設(shè)有以下四種排序方法，則()的空間復(fù)雜度最大。(A)冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希爾排序二、填空題(30分)設(shè)順序循環(huán)隊(duì)列Q[0：m-1]的隊(duì)頭指針和隊(duì)尾指針分別為F和R,其中隊(duì)頭指針F指向TOC\o"1-5"\h\z當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)列的語句為F= ;。設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為 ，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為 。設(shè)一棵二叉樹中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共有 個(gè)指針域， 個(gè)空指針域。設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)B,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為 。設(shè)無向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對(duì)應(yīng)的鄰接表中有 個(gè)表頭結(jié)點(diǎn)和 個(gè)表結(jié)點(diǎn)。設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有 關(guān)系。設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為設(shè)一棵完全二叉樹中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是 ，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。intindex(chars[],chart[]){i=j=0;while(i<strlen(s) && j<strlen(t)) if(s[i]==t[j]){i=i+l;j=j+l;}else{i= ;j= ;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則其最小生成樹上有 條邊。三、應(yīng)用題(30分)設(shè)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。設(shè)給定一個(gè)權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計(jì)算哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL。

3．設(shè)一組初始記錄關(guān)鍵字序列為（19，21，16，5，18，23），要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4．設(shè)一組初始記錄關(guān)鍵字集合為（25，10，8，27，32，68），散列表的長(zhǎng)度為8，散列函數(shù)H（k）=kmod7，要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。設(shè)無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計(jì)題（20分）設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。數(shù)據(jù)結(jié)構(gòu)試卷參考答案一、選擇題1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空題(F+1)%mO(n)，O(n)2n，n+1s->next=p->next;s->next=sn,2em=2eCBA4，16i-j+1，0n-11.2.3.4.1.2.3.4.5.、應(yīng)用題鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDEC，哈夫曼樹略，WPL=78(18,5,16,19,21,23)，(5，16，線性探測(cè)：012345中序DBEAC,后序DEBCA。h0h->821，19，18，23)1h8 102532267678 鏈地址法：h2->10深度：125364,8廣度：10123456,最你生成樹T的邊集為E=->1254)，32(1，3),(3,5),(5，6)，(5,6)}4h->685h->276四、算法設(shè)計(jì)題設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。typedefstruet{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack.top=-1;lklist*p;for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;}for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;scanf("%c",&ch);if(ch=='#'){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);}3.設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分)1．下面關(guān)于線性表的敘述錯(cuò)誤的是()。線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有()個(gè)空指針域。(A)2m-1 (B)2m (C)2m+1 (D)4m設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。(A)R-F (B)F-R (C)(R-F+M)％M(D)(F-R+M)％M設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為()。(A)BADC (B)BCDA (C) CDAB (D) CBDA設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊。(A)n(n-1)/2 (B)n(n-1) (C) n2 (D) n2-1設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為()。(A)9 (B)10 (C)11 (D)12設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)n-1 (B)n (C)n+1 (D)2n-1設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為()。TOC\o"1-5"\h\z(A)2， 3， 5，8，6 (B)3，2， 5， 8， 6(C)3， 2， 5，6，8 (D)2，3， 6， 5， 8二、填空題(24分)為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是 和 。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);TOC\o"1-5"\h\zelse{ ; ;}}中序遍歷二叉排序樹所得到的序列是 序列(填有序或無序)。快速排序的最壞時(shí)間復(fù)雜度為 ，平均時(shí)間復(fù)雜度為 。設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N。，度數(shù)為1的結(jié)點(diǎn)數(shù)為叫，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為 ；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有 個(gè)空指針域。設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e= 。設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為 。

v一〉3一〉2一〉41&設(shè)某無向圖G的鄰接表為v2一〉1一〉3 ，則從頂點(diǎn)V開始的深度優(yōu)先遍歷序列為 v一>1—>4一>23v一>1一>34廣度優(yōu)先遍歷序列為 。三、應(yīng)用題(36分)1．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink)。設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。設(shè)一棵樹T中邊的集合為{(A, B), (A, C), (A, D),(B, E), (C, F),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。設(shè)有無向圖G(如右圖所示)，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題(16分)設(shè)有一組初始記錄關(guān)鍵字序列(K,K,?,K),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將1 2 n線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于K,右半部分的每個(gè)關(guān)鍵字均大于等于K。11設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=AGB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題D2.B3.C4.A5.A6.C7.B8.C二、填空題構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法stack.top++，stack.s[stack.top]=x有序O(n2)，O(nlogn)N-1，2N+N001d/2(31，38，54，56，75，80，55，63)(1，3，4，2)，(1，3，2，4)三、應(yīng)用題(22，40，45，48，80，78)，(40，45，48，80，22，78)q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹略5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.略四、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列(K,K,…，K),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將1 2 n線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于K，右半部分的每個(gè)關(guān)鍵字均大于等于K。11voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設(shè)有兩個(gè)集合A和集合B要求設(shè)計(jì)生成集合C=AHB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}

數(shù)據(jù)結(jié)構(gòu)試卷(三)一、選擇題(30分)1?設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},2．3.r={<01,02>,<012．3.r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},則數(shù)據(jù)結(jié)構(gòu)A是()。(A)線性結(jié)構(gòu)(B)下面程序的時(shí)間復(fù)雜為for(i=1,s=0；i<=n；(A)O(n) (B)樹型結(jié)構(gòu))i++){t=1O(n2)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,(A)(B)(C)(D)q=p->next；q=p->next；q=p->next；q=p->next；p->data=q->data；q->data=p->data；p->next=q->next；p->data=q->data；for(j=1；j<=i；j++)t=t*j；s=s+t；}(C)O(n3) (D)O(n4)若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列為()。p->next=q->next；free(q)；p->next=q->next；free(q)；free(q)；free(q)；設(shè)有n個(gè)待排序的記錄關(guān)鍵字,則在堆排序中需要()個(gè)輔助記錄單元。(A)1 (B)n (C)nlogn(D)n2設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10,15,14,18,20,36,40,21(B)10,15,14,18,2040,36,21(C)10,15,14,20,1840,36,2l(D)15,10,14,18,20,36,40,21設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長(zhǎng)度為()。(A)O(1) (B)O(log2n) (C) (D)O(n2)設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為()。(A)n,e (B)e,n (C)2n,e (D)n,2e&設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有()條邊。(A)n(n-1) (B)n+1 (C)n (D)n(n+1)設(shè)有5000個(gè)待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字,則用下列()方法可以達(dá)到此目的。(A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序下列四種排序中()的空間復(fù)雜度最大。(A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序二、填空殖(48分,其中最后兩小題各6分)數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和 兩種情況。設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn),則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu),則共有 個(gè)空指針域。設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到 種不同的輸出序列。設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的 ，第i列上所有元素之和等于頂點(diǎn)i的 。設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有 個(gè)度數(shù)為1的結(jié)點(diǎn)。設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為 。7. 遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。7.& 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較 次就可以斷定數(shù)據(jù)元素X是否在查找表中。TOC\o"1-5"\h\z不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為 。設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為 ，右孩子結(jié)點(diǎn)的編號(hào)為 。設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為 。設(shè)有向圖G中有向邊的集合E={vl,2＞，＜2，3＞，＜1,4＞，＜4，2＞，＜4，3＞}，則該圖的一種拓?fù)湫蛄袨?。下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=( )%m;if(i==j)return(-1);}if( )return(j);elsereturn(-1);}下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k請(qǐng)?jiān)谙聞澗€處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t-＞key==k) ;elseif(t-＞key＞k)t=t-＞lchild;else ;}三、算法設(shè)計(jì)題(22分)1．設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷(三)參考答案一、選擇題1.B 2.B6.B 7.D一、選擇題1.B 2.B6.B 7.D3.A 4.A 5.A8.C 9.B 10.D第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中,最后刪除結(jié)點(diǎn)B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出最小的10個(gè)數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間復(fù)雜度為O(log2n)。二、填空題順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)9，501TOC\o"1-5"\h\z5出度，入度0e=d中序7O(1)i/2，2i+1(5，16，71，23，72，94，73)(1，4，3，2)j+1，hashtable[j].key==kreturn(t)，t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過二叉判定樹的高度l+log2n。三、算法設(shè)計(jì)題設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx)if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題(30分)設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為()。(A)O(n) (B)O(nlogn)(C)O(1) (D)O(n2)設(shè)一棵二叉樹的深度為k則該二叉樹中最多有()個(gè)結(jié)點(diǎn)。(A)2k-1 (B) 2k (C) 2k-1 (D) 2k-1設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為()。(A)n (B) e (C) 2n (D) 2e在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。(A)O(1) (B)O(n) (C)O(logn) (D)O(n2)5?設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有()條有向邊。(A)n (B)n-1 (C)m (D)m-1設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3 (B)4 (C)5 (D)8設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作()。(A)必須判別棧是否為滿 (B)必須判別棧是否為空(C)判別棧元素的類型 (D)對(duì)棧不作任何判別下列四種排序中()的空間復(fù)雜度最大。(A)快速排序(B)冒泡排序(C)希爾排序(D)堆設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為叫，度數(shù)為2的結(jié)點(diǎn)數(shù)為％,則下列等式成立的是()。(A)N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過()。(A)logn+1 (B) logn-1 (C) logn (D) log(n+1)二、填空題(42分)設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度 ，快速排序的平均時(shí)間復(fù)雜度為 。設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為 (設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)0根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為 深度為k的完全二叉樹中最少有 個(gè)結(jié)點(diǎn)。設(shè)初始記錄關(guān)鍵字序列為(K,K,…，K),則用篩選法思想建堆必須從第 個(gè)元素開始進(jìn)行篩12n選。設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有 個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹中有 個(gè)空指針域。設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存彳 個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ) 個(gè)隊(duì)列元素(設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置)。設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中 個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中 個(gè)元素。設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為 。TOC\o"1-5"\h\z10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為 。設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是 。設(shè)無向圖對(duì)應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè)數(shù) 第i列上非0元素的個(gè)數(shù)(填等于，大于或小于)。設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為 。設(shè)散列函數(shù)H(k)=kmodp,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;i<m;i++) ;for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k]; ;}}三、算法設(shè)計(jì)題(28分)設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案一、選擇題1．C2．D3．D4．B5．C6．A7．B8．A9．C10．A二、填空題1.O(n2)，O(nlogn)2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink3.34.2k-15.n/26.50，517.m-1，（R-F+M）%M8.n+1-i，n-i9.（19，18，16，20，30，22）10.（16，18，19，20，32，22）11.A[i][j]=112.等于13.BDCA14.hashtable[i]=0，hashtable[k]=s三、算法設(shè)計(jì)題設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題(30分)1．?dāng)?shù)據(jù)的最小單位是()。數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為()。(A)40，50，20，95 (B)15，40，60，20(C)15，20，40，45 (D)45，40，15，203．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為()。(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,85函數(shù)substr(“DATASTRUCTURE”，5,9)的返回值為()。(A)“STRUCTURE” (B)“DATA”(C)“ASTRUCTUR” (D)“DATASTRUCTURE”設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為()。(A)O(logn)(B)O(1) (C)O(n2) (D)O(n)設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為叫， ，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，TOC\o"1-5"\h\z則N=( )。(A)N+N+??+Nm (B)l+N+2N+3N+??+(m-1)Nm2 2 3 4(C)N+2N+3N+??+(m-1)Nm (D)2N+3N+??+(m+1)Nm3 4 l2設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較()次。(A)25 (B)10 (C)7 (D)1設(shè)連通圖G中的邊集E={(a, b), (a，e), (a，c), (b, e),(e, d)，(d,f)，(f，c)},則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為()。(A)abedfc (B)acfebd(C)aebdfc (D)aedfcb設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是()。(A)n-i (B)n-1-i (C)n+1-i (D)不能確定10設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是()。TOC\o"1-5"\h\z(A)40， 42， 45， 55，80， 83 (B)42，40， 45， 80， 85， 88(C)42， 40， 45， 55，80， 85 (D)42，40， 45， 85， 55， 80二、填空題(共30分)設(shè)有一個(gè)順序共享?xiàng)[0：n-1],其中第一個(gè)棧項(xiàng)指針top1的初值為-1,第二個(gè)棧頂指針top2的初值為n,則判斷共享?xiàng)M的條件是 。在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是 。設(shè)有一個(gè)n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對(duì)角線上元素)存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有 個(gè)數(shù)據(jù)元素。

TOC\o"1-5"\h\z棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為 表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為 表。設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為 ABCDEF，則該二叉樹的前序遍歷序列為 ，中序遍歷序列為 ，后序遍歷序列為 。設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為 ，有 個(gè)葉子結(jié)點(diǎn)。設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的 ，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的 。&設(shè)一組初始記錄關(guān)鍵字序列(k，k，……，k)是堆，則對(duì)i=l,2,…，n/2而言滿足的條件為1 2 n 。下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j< ;j++)if(r[j]>r[j+1]){temp=r[j+1]; ;r[j]=temp;exchange=1;}if(exchange==0)return；}}下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){if(r[mid].key==k)return(mid+1);elseif( )high=mid-1;elselow=mid+1;}return(0);三、應(yīng)用題(24分)1.2.3.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC1.2.3.設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。4.設(shè)散列表的長(zhǎng)度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)鍵字序列為(25,31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。四、算法設(shè)計(jì)題(16分)1．設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法2．設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案一、選擇題1．一、選擇題1．A 2．B6．B 7．B3．A 4．A 5．D8．B 9．C 10．C二、填空題二、填空題top1+1=top2可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的簡(jiǎn)單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，647.出度，入度8.ki<=k2i&&ki<=k2i+1i2ii2i+19.n-i，r[j+1]=r[j]10.mid=(low+high)/2，r[mid].key>k三、應(yīng)用題DEBCAE={(1,5),(5,2),(5,3),(3,4)},W=10ASL=(1*1+2*2+3*4)/7=17/7ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。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;}1．2．3．4．5．6．7．8．9．10.11.12.13.14.15.數(shù)據(jù)結(jié)構(gòu)試卷(六)一、選擇題(30分)設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為()。(A)20 (B)30 (C)40 (D)45執(zhí)行一趟快速排序能夠得到的序列是()。(A)[41,12,34,45,27]55[72,63](B)[45,34,12,41]55[72,63,27](C)[63,12,34,45,27]55[41,72](D)[12,27,45,41]55[34,63,72]設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是()。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是()。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹滿足的條件是()(A)空或只有一個(gè)結(jié)點(diǎn) (B)高度等于其結(jié)點(diǎn)數(shù)(C)任一結(jié)點(diǎn)無左孩子 (D)任一結(jié)點(diǎn)無右孩子一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是()。(A)堆排序 (B)冒泡排序 (C)快速排序 (D)希爾排序設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn),則該三叉樹的最小高度為()。(A)3 (B)4 (C)5 (D)6順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為()。(A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1ogn)二路歸并排序的時(shí)間復(fù)雜度為()。(A) O(n) (B) O(n2) (C) O(nlogn) (D) O(1ogn)深度為k的完全二叉樹中最少有()個(gè)結(jié)點(diǎn)。(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為()。(A)front->next=s；front=s；(C)rear->next=s；rear=s；(A)front->next=s；front=s；(C)rear->next=s；rear=s；設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊(A)O(n+e) (B)O(n2)(D)s->next=front；front=s；則建立該圖鄰接表的時(shí)間復(fù)雜度為()O(ne) (D)O(n3)設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn),則該哈夫曼樹中有()個(gè)葉子結(jié)點(diǎn)。(A)99(B)100(C)101(D)102設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn),則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為()。(A)O(n) (B)O(n2) (C)O(nlogn)(D)O(1ogn)設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為()。(A)第i行非0元素的個(gè)數(shù)之和 (B)第i列非0元素的個(gè)數(shù)之和(C)第i行0元素的個(gè)數(shù)之和 (D)第i列0元素的個(gè)數(shù)之和二、判斷題(20分)1．21．23．分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。()冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。()

4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個(gè)有序的序列。（）7?設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（）中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（）快速排序是排序算法中平均性能最好的一種排序。（）三、填空題（30分）TOC\o"1-5"\h\zfor（i=l,t=1,s=0；i<=n；i++）{t=t*i；s=s+1；}的時(shí)間復(fù)雜度為 。設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則進(jìn)行插入操作的語句序列為 （設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。設(shè)有向圖G的二元組形式表示為G=（D,R）,D={1,2,3,4,5},R={r},r={vl,2>,v2,4>,v4,5>,<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄?。設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多是 。設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有 個(gè)結(jié)點(diǎn)數(shù)。設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為 。設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 。簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為 ?？焖倥判蛩惴ǖ目臻g復(fù)雜度平均情況下為 最壞的情況下為 。散列表中解決沖突的兩種方法是 和 。四、算法設(shè)計(jì)題（20分）1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案1．D2．A3．A1．D2．A3．A4．A6．D7．B8．A9．C11．C12．A13．B14．D15．B一、選擇題5．D10．B二、判斷題1．錯(cuò)二、判斷題1．錯(cuò)2．對(duì)6．錯(cuò)7．對(duì)3．對(duì)4．對(duì)8．錯(cuò)9．對(duì)5．錯(cuò)10．對(duì)三、填空題O(n)s->next=p->next;p->next=s(1，3，2，4，5)n-1129F==Rp->lchild==0&&p->rchild==0O(n2)O(nlog2n)，O(n)開放定址法，鏈地址法四、算法設(shè)計(jì)題設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷(七)一、選擇題(30分)1?設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。2n (B)n (C)n/2 (D)n(n-1)設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有()條邊。(A)n (B)n-1 (C)2n (D)2n-1設(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，80()二叉排序樹可以得到一個(gè)從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(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-1程序段s=i=0；do{i=i+l；s=s+i；}while(iv=n)；的時(shí)間復(fù)雜度為()。(A)O(n) (B)O(nlogn) (C)O(n2) (D)O(n3/2)設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是()。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=0設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有()。(A)20 (B)256 (C)512 (D)1024設(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)4設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為()。(A)top=top+1; (B)top=top-1;(C)top->next=top; (D)top=top->next;二、判斷題(20分)不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。()當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。()設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(log2n)。()完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。()哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。()對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。()先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。()由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。()線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。()帶權(quán)無向圖的最小生成樹是唯一的。()三、填空題(30分)設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為 =p；s-〉right=p-〉right； =s；p-〉right-〉left=s；(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right)。設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有 條有向條；設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中共有 條無向邊。設(shè)關(guān)鍵字序列為(人，K,…，K),則用篩選法建初始堆必須從第 個(gè)元素開始進(jìn)行篩選。TOC\o"1-5"\h\zl2 n解決散列表沖突的兩種方法是 和 。設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有 個(gè)。高度為h的完全二叉樹中最少有 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是 。設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是 。設(shè)一棵二叉樹的前序序列為ABC,則有 種不同的二叉樹可以得到這種序列。下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語句。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分)設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題1．B2．B3．C4．B5．B6．A7．C8．C9．B10．D二、判斷題1．對(duì)2．對(duì)3．對(duì)4．對(duì)5．對(duì)6．對(duì)7．對(duì)8．錯(cuò)9．錯(cuò)10．錯(cuò)三、填空題s->left=p，p->rightn(n-1)，n(n-1)/2n/2開放定址法，鏈地址法146.2h-1，2h-17.(12，24，35，27，18，26)(12，18，24，27，35，26)5i<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';}}設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。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);}}1.2.3.4.5.6.7.8.9.10.二1.2.3.4.5.6.7.8.9.10.三1．?dāng)?shù)據(jù)結(jié)構(gòu)試卷(八)選擇題(30分)字符串的長(zhǎng)度是指()(A)串中不同字符的個(gè)數(shù)(C)數(shù)據(jù)結(jié)構(gòu)試卷(八)選擇題(30分)字符串的長(zhǎng)度是指()(A)串中不同字符的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù)建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為()(A)O(n) (B)O(1)兩個(gè)字符串相等的充要條件是((A)兩個(gè)字符串的長(zhǎng)度相等(C)同時(shí)具備(A)和(B)兩個(gè)條件O(n2) (D)O(logn))。兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等以上答案都不對(duì)設(shè)某散列表的長(zhǎng)度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇()。(A)99 (B)97 (C)91(D)93在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為()。(A)O(n) (B)O(1ogn)(C)O(nlogn)(D)O(n2)設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?)。(A)A[1],A[2],A[3],A[4] (B)A[1],A[14],A[7],A[4]A[7],A[3],A[5],A[4] (D)A[7],A[5],A[3],A[4]設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn),則該完全二叉樹的深度為()。(A)8 (B)7 (C)6 (D)5設(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)8設(shè)無向圖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)aedfbc隊(duì)列是一種()的線性表。(A)先進(jìn)先出 (B)先進(jìn)后出 (C)只能插入 (D)只能刪除判斷題(20分)如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等,則稱這兩個(gè)關(guān)鍵字為同義詞。()設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為0(nlog2n)。()分塊查找的基本思想是首先在索引表中進(jìn)行查找,以便確定給定的關(guān)鍵字可能存在的塊號(hào),然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。()二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。()向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。()如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。()非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。()不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。()圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組,以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。()稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。()填空題(30分)設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為 。

2．下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(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;}TOC\o"1-5"\h\zelseif(t->data>k)bstinsert(t->lchild,k);else ;}設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s-〉next二p-〉next; ;。設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p= 和head= (設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)。設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC,則其前序遍歷序列為 。完全二叉樹中第5層上最少有 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。設(shè)有向圖中不存在有向邊〈V,V〉，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于ij 。設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為 。設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹上有 條邊。設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與 相互交換即可。四、算法設(shè)計(jì)題(20分)設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案一、選擇題1．C 2．C3．C4．B5．B6．C 7．B8．C9．A10．A二、判斷題1．對(duì)2．錯(cuò)3．對(duì)4．錯(cuò)5．錯(cuò)6．對(duì)7．對(duì)8．對(duì)9．對(duì)10．對(duì)三、填空題(49，13，27，50，76，38，65，97)t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)p->next=shead->rlink，p->llinkCABD1，160(13，27，38，50，76，49，65，97)n-150四、算法設(shè)計(jì)題設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(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)試卷(九)一、選擇題(30分)1．下列程序段的時(shí)間復(fù)雜度為()。j++)c[i][j]=0；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j](C)O(m+n*t)(D)O(m*t+n)for(i=0；i<m；i++)for(j=0；j<tfor(i=0；i<m；i++)for(j=0j++)c[i][j]=0；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j](C)O(m+n*t)(D)O(m*t+n)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)()個(gè)元素。(A)n-i (B)n+l-i (C)n-1-i (D)i設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，Tl、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為()。(A)Nl-l (B)N2-l (C)N2