數(shù)據(jù)結構試題

1、1 緒論 沈陽理工大學應用技術學院 信息與控制學院 計算機科學與技術教研室 2011-5-8 -1- 數(shù)據(jù)結構復習題：緒論 單選題 1、在數(shù)據(jù)結構中，與所使用的計算機無關的數(shù)據(jù)叫_結構。 A 存儲|B 物理|C 邏輯|D 物理和存儲 2、在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成_。 A 動態(tài)結構和靜態(tài)結構|B 緊湊結構和非緊湊結構|C 線性結構和非線性結構|D 內(nèi)部結構和外部結構圖 3、數(shù)據(jù)結構在計算機內(nèi)存中的表示是指_。 數(shù)據(jù)的存儲結構|數(shù)據(jù)結構|數(shù)據(jù)的邏輯結構|數(shù)據(jù)元素之間的關系 4、在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的_結構。 邏輯|存儲|邏輯和存儲|物理 5、在以下的敘述中，正

2、確的是_。 線性表的線性存儲結構優(yōu)于鏈表存儲結構|二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表|棧的操作方式是先進 先出|隊列的操作方式是先進后出 6、在決定選取何種存儲結構時，一般不考慮_。 各結點的值如何|結束個數(shù)的多少|(zhì)對數(shù)據(jù)有哪些運算|所用編程語言實現(xiàn)這種結構是否方便 7、在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲_。 數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關系|數(shù)據(jù)的存儲方法 8、下面說法錯誤的是_。 (1) 算法原地工作的含義是指不需要任何額外的輔助空間 (2) 在相同的規(guī)模 n 下，復雜度 O(n)的算法在時間上總是優(yōu)于復雜度 O(2n)的算法 (3) 所謂時間復雜

3、度是指最壞情況下，估計算法執(zhí)行時間的一個上界 (4) 同一個算法，實現(xiàn)語句的級別越高，執(zhí)行效率越低 (1)|(1)、(2)|(1)、(4)|(3) 9、通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性。這意味著_。 數(shù)據(jù)元素具有同一特點|不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同， 而且對應的數(shù)據(jù)項的類型要一致|每個 數(shù)據(jù)元素都一樣|數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 10、以下說法正確的是_。 數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項是數(shù)據(jù)的基本單位|數(shù)據(jù)結構是帶結構的數(shù)據(jù)項的集合|一些表面上很不 相同的數(shù)據(jù)可以有相同的邏輯結構 11、數(shù)據(jù)項是數(shù)據(jù)的最小單元, 數(shù)據(jù)元素是數(shù)據(jù)的基本單位. 數(shù)據(jù)項|數(shù)據(jù)

4、元素|信息項|表元素 12、數(shù)據(jù)結構是指_數(shù)據(jù)元素_以及它們之間的_結構_. (1)數(shù)據(jù)元素 (2)結構|(1)計算方法 (2)關系|(1)邏輯存儲 (2)運算|(1)數(shù)據(jù)映像 (2)算法 13、計算機所處理的數(shù)據(jù)一般具備某種內(nèi)在的關系,這是的指_. 數(shù)據(jù)和數(shù)據(jù)之間存在的某種關系|元素和元素之間存在某種關系|元素內(nèi)部具有某種結構|數(shù)據(jù)項和數(shù)據(jù)項之 間存在某種關系 14、數(shù)據(jù)的邏輯結構可以分為_兩類. 動態(tài)結構和表態(tài)結構|緊湊結構和非緊湊結構|線性結構和非線性結構|內(nèi)部結構和外部結構 15、數(shù)據(jù)的邏輯結構是指_關系的整體. 數(shù)據(jù)元素之間邏輯|數(shù)據(jù)項之間邏輯|數(shù)據(jù)類型之間|存儲結構之間 16、在存

5、儲數(shù)據(jù)時,通常不僅要存儲各數(shù)據(jù)元素的值,而且還要存儲_. -2- 數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關系|數(shù)據(jù)的存儲方法 17、在數(shù)據(jù)的存儲結構中,一個存儲結點存儲一個_. 數(shù)據(jù)項|數(shù)據(jù)元素|數(shù)據(jù)結構|數(shù)據(jù)類型 18、在計算機的存儲器中表示時,物理地址和邏輯地址直接對應并且是連續(xù)的,稱之為_. 邏輯結構|順序存儲結構|鏈式存儲結構|以上都對 19、數(shù)據(jù)采用鏈式存儲結構時,要求_. 每個結點用占一片連續(xù)的存儲區(qū)域|所有結點占用一片連續(xù)的存儲區(qū)域|結點的最后一個數(shù)據(jù)域是指針類型| 每個結點有多少個后繼,就設多少個指針域 20、數(shù)據(jù)的運算_. 效率與采用何種存儲結構有關|是根據(jù)存儲結構來

6、定義的|有算術運算和關系運算兩大類|必須用程序設計語 言來描述 21、下列說法中,不正確的是_. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位|數(shù)據(jù)可由若干個數(shù)據(jù)元素構成|數(shù) 據(jù)項可由若干個數(shù)據(jù)元素構成 22、_不是算法的基本特性. 可行性|長度有限|在規(guī)定的時間內(nèi)完成|確定性 23、計算機中算法指的是解決某一問題的有限運算序列,它必須具備輸入、輸出、_. 可行性、可移植性和可擴充性|可行性、有窮性和確定性|確定性、有窮性和穩(wěn)定性|易讀性、穩(wěn)定性和確定 性 24、以下不屬于算法特性的是_. 可行性|有輸入|確定性|健壯性 25、下面關于算法的說法正確的是_. 算法最終必須由

