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

1、單元練習1一判斷題（下列各題，正確的請在前面的括號內(nèi)打；錯誤的打 ）（）（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（）（2）一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運算集構(gòu)成的整體。（）（3）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(數(shù)據(jù)項是數(shù)據(jù)的最小單位)（）（4）數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的儲存結(jié)構(gòu)是不同的（）（5）程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。（）（6）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（）（7）數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。（）（8）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。

2、（）（9）數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。（）（10）算法是對解題方法和步驟的描述。二填空題（1） 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲結(jié)構(gòu) 兩種結(jié)構(gòu)。（2） 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和 圖形結(jié)構(gòu) 。（3） 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和 非線性結(jié)構(gòu) 。（4） 樹形結(jié)構(gòu) 和 圖形結(jié)構(gòu) 合稱為非線性結(jié)構(gòu)。（5） 在樹形結(jié)構(gòu)中，除了樹根結(jié)點以外，其余每個結(jié)點只有 1 個前趨結(jié)點。（6） 在圖形結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。（7） 數(shù)據(jù)的存儲結(jié)構(gòu)又叫 物理結(jié)構(gòu) 。（8） 數(shù)據(jù)的存儲結(jié)構(gòu)形式包括：順序存儲、鏈式存儲、索引存儲和 散列存儲 。（

3、9） 線性結(jié)構(gòu)中的元素之間存在 一對一 的關(guān)系。（10） 樹形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在 一對多 的關(guān)系，（11） 圖形結(jié)構(gòu)的元素之間存在 多對多 的關(guān)系。（12） 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和 算法（或運算） 三個方面的內(nèi)容。（13） 數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的 關(guān)系 的有限集合。（14） 算法是一個 有窮指令 的集合。（15） 算法效率的度量可以分為事先估算法和 事后統(tǒng)計法 。（16） 一個算法的時間復雜性是算法 輸入規(guī)模 的函數(shù)。（17） 算法的空間復雜度是指該算法所耗費的 存儲空間 ，它是該算法求解問題規(guī)模n的函數(shù)。（18） 若一個算法中

4、的語句頻度之和為T（n）=6n+3nlog2n，則算法的時間復雜度為 O（nlog2n） 。（19） 若一個算法中的語句頻度之和為T（n）=3n+nlog2n+n2，則算法的時間復雜度為 O（n2） 。（20） 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的 操作對象 ，以及它們之間的關(guān)系和運算的學科。三選擇題（1）數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（ A ）及它們之間的相互聯(lián)系。 A. 存儲結(jié)構(gòu)和邏輯結(jié)構(gòu) B. 存儲和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯（2）在邏輯上可以把數(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)部

5、結(jié)構(gòu)和外部結(jié)構(gòu)（3）數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ C ）。 A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲結(jié)構(gòu) D. 鏈式存儲結(jié)構(gòu)（4）非線性結(jié)構(gòu)中的每個結(jié)點（ D ）。A. 無直接前趨結(jié)點B. 無直接后繼結(jié)點C. 只有一個直接前趨結(jié)點和一個直接后繼結(jié)點D. 可能有多個直接前趨結(jié)點和多個直接后繼結(jié)點（5）鏈式存儲的存儲結(jié)構(gòu)所占存儲空間（ A ）。 A 分兩部分，一部分存放結(jié)點的值，另一部分存放表示結(jié)點間關(guān)系的指針 B 只有一部分，存放結(jié)點的值 C 只有一部分，存儲表示結(jié)點間關(guān)系的指針 D 分兩部分，一部分存放結(jié)點的值，另一部分存放結(jié)點所占單元素（6）

