《計算機軟件技術(shù)基礎(chǔ)》課后題

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第一節(jié) 概 論一、選擇題1要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著( )。A數(shù)據(jù)元素具有同一的特點 B不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致 C每個數(shù)據(jù)元素都一樣 D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等2數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的( (1) )以及它們之間的( (2) )和運算的學(xué)科。(1) A操作對象 B計算方法 C物理存儲 D數(shù)據(jù)映像(2) A結(jié)構(gòu) B關(guān)系 C運算 D算法3數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。 (1) A算法 B數(shù)據(jù)元素 C數(shù)據(jù)操

2、作 D邏輯結(jié)構(gòu) (2)A操作 B映像 C存儲 D關(guān)系4在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( )。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5線性表的順序存儲結(jié)構(gòu)是一種( )的存儲結(jié)構(gòu)。A隨機存取 B順序存取 C索引存取 DHash存取6算法分析的目的是( )。A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進 D分析算法的易懂性和文檔性7計算機算法指的是( (1) )，它必須具備輸入、輸出和( (2) )等五個特征。 (1) A計算方法 B排序方法 C解決某一問題的有限運算序列 D調(diào)度方法 (2) A可行性、可

3、移植性和可擴充性 B可行性、確定性和有窮性 C確定性，有窮性和穩(wěn)定性 D易讀性、穩(wěn)定性和安全性8線性表若采用鏈表存儲結(jié)構(gòu)，要求內(nèi)存中可用存儲單元的地址( )。A必須是連續(xù)的 B部分必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)不連續(xù)都可以9在以下的敘述中，正確的是( )。A線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu) B二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表 C棧的操作方式是先進先出 D隊列的操作方式是先進后出10根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式，其中解釋錯誤的是( )。A集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散 B線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次

4、排列形成一條“鎖鏈” C樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹 D圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接11以下說法正確的是( )。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位 B數(shù)據(jù)項是數(shù)據(jù)的基本單位 C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合 D數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題1數(shù)據(jù)元素是數(shù)據(jù)的最小單位。2數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。3數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。4數(shù)據(jù)項是數(shù)據(jù)的基本單位。5數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。6數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中實際的存儲形式。7算法

5、和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。8順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。三、填空題1所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的_。2，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容_ 、 、 _。3數(shù)據(jù)的邏輯結(jié)構(gòu)包括_ _、_ _、_ _和_ _四種類型。4在線性結(jié)構(gòu)中，開始結(jié)點_ _前驅(qū)結(jié)點，其余每個結(jié)點有且只有_ _個前驅(qū)結(jié)點。5在樹形結(jié)構(gòu)中，根結(jié)點只有_ _，其余每個結(jié)點有且只有_ _前驅(qū)結(jié)點；葉結(jié)點沒有_ _結(jié)點，其余每個結(jié)點的后繼結(jié)點可以有_ _·6在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點可以有_ _。7算法的五個重要

6、特性是_ _、_ _、_ _、_ _、_ _。8下列程序段的時間復(fù)雜度是_ _。 for (i=1；i<=n；i+) Ai，i=0；9下列程序段的時間復(fù)雜度是_ _。 S=0； for(i=1；i<=n；i+) for(j=1；j<=n；j+) s=s+Bi,j； sum=s；10存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的_ _實現(xiàn)。11從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的“數(shù)據(jù)”應(yīng)分成三個不同的層次，即_ _、_ _和_ _。12根據(jù)需要，數(shù)據(jù)元素又被稱為_ _、_ _、_ _或_ _。13通常，存儲結(jié)點之間可以有_ _、_ _、_ _、_ _四種關(guān)聯(lián)方式，稱為四種基本存儲方式。14通常從_ _、_

