數(shù)據(jù)結(jié)構(gòu)習題及答案

第一章1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C ）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)l 2. 在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機無關(guān)的是( A )A. 邏輯結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯和存儲結(jié)構(gòu) D. 物理結(jié)構(gòu)3.下面程序的時間復(fù)雜度為_O（mn）_。 for (int i=1; i=m; i+) for (int j=1; jnext=null C head-next=head D head!=nulll 3.在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（D）A 單鏈表 B 雙鏈表 C 循環(huán)鏈表 D 順序表l 4.對于只在表的首、尾兩端進行手稿操作的線性表，宜采用的存儲結(jié)構(gòu)為(C)A 順序表 B 用頭指針表示的單循環(huán)鏈表 C 用尾指針表示的單循環(huán)鏈表 D 單鏈表l 5.在一個具有n 個結(jié)點的有序單鏈表中插入一個新的結(jié)點，并保持鏈表元素仍然有序，則操作的時間復(fù)雜度為( D )A O(1) B O(log2n) C O(n2) D O(n)l 6.在一個長度為n (n1)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行(B)操作與鏈表的長度有關(guān)A 刪除單鏈表中第一個元素 B 刪除單鏈表中最后一個元素 C 在第一個元素之前插入一個新元素 D 在最后一個元素之后插入一個新元素l 7.與單鏈表相比，雙向鏈表的優(yōu)點之一是(D)A 插入刪除操作更簡單 B 可以進行隨機訪問 C 可以省略表頭指針或表尾指針 D 順序訪問相鄰結(jié)點更容易l 8.若list是某帶頭結(jié)點的循環(huán)鏈表的頭結(jié)點指針，則該鏈表最后那個鏈結(jié)點的指針域(頭結(jié)點的地址)中存放的是( B )A list的地址 B list的內(nèi)容 C list指的鏈結(jié)點的值 D 鏈表第一個鏈結(jié)點的地址l 9.若list1和list2分別為一個單鏈表與一個雙向鏈表的第一個結(jié)點的指針，則( B )A list2比list1占用更多的存儲單元 B list1與list2占用相同的存儲單元 C list1和list2應(yīng)該是相同類型的指針變量 D 雙向鏈表比單鏈表占用更多的存儲單元10.鏈表中的每個鏈結(jié)點占用的存儲空間不必連續(xù)，這句話正確嗎？ (不正確)11. 某線性表采用順序存儲結(jié)構(gòu)，元素長度為4，首地址為100，則下標為12的（第13個）元素的存儲地址為148。V 100+4*12=14811.在順序表的（ 最后一個結(jié)點之后 ）插入一個新的數(shù)據(jù)元素不必移動任何元素。12.若對線性表進行的操作主要不是插入刪除，則該線性表宜采用（ 順序 ）存儲結(jié)構(gòu)，若頻繁地對線性表進行插入和刪除操作，則該線性表宜采用( 鏈 )存儲結(jié)構(gòu)。13、一個順序表所占用存儲空間的大小與（B）無關(guān)。A表的長度 B.元素的存放順序 C. 元素的類型 D.元素中各的類型l 14、設(shè)存儲分配是從低地址到高地址進行的。若每個元素占用4個存儲單元，則某元素的地址是指它所占用的單元的（A）。A. 第1個單元的地址 B. 第2個單元的地址 C. 第3個單元的地址 D. 第4個單元的地址 15、若線性表采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第1個元素的存儲地址為100，則第12個元素的存儲地址是（ B）。A. 112 B. 144 C.148 D. 412 l 16、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在表的第i個位置插入一個數(shù)據(jù)元素，i的合法值應(yīng)該是( D )。A. i0 B.i=n C.1=i=n D. 1=i0 B.y=n C.1=i=n D. d=inext=p; p-next=q; B. q-next=p-next; p-next=q; C. q-next=p-next; p =q; D. p-next=q; q-next=p; 25、若刪除非空線性鏈表中由p所指的鏈結(jié)點的直接后繼鏈結(jié)點的過程過程是依次執(zhí)行（ B）。A. r=p-next; p-next=r; free(r);B. r=p-next; p-next=r-next; free(r); C. r=p-next; p-next=r-next; free(p); D. p-next=p-next-next; free(p); 26、在非空雙向循環(huán)鏈表中由q所指的鏈結(jié)點后面插入一個由p所指的鏈結(jié)點的操作依次為p-prior=q; p-next=q-next;q-next=p;（ C ）。A. q-prior=p B. q-next-prior=p C. p-next-prior=p; D. p-prior-next=p; 27、在非空雙向循環(huán)鏈表中由q所指的鏈結(jié)點前面插入一個由p所指的鏈結(jié)點的操作依次為p-next=q; p-prior=q-prior;q-prior=p;（ D ）。A.q-next=p; B. q-prior-next=p; C. p-next-prior=p; D. p-prior-next=p; 28、順序存儲的線性表(a1,a2,an),在任一結(jié)點前插入一個新結(jié)點時所需移動結(jié)點的平均次數(shù)為（ D ）。A. n B. n/2 C. n+1 D. (n+1)/2 29、在長度為n的順序表的第i（1in+1）個位置上插入一個元素，元素的移動次數(shù)是( A )。A. n-i+1 B. n-i C. i D. i-1 30、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（ D）。A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表 D. 順序表 31、在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（ C ）。A. 數(shù)據(jù)元素的相鄰地址表示 B. 數(shù)據(jù)元素在表中的序號表示 C. 指向后繼元素的指針表示 D. 數(shù)據(jù)元素的值表示 25、假設(shè)指針p指向單鏈表中的某一結(jié)點，若把p指針后面的結(jié)點刪除，只需修改下列哪個指針值即可（ ）。 Ap=p-next; Bp-next=p-next-next Cp=p-next-next; Dp-next=p; 26、在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針P所指向的結(jié)點，則執(zhí)行(D )。Aq-nextp-next；p-nextq Bp-nextq-next；qp；Cq-nextp-next；p-nextq；Dp-nextq-next；q-nextp；27、構(gòu)造一個空的線性表L用（A ）A.InitList(&L)B.DestroyList (&L) C.ListEmpty(L)D.ClearList(&L)第三章1、棧和隊列的共同點是（ C ）A. 都是先進后出 B. 都是先進先出在 C. 只允許在端點處插入和刪除元素D. 沒有共同點2、一個棧的進棧順序是a,b,c,d,e，則棧的出棧順序不可能是（ C ）A. edcba B.decba C. dceab D. adcbe 3、設(shè)n個元素的進棧序列為1,2,3,n，出棧序列為p1,p2,p3,pn，若p1=n，則pi(1=inext=top D.top-next=p 19、若非空堆棧采用鏈式存儲結(jié)構(gòu)，棧頂指針為top，刪除堆棧一個元素的過程是依次執(zhí)行p= top；（ B ）; free(p)A.top=p B. top=p-next C. p=top-next D. p=p-next 20、若隊列采用鏈式存儲結(jié)構(gòu)，隊頭元素指針與隊尾元素指針分別為front和rear，向隊列中插入一個由p所指的新結(jié)點的過程是依次執(zhí)行：（ C ）;rear=p;A. rear=p B. front=p C. rear-next=p D. front-next=p 21、若非空隊列采用鏈式存儲結(jié)構(gòu)，隊頭元素指針與隊尾元素指針分別為front和rear，刪除隊列的一個元素的過程是依次執(zhí)行：p=front; ( D ); free(p)A.rear=p B. rear=p-next C. p-next=rear D. front=p-next 22、在循環(huán)隊列中，若front與rear分別表示隊頭元素和隊尾元素的位置，則判斷循環(huán)隊列隊空的條件是（ C ）。A. front=rear+1 B. rear=front+1 C. front=rear D. front=rear=0 23、若描述某循環(huán)隊列的數(shù)組為為CircleM ，當循環(huán)隊列滿時，隊列中有（ B ）個元素。A. M B. M-1 C. M+1 D. M+2 24、在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（ D ）結(jié)構(gòu)。A. 線性表 B.數(shù)組 C. 堆棧 D. 隊列 25、設(shè)計一個遞歸問題的非遞歸算法通常需要設(shè)置（ C ）結(jié)構(gòu)。A. 線性表 B.數(shù)組 C. 堆棧 D. 隊列 26