數(shù)據(jù)結(jié)構(gòu)試題AVIP

數(shù)據(jù)結(jié)構(gòu)試題A數(shù)據(jù)結(jié)構(gòu)試題A數(shù)據(jù)結(jié)構(gòu)試題A資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)試題A版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：一、單項選擇題（在每小題的4個備選答案中，選出1個正確的答案，并將其號碼填在題干的括號內(nèi)。每小題2分，共30分）若某線性表中最常用的操作是取第I個元素和找第I個元素的前趨元素，則采用（）存儲方式最節(jié)省時間。A)單鏈表 B)雙鏈表 C)單向循環(huán)鏈表 D)順序表2．串是任意有限個（） A)符號構(gòu)成的序列 B)符號構(gòu)成的集合 C)字符構(gòu)成的序列 D)字符構(gòu)成的集合3．設(shè)矩陣A的任一元素滿足： 現(xiàn)將A的所有非0元素以行序為主序存放在首地址為2000的存儲區(qū)域中，每個元素占有4個單元，則元素A[9,5]的首地址為（）。 A)2340 B)2336 C)2164 D)21604．如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時（） A)必須判別棧是否滿 B)對棧不作任何判別 C)必須判別棧是否空 D)判別棧元素的類型5．設(shè)數(shù)組Data[0..m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（） A)front=front+1 B)front=(front+1)%m C)rear=(rear+1)%m D)front=(front+1)%(m+1)6．深度為6（根的層次為1）的二叉樹至多有（）結(jié)點。 A)64 B)32 C)31 D)637．將含100個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1。則編號為49的結(jié)點X的雙親的編號為（）。 A)24 B)25 C)23 D)無法確定8．設(shè)有一個無向圖G=(V,E)和G’=(V’,E’)，如果G;G的生成樹，則下面不正確的說法是（）。 A)G’為G的子圖 B)G’為G的連通分量 C)G’為G的極小連通子圖且V’=V D)G’為G的一個無環(huán)子圖9．下列序列中，()是執(zhí)行第一趟快速排序后得到的序列。(排序的關(guān)鍵字類型是字符串)A)[da，ax，eb，cd，bb]ff[ha，gc]B)[ge，ax，eb，cd，bb]ff[da，ha]C)[cd，eb，ax，da]ff[ha，gc，bb]D)[ax，bb，cd．da]ff[eb，gc，ha]10．二分查找要求被查找的表是()。A)鍵值有序的鏈接表B)鏈接表但鍵值不一定有序C)鍵值有序的順序表D)順序表但鍵值不一定有序11．當初始序列已經(jīng)按鍵值有序，用直接插入算法對其進行排序，需要循環(huán)的次數(shù)為()。A)n2B)nlog2nc)log2nD)n-112．堆是一個鍵值序列(k1，k2，…，kn)，對i=1，2，…，，滿足()。A)ki≤k2i≤k2i+1B)ki<k2i+1<k2iC)ki≤k2i且ki≤k2i+1(2i+l≤n)D)ki≤k2i或ki≤k2i+1(2i+1≤n)13．使用雙向鏈表存儲數(shù)據(jù)，其優(yōu)點是可以()。A)提高檢索速度B)很方便地插入和刪除數(shù)據(jù)C)節(jié)約存儲空間D)很快回收存儲空間14．設(shè)計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。A)線性表的順序存儲結(jié)構(gòu)B)棧C)隊列D)線性表的鏈式存儲結(jié)構(gòu)15．設(shè)高度為k的二叉樹上只有度為0和2的結(jié)點，則此類二叉樹中所含的結(jié)點數(shù)至少為()。A)k+lB)2kC)2k-1D)2k+1二、填空題(每空2分，共28分)1．設(shè)r指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入s所指的結(jié)點，需執(zhí)行的三條語句是r=s；r->next=NULL。2．在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是。3．設(shè)一個鏈棧的棧頂指針是ls，棧中結(jié)點格式為，?？盏臈l件是____________。如果棧不為空，則退棧操作為p=ls；；free(p)。4．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有個葉子結(jié)點。5．樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法，孩子兄弟鏈表法和。6．n個頂點的連通圖的生成樹有條邊。7．一個有向圖G中若有弧<vi，vj>、<vj，vk>和<vi，vk>，則在圖G的拓撲序列中，頂點vi，vj和vk的相對位置為________。8．設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序，快速排序、冒泡排序和歸并排序方法對其進行排序(按遞增順序)，__最省時間，__最費時間。9．下面是將鍵值為x的結(jié)點插入到二叉排序樹中的算法，請在劃線處填上適當?shù)膬?nèi)容。typedefstructnode{intkey；structnode*left,*right；}voidsearchinsert(intx;pnodet)/*t為二叉排序樹根節(jié)點的指針*/{if（_____）{p=malloc(suze)；p->key=x;p->left=NULL；p->right=NULL；t=p；}elseif(x<t->key)searchinsert(x,t->left)else_____}10.線性表的___主要有點是從表中任一結(jié)點出發(fā)能訪問到所有結(jié)點。而使用____________，可根據(jù)需要在前后兩個方向上方便地進行查找。三、應(yīng)用題（本題共28分）1.樹的后根遍歷方法是：若樹非空，則1）依次后根遍歷根的各個子樹T1，T2，……，Tm；2）訪問根節(jié)點。對圖1所示的樹，用后根遍歷方法進行遍歷，請寫出遍歷所得到的結(jié)點訪問序列。（4分）AABCDEFGHIJK圖1樹2.將圖2的森林轉(zhuǎn)換成二叉樹。（4分）AABCDEFGIJ圖2森林3.圖3表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連接城市間的公路，邊上的權(quán)表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。（4分）661433211811651624361519圖3網(wǎng)4．已知一個無向圖的鄰接表如圖4所示。VV124∧V2541∧V345∧V4321∧V532∧圖4鄰連表1)畫出這個圖。2)以v1為出發(fā)點，對圖進行廣度優(yōu)先搜索，寫出所有可能的訪問序列。(本題4分，每小題2分)5．設(shè)n個元素的有序表為R，K為一個給定的值，二分查找算法如下：intbinswarth(sqlistR；keytypeK){L=1；h=n；suc=0；while((L<=h)＆＆(!suc){mid=(L+h)／2；switch{K=R[mid].key：suc=L；break；k<R[mid].key：h=mid-l；break；K>R[mid].key：L=mid+1}}if(suc)return(mid)elsereturn(0)；}將上述算法中劃線語句改為：K<R[mid].key：h=mid。1)改動后，算法能否正常工作?請說明原因。2)若算法不能正常工作，給出一個查找序列和一個出錯情況的查找鍵值；若能正常工作，請給出一個查找序列和查找某個鍵值的比較次數(shù)。(本題6分，每小題3分)6．有一組鍵值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大進行排序，請寫出每趟的結(jié)果，并標明在第一趟排序過程中鍵值的移動情況。(本題6分)四、設(shè)計題（共14分）設(shè)一顆二叉樹以二叉鏈表為存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為。設(shè)計一個算法，求在先根序列中處于第k個位置的結(jié)點。（本題6分）2.設(shè)某個單鏈表L的結(jié)點結(jié)構(gòu)為，試畫出該鏈表的結(jié)構(gòu)圖，并用C語言編寫算法，判斷該鏈表的元素值是否是遞增的。（本題8分）數(shù)據(jù)結(jié)構(gòu)導論模擬試卷（一）分析與解答一、單項選擇題1，D．2，C．3，D．4，C．5，D．6，D．7，A．8，B．9，A．10，C．11，D．12，C．13，A．14，B．15，C。二、填空題1.分析：在r所指鏈尾插入了所指結(jié)點，需執(zhí)行的三步操作是：1）r->next=s；2）r=s；3）r->next=NULL答案：r->next=s。2.分析：單鏈表最后一個結(jié)點的指針域為空，所以可用p->next==NULL作為判斷最后一個結(jié)點的條件。3.分析：當?？諘r，棧頂指針為空，故判?？諚l件為ls==NULL。棧非空時，退棧操作步驟為：1）p=ls；2）ls=ls->link；3）free(p)答案：ls==NULL，ls=ls->link。4.分析：設(shè)n1=2,n2=3,n3=4,樹的總結(jié)點數(shù)為n=n0+n1+n2+n3。(1)樹的分支樹為n-1=n1+2n2+n3。(2)(2)-(1)：-1=n2+2n3-n0有n0=n2+2n3+1=3+2×4+1=12答案：12。5.答案：雙親表示法。6.分析：n個頂點的連通圖，其生成樹有且僅有n-1條邊。答案：n-1。7.分析：按題意畫出圖5所示示意圖。由此知，在拓撲序列中i,j,k的相對位置是i,j,k。iikj圖5有向圖G的局部示意圖答案：i,j,k。8.分析：對冒泡排序來講，由于哨兵的作用，經(jīng)一趟排序后，就能判斷出當前無序區(qū)已經(jīng)自然有序，終止算法。故它最省時間。對快速排序來講，由于待排序空間是有序的，每趟排序后，中間元素的左邊總是一個空區(qū)域，而右邊區(qū)域長度僅比上一趟少1。因此當在最壞情況下，占用時間最長。答案：冒泡排序、快速排序。9.答案：t==NULL,searchinsert(x,t->right)。10.分析：線性表的存儲方式有多種，其中循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)，都能訪問到所有其它的結(jié)點。而如果采用雙向鏈表，則可以按前后兩個方向進行查找。答案：循環(huán)鏈表、雙向鏈表。三、應(yīng)用題1.答案：EBFGCKHIJDA。2.分析：先將每棵樹轉(zhuǎn)換成二叉樹，然后再將各二叉樹的根結(jié)點作為兄弟連接在一起。而樹轉(zhuǎn)換成二叉樹的方法是，先將兄弟結(jié)點連在一起，然后除最左邊的孩子外，斷開其它雙親到孩子的連線。答案：如圖6所示。AABCDEFGIJ（a）先將各樹轉(zhuǎn)換成二叉樹ABCABCDEFGIJAABCDEFGIJ（c）將各二叉樹組合在一起圖6森林轉(zhuǎn)換成二叉樹3.分析：本題實際上是求最小生成樹問題。由于圖中有兩條權(quán)值為6的邊，故可以得到兩種方案。答案：如圖7所示。181818181111665516162436152436154.答案：（1）如圖8所示。225314圖8圖4所示鄰接表所對應(yīng)的圖（2）v1v2v4v5v3和v1v4v2v3v5。5．分析：經(jīng)過改動以后，有可能出現(xiàn)死循環(huán)，比如當查找的鍵值k小于有序表中的最小鍵值時，就會出現(xiàn)死循環(huán)。答案：(1)算法不能正常運行。(2)假設(shè)有序表的查找序列為(7，10，12，16，24，39，42)，當待查的鍵值為k=5時，出現(xiàn)死循環(huán)。6．答案：25842l471527683520第一趟[201521]25[4727683584]第二趟[15]20[21]25[3527]47[6884]第三趟15202125[27]354768[84]得到：15202l252735476884第一趟排序過程中鍵值的移動情況如圖9所示。①①x25842l471527683520②③④圖9鍵值移動示意圖四、設(shè)計題1．分析：因為是求前根序列中處于第k個位置的結(jié)點，所以本算法是按前根遍歷來實現(xiàn)的。在這當中，訪問根結(jié)點的操作就是計算器count加1，然后判斷count是否等于k，等于k就退出并返回指向?qū)?yīng)結(jié)點的指針，否則繼續(xù)按前根遍歷往下查找。答案：Viodsearch(bitreptrt；integerk){if(t!=NULL){count++；if(count==k)return(t)；else{search(t->lchild,k)；search(t->rehild，k)；}}}2．分析：判斷一個單鏈表是否遞增，只要從起始結(jié)點開始，依次向后比較前一個結(jié)點的鍵值是否小于后一個