數據結構與演算法課後答案趙仲孟

① java演算法背包溢出最小值

java演算法背包溢出最小值最小值-1,即最小值+(-1),即1-0000加1-1111,變成0-1111。

最大值＋1，即0-1111加0-0001，變成1-0000，即最小值最小值－1，即最小值＋（－1)，即1-0000加1-1111，變成0-1111，即最大值正數區間和負數區間形成了循環，正數區間最大值＋1，就進入了負數區間，負數區間最大值＋1，就進入了正數區間。

基本信息

數據結構與演算法課程是電子科技大學於2018年02月26日首次在中國大學MOOC開設的慕課課程、國家精品在線開放課程。該課程授課教師為林劼、戴波、劉震、周益民。據2021年3月中國大學MOOC官網顯示，該課程已開課7次。

數據結構與演算法課程共6個模塊，包括緒論、線性表、查找、排序、遞歸與分治、樹與二叉樹、圖論與貪心演算法、動態規劃等內容。

數據結構與演算法課程是計算機科學與技術的學科基礎課程，也是是計算機圖形學、計算機網路、編譯原理、計算機操作系統等後續課程的基礎理論之一，其應用范圍也早已擴展到圖像處理與模式識別、海量數據挖掘、科學數據處理、復雜網路分析等許多計算機前沿領域。

② 19年3月二級C--數據結構與演算法

1.假設線性表的長度為n，則最壞情況下:

冒泡排序: 需要經過n/2遍的從前往後掃描和n/2遍從後往前掃描，需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。

快速排序: 比較次數也是n(n-1)/2。總的時間復雜度為O(n的平方)。

直接插入排序: 所需要比較的次數為n(n-1)/2。總的時間復雜度為O(n的平方)。

希爾排序所需要比較的次數為O(n的1.5次方)。(時間復雜度小於以上三種)

堆排序: 最壞情況下，其時間復雜度為O(nlogn)。(小於O(n的平方))。

2.根據數據結構中各元素之間前後關系的復雜程度，一般數據結構分為兩大類: 線性結構和非線性結構。

如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點 ②每個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

3.演算法時間復雜度與空間復雜度沒有關系。

4.所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。

為了能夠比較客觀的反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所用的計算機程序設計語言，以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。

5.同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。

演算法分析的目的在於選擇合適演算法和改進演算法。

6.堆排序在平均情況下的時間復雜度與最壞情況下的時間復雜度都是O(nlogn)。

7.二叉鏈表: 以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和第一個孩子下的一個兄弟結點。

  循環鏈表是鏈式存儲結構，循環隊列是線性存儲結構。( 【×】循環鏈表是循環隊列的鏈式存儲結構)

  雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點都有兩個指針，分別指向直接後繼和直接前驅，所以從雙鏈表中的任意一個結點開始都可以很方便地訪問它的前驅結點和後繼結點。

8.數據的邏輯結構由兩個要素: 一是數據元素的集合，通常記為D。二是D上的關系，它反映了D中各元素之間的前後件關系，通常記為R。

即一個數據結構可以表示成B=(D,R)，其中B表示數據結構，為了反映D中各元素之間的前後件關系，一般用二元組來表示。例如，假如a與b是D中的兩個數據，則二元組表示a是b的前件，b是a的後件。

  線性結構用圖形表示更加直觀。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，結構為: 5→1→7→9→3

9.快速排序法是一種互換類的排序方法，但由於比冒泡排序的速度快，因此稱為快速排序。

其基本思想是從線性表中選擇一個元素設為t，將線性表後面小於t的元素移到前面，而前面大於t的元素移到後面，結果就將線性表分成了兩部分，t插入到分界線的位置處，這個過程稱為線性表的分割。

  簡單插入排序法，是指將無序序列中的各元素依次插入到已經有序的線性表中。

  冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換，逐步將線性表變為有序。

  後兩種元素的移動過程中不會產生新的逆序。

10.程序可作為演算法的一種描述。

