數(shù)據(jù)結構各章題庫及答案

1、第 1 章 緒論習題1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構、邏輯結構、存儲結構、抽象數(shù)據(jù)類型。2．試舉一個數(shù)據(jù)結構的例子，敘述其邏輯結構和存儲結構兩方面的含義和相互關系。3．簡述邏輯結構的四種基本關系并畫出它們的關系圖。4．存儲結構由哪兩種基本的存儲方法實現(xiàn)？5．選擇題（1）在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ ） 。A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構C．線性結構和非線性結構

2、 D．內(nèi)部結構和外部結構（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（ ） 。A．存儲結構 B．存儲實現(xiàn)C．邏輯結構 D．運算實現(xiàn)（3）通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ） 。A．數(shù)據(jù)具有同一特點B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相

3、等（4）以下說法正確的是（ ） 。A．數(shù)據(jù)元素是數(shù)據(jù)的最小單位B．數(shù)據(jù)項是數(shù)據(jù)的基本單位C．數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構（5）以下與數(shù)據(jù)的存儲結構無關的術語是（ ） 。A．順序隊列 B. 鏈表 C. 有序表 D. 鏈棧（6）以下數(shù)據(jù)結構中， （ ）是非線性數(shù)據(jù)結構A．樹 B．字符串 C．隊

4、 D．棧6．試分析下面各程序段的時間復雜度。（1）x=90; y=100; while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)第 2 章 線性表1．選擇題（1）一個向量第一個元素的存儲地址是 100，每個

5、元素的長度為 2，則第 5 個元素的地址是（ ） 。A．110 B．108 C．100 D．120（2）在 n 個結點的順序表中，算法的時間復雜度是 O(1)的操作是（ ） 。A．訪問第 i 個結點（1≤i≤n）和求第 i 個結點的直接前驅(qū)（2≤i≤n） B．在第 i 個結點后插入一個新結點（1≤i≤n）C．刪除第 i 個結點（1≤i≤n）D．將 n 個結點從小到大排

6、序（3） 向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 的元素個數(shù)為（ ） 。A．8 B．63.5 C．63 D．7（4）鏈接存儲的存儲結構所占存儲空間（ ） 。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)（5

7、）線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址（ ） 。A．必須是連續(xù)的 B．部分地址必須是連續(xù)的C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以（6）線性表Ｌ在（ ）情況下適用于使用鏈式結構實現(xiàn)。A．需經(jīng)常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入 C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構復雜（7）單鏈表的存儲密度（ ） 。A．大于 1 B

8、．等于 1 C．小于 1 D．不能確定（8）將兩個各有 n 個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ） 。A．n B．2n-1 C．2n D．n-1（9）在一個長度為 n 的順序表中，在第 i 個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（ ）個元素。A．n-i B．n-i+1 C．n-i-1