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

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

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

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

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

6、何種存儲結構有關 | 是根據存儲結構來定義的 | 有算術運算和關系運算兩大類 |必須用程序設計語 言來描述21 、以下說法中 ,不正確的選項是 .數據元素是數據的根本單位 |數據項是數據中不可分割的最小可標識單位 | 數據可由假設干個數據元素構成 |數 據項可由假設干個數據元素構成22、不是算法的根本特性 .可行性 |長度有限 |在規定的時間內完成 | 確定性23、計算機中算法指的是解決某一問題的有限運算序列,它必須具備輸入、輸出、 .可行性、可移植性和可擴充性 | 可行性、有窮性和確定性 | 確定性、有窮性和穩定性| 易讀性、穩定性和確定性24、以下不屬于算法特性的是 .可行性 |有輸入 |

7、確定性 |健壯性25、下面關于算法的說法正確的選項是 .算法最終必須由程序實現 | 算法的有窮性是對于任意的一組輸入值必須在有窮步驟后結束|算法的可行性是指指令不能有二義性 | 以上幾個都是錯誤的26、算法的時間復雜度與 有關問題規模 | 計算機硬件性能 | 編譯程序質量 | 程序設計語言27、算法分析的主要任務是分析 .算法是否具有較好的可讀性 | 算法中是否存在語法錯誤 |算法的功能是否符合設計要求 |算法的執行時間和問 題規模之間的關系28、 某算法的時間復雜度為0(n2)說明該算法的 .問題規模是n2|執行時間等于n2|執行時間與n2成正比|問題規模與n2成正比29、 算法分析的目的是

8、 .找出數據結構的合理性 | 研究算法中輸入和輸出關系 | 分析算法的效率以求改良 | 分析算法的易讀性和文檔性30、線性表是具有 n 個的有限序列。表元素 | 字符 | 數據元素 | 數據項31 、線性表是 。一個有限序列，可以為空 | 一個有限序列，不可以為空 | 一個無限序列，可以為空 | 一個無限序列，不可以為 空32、 線性表采用鏈表存儲時，其地址 。必須是連續的 | 一定是不連續的 | 局部地址必須是連續的 | 連續與否均可以33、 鏈表不具備的特點是 。可隨機訪問任一結點 |插入刪除不需要移動元素 |不必事先估計存儲空間 |所需空間與其長度成正比34、 線性表的靜態存儲結構與順序

9、存儲結構相比優點是 。所有的操作算法實現簡單 | 便于隨機存取 | 便于插入和刪除 | 便于利用零散的存儲器空間35、設線性表有 n 個元素，以下操作中， 在順序表上實現比在鏈表上實現效率更高。輸出第i(1<=i<=n)個元素值|交換第1個元素與第2個元素的值|順序輸出這n個元素的值|輸出與給定值x相 等的元素在線性表中的序號36、對于一個線性表， 既要求能夠較快地進行插入和刪除， 又要求存儲結構能夠反映數據元素之間的邏輯關系，那么應采用 存儲結構。順序|鏈式| 散列| 索引37、設線性表中有 2n 個元素，以下操作中， 在單鏈表上實現要比在順序表上實現效率更高。刪除指定的元素|在

10、最后一個元素的后面插入一個新元素|順序輸出前k個元素|交換第i個元素和第2n-i-1個元素的值(i=0，1，n-1)38、 需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是。單鏈表 | 靜態鏈表 | 線性鏈表 | 順序存儲結構39、 如果最常用其所長的操作是取第i 個結點及其前驅，那么采用 結構方式最節省時間。單鏈表 | 雙鏈表 | 單循環鏈表 | 順序表40、 與單鏈表相比，雙鏈表的優點之一是 。插入、刪除操作更簡單 | 可以進行隨機訪問 | 可以省略表頭指針或表尾指針 | 訪問前后相鄰結點更靈活41 、數據結構在計算機內存中的表示是指 .數據的存儲結構 | 數據結構 |數據

