第一章 數據結構與算法
一.算法的基本概念
計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。
1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報。
2.算法的基本要素：算法中對數據的運算和操作、算法的控制結構。
3.算法設計的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。
4.算法設計的要求：正確性、可讀性、健壯性、效率與低存儲量需求
二.算法的復雜度
1.算法的時間復雜度：指執行算法所需要的計算工作量
2.算法的空間復雜度：執行這個算法所需要的內存空間
三.數據結構的定義
1.數據的邏輯結構：反映數據元素之間的關系的數據元素集合的表示。數據的邏輯結構包括集合、線形結構、樹形結構和圖形結構四種。
2.數據的存儲結構：數據的邏輯結構在計算機存儲空間種的存放形式稱為數據的存儲結構。常用的存儲結構有順序、鏈接、索引等存儲結構。
四.數據結構的圖形表示：
在數據結構中，沒有前件的結點稱為根結點；沒有后件的結點成為終端結點。插入和刪除是對數據結構的兩種基本運算。還有查找、分類、合并、分解、復制和修改等。
五.線性結構和非線性結構
根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構和非線性結構。
線性結構：非空數據結構滿足：有且只有一個根結點；每個結點最多有一個前件，最多只有一個后件。非線性結構：如果一個數據結構不是線性結構，稱之為非線性結構。
常見的線性結構：線性表、棧、隊列
六.線性表的定義
線 性表是n 個元素構成的有限序列（A1，A2，A3……）。表中的每一個數據元素，除了第一個以外，有且只有一個前件。除了最后一個以外有且只有一個后件。即線性表 是一個空表，或可以表示為（a1,a2,……an）, 其中ai(I=1,2,……n)是屬于數據對象的元素，通常也稱其為線性表中的一個結點。
非空線性表有如下一些特征：
（1）有且只有一個根結點a1,它無前件；
（2）有且只有一個終端結點an，它無后件；
（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。線性表中結點的個數n稱為線性表的長度。當n=0時稱為空表。
七.線性表的順序存儲結構
線性表的順序表指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。
線性表的順序存儲結構具備如下兩個基本特征：
1.線性表中的所有元素所占的存儲空間是連續的；
2.線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
即線性表邏輯上相鄰、物理也相鄰，則已知第一個元素首地址和每個元素所占字節數，則可求出任一個元素首地址。
假設線性表的每個元素需占用K個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲位置。則線性表中第i+1個數據元素的存儲位置LOC(ai+1)和第i個數據元素的存儲位置LOC(ai)之間滿足下列關系:
LOC(ai+1)=LOC(ai)+K
LOC(ai)=LOC(a1)+(i-1)*K???? ①
其中，LOC(a1)是線性表的第一個數據元素a1的存儲位置，通常稱做線性表的起始位置或基地址。
因為在順序存儲結構中，每個數據元素地址可以通過公式①計算得到，所以線性表的順序存儲結構是隨機存取的存儲結構。
在線性表的順序存儲結構下，可以對線性表做以下運算：
插入、刪除、查找、排序、分解、合并、復制、逆轉
八.順序表的插入運算
線性表的插入運算是指在表的第I個位置上，插入一個新結點x，使長度為n的線性表（a1,a2 …ai…an）變成長度為n+1的線性表(a1,a2…x,ai…an).
該算法的時間主要花費在循環的結點后移語句上，執行次數是n-I+1。
當I=n+1,最好情況，時間復雜度o(1) 當I=1, 最壞情況，時間復雜度o(n)
算法的平均時間復雜度為o(n)
九.順序表的刪除運算
線性表的刪除運算是指在表的第I個位置上，刪除一個新結點x，使長度為n的線性表（a1,a2 …ai…an）變成長度為n-1的線性表(a1,a2…ai-1,ai+1…an).
當I=n,時間復雜度o(1),當I=1,時間復雜度o(n) ,平均時間復雜度為o(n)
十.棧及其基本運算
1. 什么是棧？ 棧實際上也是一個線性表，只不過是一種特殊的線性表。棧是只能在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除這一端為棧頂（TOP），另一端為 棧底（BOTTOM）。當表中沒有元素時稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后 才能被刪除的元素。
假設棧S=（a1,a2,a3,……an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3……an的次序進棧，退棧的第一個元素應該是棧頂元素。即后進先出。
2.棧的順序存儲及其運算
用S（1：M）作為棧的順序存儲空間。M為棧的最大容量。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
入棧運算：在棧頂位置插入一個新元素。
首先將棧頂指針進一（TOP+1），然后將新元素插入到棧頂指針指向的位置。
退棧運算：指取出棧頂元素并賦給一個指定的變量。
首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一（TOP-1）
讀棧頂元素：將棧頂元素賦給一個指定的變量。棧頂指針不會改變。
十一.隊列及其基本運算
1.什么是隊列
隊列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做對頭，允許插入的一端叫做對尾。
隊列的修改是先進先出。往隊尾插入一個元素成為入隊運算。從對頭刪除一個元素稱為退隊運算。
2.循環隊列及其運算
在 實際應用中，隊列的順序存儲結構一般采用循環隊列的形式。所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間。在循環 隊列中，，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置直到隊 尾指針 rear指向的位置之間所有的元素均為隊列中的元素。
在實際使用循環隊列時，為了能區分隊滿還是隊列空，通常需要增加一個標志S：
隊列空，則S=0，rear=front=m???? 隊列滿，則S=1，rear=front=m
循環隊列主要有兩種基本運算：入隊運算和退隊運算
n????? 入隊運算
指在循環隊列的隊尾加入一個新元素，首先rear=rear+1,當rear=m+1時，置rear=1,然后將新元素插入到隊尾指針指向的位置。當S=1，rear=front,說明隊列已滿，不能進行入隊運算，稱為“上溢”。
n????? 退隊運算
指在循環隊列的排頭位置退出一個元素并賦給指定的變量。首先front=front+1,并當front=m+1時，置front=1,然后將排頭指針指向的元素賦給指定的變量。當循環隊列為空S=0，不能進行退隊運算，這種情況成為“下溢”。
十二.線性單鏈表的結構及其基本運算
1.線性單鏈表的基本概念
一 組任意的存儲單元存儲線性表的數據元素，因此，為了表示每個數據元素ai與其直接后繼數據元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本 身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。這兩部分信息組成數據元素ai的存儲映象，成為結點。它包括兩個域：其中存儲 數據元素信息的域稱為數據域，存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。N個結點鏈結成一個鏈表，即為線性表(a1, a2,……,an)的鏈式存儲結構。又由于此鏈表的每個結點中只包含一個指針域，故又稱線性鏈表或單鏈表。
有時，我們在單鏈表的第一個結點之前附設一個結點，稱之為頭結點，它指向表中第一個結點。頭結點的數據域可以不存儲任何信息，也可存儲如線性表的長度等類的附加信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。
在單鏈表中，取得第I個數據元素必須從頭指針出發尋找，因此，單鏈表是非隨機存取的存儲結構?? 鏈表的形式：單向，雙向
2.線性單鏈表的存儲結構
3帶鏈
3.帶列的棧與隊列
棧也是線性表，也可以采用鏈式存儲結構。
隊列也是線性表，也可以采用鏈式存儲結構。
十三.線性鏈表的基本運算 1.線性鏈表的插入 2.線性鏈表的刪除
十四.雙向鏈表的結構及其基本運算
在雙向鏈表的結點中有兩個指針域，其一指向直接后繼，另一指向直接前驅。
十五.循環鏈表的結構及其基本運算
是另一種形式的鏈式存儲結構，它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。因此，從表中任一結點出發均可找到表中其他結點。
十六.樹的定義
樹是一種簡單的非線性結構。樹型結構的特點：
1.每個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。
2.每一個結點可以有多個后件結點，稱為該結點的子結點。沒有后件的結點稱為葉子結點
3.一個結點所擁有的后件個數稱為樹的結點度
4.樹的最大層次稱為樹的深度。
十七.二叉樹的定義及其基本性質
1.二叉樹是另一種樹型結構，它的特點是每個結點至多只有二棵子樹（即二叉樹中不存在度大于2的結點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。
2.二叉樹的基本性質
①在二叉樹的第I層上至多有2i-1個結點。
②深度為k的二叉樹至多有2k-1個結點(k>=1)
③在任意一個二叉樹中，度為0的結點總是比度為2的結點多一個；
④具有n 個結點的二叉樹，其深度至少為[log2n]+1。
一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。
3.滿二叉樹與完全二叉樹
滿二叉樹：除最后一層以外，每一層上的所有結點都有兩個子結點。在滿二叉樹的第K層上有2K-1個結點，且深度為M的滿二叉樹右2M-1個結點
完全二叉樹：除最后一層以外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。具有N個結點的完全二叉樹的深度為[log2n]+1
完全二叉樹總結點數為N，
若N為奇數，則葉子結點數為（N+1）/2 若N為偶數，則葉子結點數為N/2
4.二叉樹的存儲結構
二叉樹通常采用鏈式存儲結構