7、_、_ _、_ _等幾方面評價算法(包括程序)的質(zhì)量。15一個算法的時空性能是指該算法的_ _和_ _，前者是算法包含的_ _，后者是算法需要的_ _。16在一般情況下，一個算法的時間復(fù)雜度是_ _的函數(shù)。17常見時間復(fù)雜度的量級有：常數(shù)階O(_ _)、對數(shù)階O(_ _)、線性階O(_ _)、平方階O(_ _)和指數(shù)階O(_ _)。通常認為，具有指數(shù)階量級的算法是_ _的。18數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的_ _和_ _。19數(shù)據(jù)對象是性質(zhì)相同的_ _的集合。20抽象數(shù)據(jù)類型是指一個_ _以及定義在該模型上的一組操作。四、應(yīng)用題1分析下列程序段的時間復(fù)雜度。 i=1； WHILE (i<

8、=n) i=i*2； _ _2敘述算法的定義及其重要特性。3簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。4邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？5將數(shù)量級210，n，n2，n3，nlog2n，log2n，2n，n!，(23)n，n23按增長率進行排列。6設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1，k2，k3，k9，R=<k1，k3>，<k1，k8>，<k2，k3>，<k2，k4>，<k2，k5>，<k3，k9>，<k5，k6>，<k8，k9>，<k9，k7>，<k4，k6>，畫出這個邏輯結(jié)構(gòu)

9、的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？7設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。8分析下列程序的時間復(fù)雜度(設(shè)n為正整數(shù))。 (1)int rec(int n) if(n=1)return(1)； else return(n*rec(n-1)； (2)x=91；y=100； While (y>0) if(x>10) y-； (3)i=1；j=0； while(i+j<=n) if(i>j)j+； else i+; (4)x=n；y=0；while(x>=(y+1)*(y+1) y+；答： 9設(shè)n

10、為正數(shù)。試確定下列各程序段中前面加記號的語句的頻度： (1)i=1；k=0； while(i<=n-1) k+=10*i； i+； ) (2) k=0； for(i=1；i<=n；i+) for(j=i；j<=n：j+) k+；答：第二節(jié) 線性表一、選擇題1線性結(jié)構(gòu)中的一個結(jié)點代表一個( )。 A數(shù)據(jù)元素 B數(shù)據(jù)項 C數(shù)據(jù) D數(shù)據(jù)結(jié)構(gòu)2線性表L=(a1，a2，ai，an)，下列說法正確的是( )。 A每個元素都有一個直接前驅(qū)和直接后繼 B線性表中至少要有一個元素 C表中諸元素的排列順序必須是由小到大或由大到小的 D除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接

11、前驅(qū)和直接后繼3順序表是線性表的( )。 A鏈式存儲結(jié)構(gòu) B順序存儲結(jié)構(gòu) C索引存儲結(jié)構(gòu) D散列存儲結(jié)構(gòu)4對于順序表，以下說法錯誤的是( )。 A順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址 B順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C順序表的特點是：邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰 D順序表的特點是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中5對順序表上的插入、刪除算法的時間復(fù)雜度分析來說，通常以( )為標(biāo)準操作。 A條件判斷 B結(jié)點移動 C算術(shù)表達式 D賦值語句6對于順序表的優(yōu)缺點，以下說法錯誤的是( )。 A無需為表示結(jié)點間的邏輯

12、關(guān)系而增加額外的存儲空間 B可以方便地隨機存取表中的任一結(jié)點 C插入和刪除操作較方便 D由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進行(靜態(tài)分配)7在含有n個結(jié)點的順序存儲的線性表中，在任一結(jié)點前插入一個結(jié)點所需移動結(jié)點的平均次數(shù)為( )。 An Bn/2 C(n-1)/2 D(n+1)/28在含有n個結(jié)點的順序存儲的線性表中，刪除一個結(jié)點所需移動結(jié)點的平均次數(shù)為( )。 An Bn/2 C(n-1)/2 D(n+1)/29帶頭結(jié)點的單鏈表為空的條件是( )。Ahead=NULL Bhead->next=NULL Chead->next=head Dhead!=NULL10非空

13、單循環(huán)鏈表head的尾結(jié)點*p滿足( )。 Ap->next=NULL Bp=NULL Cp->next=head Dp=head11在雙循環(huán)鏈表的*p結(jié)點之后插入*s結(jié)點的操作是( )。 Ap->next=s；s->prior=p；p->next->prior=s；s->next=p->next； Bp->next=s；p->next->prior=s；s->prior=p：s->next=p->next； Cs->prior=p；s->next=p->next；p->next=s；p

14、->next->prior=s； Ds->prior=p；s->next=p->next；p->next->pror=s；p->next=s；12. 在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入結(jié)點*s，則執(zhí)行( )。 As->next=p->next；p->next=s； Bp->next=s->next；s->next=p； Cq->next=s; s->next=p； Dp->next=s; s->next=q；13. 在一個單鏈表中，若*p結(jié)點不是最后

15、結(jié)點。在*p之后插入結(jié)點*s，則執(zhí)行( )。 As->next=p；p->next=s; Bs->next=p->next；p->next=s； Cs->next=p->next； p=s； Dp->next=s； s->next=p;14. 若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)元素，則采用( )存儲方式最節(jié)省時間。 A順序表 B. 單鏈表 C雙鏈表 D單循環(huán)鏈表15設(shè)rear是指向非空帶頭結(jié)點的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點的操作可表示為( )。 Ap=rear；rear=rear->next； free(

16、p) Brear=rear->next；free(rear)； Crear=rear->next->next； free(rear)； Dp=rear->next->next；rear->next->next=p->next；free(p)；16在一個單鏈表中，若刪除*p結(jié)點的后繼結(jié)點，則執(zhí)行( )。 Aq=p->next；p->next=q->next；free(q)； Bp=p->next；p->next=p->next->next；free(p)； Cp->next=p->next；fr

