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

-.z.TOC\o"1-1"\h\z\u數(shù)據(jù)結(jié)構(gòu)試卷（一）1數(shù)據(jù)結(jié)構(gòu)試卷（二）4數(shù)據(jù)結(jié)構(gòu)試卷（三）6數(shù)據(jù)結(jié)構(gòu)試卷（四）8數(shù)據(jù)結(jié)構(gòu)試卷（五）11數(shù)據(jù)結(jié)構(gòu)試卷（六）14數(shù)據(jù)結(jié)構(gòu)試卷（七）16數(shù)據(jù)結(jié)構(gòu)試卷（八）18數(shù)據(jù)結(jié)構(gòu)試卷（九）20數(shù)據(jù)結(jié)構(gòu)試卷（十）23數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案26數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案27數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案28數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案30數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案32數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案33數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案36數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案37數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案38數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案39-.z.數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）棧和隊列的共同特點是(A)。A.只允許在端點處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點用方式存儲的隊列，在進(jìn)行插入運(yùn)算時(D).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？(D)A.隊列B.棧C.線性表D.二叉樹設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示（C）。A．688B．678C．692D．696樹最適合用來表示(C)。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第k層的結(jié)點數(shù)最多為(D).A．2k-1B.2K+1C.2K-1D.2k-1若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放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個記錄的文件進(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)行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個，A．1B．2C．3D．4設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有(A)條邊才能確保是一個連通圖。A.5B.6C.7D.8三、計算題（每題6分，共24分）在如下數(shù)組A中存儲了一個線性表，表頭指針為A[0].ne*t，試寫出該線性表。A01234567data605078903440ne*t3572041線性表為：（78，50，40，60，34，90）請畫出下圖的鄰接矩陣和鄰接表。已知一個圖的頂點集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)204.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。見圖1244444222552852834528434444422255285283452843圖12圖11四、閱讀算法（每題7分，共14分）LinkListmynote(LinkListL){//L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->ne*t){q=L；L=L－>ne*t；p=L；S1：while(p－>ne*t)p=p－>ne*t；S2：p－>ne*t=q；q－>ne*t=NULL；}returnL；}請回答下列問題：（1）說明語句S1的功能；查詢鏈表的尾結(jié)點（2）說明語句組S2的功能；將第一個結(jié)點到鏈表的尾部，作為新的尾結(jié)點（3）設(shè)鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為（a2,a3,…,an,a1）voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄湮?、算法填空（?分）二叉搜索樹的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return__true__;}elseif(item<BST->data)returnFind(___BST->left__,item);elsereturnFind(____BST->right__,item);}//if}六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值*的結(jié)點數(shù)。intCount*(LNode*HL,ElemType*)intCount*(LNode*HL,ElemType*){inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL){if(P->data==*)i++;p=p->ne*t;}//while,出循環(huán)時i中的值即為*結(jié)點個數(shù)returni;}//Count*數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2．設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。(A)2m-1 (B)2m (C)2m+1 (D)4m3．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。(A)R-F (B)F-R(C)(R-F+M)％M (D)(F-R+M)％M4．設(shè)*棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。(A)BADC (B)BCDA(C)CDAB (D)CBDA5．設(shè)*完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-16．設(shè)*棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（）。 (A)9 (B)10 (C)11 (D)127．設(shè)*有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點。 (A)n-1(B)n (C)n+1 (D)2n-18．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。 (A)2，3，5，8，6 (B)3，2，5，8，6(C)3，2，5，6，8 (D)2，3，6，5，8三、應(yīng)用題(36分)設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。(22，40，45，48，80，78)，(40，45，48，80，22，78)設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。2,ASL=91*1+2*2+3*4+4*2)=25/9設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題(16分)設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,*=r[s];while(i<j){while(i<j&&r[j]>*)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<*)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=*;}設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。typedefstructnode{intdata;structnode*ne*t;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->ne*t){for(q=hb;q!=0;q=q->ne*t)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->ne*t=hc;hc=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(每題1分，共20分)1．設(shè)*數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，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)樹型結(jié)構(gòu) (C)物理結(jié)構(gòu) (D)圖型結(jié)構(gòu)2．下面程序的時間復(fù)雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序列為（）。(A)q=p->ne*t；p->data=q->data；p->ne*t=q->ne*t；free(q)；(B)q=p->ne*t；q->data=p->data；p->ne*t=q->ne*t；free(q)； (C)q=p->ne*t；p->ne*t=q->ne*t；free(q)； (D)q=p->ne*t；p->data=q->data；free(q)；4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。(A)1 (B)n (C)nlog2n (D)n25．設(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，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，216．設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（）。 (A)O(1) (B)O(log2n) (C) (D)O(n2)7．設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（）。 (A)n，e (B)e，n (C)2n，e(D)n，2e8.設(shè)*強(qiáng)連通圖中有n個頂點，則該強(qiáng)連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。(A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序10.下列四種排序中（）的空間復(fù)雜度最大。(A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序三、計算題(每題10分，共30分)1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生沖突采用線性探查法處理，試：H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突（1）計算出每一個元素的散列地址并在下圖中填寫出散列表：`01234566336152240（2）求出在查找每一個元素概率相等情況下的平均查找長度。ASL=3．已知序列（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è)計題(每題15分，共30分)設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*ne*t;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->ne*t){for(q=p->ne*t,s=q;q!=0;)if(q->data==p->data){s->ne*t=q->ne*t;free(q);q=s->ne*t;}else{s=q,q=q->ne*t;}}}設(shè)計一個求結(jié)點*在二叉樹中的雙親結(jié)點算法。設(shè)計一個求結(jié)點*在二叉樹中的雙親結(jié)點算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,char*){if(bt!=0&&flag==0)if(bt->data==*){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,*);preorder(bt->rchild,*);}}voidparent(bitree*bt,char*){inti;preorder(bt,*);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==*||q[i]->rchild->data)break;if(flag==0)printf("notfound*\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題(每題1分共20分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。(A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點。 (A)2k-1 (B)2k (C)2k-1(D)2k-13．設(shè)*無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。(A)n (B)e (C)2n (D)2e4．在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（）。(A)O(1) (B)O(n)(C)O(log2n) (D)O(n2)5．設(shè)*有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）條有向邊。(A)n (B)n-1 (C)m(D)m-16．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3 (B)4(C)5(D)87．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型 (D)對棧不作任何判別8．下列四種排序中（）的空間復(fù)雜度最大。(A)快速排序 (B)冒泡排序 (C)希爾排序 (D)堆9．設(shè)*二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素*的最多比較次數(shù)不超過（）。(A)log2n+1(B)log2n-1(C)log2n (D)log2(n+1)三、計算題(每題10分，共30分)1、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林：(1)求樹（a）的先根序列和后根序列；(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹；(2)求森林先序序列和中序序列；ABCDEF;BDEFCA；（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹；3、設(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(7)=6四、算法設(shè)計題(每題10分，共30分)設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*ne*t;}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->ne*t;p->ne*t=0;if(p->data>='A'&&p->data<='Z'){p->ne*t=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->ne*t=hb;hb=p;}else{p->ne*t=hc;hc=p;}}}設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。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)試卷（五）一、選擇題(20分)1．?dāng)?shù)據(jù)的最小單位是（）。(A)數(shù)據(jù)項 (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個長度為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，854．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE”5．設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。 (A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm (C)N2+2N3+3N4+……+(m-1)Nm (D)2Nl+3N2+……+(m+1)Nm7．設(shè)有序表中有1000個元素，則用二分查找查找元素*最多需要比較（）次。 (A)25 (B)10(C)7 (D)18．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。 (A)abedfc (B)acfebd(C)aebdfc (D)aedfcb9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i (B)n-1-i (C)n+1-i(D)不能確定10設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(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分)設(shè)*棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。DEBCA設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。E={(1,5),(5,2),(5,3),(3,4)},W=10設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。ASL=(1*1+2*2+3*4)/7=17/7設(shè)散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。ASL1=7/6，ASL2=4/3四、算法設(shè)計題(28分)設(shè)計判斷兩個二叉樹是否相同的算法。設(shè)計判斷兩個二叉樹是否相同的算法。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è)計兩個有序單鏈表的合并排序算法。設(shè)計兩個有序單鏈表的合并排序算法。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->ne*t=ha;s=ha;};ha=ha->ne*t;}else{if(s==0)hc=s=hb;else{s->ne*t=hb;s=hb;};hb=hb->ne*t;}if(ha==0)s->ne*t=hb;elses->ne*t=ha;}數(shù)據(jù)結(jié)構(gòu)試卷（六）一、選擇題(30分)1．設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。 (A)20 (B)30 (C)40 (D)452．執(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]3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是（）。(A)head==0 (B)head->ne*t==0(C)head->ne*t==head (D)head!=04．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。(A)堆排序 (B)冒泡排序 (C)希爾排序 (D)快速排序5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結(jié)點 (B)高度等于其結(jié)點數(shù) (C)任一結(jié)點無左孩子 (D)任一結(jié)點無右孩子6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希爾排序7．設(shè)*棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）。 (A)3 (B)4 (C)5 (D)68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）。(A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)9．二路歸并排序的時間復(fù)雜度為（）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結(jié)點。 (A)2k-1-1(B)2k-1 (C)2k-1+1 (D)2k-111.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔?，指針變量s指向?qū)⒁腙犃械慕Y(jié)點*，則入隊列的操作序列為（）。(A)front->ne*t=s；front=s； (B)s->ne*t=rear；rear=s；(C)rear->ne*t=s；rear=s； (D)s->ne*t=front；front=s；12.設(shè)*無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。(A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)13.設(shè)*哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。 (A)99 (B)100 (C)101 (D)10214.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為（）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（）。 (A)第i行非0元素的個數(shù)之和 (B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和四、算法設(shè)計題(20分)設(shè)計在順序有序表中實現(xiàn)二分查找的算法。設(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è)計判斷二叉樹是否為二叉排序樹的算法。設(shè)計判斷二叉樹是否為二叉排序樹的算法。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è)計直接插入排序算法在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->ne*t==0)return;elsefor(q=head,p=head->ne*t;p!=0;p=q->ne*t){for(s=head;s!=q->ne*t;s=s->ne*t)if(s->data>p->data)break;if(s==q->ne*t)q=p;else{q->ne*t=p->ne*t;p->ne*t=s->ne*t;s->ne*t=p;t=p->data;p->data=s->data;s->data=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題(30分)1．設(shè)*無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結(jié)點。(A)2n (B)n (C)n/2 (D)n(n-1)2．設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。(A)n(B)n-1(C)2n(D)2n-13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(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．（）二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷 (B)中序遍歷 (C)后序遍歷 (D)層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。(A)2i+1 (B)2i(C)i/2 (D)2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n) (C)O(n2)(D)O(n3/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。(A)head==0(B)head->ne*t==0(C)head->ne*t==head(D)head!=08．設(shè)*棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。 (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)鍵字個數(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->ne*t=top; (D)top=top->ne*t;四、算法設(shè)計題(20分)設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->ne*t==0)return;for(q=head;q!=0;q=q->ne*t){min=q->data;s=q;for(p=q->ne*t;p!=0;p=p->ne*t)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}設(shè)計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。設(shè)計在順序存儲結(jié)構(gòu)上實現(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è)計求結(jié)點在二叉排序樹中層次的算法。設(shè)計求結(jié)點在二叉排序樹中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,int*){if(bt!=0){lev++;if(bt->key==*)return;elseif(bt->key>*)level(bt->lchild,*);elselevel(bt->rchild,*);}}數(shù)據(jù)結(jié)構(gòu)試卷（八）一、選擇題(30分)字符串的長度是指（）。(A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù)(C)串中所含字符的個數(shù) (D)串中不同數(shù)字的個數(shù)建立一個長度為n的有序單鏈表的時間復(fù)雜度為（）(A)O(n) (B)O(1) (C)O(n2) (D)O(log2n)兩個字符串相等的充要條件是（）。 (A)兩個字符串的長度相等 (B)兩個字符串中對應(yīng)位置上的字符相等(C)同時具備(A)和(B)兩個條件 (D)以上答案都不對設(shè)*散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（）。 (A)99 (B)97 (C)91 (D)93在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）。 (A)O(n) (B)O(1og2n)(C)O(nlog2n)(D)O(n2)設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。 (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個結(jié)點，則該完全二叉樹的深度為（）。 (A)8 (B)7 (C)6 (D)5設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點，2個度數(shù)為2的結(jié)點，2個度數(shù)為3的結(jié)點，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點。 (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)}，則從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點序列為（）。(A)aedfcb (B)acfebd(C)aebcfd (D)aedfbc隊列是一種（）的線性表。(A)先進(jìn)先出 (B)先進(jìn)后出 (C)只能插入 (D)只能刪除四、算法設(shè)計題(20分)設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。typedefstruct{intverte*[m];intedge[m][m];}gadjmatri*;typedefstructnode1{intinfo;intadjverte*;structnode1*ne*tarc;}glinklistnode;typedefstructnode2{intverte*info;glinklistnode*firstarc;}glinkheadnode;voidadjmatri*toadjlist(gadjmatri*g1[],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->adjverte*=j;p->ne*tarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjverte*=i;p->ne*tarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結(jié)構(gòu)試卷（九）一、選擇題(30分)1．下列程序段的時間復(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個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（）個元素。(A)n-i (B)n+l-i (C)n-1-i (D)i3．設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為（）。(A)N1-1 (B)N2-1 (C)N2+N3 (D)N1+N34．利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為（）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(1og2n)5．設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點*，則在結(jié)點A的后面插入結(jié)點*的操作序列為（）。(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．下列各種排序算法中平均時間復(fù)雜度為O(n2)是（）。 (A)快速排序 (B)堆排序(C)歸并排序(D)冒泡排序7．設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（）。 (A)n-i (B)n-1-i (C)n+l-i (D)不能確定8．設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。 (A)小于等于m的最大奇數(shù) (B)小于等于m的最大素數(shù) (C)小于等于m的最大偶數(shù) (D)小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，則度數(shù)為0的結(jié)點數(shù)有（）個。 (A)4 (B)5 (C)6 (D)710.設(shè)完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/211.設(shè)順序表的長度為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)過（）次比較。 (A)1 (B)2 (C)3 (D)413.設(shè)順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。 (A)6 (B)11 (C)5 (D)6.514.設(shè)有向無環(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)鍵字生成的二叉排序樹的深度為（）。(A)4 (B)5 (C)6 (D)7五、算法設(shè)計題(20分)設(shè)計計算二叉樹中所有結(jié)點值之和的算法。設(shè)計計算二叉樹中所有結(jié)點值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,*=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]=*;}設(shè)計判斷單鏈表中元素是否是遞增的算法。設(shè)計判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head){if(head==0||head->ne*t==0)return(1);elsefor(q=head,p=head->ne*t;p!=0;q=p,p=p->ne*t)if(q->data>p->data)return(0);return(1);}數(shù)據(jù)結(jié)構(gòu)試卷（十）一、選擇題(24分)1．下列程序段的時間復(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è)*鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）存儲方式最節(jié)省運(yùn)算時間。 (A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點*，則在結(jié)點A和結(jié)點B插入結(jié)點*的操作序列為（）。(A)s->ne*t=p->ne*t；p->ne*t=-s； (B)q->ne*t=s；s->ne*t=p；(C)p->ne*t=s->ne*t；s->ne*t=p； (D)p->ne*t=s；s->ne*t=q；4．設(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，35．設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（）。 (A)10 (B)19 (C)28 (D)556．設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，……，Nm個度數(shù)為m的結(jié)點，則該樹中共有（）個葉子結(jié)點。 (A) (B) (C)(D)7.二叉排序樹中左子樹上所有結(jié)點的值均（）根結(jié)點的值。(A)< (B)> (C)= (D)!=8.設(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)2299.設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（）次線性探測。 (A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/210.設(shè)*棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（）個結(jié)點。 (A)2n (B)n+l (C)2n-1 (D)2n+l11.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。(A)6(B)7(C)8(D)912.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，*)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。(A)F，H，C，D，P，A，M，Q，R，S，Y，*(B)P，A，C，S，Q，D，F(xiàn)，*，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，*(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，*，Y三、算法設(shè)計題(22分)設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。設(shè)計在鏈?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->ne*t=ha;s=ha;};ha=ha->ne*t;}else{if(s==0)hc=s=hb;else{s->ne*t=hb;s=hb;};hb=hb->ne*t;}if(ha==0)s->ne*t=hb;elses->ne*t=ha;}設(shè)計在二叉排序樹上查找結(jié)點*的算法。設(shè)計在二叉排序樹上查找結(jié)點*的算法。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)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，*)調(diào)整為堆。設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，*)調(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.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空題（每空1分，共26分）正確性易讀性強(qiáng)壯性高效率O(n)933-134**+2Y*3/-2nn-1n+1e2e有向無回路n(n-1)/2n(n-1)（12，40）（）（74）（23,55，63）增加1O(log2n)O(nlog2n)歸并三、計算題（每題6分，共24分）線性表為：（78，50，40，60，34，90）鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20見圖1244444222552852834528434444422255285283452843圖12讀算法（每題7分，共14分）（1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點到鏈表的尾部，作為新的尾結(jié)點（3）返回的線性表為（a2,a3,…,an,a1）遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。法填空（每?分，共8分）trueBST->leftBST->right編寫算法（8分）intCount*(LNode*HL,ElemType*){inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL){if(P->data==*)i++;p=p->ne*t;}//while,出循環(huán)時i中的值即為*結(jié)點個數(shù)returni;}//Count*數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二、填空題構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法stack.top++，stack.s[stack.top]=*有序O(n2)，O(nlog2n)N0-1，2N0+N1d/2(31，38，54，56，75，80，55，63)(1，3，4，5，2)，(1，3，2，4，5)三、應(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)酱鎯Y(jié)構(gòu)略，二叉樹略E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}略四、算法設(shè)計題設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,*=r[s];while(i<j){while(i<j&&r[j]>*)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<*)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=*;}設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。typedefstructnode{intdata;structnode*ne*t;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->ne*t){for(q=hb;q!=0;q=q->ne*t)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->ne*t=hc;hc=t;}}}數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題1.B 2.B 3.A 4.A 5.A6.B 7.D 8.C 9.B 10.D第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。二、填空題順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)9，5015出度，入度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)行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。三、計算題1．2、H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突（1）01234566336152240（2）ASL=3、(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è)計題設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*ne*t;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->ne*t){for(q=p->ne*t,s=q;q!=0;)if(q->data==p->data){s->ne*t=q->ne*t;free(q);q=s->ne*t;}else{s=q,q=q->ne*t;}}}設(shè)計一個求結(jié)點*在二叉樹中的雙親結(jié)點算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,char*){if(bt!=0&&flag==0)if(bt->data==*){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,*);preorder(bt->rchild,*);}}voidparent(bitree*bt,char*){inti;preorder(bt,*);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==*||q[i]->rchild->data)break;if(flag==0)printf("notfound*\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案一、選擇題1．C 2．D 3．D 4．B 5．C6．A 7．B 8．A 9．C 10．A二、填空題O(n2)，O(nlog2n)p>llink->rlink=p->rlink;p->rlink->llink=p->rlink32k-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三、計算題1．2．(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹；3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設(shè)計題設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*ne*t;}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->ne*t;p->ne*t=0;if(p->data>='A'&&p->d