數據結構練習題1

1、一、判斷1.在順序存儲的線性表中，邏輯上相鄰的兩個數據元素在物理位置上并不一定緊鄰。2.單鏈表設置頭結點的目的是為了簡化運算。3.從循環(huán)單鏈表的任一結點出發(fā)，可以找到表中所有結點。4.數據的存儲結構是數據的邏輯結構的存儲映象，不僅要存儲數據元素的值，還要存儲元素之間的相互關系。5.用順序表來存儲線性表時，不需要另外開辟空間來保存數據元素之間的相互關系。6.從循環(huán)單鏈表的某一結點出發(fā)，只能找到它的后繼結點，不能找到它的前趨結點。7.在單鏈表中，頭結點是必不可少的。8. 在單鏈表中，要取得某元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。9. 在一個設有頭指針和尾指針的單鏈表中,

2、執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關。10. 順序存儲方式只能用于存儲線性結構。11.棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。二、選擇1若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節(jié)省操作時間的存儲方式是( )。A）單鏈表B）雙鏈表C)單循環(huán)鏈表 D)順序表2.下面程序段的時間復雜度是（）。for (i=0;i<n;i+) for(j=0;j<n;j+)Aij=1;A)O(n) B)O(n+n+1) C)O(n+n) D)O(n*n)3設一個棧的輸入序列為12345,則借助一個棧所得到的輸出序列不可能是（）。A)54321 B）45321

3、C)43512 D)123454設單鏈表中指針p指向結點A，要刪除A之后的結點（若存在），則修改指針的操作為( )。A）p>next=p>next>nextB）p=p>next C）p=p>next>nextD）p>next=p5算法分析的兩個主要方面是（ ）。A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數據復雜性和程序復雜性6.隊列操作的原則是（ ）。A）先進先出 B）后進先出 C）只能進行插入 D）只能進行刪除7. 數據結構是（）。A一種數據類型 B數據的存儲結構C一組性質相同的數據元素的集合 D相互之間存在一種或

4、多種特定關系的數據元素的集合8. 若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則可能出現的出棧序列為（）。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，19.求單鏈表中當前結點的后繼和前驅的時間復雜度分別是（）。AO（n）和O（1）BO（1）和O（1）CO（1）和O（n） DO（n）和O（n） 10.已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為( )。A.q->next=s->next；s->next=p； B.s-

5、>next=p；q->next=s->next；C.p->next=s->next；s->next=q； D.s->next=q；p->next=s->next；11. 設循環(huán)隊列中數組的下標范圍是1n，其頭尾指針分別為f和r，則其元素個數為( )。 A. r-fB. r-f+1 C. (r-f)mod n+1 D. (r-f+n)mod n12. 算法是指(   )。A為解決問題而編寫的計算機程序   B為解決問題而采取的方法與步驟C為解決問題而需要采用的計算機語言  D為解決問題而采用的

6、計算方法13設棧S的初始狀態(tài)為空，現有5個元素組成的序列1，2，3，4，5，對該序列在S棧上依次進行如下操作(從序列中的1開始，出棧后不再進棧)：進棧、進棧、進棧、出棧、進棧、出棧、進棧。試問出棧的元素序列是(    )。A5，4，3，2，1 B2，1   C2，3    D3，413設指針變量 p 指向單鏈表中結點 A ，若刪除單鏈表中結點 A ，則需要修改指針的操作序列為（ ）。 Aq= p->next ； p->data=q->data ； p->next=q->nex

7、t ； free(q) ； Bq= p->next ； q->data=p->data ； p->next=q->next ； free(q) ； Cq= p->next ； p->next=q->next ； free(q) ； Dq= p->next ； p->data=q->data ； free(q) ； 14. 下面關于線性表的描述，錯誤的是(    )。A棧是線性表的一種B任給一索引i（1<=i<=表中元素個數），就能在線性表中唯一確定一個元素C線性表的任一元素都有前驅和后繼 D線性表

8、是一個線性序列15. 以下數據結構中，（ ）是非線性數據結構。A樹 B字符串 C隊 D棧16設計一個判別表達式中左，右括號是否配對出現的算法，采用（ ）數據結構最佳。A線性表的順序存儲結構 B. 隊列 C. 線性表的鏈式存儲結構 D. 棧17. 設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為（ ）。Ap->next=p->next->next B p=p->nextC p=p->next->next Dp->next=p18. 數據結構中，與所使用的計算機無關的是數據的（ ）結構。A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲

9、19. 向一個帶頭結點的棧頂指針為ls的鏈棧中插入一個s所指結點時，則執(zhí)行（ ）。 A）ls->next=s; B） s->next=ls->next;ls->next=s; C) s->next=ls;ls=s; D) s->next=ls;ls=ls->next; 20. 對一個算法的評價，不包括如下( )方面的內容。 A.健壯性和可讀性 B.并行性 C.正確性 D.時空復雜度21.有六個元素6，5，4，3，2，1 的順序進棧，下列哪一個不是合法的出棧序列（ ）。A.5 4 3 6 1 2 B.4 5 3 1 2 6

10、C.3 4 6 5 2 1 D.2 3 4 1 5 622. 設數組A0M-1作為循環(huán)隊列Q的存儲空間，f為頭指針，r為尾指針，刪除隊頭元素的語句為（ ）。  A.f=f+1    B.f=(r+1) % M C.f=(f+1) % M  D.f=(f+1) % (M+1)23. 以下數據結構中，（ ）是非線性數據結構。A.樹 B.字符串 C.隊 D.棧24.下面關于線性表的敘述中，錯誤的是哪一個（ ）。A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 B.線性表采用順序存儲，便于進行插入和刪除操作。