17、ee(p->next)； Dp=p->next->next；free(p->next)；17設(shè)指針p指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用( )式來刻畫。 Ap->prior->next->=p->next->next Bp->prior->prior=p->next->prior Cp->prior->next->=p->next->prior Dp->next->next=p->prior->prior18在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rear后，

18、其頭結(jié)點和尾結(jié)點的存儲位置分別是( )。 Arear和rear->next->next Brear->next和rear Crear->next->next和rear Drear和rear->next19循環(huán)鏈表的主要優(yōu)點是( )。 A不再需要頭指針了 B已知某個結(jié)點的位置后，容易找到它的直接前驅(qū) C在進行插入、刪除操作時，能更好地保證鏈表不斷開 D從表中任一結(jié)點出發(fā)都能掃描到整個鏈表20在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是( )。 A單鏈表 B雙鏈表 C循環(huán)鏈表 D順序表二、判斷題1順序存儲的線性表可以隨機存取。2順序存儲的線性表的插入和刪除

19、操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要移動。3線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。4在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。5在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。6在單鏈表中，可以從頭結(jié)點開始查找任何一個元素。7線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。8在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關(guān)。9在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。10順序存儲方式只能用于存儲線性結(jié)構(gòu)

20、。三、填空題1為了便于討論，有時將含n(n>0)個結(jié)點的線性結(jié)構(gòu)表示成(a1，a2，an)，其中每個ai代表一個_結(jié)點_。a1稱為_ _結(jié)點，an稱為_ _結(jié)點，i稱為ai在線性表中的_ _。對任意一對相鄰結(jié)點ai、ai+1(1i<n)，ai稱為ai+1的直接_ _，ai+1稱為ai的直接_ _。2線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接_ _外，其他結(jié)點有且僅有一個直接_ _；除終端結(jié)點沒有直接_ _外，其他結(jié)點有且僅有一個直接_ _。3所有結(jié)點按一對一的鄰接關(guān)系構(gòu)成的整體就是_ _結(jié)構(gòu)。4線性表的邏輯結(jié)構(gòu)是_ _結(jié)構(gòu)，其所含結(jié)點的個數(shù)稱為線性表的_ _。5

21、在單鏈表中，刪除p所指結(jié)點的直接后繼的操作是_ _；p->next=q->next；free(q)； 6非空的單循環(huán)鏈表head的尾結(jié)點(由指針p所指)滿足_ _ _。7rear是指向非空帶頭結(jié)點的單循環(huán)鏈表的尾指針，則刪除起始結(jié)點的操作可表示為_ _；q=p->next；p->next=q->next；free(q)；_。8對于一個具有n個結(jié)點的單鏈表，在p所指結(jié)點后插入一個結(jié)點的時間復(fù)雜度為_ _，在給定值為x的結(jié)點后插入新結(jié)點的時間復(fù)雜度為_ _。9單鏈表表示法的基本思想是用_ _表示結(jié)點間的邏輯關(guān)系。10在順序表中插入或刪除一個元素，平均需要移動_ _元素