二叉樹具有下列重要特性：

??? 性質1 在二叉樹的第i層上至多有2i-1個結點(i≥1)。

???? 利用歸納法容易證得此性質。
???? i=1時，只有一個根結點。 顯然，2i-1=20=1是對的。
???? 現在假定對所有的j，1≤j<i，命題成立，即第j層上至多有2j-1個結點。那么，可以證明j=i時命題也成立。
???? 由歸納假設：第i-1層上至多有2i-2個結點。由于二叉樹的每個結點的度至多為 2，故在第i層上的最大結點數為第i-1層上的最大結點數的2倍，即2*2i-2=2i-1。

??? 性質2 深度為k的二叉樹至多有2k-1個結點，(k≥1)。

??? 由性質1可見，深度為k的二叉樹的最大結點數為
k??????????????????????? k
∑(第i層上的最大結點數) =∑2i-1=2k -1
i=1???????????????????? i=1

??? 性質3 對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。

???? 設n1為二叉樹T中度為1的結點數。因為二叉樹中所有結點的度均小于或等于2所以其結點總數為

n=n0+n1+n2 (6—1)
???? 再看二叉樹中的分支數。除了根結點外，其余結點都有一個分支進入，設B為分支總數，則n=B+1。由于這些分支是由度為1或2的結點射出的，所以又有B=n1+ 2n2。