11、的邏輯結構 | 數據元素之間的關系 42、下面程序段的時間復雜度為 O(m)| O(n)|O(m*n)|O(m+n)for(int i=0;i<m;i+)for(int j=0;j<n;j+) aij=i*j;數據結構復習題答案：緒論單項選擇題1 、存儲 | 物理 | 邏輯 | 物理和存儲C1C2C3A4A5B6A7C8A9B10D11AB12AB13B14C2、動態結構和靜態結構 | 緊湊結構和非緊湊結構 | 線性結構和非線性結構 | 內部結構和外部結構 圖 ? A C3、數據的存儲結構 | 數據結構 | 數據的邏輯結構 | 數據元素之間的關系A4、邏輯 | 存儲 | 邏輯和存儲

12、 | 物理A5、 線性表的線性存儲結構優于鏈表存儲結構| 二維數組是其數據元素為線性表的線性表 | 棧的操作方式是先進先出 | 隊列的操作方式是先進后出B6、各結點的值如何 | 結束個數的多少 |對數據有哪些運算 | 所用編程語言實現這種結構是否方便A7、數據的處理方法 | 數據元素的類型 |數據元素之間的關系 |數據的存儲方法C8、 (1)|(1) 、(2)|(1) 、 (4) |(3)A9、 數據元素具有同一特點| 不僅數據元素所包含的數據項的個數要相同，而且對應的數據項的類型要一致|每個數據元素都一樣 |數據元素所包含的數據項的個數要相等B10、 數據元素是數據的最小單位| 數據項是數據

13、的根本單位 | 數據結構是帶結構的數據項的集合 | 一些表面上很不相同的數據可以有相同的邏輯結構D1 1 、數據項 | 數據元素 | 信息項 | 表元素A|B12、(1)數據元素(2)結構|(1 )計算方法(2)關系 |(1 )邏輯存儲 (2)運算|(1) 數據映像(2)算法A|B13、數據和數據之間存在的某種關系 | 元素和元素之間存在某種關系 |元素內部具有某種結構 |數據項和 數據項之間存在某種關系 B14 、動態結構和表態結構 | 緊湊結構和非緊湊結構 | 線性結構和非線性結構 | 內部結構和外部結構C15、數據元素之間邏輯 | 數據項之間邏輯 | 數據類型之間 |存儲結構之間A16、

14、數據的處理方法 |數據元素的類型 | 數據元素之間的關系 | 數據的存儲方法 C17、數據項 | 數據元素 | 數據結構 | 數據類型B18、邏輯結構 | 順序存儲結構 |鏈式存儲結構 | 以上都對 B19、每個結點用占一片連續的存儲區域|所有結點占用一片連續的存儲區域 | 結點的最后一個數據域是指針類型 | 每個結點有多少個后繼 ,就設多少個指針域A20、效率與采用何種存儲結構有關 |是根據存儲結構來定義的 | 有算術運算和關系運算兩大類 |必須用程 序設計語言來描述 A 21、數據元素是數據的根本單位 | 數據項是數據中不可分割的最小可標識單位 | 數據可由假設干個數據元 素構成 | 數據

15、項可由假設干個數據元素構成 D 22、可行性 |長度有限 |在規定的時間內完成 |確定性 B23、可行性、可移植性和可擴充性 | 可行性、有窮性和確定性 | 確定性、有窮性和穩定性 | 易讀性、穩定 性和確定性 B24、可行性 |有輸入|確定性 |健壯性D25、算法最終必須由程序實現 | 算法的有窮性是對于任意的一組輸入值必須在有窮步驟后結束 | 算法的 可行性是指指令不能有二義性 | 以上幾個都是錯誤的 B26、問題規模 | 計算機硬件性能 |編譯程序質量 | 程序設計語言 A27、算法是否具有較好的可讀性 |算法中是否存在語法錯誤 | 算法的功能是否符合設計要求 |算法的執行 時間和問題規