22、，具體移動的元素個數(shù)與_ _有關(guān)。11在一個長度為n的向量的第i(1in+1)個元素之前插入一個元素時，需向后移動_ _個元素。12在一個長度為n的向量中刪除第i(1in)個元素時，需向前移動_ _個元素。13在雙鏈表中，每個結(jié)點有兩個指針域，一個指向_ _，另一個指向_ _。14在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=_ _。15設(shè)head指向單鏈表的表頭，p指向單鏈表的表尾結(jié)點，則執(zhí)行p->next=head后，該單鏈表構(gòu)成_ _。16在單鏈表中，若p和s是兩個指針，且滿足p->next與s相同，則語句p->n

23、ext=s->next的作用是_ _s指向的結(jié)點。17設(shè)r指向單循環(huán)鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入s所指的結(jié)點，需執(zhí)行的三條語句是_ _ ；r->next=s；r=s；18在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是_ _ _。19在雙循環(huán)鏈表中，若要在指p所指結(jié)點前插入s所指的結(jié)點，則需執(zhí)行下列語句：s->next=p； s->prior=p->prior；_ _ _=s；p->prior=s；20在單鏈表中，若要在p所指結(jié)點之前插入s所指的結(jié)點，可進行下列操作： s->next=_ _ _ _； p->next=s； tem

24、p=p->data； p->data=_ _； s->data=_ _ _；四、應(yīng)用題1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點)。答： 2何時選用順序表，何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？答： 3在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點？具體的移動次數(shù)取決于哪兩個因素？答： 4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？答： 5雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某個結(jié)點，不知道頭指針，能否將結(jié)點*p 從相應(yīng)的鏈表中刪除？若可以，其時間復(fù)雜度各為多少？答： 6下列算法的功能是什么？ LinkList *testl(LinkList

25、 *L) /L是無頭結(jié)點的單鏈表 LinkList *q，*p； if(L&&L->next) q=L； L=L->next； p=L; while(p->next) p=p->next； p->next=q; q->next=NULL；return L；答： 7如果有n個線性表同時共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會自動地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)？為什么？答： 8若線性表的總數(shù)基本穩(wěn)定，且很少進行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲結(jié)構(gòu)？為什么？答：五、算法設(shè)計題假設(shè)

26、算法中用到的順序表和鏈表結(jié)構(gòu)如下：#define maxsize 100;Typedef struct node1 datatype datamaxsize; int length SeqList;Typedef struct node2 datatype data; struct node2 *next LinkedList ;1試用順序表作為存儲結(jié)構(gòu)，實現(xiàn)將線性表(a0，a1，a2，an-1)就地逆置的操作，所謂“就地”是指輔助空間為O(1)。答：(1)順序表的就地逆置 (2)鏈表的就地逆置 2設(shè)順序表L是一個遞增(允許有相同的值)有序表，試寫一算法將x插入L中，并使L仍為一個有序表。答：

27、 3.設(shè)單鏈表L是一個遞減有序表，試寫一個算法將x插入其中后仍保持L的有序性。答：4. 試寫出在不帶頭結(jié)點的單鏈表的第i個元素之前插入一個元素的算法。答：5設(shè)A、B是兩個線性表，其表中元素遞增有序，長度分別為m和n。試寫一算法分別以順序存儲和鏈式存儲將A和B歸并成一個仍按元素值遞增有序的線性表C。答：6設(shè)指針la和lb分別指向兩個不帶頭結(jié)點的單鏈表的首結(jié)點，設(shè)計從表la中刪除第i個元素起共len個元素，并將這些元素插入到lb中第j個結(jié)點之前的算法。7單鏈表L是一個遞減有序表，試寫一高效算法，刪除表中值大于min且小于max的結(jié)點(若表中有這樣的結(jié)點)，同時釋放被刪結(jié)點空間，這里min和max是

28、兩個給定的參數(shù)。8編寫一個算法將一個頭結(jié)點指針為pa的單鏈表A分解成兩個單鏈表A和B，其頭結(jié)點指針分別為pa和pb，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素，而B鏈表中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序。9假設(shè)以兩個元素值遞增有序排列的線性表A、B分別表示兩個集合，要求另辟空間構(gòu)造一個線性表C，其元素為兩集合的交集，且表C中的元素值也遞增有序排列。用順序表實現(xiàn)并寫出C的算法。11假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點*s的直接前驅(qū)結(jié)點。12計算帶頭結(jié)點的循環(huán)鏈表的結(jié)點個數(shù)。13已知由單鏈表表示的線性表中，含有三