n=n1+2*n2+1 (6—2)
???? 于是得由式(6—1)和(6—2)得 n0=n2+1

十八.二叉樹的遍歷
就是遵從某種次序，訪問二叉樹中的所有結點，使得每個結點僅被訪問一次。一般先左后右。
1.前序遍歷DLR 首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。
2.中序遍歷LDR 首先遍歷左子樹，然后根結點，最后右子樹
3.后序遍歷LRD 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。
十九.順序查找與二分查找
1.順序查找 在兩種情況下只能用順序查找：線性表為無序表、鏈式存儲結構的有序表
2.二分查找 只適用于順序存儲的有序表（從小到大）。
對于長度為N的有序線性表，在最壞情況下，二分查找只需要比較log2N次，而順序查找要比較N次。 排序：指將一個無序序列整理成按值非遞減順序排列的有序序列。
二十.交換類排序法
冒泡排序與快速排序法屬于交換類的排序方法
1.冒泡排序法 假設線性表的長度為N，則在最壞的情況下，冒跑排序需要經過N/2遍的從前往后的掃描和N/2遍的從后往前的掃描，需要的比較次數為N（N-1）/2
2.快速排序法
二十一.選擇類排序法 1.簡單選擇排序法 2.堆排序法
二十三.插入類排序法 1.簡單插入排序法2.希爾排序法
?????????? 最壞情況下????? 最好情況下????? 說明
交換排序????? 冒泡排序????? n(n-1)/2??????????? 最簡單的交換排序。在待排序的元素序列基本有序的前提下，效率最高
???? 快速排序????? n(n-1)/2????? O(Nlog2 N)????
插入排序????? 簡單插入排序????? n(n-1)/2??????????? 每個元素距其最終位置不遠時適用
???? 希爾排序????? O(n1.5)??????????
選擇排序????? 簡單選擇排序????? n(n-1)/2??????????
???? 堆排序????? O(nlog2n)??????????? 適用于較大規模的線性表
練習：
1.棧和隊列的共同特點是（只允許在端點處插入和刪除元素）
2.如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是（e2,e4,e3,e1）
3.棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是（DCBEA）
4.棧通常采用的兩種存儲結構是（線性存儲結構和鏈表存儲結構）
5.下列關于棧的敘述正確的是（D）
???? A.棧是非線性結構B.棧是一種樹狀結構C.棧具有先進先出的特征D.棧有后進先出的特征
6.鏈表不具有的特點是（B）A.不必事先估計存儲空間?????? B.可隨機訪問任一元素
C.插入刪除不需要移動元素????? D.所需空間與線性表長度成正比
7.用鏈表表示線性表的優點是（便于插入和刪除操作）
8.在單鏈表中，增加頭結點的目的是（方便運算的實現）
9.循環鏈表的主要優點是（從表中任一結點出發都能訪問到整個鏈表）
10.線性表L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
???? A.每個元素都有一個直接前件和直接后件?? B.線性表中至少要有一個元素
???? C.表中諸元素的排列順序必須是由小到大或由大到小
???? D.除第一個和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件
11.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（D）
A.必須是連續的 B.部分地址必須是連續的C.一定是不連續的 D.連續不連續都可以
12.線性表的順序存儲結構和線性表的鏈式存儲結構分別是（隨機存取的存儲結構、順序存取的存儲結構）
13.樹是結點的集合，它的根結點數目是（有且只有1）
14.在深度為5的滿二叉樹中，葉子結點的個數為（31）
15.具有3個結點的二叉樹有（5種形態）
16.設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數為（13）
17.已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）
18.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）
19.若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是（gdbehfca）
20.數據庫保護分為：安全性控制、 完整性控制 、并發性控制和數據的恢復。

