⑴ 數據結構與演算法 求高手作答.感激不敬
4121212332
知道有三個錯的你也不公布出來
⑵ 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。
⑶ 求數據結構與演算法分析高人幫忙做下這幾道題目。（希望能給出正確答案，在此謝過！！！）
填空題
1. n-1
因為隊尾指針總是指向空。
2. 1
因為無向圖的鄰接矩陣是對稱的。
3. 61
元素數量=
(rear+max-front) 當front > rear
(front+max-rear) 當rear > front
4. 深度優先搜索演算法
5.
判斷題
1. F
二叉樹就可以用數組存儲。
2. F
當發生沖突時，它要在下一個位置找，但如果該位置已被佔用，仍需要繼續向前。故同
義詞不一定相鄰。
3. F
圖的鄰接矩陣的行列數只取決於頂點數量。
4. F
沒有最快的排序演算法，只有特定條件下的相對較快。
5. T
選擇題
1. D
2. B
Loc(a[6]) = Loc(a[1]) + (6-1)*2
= 90 + 10 =100
3. A
4. C
5. C
進堆排序時，每個元素在最底下的葉子層都有，然後較大的非葉子結點存儲。
6. C
構造一棵二叉樹：
/
* +
A + - F
B C D E
對該二叉樹進行後序遍歷即可。
7. C
折半查找要求查找表有序，並且可以根據下標定位，要求是直接存取。
順序存儲方式：可直接存取，但插入刪除需耗時間
鏈式存儲方式：只能順序存取，插入刪除方便
8. D
二次探測再散列法：
addr(key) = (初始哈希值+di)%表長
di=1、-1、4、-4、9、-9...
addr(15) = 15 % 11 = 4
addr(38) = 38 % 11 = 5
addr(61) = 61 % 11 = 6
addr(84) = 84 % 11 = 7
addr(49) = 49 % 11 = 5 有沖突
addr(49) = (5+1)%14=6 有沖突
addr(49) = (5-1)%14=4 有沖突
addr(49) = (5+4)%14=9
9. D
執行p的後繼指針(next)指向p的直接後繼結點(next)的下一個結點(next)即可
⑷ 我有兩道數據結構的問題 希望能給出詳細解答和做題步驟
數據結構與演算法的地位對於一個程序員來說不言而喻。今天這篇文章不是來勸你們學習數據結構與演算法的，也不是來和你們說數據結構與演算法有多重要。
主要是最近幾天後台有讀者問我是如何學習數據結構與演算法的，有沒有什麼捷徑，是要看視頻還是看書，去哪刷題等.....而且有些還是大三大四的，搞的我都替你們著急、擔心.....
所以我今天就分享下自己平時都是怎麼學習的。
學習演算法的捷徑就是多刷題
說實話，要說捷徑，我覺得就是腳踏實地著多動手去刷題，多刷題。
但是，如果你是小白，也就是說，你連常見的數據結構，如鏈表、樹以及常見的演算法思想，如遞歸、枚舉、動態規劃這些都沒學過，那麼，我不建議你去刷題的。而是先去找本書先去學習這些，然後再去刷題。
也就是說，假如你要去諸如leetcode這些網站刷題，那麼，你要先具備一定的基礎，這些基礎包括：
1、常見數據結構：鏈表、樹(如二叉樹)。
2、常見演算法思想：貪婪法、分治法、窮舉法、動態規劃，回溯法。
以上列出來的算是最基本的吧。就是說你刷題之前，要把這些過一遍再去刷題。如果你連這些最基本的都不知道的話，那麼你再刷題的過程中，會很難受的，思路也會相對比較少。
總之，千萬不要急，先把這些基本的過一遍，力求理解，再去刷題。這些基礎的數據結構與演算法，我是在大一第二學期學的，我沒看視頻，我是通過看書學的，那時候看的書是：
1、演算法分析與分析基礎：這本比較簡單，推薦新手看。
2、數據結構與演算法分析---C語言描述：代碼用C寫的，推薦看。
3、挑戰程序設計競賽(第二版)：也是很不錯的一本書，推薦看。