數據結構與演算法分析試題

A. CSharp 筆試題， 哪位能提供一些 C#（數據結構和演算法）方面的面試題 筆試題資源，謝謝

1.列出所有可用於兩個頁面之間傳遞參數的方法。
2.打開一個HTML頁面，要自動提交頁面的一個form，如何實現？請簡單寫出相關的頁面代碼（包括form的主要代碼）
3.C＃的類中，函數Public,Private,Protect,internal限定符各有什麼區別？
4.你對.net的GC的理解,不能超過300字。
5.請寫一個查詢語句：從user表中取出name列中的起始字元是「北京」的全部記錄
6.請你簡單的說明資料庫建立索引的優缺點
7.如果禁用了cookie，是否會影響到session的使用？原因？
8.C＃中Finalize，Dispose有什麼不同？
9.最大公約數
既能被兩個整數整除的最大整數，例如，24與15兩個數的最大公約數為3.求最大公約數可以用求余法來實現。即用兩個整數中最大的整數除以最小的數求余數，然後使用除數除以余數求余，直到余數為0時，之前的除數也就是兩個數的最大公約數。
10.求素數的程序
A.The algorithm is quite simple.Given an array of integers starting at 2.Cross out all multiples of 2.Find the next uncrossed integer,and cross out all of its multiples.Repeat until you have passed the square root of the maximum value.
A.請翻譯上述文字。
B.編程 要求輸入一個正整數（可以寫死在程序中），返回小於這個數的所有素數。

.net工程師面試題：
1)網站發布的時候後台.cs文件會變成.dll文件
問：如何讓html文件變成空白？
2）一個表中的name有很多重復
問1）：如何只顯示重復項？
問2）：如何不顯示重復項？
3）一個網站注冊會員的時候信息將會很多，會需要「下一步」這樣的頁面跳轉，請問當點擊下一步的時候如何對上一頁的信息進行保存（不用資料庫）？

B. 數據結構考試重點

第一章 數據結構基本概念
1、基本概念：理解什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量

第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現

第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示

第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法

第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法

第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法

第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法

第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算

第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算

第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算

C. 關於數據結構的題

三、單項選擇題
（ C ）1. 數據結構中，與所使用的計算機無關的是數據的 結構；
A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲

（ C ）2. 演算法分析的目的是：
A) 找出數據結構的合理性 B) 研究演算法中的輸入和輸出的關系
C) 分析演算法的效率以求改進 D) 分析演算法的易懂性和文檔性

（ A ）3. 演算法分析的兩個主要方面是：
A) 空間復雜性和時間復雜性 B) 正確性和簡明性
C) 可讀性和文檔性 D) 數據復雜性和程序復雜性

（ C ）4. 計算機演算法指的是：
A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調度方法

（ C ）5. 計算機演算法必須具備輸入、輸出和
等5個特性。
A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性
C) 確定性、有窮性和穩定性 D) 易讀性、穩定性和安全性

（ C ）6．數據在計算機存儲器內表示時，物理地址與邏輯地址相同並且是連續的，稱之為：
（A）存儲結構 （B）邏輯結構 （C）順序存儲結構 （D）鏈式存儲結構
（ A ）7. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是
（A）110 （B）108 （C）100 （D）120
（ C ）8. 向一個有127個元素的順序表中插入一個新元素並保持原來順序不變，平均要移動 個元素
（A）8 （B）63.5 （C）63 （D）7
（ AF ）9. 鏈接存儲的存儲結構所佔存儲空間：
（A） 分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針
（B） 只有一部分，存放結點值
（C） 只有一部分，存儲表示結點間關系的指針
（D） 分兩部分，一部分存放結點值，另一部分存放結點所佔單元數
（E）一定是不連續的 （F）連續或不連續都可以
（ B ）10． 線性表L在 情況下適用於使用鏈式結構實現。
（A）需經常修改L中的結點值 （B）需不斷對L進行刪除插入
（C）L中含有大量的結點 （D）L中結點結構復雜

（ A ）11. 棧中元素的進出原則是
A．先進先出 B．後進先出 C．棧空則進 D．棧滿則出
（ C ）12. 若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為
A．i B．n-i C．n-i+1 D．不確定

四、簡答題