11.為了降低演算法的空間復雜度，要求演算法盡量採用原地工作，所謂的原地工作是指執行演算法時所使用的額外空間固定。

  一個演算法的空間復雜度一般是指執行這個演算法所需要的內存空間，一個演算法所佔用的存儲空間包括程序所佔的空間，輸入的初始數據所佔的空間以及演算法執行過程中所需要的額外空間。

12.能從任意一個結點開始沒有重復的掃描到所有結點的數據結構是循環鏈表。

13.循環隊列是隊列的一種存儲結構

14.演算法的設計要求包括效率與低存儲量，即要考慮演算法的時間復雜度與空間復雜度。

  演算法的復雜度包括時間復雜度和空間復雜度。

  時間復雜度: 是指執行演算法所需要的計算工作量。

  空間復雜度: 一般是指執行這個演算法所需要的內存空間。

15.棧是一種特殊的線性表。鏈式結構把每一個存儲結點分為數據域與指針域，帶鏈的棧可以通過指針域的變化改變原有的棧的組織數據原則; 而順序棧的棧底指針不變，棧頂指針改變。

16.堆排序在最壞的情況下需要比較nlogn次。

  快速排序，在最壞情況下需要比較n(n-1)/2次。

  順序查找，在最壞情況下需要比較n次。

  最壞情況下，二分查找需要log2n(小於n-1)

  在長度為n的順序表中尋找最大項/最小項時，比較次數最少為1，最多為n-1。

17.如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根節點 ②每一個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱為非線性結構。

18.帶鏈棧空的條件是 top=bottom=NULL

19.滿二叉樹也是完全二叉樹，完全二叉樹不一定是滿二叉樹。對於滿二叉樹和完全二叉樹來說，可以按照程序進行順序存儲，不僅節省了空間，又能方便地確定每一個結點的父結點等於左右子結點的位置，但順序存儲結構對於一般的二叉樹不適用。

20.帶鏈棧隊頭指針與隊尾指針相同，且不為空時，隊列元素個數為1; 若為空時，隊列元素個數為0。

帶鏈棧的棧底指針是隨棧的操作而動態變化的。

21.二叉樹的鏈式存儲結構，也稱為二叉鏈表。在二叉樹中，由於每一個元素可以有兩個後件，因此用於存儲二叉樹的存儲結點的指針域有兩個，所以二叉鏈表屬於非線性結構。

22.線性表由一組元素數據元素構成，各元素的數據類型必須相同，矩陣是一個比較復雜的線性表，線性表除了插入和刪除運算之外，還可以查找，排序，分解，合並等。數組是長度固定的線性表。

23.冒泡排序中，在互換兩個相鄰元素時，只能消除一個逆序; 快速排序及希爾排序中，一次交換可以消除多個逆序。

24.二分法檢索的效率比較高，設線性表有n個元素，則最多的比較次數為log2n，最少檢索次數為1。

25.循環鏈表的結構具有以下兩個特點。一，在循環鏈表中，增加了一個表頭結點，其數據域為任意或者根據需要來設置指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。二、循環鏈表中最後一個節點的指針域不是空，而是指向表頭結點，即在循環鏈表中所有的結點指針構成一個環狀鏈。

26.二叉樹的存儲結構是非線性結構，而完全二叉樹是特殊形態的二叉樹。採用順序存儲的完全二叉樹屬於非線性結構。

27.時間復雜度和計算機運行速度以及存儲空間無關。

演算法的空間復雜度和存儲結構無關。

數據處理效率與數據的存儲結構有關。

28.線性表，向量，棧，隊列都屬於線性結構的順序存儲。

29.循環隊列是隊列的存儲結構。

  循環鏈表是另一種形式的念式存儲結構。

  (✘循環鏈表是循環隊列的鏈式存儲結構。✘)

30.完全二叉樹的總結點為奇數時，葉子結點是總結點加一再除以二。

