十套數(shù)據(jù)結(jié)構(gòu)試題及答案1

數(shù)據(jù)結(jié)構(gòu)試卷（一） 錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（二） 錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（三） 錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（四） 錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（五） 錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（六） 錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（七） 錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（八） 錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（九） 錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（十） 錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案參考答案錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案參考答案錯(cuò)誤!未定義書簽。書簽。數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案 錯(cuò)誤!未定義數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案參考答案錯(cuò)誤!未定義書簽。數(shù)據(jù)結(jié)構(gòu)試卷（一）2分，共20分）棧和隊(duì)列的共同特點(diǎn)是 （A）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)用鏈接方式存儲的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí) （D）.A.僅修改頭指針 B.頭、尾指針都要修改C.僅修改尾指針 D.頭、尾指針可能都要修改以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu) （D）A.隊(duì)列B.棧 C.線性表 D.二叉樹3.設(shè)有一個(gè)二維數(shù)組 A[m][n],假設(shè)A[0]⑼存放位置在644（10）,A[2][2]存放位置在676（10）,3.每個(gè)元素占一個(gè)空間，問A[3][3]（10）存放在什么位置腳注 （10）表示用10進(jìn)制表示（C）。C．692 D．696B.C．692 D．696B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)D.2k-1TOC\o"1-5"\h\z樹最適合用來表示 （C ）。A.有序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)二叉樹的第 k層的結(jié)點(diǎn)數(shù)最多為（D）.A．2k-1 +1若有18個(gè)元素的有序表存放在一維數(shù)組 A[19]中，第一個(gè)元素放 A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為 （D）A.1， 2， 3 B.9， 5， 2，3C.9， 5， 3 D.9， 4， 2，3對n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為（C）A.O（1） B.O（n） C.O（1og2n） D.O（n2）對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個(gè)，A．1 B．2 C．3 D．4設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有 （A ）條邊才能確保是一個(gè)連通圖。三、計(jì)算題（每題6分，共24分）.在如下數(shù)組A中鏈接存儲了一個(gè)線性表，表頭指針為A[0].next，試寫出該線性表。44446050789034403572041datanextA0 1 2 3 4 5 601110101011101110101線性表為：(78,50,40,60,34,90).請畫出下圖的鄰接矩陣和鄰接表。.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹為： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10, (4,7)20.畫出向小根堆中加入數(shù)據(jù) 4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。見圖124 5 64 5 64 5 64 5 64.圖11｛設(shè)某強(qiáng)連有()條邊。(A)n(n-1).4.圖11｛設(shè)某強(qiáng)連有()條邊。(A)n(n-1).設(shè)有5000個(gè)待排選出其中最小的以達(dá)到此目的。(A)快速排序.下列四種排序中((A)插入排序)的空間復(fù)雜度最大。通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少(B)冒泡排序 (C)堆排序(D)歸并排序四、閱讀算法(每題7分，共14分)1.LinkListmynote(LinkListL)(D)n(n+1)序的記錄關(guān)鍵字，如果需要用最快的方法10個(gè)記錄關(guān)鍵字，則用下列( )方法可(D)插入排序三、計(jì)算題(每題10分，共30分).已知二叉樹的前序遍歷序列是 AEFBGCDHIKJ中序遍歷序列是EFAGBCHKIJD畫出此二叉樹，并畫出它的后序線索二叉樹。.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為 [0..6],假定選用的散列函數(shù)是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：H(36)=36mod7=1; Hi(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突 H2(22)=(2+1)mod7=3;Hi(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突(1)計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表:' 0 12 363361522401ASL=—211351.61ASL=—211351.6.已知序列(10,18,4,3,6,12,1,9,18,8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題(每題15分，共30分).設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。設(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)算法。設(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)試卷(四)一、選擇題(每題1分共20分)TOC\o"1-5"\h\z.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為( )。(A)O(n) (B)O(nlog2n) (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(log2n) (D)O(n2).設(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è)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作( )。(A)必須判別棧是否為滿 (B)必須判別棧是否為空(C)判別棧元素的類型 (D)對棧不作任何判別.下列四種排序中( )的空間復(fù)雜度最大。(A)快速排序 (B)冒泡排序 (C)希爾排序(D)堆.設(shè)某二叉樹中度數(shù)為 0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,則下列等式成立的是( )。(A)No=Ni+1 (B)No=Ni+N2 (C)No=N2+1 (D)No=2Ni+1.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素 X的最多比較次數(shù)不超過()。(A)10g2n+1 (B)10g2n-1 (C)10g2n (D)10g2(n+1)三、計(jì)算題(每題10分，共30分)1、畫出廣義表LS=((),(e),(a,(b,c,d))的頭尾鏈表存儲結(jié)構(gòu)。LS0Ie101al11|0Ie101al11|I|---->11|J-0lb [0Tc>2、下圖所示的森林：(1)求樹(a)的先根序列和后根序歹U;(1)ABCDEF;BDEFCA(2)ABCDEFGHIJK;BDEFCAIJKH琳轉(zhuǎn)換為相應(yīng)的二叉樹;

(2)求森林先序序列和中序序列;ABCDEF;BDEFCA3、設(shè)散列表的地址范圍是 [0..9],散列函數(shù)為H(key)=(key2+2)MOD9,并采用鏈表處理沖突，請畫出元素 7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H⑺=6（每題10分，共30分）．設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 (大寫字母、數(shù)字和其它字符 )，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。設(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)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯Y(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)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。在鏈?zhǔn)酱鎯Y(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)試卷(五)數(shù)據(jù)結(jié)構(gòu)試卷(五)數(shù)據(jù)結(jié)構(gòu)試卷(五)數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題(20分)TOC\o"1-5"\h\z.數(shù)據(jù)的最小單位是( )。(A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素(D)數(shù)據(jù)變量.設(shè)一組初始記錄關(guān)鍵字序列為 (50,40,95,20,15,70,60,45),則以增量d=4的一趟希爾排序Z束后前4條記錄關(guān)鍵字為( )。(A)40,50,20,95(B)15,40,60,20(C)15,20,40,45(D)45,40,15,20.設(shè)一組初始記錄關(guān)鍵字序列為 (25,50,15,35,80,85,20,40,36,70),其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(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(DATASTRUCTURE5,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(log2n) (B)O(1) (C)O(n2) (D)O(n).設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N。，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm,則No=()。(A)Ni+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm (D)2N+3N2+……+(m+1)NmTOC\o"1-5"\h\z.設(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é)果是( )。(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三、應(yīng)用題（32分）1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC前序遍歷序列為要求給出該二叉樹的的后序遍歷序列。三、應(yīng)用題（32分）1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC前序遍歷序列為要求給出該二叉樹的的后序遍歷序列。DEBCAABDEG設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。E={(1,5),(5,2),(5,3),(3,4)},W=10設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長度。ASL=(1*1+2*2+3*4)/7=17/7設(shè)散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為 (25，31，8，27，13，68)，要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題(28分)．設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。設(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è)有序單鏈表的合并排序算法。設(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;數(shù)據(jù)結(jié)構(gòu)試卷(六)5．，(30分)設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為((A)20)。(B)30執(zhí)行一趟快速排序能夠得到的序列是[41[45[63[1212，341227，3412344545，27]55[7241]55[72，6345，27]55[4141]55[34，6363]27]72]72](C)40)。head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是(head==0(C)head->next==head(D)head!=0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為數(shù)據(jù)結(jié)構(gòu)試卷(六)5．，(30分)設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為((A)20)。(B)30執(zhí)行一趟快速排序能夠得到的序列是[41[45[63[1212，341227，3412344545，27]55[7241]55[72，6345，27]55[4141]55[34，6363]27]72]72](C)40)。head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是(head==0(C)head->next==head(D)head!=0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為(A)堆排序(B)冒泡排序(D)45head->next==0O(nlog2n)的是( )。(C)希爾排序(D)快速排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是((A)空或只有一個(gè)結(jié)點(diǎn)(C)任一結(jié)點(diǎn)無左孩子(B)高度等于其結(jié)點(diǎn)數(shù)(D)任一結(jié)點(diǎn)無右孩子6．一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是(一定能夠選出一個(gè)兀素放在其最終位置上的是((A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序7．設(shè)某棵三叉樹中有設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為()。(A)3(B)4(C)5(D)68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為((A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)9．二路歸并排序的時(shí)間復(fù)雜度為二路歸并排序的時(shí)間復(fù)雜度為()。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有(二叉樹中最少有()個(gè)結(jié)點(diǎn)。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1)。)。rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，X,則入隊(duì)列的操作序列為(11.設(shè)指針變量 front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn))。)。)。(A)front->next=s；front=s；rear->next=s；rear=s；設(shè)某無向圖中有 n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為(s->next=rear；rear=s；(D)s->next=front；front=s；則建立該圖鄰接表的時(shí)間復(fù)雜度為()。(A)O(n+e)設(shè)某哈夫曼樹中有(A)99設(shè)二叉排序樹上有(A)O(n)(B)O(n2)(C)O(ne)199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有((B)100(C)101(D)O(n3))個(gè)葉子結(jié)點(diǎn)。(D)102n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為()。O(n2)O(nlog2n)O(1og2n)15.設(shè)用鄰接矩陣 A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為()。第i行非0元素的個(gè)數(shù)之和第i列非0元素的個(gè)數(shù)之和(C)第i行0元素的個(gè)數(shù)之和 (D)第i列0元素的個(gè)數(shù)之和(20分).設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

設(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ì)判斷二叉樹是否為二叉排序樹的算法。設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){minnum=bt->key;inorder(bt->rchild);}}if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;

if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法voidstraightinsertsort(lklist*&head)(Iklist*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;s->next=p;if(s==q->next)q=p;s->next=p;else{q->next=p->next; p->next=s->next;t=p->data;p->data=s->data;s->data=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷(七)數(shù)據(jù)結(jié)構(gòu)試卷(七)數(shù)據(jù)結(jié)構(gòu)試卷(七)數(shù)據(jù)結(jié)構(gòu)試卷(七)一、選擇題 (30分)．設(shè)某無向圖有 n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)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開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為()。(A)2i+1 (B)2i (C)i/2 (D)2i-1．程序段 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)．設(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)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;四、算法設(shè)計(jì)題(20分)設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xià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;}}}設(shè)計(jì)在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(shè)計(jì)在順序存儲結(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)在二叉排序樹中層次的算法。設(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);}}數(shù)據(jù)結(jié)構(gòu)試卷(八)(30分)字符串的長度是指()。(A)串中不同字符的個(gè)數(shù)數(shù)據(jù)結(jié)構(gòu)試卷(八)(30分)字符串的長度是指()。(A)串中不同字符的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù)建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為()(A)O(n) (B)O(1)兩個(gè)字符串相等的充要條件是((A)兩個(gè)字符串的長度相等(C)同時(shí)具備(A)和(B)兩個(gè)條件O(n2) (D)O(log2n))。(B)兩個(gè)字符串中對應(yīng)位置上的字符相等以上答案都不對.設(shè)某散列表的長度為 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(1og2n) (C)O(nlog2n) (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](C)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隊(duì)列是一種()的線性表。(A)aedfcb (B)acfebd隊(duì)列是一種()的線性表。(A)先進(jìn)先出 (B)先進(jìn)后出(C)aebcfd (D)aedfbc(C)只能插入 (D)只能刪除四、算法設(shè)計(jì)題(20分)設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(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)為對應(yīng)鄰接表的算法。設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(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[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)試卷(九)數(shù)據(jù)結(jié)構(gòu)試卷(九)數(shù)據(jù)結(jié)構(gòu)試卷(九)數(shù)據(jù)結(jié)構(gòu)試卷(九)一、選擇題(30分)．下列程序段的時(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)．設(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是由T1、T2和T3三棵樹組成的森林，與 F對應(yīng)的二叉樹為B,T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹 B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為()。(A)N1-1 (B)N2-1 (C)N2+N3 (D)N1+N3．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為()。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(1og2n).設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn) A,指針變量s指向被插入的結(jié)點(diǎn) X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。p->right=s； s->left=p；p->right->left=s； s->right=p->right；s->left=p；s->right=p->right；p->right=s；p->right->left=s；p->right=s； p->right->left=s；s->left=p； s->right=p->right；s->left=p；s->right=p->right；p->right->left=s；p->right=s；.下列各種排序算法中平均時(shí)間復(fù)雜度為 O(n2)是( )。(A)快速排序 (B)堆排序(C)歸并排序 (D)冒泡排序.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是 n,則輸出序列中的第i個(gè)輸出元素是()。(A)n-i (B)n-1-i (C)n+l-i (D)不能確定.設(shè)散列表中有m個(gè)存儲單元，散列函數(shù) H(key尸key%p,則p最好選擇()。(A)小于等于 m的最大奇數(shù) (B)小于等于 m的最大素?cái)?shù)(C)小于等于 m的最大偶數(shù) (D)小于等于 m的最大合數(shù)．設(shè)在一棵度數(shù)為3的樹中，度數(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)7.設(shè)完全無向圖中有 n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/2.設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為()。(A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/2.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過()次比較。(A)1 (B)2 (C)3 (D)4.設(shè)順序線性表的長度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長度為()。(A)6 (B)11 (C)5 (D).設(shè)有向無環(huán)圖G中的有向邊集合 E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?)。1，21，2，3，42，3，4，1，4，2，3 (D)1，2，4，3數(shù)據(jù)結(jié)構(gòu)試卷(十)數(shù)據(jù)結(jié)構(gòu)試卷(十).設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為()。(A)4 (B)5 (C)6 (D)7五、算法設(shè)計(jì)題(20分)．設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}．設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。設(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;}．設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。設(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);一、選擇題(24分)．下列程序段的時(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)．設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲方式最節(jié)省運(yùn)算時(shí)間。(A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表.設(shè)指針q指向單鏈表中結(jié)點(diǎn) A,指針p指向單鏈表中結(jié)點(diǎn) A的后繼結(jié)點(diǎn)B,指針s指向TOC\o"1-5"\h\z被插入的結(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 ；．設(shè)輸入序列為 1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為( )。(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，3.設(shè)有一個(gè)10階的下三角矩陣A(包括對角線)，按照從上到下、從左到右的順序存儲到連續(xù)的55個(gè)存儲單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為()。(A)10 (B)19 (C)28 (D)55.設(shè)一棵m叉樹中有Ni個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)， ，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有()個(gè)葉子結(jié)點(diǎn)。m mm m(A)(i1)Ni(B)Ni (C)Ni (D)1(i1)Nii1 i1 i2 i2二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均()根結(jié)點(diǎn)的值。(A)< (B)> (C)= (D)!=設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為()。(A)129 (B)219 (C)189 (D)229設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這 n個(gè)關(guān)鍵字映射到HASH表中需要做()次線性探測。(A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/2設(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-111.設(shè)一組初始記錄關(guān)鍵字的長度為(A)2n(B)n+l(C)2n-111.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過((D)2n+l)趟插入排序可以得到有序序列。(A)6 (B)7 (C)812.(A)6 (B)7 (C)812.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，

的第一趟冒泡排序結(jié)束后的結(jié)果是()。(D)9P,A,M,S,R,D,F,X),則按字母升序MM，Q，R，S，Y，XF，X，R，H，M，YM，S，Y，P，H，XTOC\o"1-5"\h\zF， H， C， D， P， A，P， A， C， S， Q， D，A， D， C， R， F， Q，(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y三、算法設(shè)計(jì)題(22分)(D)設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯Y(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;}設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹上查找結(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);}.設(shè)關(guān)鍵字序列(kl, k2,…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列 (kl, k2,…，kn-1 , x)調(diào)整為堆。設(shè)關(guān)鍵字序列(kl,k2,…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列 (kl,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分，共26分）高效率正確性易讀性強(qiáng)壯性高效率O（n）TOC\o"1-5"\h\z9 3 3-1 34X*+2Y*3/-2n n-1 n+1e 2e有向無回路n（n-1）/2 n（n-1）（12，40） （ ） （74） （23,55，63）增加1O（log2n） O（nlog2n）12.歸并6分，共24分）.線性表為：（78，50，40，60，34，90）

.鄰接矩陣：0鄰接表如圖11所示:圖11.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,4.見圖(4,6)4,(1,3)5,(1,4)8,(1,2)3,4.見圖(4,6)4,(1,3)5,(1,4)8,12(2,5)10,(4,7)203trueBST->leftBST->right3trueBST->leftBST->right四、讀算法(每題7分，(1)查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(a2,a3,…，an,a〔)2.遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五、法填?每空2分，共8分)六、編寫算法(8分)1.intCountX(LNode*HL,ElemTypex)1.{inti=0;LNode*p=HL;ey==kreturn(t),t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。1+log2n。1+log2n。2、H(36)=36mod7=1;H(15)=15mod7=1;???.沖突Hi(22)=(1+1)mod7=2;??H2(22)=(2+1)mod7=3;??沖突Hi(15)=(1+1)mod7=2;2、H(36)=36mod7=1;H(15)=15mod7=1;???.沖突Hi(22)=(1+1)mod7=2;??H2(22)=(2+1)mod7=3;??沖突Hi(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突0 1 2 3 4 5 663361522403,、 1ASL=-1.63、(8,9,4,3,6,1),10,(12,1818)(1,6,4,3),8,(9),10,12,(1018)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題.設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){Iklist*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)試卷(四)參考答案一、選擇題C 2．D 3．D 4．B 5．CA 7．B 8．A 9．C 10．A二、填空題O(n2)，O(nlog2n)p>llink->rlink=p->rlink;p->rlink->llink=p->rlink3.32k-1n/250，51m-1，(R-F+M)%Mn+1-i，n-i(19，18，16，20，30，22)(16，18，19，20，32，22)A[i][j]=1等于BDCAhashtable[i]=0，hashtable[k]=s三、計(jì)算題1．LS51人110d0rbABCDEF;BDEFCA(2)ABCDEFGHIJK;BDEFCAIJKH琳轉(zhuǎn)換為相應(yīng)的二叉樹;H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H⑺=60645120645123789四、算法設(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)酱鎯Y(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)酱鎯Y(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)試卷（五）參考答案一、選擇題1．A2．B3．A4．A5．D6．B7．B8．B9．C10．C二、填空題top1+1=top2可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的簡單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，64出度，入度ki<=k2i&&ki<=k2i+1n-i，r[j+1]=r[j]mid=(low+high)/2，r[mid].key>k三、應(yīng)用題DEBCAE={(1,5),(5,2),(5,3),(3,4)},W=10

ASL=(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;}數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案1．D1．D2．A3．A4．A6．D7．B8．A9．C11．C12A13．B14D15．B二、判斷題1．錯(cuò)2．對3．對4．對對5．錯(cuò)6．錯(cuò)7．對8．錯(cuò)9．對對10．對、選擇題5．D10．B三、填空題O(n)s->next=p->next;p->next=s(1，3，2，4，5)TOC\o"1-5"\h\zn-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)酱鎯Y(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)試卷（七）參考答案、選擇題1．B6．A2．B7．C3．C8．C4．B9．B5．B10．D二、判斷題1．2．3．4．5．6．7．8．錯(cuò)9．錯(cuò)10．錯(cuò)三、填空題s->left=p，p->rightn(n-1)，n(n-1)/2n/2開放定址法，鏈地址法142s->left=p，p->rightn(n-1)，n(n-1)/2n/2開放定址法，鏈地址法142h-12h-1(12，24，35，(12，18，24，27，18，27，35，26)26)10.i<j&&r[i].key<，r[i]=x四、算法設(shè)計(jì)題設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xià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;}}}設(shè)計(jì)在順序存儲結(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->k