16、模之間的關系 D28、問題規模是n2|執行時間等于n2|執行時間與n2成正比|問題規模與n2成正比C29、找出數據結構的合理性 | 研究算法中輸入和輸出關系 | 分析算法的效率以求改良 | 分析算法的易讀性和文檔性C30、 表元素 | 字符 | 數據元素 | 數據項C31、一個有限序列，可以為空 | 一個有限序列，不可以為空 | 一個無限序列，可以為空 | 一個無限序列， 不可以為空 A32、必須是連續的 | 一定是不連續的 | 局部地址必須是連續的 | 連續與否均可以D33、可隨機訪問任一結點 |插入刪除不需要移動元素 |不必事先估計存儲空間 |所需空間與其長度成正比A34、所有的操作算法實

17、現簡單 | 便于隨機存取 | 便于插入和刪除 | 便于利用零散的存儲器空間 C35、輸出第i(1<=i<=n)個元素值|交換第1個元素與第2個元素的值|順序輸出這n個元素的值|輸出與15A16C17B18B19A20A21D22B23B24D25B26A27D28C29C30C31A32D33A34C35A36B37A38B39B40D41A42C給定值 x 相等的元素在線性表中的序號A36、順序|鏈式|散列|索引B37、 刪除指定的元素|在最后一個元素的后面插入一個新元素|順序輸出前k個元素|交換第i個元素和第2n-i-1個兀素的值(i=0, 1，n-1)A38、單鏈表 | 靜態

18、鏈表 | 線性鏈表 | 順序存儲結構B39、單鏈表 | 雙鏈表 | 單循環鏈表 | 順序表D40、插入、 刪除操作更簡單 | 可以進行隨機訪問| 可以省略表頭指針或表尾指針 | 訪問前后相鄰結點更靈活D41 、數據的存儲結構 |數據結構 |數據的邏輯結構| 數據元素之間的關系A42、 O(m|O(m*n)|O(m+n)C數據結構復習題：緒論判斷題1、數據元素是數據的最小單位。2、數據項是數據的根本單位。3、數據元素是數據的最小單位4、數據對象就是一組任意數據元素的集合5、任何數據結構都具備3 個根本運算 : 插入、刪除和查找 .6、數據是由一些類型相同的數據元素構成的7、數據是邏輯結構與各數據

19、元素在計算機中如何存儲有關8、如果數據元素值發生改變,那么數據的邏輯結構也隨之改變.9、邏輯結構相同的數據 ,可以采用多種不同的存儲方法 .10、邏輯結構相同的數據 ,結點類型也一定相同11、邏輯結構不相同的數據 ,必須采用不同的存儲方式來存儲12、數據的邏輯結構是指數據的各數據項之間的邏輯關系 .13、算法的優劣與算法描述語言有無關，但與所有計算機有關。14、算法可以用不同的語言描述，如果用C或Pascal等高級語言來描述，那么算法實際上就是程序了。15 、程序一定是算法。16、算法最終必須由計算機程序實現。19、健壯的算法不會因非法入輸數據而出現莫名其妙的執行結果。數據結構復習題答案：緒論

20、判斷題1 、 False2、False3、False4、False5、False6、True7、False8、False9、True10、False11、False12、False13、False14、False15、False16、False19 、 True數據結構復習題：緒論算法分析題1、求兩個n階矩形的乘法C=A*B,其算法如下：#define MAX 100void maxtrixmult(int ,float aMAXMAX,bMAXMAX,float cMAXMAX)int i,j,k;float x;for(i=1;i<=n;i+)/ for (j=1;j<=n;j

21、+)/ x=0; / for(k=1;k<=n;k+)/ x+=aik*bkj; / cij=x; / 計算各語句的頻度，并分析該算法的時間復雜度。2、 設n是偶數，試計算運行以下程序段后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,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

22、=%d,x=%d",s,x);(1) 分析算法中語句"s+;"的執行次數； 分析算法中語句"x+=2;"的執行次數；(3) 分析該算法的時間復雜度 ;(4) 假定 n=5, 試指出執行該算法的輸出結果。6、設n是偶數，試計算運行以下程序段后m的值并給出該程序段的時間復雜度。int m=0,i,j;for (i=1;i<=n;i+)for (j=2*i;j<=n;j+)m+;數據結構復習題答案：緒論算法分析題頻度x+=aik*bkj; / 1、答：語句/ n+1/ n(n+1)/ n2/ n2(n+1)for(i=1;i<=n;