29、類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使得每個表中只含有同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。14、己知A、B和C為三個遞增有序的線性表，現(xiàn)要求對A表進行如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法(注：題中未特別指明同一表中的元素值各不相同)。15雙循環(huán)鏈表中，設(shè)計滿足下列條件的算法。 (1)在值為x的結(jié)點之前插入值為y的結(jié)點。(2)刪除值為x的結(jié)點。16設(shè)有一個雙循環(huán)鏈表，其中有一結(jié)點的指針為p，編寫算法將p與其右邊的一個結(jié)點進行交換。17設(shè)有一個雙鏈

30、表，每個結(jié)點中除有prior、data和next三個域外，還有一個可訪問頻度域freq，在鏈表啟用之前，其初始值均為0。每當(dāng)鏈表進行一次LocateNode(L，x)操作時令元素值為x的結(jié)點中freq域的值加l，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減次序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode操作的算法。18給出用單鏈表存儲多項式的結(jié)構(gòu)，并編寫一個按指數(shù)值遞增次序輸入所產(chǎn)生的多項式鏈表的過程。19根據(jù)上題的多項式鏈表結(jié)構(gòu)，編寫一個過程實現(xiàn)兩個多項式相加的運算。20約瑟夫環(huán)問題：任給正整數(shù)n、k，按下述方法可得排列1，2，n的一個置換：將數(shù)字l，2，n

31、環(huán)形排列，按順時針方向從1開始計數(shù)；計滿k時輸出該位置上的數(shù)字(并從環(huán)中刪去該數(shù)字)，然后從下一個數(shù)字開始繼續(xù)計數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。例如，n=10、k=3時，輸出的置換是3，6，9，2，7，1，8，5，10。分別以數(shù)組和以不帶頭結(jié)點的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu)解決上述問題。第三節(jié) 棧和隊列一、選擇題1設(shè)有一順序棧s，元素s1，s2，s3，s4，s5，s6依次入棧，如果6個元素出棧的順序是s2，s3，s4，s6，s5，s1，則棧的容量至少應(yīng)該是( )。 A2 B3 C5 D62若一個棧的輸入序列是a、b、c，則通過入棧、出棧操作可能得到a、b、c的不同排列個數(shù)為( )。 A

32、4 B5 C6 D73設(shè)有一順序棧已經(jīng)含有3個元素，如圖3-1所示，元素a4正等待入棧。以下序列中不可能出現(xiàn)的出棧序列是( )。 Aa3，a1，a4，a2 Ba3，a2，a4，a1 Ca3，a4，a2，a1 Da4，a3，a2，a14和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是( )。 A通常不會出現(xiàn)棧滿的情況 B通常不會出現(xiàn)?？盏那闆r C插入操作更容易實現(xiàn) D刪除操作更容易實現(xiàn)5若一個棧的輸入序列是1，2，3，4，n，輸出序列的第一個元素是n，則第i個輸出元素是( )。 A不確定 Bn-i Cn-i+1 Dn-i-16以下說法正確的是( )。 A因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不

33、會出現(xiàn)棧滿情況 B因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 C對于鏈棧而言，在棧滿狀態(tài)下，如果再進行入棧操作，則會發(fā)生“上溢” D對于順序棧而言，在棧滿狀態(tài)下，如果再進行入棧操作，則會發(fā)生“下溢”7順序隊列的入隊操作應(yīng)為( sq.rear初值為-1 )。 Asq.rear=sq.rear+1；sq.datasq.rear=x; Bsq.datasq.rear=x；sq.rear=sq.rear+1； Csq.rear=(sq.rear+1)maxsize；sq.datasq.rear+1=x; Dsq.datasq.rear=x；sq.rear=x; sq.rear=

34、(sq.rear+1)maxslze；8循環(huán)隊列的入隊操作應(yīng)為(sq.rear初值為-1 )。 Asqrear=sqrear+1；sqdatasqrear=x Bsqdatasqrear=x；sqrear=sqrear+l； Csqrear=(sqrear+1)maxsize；sqdatasqrear=x； Dsqdatasqrear=x；sqrear=(sqrear+1)maxsize；9順序隊列的出隊操作為(sq. front初值為-1 )。 Asqfront=(sqfront+1)maxsize； Bsqfront=sqfront+1； Csqrear=(sqrear+1)maxsize