1. 試比較順序存儲結構和鏈式存儲結構的優缺點。分別在什麼情況下用二者更適合？
順序存儲結構的主要優點是：
節省存儲空間，結點之間的邏輯關系沒有佔用額外的存儲空間。
可實現對結點的隨機存取。
主要缺點是：在作插入或刪除操作時，可能需移動大量元素。
鏈式存儲結構的主要優點是：
邏輯上相鄰的節點物理上不必相鄰；插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。
缺點是：
比順序存儲結構的存儲密度小；查找結點時鏈式存儲要比順序存儲慢。

2. 順序隊的「假溢出」是怎樣產生的？如何知道循環隊列是空還是滿？
系統作為隊列用的存儲區還沒有滿,但隊列卻發生了溢出,我們把這種現象稱為"假溢出"。
判斷是空是滿的方法為：Q->rear=(Q->rear+1) % QueueSize；

3. 設循環隊列的容量為40（序號從0到39），現經過一系列的入隊和出隊運算後，有
① front=11，rear=19; ② front=19，rear=11；問在這兩種情況下，循環隊列中各有元素多少個？
第一種情況為：N=Q->rear-Q->front=8
第二種情況為：N=Q->rear+40-Q->front=32

D. 演算法與數據結構的問題，急！！！！！！！！！！！

現考慮一將隨後可能用到的多個行星名稱（名稱皆唯一）存儲在一目錄中的問題。針對後續的兩個使用場景，請比較並對比數組、二叉查找樹、avl-樹和使用線性hash函數的hash表，請指出你為達成令下列兩種情況下插入過程最快的目的所選擇的數據結構。
i）從小說中選擇100000個詞插入，其中10000個詞是不重復的（譯者按：即不按字母序隨機插入）
ii）從字典中選擇50000個不同的詞插入，這些詞大部分都是排序的
你只需關心速度性能即可，可暫不考慮內存性能。供參考，log2(10000)約等於13，log2(50000)約等於16，log2(100000)約等於17.
注意：
「比較」意即討論不同數據結構的相似特點
「對比」則是請討論不同數據結構的不同之意。

這題不是選1和2那個方法，1和2是不同場景，第一個是隨機信息的插入，且90%數據是可不用插入的，第二個是有序信息的插入。

這題蠻麻煩，不能保證答對，簡單分析下好了，對於插入操作，基本上都是兩個過程「查找」（順便也決定了插入的位置）和「插入」：

1，數組：得分兩種情況
a，非排序數組，則查找時間復雜度為O(N)，插入復雜度為O(1)，總是插入至最末尾
b，排序數組，使用二分查找，查找時間復雜度為O(log2(N))，插入的話，大部分情況需要移動內存，題中不考慮內存性能，則時間復雜度為O(1)

2，二叉查找樹，也得分兩種情況
a，平衡的，則查找復雜度O(log2(N))，插入基本上是O(1)
b，非平衡，雖然平均查找復雜度還是O(log2(N))，但實際大多數情況都比這個值要大，插入基本O(1)

3，avl-樹，這種樹實質上是也是一種二叉查找樹，它的名字是「自平衡二叉查找樹」，因此它的任何操作都保證他是平衡二叉查找樹，插入時間復雜度見上

4，線性hash函數的hash表，hash表的特點是預分配bucket count個單元，常常採用每個單元存儲一個鏈表的沖突解決方法，他的查找性能取決於樣本key數據在hash函數的圖像上是否是均勻分布的，越均勻效果越高，查找復雜度和插入復雜度都決定於bucket長度、hash函數的選取、沖突的解決方法

結合case1和2分析：

case1：由於插入的是無序數據，且其中90%是重復的（意味著查找性能比插入性能重要），顯然，適當選取bucket值和hash函數（即便是線性函數也有選擇的餘地）和解決沖突方法的hash表性能最好（趨於O(1)），avl-tree次之，排序數組和avl-tree性能相當（因這里插入操作比例低），非平衡二叉查找樹也有類似的性能，非排序數組性能最差。

case2：輸入數據是有序的，仍舊是參數合適的hash表性能最佳，趨於O(1)的時間復雜度，avl-tree次之。排序數組查找復雜度也是log2(N)，由於是有序數據，在大小順序與字典順序一致時，插入復雜度很低，而相反時，插入復雜度很高，每次都要移動幾乎整體的數據。有序數據還導致非平衡的二叉查找樹的左右子樹嚴重失衡，查找復雜度趨於O(N)，性能相當低。非排序數組仍舊是低效的

