第3章數(shù)據(jù)結(jié)構(gòu) 答案

1、第3章 數(shù)據(jù)結(jié)構(gòu)一、選擇題1. 圖形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種_B_。    A 一對多關(guān)系   B  多對多關(guān)系  C  多對一關(guān)系   D  一對一關(guān)系  2.算法分析的目的是_C_。    A 找出數(shù)據(jù)結(jié)構(gòu)的合理性  B  研究算法中的輸入和輸出的關(guān)系   C  分析算法的效率以求改進   D  分析算法的易懂性和文檔性 3.算法的時間復(fù)雜度與_A_

2、有關(guān)。    A 問題規(guī)模   B  計算機硬件性能   C  程序設(shè)計語言的類型或版本   D  算法設(shè)計者的水平  4.有下面的算法段：for (i=0; i<n; i+) k+;其時間復(fù)雜度為 B 。AO(1) BO(n) CO(log2n) DO(n2)5.計算機算法必須具備輸入、輸出和_C_。A、計算方法 B、排序方法C、解決問題的有限運算步驟 D、程序設(shè)計法6._B_是數(shù)據(jù)的基本單位。A、數(shù)據(jù)結(jié)構(gòu) B、數(shù)據(jù)元素 C、數(shù)據(jù)項 D、數(shù)據(jù)類型7.下面，對

3、非空線性表特點的論述， _C_ 是正確的。A所有結(jié)點有且只有一個直接前驅(qū)B所有結(jié)點有且只有一個直接后繼C每個結(jié)點至多只有一個直接前驅(qū)，至多只有一個直接后繼D結(jié)點間是按照1對多的鄰接關(guān)系來維系其邏輯關(guān)系的8.在順序表中，只要知道_D_，就可以在相同的時間內(nèi)求出任一結(jié)點的存儲地址。A、開始結(jié)點 B、終端結(jié)點 C、向量大小 D、基地址和結(jié)點大小9.在非空線性表中，有且只有一個直接前驅(qū)和一個直接后繼的結(jié)點是_C_。A、開始結(jié)點 B、終端結(jié)點 C、內(nèi)部結(jié)點 D、所有結(jié)點10.順序表中邏輯上相鄰的結(jié)點的物理位置為_A_。A、一定相鄰 B、不必相鄰 C、按某種規(guī)律排列 D、不要求11.一個向量第一個元素的存

4、儲地址是100，每個元素的長度為2，則第5個元素的地址是_B_。    A 110   B  108  C  100  D  120  12.鏈表不具有的特點是_A_。A、可以隨機訪問任何一個元素 B、插入和刪除元素不需要移動元素C、不必事先估計存儲空間 D、所需的存儲空間和鏈表長度無關(guān)13.數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種_D_。   A 順序存儲線性表   B  非順序存儲非線性表    

5、;C  順序存儲非線性表    D  非順序存儲線性表  14.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間_A_   A 分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針   B  只有一部分，存放結(jié)點值   C  只有一部分，存儲表示結(jié)點間關(guān)系的指針   D  分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)15.線性表在_B_ 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。   A 需經(jīng)常修改中的結(jié)點值 

6、;   B  需不斷對進行刪除插入    C  中含有大量的結(jié)點   D  中結(jié)點結(jié)構(gòu)復(fù)雜  16.線性鏈表不具有的特點是_A_ 。   A 隨機訪問   B  不必事先估計所需存儲空間大小   C  插入與刪除時不必移動元素   D  所需空間與線性表長度成正比 17.在長度為n的順序表中，往其第i個元素（1in）之前插入一個新的元素時，需要往后移動 _B_ 個元素