7、程序?qū)崿F(xiàn)|算法的有窮性是對于任意的一組輸入值必須在有窮步驟后結束|算法的可行性是 指指令不能有二義性|以上幾個都是錯誤的 26、算法的時間復雜度與_有關 問題規(guī)模|計算機硬件性能|編譯程序質(zhì)量|程序設計語言 27、算法分析的主要任務是分析_. 算法是否具有較好的可讀性|算法中是否存在語法錯誤|算法的功能是否符合設計要求|算法的執(zhí)行時間和問 題規(guī)模之間的關系 28、某算法的時間復雜度為 O(n2),表明該算法的_. 問題規(guī)模是 n2|執(zhí)行時間等于 n2|執(zhí)行時間與 n2 成正比|問題規(guī)模與 n2 成正比 29、算法分析的目的是_. 找出數(shù)據(jù)結構的合理性|研究算法中輸入和輸出關系|分析算法的效率以

8、求改進|分析算法的易讀性和文檔性 30、線性表是具有 n 個_的有限序列。 表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項 31、線性表是_。 一個有限序列，可以為空|一個有限序列，不可以為空|一個無限序列，可以為空|一個無限序列，不可以為 空 32、線性表采用鏈表存儲時，其地址_。 必須是連續(xù)的|一定是不連續(xù)的|部分地址必須是連續(xù)的|連續(xù)與否均可以 33、鏈表不具備的特點是_。 可隨機訪問任一結點|插入刪除不需要移動元素|不必事先估計存儲空間|所需空間與其長度成正比 34、線性表的靜態(tài)存儲結構與順序存儲結構相比優(yōu)點是_。 所有的操作算法實現(xiàn)簡單|便于隨機存取|便于插入和刪除|便于利用零散的存儲器空間 -3-

9、 35、設線性表有 n 個元素，以下操作中，_在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。 輸出第 i(1<=i<=n)個元素值|交換第 1 個元素與第 2 個元素的值|順序輸出這 n 個元素的值|輸出與給定值 x 相 等的元素在線性表中的序號 36、對于一個線性表，既要求能夠較快地進行插入和刪除，又要求存儲結構能夠反映數(shù)據(jù)元素之間的邏輯關 系，則應采用_存儲結構。 順序|鏈式|散列|索引 37、設線性表中有 2n 個元素，以下操作中，_在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。 刪除指定的元素|在最后一個元素的后面插入一個新元素|順序輸出前 k 個元素|交換第 i 個元素和第 2n-i

10、-1 個 元素的值(i=0，1，?，n-1) 38、需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是_。 單鏈表|靜態(tài)鏈表|線性鏈表|順序存儲結構 39、如果最常用其所長的操作是取第 i 個結點及其前驅(qū)，則采用_結構方式最節(jié)省時間。 單鏈表|雙鏈表|單循環(huán)鏈表|順序表 40、與單鏈表相比，雙鏈表的優(yōu)點之一是_。 插入、刪除操作更簡單|可以進行隨機訪問|可以省略表頭指針或表尾指針|訪問前后相鄰結點更靈活 41、數(shù)據(jù)結構在計算機內(nèi)存中的表示是指_. 數(shù)據(jù)的存儲結構|數(shù)據(jù)結構|數(shù)據(jù)的邏輯結構|數(shù)據(jù)元素之間的關系 42、下面程序段的時間復雜度為_ O(m)| O(n)|O(m*n)|O

11、(m+n) for(int i=0;i<m;i+) for(int j=0;j<n;j+) aij=i*j; 數(shù)據(jù)結構復習題：緒論 判斷題 1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 2、數(shù)據(jù)項是數(shù)據(jù)的基本單位。 3、數(shù)據(jù)元素是數(shù)據(jù)的最小單位 4、數(shù)據(jù)對象就是一組任意數(shù)據(jù)元素的集合 5、任何數(shù)據(jù)結構都具備 3 個基本運算: 插入、刪除和查找. 6、數(shù)據(jù)是由一些類型相同的數(shù)據(jù)元素構成的 7、數(shù)據(jù)是邏輯結構與各數(shù)據(jù)元素在計算機中如何存儲有關 8、如果數(shù)據(jù)元素值發(fā)生改變,則數(shù)據(jù)的邏輯結構也隨之改變. 9、邏輯結構相同的數(shù)據(jù),可以采用多種不同的存儲方法. 10、邏輯結構相同的數(shù)據(jù),結點類型也一定相同