E. 南京信息工程大學人工智慧835真題分布

第一部分 目標與基本要求
數據結構與演算法分析考試是為南京信息工程大學招收人工智慧
方向碩士研究生而設置的具有選拔性質的全國統一入學考試科目，其目的是科學、公平、有效地測試學生掌握大學本科階段數據結構與演算法分析的基本知識、基本理論，以及運用數據結構與演算法分析的理論和方法分析和解決問題的能力。評價的標準是高等學校本科畢業生能達到的及格或及格以上水平，以保證被錄取者在開展人工智慧方向的研究工作中，具有基本的計算機程序設計、數據結構與演算法分析的理論素質，並具有理解和分析工程實際問題和具有工程實際應用的基本能力。

F. 數據結構與演算法拿什麼搜題

可以使用大學搜題app。
《數據結構與演算法》注重理論與實踐相結合，內容深入淺出，可以作為高等院校計算機學科相關專業的教材或參考書，同時對計算機科技工作者也有參考價值。
《數據結構與演算法》以基本數據結構和演算法設計策略為知識單元，系統地介紹了數據結構的知識與應用、計算機演算法的設計與分析方法，主要內容包括線性表、樹、圖和廣義表、演算法設計策略以及查找與排序演算法等。

G. 求《演算法與數據結構考研試題精析第三版》全文免費下載百度網盤資源,謝謝~

《演算法與數據結構考研試題精析第三版》網路網盤pdf最新全集下載:
鏈接: https://pan..com/s/1hdJxho2NwiuZLzCNLVmA5A

H. 求下面數據結構試題的答案...

一．

1,復雜性2.線性結構非線性結構

3．可以按序號隨機存取4.數據元素

5.後進先出6.n7.只能在隊頭進行

9.長度1深度1

10-+A*BC/DE

11

12頂點Vp到頂點Vq之間的路徑是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13n（n-2）/214n—1152n—1

17一種存儲結構

19可以從表中任意結點開始遍歷整個鏈表；只用一個指向尾結點的指針對鏈表頭、尾進行操作，提高了效率。

20棧是僅限制在表的一端進行插入和刪除的運算的線性表，是一種操作受限的線性表。

二．

1演算法的時間復雜度和空間復雜度

2.隊列

3.

4嵌套集合表示法，廣義表表示法，凹入表示法

5.456.S(1)X(1)S(2)S(3)X(3)S(4)X(4)X(2)

7（1）O（nˆ2）

（2）O（nˆ2）

8.

哈夫曼樹：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.鄰接矩陣：

鄰接表：

10.二叉樹：

前序：ABCEFD

中序：BEFCDA

後序：FEDCBA

I. 求數據結構試題…重點

這是我們老師要求的重點，即考點。列印出來，背一下就行了，准過！
第一章：緒論
1.1：數據結構課程的任務是：討論數據的各種邏輯結構、在計算機中的存儲結構以及各種操作的演算法設計。

1.2：數據：是客觀描述事物的數字、字元以及所有的能輸入到計算機中並能被計算機接收的各種集合的統稱。

數據元素：表示一個事物的一組數據稱作是一個數據元素，是數據的基本單位。

數據項：是數據元素中有獨立含義的、不可分割的最小標識單位。

數據結構概念包含三個方面：數據的邏輯結構、數據的存儲結構的數據的操作。

1.3數據的邏輯結構指數據元素之間的邏輯關系，用一個數據元素的集合定義在此集合上的若干關系來表示，數據結構可以分為三種：線性結構、樹結構和圖。

1.4：數據元素及其關系在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。

數據的存儲結構基本形式有兩種：順序存儲結構和鏈式存儲結構。

2.1：演算法：一個演算法是一個有窮規則的集合，其規則確定一個解決某一特定類型問題的操作序列。演算法規則需滿足以下五個特性：

輸入——演算法有零個或多個輸入數據。
輸出——演算法有一個或多個輸出數據，與輸入數據有某種特定關系。
有窮性——演算法必須在執行又窮步之後結束。
確定性——演算法的每個步驟必須含義明確，無二義性。
可行性——演算法的每步操作必須是基本的，它們的原則上都能夠精確地進行，用筆和紙做有窮次就可以完成。
有窮性和可行性是演算法最重要的兩個特徵。

