數(shù)據(jù)結(jié)構(gòu)算法題考什么 數(shù)據(jù)結(jié)構(gòu)本科生筆試題
數(shù)據(jù)結(jié)構(gòu)與算法選擇題，求數(shù)據(jù)結(jié)構(gòu)試題…重點(diǎn)，數(shù)據(jù)結(jié)構(gòu)考試重點(diǎn)，數(shù)據(jù)結(jié)構(gòu)大概會(huì)考哪些算法題呢？數(shù)據(jù)結(jié)構(gòu)與算法考試 急急急，數(shù)據(jù)結(jié)構(gòu)與算法選擇題。
本文導(dǎo)航
- 數(shù)據(jù)結(jié)構(gòu)與算法1800題
- 數(shù)據(jù)結(jié)構(gòu)大題試題及答案完整版
- 數(shù)據(jù)結(jié)構(gòu)本科生筆試題
- 數(shù)據(jù)結(jié)構(gòu)和算法之前先學(xué)什么
- 數(shù)據(jù)結(jié)構(gòu)真題匯總
- 數(shù)據(jù)結(jié)構(gòu)?？嫉乃惴?/a>
數(shù)據(jù)結(jié)構(gòu)與算法1800題
第一題，DFS（深度優(yōu)先遍歷）是一個(gè)遞歸算法，在遍歷的過程中，先訪問的點(diǎn)被壓入棧底（棧是先進(jìn)后出），再說：拓?fù)溆行蚴侵溉绻c(diǎn)U到點(diǎn)V有一條弧，則在拓?fù)湫蛄兄蠻一定在V之前。深度優(yōu)先算法搜索路徑恰恰是一條弧，棧的輸出是從最后一個(gè)被訪問點(diǎn)開始輸出，最后一個(gè)輸出的點(diǎn)是第一個(gè)被訪問的點(diǎn)。所以是逆的拓?fù)溆行蛐蛄?/p>
第二題：無向圖路徑長(zhǎng)度是指兩個(gè)頂點(diǎn)之間弧的條數(shù)，如果兩頂點(diǎn)路徑長(zhǎng)度有2條弧，則有3個(gè)頂點(diǎn)例如A——B——C；
第三題：A：極小連通圖是一棵生成樹，只有N-1條邊，但是連通分量可能有N條邊，例如極小連通圖A—— B——C，連通分量“A”——B——C——“A”(這里的最后一個(gè)“A”跟第一個(gè)“A”一致）：；
B:你查下極大強(qiáng)連通子圖概念就明白了；
C:你看看第二題的例子就明白了，AC之間沒有弧，但他們是一個(gè)拓?fù)湫蛄校?/p>
D：例如：環(huán)形圖就不滿足，比如長(zhǎng)方形，四個(gè)頂點(diǎn)，兩種遍歷都能訪問到每個(gè)頂點(diǎn)，但不是完全圖
數(shù)據(jù)結(jié)構(gòu)大題試題及答案完整版
這是我們老師要求的重點(diǎn)，即考點(diǎn)。打印出來，背一下就行了，準(zhǔn)過！
第一章：緒論
1.1：數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)是：討論數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及各種操作的算法設(shè)計(jì)。
1.2：數(shù)據(jù)：是客觀描述事物的數(shù)字、字符以及所有的能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)接收的各種集合的統(tǒng)稱。
數(shù)據(jù)元素：表示一個(gè)事物的一組數(shù)據(jù)稱作是一個(gè)數(shù)據(jù)元素，是數(shù)據(jù)的基本單位。
數(shù)據(jù)項(xiàng)：是數(shù)據(jù)元素中有獨(dú)立含義的、不可分割的最小標(biāo)識(shí)單位。
數(shù)據(jù)結(jié)構(gòu)概念包含三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)的操作。
1.3數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系，用一個(gè)數(shù)據(jù)元素的集合定義在此集合上的若干關(guān)系來表示，數(shù)據(jù)結(jié)構(gòu)可以分為三種：線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖。
1.4：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)基本形式有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
2.1：算法：一個(gè)算法是一個(gè)有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類型問題的操作序列。算法規(guī)則需滿足以下五個(gè)特性：
輸入——算法有零個(gè)或多個(gè)輸入數(shù)據(jù)。
輸出——算法有一個(gè)或多個(gè)輸出數(shù)據(jù)，與輸入數(shù)據(jù)有某種特定關(guān)系。
有窮性——算法必須在執(zhí)行又窮步之后結(jié)束。
確定性——算法的每個(gè)步驟必須含義明確，無二義性。
可行性——算法的每步操作必須是基本的，它們的原則上都能夠精確地進(jìn)行，用筆和紙做有窮次就可以完成。
有窮性和可行性是算法最重要的兩個(gè)特征。
2.2：算法與數(shù)據(jù)結(jié)構(gòu)：算法建立數(shù)據(jù)結(jié)構(gòu)之上，對(duì)數(shù)據(jù)結(jié)構(gòu)的操作需用算法來描述。
算法設(shè)計(jì)依賴數(shù)據(jù)的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)。
2.3：算法的設(shè)計(jì)應(yīng)滿足五個(gè)目標(biāo)：
正確性：算法應(yīng)確切的滿足應(yīng)用問題的需求，這是算法設(shè)計(jì)的基本目標(biāo)。
健壯性：即使輸入數(shù)據(jù)不合適，算法也能做出適當(dāng)?shù)奶幚恚粫?huì)導(dǎo)致不可控結(jié)
高時(shí)間效率：算法的執(zhí)行時(shí)間越短，時(shí)間效率越高。 果。
高空間效率：算法執(zhí)行時(shí)占用的存儲(chǔ)空間越少，空間效率越高。
可讀性：算法的可讀性有利于人們對(duì)算法的理解。
2.4：度量算法的時(shí)間效率，時(shí)間復(fù)雜度，（課本39頁）。
2.5：遞歸定義：即用一個(gè)概念本身直接或間接地定義它自己。遞歸定義有兩個(gè)條件：
至少有一條初始定義是非遞歸的，如1！=1.
由已知函數(shù)值逐步遞推計(jì)算出未知函數(shù)值，如用（n-1）！定義n！。
第二章：線性表
1.1線性表：線性表是由n(n>=0)個(gè)類型相同的數(shù)據(jù)元素a0,a1,a2,…an-1,組成的有限序列,記作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整數(shù)、浮點(diǎn)數(shù)、字符、也可以是對(duì)象。n是線性表的元素個(gè)數(shù)，成為線性表長(zhǎng)度。若n=0，則LinearList為空表。若n>0，則a0沒有前驅(qū)元素，an-1沒有后繼元素，ai（0<i<n-1）有且僅有一個(gè)直接前驅(qū)元素ai-1和一個(gè)直接后繼元素ai+1。
1.2線性表的順序存儲(chǔ)是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲(chǔ)次序與它們?cè)诰€性表中的邏輯次序相同。
線性表的數(shù)據(jù)元素?cái)?shù)據(jù)同一種數(shù)據(jù)類型，設(shè)每個(gè)元素占用c字節(jié)，a0的存儲(chǔ)地址為
Loc（a0），則ai的存儲(chǔ)地址Loc（ai）為：Loc（ai） = Loc（a0）+ i*c
數(shù)組是順序存儲(chǔ)的隨機(jī)存儲(chǔ)結(jié)構(gòu)，它占用一組連續(xù)的存儲(chǔ)單元，通過下標(biāo)識(shí)別元素，元素地址是下標(biāo)的線性函數(shù)。
1.3：順序表的插入和刪除操作要移動(dòng)數(shù)據(jù)元素。平均移動(dòng)次數(shù)是 屬數(shù)據(jù)表長(zhǎng)度的一半。（課本第50頁）
1.4：線性表的鏈?zhǔn)酱鎯?chǔ)是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必須采用附加信息表示數(shù)據(jù)元素之間的順序關(guān)系。
它有兩個(gè)域組成：數(shù)據(jù)域和地址域。通常成為節(jié)點(diǎn)。（課本第55頁及56頁）
1.5單鏈表（課本56頁）
單鏈表的遍歷：Node<E> p = head; while(p!=null){ 訪問p節(jié)點(diǎn)；p = p.next;}
單鏈表的插入和刪除操作非常簡(jiǎn)便，只要改變節(jié)點(diǎn)間的鏈接關(guān)系，不需移動(dòng)數(shù)據(jù)元素。
單鏈表的插入操作：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); 中間插入或尾插入都不會(huì)改變單表
q.next = head; 的頭指針head。
head = q;
}
單鏈表的刪除操作：
頭刪除：head = head.next;
中間/尾刪除：if(p.next!=null){ p.next = p.next.next;}
循環(huán)單鏈表：如果單鏈表最后一個(gè)節(jié)點(diǎn)的next鏈保存單鏈表的頭指針head值，則該單鏈表成為環(huán)形結(jié)構(gòu)，稱為循環(huán)單鏈表。（課本67）
若rear是單鏈表的尾指針，則執(zhí)行（rear.next=head;）語句，使單鏈表成為一條循環(huán)單鏈表。當(dāng)head.next==head時(shí)，循環(huán)單鏈表為空。
1.6：雙鏈表結(jié)構(gòu)：雙鏈表的每個(gè)結(jié)點(diǎn)有兩個(gè)鏈域，分別指向它的前驅(qū)和后繼結(jié)點(diǎn)，
當(dāng)head.next==null時(shí)，雙鏈表為空。
設(shè)p指向雙鏈表中非兩端的某個(gè)結(jié)點(diǎn)，則成立下列關(guān)系：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;}
循環(huán)雙鏈表：當(dāng)head.next==head且head.prev==head時(shí)，循環(huán)雙鏈表為空。
第三章：棧和隊(duì)列
1.1棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進(jìn)行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈?zhǔn)綏！?/p>
棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。
棧的進(jìn)出棧順序：后進(jìn)先出，先進(jìn)后出。（及75頁的思考題）。
1.2：隊(duì)列：隊(duì)列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進(jìn)行。
向隊(duì)列中插入元素的過程稱為入隊(duì)，刪除元素的過程稱為出對(duì)，允許入隊(duì)的一端稱為隊(duì)尾，允許出隊(duì)的一端稱為對(duì)頭。沒有元素的隊(duì)列稱為空隊(duì)列。隊(duì)列是先進(jìn)先出。
第四章：串
1.1：串是一種特殊的線性表，其特殊性在于線性表中的每個(gè)元素是一個(gè)字符。一個(gè)串記為： s=“s0s1s2…sn-1” 其中n>=0,s是串名，一對(duì)雙引號(hào)括起來的字符序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）為特定字符集合中的一個(gè)字符。一個(gè)串中包含的字符個(gè)數(shù)稱為串的長(zhǎng)度。
長(zhǎng)度為0的串稱為空串，記作“”，而由一個(gè)或多個(gè)空格字符構(gòu)成的字符串稱為空格串。
子串：由串s中任意連續(xù)字符組成的一個(gè)子序列sub稱為s的子串，s稱為sub的主串。子串的序號(hào)是指該子串的第一個(gè)字符在主串中的序號(hào)。
串比較：兩個(gè)串可比較是否相等，也可比較大小。兩個(gè)串（子串）相等的充要條件是兩個(gè)串（子串）的長(zhǎng)度相同，并且各對(duì)應(yīng)位置上的字符也相同。
兩個(gè)串的大小由對(duì)應(yīng)位置的第一個(gè)不同字符的大小決定，字符比較次序是從頭開始依次向后。當(dāng)兩個(gè)串長(zhǎng)度不等而對(duì)應(yīng)位置的字符都相同時(shí)，較長(zhǎng)的串定義為較“大”。
第五章：數(shù)組和廣義表
1.1：數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。
1.2：一維數(shù)組：一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)。一個(gè)一維數(shù)組占用一組連續(xù)的存儲(chǔ)單元。
設(shè)數(shù)組第一個(gè)元素a0的存儲(chǔ)地址為L(zhǎng)oc（a0），每個(gè)元素占用c字節(jié)，則數(shù)組其他元素ai的存儲(chǔ)地址Loc（ai）為： Loc（ai）= Loc（a0）+i*c
數(shù)組通過下標(biāo)識(shí)別元素，元素地址是下標(biāo)的線性函數(shù)。一個(gè)下標(biāo)能夠唯一確定一個(gè)元素，所劃給的時(shí)間是O（1）。因此數(shù)組是隨機(jī)存取結(jié)構(gòu)，這是數(shù)組最大的優(yōu)點(diǎn)。
1.3：多維數(shù)組的遍歷：有兩種次序：行主序和列主序。
行主序：以行為主序，按行遞增訪問數(shù)組元素，訪問完第i行的所有元素之后再訪問第i+1行的元素，同一行上按列遞增訪問數(shù)組元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列為主序，按列遞增訪問數(shù)組元素，訪問完第j列的所有元素之后再訪問第j+1列的元素，同一列上按列遞增訪問數(shù)組元素。
多維數(shù)組的存儲(chǔ)結(jié)構(gòu)：多維數(shù)組也是由多個(gè)一維數(shù)組組合而成，組合方式有一下兩種。
靜態(tài)多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)：可按行主序和列主序進(jìn)行順序存儲(chǔ)。
按行主序存儲(chǔ)時(shí)，元素aij的地址為：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存儲(chǔ)時(shí)，Loc（aij）= Loc（a00）+（j*m+i）*c
動(dòng)態(tài)多維數(shù)組的存儲(chǔ)結(jié)構(gòu)。
二維數(shù)組元素地址就是兩個(gè)下標(biāo)的線性函數(shù)。無論采用哪種存儲(chǔ)結(jié)構(gòu)，多維數(shù)組都是基于一維數(shù)組的，因此也只能進(jìn)行賦值、取值兩種存取操作，不能進(jìn)行插入，刪除操作。
第六章：
樹是數(shù)據(jù)元素（結(jié)點(diǎn)）之間具有層次關(guān)系的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，除根以外的結(jié)點(diǎn)只有一個(gè)直接前驅(qū)結(jié)點(diǎn)，可以有零至多個(gè)直接后繼結(jié)點(diǎn)。根沒有前驅(qū)結(jié)點(diǎn)。
樹是由n（n>=0）個(gè)結(jié)點(diǎn)組成的有限集合（樹中元素通常稱為結(jié)點(diǎn)）。N=0的樹稱為空樹；n>0大的樹T；
@有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，沒有前驅(qū)結(jié)點(diǎn)。
@除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m（m>=0）個(gè)互不相交的集合T0,T1,T3……..,Tm-1，其中每個(gè)集合Ti（0<=i<m）本身又是一棵樹，稱為根的子樹。
樹是遞歸定義的。結(jié)點(diǎn)是樹大的基本單位，若干個(gè)結(jié)點(diǎn)組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹的每個(gè)結(jié)點(diǎn)都是該樹中某一棵子樹的根。因此，樹是由結(jié)點(diǎn)組成的、結(jié)點(diǎn)之間具有層次關(guān)系大的非線性結(jié)構(gòu)。
結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為其父母結(jié)點(diǎn)，反之，結(jié)點(diǎn)大的后繼結(jié)點(diǎn)稱為其孩子結(jié)點(diǎn)。一棵樹中，只有根結(jié)點(diǎn)沒有父母結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個(gè)父母結(jié)點(diǎn)。
擁有同一個(gè)父母結(jié)點(diǎn)的多個(gè)結(jié)點(diǎn)之間稱為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的祖先是指從根結(jié)點(diǎn)到其父母結(jié)點(diǎn)所經(jīng)過大的所有結(jié)點(diǎn)。結(jié)點(diǎn)的后代是指該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，以及孩子的孩子等。
結(jié)點(diǎn)的度是結(jié)點(diǎn)所擁有子樹的棵數(shù)。度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，又叫終端結(jié)點(diǎn)；樹中除葉子結(jié)點(diǎn)之外的其他結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，又叫非葉子結(jié)點(diǎn)或非終端結(jié)點(diǎn)。樹的度是指樹中各結(jié)點(diǎn)度的最大值。
結(jié)點(diǎn)的層次屬性反應(yīng)結(jié)點(diǎn)處于樹中的層次位置。約定根結(jié)點(diǎn)的層次為1，其他結(jié)點(diǎn)的層次是其父母結(jié)點(diǎn)的層次加1。顯然，兄弟結(jié)點(diǎn)的層次相同。
樹的高度或深度是樹中結(jié)點(diǎn)的最大層次樹。
設(shè)樹中x結(jié)點(diǎn)是y結(jié)點(diǎn)的父母結(jié)點(diǎn)，有序?qū)Γ▁，y）稱為連接這兩個(gè)結(jié)點(diǎn)的分支，也稱為邊。
設(shè)（X0,X1,….,Xk-1）是由樹中結(jié)點(diǎn)組成的一個(gè)序列，且（Xi，Xi+1）（0<=i<k-1）都是樹中的邊，則該序列稱為從X0到Xk-1的一條路徑。路徑長(zhǎng)度為路徑上的邊數(shù)。
在樹的定義中，結(jié)點(diǎn)的子樹T0，T1…..,Tm-1之間沒有次序，可以交換位置，稱為無序樹，簡(jiǎn)稱樹。如果結(jié)點(diǎn)的子樹T0,T1……,Tm-1從左到右是有次序的，不能交換位置，則 稱該樹為有序樹。
森林是m（m>=0）棵互不相干的樹的集合。給森林加上一個(gè)根結(jié)點(diǎn)就變成一棵樹，將樹的根節(jié)點(diǎn)刪除就變成森林。
二叉樹的性質(zhì)1：若根結(jié)點(diǎn)的層次為1，則二叉樹第i層最多有2 的i-1次方（i>=1）個(gè)結(jié)點(diǎn)。
二叉樹的性質(zhì)2：在高度為k的二叉樹中，最多有2的k次方減一個(gè)結(jié)點(diǎn)。
二叉樹的性質(zhì)3：設(shè)一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為n0,2度結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。
一棵高度為k的滿二叉樹是具有2的k次方減一個(gè)結(jié)點(diǎn)的二叉樹。滿二叉樹中每一層的結(jié)點(diǎn)數(shù)目都達(dá)到最大值。對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定根節(jié)點(diǎn)的序號(hào)為0，從根節(jié)點(diǎn)開始，自上而下，每層自左至右編號(hào)。
一棵具有n個(gè)結(jié)點(diǎn)高度為k的二叉樹，如果他的每個(gè)節(jié)點(diǎn)都與高度為k的滿二叉樹中序號(hào)為0~n-1
的結(jié)點(diǎn)一一對(duì)應(yīng)，則這棵二叉樹為為完全二叉樹。
滿二叉樹是完全二叉樹，而完全二叉樹不一定是滿二叉樹。完全二叉樹的第1~k-1層是滿二叉樹第k層不滿，并且該層所有結(jié)點(diǎn)必須集中在該層左邊的若干位置上。
二叉樹的性質(zhì)4：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其高度k=log2n的絕對(duì)值+1
二叉樹的性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)序號(hào)為i的結(jié)點(diǎn)，有
@若i=0，則i為根節(jié)點(diǎn)，無父母結(jié)點(diǎn)；若i>0，則i的父母結(jié)點(diǎn)的序號(hào)為[（i-1）/2]。
@若2i+1<n，則i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無左孩子。
@若2i+2<n，則i的右孩子結(jié)點(diǎn)的序號(hào)為2i+2，否則i無右孩子。
二叉樹的遍歷
二叉樹的遍歷是按照一定規(guī)則和次序訪問二叉樹中的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問一次。
二叉樹的三種次序遍歷
1：先根次序；訪問根節(jié)點(diǎn)，遍歷左子樹，遍歷右子樹。
2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。
3：后根次序；遍歷左子樹，遍歷右子樹，訪問根節(jié)點(diǎn)。
先根次序遍歷時(shí)，最先訪問根節(jié)點(diǎn)；后根次序遍歷時(shí)，最后訪問根節(jié)點(diǎn)；中根次序遍歷時(shí)，左子樹上的結(jié)點(diǎn)在根節(jié)點(diǎn)之前訪問，右子樹上的結(jié)點(diǎn)在根節(jié)點(diǎn)之后訪問。
二叉樹的插入和刪除操作P147
二叉樹的層次遍歷P149
習(xí)題P167 6—10，6—19
第七章
圖是由定點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)關(guān)邊系。頂點(diǎn)之間的關(guān)系成為邊。一個(gè)圖G記為G=（V,E），V是頂點(diǎn)A的有限集合，E是邊的有限集合。即 V={A|A屬于某個(gè)數(shù)據(jù)元素集合}
E={(A,B)|A,B屬于V}或E={<A,B>|A,B屬于V且Path（A,B）}其中Path（A,B）表示從頂點(diǎn)A到B的一條單向通路，即Path（A,B）是有方向的。
無向圖中的邊事沒有方向，每條邊用兩個(gè)頂點(diǎn)的無序?qū)Ρ硎尽?/p>
有向圖中的邊是有方向，每條邊用兩個(gè)頂點(diǎn)的有序?qū)Ρ硎尽?/p>
完全圖指圖的邊數(shù)達(dá)到最大值。n個(gè)頂點(diǎn)的完全圖記為Kn。無向完全圖Kn的邊數(shù)為n*（n-1）/2,有向完全圖Kn的邊數(shù)為n*（n-1）。
子圖：設(shè)圖G==(V,E),G’=(V’,E’)，若V’包含于V且E’包含于E,則稱圖G’是G的子圖。若G’是G的真子圖。
連通圖：在無向圖G中，若從頂點(diǎn)VI到Vj有路徑，則稱Vi和Vj是聯(lián)通的。若圖G中任意一對(duì)頂點(diǎn)Vi和Vj（Vi不等于Vj）都是聯(lián)通的，則稱G為連通圖。非連通圖的極大聯(lián)通子圖稱為該圖的聯(lián)通分量。
強(qiáng)連通圖：在有向圖中，若在每一對(duì)頂點(diǎn)Vi和Vj（Vi不等于Vj）之間都存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，則稱該圖的強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱為該圖的強(qiáng)連通圖分量。
圖的遍歷
遍歷圖是指從圖G中任意一個(gè)頂點(diǎn)V出發(fā)，沿著圖中的邊前行，到達(dá)并訪問圖中的所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次。遍歷圖要考慮一下三個(gè)問題：
@指定遍歷的第一個(gè)訪問頂點(diǎn)
@由于一個(gè)頂點(diǎn)可能與多個(gè)頂點(diǎn)相鄰，因此要在多個(gè)鄰接頂點(diǎn)之間約定一種訪問次序。
@由于圖中可能存在回路，在訪問某個(gè)頂點(diǎn)之后，可能沿著某條路徑又回到該頂點(diǎn)。
深度優(yōu)先搜索
圖的深度優(yōu)先搜索策略是，訪問某個(gè)頂點(diǎn)v，接著尋找v的另一個(gè)未被訪問的鄰接頂點(diǎn)w訪問，如此反復(fù)執(zhí)行，走過一條較長(zhǎng)路徑到達(dá)最遠(yuǎn)頂點(diǎn)；若頂點(diǎn)v沒有未被訪問的其他鄰接頂點(diǎn)，則回到前一個(gè)被訪問頂點(diǎn)，再尋找其他訪問路徑。
圖的深度優(yōu)先搜索遍歷算法P188
聯(lián)通的無回路的無向圖，簡(jiǎn)稱樹。樹中的懸掛點(diǎn)又成為樹葉，其他頂點(diǎn)稱為分支點(diǎn)。各連通分量均為樹的圖稱為森林，樹是森林。
由于樹中無回路，因此樹中必定無自身環(huán)也無重邊（否則他有回路）若去掉樹中的任意一條邊，則變成森林，成為非聯(lián)通圖；若給樹加上一條邊，形成圖中的一條回路，則不是樹。P191
生成樹和生成森林：
一個(gè)連通無向圖的生成樹是該圖的一個(gè)極小聯(lián)通生成子圖，它包含原圖中所有頂點(diǎn)（n個(gè)）以及足以構(gòu)成一棵樹的n-1條邊。
一個(gè)非聯(lián)通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。
圖的生成圖或生成森林不是唯一的，從不同頂點(diǎn)開始、采用不同遍歷可以得到不同的生成樹或森林。
在生成樹中，任何樹中，任何兩個(gè)頂點(diǎn)之間只有唯一的一條路徑。
第八章
折半查找算法描述 P206,P207
二叉排序樹及其查找：
二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：
@每個(gè)結(jié)點(diǎn)都有一個(gè)作為查找依據(jù)的關(guān)鍵字，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。
@若一個(gè)結(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于這個(gè)節(jié)點(diǎn)的關(guān)鍵字；
@每個(gè)結(jié)點(diǎn)的左右子樹也分別為二叉排序樹。
在一棵二叉排序樹中，查找值為value的結(jié)點(diǎn)，算法描述如下：
@從根結(jié)點(diǎn)開始，設(shè)p指向根結(jié)點(diǎn)
@將value與p結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若兩者相等，則查找成功；若value值較小，則在p的左子樹中繼續(xù)查找；若value值較大，則在p的右子樹中繼續(xù)查找。
@重復(fù)執(zhí)行上一步，直到查找成功或p為空，若p為空，則查找不成功。
習(xí)題 8-6
第九章
直接插入排序算法描述：p228
冒泡排序算法的描述：p232
快速排序算法描述p233
直接選擇排序算法描述p236
直接選擇排序算法實(shí)現(xiàn)如下：
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;
}
}
}
}
堆排序是完全二叉樹的應(yīng)用，是充分利用完全二叉樹特性的一種選擇排序。
堆定義：設(shè)n個(gè)元素的數(shù)據(jù)序列{k0，k1，。。。。kn-1}，當(dāng)且僅當(dāng)滿足下列關(guān)系
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]時(shí)，序列{k0，k1…….kn-1}稱為最小堆或最大堆。將最小（大）堆看成是一顆完全二叉樹的層次遍歷序列，則任意一個(gè)結(jié)點(diǎn)的關(guān)鍵字都小于等于（大于等于）它的孩子節(jié)點(diǎn)的關(guān)鍵字值，由此可知，根結(jié)點(diǎn)值最?。ù螅?。根據(jù)二叉樹的性質(zhì)5，完全二叉樹中的第i（0<=i<n）個(gè)結(jié)點(diǎn)，如果有孩子，則左孩子為第2i+1個(gè)結(jié)點(diǎn)，右孩子為第2i+2個(gè)結(jié)點(diǎn)。
希望對(duì)你會(huì)有所幫助。
數(shù)據(jù)結(jié)構(gòu)本科生筆試題
二叉樹 鏈表 哈夫曼 堆棧 隊(duì)列 還有排序
其中都是以鏈表和數(shù)組為核心
數(shù)據(jù)結(jié)構(gòu)和算法之前先學(xué)什么
是呀，時(shí)間緊迫得有所取舍，第一年統(tǒng)考沒有底，連個(gè)參考的都沒有::81::
數(shù)據(jù)結(jié)構(gòu)真題匯總
第一題：typedef struct node { elemtype data; elemtype code; struct node *next; }Lnode; 第二題，因?yàn)楦咝实乃惴▽?duì)要查找的序列要求高，如二分查找要求查找序列有序，低效率的查找對(duì)查找的序列要求很低，甚至沒有要求。第三問：折半查找的算法思想是將數(shù)列按有序化(遞增或遞減)排列，查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。 折半查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。但是，折半查找的先決條件是查找表中的數(shù)據(jù)元素必須有序第四問 ：二次探查法的探查序列是： hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2 即探查序列為d=h(key)，d+12，d+22，…，等?！≡摲椒ǖ娜毕菔遣灰滋讲榈秸麄€(gè)散列空間。
數(shù)據(jù)結(jié)構(gòu)?？嫉乃惴?/h3>
1.A
存取任一指定序號(hào)，用順序表最方便，在最后進(jìn)行插入和刪除運(yùn)算，順序表也可以方便的實(shí)現(xiàn)。
2.C
第一個(gè)是5，第二個(gè)是4，都可以，表示5、4是最后進(jìn)棧的，之后再要出棧1，不可能
3.D
4.C
5.A
生成樹
6.D
二分查找的前提是該查找必須是順序存儲(chǔ)的有序表
7.C
8.不清楚
9.B
abc,cba正好倒過來。
10.B
掃描二維碼推送至手機(jī)訪問。
版權(quán)聲明：本文由尚恩教育網(wǎng)發(fā)布，如需轉(zhuǎn)載請(qǐng)注明出處。