12、11、邏輯結構不相同的數(shù)據(jù),必須采用不同的存儲方式來存儲 12、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系. 13、算法的優(yōu)劣與算法描述語言有無關，但與所有計算機有關。 14、算法可以用不同的語言描述，如果用 C 或 Pascal 等高級語言來描述，則算法實際上就是程序了。 15、程序一定是算法。 16、算法最終必須由計算機程序?qū)崿F(xiàn)。F 19、健壯的算法不會因非法入輸數(shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行結果。 -4- 數(shù)據(jù)結構復習題：緒論 算法分析題 1、求兩個 n 階矩形的乘法 C=A*B,其算法如下: #define MAX 100 void maxtrixmult(int ,float aMAX

13、MAX,bMAXMAX,float cMAXMAX) int i,j,k; float x; for(i=1;i<=n;i+) for (j=1;j<=n;j+) x=0; for(k=1;k<=n;k+) x+=aik*bkj; cij=x; 計算各語句的頻度,并分析該算法的時間復雜度。 2、設 n 是偶數(shù),試計算運行下列程序段后 m 的值并給出該程序段的時間復雜度。 m=0; for(i=1;i<=n;i+) for(j=2*1;j<=n;j+) m+; 3、閱讀下列算法: void suan_fa(int n) int i,j,k,s,x; for (s=0

14、,i=0;i<n;i+) for (j=i;j<n;j+) s+; i=1;j=n;x=0; while (i<j) i+; j-; x+=2; pirntf("s=%d,x=%d",s,x); (1) 分析算法中語句"s+;"的執(zhí)行次數(shù); (2) 分析算法中語句"x+=2;"的執(zhí)行次數(shù); -5- / / / / / / (3) 分析該算法的時間復雜度; (4) 假定 n=5, 試指出執(zhí)行該算法的輸出結果。 6、設 n 是偶數(shù),試計算運行下列程序段后 m 的值并給出該程序段的時間復雜度。 int m=0,i,j; f

15、or (i=1;i<=n;i+) for (j=2*i;j<=n;j+) m+; m=n*n/4 O() 數(shù)據(jù)結構復習題：緒論 填空題 1、一個數(shù)據(jù)結構在計算機中_映像_稱為存儲結構。 2、數(shù)據(jù)邏輯結構包括 、 和 三種類型，樹形結構和圖形結構合稱為_。 3、在線性結構中，第一個結點_前驅(qū)結點，其余每個結點有且只有_個前驅(qū)結點：最后一個結 點_后續(xù)結點，其余每個結點有且只有_個后續(xù)結點。 4、 在樹形結構中， 樹根結點沒有_結點， 其余每個結點有且只有_個前驅(qū)結點:葉子結點沒有_ 結點,其余每個結點后的后續(xù)結點可以_ 5、在圖形結構中，每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以_任意多個