6、算法的計算量大小稱為算法的（ C ）。 A. 現(xiàn)實性 B. 難度 C. 時間復雜性 D. 效率（7）數(shù)據(jù)的基本單位是（ B ）。 A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 文件（8）每個結(jié)點只含有一個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結(jié)構(gòu)稱為（ A ）結(jié)構(gòu)。 A. 順序存儲 B. 鏈式存儲 C. 索引存儲 D. 散列存儲（9）每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（ B ）存儲方式。 A. 順序 B. 鏈式C. 索引 D. 散列（10）以下任何兩個結(jié)點之間都沒有邏輯關(guān)系的是（ D ）。 A. 圖形結(jié)構(gòu) B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu)

7、 D. 集合（11）在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是（ C ）。 A. 物理結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 邏輯和存儲結(jié)構(gòu)（12）下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（ A ）。 A. 集合 B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu) D. 圖形結(jié)構(gòu)（13）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ A ）。 A. 邏輯結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯實現(xiàn) D. 存儲實現(xiàn)（14）每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位置的表，該存儲方式是（ C ）存儲方式。 A. 順序 B. 鏈式 C. 索引 D. 散列（15）

8、算法能正確的實現(xiàn)預定功能的特性稱為算法的（ A ）。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性（16）算法在發(fā)生非法操作時可以作出處理的特性稱為算法的（ C ）。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性（17）下列時間復雜度中最壞的是（ D ）。 A. O（1） B. O（ n） C. O（log2n） D. O（n2）（18）下列算法的時間復雜度是（ D ）。 for (i=0;i<n;i+) for (j=0;i<n;j+) cij=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2）（19）算法分析的兩個主要方面是

9、（ A ）。A. 空間復雜性和時間復雜性 B. 正確性和簡明性C. 可讀性和文檔性 D. 數(shù)據(jù)復雜性和程序復雜性（20）計算機算法必須具備輸入、輸出和（ C ）。 A. 計算方法 B. 排序方法 C. 解決問題的有限運算步驟 D. 程序設計方法四分析下面各程序段的時間復雜度（1） for (i=0;i<n;i+) for (j=0;j<m;j+) Aij解： O(n*m)（2） s=0; for (i=0;i<n;i+) for (j=0;j<n;j+) s+=Bij; sum=s;解： O(n2)（3） T=A；A=B；B=T；解：O(1)（4） s1(int n)

10、int p=1,s=0; for (i=1;i<=n;i+) p*=i;s+=p; return(s);O(n)*（5） s2(int n)x=0;y=0;for (k=1;k<=n;k+)x+;for (i=1;i<=n;i+)for (j=1;j<=n;j+)y+;解：O(n2)五 根據(jù)二元組關(guān)系，畫出對應邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。1 A=（D，R），其中：D=a，b，c，d，e，R= 解： a b c d e 屬于集合2 B=（D，R），其中：D=a，b，c，d，e，f， R=rR=<a,b>，<b,c>，<c,d&g

11、t;，<d,e>，<e,f> （尖括號表示結(jié)點之間關(guān)系是有向的）解： baedfc屬于線性結(jié)構(gòu)。3根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。F=（D，R），其中： D=50，25，64，57，82，36，75，55，R=<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>2550755736826455解：屬于樹結(jié)構(gòu)4 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。C=（D，R），其中： D=1，2，3，4

12、，5，6，R=（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6） （園括號表示結(jié)點之間關(guān)系是有向的）解：126345屬于圖結(jié)構(gòu)5根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。E=（D，R），其中： D=a，b，c，d，e，f，g，h，R=<d,b>，<d,g>，<d,a>，<b,c>，<g,e>，<g,h>，<e,f>解：bdfeachg屬于樹結(jié)構(gòu)。模擬考題1 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。A=（D，R），其中： D=1，2，3，4

13、，5，6，R=（1,2）,（1,6）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（5,6）126345解： 屬于圖結(jié)構(gòu)2 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。B=（D，R），其中： D=40，30，20，60，50，80，70，10，R=<30,20>,<30,60>,<20,40>,<60,50>,<60,70>,<60,80>,<70,10>2030105080407060解：屬于樹結(jié)構(gòu)3 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。C=（D，R），其中： D=1，2，3，4，5，6，R=（1,2）,（2,3）,（