2.2：演算法與數據結構：演算法建立數據結構之上，對數據結構的操作需用演算法來描述。

演算法設計依賴數據的邏輯結構，演算法實現依賴數據結構的存儲結構。

2.3：演算法的設計應滿足五個目標：

正確性：演算法應確切的滿足應用問題的需求，這是演算法設計的基本目標。
健壯性：即使輸入數據不合適，演算法也能做出適當的處理，不會導致不可控結
高時間效率：演算法的執行時間越短，時間效率越高。 果。
高空間效率：演算法執行時佔用的存儲空間越少，空間效率越高。
可讀性：演算法的可讀性有利於人們對演算法的理解。
2.4：度量演算法的時間效率，時間復雜度，（課本39頁）。

2.5：遞歸定義：即用一個概念本身直接或間接地定義它自己。遞歸定義有兩個條件：

至少有一條初始定義是非遞歸的，如1！=1.
由已知函數值逐步遞推計算出未知函數值，如用（n-1）！定義n！。
第二章：線性表
1.1線性表：線性表是由n(n>=0)個類型相同的數據元素a0,a1,a2,…an-1,組成的有限序列,記作： LinearList = (a0,a1,a2,…an-1)

其中，元素ai可以是整數、浮點數、字元、也可以是對象。n是線性表的元素個數，成為線性表長度。若n=0，則LinearList為空表。若n>0，則a0沒有前驅元素，an-1沒有後繼元素，ai（0<i<n-1）有且僅有一個直接前驅元素ai-1和一個直接後繼元素ai+1。

1.2線性表的順序存儲是用一組連續的內存單元依次存放線性表的數據元素，元素在內存的物理存儲次序與它們在線性表中的邏輯次序相同。

線性表的數據元素數據同一種數據類型，設每個元素佔用c位元組，a0的存儲地址為

Loc（a0），則ai的存儲地址Loc（ai）為：Loc（ai） = Loc（a0）+ i*c

數組是順序存儲的隨機存儲結構，它佔用一組連續的存儲單元，通過下標識別元素，元素地址是下標的線性函數。

1.3：順序表的插入和刪除操作要移動數據元素。平均移動次數是 屬數據表長度的一半。（課本第50頁）

1.4：線性表的鏈式存儲是用若乾地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據元素在物理位置上不一定相鄰，必須採用附加信息表示數據元素之間的順序關系。

它有兩個域組成：數據域和地址域。通常成為節點。（課本第55頁及56頁）

1.5單鏈表（課本56頁）

單鏈表的遍歷：Node<E> p = head; while(p!=null){ 訪問p節點；p = p.next;}

單鏈表的插入和刪除操作非常簡便，只要改變節點間的鏈接關系，不需移動數據元素。

單鏈表的插入操作：1）：空表插入/頭插入 2)中間插入/尾插入

if(head == null) Node<E> q = new Node<E>(x);

{ head = new Node<E>(x); q.next = p.next;

}else{ p.next = q;

Node<E> q=new Node<E>(x); 中間插入或尾插入都不會改變單表

q.next = head; 的頭指針head。

head = q;

}

單鏈表的刪除操作：

頭刪除：head = head.next;
中間/尾刪除：if(p.next!=null){ p.next = p.next.next;}
循環單鏈表：如果單鏈表最後一個節點的next鏈保存單鏈表的頭指針head值，則該單鏈表成為環形結構，稱為循環單鏈表。（課本67）

若rear是單鏈表的尾指針，則執行（rear.next=head;）語句，使單鏈表成為一條循環單鏈表。當head.next==head時，循環單鏈表為空。

1.6：雙鏈表結構：雙鏈表的每個結點有兩個鏈域，分別指向它的前驅和後繼結點，

當head.next==null時，雙鏈表為空。

設p指向雙鏈表中非兩端的某個結點，則成立下列關系：p=p.next.prev=p.prev.next。

雙鏈表的插入和刪除：1）插入 2)刪除

q=new DLinkNode（x）； p.prev.next = p.next;

q.prev=p.prev;q.next =p; if(p.next=null){

p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}

循環雙鏈表：當head.next==head且head.prev==head時，循環雙鏈表為空。

第三章：棧和隊列
1.1棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈式棧。

棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。

