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

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

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

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

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

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

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

8、=n) i=i*2； _ _2敘述算法的定義及其重要特性。3簡述下列術語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結構，數(shù)據(jù)對象。4邏輯結構與存儲結構是什么關系？5將數(shù)量級210，n，n2，n3，nlog2n，log2n，2n，n!，(23)n，n23按增長率進行排列。6設有數(shù)據(jù)邏輯結構為：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>，畫出這個邏輯結構

9、的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？7設有如圖1.1所示的邏輯結構圖，給出它的邏輯結構，并說出它是什么類型的邏輯結構。8分析下列程序的時間復雜度(設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設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線性結構中的一個結點代表一個( )。 A數(shù)據(jù)元素 B數(shù)據(jù)項 C數(shù)據(jù) D數(shù)據(jù)結構2線性表L=(a1，a2，ai，an)，下列說法正確的是( )。 A每個元素都有一個直接前驅和直接后繼 B線性表中至少要有一個元素 C表中諸元素的排列順序必須是由小到大或由大到小的 D除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接

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

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

13、單循環(huán)鏈表head的尾結點*p滿足( )。 Ap->next=NULL Bp=NULL Cp->next=head Dp=head11在雙循環(huán)鏈表的*p結點之后插入*s結點的操作是( )。 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結點是*p結點的前驅結點，若在*q和*p之間插入結點*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結點不是最后

15、結點。在*p之后插入結點*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個元素的前驅元素，則采用( )存儲方式最節(jié)省時間。 A順序表 B. 單鏈表 C雙鏈表 D單循環(huán)鏈表15設rear是指向非空帶頭結點的單循環(huán)鏈表的尾指針，則刪除表頭結點的操作可表示為( )。 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結點的后繼結點，則執(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設指針p指向雙鏈表的某一結點，則雙鏈表結構的對稱性可用( )式來刻畫。 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)鏈表中，將頭指針改設為尾指針rear后，

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

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

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

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

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

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

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

25、 *L) /L是無頭結點的單鏈表 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)變化，線性表的總長度也會自動地改變。在此情況下，應選擇哪一種存儲結構？為什么？答： 8若線性表的總數(shù)基本穩(wěn)定，且很少進行插入、刪除操作，但要求以最快的方式存取線性表的元素，應該用哪種存儲結構？為什么？答：五、算法設計題假設

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

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

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

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

30、表，每個結點中除有prior、data和next三個域外，還有一個可訪問頻度域freq，在鏈表啟用之前，其初始值均為0。每當鏈表進行一次LocateNode(L，x)操作時令元素值為x的結點中freq域的值加l，并調整表中結點的次序，使其按訪問頻度的遞減次序排列，以便使頻繁訪問的結點總是靠近表頭。試寫一符合上述要求的LocateNode操作的算法。18給出用單鏈表存儲多項式的結構，并編寫一個按指數(shù)值遞增次序輸入所產(chǎn)生的多項式鏈表的過程。19根據(jù)上題的多項式鏈表結構，編寫一個過程實現(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ù)組和以不帶頭結點的、已知尾指針的單循環(huán)鏈表為存儲結構解決上述問題。第三節(jié) 棧和隊列一、選擇題1設有一順序棧s，元素s1，s2，s3，s4，s5，s6依次入棧，如果6個元素出棧的順序是s2，s3，s4，s6，s5，s1，則棧的容量至少應該是( )。 A2 B3 C5 D62若一個棧的輸入序列是a、b、c，則通過入棧、出棧操作可能得到a、b、c的不同排列個數(shù)為( )。 A

32、4 B5 C6 D73設有一順序棧已經(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)棧空的情況 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順序隊列的入隊操作應為( 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)隊列的入隊操作應為(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如果以鏈表作為棧的存儲結構，則出棧操作時( )。 A必須判別棧是否滿 B判別棧元素的類型 C必須判別棧是否空 D對棧不做任何判別14，向一個棧頂指針為Top的鏈棧中插入一個s所指結點時，其操作步驟為( )。 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的鏈棧中刪除一個結點，并將被刪結點的值保存到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所指結點的操作為( )。 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設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用( )數(shù)據(jù)結構最佳。 A線性表的順序存儲結構 B棧 C隊列 D線性表的鏈式存儲結構二、判斷題1在順序棧棧滿情況下，不能再入棧，否則會產(chǎn)生“上溢”。2與順序棧相比，鏈棧的一個優(yōu)點是插入和刪除操作更加方便。3若一個棧的輸入序列為1，2，3，n，其輸出

39、序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=i+1(i=1，2，n)。4在鏈隊中，即使不設置尾指針也能進行入隊操作。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若以鏈表作為棧的存儲結構，則入棧需要判斷棧是否滿10若以鏈表作為棧的存儲結構，則出棧需要判斷棧是否空。三、填空題1向一個棧頂指針為Top的鏈棧中插入一個s所指的結點時，其進行的操作是_ _；Top =s

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

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

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

43、回到輸入序列，試問經(jīng)過這個棧后可以得到多少種輸出序列?答： 4按照運算符優(yōu)先法，畫出對下面算術表達式求值時，操作數(shù)棧和運算符棧的變化過程：9-2*4+(8+1)/3。答：5鏈棧中為何不設置頭結點?答： 第四節(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ù)組是一種復雜的數(shù)據(jù)結構，數(shù)組元素之間的關系既不是線性的也不是樹形的。 4插入和刪除操作是數(shù)據(jù)結構中最基本的兩種操作，所以這兩種操作在數(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對應的S中的存儲位置是_ _ _。四、應用題1假設有二維數(shù)組A6,8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始地址(基地址)為1000，計算：(1)數(shù)組A的容量。(2)按行優(yōu)先方式存儲時，元素A1，4的地址。(3)按列優(yōu)先方式存儲時，元素A4,7的地址。答： 2設有三對角矩陣An，n，將其三條對角線上的元素逐行存放于數(shù)組B3n-3中，使得Bk=Ai,j，求： (1)用i，j表示k的下

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

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

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

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

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