1、XX科技大學(xué)成都學(xué)院二零零八至二零零九學(xué)年第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課堂測試（60分鐘）閉卷考試時(shí)間:題號(hào)-一一-二二-三總分評卷教師分?jǐn)?shù)一填空題（每空2分，共40分）；數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和_空間復(fù)雜度兩種方法衡量其效率。1. 下面程序段的時(shí)間復(fù)雜度為_0（n若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲(chǔ)方式最節(jié)省時(shí)間。A. 順序表B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為：A）。（n>1）for（i=1;i<=n;i+）for（j=1;j<=i;j+）x=x+1;2. 靜態(tài)

2、鏈表中指針表示的是一結(jié)點(diǎn)的地址。3. 線型表、棧和隊(duì)列都是線型結(jié)構(gòu)，可以在線型表的任意位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊(duì)列只能在隊(duì)尾插入元素和隊(duì)頭除元素。4. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。5. 在一個(gè)長度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_n-i+1_個(gè)元素。6. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的驅(qū)。7. 帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是head->next=NULL。8. 在棧頂指針為hs的鏈棧中，判斷棧空的條件是hs=NULL一。9. 在hq的鏈隊(duì)列中，判定只

3、有一個(gè)結(jié)點(diǎn)的條件是_hq.front->next=hq.rear。10. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p指向），滿足條件p->next=head。11. 兩個(gè)串相等的充分必要條件是串長相等且對應(yīng)字符相等。12. 空串是度為0的串其長度等于0。13. 空格串是由空格字符組成的串，其長度等于空格的個(gè)數(shù)3.表元編號(hào)結(jié)點(diǎn)表元間關(guān)系1a132a213a324.5.6.7.8.9.10.11.12.13.14.15.A.循環(huán)鏈表B單鏈表C雙向循環(huán)鏈表D雙向鏈表有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？(B)A.543612B.346521C.45312

4、6D.234156若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m,topi代表第i個(gè)棧(i=1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是(B)。A.top2-top1|=0B.top1+1=top2C.top1+top2=mD.top1=top2數(shù)組Qn用來表示一個(gè)循環(huán)隊(duì)列，front為當(dāng)前隊(duì)列頭元素的前一位置，rear為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為(D)A.rearfrontB.(n+frontrear)%nC.n+rearfrontD.(n+rearfront)%n設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5和e6依

5、次通過棧S,一個(gè)元素出棧后即進(jìn)隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e6,e5,e3,e1則棧S的容量至少應(yīng)該是(B)oA.6B.4C.3D.2在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)BC.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)BC.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D判定一個(gè)順序棧ST(最多元素為N為空的條件是!=ST.base!=N一個(gè)隊(duì)列的入列序列是1,A.4,3,2,1B.1,2,3,42,CC)o.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu).內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)(B)B.ST.top=ST.base.ST.top=N3,4,則隊(duì)列的輸出序列是B.1,

6、4,3,2D.3,2,4,1判定一個(gè)循環(huán)隊(duì)列QU最多元素為N)為空的條件是CA.QU.front=(QU.rear+1)%NB.QU.front!=(QU.rear+1)%N!=QU.rear判定一個(gè)循環(huán)隊(duì)列QU(最多元素為mQ為滿隊(duì)列的條件是AoA.QU.front=(QU.rear+1)!=(QU.rear+1)%NC. !=QU.rea葉1不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是AA.head=NULLB.head->next=NULLC.head->next=headD. head!=NULL14. 在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是(C)oA. p-&g

7、t;Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;從一個(gè)具有n個(gè)結(jié)點(diǎn)的單

8、鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_D結(jié)點(diǎn)。A.nB.n/2C.(n1)/2D.(n+1)/2設(shè)串s1=ABCDEF',s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的字串，len(s)返回串s的長度，則con(subs(s1,2,len(s2),subs(s1,len(s2),2)的結(jié)果串是DA)BCDEFB)BCDEFGC)BCPQRSTD)BCDEFEF三.綜合題(每題6分，共30分)1. 線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線

9、性表L=23，17，47,05，31，若它以單鏈表方式存儲(chǔ)在下列100119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)(占2個(gè)字節(jié))和指針(占2個(gè)字節(jié)，由大寫字母表示)組成，如下所示：10012047p23q05r31s17t其中指針p，q，r，s，t的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？(共6分)答：p=108q=116r=112s=0或NULLt=100首址=104末址=112。2. 如果想將輸入的一個(gè)字符序列逆序輸出，如輸入“abcde”輸出“fedcba”，請分析用線性表、堆棧和隊(duì)列等方式正確輸出的可能性？(共6分)線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量(j-)從表