棧的進出棧順序：後進先出，先進後出。（及75頁的思考題）。

1.2：隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進行。

向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為隊尾，允許出隊的一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進先出。

第四章：串
1.1：串是一種特殊的線性表，其特殊性在於線性表中的每個元素是一個字元。一個串記為： s=「s0s1s2…sn-1」 其中n>=0,s是串名，一對雙引號括起來的字元序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）為特定字元集合中的一個字元。一個串中包含的字元個數稱為串的長度。

長度為0的串稱為空串，記作「」，而由一個或多個空格字元構成的字元串稱為空格串。

子串：由串s中任意連續字元組成的一個子序列sub稱為s的子串，s稱為sub的主串。子串的序號是指該子串的第一個字元在主串中的序號。

串比較：兩個串可比較是否相等，也可比較大小。兩個串（子串）相等的充要條件是兩個串（子串）的長度相同，並且各對應位置上的字元也相同。

兩個串的大小由對應位置的第一個不同字元的大小決定，字元比較次序是從頭開始依次向後。當兩個串長度不等而對應位置的字元都相同時，較長的串定義為較「大」。

第五章：數組和廣義表
1.1：數組是一種數據結構，數據元素具有相同的數據類型。一維數組的邏輯結構是線性表，多維數組是線性表的擴展。

1.2：一維數組：一維數組採用順序存儲結構。一個一維數組佔用一組連續的存儲單元。

設數組第一個元素a0的存儲地址為Loc（a0），每個元素佔用c位元組，則數組其他元素ai的存儲地址Loc（ai）為： Loc（ai）= Loc（a0）+i*c

數組通過下標識別元素，元素地址是下標的線性函數。一個下標能夠唯一確定一個元素，所劃給的時間是O（1）。因此數組是隨機存取結構，這是數組最大的優點。

1.3：多維數組的遍歷：有兩種次序：行主序和列主序。

行主序：以行為主序，按行遞增訪問數組元素，訪問完第i行的所有元素之後再訪問第i+1行的元素，同一行上按列遞增訪問數組元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)

2)列主序：以列為主序，按列遞增訪問數組元素，訪問完第j列的所有元素之後再訪問第j+1列的元素，同一列上按列遞增訪問數組元素。

多維數組的存儲結構：多維數組也是由多個一維數組組合而成，組合方式有一下兩種。

靜態多維數組的順序存儲結構：可按行主序和列主序進行順序存儲。
按行主序存儲時，元素aij的地址為：Loc（aij）= Loc（a00）+（i*n+j）*c

按列主序存儲時，Loc（aij）= Loc（a00）+（j*m+i）*c

動態多維數組的存儲結構。
二維數組元素地址就是兩個下標的線性函數。無論採用哪種存儲結構，多維數組都是基於一維數組的，因此也只能進行賦值、取值兩種存取操作，不能進行插入，刪除操作。

第六章：

樹是數據元素（結點）之間具有層次關系的非線性結構。在樹結構中，除根以外的結點只有一個直接前驅結點，可以有零至多個直接後繼結點。根沒有前驅結點。

樹是由n（n>=0）個結點組成的有限集合（樹中元素通常稱為結點）。N=0的樹稱為空樹；n>0大的樹T；

@有一個特殊的結點稱為根結點，它只有後繼結點，沒有前驅結點。

@除根結點之外的其他結點分為m（m>=0）個互不相交的集合T0,T1,T3……..,Tm-1，其中每個集合Ti（0<=i<m）本身又是一棵樹，稱為根的子樹。

樹是遞歸定義的。結點是樹大的基本單位，若干個結點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹的每個結點都是該樹中某一棵子樹的根。因此，樹是由結點組成的、結點之間具有層次關系大的非線性結構。

結點的前驅結點稱為其父母結點，反之，結點大的後繼結點稱為其孩子結點。一棵樹中，只有根結點沒有父母結點，其他結點有且僅有一個父母結點。

擁有同一個父母結點的多個結點之間稱為兄弟結點。結點的祖先是指從根結點到其父母結點所經過大的所有結點。結點的後代是指該結點的所有孩子結點，以及孩子的孩子等。

結點的度是結點所擁有子樹的棵數。度為0的結點稱為葉子結點，又叫終端結點；樹中除葉子結點之外的其他結點稱為分支結點，又叫非葉子結點或非終端結點。樹的度是指樹中各結點度的最大值。