31.在實際處理中，可以用一位數組來存儲堆序列中的元素，也可以用完全二叉樹來直觀的表示堆的結構。在用完全二叉樹表示堆時，樹中所有非葉子結點值均不小於其左，右子樹的根結點值，因為堆頂元素必須為序列的n個元素的最大項，因此其中序並不是有序序列。

  多重鏈表指表中每個結點由兩個或兩個以上的指針域的鏈表。如果一個非空的數據結構滿足下列兩個條件，①有且只有一個根結點，②每個結點最多有一個前件，也最多有一個後件，則稱該數據結構為線性結構，所以多重鏈表不一定是非線性結構。

  在計算機中二叉樹通常採用鏈式存儲結構，對於滿二叉樹和完全二叉樹來說，可以按層次進行順序存儲。

  排序二叉樹的中序遍歷序列是有序序列。

32.對於一個固定的規模，演算法所執行的基本運算次數還可能與特定的輸入有關。

33.在線性表中尋找最大項時，平均情況下和最壞情況下比較次數都是n-1。

34.在長度為n的順序表中查找一 個元素， 假沒需要查找的元素有一半的機會在表中，並且如果元素在表中，則出現在表中每個位置上的可能性是相

同的。則在平均情況下需要比較的次數大約為_

A.3n/4    B.n    C.n/2  D.n/4

本題的考查知識點是順序表的存儲結構。

因為需要查找的元素有一半機會在表中，所以二分之一的情況下平均比較次數為n/2，另二分之一的情況下平均比較次數為n。總的平均比較次數為(n/2+n) /2-3n/4。

故本題答案為A。

35.設數據結構B=(D, R)，其中

D={a,b,c,d，e，f}

R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}該數據結構為

A.線性結構    B.循環隊列

C.循環鏈表    D.非線性結構

本題的考查知識點是數據結構。

如果一個非控的數據結構滿足下列兩個條件: 1) 有且只有一個根節點; 2) 每一一個結點最多有一一個前件，也最多有一一個後件。則稱該數據結構為線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

數據結構B=(D, R)中， 每一個結點均有一個前件，不符合「有且只有一個根節點」的條件，所以為非線性結構。故本題答案選D。

36.某帶鏈的隊列初始狀態為front=rear=NULL。經過一系列正常的入隊與退隊操作後，front=rear=10。 該隊列中的元素個數為_

A.1    B.0    C.1或0    D.不確定

本題的考查知識點是帶鏈隊列。

在初始狀態為front=rear=NULL的帶鏈隊列入隊時，如果插入的結點既是隊首結點又是隊尾結點，則rear和front同時指向這個結點;否則在循環隊列的隊尾加入一一個新元素，rear指向新增結點的數據域，rear+1, front不變。 退隊時，在循環隊列的排頭位置退出一個元素並賦給指定的變數，front指向第二個結點的數據域，front+1, rear不變。當front=rear=10時， front和rear同時指向這個唯一 元素，所以該隊列中的元素個數為1。

故本題答案為A。

37.若二叉樹沒有葉子結點，則為空二叉樹。

38.某帶鏈棧的初始狀態為top=bottom=NULL, 經過一系列正 常的入棧與退棧操作後，top=10, bottom=20。 該棧中的元素個數為_____。

A.不確定    B. 10    C.1    D.0

本題考查的知識點是棧。

帶鏈的棧是具有棧屬性的鏈表，線性鏈表的存儲單元是不連續的，為把存儲空間中一-些離散的空閑存 儲結點利用起來，把所有空閑的結點組織成一個帶鏈的棧，稱為可利用棧。

線性鏈表執行刪除操作運算時， 被刪除的結點可以」回收到可利用棧，對應於可利用棧的入棧運算;線性鏈表執行插入運算時，需要一個新的結點，可以在可利用棧中取棧頂結點，對應於可利用棧的退棧運算。

可利用棧的入棧運算和退棧運算只需要改動top指針即可。因為是不連續的存儲空間，所以top指針將不會有規律地連續變化，因此無法據此判斷棧中的元素個數。

所以本題答案為A。

③ 求答案啊 - - 數據結構與演算法習題

10.A B C D / － E * +
11.b
12.c
13.b
14.c
15.c(不確定)
16d
17.c
18.c
19a
20b
21.c
22A B C D / + E * -(跟10差不多)
23n
24y
25n
26y
27y
28（沒看懂）
29y
30n
31n