10、尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。3. 寫出刪除順序表中第i個(gè)元素的算法：(共6分)StatusListDelete_sq(SqList&L,inti,ElemType&e)Statusdel_sqllist(SqList&L,inti,ElemType&e)if(i<1IIi>L.length)returnERROR;e=L.elemi;for(j=i+1;j<=Length;j+)L.elemj-1=L.elemj;-L.length;returnOK;4. 寫出順序棧的入棧算法

11、(共6分)StatusPush(SqStack&S,SelemTypee)voidPush(Stack&S,ElemTypee)/在棧頂之上插入元素e為新的棧頂元素p=newLNode;/建新的結(jié)點(diǎn)if(!p)exit(1);/存儲(chǔ)分配失敗p->data=e;p->next=S.top;/鏈接到原來的棧頂S.top=p;/移動(dòng)棧頂指針+S.length;/棧的長度增1/Push寫出鏈隊(duì)列的出隊(duì)列算法(共6分)StatusDeQueue(LinkQueue&Q,QelemType&e)StatusDeQueue(LinkQueue&Q,QEle

12、mType&e)若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回0K;否則返回ERRORif(Q.front=Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;xx科技大學(xué)成都學(xué)院20082009學(xué)年第一學(xué)期中期試題一一數(shù)據(jù)結(jié)構(gòu)答案7.p=108q=116r=112s=0或NULI填空題(每題2分，共40分)；題號(hào)參考答案1空間復(fù)雜度20(n2)3下一結(jié)點(diǎn)的地址4線型，任意，棧頂，隊(duì)尾，隊(duì)

13、頭5n-16n-i+17前驅(qū)8head->next=NULL9hs=NULL10hq.front->next=hq.rear11p->next=head12串長相等且對應(yīng)字符相等13長度為0的串，014由空格字符組成的串，空格的個(gè)數(shù)單項(xiàng)選擇題（每題2分，共30分）;綜合題（共30分）題號(hào)12345678910答案AABBDBCBBC題號(hào)1112131415答案AACDDt=100首址=104末址=112。8.線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量(j-)從表尾開始打印輸出;堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。3. Statusdel

14、_sqllist(SqList&L,inti,ElemType&e)if(i<1IIi>L.length)returnERROR;e=L.elemi;for(j=i+1;j<=Length;j+)L.elemj-1=L.elemj;-L.length;returnOK;4.voidPush(Stack&S,ElemTypee)/在棧頂之上插入元素e為新的棧頂元素p=newLNode;/建新的結(jié)點(diǎn)if(!p)exit(1);/存儲(chǔ)分配失敗p->data=e;p->next=S.top;/鏈接到原來的棧頂S.top=p;/移動(dòng)棧頂指針+S.le

15、ngth;/棧的長度增1/PushStatusDeQueue(LinkQueue&Q,QElemType&e)若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK;否則返回ERRORif(Q.front=Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;全真模擬試題（一）一、單項(xiàng)選擇題（在每小題的4個(gè)備選答案中，選出正確的答案，并將其號(hào)碼填在題干的括號(hào)內(nèi)。每小題2分，共24分）若某

16、線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（4）存儲(chǔ)方式最節(jié)省時(shí)間。單鏈表雙鏈表單向循環(huán)順序表1. 串是任意有限個(gè)（1）符號(hào)構(gòu)成的序列符號(hào)構(gòu)成的集合字符構(gòu)成的序列字符構(gòu)成的集合設(shè)矩陣A（aij，l<i,j書元素滿足：盯0（i>j,l<i,j<10）aj=O（ivj,I<i,j<10）2000的存儲(chǔ)區(qū)域中，每個(gè)元素現(xiàn)將A的所有非0元素以行序?yàn)橹餍虼娣旁谑椎刂窞檎加?個(gè)單元，則元素A95的首址為2340233621642160如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（） 必須判別棧是否滿對棧不作任何判別 必須判別棧是否空判別棧元素的類型2

17、. 設(shè)數(shù)組Data0.m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為（）front=front+1front=(front+1)%mrear=(rea葉1)%mfront=(front+1)%(m+1)深度為6(根的層次為1)的二叉樹至多有()結(jié)點(diǎn)64323163將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點(diǎn)編號(hào)根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為49的結(jié)點(diǎn)X的雙親編號(hào)為（）242523無法確定設(shè)有一個(gè)無向圖G=（V，E）和G=V',E'）如果G'為G的生成樹，則下面不正確的說法是（）G為G的子圖G為G的邊通分量

18、G為G的極小連通子圖且V=VG為G的一個(gè)無環(huán)子圖3. 用線性探測法查找閉散列表，可能要探測多個(gè)散列地址，這些位置上的鍵值（）一定都是同義詞一定都不是同義詞都相同不一定都是同義詞二分查找要求被查找的表是（3）鍵值有序的鏈接表鏈接表但鍵值不一定有序鍵值有序的順序表順序表但鍵值不一定有序4. 當(dāng)初始序列已經(jīng)按鍵值有序，用直接插入算法對其進(jìn)行排序，需要循環(huán)的次數(shù)為（）n2nlog2nlog2nn-15. 堆是一個(gè)鍵值序列ki,k2,燦,對i=1,2,|_n/2滿足（）kiWki<ki+1ki<k2i+1<k2iki<ki且ki<ki+1（2i+1<n）kiWk或ki

19、W2i+1（2i+1<n）二、判斷題（判斷下列各題是否正確，正確在括號(hào)內(nèi)打“V',錯(cuò)的找“X”每小題1分，共10分）雙鏈表中至多只有一個(gè)結(jié)點(diǎn)的后繼指針為空。（）1. 在循環(huán)隊(duì)列中，front指向隊(duì)列中第一個(gè)元素的前一位置，rear指向?qū)嶋H的隊(duì)尾元素，隊(duì)列為滿的條件是front=rear°（）對鏈表進(jìn)行插入和刪除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)。（）2. 棧可以作為實(shí)現(xiàn)程序設(shè)計(jì)語言過程調(diào)用時(shí)的一種數(shù)據(jù)結(jié)構(gòu)。（）在一個(gè)有向圖的拓樸序列中，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>。（）i3. 對有向圖G,如果從任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個(gè)頂點(diǎn)

20、，則該圖一定是完全圖。（）順序查找法”是指在順序表上進(jìn)行查找的方法。（）4. 向二叉排序樹插入一個(gè)新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)一定成為二叉排序樹的一個(gè)葉子結(jié)點(diǎn)。（）鍵值序列A，C，D，E，F(xiàn)，E，F(xiàn)是一個(gè)堆。5. 二路歸并時(shí)，被歸并的兩個(gè)子序列中的關(guān)鍵字個(gè)數(shù)一定要相等。（）三、填空題（每空2分，共24分）1. 設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語句是;r=s;r->next=null;。2. 在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是。3. 設(shè)一個(gè)鏈棧的棧頂指針是Is,棧中結(jié)點(diǎn)格式為info|link,?？盏臈l件是如果棧不為空，則退棧操作為p=ls

