數(shù)據(jù)結構(c語言版)習題答案嚴蔚敏李冬梅吳偉民23490數(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．內部結構和外部結構 （2）與數(shù)據(jù)元素本身的形式、內容、相對位置、個數(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ù)

3、據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 （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．樹

4、 B．字符串 C．隊 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 章 線性表

5、 1．選擇題 （1）一個向量第一個元素的存儲地址是 100，每個元素的長度為 2，則第 5 個元素的地址是（ ） 。 A．110 B．108 C．100 D．120 （2）在 n 個結點的順序表中，算法的時間復雜度是 O(1)的操作是（ ） 。 A．訪問第 i 個結點（1≤i≤n）和求第 i 個結點的直接前驅（2≤i≤n） B．在第 i 個結點后插入一個新結點（1≤i≤n

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

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

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

9、A．n-i B．n-i+1 C．n-i-1 D．i (10) 線性表L=(a1，a2,……an)，下列說法正確的是（ ） 。 A．每個元素都有一個直接前驅和一個直接后繼 B．線性表中至少有一個元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼。 (11) 若指定有 n 個元素的向量，則建立一個有序單鏈表的時間復雜