11、C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。 D.線性表采用鏈接存儲，便于插入和刪除操作。25. 在棧操作中,輸入序列為A,B,C,D,不可能得到的輸出序列是( )。A.A,B,C,D B.D,C,B,A C.A,C,D,B D.C,A,B,D26. 鏈棧與順序棧相比有一個明顯的優(yōu)點，即（ ）。A.占用存儲空間更少 B.通常不會出現棧滿的情況 C.不會出現?？盏那闆r D.程序執(zhí)行速度更27. 對線性表，在下列哪種情況下應當采用鏈表表示（ ）。A.經常需要隨機的存取元素 B.經常需要插入刪除操作 C.表中元素需要占據一片連續(xù)的存儲空間 D.表中元素個數不變28. 下列程序段的時間復雜度為

12、（ ）。for(i=0； i<m； i+) for(j=0； j<t； j+) cij=0；for(i=0； i<m； i+) for(j=0； j<t； j+) for(k=0； k<n； k+) cij=cij+aik*bkj；(A) O(m*n*t)(B) O(m+n+t)(C) O(m+n*t)(D) O(m*t+n)29設順序線性表中有n個數據元素，則刪除表中第i個元素需要移動（ ）個元素。(A) n-i(B) n+l -i(C) n-1-i(D) i30. 設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作

13、序列為（ ）。(A) p->next=s； s->prior=p； p->next->prior=s； s->next=p->next；(B) s->prior=p；s->next=p->next；p->next=s； p->next->prior=s；(C) p->next=s； p->next->prior=s； s->prior=p； s->next=p->next；(D) s->prior=p；s->next=p->next；p->next->pri

14、or=s； p->next=s；31. 設輸入序列1、2、3、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。(A) n-i(B) n-1-i(C) n+l -i(D) 不能確定三、填空1四類基本邏輯結構是集合、（）、（）、圖狀結構。2順序存儲結構是通過（ ）表示元素之間的關系的;鏈式存儲結構是通（ ）表示元素之間的關系的。 3僅允許在表的一端進行插入和刪除運算的線性表被稱為（）。4.有一在順序隊列中做入隊運算時，應先判別隊列是否（）；在做出隊運算時，應先判別隊列是否（）。5.不含頭結點的單鏈表，頭指針為head，則判斷其為空的條件為（ ）。6棧和隊列是

15、運算（）的線性表。7. 假設帶頭結點的非空單循環(huán)鏈表中僅設尾指針L，則在第1個數據元素結點之前插入指針s所指結點的語句依次是 ； 。8.無表頭結點的鏈隊列Q為空的條件是 。9. 表長為n的順序表中插入元素平均移動的次數為 。10. 在一個長度為n的單鏈表L中，刪除鏈表中p所指結點的后繼結點的時間復雜度為 。11約定棧S的進棧序列為p1,p2,p3pn，如果第一個出棧元素為pn,則第i個出棧元素為 。12假設為循環(huán)隊列分配的向量空間為Q20，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為 。13. 設順序循環(huán)隊列Q0：m-1的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當前隊

16、頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的位置，則出隊列的語句為F = 。14. 計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數為 。 for(i=l；i<=n-l；i+) for(j=1;j>=i;j-) s; 15. 長度為n的順序表，刪除元素平均移動的次數為 。16. 在順序表中訪問任意一結點的時間復雜度均為（ ），因此，順序表是一種（ ）存取的數據結構。17在單鏈表中，除了首結點外，任一結點的存儲位置由（）指示。18. 設循環(huán)隊列空間n=40，隊尾指針rear=6，隊頭指針front=25，則此循環(huán)隊列中當前元素的數目是（）。19. 在下面的程序段中，對賦值的語句的頻度

17、為（ ）（表示為n的函數） for(i=1;i<=n;i+)for(j=1;j<=n;j+)x=x+1；20. 在做進棧運算時應先判別棧是否（ ）;在作退棧運算時應先判別棧是否( )；當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為( )。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的( )分別設在內存空間的兩端，這樣只有當( )時才產生溢出。21. .在雙向鏈表中，每個結點都有兩個指針域，一個指向（ ），另一個指向（ ）。22. 循環(huán)隊列的引入，是為了克服（ ）。23. 若有一個大小為6的數組來實現循環(huán)隊列，且當前的rear和f

18、ront的值為0和3，當從隊列中刪除1個元素后，front的值為 ，再加2個元素后，rear的值為 。四、應用題1.簡述順序表和鏈表存儲方式的特點。2. 簡要敘述循環(huán)隊列的數據結構，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊首指針與隊尾指針的值。3. 對線性表的單鏈表，循環(huán)鏈表，雙向鏈表三種存儲結構的進行描述，并給出它們的區(qū)別。五、算法設計1.設有一個由正整數組成的無序單鏈表，編寫完成下列功能的算法： （1）找出最大值結點，且打印該數值； （2）若該數值是偶數，則將其與直接后繼結點的數值交換；單鏈表類型描述：typedef struct Node    ElemType dat

19、a；  struct Node  * next；Node, *LinkList； 2. 假設以帶頭結點的單鏈表表示非遞減有序表，設計一算法刪除表中所有值大于min且小于max（假設min<max）同時釋放結點空間。3. 設計在單鏈表中刪除值相同的多余結點的算法。 4. 在帶頭結點的單鏈表head的結點a之后插入新元素x。5. 假設有一個帶頭結點的循環(huán)鏈表L的長度大于1，試編寫算法在此鏈表中刪除尾結點。鏈表類型描述：typedef struct Node    ElemType data；  struct Node  * next；Node, *LinkList； 6. 設頭指針為head，編寫算法實現帶頭結點的單鏈表head的就地逆置，即利用原帶頭結點的單鏈表 head的結點空間把數據元素序列(a1，a2，an)逆置為(an，