23、i+) for (j=1;j<=n;j+) x=0;for(k=1;k<=n;k+)n3cij=x;/ n2 所以： f(n)n+1+ n(n+1)+ n2+ n2(n+1)+ n3+ n2=2n3+4n2+2n+1=O( n3 )2、答： m+n(n-1)O(n2)3、 分析算法中語句s+;的執行次數：n+ (n-1) +(n-2)+1= n(n+1)/2分析算法中語句x+=2;的執行次數：n/2分析該算法的時間復雜度 : O(n2)假定n=5,試指出執行該算法的輸出結果：s=15, x=46、數據結構復習題：緒論填空題1 、一個數據結構在計算機中 稱為存儲結構。2、 數據邏輯結

24、構包括 ， 和三種類型，樹形結構和圖形結構合稱為 。3、 在線性結構中，第一個結點 前驅結點，其余每個結點有且只有 個前驅結點：最后一個結點 后續結點，其余每個結點有且只有 個后續結點。4、在樹形結構中， 樹根結點沒有 結點，其余每個結點有且只有 個前驅結點 ：葉子結點沒有 結點 ,其余每個結點后的后續結點可以 5、 在圖形結構中，每個結點的前驅結點數和后續結點數可以 。6、 線性結構中元素之間存在 關系，樹形結構中元素之間存在 關系，圖形結構中元素之間存在 關系。7、算法的 5 個重要特性是 、 、 、輸入和輸出。8、算法可以用不同的語言描述， 如果用C語言或PASCALS言等高級語言來描述

25、， 那么算法實現上就是程序了。這個斷言是 。9、 數據結構、 數據元素和數據項在計算機中的映射(或表示 )分別稱為存儲結構、 結點和數據域。 這個斷言是o10 、下面程序段的時間復雜度是 。for (i=0;i<n;i+) for(j=0;j<m;j+)Aij=0;11 、下面程序段的時間復雜度是 。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 、下面程序段的時間復雜度是 。i=1;while(i<=n)i=i*3