16、_。 6、線性結構中元素之間存在_一對一_關系，樹形結構中元素之間存在_一對多_關系，圖形結 構中元素之間存在_多對多_關系。 7、算法的 5 個重要特性是_、_、_、輸入和輸出。 8、 算法可以用不同的語言描述， 如果用 C 語言或 PASCAL 語言等高級語言來描述， 則算法實現(xiàn)上就是程序了。 這個斷言是_。 9、數(shù)據(jù)結構、數(shù)據(jù)元素和數(shù)據(jù)項在計算機中的映射(或表示)分別稱為存儲結構、結點和數(shù)據(jù)域。這個斷言是 _。 10、下面程序段的時間復雜度是_。 for (i=0;i<n;i+) for(j=0;j<m;j+) Aij=0; 11、下面程序段的時間復雜度是_O(sqrt(n)

17、_。 i=s=0; while(s<n) i+; s+=i; 12、下面程序段的時間復雜度是_。 s=0; for (i=0;i<n;i+) for (j=0;j<n;j+) s+=Bij; sum=s; 13、下面程序段的時間復雜度是_O(log3n)_。 i=1; -6- while(i<=n) i=i*3; 14、有如下遞歸函數(shù) fact(n),分析其時間復雜度。 int fact(int n) if (n<=1) return 1; else return (n*fact(n-1); 15、指出下列各算法的時間復雜度 (1) prime(int n) in

18、t i=2; while(n%i!=0 && i<sqrt(n) i+; if (i*1.0>sqrt(n) printf "是一素數(shù)" else printf "不是一素數(shù)" O(sqrt(n) (2) sum1(int n) int p=1,sum=0,i; for (i=1;i<=n;i+) p*=i; sum+=p; returm (sum); (3) sum2(int n) int sum=0,i,j; for (i=1;i<=n;i+) p=1; for (j=1;j<=i;j+) p*=j; s

19、um+=p; return (sum); 16、數(shù)據(jù)的邏輯結構是指_. -7- 17、一個數(shù)據(jù)結構在計算機中的_表示_稱為存儲結構. 18、順序存儲方法是把邏輯上_相鄰的結點_存儲在物理位置上_相鄰的存儲單元_里;鏈式存儲方法中 結點間的邏輯關系是由 附加的指針字段表示_的. 19、數(shù)據(jù)結構是指研究數(shù)據(jù)的_存儲結構_和_邏輯結構_以及它們之間的相互關系,并對這種結構定義 相應的_運算_,設計出相應的_算法_,從而確保經(jīng)過這些運算后所得到的新結構是原來的結構類型. 20、一個算法具有 5 個特性:_、_、_、輸入和輸出。 21、算法的執(zhí)行時間是_的函數(shù)。 22、數(shù)據(jù)的邏輯結構是從邏輯上描述數(shù)據(jù),

20、它與數(shù)據(jù)的_存儲結構、物理結構_無關,是獨立于計算機的. 23、數(shù)據(jù)的邏輯結構被分為_、_、_和_種。 24、數(shù)據(jù)的存儲結構被分為_、_、_和_種。 25、在線性結構、樹形結構和圖形結構中，前驅(qū)和后繼結點之間分別存在著_1:1_、_1： N_、_M:N_的聯(lián)系。 26、一種抽象數(shù)據(jù)類型包括_數(shù)據(jù)_和_操作_兩個部分。 27、 從一維數(shù)組 an中順序查找出一個最大值元素的時間復雜度為_， 輸出一個二維數(shù)組 bmn 中所有元素值的時間復雜度為_ 28、在下面程序段中，s=s+p 語句的執(zhí)行次數(shù)為_n_，p*=j 語句的執(zhí)行次數(shù)為 _n*(n+1)/2_，該程序段的時間復雜度為_O(n*n)_。 i

21、nt i=0,s=0; while(+i<=n) int p=1; for(int j=1;j<=i;j+) p*=j; s=s+p; 29、一個算法的時間復雜度為（3*n*n+2nlog2n+4n-7)/(5n)，其數(shù)量級表示為_O(n)_。 30、從一個數(shù)組 a10中順序查找元素時，假定查找每個元素的概率都相同，則進行一次查找運算時的平均 查找長度（即同元素的平均比較次數(shù)）為_。 31、從一個數(shù)組 a7中順序查找元素時，假定查找第 1 個元素 a0的概率為 1/3，查找第 2 個元素 a1的概率 為 1/4，其找其余元素的概率均相同，則在查找成功時同元素的平均比較次數(shù)為_35/

22、12_。 32、對于一個 n*n 的矩陣的任意矩陣元素 aij，按行存儲時和按列存儲時的地址之差是 _(i-j)*(n-1)*d_。設兩種存儲時的開始存儲地址均為(0,0)，每個元素所占存儲單元數(shù)均為 d。 33、設有一個二維數(shù)組 A1020，按行存放于一個連續(xù)的存儲空間中，A00的存儲地址是 200，每個數(shù)組 元素占 1 個存儲字，則 A62的存儲字地址是_ 34、設有一個二維數(shù)組 A1020，按列為主序存放于一個連續(xù)的存儲空間中，A00的存儲地址是 200，每 個數(shù)組元素占 1 個存儲字，則 A62的存儲字地址是_。 37、在線性表的單鏈接存儲結構中，每個結點包含有兩個域，一個叫_，另一個

23、叫_ 域。 數(shù)據(jù)結構復習題：緒論 問答題 1、當你為解決某一問題而選擇數(shù)據(jù)結構時,應從哪些方面考慮? 2、簡述邏輯結構與存儲結構的關系. 3、 數(shù)據(jù)運算是數(shù)據(jù)結構的一個重要方面,試舉例說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同,只是對于 運算的定義不同,因而兩個結構具有顯著不同的特性,則這兩個數(shù)據(jù)結構是不同的. -8- 數(shù)據(jù)結構復習題答案：緒論 問答題 1、解答：通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的時間 又涉及以下三點： （1）程序運行時所需輸入的數(shù)據(jù)總量。 （2）計算機執(zhí)行每條指令所需的時間。 （3）程序中指令重復執(zhí)行的次數(shù)。 2、答：數(shù)據(jù)的邏輯

24、結構反映數(shù)據(jù)元素之間的邏輯關系（即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系” ） ，數(shù)據(jù) 的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。 3、答：棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲） ，但由于其運算集合不同而 成為不同的數(shù)據(jù)結構。 2 線性表 沈陽理工大學應用技術學院 信息與控制學院 計算機科學與技術教研室 2011-5-8 -9- - 10 - 數(shù)據(jù)結構復習題：線性表 單選題 1、在一個長度為 n 的順序表中，向第 i 個元素(1in+1)之前插入一個新元素時，需向后移動_個元素。 2、從一個具有 n 個節(jié)點的單鏈表中查找其值等于 x 結點時，

25、在查找成功的情況下，需平均比較_(n+1)/2_ 個結點。 3、在一個單鏈表中，已知*q 結點是*p 結點的前驅(qū)結點，若在*q 和*p 之間插入*s 結點， 則執(zhí)行_。 4、線性表是_ 。 5、對順序存儲的線性表，設其長度為 n，在任何位置上插入或刪除操作都是等概率的， 刪除一個元素時大 約要移動表中的_個元素。 6、線性表采用鏈式存儲時，其地址_。 7、設單鏈表中指針 p 指著結點 m，指針 f 指著將要插入的新結點 x，當 x 插在鏈表中最后一個結點 m 之后 時，只要先修改_后修改 p->link=f 即可。 8、在雙向鏈表存儲結構中，刪除 p 所指的結點時需修改指針_。 9、在雙

26、向鏈表存儲結構中，刪除 p 所指的結點的前趨結點（若存在）時需修改指針_。 10、根據(jù)線性表的鏈式存儲結構，每個結點所含指針的個數(shù)，鏈表分為單鏈表和_。 11、在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上_。 12、鏈表不具備的特點是_。 13、不帶頭結點的單鏈表 head 為空的判定條件是_。 14、帶頭結點的單鏈表的 head 為空的判定條件是_。 15、帶頭結點的雙循環(huán)表 L 為空表的條件是_L->next=L_。 16、非空的循環(huán)單鏈表 head 的尾結點(由 p 所指向)滿足_。 17、在循環(huán)雙鏈表的 p 所指結點之前插入 s 所指結點的操作是_。 18、若某表最常用

27、的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用_帶頭結點的 雙循環(huán)鏈表_存儲方式最節(jié)省運算時間。 19、某線性表最常用的操作是在最后一個結點之后插入一個結點或刪除第一個結點，故采用_僅有尾指針 的單循環(huán)鏈表_存儲方式最節(jié)省運算時間。 20、需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是_。 21、如果最常用的操作是取第 i 個結點及其前驅(qū)，則采用_順序表_存儲方式最節(jié)省時間。 22、在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是_。 23、在一個長度為 n(n>1)的單鏈表上，設有頭和尾兩個指針，執(zhí)行_刪除單鏈表中的最后

28、一個元素_ 操作與鏈表的長度有關。 24、設線性表有 n 個元素，以下算法中，_在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。 25、設線性表中有 2n 個元素，算法_刪除所有值為 x 的元素_，在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效 率更高。 26、與單鏈表相比，雙鏈表的優(yōu)點之一是_。 27、 如果對線性表的運算只有 4 種， 即刪除第一個元素， 刪除最后一個元素， 在第一個元素前面插入新元素， 在最后一個元素的后面插入新元素，則最后使用_只有表頭指針沒有表尾指針的循環(huán)雙鏈表_。 28、如果對線性表的運算只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 _。 29、設有兩個長度為

29、n 的單鏈表，結點類型相同。若以 h1 為表頭指針的鏈表是非循環(huán)的，以 h2 為表頭指針 的鏈表是循環(huán)的，則_。 30、在長度為 n 的_上，刪除第一個結點，其算法的時間復度為 O(n)。 31、將兩個各有 n 個元素的有序順序表歸并成一個有序順序表，其最少的比較次數(shù)是_n_。 - 11 - 32、帶頭結點的單鏈表 L 為空的判定條件是_。 33、在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是_。 34、在一個長度為 n(n>1)的帶頭結點的單鏈表 h 上， ，另設有尾指針 r(指向尾結點)，執(zhí)行_操作與鏈 表的長度有關。 35、在一個雙鏈表中，在*p 結

30、點之后插入結點*q 的操作是_。 36、在一個雙鏈表中，在*p 結點之前插入*q 結點的操作是_。 37、在一個雙鏈表達式，刪除*p 結點的操作是_。 38、在一個雙鏈表中，刪除*p 結點之后的一個結點的操作是_。 39、非空的循環(huán)單鏈表 L 的尾結點(由 p 所指向)滿足_。 40、帶頭結點的雙循環(huán)鏈表 L 為空表的條件是_。 41、若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用_帶頭結點 的循環(huán)雙鏈表_存儲方式最節(jié)省運算時間。 42、如果對含有 n(n>1)個元素的線性表的運算只有 4 種:刪除第一個元素；刪除最后一個元素；在第一個元 素前面插入新元素；

31、在最后一個元素的后面插入新元素，則最好使用_只有頭結點指針沒有尾結點指針的 循環(huán)雙鏈表_。 43、 某線性表最常用的操作是在最后一個結點之后插入一個結點或刪除第一個結點， 則采用_僅有尾結點 指針的單循環(huán)鏈表_存儲方式最節(jié)省運算時間。 44、設有兩個長度為 n 的單鏈表，結點類型相同，若以 h1 為頭結點的鏈表是非循環(huán)的，以 h2 為頭結點指針 的鏈表是循環(huán)的，則_。 45、在長度驎 n(n>1)的_只有首結點指針 h 的不帶頭結點的循環(huán)單鏈表_上，刪除第一個元素，其算法的 時間復雜度為 O(n)。 46、元素 A、B、C、D 依次進順序棧后，棧頂元素是_，棧底元素是_。 47、經(jīng)過以下

32、棧運算后，X 的值是_。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x); 48、經(jīng)過以下的棧運算后，StackEmpty(s)的值是_。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y) 49、設一個棧的輸入序列為 A、B、C、D，則借助一個棧所得到的輸出序列不可能是_。 50、若線性表最常用的運算是存取第 i 個元素及其前驅(qū)的值,則采用_存儲方式節(jié)省時間. 51、鏈表不具備的特點是_. 52、在一個長度為 n 的順序存儲的線性表中，向第 i 個元素(1<=i<=n+1

33、)位置插入一個新元素時，需要從后向 前依次后移_個元素 53、 在一個長度為 n 的順序存儲的線性表中， 刪除第 i 個元素(1<=i<=n)時， 需要從前向后依次前移_n-i_ 個元素 54、在一個長度為 n 的線性表中順序查找值為 x 的元素時，查找成功時的平均查找長度（即 x 同元素的平均 比較次數(shù)，查找每個元素的概率都相等）為（ ） 57、在一個單鏈表 HL 中，若要刪除由指針 q 所指向結點的后繼結點，則執(zhí)行_。 數(shù)據(jù)結構復習題：線性表 判斷題 1、順序存儲的線性表可以隨機存取。 2、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同

34、一數(shù) 據(jù)對象。T 3、在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結點查找任何一個元素。 - 12 - 4、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。 5、鏈表的每個結點中，都恰好包含一個指針。 6、線性表中每個元素都有一個直接前驅(qū)和直接后繼。 7、線性表中所有元素的排列順序必須由小到大或由大到小。 8、靜態(tài)鏈表的存儲空間在運算中可以改變大小。 9、靜態(tài)鏈表既有順序存儲結構的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中的第 i 個元素的時間與 i 無關。 10、靜態(tài)鏈表中能容納元素個數(shù)的最大數(shù)在定義時就確定了，以后不能增加。 1

35、1、靜態(tài)鏈表與動態(tài)鏈表的插入、刪除操作類似，不需做元素的移動。 12、線性表的順序存儲結構優(yōu)于鏈式存儲結構。 15、在雙鏈表中，可以從任一結點開始沿同一方向查找任何其他結點。F 數(shù)據(jù)結構復習題：線性表 算法分析題 1、己知一個順序表 L,其中的元素按值非遞減有序排列,設計一個算法插入一個元素 x 后保持該順序表仍按遞 減有序排列。要求算法的空間復雜度為 O(1)。 2、設計一個算法從順序表 L 中刪除所有值為 X 的元素。要求算法的空間復雜度為 O(1)。 3、從順序表 L 中刪除重復的元素,并使剩余元素間的相應次序保持不變.要求本算法的空間復雜記度為 O(1)。 4、 有一個單鏈表(不同結點

36、的數(shù)據(jù)域值可能相同),其頭指針為 head,設計一個算法計算數(shù)據(jù)域為 x 的結點個數(shù)。 5、己知線性表元素遞增有序,并以帶頭結點的單鏈表作存儲結構,設計一個高效算法,刪除表中所有值大于 mink 且小于 maxk 的元素(若表中存在這樣的元素)。并分析所寫算法的時間復雜度。 6、設計一個在帶頭結點的單鏈表中刪除一個最小值結點的高效算法。 7、有一個不帶頭結點的單鏈表 L(至少有 1 人結點),其頭指針為 head,設計一個算法將 L 逆置,即最后一個結點 變成第一個結點,原來倒數(shù)第二個結點變成第二個結點,如此等等。 8、用單鏈表表示集合,設計一個算法求兩個集合的差。要求不破壞原有的結點。 9、

37、用單鏈表表示集合,設計一個算法求兩個集合的并。要求不破壞原有的結點。 10、設計一個算法,將一個頭結點指針為 a 的單鏈表 A 分解成兩個單鏈表 A 和 B,其頭結點指針分別為 a 和 b, 使得 A 鏈表中含有原鏈表 A 中序號為奇數(shù)的元素,而 B 鏈表中含有原鏈表 A 中序號為倒數(shù)的元素,且保持原來 的相對順序。 11、 有一個單鏈表,其結點的元素值以遞增有序排列,設計一個算法刪除該單鏈表中多余的元素值相同的結點。 12、己知兩個存放整數(shù)的有序單鏈表(己按整數(shù)從小至大的順序排序),指針 L1 和 L2 分別指向這兩個單鏈表的 頭結點。設計一個算法,將 L1 和 L2 合并成一個單鏈表,且新

38、的鏈表仍按整數(shù)由小到大的順序排列,新的單鏈表 的結點由 L1 和 L2 的結點構成。要求合并后的單鏈表利用原來單鏈表的存儲空間。 13、設計一個算法,將線性表 lb 連接到 la 之后,要求其時間復雜度為 O(1),占用的輔助空間盡量小。描述所用 的結構。 14、設指針 p 指向雙鏈表中的結點 X,指針 f 指向?qū)⒁迦氲男陆Y點 Y,Y 要插入在結點 X 之后,寫出指針需要修 改的有關步驟。 15、有一個循環(huán)雙鏈表,每個結點由兩個指針(prior 和 next)以及關鍵字(data)構成,p 指向其中某一結點,設計一 個算法從該循環(huán)雙鏈表中刪除 p 所指的結點。 16、設有一個循環(huán)雙鏈表,其中

39、有一結點的指針為 p,設計一個算法將 p 與其后續(xù)結點進行交換。 19、設 A 和 B 是兩個單鏈表(帶頭結點)，其表中元素遞增有序。設計一個算法將 A 和 B 歸并成一個按元素值 遞增有序的單鏈表 C，要求輔助空晨為 O(1)，并分析算法的時間復雜度。 - 13 - 數(shù)據(jù)結構復習題：線性表 填空題 1、在線性結構中第一結點_前驅(qū)結點，其余每個結點有且只有_個前驅(qū)結點；最后一個結點_ 后繼結點。 2、對于順序存儲的線性表，當隨機插入或刪除一個元素時，約需平均移動表長_的元素。 3、對于長度為 n 的順序表，插入或刪除元素的時間復雜性為_；對于順序?；蜿犃?，插入或刪除元 素的時間復雜性為_。 4

40、、在線性表的順序存儲中，元素之間的邏輯關系是通過_相鄰位置_決定的；在線性表的鏈接存儲 中，元素之間的邏輯關系是通過_連接指針_決定的。 5、一個單鏈表中刪除*p 結點時，應執(zhí)行如下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next=_; (4)free(q); 6、對于線性表的順序存儲，需要預先分配好存儲空間，若分配太多則容易造成存儲空間的_，若 分配太少又容易在算法中造成_溢出_，因此適應于數(shù)據(jù)量變化不大的情況；對于線性表的鏈接存儲 (假定采用動態(tài)結點)，不需要_存儲空間，存儲器中的整個_動態(tài)存儲區(qū)_都

41、可供使用，分 配和回收結點都非常方便，能夠有效地利用存儲空間，在算法中不必考慮_溢出_的發(fā)生，因此適應 數(shù)據(jù)量變化較大的情況。 7、從順序表中刪除第 i 個元素時，首先把第 i 個元素賦給_變參或函數(shù)名_帶回，接著從_連接 指針_開始向后的所有元素均_一個位置，最后使線性表的長度_。 8、向一個長度為 n 的順序表中的第 i 個元素(0<=i<=n-1)之前插入一個元素時，需向后移動_個元素。 9、在一個長度為 n 的順序表刪除第 i 個元素(0<=i<=n-1)時，需向前移動_個元素。 10、在單鏈表中設置頭結點的作用是_簡化插入、刪除算法_。 11、在單鏈表中，要刪

42、除某一指定的結點，必須找到該結點的_結點。 12、訪問單鏈表中的結點，必須沿著_指針鏈_依次進行。 13、在雙鏈表中，每個結點有兩個指針域，一個指向_，另一個指向_。 14、在_循環(huán)雙_鏈表上，刪除最后一個結點，其算法的時間復雜度為 O(1)。 15、在一個單鏈表中的 p 所指結點之前插入一個 s 所指結點時，可執(zhí)行如下操作。 (1)s->next=_。 (2)p->next=s; (3)t=p->data; (4)p->data=_。 (5)s-.data=_。 16、在一個單鏈表中刪除 p 所指結點時，應執(zhí)行以下操作： q=p->next; p_data=p-

43、>next->data; p->next=_; free(q); 17、在一個單鏈表中 p 所指結點之后插入一個 s 所指結點時，應執(zhí)行 s->next=_和 p->next=_ 的操作。 18、對于一個具有 n 個結點的單鏈表，在*p 結點后插入一個新結點的時間復雜度是_O(1)_；在給定值 - 14 - 為 x 的結點后插入一后新結點的時間復雜度是_。 19、在線性表的順序存儲中，元素之間的邏輯關系是通過_物理存儲位置_決定的；在線性表的鏈式存儲 中，元素之間的邏輯關系是通過_鏈域的指針值_決定的。 20、在一個長度為 n 的順序表中刪除第 i 個元素(1&l

44、t;=i<=n)時，需向前移動_個元素。 21、為了設置一個空的順序表 L，采用的操作是_L->length=0_。 22、刪除順序表的_元素，不需要移動任何元素。 23、刪除順序表的_最后一個_元素，不需要移動的元素最多。 24、在順序表_元素后面插入一個元素，不需要移動任何元素。 25、插入順序表的_元素，需要移動的元素最多。 26、在長度為 n 的順序表 L 中查找指定元素值的元素，其時間復雜度為_。 27、求單鏈表長度的時間復雜度為_。 28、刪除單鏈表 L 中某結點*p 之后的一個結點，其時間復雜度為_。 29、刪除單鏈表 L 中某結點*p 之前的一個結點，其時間復雜度為

45、_O(n)_。 30、在一個單鏈表(己知每個結點含有數(shù)據(jù)域 data 和指針域 next)中刪除 p 所指結點時，應執(zhí)行以下操作： (1)q=p->next; (2)p->data=q->data; (3)p->next = _; (4)free(q); 31、在一個單鏈表中的 p 所指結點之后插入*s 結點時，應執(zhí)行 s->next=_和 p->next=_的操作。 32、對于一個具有 n 個結點的單鏈表，在*p 結點后插入一個新結點的時間復雜度是_;在給定值為 x 的結點后插入一個新結點的時間復雜度是_。 33、刪除雙鏈表 L 中某結點*p 之后的一個結

46、點，其時間復雜度為_。 34、刪除雙鏈表 L 中某結點*p 之前的一個結點，其時間復雜度為_。 35、在非循環(huán)的_鏈表中，可以用表尾指針代替表頭指針。 36、對于雙鏈表，在兩個結點之間插入一個新結點需要修改的指針共_。 37、在一個雙鏈表中，若要在*p 結點之前插入結點*q，則執(zhí)行的操作是_。 38、循環(huán)單鏈表 L 為空的條件是_。 39、 在單鏈表中,結點與結點之間的邏輯關系不是通過存儲單元的順序來表示的,而是通過_指向下一個結點 的指針_來實現(xiàn)的. 40、對于一個長度為 n 的順序存儲的線性表，在表頭插入元素的時間復雜度為_，在表尾插入元 素的時間復雜度為_。 41、對于一個單鏈接存儲的線

47、性表，在表頭插入結點的時間復雜度為_，在表尾插入元素的時間 復雜度為_。 42、在線性表的順序存儲中，若一個元素的下標為 i，則它的前驅(qū)元素的下標為_，后繼元素的 下標為_。 43、在線性表的單鏈接存儲中，若一個元素所在結點的地址為 p，則其后繼結點的地址為 _p->next_，若 p 為一個數(shù)組 a 中的下標，則其后繼結點的下標的_ap->next_。 44、在循環(huán)單鏈表中，最后一個結點的指針域指向_結點。 45、在雙向鏈表中每個結點包含有兩個指針域，一個指向其_結點，另一個指向其_ 結點。 46、在循環(huán)雙向鏈表中表頭結點的左指針域指向_結點，最后一個結點的右指針域指向 _結點。

48、 47、在以為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為_ 和_。 - 15 - 50、在由數(shù)組 a 中元素結點構成的單鏈表中，在下標為 i 的結點的后面插入一個下標為 j 的結點時，需要進 行的操作為_和_語句。 數(shù)據(jù)結構復習題：線性表 問答題 1、線性表有兩種存儲結構：一是順序表，二是鏈表。試問： (1)兩種存儲表示各有哪些主要優(yōu)缺點? (2)如果有 n 個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自 動地改變。在此情況下，應選用哪種存儲結構?為什么? (3)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表

49、中的元素，那 么，應采用哪種存儲結構?為什么? 解答：(1)順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起 元素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設指示結點之間有序關系的指針 域，存取數(shù)據(jù)元素不如順序存儲方便，但結點的插入、刪除操作十分簡單。 (2)應選用鏈接表存儲結構。 其理由是， 鏈式存儲結構用一組任意的存儲單元依次存儲線性表里各元素， 這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結構，在對元素作插入或刪除運算時，不需要移 動元素，僅修改指針即可。所以很容易實現(xiàn)表的容量擴充。 (3)應選用順序存儲結構。其理由是，每

50、個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元 素在線性表中的序號成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機存取，所 以線性表的順序存儲結構是一種隨機存取的存儲結構。而鏈表則是一種順序存取的存儲結構。 2、用線性表的順序結構來描述一個城市的設計和規(guī)劃合適嗎?為什么? 不合適。因為一個城市的設計和規(guī)劃涉及非常多的項目，很復雜，經(jīng)常需要修改、 擴充和刪除各種信息， 才能適應不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應其需要，故是不合適的。 3、在單鏈表和雙向表中，能否從當前結點出發(fā)訪問到任一結點? 在單鏈表中只能由當前結點訪問其后的任一結點，因為沒有指向其前驅(qū)

51、結點的指針。而在雙向鏈表中， 既有指向后繼結點的指針又有指向前驅(qū)結點的指針，故可由當前結點出發(fā)訪問鏈表中任一結點。 4、編寫下列算法 (1)向類型有 list 的線性表 L 的第 i 個元素（0iL.len）之后插入一個新元素 x。 (2)從類型為 list 的線性表 L 中刪除其值等于 x 的所有元素。 (3)將兩個有序表 A 和 B 合并成一個有序表 C，其中 A，B，C 均為 list 類型的變參。 (1) 解答: status insert(SqList L,int i,ElemType x) / 向線性表 L 中第 i 個元素之后插入值為 x 的新元素 (1) if (L.len =

52、 =m0) error('overflow'); (2) if (i<0) | (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i1;-j ) L.vecj1L.vecj; (4) L.veci1x; (5) L.lenlen1; (2) 解答: status delete(L,x) / 從線性表 L 中刪除其值等于 x 的所有元素 i1; while (i<L.len ) if (L.veci= =x ) - 16 - () for( ji1 ;j<= L.len ;

53、+j) L.vec 5、編寫下列算法，假定單鏈表的表頭指針用 HL 表示，類型為 linklist。 (1)將一個單鏈表中的所有結點按相反次序鏈接。 (2)刪除單鏈表中第 i 個（i1）結點。 (3)刪除單鏈表中由指針 p 所指向的結點。 (4)從帶有附加表頭結點的循環(huán)單鏈表中刪除其值等于 x 的第一個結點。 (5)在單鏈表中指針 p 所指結點之前插入一個值為 x 的新結點。 (6)從循環(huán)單鏈表中查找出最小值。 (7)根據(jù)一維數(shù)組 A(1:n)中順序存儲的具有 n 個元素的線性表建立一個帶有附加表頭結 點的單鏈表。 解答：(1)將一個單鏈表中的所有結點按相反次序鏈接。 (1) 解答: stat

54、us contrary(HL) / 使 HL 單鏈表中的所有結點按相反次序鏈接 pHL ; /p 指向未被逆序的第一個結點，初始指向原表頭結點 HLnil; /HL 指向逆序后的表頭結點，初始值為空 while (p!=nil ) (1) qp; /q 指向?qū)⒈荒嫘蜴溄拥慕Y點 (2) pp.next; (3) q.nextHL; (4) HLq; (2)刪除單鏈表中第 i 個（i1）結點。 (2) 解答:status delete(HL,i) (1) if (i<0) or (HLnil) error('not h&&le'); (2) if (i1 )

55、HLHL->next; return ; (3) j1; pHL; /p 指針所指向的結點，是單鏈表中第 j 6、對鏈表設置頭結點的作用是什么?(至少說出兩條好處) 解答：(1) 對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除表中任何結點，所要做的都是修改前一 結點的指針域，因為任何元素結點都有前驅(qū)結點。若鏈表沒有頭結點，則首元素結點沒有前驅(qū)結點，在其前 插入結點或刪除該結點時操作會復雜些。 (2) 對帶頭結點的鏈表，表頭指針是指向頭結點的非空指針，因此空表與非空表的處理是一樣的。 7、在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針 p 指向某結點，不知道頭指針，能否將結點*p 從相應的 鏈表中刪去？若可以，其時間復雜度各為多少？ 解答：1. 單鏈表。當我們知道指針 p 指向某結點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其 頭指針，所以無法訪問到 p 指針指向的結點的直接前趨。因此無法刪去該結點。 2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知