21、；;free(p);。4. 已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹中有個(gè)葉子的結(jié)點(diǎn)。5. 樹有三種常用的存儲(chǔ)結(jié)構(gòu)，即孩子鏈表法、孩子兄弟鏈表法和N個(gè)頂點(diǎn)的連通圖的生成樹有邊。6. 一個(gè)有向圖G中若有弧VVi,Vj>、<vj,vk>和<vi,vk>,則在圖G的拓?fù)湫蛄兄?，頂點(diǎn)Vi,Vj和Vk的相對位置為。7. 設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進(jìn)行(按遞增排序)，最省時(shí)間，最費(fèi)時(shí)間。8. 下面是將鍵值為x的結(jié)點(diǎn)插入到二叉排序樹中的算法，請?jiān)趧澗€處填上適當(dāng)?shù)膬?nèi)容。typede

22、fstructpnodeintkey;structpnode*left,*right;pnode;voidsearchinsert(intx,pnodet)/*t為二叉排序樹根結(jié)點(diǎn)的指針*/if()p=malloc(size);p->key=x;p->lchild=null;p->rchild=null;t=p;elseif(x<t->key)searchinsert(x,t->lchild)else;四、應(yīng)用題(本題共28分)樹的后根遍歷方法是：若樹非空則(4分)(1) 依據(jù)次后根遍歷根的各個(gè)子樹T!，T2，Tm;(2) 訪問根結(jié)點(diǎn)將下圖的森林轉(zhuǎn)換為二叉樹