26、;14、有如下遞歸函數 fact(n), 分析其時間復雜度。 int fact(int n)if (n<=1) return 1;else return (n*fact(n-1);15、指出以下各算法的時間復雜度(1) prime(int n) int i=2;while(n%i!=0 && i<sqrt(n) i+;if (i*1.0>sqrt(n) printf "是一素數 "elseprintf " 不是一素數 "(2) sum1(int n)int p=1,sum=0,i;for (i=1;i<=n;i+)

27、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;sum+=p;return (sum);16、數據的邏輯結構是指 .17、一個數據結構在計算機中的 稱為存儲結構 .18、順序存儲方法是把邏輯上 存儲在物理位置上 里 ;鏈式存儲方法中結點間的邏輯關系是由的.19、數據結構是指研究數據的 和 以及它們之間的相互關系,并對這種結構定義相應的 ,設計出相應的 ,從而確保經過這些運算后所得到的新結構是原來的結構類型.20、一個算法具有 5 個特性

28、:、 、 、輸入和輸出。21、算法的執行時間是 的函數。22、數據的邏輯結構是從邏輯上描述數據,它與數據的 無關 ,是獨立于計算機的 .23、 數據的邏輯結構被分為 、和4種。24、 數據的存儲結構被分為 、和4種。25、 在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著 、 、的聯系。26、 一種抽象數據類型包括 和兩個局部。27、 從一維數組an中順序查找出一個最大值元素的時間復雜度為 ,輸出一個二維數組bmn中所有元素值的時間復雜度為 28、 在下面程序段中，s=s+p語句的執行次數為 ，p*=j語句的執行次數為 ，該程序段的時間復雜度為 。int i=0,s=0;whil

29、e(+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) ，其數量級表示為 。30、從一個數組 a10 中順序查找元素時，假定查找每個元素的概率都相同，那么進行一次查找運算時的平均 查找長度(即同元素的平均比擬次數)為 。31、 從一個數組a7中順序查找元素時，假定查找第1個元素a0的概率為1/3,查找第2個元素a1的概率為 1/4，其找其余元素的概率均相同，那么在查找成功時同元素的平均比擬次數為。32、 對于一個n*n的矩陣A的任意矩陣元素aij,按行存儲時和

30、按列存儲時的地址之差是 。設兩種存儲時的開始存儲地址均為LOC(0,0)，每個元素所占存儲單元數均為d。33、 設有一個二維數組 A1020，按行存放于一個連續的存儲空間中，A00的存儲地址是200,每個數組元素占 1 個存儲字,那么 A62 的存儲字地址是 34、設有一個二維數組 A1020 ,按列為主序存放于一個連續的存儲空間中, A00 的存儲地址是 200,每個數組元素占 1 個存儲字,那么 A62 的存儲字地址是 。37、在線性表的單鏈接存儲結構中,每個結點包含有兩個域,一個叫 ,另一個叫 域。數據結構復習題答案：緒論填空題1 、映射2、線性結構 | 樹形結構 | 圖形結構 |非線性

31、結構3、沒有 |1| 沒有|14、前驅 |1| 后續 | 任意多個5、任意多個6、一對一 |一對多 |多對多7、有窮性 |確定性 |可行性8、錯誤9、正確10、O(n*m)11、O(Vn)12 、 O(n2)13 、 O(log3n)14、O(n)15、O(Vn)|O(n)|O(n2)16、數據元素之間的邏輯關系17、映像 ?表示 ?映像或表示18、相鄰的結點 | 相鄰的存儲單元 | 附加的指針字段表示19 、存儲結構 ?物理結構 | 邏輯結構 | 運算 | 算法20、可行性 |有窮性|確定性21 、問題規模22、存儲結構、物理結構23、集合結構、線性結構、樹形結構、圖形結構(次序無先后)24

32、、順序結構、鏈接結構、索引結構、散列結構(次序無先后)25、1:1|1:N|M:N26、數據 | 操作27、O(n) | O(m*n)28 、n| n(n+1)/ 229、O(n)30、5.531、35/1232、(i-j)*(n-1)*d33、32234、22637、值 | 指針 數據結構復習題：緒論問答題1、當你為解決某一問題而選擇數據結構時,應從哪些方面考慮 ?2、簡述邏輯結構與存儲結構的關系.3、數據運算是數據結構的一個重要方面,試舉例說明兩個數據結構的邏輯結構和存儲方式完全相同,只是對于運算的定義不同 ,因而兩個結構具有顯著不同的特性,那么這兩個數據結構是不同的 .數據結構復習題答案

33、：緒論問答題1、解答：通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的時間 又涉及以下三點：1程序運行時所需輸入的數據總量。2計算機執行每條指令所需的時間。3程序中指令重復執行的次數。2、答：數據的邏輯結構反映數據元素之間的邏輯關系即數據元素之間的關聯方式或“鄰接關系，數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。3、答：棧和隊列的邏輯結構相同，其存儲表示也可相同順序存儲和鏈式存儲，但由于其運算集合不同而成為不同的數據結構。2 線性表沈陽理工大學應用技術學院信息與控制學院計算機科學與技術教研室2022-5-8數據結構復習題：線性表單

34、項選擇題1、 在一個長度為n的順序表中，向第i個元素(1< i < n+1)之前插入一個新元素時， 需向后移動 個元素。2、 從一個具有n個節點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比擬 個結點。3、 在一個單鏈表中， *q結點是*p結點的前驅結點，假設在*q和*p之間插入*s結點， 那么執行。4、 線性表是 。5、 對順序存儲的線性表，設其長度為n,在任何位置上插入或刪除操作都是等概率的，刪除一個元素時大約要移動表中的 個元素。6、 線性表采用鏈式存儲時,其地址 。7、 設單鏈表中指針 p指著結點m，指針f指著將要插入的新結點 X，當x插在鏈表中最后一個結點

35、m之后 時,只要先修改 后修改 p->link=f 即可。8、 在雙向鏈表存儲結構中，刪除p 所指的結點時需修改指針 。9、 在雙向鏈表存儲結構中，刪除p 所指的結點的前趨結點(假設存在)時需修改指針 。10、 根據線性表的鏈式存儲結構，每個結點所含指針的個數，鏈表分為單鏈表和。11、 在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上。12、 鏈表不具備的特點是 。13、 不帶頭結點的單鏈表 head 為空的判定條件是 。14、 帶頭結點的單鏈表的 head 為空的判定條件是 。15、帶頭結點的雙循環表 L 為空表的條件是 。16、 非空的循環單鏈表 head 的尾結點 (由 p

36、所指向 )滿足 。17、 在循環雙鏈表的 p所指結點之前插入s所指結點的操作是。18、 假設某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，那么采用 存儲方式最節省運算時間。19、 某線性表最常用的操作是在最后一個結點之后插入一個結點或刪除第一個結點，故采用存儲方式最節省運算時間。20、 需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是 。21、 如果最常用的操作是取第i 個結點及其前驅，那么采用 存儲方式最節省時間。22、在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 。23、 在一個長度為n(n>1)的單鏈表上，設有

37、頭和尾兩個指針，執行 操作與鏈表的長度有關。24、設線性表有 n 個元素，以下算法中， 在順序表上實現比在鏈表上實現效率更高。25、設線性表中有 2n 個元素，算法 ，在單鏈表上實現要比在順序表上實現效率更高。26、 與單鏈表相比，雙鏈表的優點之一是 。27、如果對線性表的運算只有 4 種，即刪除第一個元素， 刪除最后一個元素， 在第一個元素前面插入新元素，在最后一個元素的后面插入新元素，那么最后使用 。28、如果對線性表的運算只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，那么最好使用 。29、設有兩個長度為 n 的單鏈表， 結點類型相同。 假設以 h1 為表頭指針的鏈表是非循環

38、的， 以 h2 為表頭指針的鏈表是循環的，那么 。30、 在長度為 n 的 上，刪除第一個結點，其算法的時間復度為O(n)。31 、將兩個各有 n 個元素的有序順序表歸并成一個有序順序表，其最少的比擬次數是。32、帶頭結點的單鏈表 L 為空的判定條件是 。33、在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 。34、 在一個長度為n(n>1)的帶頭結點的單鏈表 h上，另設有尾指針r(指向尾結點)，執行操作與鏈 表的長度有關。35、在一個雙鏈表中，在 *p 結點之后插入結點 *q 的操作是 。36 、在一個雙鏈表中，在 *p 結點之前插入 *q 結點的操作是

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

40、方式最節省運算時間。44、設有兩個長度為 n 的單鏈表， 結點類型相同， 假設以 h1 為頭結點的鏈表是非循環的， 以 h2 為頭結點指針的鏈表是循環的，那么 。45、 在長度驎n(n>1)的上，刪除第一個元素，其算法的時間復雜度為0(n)。46、元素 A、 B、 C、 D 依次進順序棧后，棧頂元素是 ，棧底元素是 。47、 經過以下棧運算后，X的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、 經過以下的棧運算后，StackEmpty(s)的值是。InitStack(s);Push(s,a);Push(s,b);P

41、op(s,x);Pop(s,y)49、 設一個棧的輸入序列為A、B、C、D,那么借助一個棧所得到的輸出序列不可能是 。50、 假設線性表最常用的運算是存取第i個元素及其前驅的值，那么采用 存儲方式節省時間51 、鏈表不具備的特點是 .52、 在一個長度為 n的順序存儲的線性表中，向第i個元素(1<=i<=n+1)位置插入一個新元素時，需要從后向前依次后移 個元素53、 在一個長度為n的順序存儲的線性表中，刪除第i個元素(1<=i<=n)時，需要從前向后依次前移 個元素54、 在一個長度為n的線性表中順序查找值為x的元素時，查找成功時的平均查找長度(即 x同元素的平均比擬

42、次數，查找每個元素的概率都相等)為()57、在一個單鏈表 HL中，假設要刪除由指針q所指向結點的后繼結點，那么執行 。數據結構復習題答案：線性表單項選擇題1、 n-1|n-i+1|n-i-1|IB2、 n|n/ 2|(n-1)/ 2|(n+1)/2D3、s->next=p->next; p->next=s;|p->next=s->next; s->next=p;|q->next=s; s->next=p;|p->next=s; s->next=q;C4、 一個有限序列，可以為空。|一個有限序列，不能為空。 |一個無限序列，可以為空。

43、| 一個無限序列，不能為空。A5、n+1|n-1|(n-1)/ 2|nC6、 必須是連續的。|局部地址必須是連續的。 |一定是不連續的。 | 連續與否均可以。 D7、f->link=p;|f->link=p->link;|p->link=f->link;|f=nil;B8、(p->rlink) ->rlink) ->link=p;p->rlink=(p->rlink) ->rlink;|(p->llink) ->rlink=p->rlink;(p->rlink)->llink=p->llink

44、;|p->llink=(p->llink) ->llink;(p->llink) ->llink) ->rlink=p;|(p->llink) ->llink) ->rlink=p;p->llink=(p->llink)->llink; B9、(p->llink) ->llink) ->rlink=p;p->llink=(p->llink) ->llink;|(p->rlink) ->rlink) ->llink=p;p->rlink=(p->rlink)

