一 填空題
1.資料的邏輯結構是從 邏輯 關系上描述資料，它與資料的 具體存儲 無關，是獨立于計算機的。
2.在一個帶頭結點的單循環連結清單中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head= p->next->next .尾結點表示為 p->next
3.棧頂的位置是随着 入棧 和 出棧 操作而變化的。
4.在串S=“structure”中，以t為首字元的子串有 12 個
第一個t為首的子串有t、tr、tru.、truck、truct、tructu、tructur、tructure等8個
第二個t為首的有t、tu、tur、ture4個一共是12個
不需要去掉
5.假設一個9階的上三角矩陣A按列優先順序壓縮存儲在一堆數組B中、其中B[0]存儲矩陣中第一個元素a[1][1],則B[31]中存放的元素是 a[4][8]
九階：9*9上三角：非零元素在右上半部分。按列：1+2+3+4+5+6+7=28個,第一列存儲1個第二列存儲2個，以此類推。第8列需要存儲四個（31+1-28=4）。B[0~31]共32個。故答案是a(4,8)。第四行第8列。
6.已知一棵完全二叉樹中共有768結點，則該樹中共有 384 個葉子結點和 1 個隻具有左孩子的結點和 0 個隻具有右孩子的結點。
設二叉樹度為0結點個數為n0，度為1的結點個數為n1，度為2結點個數為n2
于是n0 + n1 + n2 = 768
按照二叉樹的性質：n0 = n2 + 1，代入得
2n2 + n1 + 1 = 768，顯然n1為奇數
考慮到完全二叉樹中，最多隻有1個度為1的結點 ，是以n1 =1
是以n2 = 383
n0 = 384
7.AOV網是一種 有向無環 的圖。
8.在單連結清單上難以實作的排序方法有 快速排序 和 堆排序 。
9.在有序表（12,24,36,48,60,72,84）中二分查找關鍵字72時所需進行的關鍵字比較次數為：
2 。
第一次二分查找取序列中間值48，比較72>48
第二次查找取48右側的子序列60,72,84的中值72，比較72==72，傳回。查找完成
10.對于一棵具有n個結點的二叉樹，用二叉連結清單存儲時，其指針總數為 2n 個, n+1個指針是空閑的，有 n-1 指向孩子結點。
n個節點則有2n個鍊域，除了根節點沒有被lchild和rchild指向，其餘的節點必然會被指到。是以指針總數為2n個，指向了孩子節點的指針則為n-1個，因為n個節點的二叉樹，除根結點以外都有自己的父親結點或者說其都是一個孩子節點，是以有n-1個指針指向他們。那剩下的就是空閑指針了，共有2n-(n-1)=n+1個。
11.若對一棵完全二叉樹從0開始進行結點的編号，并按此編号把它順序存儲到一堆數組A中，即編号為0的結點存儲到A[0]中。其餘類推。則A[i]元素的左孩子元素為 A[2i+1] ，右孩子元素為 A[2i+2] ，雙親元素為 A[（i-1）/2] 。
畫圖找規律。
12.在一個具有n個頂點的無向完全圖中，包含有 n(n-1)/2 條邊，在一個具有n個頂點的有向完全圖中包含有 n(n-1) 條邊。
定義：具有n個頂點和n(n-1)/2條邊的無向圖稱為完全無向圖，具有n個頂點，n（n-1）條弧的有向圖稱為完全有向圖。完全無向圖和完全有向圖都稱為完全圖。顯然，完全圖具有最多的邊數，即任意一對頂點間均有邊或弧相連。
記不住就畫圖找規律！
13.在所有内部排序算法中，速度最快的是 快速排序 。
二、單選題
1.算法指的是（ D 解決問題的有限運算序列 ）。
2.線性表采用鍊式存儲時，結點的存儲位址（ B 連續與否均可 ）
3.将長度為n的單連結清單接在長度為m的單連結清單之後的算法的時間複雜度為（ C O（m） ）
4.由兩個棧共享一個向量空間的好處是：（ B 節省存儲空間，降低上溢發生的機率 ）
雙向棧——兩個棧共享同一存儲空間
當程式中同時使用兩個棧時，可以将兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。如下圖所示：當一個棧的元素較多，超過向量空間的一半時，隻要另一個棧的元素不多，那麼前者就可以占用後者的部分存儲空間。隻有當整個向量空間被兩個棧占滿（即兩個棧頂相遇）時，才會發生上溢，是以兩個棧共享一個長度為m的向量空間
5.設有如下遺産繼承規則：丈夫和妻子可以互相繼承遺産；子女可以繼承父親或母親的遺産；子女間不能互相繼承。表示該遺産繼承關系最适合的資料結構應該是（ B 圖 ）
6.在資料結構中，從邏輯上可以把資料結構分成（ C 線性結構和非線性結構 ）
7.以下資料結構中不屬于線性資料結構的是（ C 二叉樹）
8.算法的時間複雜度是指（ C 算法執行過程中所需要的基本運算次數 ）
9.哈夫曼樹是（ C 樹的路徑長度最短的二叉樹?可能有問題，我最後這套試卷不是滿分 ）
10.由帶權9,1,3,5,6的五個葉子結點生成的哈夫曼樹的帶權路徑長度為（ C 52 ）
算法步驟如下：
①有n棵權值分别為w1,w2,
,wn的二叉樹，将其組合成一個森林集合F={T1,T2,
Tn}，其中每棵二叉樹Ti中都隻有一個權值為wi的根節點，其左右孩子為空。
②在森林F中選出兩棵根節點的權值最小的樹，将這兩棵樹合并為一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，并将所選的兩棵樹的根分别作為新樹的左、右孩子，不用區分先後，将左、右孩子的權值之和作為新樹根的權值。
③對新的森林集合F重複步驟②，直到森林F中隻剩下一棵樹為止，最後生成的二叉樹為哈夫曼樹。
11.深度為k的完全二叉樹所含葉子結點的個數最多為（ C 2^(K-1) ）
找規律！
12.具有10個葉結點的二叉樹中有（ B 9 ）個度為2的結點。
公式：對任何一棵二叉樹，如果葉子結點數為n0，度為2的結點數為n2，則一定有n0=n2+1。是以n2=n0-1=9。
三、簡答題
1.對于給定的五個實數w={8,5,13,2,6},試構造哈夫曼樹，并求出該樹的最小帶權路徑長度。
構造的哈夫曼樹是：
(34)
/
(13) (21)
/ \ /
6 (7) 8 13
/
2 5
WPL = 62+23 + 53 + 82+ 13*2 = 75
2.已知一個無向圖的頂點集為{a,b,c,d,e}，其鄰接矩陣如下所示
（1）畫出該圖的圖形；
（2）根據鄰接矩陣從頂點a出發進行深度優先周遊和廣度優先周遊，寫出相應的周遊序列。
鄰接矩陣：
定義
鄰接矩陣（Adjacency Matrix）是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖，其中V={v1,v2,…,vn} [1] 。G的鄰接矩陣是一個具有下列性質的n階方陣：
①對無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅讨論無向簡單圖），副對角線不一定為0，有向圖則不一定如此。
②在無向圖中，任一頂點i的度為第i列（或第i行）所有非零元素的個數，在有向圖中頂點i的出度為第i行所有非零元素的個數，而入度為第i列所有非零元素的個數。
③用鄰接矩陣法表示圖共需要n^2個空間，由于無向圖的鄰接矩陣一定具有對稱關系，是以扣除對角線為零外，僅需要存儲上三角形或下三角形的資料即可，是以僅需要n（n-1）/2個空間。
在圖的鄰接矩陣表示法中：
① 用鄰接矩陣表示頂點間的相鄰關系
② 用一個順序表來存儲頂點資訊
圖的矩陣
設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣：
【例】
下圖中無向圖G 5 和有向圖G 6 的鄰接矩陣分别為A1 和A 2 。
網絡矩陣
若G是網絡，則鄰接矩陣可定義為：
其中：
w ij 表示邊上的權值;
∞表示一個計算機允許的、大于所有邊上權值的數。
【例】下面帶權圖的兩種鄰接矩陣分别為A 3 和A 4 。
二叉樹深度優先周遊和廣度優先周遊
對于一顆二叉樹，深度優先搜尋(Depth First Search)是沿着樹的深度周遊樹的節點，盡可能深的搜尋樹的分支。以上面二叉樹為例，深度優先搜尋的順序
為：ABDECFG。怎麼實作這個順序呢 ？深度優先搜尋二叉樹是先通路根結點，然後周遊左子樹接着是周遊右子樹，是以我們可以利用堆棧的先進後出的特點，
現将右子樹壓棧，再将左子樹壓棧，這樣左子樹就位于棧頂，可以保證結點的左子樹先與右子樹被周遊。
廣度優先搜尋(Breadth First Search),又叫寬度優先搜尋或橫向優先搜尋，是從根結點開始沿着樹的寬度搜尋周遊，上面二叉樹的周遊順序為：ABCDEFG.
可以利用隊列實作廣度優先搜尋。
3.已知一個圖的頂點集V和邊集E分别為：
V={1,2,3,4,5,6,7}，E={（1,2）3，（1,3）5，（1,4）8，（2,5）10，（2,3）6，（3,4）15，（3,5）12，（3，6）9，（4,6）4，（4,7）20,（5,6）18，（6,7）25}；
（1）畫出其鄰接表；
（2）用布魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
自己的感想：如果是v1、v2、v3···用下标，不是直接用值。
②鄰接表
鄰接表存儲的基本思想：對于圖的每個頂點vi，将所有鄰接于vi的頂點鍊成一個單連結清單，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點資訊的一維數組構成了頂點表。
鄰接表有兩種結點結構：頂點表結點和邊表結點.。
頂點表 邊表
其中：vertex：資料域，存放頂點資訊。 firstedge：指針域，指向邊表中第一個結點。 adjvex：鄰接點域，邊的終點在頂點表中的下标。 next：指針域，指向邊表中的下一個結點。
adjacency
英 [ə’dʒeɪsnsɪ] 美 [ə’dʒeɪsənsɪ]
n.鄰接
vertex
英 [ˈvɜ:teks] 美 [ˈvɜ:rteks]
n.
頂點;最高點;<數>（三角形、圓錐體等與底相對的）頂;（三角形、多邊形等的）角的頂點
若是有向圖，鄰接表的結構是類似的，如圖7-4-7，以頂點作為弧尾來存儲邊表容易得到每個頂點的出度，而以頂點為弧頭的表容易得到頂點的入度，即逆鄰接表。
對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的資料域，存儲權值資訊即可，如圖7-4-8所示。
克魯斯卡爾算法
克魯斯卡爾算法的基本思想是以邊為主導地位，始終選擇目前可用（所選的邊不能構成回路）的最小權植邊。是以Kruskal算法的第一步是給所有的邊按照從小到大的順序排序。這一步可以直接使用庫函數qsort或者sort。接下來從小到大依次考察每一條邊（u，v）。
具體實作過程如下：
<1> 設一個有n個頂點的連通網絡為G（V,E），最初先構造一個隻有n個頂點，沒有邊的非連通圖T={V,空}，圖中每個頂點自成一格連通分量。
<2> 在Ｅ中選擇一條具有最小權植的邊時，若該邊的兩個頂點落在不同的連通分量上，則将此邊加入到Ｔ中；否則，即這條邊的兩個頂點落到同一連通分量上，則将此邊舍去（此後永不選用這條邊），重新選擇一條權植最小的邊。
<3> 如此重複下去，直到所有頂點在同一連通分量上為止。
四、算法填空題
1.void ABC(BTNode*BT)
{
if(BT){
ABC(BT->left);
ABC(BT->right);
cout<data<<’’;
}
}
該算法的功能是：
後序周遊（LRD）是二叉樹周遊的一種，也叫做後根周遊、後序周遊，可記做左右根。後序周遊有遞歸算法和非遞歸算法兩種。在二叉樹中，先左後右再根，即首先周遊左子樹，然後周遊右子樹，最後通路根結點。
後序周遊首先周遊左子樹，然後周遊右子樹，最後通路根結點，在周遊左、右子樹時，仍然先周遊左子樹，然後周遊右子樹，最後周遊根結點。即：
若二叉樹為空則結束傳回，
否則：
（1）後序周遊左子樹（2）後序周遊右子樹（3）通路根結點
如右圖所示二叉樹
後序周遊結果：DEBFCA
已知前序周遊和中序周遊，就能确定後序周遊。 [1]
1、先序周遊（根左右）
先序周遊先從二叉樹的根開始，然後到左子樹，再到右子樹,，如圖
先序周遊序列是ABDCEF，重點是記住第一個字母“A”是根，出發點是根“A”
2、中序周遊（左根右）
中序周遊先從左子樹開始，然後到根，再到右子樹，如圖3
即中序周遊序列是DBAECF，重點是記住中序周遊的根位置，是在序列的第一個字母和最 後一個字母之間，出發點是左子樹的最下邊的左邊的開始，（為什麼到A之後直接跳過C呢？因為C也是E和F的根，是以按照中序周遊規律，先到E再到C再到F）
3、後序周遊（左右根）
後序周遊先從左子樹開始，然後到右子樹，再到根，如圖
即後序周遊序列式DBECFCA,重點是知道了根是最後面一個字母“A”， 出發點是左子樹的最下邊左邊。
四、道了先序周遊和中序周遊，或者是後序周遊和中序周遊，判斷出後序周遊，或者是先序周遊的方法
比如知道先序周遊是ABDCEF，中序周遊是DBAECF，那麼可以從先序周遊知道這個二叉樹的根是A，（如果是選擇題，可以快速判斷出後序周遊的序列最後面一個字母肯定是A，然後選擇最後面有A的選項）
從中序周遊看出A把DB和ECF隔開，即DB \A \ECF，是以可以知道DB屬于左子樹，ECF屬于右子樹
如果是填空題就要寫出該二叉樹的圖，先寫出左子樹，從中序周遊知道DB是右子樹，把DB看成一個整體，則從先序周遊判斷可以确定B是D的根，這樣就确定出左子樹的圖是
把ECF右子樹看成一個整體，則從先序周遊可以知道C是E和F的根，确定出右子樹是
然後把兩個子樹連在根“A”的下面，再根據後序周遊規律讀出序列就可以了
2、二叉樹搜尋樹的查找——遞歸算法
bool Find(BTreeNode*BST,ElemType& item)
{ if (BSTNULL)
return false;//查找失敗
else {
if (itemBST->data){
item=BST->data;//查找成功
return ;}
else if (itemdata)
return Find( ,item);
else return Find( ,item);
}
五、程式設計題
1、編寫一個函數實作單連結清單的倒置。
struct Node
{
int data;
struct Node*next;
};
非遞歸（疊代）方式
node* reverseList(node* H)
{
if (H == NULL || H->next == NULL) //連結清單為空或者僅1個數直接傳回
return H;
node* p = H, *newH = NULL;
while (p != NULL) //一直疊代到鍊尾
{
node* tmp = p->next; //暫存p下一個位址，防止變化指針指向後找不到後續的數
p->next = newH; //p->next指向前一個空間
newH = p; //新連結清單的頭移動到p，擴長一步連結清單
p = tmp; //p指向原始連結清單p指向的下一個空間
}
return newH;
}
老師的代碼：
//倒置
typedef struct Node
{
int data;//資料域
struct Node *next;//指針域
} TNode;
TNode*reverse(TNode*head)
{
TNode *p,*q;
p=q=head;
head=NULL;
while(p!=NULL)
{
q=p->next;
p->next=head;
head=p;
p=q;
}
return head;
}
2、統計出單連結清單HL中結點的值等于給定X的結點數。（有多少個結點的值是x）
最後自己的感想：本次考試滿分100分，我好像隻考了93分。這是期末的原題卷子，是我在考前整理的，考前一題一題的過，我比較笨，而且很疑惑這樣做到底是不是無用功，即浪費時間還效率低。我一直覺得自己很笨記憶力很差，但是不這樣做筆記又好像我還是什麼都不會。現在過了幾個月了，發現這些知識我又忘記了。想了想還是重新整理下吧，萬一找不到工作就隻能考研了，這些知識也許又要學一遍。
我現在處于一個很迷茫的狀态，很多知識很多知識需要學習，好多好多，我有時候壓力很大，好不容易學的差不多了，結果過幾天放着沒看就又忘記了，好想哭。代碼敲了就忘，也是沒誰了，加油吧！！！要努力呀！希望2019可以減肥成功~，另外可以把web安全學習好，争取學會挖洞，然後這學期争取考個好成績！！加油！