7、。An-iBn-i+1Cn-i-1Di18.在長度為n的順序表中，刪除第i個元素（1in）時，需要往前移動_A_個元素。An-iBn-i+1Cn-i-1Di19.往一個順序表的任一結(jié)點前插入一個新數(shù)據(jù)結(jié)點時，平均而言，需要移動_B_個結(jié)點。AnBn/2Cn+1D(n+1)/220.帶表頭結(jié)點的單鏈表Lk_h為空的判定條件是_B_ 。ALk_h = NULLBLk_h->Next = NULLCLk_h->Next = Lk_hDLk_h != NULL21.在一個單鏈表中，已知qtr所指結(jié)點是ptr所指結(jié)點的直接前驅(qū)?，F(xiàn)要在qtr所指結(jié)點和ptr所指結(jié)點之間插入一個rtr所指的結(jié)點

8、，要執(zhí)行的操作應(yīng)該是_C_。Artr->Next = ptr->Next;ptr->Next = rtr;Bptr->Next = rtr->Next;Cqtr->Next = rtr;rtr->Next = ptr;Dptr->Next = rtr;rtr->Next = qtr->Next;22.在單鏈表中，如果指針ptr所指結(jié)點不是鏈表的尾結(jié)點，那么在ptr之后插入由指針qtr所指結(jié)點的操作應(yīng)該是_B_ 。Aqtr->Next = ptr ;Bqtr->Next = ptr->Next ;ptr->Nex

9、t = qtr ; ptr->Next = qtr ;Cqtr->Next = ptr->Next ;Dptr->Next = qtr ;ptr = qtr ; qtr->Next = ptr ;23.棧與一般線性表的區(qū)別在于_B_。A、數(shù)據(jù)元素的類型不同 B、運算是否受限制C、數(shù)據(jù)元素的個數(shù) D、邏輯結(jié)構(gòu)不同24.棧的插入和刪除操作在_A_進行。A、棧頂 B、棧底 C、任意位置 D、指定位置25.一個順序棧一旦被聲明，其占用空間大小_A_。A、已固定 B、可以變化 C、不能固定 D、動態(tài)變化26.設(shè)有一個順序棧S，元素s1， s2， s3， s4， s5， s6

10、依次進棧，如果6個元素的出棧順序為s2， s3， s4， s6， s5， s1，則順序棧的容量至少應(yīng)為_B_   A 2  B  3   C  4  D  5  27.若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn)_C_種情況。   A 3，2，1  B  2，1，3   C  3，1，2   D  1，3，2  28.一個棧的入棧序列是abcde，則棧不可能的輸出序列是_C_。A、e

11、dcba B、decba C、dceab D、abcde29.隊列的插入操作是在_B_進行的。A、隊首 B、隊尾 C、隊前 D、隊后30.隊列的刪除操作是在_A_進行的。A、隊首 B、隊尾 C、隊前 D、隊后31.為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 _A_。 A.隊列      B.棧         C.線

12、性表     D.有序表32.下列關(guān)于線性表、棧和隊列的敘述，錯誤的是_A_。 A.線性表是給定的n（n必須大于零）個元素組成的序列。 B.線性表允許在表的任何位置進行插入和刪除操作。 C.棧只允許在一端進行插入和刪除操作。 D.隊列允許在一端進行插入，在令一端進行刪除。33.一個隊列的入隊序列是1,2,3,4，則隊列的確定輸出序列_B_ A. 4,3,2,1     B. 1,2,3,4     C. 1,4,3,2 

13、60;       D. 3,2,4,1 34.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng)前rear 和front的值分別為0和3.當(dāng)從隊列中刪除一個元素,再加入兩個元素后, rear 和front的值分別為_B_ A. 1和5 B. 2和4 C. 4和2 D. 5和135.最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是_B_。 A. (rear+1)%n=front B. rear=front C. rear+1=front D. (rear-l)%n=front36.循環(huán)隊列存儲在

14、數(shù)組A0.m中，則入隊時的操作為_D_。 A. rear=rear+1 B. rear=(rear+1)%(m-1) B. rear=(rear+1)%m D. rear=(rear+1)%(m+1)37.數(shù)組用來表示一個循環(huán)隊列，為當(dāng)前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素的公式為 _D_    A rf;  B  （nfr）% n;  C  nrf;    D  （nrf）% n  38.一個長度為50的循環(huán)隊列中，隊頭指針（fr