45、->rlink;|(p->llink) ->rlink=p->rlink;(p->rlink) ->llink=p->llink;| p->llink=(p->llink) ->llink;(p->llink) ->llink) ->rlink=p;A10、循環鏈表 | 多重鏈表 | 普通鏈表 |無頭結點鏈表B11、一定相鄰 | 不一定相鄰 | 有時相鄰 | B12、可隨機訪問任一結點 |插入刪除不需要移動元素 |不必事先估計存儲空間 | 所需空間與其長度成正比 A13 、head=NULL|head->nex

46、t=NULL|head->next=head|head!=NULLA14 、head=NULL|head->next=NULL|head->next=head|head!=NULLB15 、L=NULL|L->next=NULL|L->prior=NULL|L->next=LD16 、p->next=NULL|p=NULL|p->next=head|p=headC17、 p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;|p->prior=s;

47、p->prior->next=s;s->next=p;s->prior=p->prior; |s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;|s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; D18、單鏈表 |給出表頭指針的單循環鏈表|雙鏈表| 帶頭結點的雙循環鏈表 D19、單鏈表 |僅有頭結點的單循環鏈表 |雙鏈表 |僅有尾指針的單循環鏈表 D20、單鏈表 | 靜

48、態鏈表 | 線性鏈表 | 順序存儲結構 B21、單鏈表 |雙鏈表 |單循環鏈表 |順序表D22 、O(1)|O(n)|O(n2)|O(nlog2n)B23、刪除單鏈表中的第一個元素| 刪除單鏈表中的最后一個元素 | 在單鏈表第一個元素前插入一個新元素 | 在單鏈表最后一個元素后插入一個新元素 B24、 輸出第i(O<=i<=n-1)個元素值|交換第0個元素與第1個元素的值|順序輸出這n個元素的值|輸出與給定 值 x 相等的元素在線性表中的序號A25、 刪除所有值為x的元素|在最后一個元素的后面插入一個新元素|順序輸出前k個元素|交換第i個元素和第2n-i-1個元素的值(i=0,i,

49、n-1)A26、 插入、刪除操作更簡單| 可以進行隨機訪問 | 可以省略表頭指針或表尾指針 | 順序訪問相鄰結點更靈活D27、 只有表尾指針沒有頭指針的循環單鏈表| 只有表尾指針沒有表頭指針的非循環雙鏈表 | 只有表頭指針沒有表尾指針的循環雙鏈表| 既有表頭指針也有表尾指針的循環單鏈表C28、 只有表頭指針沒有表尾指針的循環單鏈表| 只有表尾指針沒有表頭指針的循環單鏈表 | 非循環雙鏈表 | 循 環雙鏈表 B29、 對于兩個鏈表來說，刪除第一個結點的操作，其時間復雜度都是0(1)|對于兩個鏈表來說，刪除最后一個結點的操作， 其時間復雜度都是 O(n)| 循環鏈表要比非循環鏈表占用更多的內存空間