1. 在計算機中，算法是指（解題方案的準確而完整的描述）
2.在下列選項中，哪個不是一個算法一般應該具有的基本特征（無窮性）
說明：算法的四個基本特征是：可行性、確定性、有窮性和擁有足夠的情報。
3. 算法一般都可以用哪幾種控制結構組合而成（順序、選擇、循環）
4.算法的時間復雜度是指（算法執行過程中所需要的基本運算次數）
5. 算法的空間復雜度是指（執行過程中所需要的存儲空間）
6. 算法分析的目的是（分析算法的效率以求改進）
7. 下列敘述正確的是（C）
A．算法的執行效率與數據的存儲結構無關
B．算法的空間復雜度是指算法程序中指令（或語句）的條數
C．算法的有窮性是指算法必須能在執行有限個步驟之后終止
D．算法的時間復雜度是指執行算法程序所需要的時間
8.數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及（數據的存儲結構）
9. 數據結構中，與所使用的計算機無關的是數據的（C）
A．存儲結構?? B．物理結構???? C．邏輯結構???? D．物理和存儲結構
10. 下列敘述中，錯誤的是（B）
A．數據的存儲結構與數據處理的效率密切相關
B．數據的存儲結構與數據處理的效率無關
C．數據的存儲結構在計算機中所占的空間不一定是連續的
D．一種數據的邏輯結構可以有多種存儲結構
11. 數據的存儲結構是指（數據的邏輯結構在計算機中的表示）
12. 數據的邏輯結構是指（反映數據元素之間邏輯關系的數據結構）
13. 根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為（線性結構和非線性結構）
14. 下列數據結構具有記憶功能的是（C）A．隊列B．循環隊列C．棧D．順序表
15. 下列數據結構中，按先進后出原則組織數據的是（B）
A．線性鏈表?? B．棧??????????? C．循環鏈表??????? D．順序表
16. 遞歸算法一般需要利用（隊列）實現。
17. 下列關于棧的敘述中正確的是（D）A．在棧中只能插入數據B．在棧中只能刪除數據
C．棧是先進先出的線性表??????????? D．棧是先進后出的線性表
18. 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是（DCBEA）
19.如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是（e2,e4,e3,e1）
20. 由兩個棧共享一個存儲空間的好處是（節省存儲空間，降低上溢發生的機率）
21. 應用程序在執行過程中，需要通過打印機輸出數據時，一般先形成一個打印作業，將其存放在硬盤中的一個指定（隊列）中，當打印機空閑時，就會按先來先服務的方式從中取出待打印的作業進行打印。
22.下列關于隊列的敘述中正確的是（C）A．在隊列中只能插入數據 B．在隊列中只能刪除數據?? C．隊列是先進先出的線性表??????????? D．隊列是先進后出的線性表
23.下列敘述中，正確的是（D）A．線性鏈表中的各元素在存儲空間中的位置必須是連續的
B．線性鏈表中的表頭元素一定存儲在其他元素的前面 C．線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面 D．線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的
24.下列敘述中正確的是（A）A．線性表是線性結構????? B．棧與隊列是非線性結構
C．線性鏈表是非線性結構???????????????????????????????? D．二叉樹是線性結構
25. 線性表L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
A．每個元素都有一個直接前件和直接后件????? B．線性表中至少要有一個元素
C．表中諸元素的排列順序必須是由小到大或由大到小D．除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件
26.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（連續不連續都可以）
27. 鏈表不具有的特點是（B）A．不必事先估計存儲空間??????????? B．可隨機訪問任一元素
C．插入刪除不需要移動元素??????????? D．所需空間與線性表長度成正比
28. 非空的循環單鏈表head的尾結點（由p所指向），滿足（p->next=head）
29.與單向鏈表相比，雙向鏈表的優點之一是（更容易訪問相鄰結點）
30. 在（D）中，只要指出表中任何一個結點的位置，就可以從它出發依次訪問到表中其他所有結點。A．線性單鏈表??????????? B．雙向鏈表??????????? C．線性鏈表??????????? D．循環鏈表
31. 以下數據結構屬于非線性數據結構的是（C）A．隊列????? B．線性表C．二叉樹????? D．棧
32.樹是結點的集合，它的根結點數目是（有且只有1）
33.具有3個結點的二叉樹有（5種形態）
34. 在一棵二叉樹上第8層的結點數最多是（128） 注：2K-1
35. 在深度為5的滿二叉樹中，葉子結點的個數為（16） 注：2n-1
36. 在深度為5的滿二叉樹中，共有（31）個結點。 注：2n－1
37.設一棵完全二叉樹共有699個結點，則在該二叉樹中的葉子結點數為（350）
說明：完全二叉樹總結點數為N，若N為奇數，則葉子結點數為（N+1）/2；若N為偶數，則葉子結點數為N/2。
38. 設有下列二叉樹，對此二叉樹中序遍歷的結果是（B）
A．ABCDEF????
B．DBEAFC
C．ABDECF????
D．DEBFCA
39.已知二叉樹后序遍歷序列是dabec，中序遍歷序列debac，它的前序遍歷序列是（cedba）
40. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）
41.若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是（gdbehfca）
42. 串的長度是（串中所含字符的個數）
43.設有兩個串p和q，求q在p中首次出現位置的運算稱做（模式匹配）
44. N個頂點的連通圖中邊的條數至少為（N-1）
45.N個頂點的強連通圖的邊數至少有（N）
46.對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數為（N）
47. 最簡單的交換排序方法是（冒泡排序）
48.假設線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數為（n(n-1)/2）
49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）
50. 在最壞情況下，下列順序方法中時間復雜度最小的是（堆排序）
51. 希爾排序法屬于（插入類排序）
52. 堆排序法屬于（選擇類排序）
53. 在下列幾種排序方法中，要求內存量最大的是（歸并排序）
54. 已知數據表A中每個元素距其最終位置不遠，為節省時間，應采用（直接插入排序）
55. 算法的基本特征是可行性、確定性、 有窮性?? 和擁有足夠的情報。