15、ont）等于41，隊尾指針（rer）等于20，則隊列中有_D_個元素。   A 41   B  20  C  21   D  29  39.二維數(shù)組M，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時元素_B_的起始地址相同。 A、M24 B、M34 C、M35 D、M4440.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是_C_A、80 B、100

16、 C、240 D、27041.有一個二維數(shù)組mn，按行存儲，假設(shè)00存放位置在644（10進制），22存放位置在676（10進制），每個元素占一個空間，則45在_C_位置。   A 692   B  626   C  709   D  724  42.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為_C_。A、SA+141 B、SA+144 C、SA+222 D、SA+225

17、43.在具有100個結(jié)點的樹中，其邊的數(shù)目為_C_。   A 101   B  100   C  99   D  98  44.按照樹的定義，具有3個結(jié)點的樹有_A_種形態(tài)。A、2 B、3 C、4 D、545.按照二叉樹的定義，具有3個結(jié)點的二叉樹有_D_種形態(tài)。A、2 B、3 C、4 D、546.下面說法中，_D_是正確的。A、度為2的樹是二叉樹 B、度為2的有序樹是二叉樹C、子樹有嚴(yán)格左、右之分的樹是二叉樹 D、子樹有左、右之分、且度不超過2的樹是二叉樹47.下面的說法中

18、，_C_是正確的。A、二叉樹的度為2 B、二叉樹中任意一個結(jié)點的度都為2C、任何二叉樹中結(jié)點度可以小于2 D、任何二叉樹中至少有一個結(jié)點的度為248.若一棵二叉樹有10個度為2的結(jié)點，則該二叉樹的葉結(jié)點的個數(shù)_B_。A、9 B、11 C、12 D、不確定49.具有10個葉結(jié)點的二叉樹中有_A_個度為2的結(jié)點。A、9 B、11 C、12 D、不確定50.若一棵滿二叉樹有2047個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)為_B_。A、512 B、1024 C、2048 D、409651.具有65個結(jié)點的完全二叉樹的高度為_B_。   A 8   B  7&#

19、160;  C  6   D  5  52.深度為5的二叉樹至多有_B_個結(jié)點。A、16 B、31 C、15 D、3053.在一棵樹的左孩子-右兄弟表示法中，一個結(jié)點的右孩子是該結(jié)點的_A_結(jié)點。A、兄弟 B、父子 C、祖先 D、子孫54.在一棵樹的雙親表示中，每個數(shù)據(jù)元素包含_B_個域。A、1 B、2 C、3 D、455.對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用_C_次序的遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按

20、層次遍歷56.某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E 則前序序列是_B_AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不對 57.二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是_C_A、 E B、 F C、 G D、 H 58.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是_A_。    A 唯一的    B  有多種，但根結(jié)點都沒有左孩子   C

21、0; 有多種  D  有多種，但根結(jié)點都沒有右孩子 59.在一個圖中，所有頂點的度數(shù)之和等于所有邊的數(shù)目的_C_倍。A、1/2 B、1 C、2 D、460.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_B_倍。A、1/2 B、1 C、2 D、461.一個具有n個頂點的無向圖最多有_A_條邊。A、n×（n1）/2 B、n×（n1）C、n×（n+1）/2 D、n×n62.一個具有n個頂點的有向圖最多有_B_條邊。A、n×（n1）/2 B、n×（n1）C、n×（n+1）/2 D、n