23、。(4分)1. 下圖表示一個(gè)地區(qū)的交通網(wǎng)，頂點(diǎn)表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費(fèi)的代價(jià)。怎樣選擇能夠溝通每個(gè)城市且總造價(jià)最省的n-1條公路，畫出所有可能的方案。(4分)圖7.11遍歷無向圖(a)無向圖Ge(b)深度優(yōu)先搜索示例(c)G6的鄰接表表示(c)表頭結(jié)點(diǎn)4已知一個(gè)無向圖的鄰接表如下圖所示。(本題4分，每小題2分)(1)畫出這個(gè)圖。以V1為出發(fā)點(diǎn)，對圖進(jìn)行廣度優(yōu)先搜索，寫出所有可能的訪問序列。5. 設(shè)n個(gè)元素的有序表為R,K為一個(gè)給定的值，二分查找算法如下：intbinsearch(sqlistR,keytypeK)j=1;h=n;suc=0;while(j<

24、;=h)&&(!suc)mid=(j+h)/2;switchcaseK=Rmid.key:suc=1;break;caseK<Rmid.key:h=mid-1;break;caseK>Rmid.key:j=mid+1if(suc)return(mid);elsereturn(0);將上述算法中劃線語句改為：K<Rmid.key:h=mid.(1) 改動(dòng)后，算法能否正常工作？請說明原因。(2) 若算法不能正常工作，給出一個(gè)查找序列和一個(gè)出錯(cuò)情況的查找鍵值；若能正常工作，請給出一個(gè)查找序列和查找某個(gè)鍵值的比較次數(shù)。(本題6分，每小題3分)有一組鍵值25,84,21

25、,47，15，27,68,35,24，采用快速排序方法由小到大進(jìn)行排序，請寫出每趟的結(jié)果，并標(biāo)明在第一趟排序過程中鍵值的移動(dòng)情況。(本題6分)五、設(shè)計(jì)題(共14分)設(shè)棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為lchild|data|rchild。設(shè)計(jì)一個(gè)算法，求在前根序列中處于第k個(gè)位置的結(jié)點(diǎn)。(本題6分)1. 設(shè)某單鏈表L的結(jié)點(diǎn)結(jié)構(gòu)為data|next試畫出該鏈表的結(jié)構(gòu)圖，并用類C語言編寫算法判斷該鏈表的兀素是否是遞增的。(本題8分)全真模擬試題(一)參考答案、單項(xiàng)選擇題123分析：按題意，矩陣A是個(gè)三角矩陣，Al,j的首地址可用下列公式計(jì)算：LOC(aj)=LOC(aii)+(k-1)*L其

26、中K為Al,j在A中的序號(hào)k=I*(I-1)/2+j，L為每個(gè)元素所占的單元數(shù)。所以有：LOC(aj)=2000+(9*(9-1)/2+5-1)*4=2000+160=2160。故為答案45678分析：如果G'為G的生成樹，那么G'是G的子圖，也是G的無環(huán)子圖，并且還是G的極小連通子圖，且V=V,而連通分量則是指無向圖的極大連通子圖。故答案是錯(cuò)誤的。9.10。11。12。二、判斷題1. 樹的總結(jié)點(diǎn)數(shù)為n=n0+n1+n2+n3.三、填空題1.R->next=s.2.P->next=NULL3.Ls=NULL、ls=ls->link.4.12分析：設(shè)n1=2,n2=3,n3=4樹的分支數(shù)為n-1=n1+2n2+3n3-得：-1=n2+2n3-n0有n0=n2+2n3+1=3+2*4+1=12雙親表示法。5. N-1I,j,k.6. 冒泡排序、快速排序T=NULL、search