結點的層次屬性反應結點處於樹中的層次位置。約定根結點的層次為1，其他結點的層次是其父母結點的層次加1。顯然，兄弟結點的層次相同。

樹的高度或深度是樹中結點的最大層次樹。

設樹中x結點是y結點的父母結點，有序對（x，y）稱為連接這兩個結點的分支，也稱為邊。

設（X0,X1,….,Xk-1）是由樹中結點組成的一個序列，且（Xi，Xi+1）（0<=i<k-1）都是樹中的邊，則該序列稱為從X0到Xk-1的一條路徑。路徑長度為路徑上的邊數。

在樹的定義中，結點的子樹T0，T1…..,Tm-1之間沒有次序，可以交換位置，稱為無序樹，簡稱樹。如果結點的子樹T0,T1……,Tm-1從左到右是有次序的，不能交換位置，則 稱該樹為有序樹。

森林是m（m>=0）棵互不相乾的樹的集合。給森林加上一個根結點就變成一棵樹，將樹的根節點刪除就變成森林。

二叉樹的性質1：若根結點的層次為1，則二叉樹第i層最多有2 的i-1次方（i>=1）個結點。

二叉樹的性質2：在高度為k的二叉樹中，最多有2的k次方減一個結點。

二叉樹的性質3：設一棵二叉樹的葉子結點數為n0,2度結點數為n2，則n0=n2+1。

一棵高度為k的滿二叉樹是具有2的k次方減一個結點的二叉樹。滿二叉樹中每一層的結點數目都達到最大值。對滿二叉樹的結點進行連續編號，約定根節點的序號為0，從根節點開始，自上而下，每層自左至右編號。

一棵具有n個結點高度為k的二叉樹，如果他的每個節點都與高度為k的滿二叉樹中序號為0~n-1

的結點一一對應，則這棵二叉樹為為完全二叉樹。

滿二叉樹是完全二叉樹，而完全二叉樹不一定是滿二叉樹。完全二叉樹的第1~k-1層是滿二叉樹第k層不滿，並且該層所有結點必須集中在該層左邊的若干位置上。

二叉樹的性質4：一棵具有n個結點的完全二叉樹，其高度k=log2n的絕對值+1

二叉樹的性質5：一棵具有n個結點的完全二叉樹，對序號為i的結點，有

@若i=0，則i為根節點，無父母結點；若i>0，則i的父母結點的序號為[（i-1）/2]。

@若2i+1<n，則i的左孩子結點序號為2i+1；否則i無左孩子。

@若2i+2<n，則i的右孩子結點的序號為2i+2，否則i無右孩子。

二叉樹的遍歷

二叉樹的遍歷是按照一定規則和次序訪問二叉樹中的所有結點，並且每個結點僅被訪問一次。

二叉樹的三種次序遍歷

1：先根次序；訪問根節點，遍歷左子樹，遍歷右子樹。

2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。

3：後根次序；遍歷左子樹，遍歷右子樹，訪問根節點。

先根次序遍歷時，最先訪問根節點；後根次序遍歷時，最後訪問根節點；中根次序遍歷時，左子樹上的結點在根節點之前訪問，右子樹上的結點在根節點之後訪問。

二叉樹的插入和刪除操作P147

二叉樹的層次遍歷P149

習題P167 6—10，6—19

第七章

圖是由定點集合及頂點間的關系集合組成的一種數據關邊系。頂點之間的關系成為邊。一個圖G記為G=（V,E），V是頂點A的有限集合，E是邊的有限集合。即 V={A|A屬於某個數據元素集合}

E={(A,B)|A,B屬於V}或E={<A,B>|A,B屬於V且Path（A,B）}其中Path（A,B）表示從頂點A到B的一條單向通路，即Path（A,B）是有方向的。

無向圖中的邊事沒有方向，每條邊用兩個頂點的無序對表示。

有向圖中的邊是有方向，每條邊用兩個頂點的有序對表示。

完全圖指圖的邊數達到最大值。n個頂點的完全圖記為Kn。無向完全圖Kn的邊數為n*（n-1）/2,有向完全圖Kn的邊數為n*（n-1）。

子圖：設圖G==(V,E),G』=(V』,E』)，若V』包含於V且E』包含於E,則稱圖G』是G的子圖。若G』是G的真子圖。