35、； Dsqrear=sqrear+1;10循環(huán)隊列的出隊操作為(sq. front初值為-1 )。 Asqfront=(sqfront+1)maxsize； Bsqfront=sqfront+1； Csqrear=(sqrear+1)maxsize； Dsqrear=sqrear+l；11循環(huán)隊列的隊滿條件為( )。 A(sqrear+1)maxsize=(sqfront+1)maxsize； B(sqrear+1)maxsize=sqfront+1； C(sqrear+1)maxsize=sqfront； Dsqrear=sqfront；12循環(huán)隊列的隊空條件為( )。 A(sqrear+1

36、)maxsize=(sqfront+1)maxsize； B(sqrear+1)maxsize=sqfront+1； C(sqrear+1)maxsize=sqfront； Dsqrear=sqfront；13如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時( )。 A必須判別棧是否滿 B判別棧元素的類型 C必須判別棧是否空 D對棧不做任何判別14，向一個棧頂指針為Top的鏈棧中插入一個s所指結(jié)點時，其操作步驟為( )。 ATop->next=s； Bs->next=Top->next；Top->next=s； Cs->next=Top；Top=s； Ds->nex

37、t=Top；Top=Top->next；15從棧頂指針為Top的鏈棧中刪除一個結(jié)點，并將被刪結(jié)點的值保存到x中，其操作步驟為( )。 Ax=Top->data；Top=Top->next； BTop=Top->next；x=Top->data； Cx=Top；Top=Top->next； Dx=Top->data；16在一個鏈隊中，苕f、r分別為隊頭、隊尾指針，則插入s所指結(jié)點的操作為( )。 Af->next=s；f=s； Br->next=s；r=s； Cs->next=r；r=s； Ds->next=f；f=s；17一個棧

38、的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是( )。 Ae，d，c，b，a Bd，e，c，b，a Cd，c，e，a，b Da，b，c，d，e18一個隊列的入隊序列是1，2，3，4，則隊列可能的輸出序列是( )。 A4，3，2，1 *B1，2，3，4 C1，4，3，2 D3，2，4，119設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用( )數(shù)據(jù)結(jié)構(gòu)最佳。 A線性表的順序存儲結(jié)構(gòu) B棧 C隊列 D線性表的鏈式存儲結(jié)構(gòu)二、判斷題1在順序棧棧滿情況下，不能再入棧，否則會產(chǎn)生“上溢”。2與順序棧相比，鏈棧的一個優(yōu)點是插入和刪除操作更加方便。3若一個棧的輸入序列為1，2，3，n，其輸出

39、序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=i+1(i=1，2，n)。4在鏈隊中，即使不設(shè)置尾指針也能進行入隊操作。5在對鏈隊(帶頭指針)做出隊操作時，不會改變front指針的值。6循環(huán)隊列中元素個數(shù)為rear-front。7一個棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到4,3,1,28一個棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到1,2,3,4。9若以鏈表作為棧的存儲結(jié)構(gòu)，則入棧需要判斷棧是否滿10若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。三、填空題1向一個棧頂指針為Top的鏈棧中插入一個s所指的結(jié)點時，其進行的操作是_ _；Top =s

40、；_。2從棧頂指針為Top的鏈棧中刪除一個結(jié)點，并將結(jié)點保存在x中，進行的操作是_ _ _；Top=Top->next。3在具有n個單元的循環(huán)隊列中，隊滿時共有_n-1_個元素。4假設(shè)以S和X分別表示入棧和出棧操作，則對輸入序列a，b，c，d，e進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為_ _。5設(shè)有數(shù)組Am作為循環(huán)隊列的存儲空間，front為隊頭指針，rear為隊尾指針，則元素x執(zhí)行入隊操作的語句是_ _； Arear=x。6在一個鏈隊中，如果f、r分別為隊頭、隊尾指針，則插入s所指結(jié)點的操作是_ _。7棧的邏輯特點是_ _，隊列的邏輯特點是_ _，二者的共同特點是_