1.一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是算法的控制結構。
1. 算法的復雜度主要包括時間復雜度和 空間 復雜度。
2. 實現算法所需的存儲單元多少和算法的工作量大小分別稱為算法的空間復雜度和時間復雜度 。
3.所謂數據處理是指對數據集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析。
4.數據結構是指相互有關聯的 數據元素 的集合。
5.數據結構分為邏輯結構與存儲結構，線性鏈表屬于 存儲結構 。
6.數據結構包括數據的 邏輯 結構和數據的存儲結構。
7. 數據結構包括數據的邏輯結構、數據的 存儲結構 以及對數據的操作運算。
8.數據元素之間的任何關系都可以用 前趨和后繼 關系來描述。
9.數據的邏輯結構有線性結構和非線性結構兩大類。
10.常用的存儲結構有順序、鏈接、 索引 等存儲結構。
11. 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置?? 相鄰 的存儲單元中。
12. 棧的基本運算有三種：入棧、退棧與讀棧頂元素 。
13. 隊列主要有兩種基本運算：入隊運算與 退隊運算 。
14. 在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為 可利用棧 。
15.棧和隊列通常采用的存儲結構是 鏈式存儲和順序存儲?? 。
16.當線性表采用順序存儲結構實現存儲時，其主要特點是 邏輯結構中相鄰的結點在存儲結構中仍相鄰 。
17. 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就 進1 。
18.當循環隊列非空且隊尾指針等于對頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為 上溢?? 。
19.當循環隊列為空時，不能進行退隊運算，這種情況稱為 下溢 。
20. 在一個容量為25的循環隊列中，若頭指針front=16，尾指針rear=9，則該循環隊列中共有 18 個元素。注：當rear<front時，元素個數＝總容量－（front－rear）；
當rear>front時，元素個數＝rear－front。
21. 在一個容量為15的循環隊列中，若頭指針front=6，尾指針rear=9，則該循環隊列中共有3 個元素。
22.順序查找一般是指在 線性表 中查找指定的元素。
23.在計算機中存放線性表，一種最簡單的方法是 順序存儲 。
24.在程序設計語言中，通常定義一個 一維數組 來表示線性表的順序存儲空間。
25.在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數據元素值，稱為數據域，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結點的前一個或后一個結點（即前件或后件）。
26.在 線性單鏈表中 ，每一個結點只有一個指針域，由這個指針只能找到后繼結點，但不能找到前驅結點。
27. 為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個 新結點 ，以便用于存儲該元素的值。
28. 在線性鏈表中刪除一個元素后，只需要改變被刪除元素所在結點的前一個結點的 指針域 即可。
29. 用鏈表表示線性表的突出優點是 便于插入和刪除操作 。
30. 在樹形結構中，樹根結點沒有?? 前件 。
31. 在樹結構中，一個結點所擁有的后件個數稱為該結點的度。葉子結點的度為 0 。
32. 設一棵二叉樹中有3個葉子結點，8個度為1的結點，則該二叉樹中總的結點數為 13。
33. 設一棵完全二叉樹共有739個結點，則在該二叉樹中有 370 個葉子結點。
34. 設一棵完全二叉樹共有700個結點，則在該二叉樹中有 350 個葉子結點。
35. 在先左后右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為三種：前序遍歷、 中序 遍歷和后序遍歷。
36. 若串S="Program"，則其子串的數目是 29 。 注：n(n+1)/2+1
37. 若串S=”MathTypes”，則其子串的數目是 46 。
38. 對長度為n的線性表進行插入一個新元素或刪除一個元素時，在最壞情況下所需要的比較次數為 n 。
39. 在長度為n的有序線性表中進行順序查找。最壞的情況下，需要的比較次數為?? n?? 。
40. 在長度為n的有序線性表中進行二分查找。最壞的情況下，需要的比較次數為 log2n 。
41. 長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數為 n/2 。
42. 排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、 交換排序 和選擇排序等。
43. 快速排序法可以實現通過一次交換而消除多個 逆序 。
44. 快速排序法的關鍵是對線性表進行 分割 。
45. 冒泡排序算法在最好的情況下的元素交換次數為 0 。
46. 在最壞情況下，冒泡排序的時間復雜度為 n(n-1) /2 。
47. 對于長度為n的線性表，在最壞情況下，快速排序所需要的比較次數為 n(n-1) /2 。
48.在最壞情況下，簡單插入排序需要比較的次數為 n(n-1) /2 。
49.在最壞情況下，希爾排序需要比較的次數為 O(n1.5) 。注：括號里是n的1.5次方。
50. 在最壞情況下，簡單選擇排序需要比較的次數為 n(n-1) /2 。
51. 在最壞情況下，堆排序需要比較的次數為 o(nlog2n) 。
52.對于輸入為N個數進行快速排序算法的平均時間復雜度是 O(Nlog2 N)。

總結

以上是生活随笔為你收集整理的数据结构与算法常见笔试题 .的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。