50、 |h1 和 h2 是不同類型 的變量B30、 只有表頭指針的不帶表頭結點的循環單鏈表| 只有表尾指針的不帶表頭結點的循環單鏈表 | 只有表尾指針 的帶表頭結點的循環單鏈表 | 只有表頭指針的帶表頭結點的循環單鏈表 A31、n|2n-1|2n|n-1A32、L=NULL|L->next=NULL|L->next=L|L!=NULLB33、0(1)|0(n)|0(門人2)|0(nlog2n)B34、 刪除單鏈表中的第一個元素| 刪除單鏈表中的最后一個元素 |在單鏈表第一個元素前插入一個新元素 |在單鏈表最后一個元素后插入一個新元素B 35、 q->prior=p;p->n

51、ext=q;p->next->prior=q;q->next=p->next;|q->next=p->next;p->next->prior=q;p->next=q;q->prior=p ;|p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;|p->next->prior=q;q->next=p->next;q->prior=p;p->next =q; B36、 p->prior=q;q->ne

52、xt=p;p->prior->next=q;q->prior=p->prior;|q->prior=p->prior;p->prior->next=q;q->next=p;p->prior =q->next;|q->next=p;p->next=q;q->prior->next=q;q->next=p;|p->prior->next=q;q->next=p;q->prior=p->prior;p->pri or=q; D37、 p->prior->ne