41、_。8_ _可以作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。9在隊列中，新插入的結(jié)點只能添加到_ _。10鏈隊在一定范圍內(nèi)不會出現(xiàn)_ _的情況。當(dāng)lqfront=lqrear時，隊中無元素，此時_ _。11設(shè)一個鏈棧的棧頂指針為ls，棧中結(jié)點的格式為data:next，?？盏臈l件是_ _；如果棧不為空，則出棧操作為p=ls; _ _；free(p)。12對帶有頭結(jié)點的鏈隊lq，判定隊列中只有一個數(shù)據(jù)元素的條件是_ _。 13設(shè)有一個空棧，現(xiàn)在輸入序列為1，2，3，4，5，經(jīng)過push，push，pop，push，pop，push后，棧頂指針?biāo)冈厥莀 _。14設(shè)用一維數(shù)組An來表示一個棧，令A(yù)0為棧

42、底。用整型變量t來指示當(dāng)前棧頂?shù)奈恢?，At為棧頂元素。往棧中壓入一個新元素時，變量t的值_ _，從棧中彈出一個元素時，變量t的值_ _。設(shè)空棧時，輸入序列a，b，c經(jīng)過push，pop，push，push，pop操作后，從棧中彈出的元素是_ _。四、應(yīng)用題2設(shè)有字符串為3*-y-a/y2，試利用棧寫出將其轉(zhuǎn)換為3y-*ay2/-的操作過程。假定用X代表掃描該字符串過程中順序取一個字符入棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS。答： 3設(shè)有一個輸入序列a，b，c，d，元素經(jīng)過一個棧到達輸出序列，而且元素一旦離開輸入序列就不能再

43、回到輸入序列，試問經(jīng)過這個棧后可以得到多少種輸出序列?答： 4按照運算符優(yōu)先法，畫出對下面算術(shù)表達式求值時，操作數(shù)棧和運算符棧的變化過程：9-2*4+(8+1)/3。答：5鏈棧中為何不設(shè)置頭結(jié)點?答： 第四節(jié) 數(shù)組一、選擇題1數(shù)組通常具有的兩種基本操作是( )。 A建立和刪除 B索引和修改 C查找和修改 D查找和索引2二維數(shù)組A11，6采用行序為主序方式存儲，每個數(shù)據(jù)元素占4個存儲單元，且A0，0的存儲地址是1000，則A8，4的存儲地址是( )。 A1208 B1212 C1368 D13643對矩陣壓縮存儲是為了( )。 A方便運算 B節(jié)省空間 C方便存儲 D提高運算速度4稀疏矩陣的壓縮存

44、儲方法通常有兩種，即( )。 A二元數(shù)組和三元數(shù)組 B三元組和散列 C三元組和十字鏈表 D散列和十字鏈表二、判斷題 1數(shù)組是同類型值的集合。 2數(shù)組是一組連續(xù)的內(nèi)存單元。 3數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。 4插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。 5使用三元組表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間。三、填空題 1二維數(shù)組A10， 20采用列序為主序方式存儲，每個元素占一個存儲單元，并且A1，1的存儲地址是200，則A6，12的地址是_ _。 2有一個10階對稱矩陣A采用壓縮存儲方式(以行序為主序方式)存儲其下三

45、角元素，且第一個元素A0，0的存儲地址為1，則A4，5的地址是_ _，A8，3的地址是_ _。 3下三角矩陣AN,N的下三角元素已壓縮到一維數(shù)組SN(N+1)2中，若按行序為主序存儲，則Ai，j對應(yīng)的S中的存儲位置是_ _ _。四、應(yīng)用題1假設(shè)有二維數(shù)組A6,8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始地址(基地址)為1000，計算：(1)數(shù)組A的容量。(2)按行優(yōu)先方式存儲時，元素A1，4的地址。(3)按列優(yōu)先方式存儲時，元素A4,7的地址。答： 2設(shè)有三對角矩陣An，n，將其三條對角線上的元素逐行存放于數(shù)組B3n-3中，使得Bk=Ai,j，求： (1)用i，j表示k的下