22、15;n63.一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個_A_。A、對稱矩陣 B、對角矩陣 C、三角矩陣 D、稀疏矩陣64.具有n個頂點、e條邊的無向圖采用鄰接矩陣存儲方法。則鄰接矩陣的大小為_D_。A、n B、(n-1) ×（n+1） C、(n+1) ×（n+1） D、n×n65.通常把查找過程中對關(guān)鍵字需要執(zhí)行的_C_作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。A、BST B、WPL C、ASL D、BFS66.在表長是N的順序表中，實施順序查找，在查找不成功時，與關(guān)鍵字比較的次數(shù)_C_。A、N B、1 C、N+1 D、N-167.一個順序存儲結(jié)構(gòu)的線性表有

23、255個記錄，采用線性查找法（也稱順序查找法）查找該表，在等概率條件下的平均查找長度為_A_。   A 128  B  127  C  126  D  255 68.在表長為的鏈表中進行線性查找，它的平均查找長度為_B_   A   B  （）   C  n / 2  D  （） 69.線性表必須是_B_，才能進行二分查找。A、用數(shù)組存儲的線性表 B、用數(shù)組存儲的有序表C、用鏈表存儲的線性表 D、用鏈表存儲

24、的有序表70.有一個順序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)折半查找值為82的結(jié)點時，_A_次比較后查找成功。   A 4  B  2  C  1   D  8  71.鏈表適用于 _A_ 查找   A 順序  B  二分法  C  順序、，也能二分法  D  隨機  72. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元

25、素20，它將依次與表中元素_A_比較大小。   A 28，6，12，20  B  38,12,20  C  20  D  38,70,88,100 73. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 _A_比較大小，查找結(jié)果是失敗。   A 20，70，30，50  B  30，88，70，50   C  20，50   D  30，88

26、，50 74. 對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較 _C_次關(guān)鍵字。   A 3  B  4   C  5  D  6  75. 散列查找是由鍵值_B_確定散列表中的位置，并進行存儲或查找。A、本身 B、散列函數(shù)值 C、相反數(shù) D、平方76.設(shè)某散列表長度為100，散列函數(shù)H(k)k%p, 則P 通常情況下最好選擇_C_A、91 B、93 C、97 D、9977. 哈希表的地址區(qū)間為0-17，哈希函數(shù)為H(k)=k mod 17。采用線性探測法處理沖突，并將關(guān)鍵

27、字序列26,25,72,38,8,18,59依次存儲到哈希表中。那么，元素59存放在哈希表中的地址是_D_。A. 8B. 9 C. 10D. 1178. 給定n=8，對數(shù)組R中的8個元素做升序排列，數(shù)組R中的關(guān)鍵字為：（8，3，2，1，7，4，6，5），則簡單選擇排序過程中第二趟排序結(jié)束后關(guān)鍵字的順序是_A_    A 1,2,3,8,7,4,6,5   B  1,3,2,8,7,4,6,5   C  1,2,3,4,5,6,8,7  D  1,2,3,4,5,6,7,8 7

28、9.每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_A_排序。A、插入 B、交換 C、選擇 D、歸并80.有關(guān)鍵字序列20，6，15，7，3，作升序排列，則線性插入排序過程中第三趟排序結(jié)束后關(guān)鍵字的順序是 _C_。 A 20，6，15，7，3  B  6，20，15，7，3  C  6，15，20，7，3  D  6，7，15，20，3 81.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 _C_    A 順序查找  B&#

29、160; 折半查找   C  散列查找  D  線性查找  82.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是_A_   A 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in）    B  在第i個結(jié)點后插入一個新結(jié)點（1in）   C  刪除第i個結(jié)點（1in）   D  將n個結(jié)點從小到大排序 83. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的數(shù)據(jù)元素的方法以及它們之間的_A_和運算等的學(xué)科。A、結(jié)構(gòu) B、關(guān)系 C、運算 D、 算法84.算法的計算量的大小稱為計算的_B_。A、效率 B、 復(fù)雜性 C、 現(xiàn)實性 D、 難度85. 以下數(shù)據(jù)結(jié)構(gòu)中，_A_ 是非線性數(shù)據(jù)結(jié)構(gòu)A、樹