連通圖：在無向圖G中，若從頂點VI到Vj有路徑，則稱Vi和Vj是聯通的。若圖G中任意一對頂點Vi和Vj（Vi不等於Vj）都是聯通的，則稱G為連通圖。非連通圖的極大聯通子圖稱為該圖的聯通分量。

強連通圖：在有向圖中，若在每一對頂點Vi和Vj（Vi不等於Vj）之間都存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，則稱該圖的強連通圖。非強連通圖的極大強連通子圖稱為該圖的強連通圖分量。

圖的遍歷

遍歷圖是指從圖G中任意一個頂點V出發，沿著圖中的邊前行，到達並訪問圖中的所有頂點，且每個頂點僅被訪問一次。遍歷圖要考慮一下三個問題：

@指定遍歷的第一個訪問頂點

@由於一個頂點可能與多個頂點相鄰，因此要在多個鄰接頂點之間約定一種訪問次序。

@由於圖中可能存在迴路，在訪問某個頂點之後，可能沿著某條路徑又回到該頂點。

深度優先搜索

圖的深度優先搜索策略是，訪問某個頂點v，接著尋找v的另一個未被訪問的鄰接頂點w訪問，如此反復執行，走過一條較長路徑到達最遠頂點；若頂點v沒有未被訪問的其他鄰接頂點，則回到前一個被訪問頂點，再尋找其他訪問路徑。

圖的深度優先搜索遍歷演算法P188

聯通的無迴路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。各連通分量均為樹的圖稱為森林，樹是森林。

由於樹中無迴路，因此樹中必定無自身環也無重邊（否則他有迴路）若去掉樹中的任意一條邊，則變成森林，成為非聯通圖；若給樹加上一條邊，形成圖中的一條迴路，則不是樹。P191

生成樹和生成森林：

一個連通無向圖的生成樹是該圖的一個極小聯通生成子圖，它包含原圖中所有頂點（n個）以及足以構成一棵樹的n-1條邊。

一個非聯通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。

圖的生成圖或生成森林不是唯一的，從不同頂點開始、採用不同遍歷可以得到不同的生成樹或森林。

在生成樹中，任何樹中，任何兩個頂點之間只有唯一的一條路徑。

第八章

折半查找演算法描述 P206,P207

二叉排序樹及其查找：

二叉排序樹或者是一棵空樹；或者是具有下列性質的二叉樹：

@每個結點都有一個作為查找依據的關鍵字，所有結點的關鍵字互不相同。

@若一個結點的左子樹不空，則左子樹上所有結點的關鍵字均小於這個節點的關鍵字；

@每個結點的左右子樹也分別為二叉排序樹。

在一棵二叉排序樹中，查找值為value的結點，演算法描述如下：

@從根結點開始，設p指向根結點

@將value與p結點的關鍵字進行比較，若兩者相等，則查找成功；若value值較小，則在p的左子樹中繼續查找；若value值較大，則在p的右子樹中繼續查找。

@重復執行上一步，直到查找成功或p為空，若p為空，則查找不成功。

習題 8-6

第九章

直接插入排序演算法描述：p228

冒泡排序演算法的描述：p232

快速排序演算法描述p233

直接選擇排序演算法描述p236

直接選擇排序演算法實現如下：

Public static void selectSort(int[]table){

for(int i=0;i<table.length-1;i++){

int min=I;

for(int j=i+1;j<table.length;j++){

if(table[j]<table[min])

min=j;

if(min!=i){

int temp=table[i];

table[i]==table[min];

table[min]=temp;

}

}

}

}

堆排序是完全二叉樹的應用，是充分利用完全二叉樹特性的一種選擇排序。

堆定義：設n個元素的數據序列{k0，k1，。。。。kn-1}，當且僅當滿足下列關系

k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]

或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]時，序列{k0，k1…….kn-1}稱為最小堆或最大堆。將最小（大）堆看成是一顆完全二叉樹的層次遍歷序列，則任意一個結點的關鍵字都小於等於（大於等於）它的孩子節點的關鍵字值，由此可知，根結點值最小（大）。根據二叉樹的性質5，完全二叉樹中的第i（0<=i<n）個結點，如果有孩子，則左孩子為第2i+1個結點，右孩子為第2i+2個結點。

希望對你會有所幫助。