46、標(biāo)變換公式。 (2)用k表示i，j的下標(biāo)變換公式。答： 3畫出圖5-2所示的稀疏矩陣A的三元組表和十字鏈表。答：4用三元組表表示圖5-3所示的稀疏矩陣的轉(zhuǎn)置矩陣。答：第五節(jié) 樹(樹根結(jié)點的高度為1)一、選擇題1以下說法錯誤的是( )。 A樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前驅(qū) B線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼 C二叉樹與樹是兩種不同的數(shù)據(jù)結(jié)構(gòu) D樹(及一切樹形結(jié)構(gòu))是一種“分支層次結(jié)構(gòu)2以下說法錯誤的是( )。 A二叉樹可以是空集 B二叉樹的任一結(jié)點都有兩棵子樹 C二叉樹與樹具有相同的樹形結(jié)構(gòu) D、二叉樹中任一結(jié)點的兩棵子樹有次序之分3以下說法錯誤的是( )。 A完全二叉樹上結(jié)點

47、之間的父子關(guān)系可由它們編號之間的關(guān)系來表達 B在三叉鏈表上，二叉樹的求雙親操作很容易實現(xiàn) C在二叉鏈表上，求根以及求左、右孩子等操作很容易實現(xiàn) D在二叉鏈表上，求雙親操作的時間性能很好4以下說法錯誤的是( )。 A一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近 B哈夫曼樹中沒有度數(shù)為1的分支結(jié)點 C若初始森林中共有n棵二叉樹，最終求得的哈夫曼樹共有2n-1個結(jié)點 D若初始森林中共有n棵二叉樹，進行2n-1次合并后才能剩下一棵最終的哈夫曼樹5深度為6的二叉樹最多有( )個結(jié)點。 A64 B63 C32 D316將含有41個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，后面按從上到下、從左到右的順序?qū)?/p>

48、結(jié)點編號，那么編號為21的雙親結(jié)點編號為( )。 A10 B11 C41 D207任何一棵二叉樹的葉結(jié)點在其前序、中序、后序遍歷序列中的相對位置( )。 A肯定發(fā)生變化 B有時發(fā)生變化 C肯定不發(fā)生變化 D無法確定8設(shè)二叉樹有n個結(jié)點，則其深度為( )。 An-1 Bn Clog2n+1 D無法確定9設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含結(jié)點總數(shù)最少( )個。 Ak+l B2k C2k-1 D2k+110下列說法正確的是( )。 A樹的前序遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同 B樹的前序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C樹的后序遍歷序列與其對應(yīng)的二叉

49、樹的前序遍歷序列相同 D樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同11下列說法中正確的是( )。 A任何一棵二叉樹中至少有一個結(jié)點的度為2 B任何一棵二叉樹中每個結(jié)點的度都為2 C任何一棵二叉樹中的每個結(jié)點的度肯定等于2 D任何一棵二叉樹中的每個結(jié)點的度都可以小于212一棵二叉樹滿足下列條件：對任意結(jié)點，若存在左、右子樹，則其值都小于它的左子樹上所有結(jié)點的值，而大于右子樹上所有結(jié)點的值?，F(xiàn)采用( )遍歷方式就可以得到這棵二叉樹所有結(jié)點的遞減序列。 A前序 B中序 C后序 D層次13設(shè)森林T中有4棵樹，結(jié)點個數(shù)分別是n1、n2、n3、n4，當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，根結(jié)點的右子樹上有

50、( )個結(jié)點。 An1-1 Bn1 Cn1+n2+n3 D n2+n3+n414對含有( )個結(jié)點的非空二叉樹，采用任何一種遍歷方式，其結(jié)點訪問序列均相同。 A0 B1 C2 D不存在這樣的二叉樹15如圖6-1所示的二叉樹的中序遍歷序列是( )。 Aabcdgef Bdfebagc Cdbaefcg Ddefbagc16已知某二叉樹的后序遍歷序列是deacb，中序遍歷序列是deabc，它的前序遍歷序列是( )。 Aacbed Bbaedc Cdceab Dcedba17如果T1是由有序樹轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點的前序就是T1中結(jié)點的( )。 A前序 B中序 C后序 D層次序18某二叉樹的前序遍歷的結(jié)點訪問順序是abdgcefh，中序遍歷的結(jié)點訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是( )。 Abdgcefha Bgdbecfha Cbdgechfa Dgdbehfca19在圖6-2中的二叉樹中，( )不是完全二叉樹。20樹最適合用來表示( )。 A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之