計算機數據結構考試題及答案

全真模擬試題（一）一、 單項選擇題（在每小題的4個備選答案中，選出正確的答案，并將其號碼填在題干的括號內。每小題2分，共24分）若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最節(jié)省時間。單鏈表②雙鏈表③單向循環(huán)④順序表2．串是任意有限個（）①符號構成的序列 ②符號構成的集合③字符構成的序列 ④字符構成的集合設矩陣A（aij，l<i,j<10）的元素滿足：aij和（Aj,1弐j<10）aij=0（i<j,l<i,j<10）現將A的所有非0元素以行序為主序存放在首地址為2000的存儲區(qū)域中，每個元素占有4個單元，則元素A[9]⑸的首址為①2340 ②2336 ③2164 ④21604．如果以鏈表作為棧的存儲結構，則退棧操作時（）必須判別棧是否滿對棧不作任何判別必須判別棧是否空判別棧元素的類型5.設數組Data[0..m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（）①front=front+l ②front=（front+l）%m③rear=（rear+l）%m ④front=（front+1）%（m+1）6．深度為6（根的層次為l）的二叉樹至多有（）結點。① 64 ②32 ③31 ④637．將含l00個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親編號為（）①24 ②25 ③23 ④無法確定設有一個無向圖G=（V，E）和G'=（V'，E'）如果G'為G的生成樹，則下面不正確的說法是（）①G'為G的子圖 ②G'為G的邊通分量③G'為G的極小連通子圖且V'=V④G'為G的一個無環(huán)子圖9．用線性探測法查找閉散列表，可能要探測多個散列地址，這些位置上的鍵值（）①一定都是同義詞②一定都不是同義詞③都相同 ④不一定都是同義詞10． 二分查找要求被查找的表是（ ）①鍵值有序的鏈接表②鏈接表但鍵值不一定有序③鍵值有序的順序表④順序表但鍵值不一定有序11． 當初始序列已經按鍵值有序，用直接插入算法對其進行排序，需要循環(huán)的次數為（）①n2 ②nlog2n ③1og2n ④n-112. 堆是一個鍵值序列{k1,k2,...,kn},對i=1,2,...,|_n/2_|,滿足（）①ki<k2i<k2i+1 ②kivk2i+1vk2i③ki<k2i且ki0k2i+l（2i+19）④ki<k2i或ki<k2i+1（2i+1<n）二、 判斷題（判斷下列各題是否正確，正確在括號內打“V”，錯的找“X”。每小題1分，共10分）1．雙鏈表中至多只有一個結點的后繼指針為空。（）2．在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear。（）3．對鏈表進行插入和刪除操作時，不必移動結點。（）4．?？梢宰鳛閷崿F程序設計語言過程調用時的一種數據結構。（）在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧va,b>。（）i對有向圖G,如果從任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。（ ）“順序查找法”是指在順序表上進行查找的方法。（）向二叉排序樹插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。（）鍵值序列{A,C，D，E，F，E，F}是一個堆。二路歸并時，被歸并的兩個子序列中的關鍵字個數一定要相等。（）三、 填空題（每空2分，共24分）設r指向單鏈表的最后一個結點，要在最后一個結點之后插入s所指的結點，需執(zhí)行的三條語句是 ；r=s;r->next=null;。在單鏈表中，指針p所指結點為最后一個結點的條件是 。設一個鏈棧的棧頂指針是Is,棧中結點格式為info|link，?？盏臈l件是 .如果棧不為空，則退棧操作為p=ls； ；free（p）;。已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有 個葉子的結點。樹有三種常用的存儲結構，即孩子鏈表法、孩子兄弟鏈表法和 .N個頂點的連通圖的生成樹有 條邊。一個有向圖G中若有弧<vi,vj>、<vj,vk>和<vi,vk>,則在圖G的拓撲序列中，頂點vi,vj和vk的相對位置為 。設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行（按遞增排序）， 最省時間， 最費時間。下面是將鍵值為x的結點插入到二叉排序樹中的算法，請在劃線處填上適當的內容。typedefstructpnode{intkey;structpnode*left,*right;}pnode;voidsearchinsert（intx,pnodet）/*t為二叉排序樹根結點的指針*／{if（ ）{p=malloc（size）;p->key=x;p->lchild=null;p->rchild=null;t=p;}elseif（x<t->key）searchinsert（x,t->lchild）else ;}四、 應用題（本題共28分）樹的后根遍歷方法是：若樹非空則（4分）(1)依據次后根遍歷根的各個子樹T1,T2,……Tm;(2)訪問根結點將下圖的森林轉換為二叉樹。(4分)下圖表示一個地區(qū)的交通網,頂點表示城市,邊表示連結城市間的公路,邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路,畫出所有可能的方案。(4分)圖7.11遍歷無向圖(a)無向圖G6(b)深度優(yōu)先搜索示例(c)G6的鄰接表表示(c)表頭結點4．已知一個無向圖的鄰接表如下圖所示。(本題4分,每小題2分)畫出這個圖。以v1為出發(fā)點,對圖進行廣度優(yōu)先搜索,寫出所有可能的訪問序列。5?設n個元素的有序表為R,K為一個給定的值，二分查找算法如下：intbinsearch(sqlistR,keytypeK){j=1;h=n;suc=0;while((j<=h)&&(!suc)){mid=(j+h)/2;switch{caseK=R[mid].key:suc=1;break;caseK<R[mid].key:h=mid-1;break;caseK>R[mid].key:j=mid+1}}if(suc)return(mid);elsereturn(0);}將上述算法中劃線語句改為：K<R[mid].key:h=mid.改動后，算法能否正常工作？請說明原因。若算法不能正常工作,給出一個查找序列和一個出錯情況的查找鍵值；若能正常工作，請給出一個查找序列和查找某個鍵值的比較次數。(本題6分，每小題3分)6.有一組鍵值25,84,21,47,15,27,68,35,24,采用快速排序方法由小到大進行排序請寫出每趟的結果，并標明在第一趟排序過程中鍵值的移動情況。(本題6分)五、設計題(共14分)1．設棵二叉樹以二叉鏈表為存儲結構，結點結構為lchild|data|rchild。設計一個算法，求在前根序列中處于第k個位置的結點。(本題6分)設某單鏈表L的結點結構為dataInext，試畫出該鏈表的結構圖，并用類C語言編寫算法判斷該鏈表的元素是否是遞增的。(本題8分)全真模擬試題(一)參考答案一、單項選擇題1④2③3④分析：按題意，矩陣A是個三角矩陣，A[I,j]的首地址可用下列公式計算：LOC(aij)=LOC(a11)+(k-1)*L其中K為A[I,j]在A中的序號k=I*(I-1)/2+j,L為每個元素所占的單元數。所以有：LOC(aij)=2000+(9*(9-1)/2+5-1)*4=2000+160=2160。故為答案④TOC\o"1-5"\h\z③④④①②分析：如果G'為G的生成樹，那么G'是G的子圖，也是G的無環(huán)子圖，并且還是G的極小連通子圖，且V'=V，而連通分量則是指無向圖的極大連通子圖。故答案②是錯誤的。④10。③11。④12。③二、 判斷題v2.x3.v4.v5.x6.x7.x8.v9.v10.x三、 填空題1. R->next=s.P->next==NULLLs==NULL、ls=ls->link.12分析：設n1=2,n2=3,n3=4,樹的總結點數為n=n0+n1+n2+n3樹的分支數為n-1=n1+2n2+3n3②-①得：-1=n2+2n3-n0有n0=n2+2n3+1=3+2*4+1=12雙親表示法。N-1I,j,k.冒泡排序、快速排序T==NULL、searchinsert(x,t->rchild).四、 應用題1. EBFGCKHIJDA。2.答案如圖應用題I9.2.2所示。3.分析：本題實際上是求最小生成樹問題。由于釁中有兩條權值為6的邊，故可以得到兩種方案。答案如圖應用題I9.3.2所示。答案：(1)答案如圖應用題I9.4.2所示。(2)v1v2v4v5v3和v1v4v2v3v5。(1)經過改動以后，有可能出現死循環(huán)，比如當查找的鍵值K小于有序表中的最小鍵值時，就會出現死循環(huán)。故算法不能正常進行。(2)假設有序表的查找序列為(2,3,4,5,6)，當待查的鍵值K=1時，出現死循環(huán)。答案：25 84 214715276835 24第一趟[241521]25[4727683584]第二趟[2115]2425[3527]47[6884]AA* +比第三趟[15]212425[27]354768[84]得到152124252735476884第一趟排序過程中鍵值的移動情況如下：第一趟：[258421471527683524]一次交換之后[248421471527683525]二次交換之后[242521471527683584][242521471527683584][242521471527683584][242521471527683584]三次交換之后[241521472527683584][241521472527683584]四次交換之后[241521254727683584]以上“-”表示當前經比較不交換位置的元素。“”表示當前經比較交換位置的元素。五、設計題1.Bitreptrsearch(bitreptrt,intk