數(shù)據(jù)結(jié)構(gòu)試題庫及答案(已修改)

　

【正文】 數(shù)據(jù)結(jié)構(gòu)試題庫及答案第一章 概論一、選擇題研究數(shù)據(jù)結(jié)構(gòu)就是研究（ D ）。A. 數(shù)據(jù)的邏輯結(jié)構(gòu) B. 數(shù)據(jù)的存儲結(jié)構(gòu) C. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) D. 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作算法分析的兩個主要方面是（ A ）。 A. 空間復(fù)雜度和時間復(fù)雜度 B. 正確性和簡單性 C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ D ）。A. 圖 B. 樹 C. 廣義表 D. 棧計算機(jī)中的算法指的是解決某一個問題的有限運(yùn)算序列，它必須具備輸入、輸出、（ B ）等5個特性。A. 可執(zhí)行性、可移植性和可擴(kuò)充性 B. 可執(zhí)行性、有窮性和確定性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和確定性下面程序段的時間復(fù)雜度是（ C ）。 for(i=0。im。i++) for(j=0。jn。j++) a[i][j]=i*j。 A. O(m2) B. O(n2) C. O(m*n) D. O(m+n)算法是（ D ）。A. 計算機(jī)程序 B. 解決問題的計算方法 C. 排序算法 D. 解決問題的有限運(yùn)算序列某算法的語句執(zhí)行頻度為（3n+nlog2n+n2+8）,其時間復(fù)雜度表示（ C ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)下面程序段的時間復(fù)雜度為（ C ）。 i=1。 while(i=n) i=i*3。A. O(n) B. O(3n) C. O(log3n) D. O(n3) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的數(shù)據(jù)元素以及它們之間的（ ）和運(yùn)算等的學(xué)科。A. 結(jié)構(gòu) B. 關(guān)系 C. 運(yùn)算 D. 算法下面程序段的時間復(fù)雜度是（ ）。 i=s=0。 while(sn){ i++。s+=i。 }A. O(n) B. O(n2) C. O(log2n) D. O(n3)1抽象數(shù)據(jù)類型的三個組成部分分別為（ ）。A. 數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作 B. 數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) C. 數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型 D. 數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型1通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質(zhì)量，以下解釋錯誤的是（ ）。 A. 正確性算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能 B. 易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴(kuò)充 C. 健壯性當(dāng)環(huán)境發(fā)生變化時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生不需要的運(yùn)行結(jié)果 D. 高效性即達(dá)到所需要的時間性能1下列程序段的時間復(fù)雜度為（B）。 x=n。y=0。 while(x=(y+1)*(y+1)) y=y+1。 A. O(n) B. C. O(1) D. O(n2)二、填空題程序段“i=1。while(i=n) i=i*2。”的時間復(fù)雜度為 。數(shù)據(jù)結(jié)構(gòu)的四種基本類型中， 樹形結(jié)構(gòu) 的元素是一對多關(guān)系。三、綜合題將數(shù)量級O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增長率由小到大排序。答案： O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(N3) O(2N) 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。2. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個方面的內(nèi)容。3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。4. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。5． 在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 1個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn)。6. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個。7. 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個。8．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈?zhǔn)健⑺饕⑸⒘小?. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。10. 一個算法的效率可分為時間效率和空間效率。11. 任何一個C程序都由一個主函數(shù)和若干個被調(diào)用的其它函數(shù)組成。二、單項選擇題（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面5是：A) 空間復(fù)雜性和時間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ C ）5. 計算機(jī)算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運(yùn)算序列 D) 調(diào)度方法（ B ）6. 計算機(jī)算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡答題？ 答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的。四、分析下面各程序段的時間復(fù)雜度2. s=0。 for (i=0。 in。 i++)for(j=0。 jn。 j++) s+=B[i][j]。sum=s。 1. for (i=0。 in。 i++)for (j=0。 jm。 j++)A[i][j]=0。 3. x=0。for(i=1。 in。 i++) for (j=1。 j=ni。 j++)x++。 4. i=1。 while(i=n) i=i*3。 五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定其是哪種邏輯結(jié)構(gòu)。 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }2． D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }3．D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}第二章 線性表一、選擇題若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素算法的時間復(fù)雜度（ ）。A. O(log2n) (1) C. O(n) (n2)若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省時間。 A. 順序表 B. 單鏈表 C. 雙鏈表 D. 單循環(huán)鏈表具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ ）。A. 圖 B. 樹 C. 廣義表 D. 棧在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（ ）個元素。A. ni B. ni+1 C. ni1 D. i非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（ ）。A. pnext==head B. pnext==NULL C. p==NULL D. p==head鏈表不具有的特點(diǎn)是（ ）。A. 可隨機(jī)訪問任一元素　 B. 插入刪除不需要移動元素 C. 不必事先估計存儲空間 D. 所需空間與線性表長度成正比在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個指針q所指向的新結(jié)點(diǎn)，修改指針的操作是（ ）。 A. pnext=q。qprior=p。pnextprior=q。qnext=q。 B. pnext=q。pnextprior=q。qprior=p。qnext=pnext。 C. qprior=p。qnext=pnext。pnextprior=q。pnext=q。 D. qnext=pnext。qprior=p。pnext=q。pnext=q。線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（ ）。A. 必須是連續(xù)的 B. 必須是不連續(xù)的 C. 連續(xù)與否均可 D. 和頭結(jié)點(diǎn)的存儲地址相連續(xù)在一個長度為n的順序表中刪除第i個元素，需要向前移動（ ）個元素。A. ni B. ni+1 C. ni1 D. i+1線性表是n個（ ）的有限序列。A. 表元素 B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項 1從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個表的是（ ）。A. 單鏈表 B. 順序表 C. 循環(huán)鏈表 D. 靜態(tài)鏈表1在具有n個結(jié)點(diǎn)的單鏈表上查找值為x的元素時，其時間復(fù)雜度為（ ）。A. O(n) B. O(1) C. O(n2) D. O(n1)1線性表L=(a1,a2,……,an)，下列說法正確的是（ ）。A. 每個元素都有一個直接前驅(qū)和一個直接后繼 B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小 D. 除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后繼1一個順序表的第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的存儲地址是（ ）。A. 98 B. 100 C. 102 D. 1061在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)的時間最少的是（ ）。 A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表 D. 順序表1在一個單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ ）。A. pnext=pnextnext。B. p=pnext。pnext=pnextnext。C. p =pnext。D. p=pnextnext。1將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ ）。A. O(1) B. O(n) C. O(m) D. O(m+n)1線性表的順序存儲結(jié)構(gòu)是一種（ ）存儲結(jié)構(gòu)。A. 隨機(jī)存取 B. 順序存取 C. 索引存取 D. 散列存取 1順序表中，插入一個元素所需移動的元素平均數(shù)是（ ）。 A. (n1)/2 B. n C. n+1 D. (n+1)/2循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。A. 不再需要頭指針 B. 已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū) C. 在進(jìn)行插入、刪除運(yùn)算時能保證鏈表不斷開 D. 在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個鏈表 1不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）。A. head==NULL B. headnext==NULL C. headnext==head D. head!=NULL1在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為O(1)的是（ ）。 A. 訪問第i個元素的前驅(qū)（1） B. 在第i個元素之后插入一個新元素() C. 刪除第i個元素() D. 對順序表中元素進(jìn)行排序1已知指針p和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈表中某個結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為（ ）。A. qnext=snext；snext=p； B. snext=p；qnext=sne