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

./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.數(shù)據(jù)結(jié)構(gòu)試卷〔一一、單選題〔每題2分,共20分棧和隊(duì)列的共同特點(diǎn)是<A>。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)用鏈接方式存儲(chǔ)的隊(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.二叉樹(shù)設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在644<10>,A[2][2]存放位置在676<10>,每個(gè)元素占一個(gè)空間,問(wèn)A[3][3]<10>存放在什么位置？腳注<10>表示用10進(jìn)制表示〔C。A．688B．678C．692D．696樹(shù)最適合用來(lái)表示<C>。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為<D>.A．2k-1B.2K+1C.2K-1D.2k-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對(duì)n個(gè)記錄的文件進(jìn)行快速排序,所需要的輔助存儲(chǔ)空間大致為〔CA.O〔1B.O〔nC.O〔1og2nD.O〔n2對(duì)于線性表〔7,34,55,25,64,46,20,10進(jìn)行散列存儲(chǔ)時(shí),若選用H〔K=K%9作為散列函數(shù),則散列地址為1的元素有〔D個(gè),A．1B．2C．3D．4設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖,該圖至少應(yīng)有<A>條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8三、計(jì)算題〔每題6分,共24分在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表,表頭指針為A[0].next,試寫(xiě)出該線性表。A01234567data605078903440next3572041線性表為：〔78,50,40,60,34,90請(qǐng)畫(huà)出下圖的鄰接矩陣和鄰接表。已知一個(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};用克魯斯卡爾算法得到最小生成樹(shù),試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。用克魯斯卡爾算法得到的最小生成樹(shù)為：<1,2>3,<4,6>4,<1,3>5,<1,4>8,<2,5>10,<4,7>204.畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí),每加入一個(gè)數(shù)據(jù)后堆的變化。見(jiàn)圖1244444222552852834528434444422255285283452843圖12圖11四、閱讀算法〔每題7分,共14分LinkListmynote<LinkListL>{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if<L&&L->next>{q=L；L=L－>next；p=L；S1：while<p－>next>p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}請(qǐng)回答下列問(wèn)題：〔1說(shuō)明語(yǔ)句S1的功能；查詢鏈表的尾結(jié)點(diǎn)〔2說(shuō)明語(yǔ)句組S2的功能；將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部,作為新的尾結(jié)點(diǎn)〔3設(shè)鏈表表示的線性表為〔a1,a2,…,an,寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。返回的線性表為〔a2,a3,…,an,a1voidABC<BTNode*BT>{ifBT{ABC<BT->left>;ABC<BT->right>;cout<<BT->data<<'';}}該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)五、算法填空〔共8分二叉搜索樹(shù)的查找——遞歸算法: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}六、編寫(xiě)算法〔共8分統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX<LNode*HL,ElemTypex>intCountX<LNode*HL,ElemTypex>{inti=0;LNode*p=HL;//i為計(jì)數(shù)器while<p!=NULL>{if<P->data==x>i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷〔二一、選擇題<24分>1．下面關(guān)于線性表的敘述錯(cuò)誤的是〔。<A>線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 <B>線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間<C>線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)<D>線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2．設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu),則該哈夫曼樹(shù)中總共有〔個(gè)空指針域。<A>2m-1 <B>2m <C>2m+1 <D>4m3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針?lè)謩e為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>％M4．設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹(shù)得到序列為〔。<A>BADC<B>BCDA<C>CDAB <D>CBDA5．設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn),則該完全無(wú)向圖中有〔條邊。<A>n<n-1>/2 <B>n<n-1> <C>n2 <D>n2-16．設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn),則該二叉樹(shù)的最小高度為〔。 <A>9 <B>10 <C>11 <D>127．設(shè)某有向圖中有n個(gè)頂點(diǎn),則該有向圖對(duì)應(yīng)的鄰接表中有〔個(gè)表頭結(jié)點(diǎn)。 <A>n-1<B>n <C>n+1 <D>2n-18．設(shè)一組初始記錄關(guān)鍵字序列<5,2,6,3,8>,以第一個(gè)記錄關(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趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。<22,40,45,48,80,78>,<40,45,48,80,22,78>設(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。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>,查找方法用二分查找,要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。2,ASL=91*1+2*2+3*4+4*2>=25/9設(shè)一棵樹(shù)T中邊的集合為{<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>},要求用孩子兄弟表示法〔二叉鏈表表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略,二叉樹(shù)略設(shè)有無(wú)向圖G,要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。E={<1,3>,<1,2>,<3,5>,<5,6>,<6,4>}設(shè)有一組初始記錄關(guān)鍵字為<45,80,48,40,22,78>,要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。四、算法設(shè)計(jì)題<16分>設(shè)有一組初始記錄關(guān)鍵字序列〔K1,K2,…,Kn,要求設(shè)計(jì)一個(gè)算法能夠在O<n>的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。設(shè)有一組初始記錄關(guān)鍵字序列〔K1,K2,…,Kn,要求設(shè)計(jì)一個(gè)算法能夠在O<n>的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass<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=A∩B的算法,其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=A∩B的算法,其中集合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)試卷〔三一、選擇題<每題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>樹(shù)型結(jié)構(gòu) <C>物理結(jié)構(gòu) <D>圖型結(jié)構(gòu)2．下面程序的時(shí)間復(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é)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列為〔。<A>q=p->next；p->data=q->data；p->next=q->next；free<q>；<B>q=p->next；q->data=p->data；p->next=q->next；free<q>；<C>q=p->next；p->next=q->next；free<q>； <D>q=p->next；p->data=q->data；free<q>；4．設(shè)有n個(gè)待排序的記錄關(guān)鍵字,則在堆排序中需要〔個(gè)輔助記錄單元。<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è)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn),則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為〔。 <A>O<1> <B>O<log2n> <C> <D>O<n2>7．設(shè)無(wú)向圖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,2e8.設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn),則該強(qiáng)連通圖中至少有〔條邊。 <A>n<n-1><B>n+1<C>n<D>n<n+1>9．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字,則用下列〔方法可以達(dá)到此目的。<A>快速排序 <B>堆排序 <C>歸并排序 <D>插入排序10.下列四種排序中〔的空間復(fù)雜度最大。<A>插入排序 <B>冒泡排序 <C>堆排序 <D>歸并排序三、計(jì)算題<每題10分,共30分>1.已知二叉樹(shù)的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫(huà)出此二叉樹(shù),并畫(huà)出它的后序線索二叉樹(shù)。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計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫(xiě)出散列表：`01234566336152240〔2求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。ASL=3．已知序列〔10,18,4,3,6,12,1,9,18,8請(qǐng)用快速排序?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在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(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分>1．設(shè)一維數(shù)組中有n個(gè)數(shù)組元素,則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為〔。<A>O<n> <B>O<nlog2n> <C>O<1> <D>O<n2>2．設(shè)一棵二叉樹(shù)的深度為k,則該二叉樹(shù)中最多有〔個(gè)結(jié)點(diǎn)。 <A>2k-1 <B>2k <C>2k-1<D>2k-13．設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則該無(wú)向圖中所有頂點(diǎn)的入度之和為〔。<A>n <B>e <C>2n <D>2e4．在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為〔。<A>O<1> <B>O<n><C>O<log2n> <D>O<n2>5．設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn),則該圖中有〔條有向邊。<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è)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作〔。 <A>必須判別棧是否為滿<B>必須判別棧是否為空 <C>判別棧元素的類型 <D>對(duì)棧不作任何判別8．下列四種排序中〔的空間復(fù)雜度最大。<A>快速排序 <B>冒泡排序 <C>希爾排序 <D>堆9．設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,則下列等式成立的是〔。<A>N0=N1+1<B>N0=Nl+N2<C>N0=N2+1<D>N0=2N1+l10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)〔。<A>log2n+1<B>log2n-1<C>log2n <D>log2<n+1>三、計(jì)算題<每題10分,共30分>1、畫(huà)出廣義表LS=<<>,<e>,<a,<b,c,d>>>的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。2、下圖所示的森林：<1>求樹(shù)〔a的先根序列和后根序列；<1>ABCDEF;BDEFCA；<2>ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；<2>求森林先序序列和中序序列；ABCDEF;BDEFCA；〔3將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；<2>ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；3、設(shè)散列表的地址范圍是[0..9],散列函數(shù)為H〔key=〔key2+2MOD9,并采用鏈表處理沖突,請(qǐng)畫(huà)出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。H<4>=H<5>=0,H<3>=H<6>=H<9>=2,H<8>=3,H<2>=H<7>=6四、算法設(shè)計(jì)題<每題10分,共30分>設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素<大寫(xiě)字母、數(shù)字和其它字符>,要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法,使每個(gè)單鏈表只包含同類字符。設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素<大寫(xiě)字母、數(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)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。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)上建立一棵二叉排序樹(shù)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。#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ù)項(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,854．函數(shù)substr<"DATASTRUCTURE",5,9>的返回值為〔。 <A>"STRUCTURE"<B>"DATA" <C>"ASTRUCTUR" <D>"DATASTRUCTURE"5．設(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>6．設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl,……,度數(shù)為m的結(jié)點(diǎn)數(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個(gè)元素,則用二分查找查找元素X最多需要比較〔次。 <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>},則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為〔。 <A>abedfc <B>acfebd<C>aebdfc <D>aedfcb9．設(shè)輸入序列是1、2、3、……、n,經(jīng)過(guò)棧的作用后輸出序列的第一個(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分>設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹(shù)的的后序遍歷序列。DEBCA設(shè)無(wú)向圖G〔如右圖所示,給出該圖的最小生成樹(shù)上邊的集合并計(jì)算最小生成樹(shù)各邊上的權(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í)的平均查找長(zhǎng)度。ASL=<1*1+2*2+3*4>/7=17/7設(shè)散列表的長(zhǎng)度為8,散列函數(shù)H<k>=kmod7,初始記錄關(guān)鍵字序列為<25,31,8,27,13,68>,要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。ASL1=7/6,ASL2=4/3四、算法設(shè)計(jì)題<28分>設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。設(shè)計(jì)判斷兩個(gè)二叉樹(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è)計(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)試卷〔六一、選擇題<30分>1．設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為〔。 <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且該鏈表沒(méi)有頭結(jié)點(diǎn),則其判空條件是〔。<A>head==0 <B>head->next==0<C>head->next==head <D>head!=04．時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O<nlog2n>的是〔。<A>堆排序 <B>冒泡排序 <C>希爾排序 <D>快速排序5．設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹(shù)滿足的條件是〔。 <A>空或只有一個(gè)結(jié)點(diǎn) <B>高度等于其結(jié)點(diǎn)數(shù) <C>任一結(jié)點(diǎn)無(wú)左孩子 <D>任一結(jié)點(diǎn)無(wú)右孩子6．一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是〔。 <A>堆排序 <B>冒泡排序 <C>快速排序 <D>希爾排序7．設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn),則該三叉樹(shù)的最小高度為〔。 <A>3 <B>4 <C>5 <D>68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為〔。<A>O<n> <B>O<n2> <C>O<n1/2> <D>O<1og2n>9．二路歸并排序的時(shí)間復(fù)雜度為〔。 <A>O<n> <B>O<n2> <C>O<nlog2n> <D>O<1og2n>10.深度為k的完全二叉樹(shù)中最少有〔個(gè)結(jié)點(diǎn)。 <A>2k-1-1<B>2k-1 <C>2k-1+1 <D>2k-111.設(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； <B>s->next=rear；rear=s；<C>rear->next=s；rear=s； <D>s->next=front；front=s；12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則建立該圖鄰接表的時(shí)間復(fù)雜度為〔。<A>O<n+e> <B>O<n2> <C>O<ne> <D>O<n3>13.設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn),則該哈夫曼樹(shù)中有〔個(gè)葉子結(jié)點(diǎn)。 <A>99 <B>100 <C>101 <D>10214.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn),則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為〔。 <A>O<n> <B>O<n2> <C>O<nlog2n> <D>O<1og2n>15.設(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ù)之和四、算法設(shè)計(jì)題<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ù)是否為二叉排序樹(shù)的算法。設(shè)計(jì)判斷二叉樹(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)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法在鏈?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è)某無(wú)向圖有n個(gè)頂點(diǎn),則該無(wú)向圖的鄰接表中有〔個(gè)表頭結(jié)點(diǎn)。<A>2n <B>n <C>n/2 <D>n<n-1>2．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn),則該無(wú)向圖的最小生成樹(shù)上有〔條邊。<A>n<B>n-1<C>2n<D>2n-13．設(shè)一組初始記錄關(guān)鍵字序列為<60,80,55,40,42,85>,則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是〔。 <A>40,42,60,55,80,85 <B>42,45,55,60,85,80<C>42,40,55,60,80,85 <D>42,40,60,85,55,804．〔二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。<A>先序遍歷 <B>中序遍歷 <C>后序遍歷 <D>層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào),則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為〔。<A>2i+1 <B>2i<C>i/2 <D>2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while<i<=n>；的時(shí)間復(fù)雜度為〔。<A>O<n><B>O<nlog2n> <C>O<n2><D>O<n3/2>7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是〔。<A>head==0<B>head->next==0<C>head->next==head<D>head!=08．設(shè)某棵二叉樹(shù)的高度為10,則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有〔。 <A>20 <B>256 <C>512 <D>10249．設(shè)一組初始記錄關(guān)鍵字序列為<13,18,24,35,47,50,62,83,90,115,134>,則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為〔。<A>1<B>2 <C>3 <D>410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元素的操作序列為〔。<A>top=top+1; <B>top=top-1;<C>top->next=top; <D>top=top->next;四、算法設(shè)計(jì)題<20分>設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。設(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;}}}設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(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)在二叉排序樹(shù)中層次的算法。設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel<bitree*bt,intx>{if<bt!=0>{lev++;if<bt->key==x>return;elseif<bt->key>x>level<bt->lchild,x>;elselevel<bt->rchild,x>;}}數(shù)據(jù)結(jié)構(gòu)試卷〔八一、選擇題<30分>字符串的長(zhǎng)度是指〔。<A>串中不同字符的個(gè)數(shù)<B>串中不同字母的個(gè)數(shù)<C>串中所含字符的個(gè)數(shù) <D>串中不同數(shù)字的個(gè)數(shù)建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為〔<A>O<n> <B>O<1> <C>O<n2> <D>O<log2n>兩個(gè)字符串相等的充要條件是〔。 <A>兩個(gè)字符串的長(zhǎng)度相等 <B>兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等<C>同時(shí)具備<A>和<B>兩個(gè)條件 <D>以上答案都不對(duì)設(shè)某散列表的長(zhǎng)度為100,散列函數(shù)H<k>=k%P,則P通常情況下最好選擇〔。 <A>99 <B>97 <C>91 <D>93在二叉排序樹(shù)中插入一個(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]的過(guò)程中比較元素的順序?yàn)?lt;>。 <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è)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn),則該完全二叉樹(shù)的深度為〔。 <A>8 <B>7 <C>6 <D>5設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn),2個(gè)度數(shù)為2的結(jié)點(diǎn),2個(gè)度數(shù)為3的結(jié)點(diǎn),則該三叉鏈權(quán)中有〔個(gè)度數(shù)為0的結(jié)點(diǎn)。 <A>5 <B>6 <C>7 <D>8設(shè)無(wú)向圖G中的邊的集合E={<a,b>,<a,e>,<a,c>,<b,e>,<e,d>,<d,f>,<f,c>},則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為〔。<A>aedfcb <B>acfebd<C>aebcfd <D>aedfbc隊(duì)列是一種〔的線性表。<A>先進(jìn)先出 <B>先進(jìn)后出 <C>只能插入 <D>只能刪除四、算法設(shè)計(jì)題<20分>設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode<bitree*bt,int&count>{if<bt!=0>{count++;countnode<bt->lchild,count>;countnode<bt->rchild,count>;}}設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist<gadjmatrixg1[],glinkheadnodeg2[]>{inti,j;glinklistnode*p;for<i=0;i<=n-1;i++>g2[i].firstarc=0;for<i=0;i<=n-1;i++>for<j=0;j<=n-1;j++>if<g1.edge[i][j]==1>{p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結(jié)構(gòu)試卷〔九一、選擇題<30分>1．下列程序段的時(shí)間復(fù)雜度為〔。for<i=0；i<m；i++>for<j=0；j<t；j++>c[i][j]=0；for<i=0；i<m；i++>for<j=0；j<t；j++>for<k=0；k<n；k++>c[i][j]=c[i][j]+a[i][k]*b[k][j]；<A>O<m*n*t> <B>O<m+n+t> <C>O<m+n*t> <D>O<m*t+n>2．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素,則刪除表中第i個(gè)元素需要移動(dòng)〔個(gè)元素。<A>n-i <B>n+l-i <C>n-1-i <D>i3．設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林,與F對(duì)應(yīng)的二叉樹(shù)為B,T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3,則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為〔。<A>N1-1 <B>N2-1 <C>N2+N3 <D>N1+N34．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為〔。<A>O<n> <B>O<nlog2n> <C>O<n2> <D>O<1og2n>5．設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為〔。<A>p->right=s；s->left=p；p->right->left=s；s->right=p->right；<B>s->left=p；s->right=p->right；p->right=s；p->right->left=s；<C>p->right=s；p->right->left=s；s->left=p；s->right=p->right；<D>s->left=p；s->right=p->right；p->right->left=s；p->right=s；6．下列各種排序算法中平均時(shí)間復(fù)雜度為O<n2>是〔。 <A>快速排序 <B>堆排序<C>歸并排序<D>冒泡排序7．設(shè)輸入序列1、2、3、…、n經(jīng)過(guò)棧作用后,輸出序列中的第一個(gè)元素是n,則輸出序列中的第i個(gè)輸出元素是〔。 <A>n-i <B>n-1-i <C>n+l-i <D>不能確定8．設(shè)散列表中有m個(gè)存儲(chǔ)單元,散列函數(shù)H<key>=key%p,則p最好選擇〔。 <A>小于等于m的最大奇數(shù)<B>小于等于m的最大素?cái)?shù) <C>小于等于m的最大偶數(shù) <D>小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹(shù)中,度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè),度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè),度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè),那么度數(shù)為0的結(jié)點(diǎn)數(shù)有〔個(gè)。 <A>4 <B>5 <C>6 <D>710.設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn),則該完全無(wú)向圖中有〔條邊。<A>n<n-1>/2 <B>n<n-1> <C>n<n+1>/2 <D><n-1>/211.設(shè)順序表的長(zhǎng)度為n,則順序查找的平均比較次數(shù)為〔。 <A>n <B>n/2 <C><n+1>/2 <D><n-1>/212.設(shè)有序表中的元素為<13,18,24,35,47,50,62>,則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)〔次比較。 <A>1 <B>2 <C>3 <D>413.設(shè)順序線性表的長(zhǎng)度為30,分成5塊,每塊6個(gè)元素,如果采用分塊查找,則其平均查找長(zhǎng)度為〔。 <A>6 <B>11 <C>5 <D>6.514.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖恰病?lt;A>1,2,3,4 <B>2,3,4,1 <C>1,4,2,3 <D>1,2,4,315.設(shè)有一組初始記錄關(guān)鍵字序列為<34,76,45,18,26,54,92>,則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為〔。<A>4 <B>5 <C>6 <D>7五、算法設(shè)計(jì)題<20分>設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。voidsum<bitree*bt,int&s>{if<bt!=0>{s=s+bt->data;sum<bt->lchild,s>;sum<bt->rchild,s>;} }設(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>;}數(shù)據(jù)結(jié)構(gòu)試卷〔十一、選擇題<24分>1．下列程序段的時(shí)間復(fù)雜度為〔。i=0,s=0；while<s<n>{s=s+i；i++；}<A>O<n1/2><B>O<n1/3><C>O<n><D>O<n2>2．設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素,則選用下列〔存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 <A>單向鏈表 <B>單向循環(huán)鏈表<C>雙向鏈表 <D>雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為〔。<A>s->next=p->next；p->next=-s； <B>q->next=s；s->next=p；<C>p->next=s->next；s->next=p； <D>p->next=s；s->next=q；4．設(shè)輸入序列為1、2、3、4、5、6,則通過(guò)棧的作用后可以得到的輸出序列為〔。<A>5,3,4,6,1,2 <B>3,2,5,6,4,1<C>3,1,2,5,4,6 <D>1,5,4,6,2,35．設(shè)有一個(gè)10階的下三角矩陣A〔包括對(duì)角線,按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中,每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間,則A[5][4]地址與A[0][0]的地址之差為〔。 <A>10 <B>19 <C>28 <D>556．設(shè)一棵m叉樹(shù)中有N1個(gè)度數(shù)為1的結(jié)點(diǎn),N2個(gè)度數(shù)為2的結(jié)點(diǎn),……,Nm個(gè)度數(shù)為m的結(jié)點(diǎn),則該樹(shù)中共有〔個(gè)葉子結(jié)點(diǎn)。 <A> <B> <C><D>7.二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均〔根結(jié)點(diǎn)的值。<A>< <B>> <C>= <D>!=8.設(shè)一組權(quán)值集合W=<15,3,14,2,6,9,16,17>,要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹(shù),則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為〔。 <A>129 <B>219 <C>189 <D>2299.設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值,則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做〔次線性探測(cè)。 <A>n2 <B>n<n+1> <C>n<n+1>/2 <D>n<n-1>/210.設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n,則這棵二叉中共有〔個(gè)結(jié)點(diǎn)。 <A>2n <B>n+l <C>2n-1 <D>2n+l11.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8,則最多經(jīng)過(guò)〔趟插入排序可以得到有序序列。<A>6<B>7<C>8<D>912.設(shè)一組初始記錄關(guān)鍵字序列為<Q,H,C,Y,P,A,M,S,R,D,F,X>,則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是〔。<A>F,H,C,D,P,A,M,Q,R,S,Y,X<B>P,A,C,S,Q,D,F,X,R,H,M,Y<C>A,D,C,R,F,Q,M,S,Y,P,H,X<D>H,C,Q,P,A,M,S,R,D,F,X,Y三、算法設(shè)計(jì)題<22分>設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。voidmergelklist<lklist*ha,lklist*hb,lklist*&hc>{lklist*s=hc=0;while<ha!=0&&hb!=0>if<ha->data<hb->data>{if<s==0>hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if<s==0>hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if<ha==0>s->next=hb;elses->next=ha;}設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。bitree*bstsearch1<bitree*t,intkey>{bitree*p=t;while<p!=0>if<p->key==key>return<p>;elseif<p->key>key>p=p->lchild;elsep=p->rchild;return<0>;}設(shè)關(guān)鍵字序列<k1,k2,…,kn-1>是堆,設(shè)計(jì)算法將關(guān)鍵字序列<k1,k2,…,kn-1,x>調(diào)整為堆。設(shè)關(guān)鍵字序列<k1,k2,…,kn-1>是堆,設(shè)計(jì)算法將關(guān)鍵字序列<k1,k2,…,kn-1,x>調(diào)整為堆。voidadjustheap<intr[],intn>{intj=n,i=j/2,temp=r[j-1];while<i>=1>if<temp>=r[i-1]>break;else{r[j-1]=r[i-1];j=i;i=i/2;}r[j-1]=temp;}數(shù)據(jù)結(jié)構(gòu)試卷〔一參考答案選擇題〔每題2分,共20分1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空題〔每空1分,共26分正確性易讀性強(qiáng)壯性高效率O<n>933-134X*+2Y*3/-2nn-1n+1e2e有向無(wú)回路n<n-1>/2n<n-1>〔12,40〔〔74〔23,55,63增加1O<log2n>O<nlog2n>歸并三、計(jì)算題〔每題6分,共24分線性表為：〔78,50,40,60,34,90鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹(shù)為：<1,2>3,<4,6>4,<1,3>5,<1,4>8,<2,5>10,<4,7>20見(jiàn)圖1244444222552852834528434444422255285283452843圖12讀算法〔每題7分,共14分〔1查詢鏈表的尾結(jié)點(diǎn)〔2將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部,作為新的尾結(jié)點(diǎn)〔3返回的線性表為〔a2,a3,…,an,a1遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。法填空〔每空2分,共8分trueBST->leftBST->right編寫(xiě)算法〔8分intCountX<LNode*HL,ElemTypex>{inti=0;LNode*p=HL;//i為計(jì)數(shù)器while<p!=NULL>{if<P->data==x>i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷〔二參考答案一、選擇題1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二、填空題構(gòu)造一個(gè)好的HASH函數(shù),確定解決沖突的方法stack.top++,stack.s[stack.top]=x有序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樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略,二叉樹(shù)略E={<1,3>,<1,2>,<3,5>,<5,6>,<6,4>}略四、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列〔K1,K2,…,Kn,要求設(shè)計(jì)一個(gè)算法能夠在O<n>的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個(gè)關(guān)鍵字均小于Ki,右半部分的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass<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=A∩B的算法,其中集合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)試卷〔三參考答案一、選擇題1.B 2.B 3.A 4.A 5.A6.B 7.D 8.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,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小題分析：二分查找的過(guò)程可以用一棵二叉樹(shù)來(lái)描述,該二叉樹(shù)稱為二叉判定樹(shù)。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹(shù)的高度1+log2n。三、計(jì)算題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;….沖突〔101234566336152240〔2ASL=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è)計(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在二叉樹(shù)中的雙親結(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||