53、xxt=p->next;p->next->prior=p->prior;|p->prior=p->prior->prior;p->prior->prior=p;|p->next->prior=p;p- >next=p->next->next;|p->next=p->prior->prior;p->prior=p->rprior->prior A38、 p->next=p->next->next;p->next->next->prior=p;

54、|p->next->prior=p;p->next=p->next->next;|p->next=p->next->next; p->next->prior=p;|p->next->next=p->next;p->next->pror=p; C39 、p->next=NULL|p=NULL|p->next=L|p=L C40 、L->=NULL|L->next->prior=NULL|L->prior=NULL|L->next=LD41、單鏈表 |給出表頭指針的循

55、環單鏈表 |雙鏈表| 帶頭結點的循環雙鏈表D42、只有尾結點指針沒有頭結點指針的循環單鏈表 | 只有尾結點指針沒有頭結點指針的非循環單鏈表 |只有頭 結點指針沒有尾結點指針的循環雙鏈表 | 既有頭結點指針也有尾結點指針的循環單鏈表C43、單鏈表 |僅有頭結點的單循環鏈表 |雙鏈表 |僅有尾結點指針的單循環鏈表 D44、對于兩個鏈表來說，刪除第一個結點的操作，其時間復雜度都是 O(1)| 對于兩個鏈表來說，刪除最后一 個結點的操作，其時間復雜度都是 0(n)|循環鏈表要比非循環鏈表占用更多的內在空間|h1和h2是不同類型的變量B 45、只有首結點指針h的不帶頭結點的循環單鏈表|只有尾結點指針r的

56、不帶頭結點的循環單鏈表|只有尾結點指針r的帶頭結點h的循環單鏈表|只有頭結點h的循環單鏈表A46、 A|B|C|DD|A47、a|b|1|0A48、 a|b|1|0C49、 A、 B、 C、 D|D、 C、 B、 A|A、 C、 D、 B|D 、 A、 B、 CD50、 單鏈表 | 雙鏈表 | 單循環鏈表 | 順序表D 51 、可隨機訪問任一結點 | 插入刪除不需要移動元素 | 不必事先估計存儲空間 | 所需空間與其長度成正比A52、n-i|n-i+1|n-i-1|I53、n-1|n-i+1|n-i-1|IA54、n|n/ 2|(n+1)/ 2|(n-1)/2C57、 p=q->next;p->next=q->next;|p=q->next;q->next=p;|p=q->next;q-next=p->n