數據結構期末刷題去哪裡

1. 有什麼適合大一計算機專業學生免費的刷題網站

既然大一的同學選擇計算機專業，當然少不了刷題啦！但是有很多刷題網站是免費的，同學們想知道嗎？下面由我來講講吧。

1.力扣

這個網站收錄了很多知名互聯網公司出的演算法題目，相信大一同學很熟悉了，很多同學都在這里刷題，增強對計算機基礎知識掌握。它支持多種編程語言，如：Java、Ptthon、Ruby等。最常做的是演算法題，目前有一千多道的題目。有專門的圖文和視頻講解，方便同學們茶樓補缺。也可以在個人界面查看進展，看自己的學習情況。如果出來工作筆試中，面試官會從這里抽題。刷題過程中全部會了，那麼工作沒有什麼大問題。

以上我列舉了三個計算機免費刷題的網站，同學們看到我寫的推薦後，來收藏夾吃灰~希望同學們有時間使用這三個網站學習計算機相關知識，提高計算機專業能力，祝你們學有所成！

2. 如何學好數據結構，去哪裡刷題

https://leetcode.com/
很多企業的筆試和面試的數據結構&演算法題是從這裡面找的。

3. 萌新想問一下大佬關於數據結構刷題的書有什麼好的可以推薦嗎像高數同濟大學出版社那種經典的有嗎

c語言的刷題用清華大學出版社嚴蔚敏版（我們教材就是這個，講的不錯）配套的題集書就可以了，應該有單賣的《數據結構題集（C語言版）》

4. 如何學習數據結構

• 學好數據結構首先學好C語言指針，數據機構內在串聯全靠指針作用，指針主要難在本身是帶地址的變數，再加上指針的指針串聯導致很多人誤解，先要學會理解，要對計算機的內存結構有個大概了解，對一些常見的進制之間的轉化以及位元組對齊等有行程基本的認知。

• 理解概念，建立抽象模型，比如簡單的隊列，先進先出模式，在設計數據模型的時候，就需要有一個對頭和隊尾的概念，數據需要從隊尾插入隊頭出來，基本上三個屬性就出來了，一個對頭指針，一個隊尾指針，一個結構體數值，常見的方法有刪除清空隊列，有插入隊列操作，出隊操作，創建初始隊列操作等等，這樣子抽象數據模型，形成自己的思維理解，然後再進行代碼設計。

• 需要變通實踐，代碼調試變通，數據結構的組合無窮變著寫代碼。演算法的奧妙就是在於變換，放在數據結構也是這個樣子，掌握基本的數據機構演算法，在學好數據結構的前提下可以學習下一本經典的演算法書《演算法導論》這個是演算法的經典書籍。

• 學習數據機構不要想著有什麼技巧或者方法，把自己調整到最佳的學習狀態，方法自然就有了，不要給自己設置什麼限制，設置底線只會讓自己處在一個圍牆之內，學習新東西就是突破自我的一個過程，不要在開始學習的時候給自己過大的壓力。

5. 怎麼復習數據結構（c++）已學一學期。

要應付期末考試最快捷的方法是找到本校歷年試卷然後讓班上學得比較好的同學給講題，大概能搞懂三套題的話基本題型你也了解了，自己的話，花三天時間，即使看不懂也把整本書的知識點整成一個綱要，主要有線性表，這是一種一對一的數據結構，就是一一對應（順序表、鏈表）；棧、隊列（操作受限的線性表，說白了還是線性表）串和廣義表我當初是不考的，這部分要考也考得少；樹與二叉樹，這是一種一對多的數據結構（會計算葉子節點什麼的，了解這種結構的特點，重點有樹的遍歷，樹與森林的轉換，哈夫曼樹，二叉排序樹）；然後是圖，這是一種多對多的數據結構（重點有圖的存儲表示，圖的遍歷和最短路徑啊關鍵路徑和拓撲排序，按這些內容出的題都涉及演算法，最好是自己能讀懂演算法然後按照演算法操作，如果不行就學會做題，明白一種題怎麼做）；接下來是查找，重點是二分查找，哈希表，特別是哈希，仔細看的話你會發現這章挺有意思的；最後就是排序，重點掌握各種排序方法的實現，比較好的方法是從網上找到一些演算法執行的動態演示圖，效果相當好。說實話，當年學DS也是大白，最後漸漸明白就是通過狂做練習。對於演算法題，這不是速成的，無法提供好的解決方案，見諒。

6. 哪裡有數據結構期末考題

（三）簡答題
1．簡述順序存儲結構和鏈式存儲結構的特點
答：順序存儲結構的優點無需為表示元素間的邏輯關系而增加額外的指針空間；可以隨機存取表中的任一元素。缺點是必須事先進行空間分配，表的容量難以擴充；插入和刪除操作時需移動大量結點，效率較低。
鏈式存儲結構的優點是結點的存儲採用動態存儲，表的容量很容易擴充；插入和刪除操作方便，不必移動結點，只要修改結點中的指針即可。缺點是每個結點中需要有指針空間，比順序存儲結構的存儲密度小；只能進行順序查找結點。
2．鏈表中為何要引入頭結點？
答：鏈表進行插入和刪除操作時要判斷是否在鏈表的首端操作，若在第一結點前插入新結點和刪除第一個結點則會引起首指針head值的改變；否則head的值不會改變。在鏈表前加一個頭結點（只用指針域指向鏈表的首結點）就避免了兩種情況的判斷，使程序設計簡單了，程序的結構更清楚。
2． 簡述由二叉樹的前序、中序和後序遍歷序列確定二叉樹
答：在三種遍歷序列中，前序序列和中序序列、中序序列和後序序列能唯一確定一棵二叉樹，因為前序序列或後序序列能確定二叉樹的根結點而中序序列能確定根的左、右子樹。前序序列和後序序列不能唯一確定一棵二叉樹，但注意樹的先根序列和後根序列能唯一的確定該樹，因為樹的後根序列就是二叉樹的中序序列。
4．快速排序最壞情況的改進
答：當待排序的序列為有序序列時快速排序的效率很低，蛻變為冒泡排序了，為了避免這種情況，選序列的首元素為樞軸元素（或稱基準元素）改為選序列的首元素、中間元素和末元素三個元素中中間大的元素為基準元素（簡單的就用中間元素為基準），這可大大改善快速排序的性能。例如：
8，0，4，9，6，3，5，2，7，1
以中間大元素6為基準，基準元素與最後元素交換後為：
8，0，4，9，1，3，5，2，7，6
↑ ↑
i j
將i,j指的內容比較，若i的內容比基準小，i推進，否則i停下，開始進行j的比較；若j的內容比基準大，j推進,，否則j停下，將i的內容與j的內容交換，重復上述過程，直至j<I< SPAN>止，將基準與i的內容交換，一次分段完成。,如下所示：
8，0，4，9，1，3，5，2，7，6
2，0，4，9，1，3，5，8，7，6
2，0，4，5，1，3，9，8，7，6
2，0，4，5，1，3，6，8，7，9
5．簡述動態規劃法的基本思想
答：為了節約重復求相同子問題的時間，引入一個表（數組），不管它們是否對最終解有用，把新的子問題的解答存於該表中，待以後遇到同樣子問題時，就不再重復求該子問題，而直接從表中取出該子問題的解答，這就是動態規劃法所採用的基本思想。
（四）選擇題
1．循環隊列用數組A[0…m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數是 。
A．(rear-front+m)% m B．read-front+1
C．read-front-1 D．read-front
n 參考答案 A
2．遞歸演算法的執行過程一般來說，可分成 (1) 和 (2) 兩個階段。
(1)A．試探 B．遞推 C．枚舉 D．分析
(2)A．回溯 B．回歸 C．返回 D．合成
n 參考答案 (1) B (2) B
3．設哈希表長m=11，哈希函數H（key）=key%11。表中已有4個結點：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其餘地址為空，如果二次探測再散列處理沖突，關鍵字為49的結點地址是 。
A．8 B．3 C．5 D．9
n 參考答案 D
4．m階B-樹中所有非終端（除根之外）節點中的關鍵字個數必須大於或等於 。
A． －1 B． +1 C． －1 D．m
n 參考答案 C
5．一組記錄的關鍵碼為（46，79，56，38，40，84），則採用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為 。
A．38，40，46，56，79，84 B．40，38，46，79，56，84
C．40，38，46，56，79，84 D．40，38，46，84，56，79
n 參考答案 C
6．若一個問題的求解既可以用遞歸演算法，也可以用遞推演算法，則往往用 (1) 演算法，因為 (2) 。
（1）A．先遞歸後遞推 B．先遞推後遞歸 C．遞歸 D．遞推
（2）A．遞推的效率比遞歸高 B．遞歸宜於問題分解
C．遞歸的效率比遞推高 D．遞推宜於問題分解
n 參考答案 （1）D （2）A
7．將一棵有100節點的完全二叉樹從上到下、從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為 。
A． 99 B．98 C．50 D．48
n 參考答案 B
8．二叉樹在線索化後，仍不能有效求解的問題是 。
A．前序線索二叉樹中求前序後繼 B．中序線索二叉樹中求中序後繼
C．中序線索二叉樹中求中序前趨 D．後序線索二叉樹中求後序後繼
n 參考答案 D
9．判斷線索二叉樹中某結點P有左孩子的條件是 （1） 。若由森林轉化得到的二叉樹是非空的二叉樹，則二叉樹形狀是 （2） 。
（1）A．P！=null B．P->lchild！=null C．P->ltag=0 D．P->ltag=1
（2）A．根結點無右子樹的二叉樹 B．根結點無左子樹的二叉樹
C．根結點可能有左子樹和右子樹 D．各結點只有一個孩子的二叉樹
n 參考答案 （1）C （2）C
10．在一個單鏈表head中，若要在指針p所指結點後插入一個q指針所指結點，則執行_____。
A． p->next=q->next; q->next=p;
B． q->next=p->next; p=q;
C． p->next=q->next; p->next=q;
D． q->next=p->next; p->next=q;
n 參考答案 D
11．設二維數組a[0…m-1][0…n-1]按列優先順序存儲在首地址為loc(a[0][0])的存儲區域中，每個元素佔d個單元，則a[i][j]的地址為________。
A． loc(a[0][0]) +(j×n+i) ×d B． loc(a[0][0]) +(j×m+i) ×d
C．loc(a[0][0]) +((j-1)×n+i-1) ×d D． loc(a[0][0]) +((j-1)×m+i-1) ×d
n 參考答案 B
12．如果一個棧的進棧序列是1,2,3,4且規定每個元素的進棧和退棧各一次,那麼不可能得到的退棧序列_____。
A 4,3,2,1 B 4,2,1,3 C 1,3,2,4 D 3,4,2,1
n 參考答案 B
13．對n個元素進行快速排序時，最壞情況下的時間復雜度為 。
A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2）
n 參考答案 D
14．任何一個基於「比較」的內部排序的演算法，若對6個元素進行排序，則在最壞情況下所需的比較次數至少為 。
A．10 B．11 C ．21 D．36
n 參考答案 A
四、模擬試題
1．二叉樹的前序、中序和後序遍歷法最適合採用 （1） 來實現。
查找樹中，由根結點到所有其它結點的路徑長度的總和稱為 （2） ，而使上述路徑長度總和達到最小的樹稱為 （3） 。它一定是 （4） 。
在關於樹的幾個敘述中，只有 （5） 是正確的。
（1）A．遞歸程序 B．迭代程序 C．隊列操作 D．棧操作
（2）A．路徑和 B．內部路徑長度 C．總深度 D．深度和
（3）A．B-樹 B．B+樹 C．豐滿樹 D．穿線樹
（4）A．B-樹 B．平衡樹 C．非平衡樹 D．穿線樹
（5）A．用指針方式存儲有n個結點的二叉樹，至少要有n+1個指針
B．m階B-樹中，每個非葉子結點的後件個數≥
C．m階B-樹中，具有k個後件的結點，必含有k-1個鍵值
D．平衡樹一定是豐滿樹
n 參考答案（1）A （2）B （3）C （4）B （5）C
2．一棵查找二叉樹，其結點A、B、C、D、E、F依次存放在一個起始地址為n（假定地址以位元組為單位順序編號）的連續區域中，每個結點佔4個位元組：前二個位元組存放結點值，後二個位元組依次放左指針、右指針。若該查找二叉樹的根結點為E，則它的一種可能的前序遍歷為 （1） ，相應的層次遍歷為 （2） 。在以上兩種遍歷情況下，結點C的左指針Lc的存放地址為 （3） ，Lc的內容為 （4） 。結點A的右指針Ra的內容為 （5） 。
（1）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（2）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（3）A．n+9 B．n+10 C．n+12 D．n+13
（4）A．n+4 B．n+8 C．n+12 D．n +16
（5）A．n+4 B．n+8 C．n+12 D．n +16
n 參考答案 （1）D （2）A （3）B （4）A （5）B
3．對於給定的一組關鍵字（12，2，16，30，8，28，4，10，20，6，18），按照下列演算法進行遞增排序，寫出每種演算法第一趟排序後得到的結果：希爾排序（增量為5）得到 （1） ，快速排序（選第一個記錄為基準元素）得到 （2） ，基數（基數為10）排序得到 （3） ，二路歸並排序得到 （4） ，堆排序得到 （5） 。
（1）A．2,4,6,8,10,12,16,18,20,28,30 B．6,2,10,4,8,12,28,30,20,16,18
C．12,2,10,20,6,18,4,16,30,8,28 D．30,10,20,12,2,4,16,6,8,28,18
（2）A．10,6,18,8,4,2,12,20,16,30,28 B．6,2,10,4,8,12,28,30,20,16,18
C．2,4,6,8,10,12,16,18,20,28,30 D．6,10,8,28,20,18,2,4,12,30,16
（3）A．10,6,18,8,4,2,12,20,16,30,28 B．1,12,10,20,6,18,4,16,30,8,28
C．2,4,6,8,10,12,16,18,20,28,30 D．30,10,20,12,2,4,16,6,8,28,18
（4）A．2,12,16,8,28,30,4,6,10,18,20 B．2,12,16,30,8,28,4,10,6,20,18
C．12,2,16,8,28,30,4,6,10,28,18 D．12,2,10,20,6,18,4,16,30,8,28
（5）A．30,28,20,12,18,16,4,10,2,6,8 B．20,30,28,12,18,4,16,10,2,8,6
C．2,6,4,10,8,28,16,30,20,12,18 D．2,4,10,6,12,28,16,20,8,30,18
n 參考答案 （1）C （2）B （3）D （4）B （5）C
4．在所有排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是 （1） 。
從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 （2） 。設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用 （3） 排序法。
（1）A．希爾排序 B．起泡排序 C．插入排序 D．選擇排序
（2）A．希爾排序 B．起泡排序 C．插入排序 D．選擇排序
（3）A．起泡排序 B．快速排序 C．堆排序 D．基數排序
n 參考答案 （1）D （2）C （3）C
5．用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進行排序時,元素序列的變化情況如下：
①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84
③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84
則所採用的排序方法是 （1） 。下列（2）中不穩定的排序是 （2） 。
外排序是指 （3） 。
（1）A．選擇排序 B．希爾排序 C．歸並排序 D．快速排序
（2）A．直接插入排序 B．冒泡排序 C．Shell排序 D．歸並排序
（3）A．用機器指令直接對硬碟中需排序數據排序
B． 把需排序數據，用其它大容量機器排序
C． 把外存中需排序數據一次性調入內存，排好序後再存儲外存
D．對外存中大於內存允許空間的待排序的數據，通過多次內外間的交換實現排序。
n 參考答案 (1) D (2) C （3）D
6．在內部排序中，通常要對被排序數據進行多次掃描。各種排序方法有不同的排序實施過程和時間復雜性。對給定的整數數列（541,132,984,746,518,181,946,314,205,827）進行從小到大的排序時,採用冒泡排序和簡單選擇排序時,若先選出大元素,則第一次掃描結果分別是 （1） 採用快速排序（以中間元素518為基準）的第一次掃描結果是 （2） 。
設被排序的序列有n個元素，冒泡排序和簡單選擇排序的時間復雜度是 （3） ；快速排序的時間復雜度是 （4） 。
（1）
A．(181,132,314,205,541,518,946,827,746,984）和（541,132,827,746,518,181,946,314,205,984）
B．（132,541,746,518,181,946,314,205,827,984）和（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）和（132,541,746,518,181,946,314,205,827,984）
D．(541,132,984,746,827,181,946,314,205,518）和（132,541,746,518,181,946,314,205,827,984）
（2）A．（181,132,314,205,541,518,946,827,746,984）
B．（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）
D．(541,132,984,746,827,181,946,314,205,518）
（3）A．O(nlog2n) B．O(n) C．log2n D．O(n2)
（4）A．O(nlog2n) B．O(n2log2n) C．O(log2n) D．O(n2)
n 參考答案 （1）B （2）C （3）D （4）A
7．結定結點的關鍵字序列（F、B、J、G、E、A、I、D、C、H），對它按字母的字典順序進行排列，採用不同方法，其最終結果相同。但中間結果是不同的。
Shell排序的第一趟掃描（步長為5）結果應為 （1） 。
冒泡排序（大數下沉）的第一趟冒泡的效果是 （2） 。
快速排序的第一次掃描結果是 （3）
二路歸並排序的第一趟結局是 （4） 。
若以層次序列來建立對應的完全二叉樹後，採用篩選法建堆，其第一趟建的堆是 （5） 。
（1）A．（B、F、G、J、A、D、I、E、H、C）
B．（B、F、G、J、A、E、D、I、C、H）
C．（A、B、D、C、E、F、I、J、G、H）
D．（C、B、D、A、E、F、I、G、J、H）
（2）A．（A、B、D、C、F、E、I、J、H、G）
B．（A、B、D、C、E、F、I、H、G、J）
C．（B、F、G、E、A、I、D、C、H、J）
D．（B、F、G、J、A、E、D、I、C、H）
（3）A．（C、B、D、A、F、E、I、J、G、H）
B．（C、B、D、A、E、F、I、G、J、H）
C．（B、A、D、E、F、G、I、J、H、C）
D．（B、C、D、A、E、F、I、J、G、H）
（4）A．（B、F、G、J、A、E、D、I、C、H）
B．（B、A、D、E、F、G、I、J、H、C）
C．（A、B、D、C、E、F、I、J、G、H）
D．（A、B、D、C、F、E、J、I、H、G）
（5）

n 參考答案 （1）C （2）C （3）B （4）A （5）B
8．二叉樹 （1） 。在完全二叉樹中，若一個結點沒有 （2） ，則它必定是葉結點。每棵樹都能唯一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹里，一個結點N的左子樹是N在原樹里對應結點的 （3） ，而N的右子樹是它在原樹里對應結點的 （4） 。二叉排序樹的平均檢索長度為 （5） 。
（1）A．是特殊的樹 B．不是樹的特殊形式
C．是兩棵樹的總稱 D．是只有二個根結點的樹形結構
（2）A．左子樹 B．右子樹 C．左子樹或沒有右子樹 D．兄弟
（3）～(4)A．最左子樹 B．最右子樹 C．最鄰近的右兄弟 D．最鄰近的左兄弟
（5）A．O(n2) B．O(n) C．O(log2n) D．O(nlog2n)
n 參考答案 （1）B （2）A （3）A （4）C （5）C
9．哈希存儲的基本思想是根據 （1） 來決定 （2） ，沖突（碰撞）指的是 （3） ， __(4)___越大，發生沖突的可能性也越大。處理沖突的兩種主要方法是 （5） 。
（1）～（2）A．存儲地址 B．元素的序號 C．元素個數 D．關鍵碼值
（3） A．兩個元素具有相同序號 B．兩個元素的關鍵碼值不同，而非碼屬性相同
C．不同關鍵碼值對應到相同的存儲地址 D．數據元素過多
（4） A．非碼屬性 B．平均檢索長度 C．負載因子 D．哈希表空間
（5） A．線性探查法和雙散列函數法 B．建溢出區法和不建溢出區法
C．除余法和折疊法 D．拉鏈法和開放地址法
n 參考答案 （1）D （2）A （3）C （4）C （5）D
10． 設二維數組F的行下標為1至5，列下標為0至8，F的每個數據元素均佔4個位元組。在按行存儲的情況下，已知數據元素F[2，2]的第一個位元組的地址是1044，則F[3，4]和F[4，3]的第一個位元組的地址分別為 （1） 和 （2） ，而數組的第一個數據元素的第一個位元組和數組最後一個元素的最後一個位元組的地址分別為 （3） 和 （4） 。
對一般的二維數組G而言，當 （5） 時，其按行存儲的G[I，J]的地址與按列存儲的G[J，I]的地址相同。
（1）A．1088 B． 1084 C．1092 D．1120
（2）A．1092 B． 1088 C．1120 D．1124
（3）A．1004 B． 1044 C．1000 D．984
（4）A．1183 B． 1179 C．1164 D．1187
（5）A．G的列數與行數相同
B．G的列的上界與G的行的上界相同
C．G的列的上界與G的行的下界相同
D．G的列的上下界與G的行的上下界相同
n 參考答案 （1）A （2）C （3）C （4）B （5）D
11．某順序存儲的表格，其中有90,000個元素，已按關鍵字遞增有序排列，現假定對各個元素進行查找的概率是相同的，並且各個元素的關鍵字皆不相同。
用順序查找法查找時，平均比較次數約為 (1) ，最大比較次數為 (2) 。
現把90,000個元素按排列順序劃分成若干組，使每組有g個元素（最後一組可能不足g個）。查找時，先從第一組開始，通過比較各組的最後一個元素的關鍵字，找到欲查找的元素所在的組，然後再用順序查找法找到欲查找的元素。在這種查找法中，使總的平均比較次數最小的g是 (3) ，此時的平均比較次數是 (4) 。當g的值大於等於90,000時，此方法的查找速度接近於 (5) 。
(1)～(2) A. 25,000 B. 30,000 C. 45,000 D. 90,000
(3)～(4) A. 100 B. 200 C. 300 D. 400
(5) A. 快速分類法 B. 斐波那契查找法 C. 二分法 D. 順序查找法
n 參考答案 （1）C （2）D （3）C （4）C （5）D
12．已知無向圖的鄰接表如圖2-35所示：
此鄰接表對應的無向圖為 (1) 。此圖從F開始的深度優先遍歷為 （2） 。從F開始的廣度優先遍歷為 （3） 。從F開始的深度優先生成樹為 （4） 。從F開始的廣度優先生成樹為 （5） 。
（1）
（2）A. F G I L J M K H B. F G I L J K H M
C. F G I L J K M H D. F G H M I L J K
（3）A. F G I L J K M H B. F G H M I L J K
C. F G H I L J K M D. F G H M K I L J
（4）

（5）
n 參考答案 （1）C （2）B （3）B （4）A （5）B
13．圖2-36是帶權的有向圖G的鄰接表。以結點V1出發深度遍歷圖G所得的結點序列為 （1） ；廣度遍歷圖G所得的結點序列為 （2） ；G的一種拓撲序列是 （3） ；從結點V1到V8結點的最短路徑是 （4） ；從結點V1到V8結點的關鍵路徑是 （5） 。

（1）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7
C. V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6
（2）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
（3）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
(4)～(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8)
C.( V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)
n 參考答案 （1）D （2）C （3）B （4）D （5）B

7. 誰有數據結構的期末試題，借我參考下馬上考試了

A：

06－07第一學期期末考試試卷

試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科

一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為(K,R)，其中K是數據元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存儲 D.關系
2.線性表若採用鏈式存儲結構時，要求內存中可用存儲單元的地址____。
A.必須連續的 B.部分地址必須連續的 C.一定是不續的 D.連續不連續都可以
3.一個棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是____。
A.edcba B.decba C.dceab D.abcde
4.一個隊列的入隊序列是1、2、3、4，則隊列輸出序列是____。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.棧和隊列的共同點是____。
A.都是先進後出 B.都是先進先出
C.只允許在端點處插入、刪除元素 D.沒有共同點
6.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行____。
A. s->next = p->next; p->next=s; B. p->next = s->next; s->next = p;
C. q->next = s; s->next = p; D. p->next = s; s->next = q;
7.設串s1=『ABCDEFG』，s2=『PQRST』，函數con (x, y) 返回x與y串的連接串，函數subs (s, i, j) 返回串s的從序號i的字元開始的j個字元組成的子串，函數len (s) 返回串s的長度，則con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的結果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷結點訪問順序是dgbaechf，則其後序遍歷結點訪問順序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6個頂點的無向圖至少應有____條邊才能確保是一個連通圖。
A. 5 B. 6 C. 7 D. 8
11.採用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為–。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
12.排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列(註：初始時為空)的一端的方法，稱為____。
A. 希爾排序 B. 歸並排序 C. 插入排序 D. 選擇排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在樹形結構中，樹根結點沒有 結點，其餘每個結點有且只有 個前驅結點。
2.對n個元素的序列進行起泡排序時，最少的比較次數是 。
3.空串是 ，其長度等於0。
4.一棵有n個結點的滿二叉樹共有 個葉子結點。
5.在散列函數H(key)=key % p中，p應取 。
6.已知模式串t=『abcaabbabc』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.在對線性表的處理中一般使用兩種存儲結構，順序存儲結構和鏈式存儲結構。試敘述在什麼情況下使用順序表比鏈表好？
2.簡述什麼是穩定的排序，什麼是不穩定的排序。
3.下列中綴表達式對應的後綴形式是什麼？
(1) (A + B) * D + E / (F + A * D) + C
(2) A && B|| ! (E > F) {註：按C的優先順序)
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.數據元素不是數據的最小單位( )。
2.已知一棵二叉樹的前序序列和後序序列可以唯一地構造出該二叉樹。( )
3.AOE網是一種帶權的無環連通圖。( )
4.對於同一組待輸入的關鍵碼集合，雖然各關鍵碼的輸入次序不同，但得到的二叉搜索樹都是相同的( )。
5.一棵樹中的葉子數一定等於與其對應的二叉樹的葉子數。( )
6.鄰接表只能用於有向圖的存儲，鄰接矩陣對於有向圖和無向圖的存儲都適用。( )
7.折半插入排序是穩定的。( )
8.在散列法中，使用雙散列函數可保證絕對不產生沖突。( )
9.消除遞歸不一定需要使用棧( )
10.堆排序是交換排序的一種。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1．閱讀後分析下面程序段的功能是什麼? （6分）
SeqStack S1, S2, tmp;
DataType x; //設棧tmp和S2已做過初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( S2, x);
}
2.某子系統在通信聯絡中只可能出現8種字元，其出現的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設計赫夫曼編碼。（7分）
3.設散列表為HT[13], 散列函數為 H (key) = key %13。用線性探測再散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試寫出使用希爾排序(增量為5,2,1)方法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.編寫一個演算法frequency，統計在一個輸入字元串中所含各個不同字元出現的頻度。用適當的測試數據來驗證這個演算法。(10分)
2.在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，並統計樹中具有度為1的結點數目的演算法。要求給出二叉鏈表的類型定義。(8分)

答案：

06－07第一學期
期末考試參考答案與評分標准

試卷代碼：03266A 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科

一、單項選擇題(每小題2分，共24分。)
1. D 2. D 3. C 4. B 5. C 6. C
7. D 8. B 9. D 10. A 11. C 12. D
二、填空題(每空1分，共7分。)
1.父(或前驅)， 1
2. n-1
3. 不包含任何字元的串
4. (n+1)/2
5. 素數
6. 0111223123
三、簡答題(每小題5分，共15分)
1.答：① 順序存儲時，相鄰數據元素的存放地址也相鄰(邏輯與物理統一)；要求內存中可用存儲單元的地址必須是連續的。
優點：存儲密度大，存儲空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式存儲時，相鄰數據元素可隨意存放，但所佔存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針
優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小(<1)，存儲空間利用率低。
順序表適宜於做查找這樣的靜態操作；鏈表宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查找，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鏈表。
2.答：在排序序列中，任何兩個相等的關鍵字Ki=Kj,如果在排序前的序列中Ki領先於Kj，若在排序後的序列中Ki仍領先於Kj，則稱所用的排序方法是穩定的；反之，若可能使排序後的序列中Kj領先於Ki，則稱所用的排序方法是不穩定的。
3.答：各中綴表達式的後綴形式如下：
(1)AB+D*EFAD*+/+C+
(2)AB&&EF>!||
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.T 10.F
五、分析應用題（1、4小題各6分，2、3小題各7分）
1．（6分）
答：程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去。
2．（7分）
答：為方便起見，設各種字元的權值w={5,29,7,8,14,23,3,11}。因為n=8，所以要構造的赫夫曼樹共有m=2n-1=2*8-1=15個結點。生成的赫夫曼樹為下圖所示：

赫夫曼編碼為：概率為0.23的字元編碼為：00
概率為0.11的字元編碼為：010
概率為0.05的字元編碼為：0110
概率為0.03的字元編碼為：0111
概率為0.29的字元編碼為：10
概率為0.14的字元編碼為：110
概率為0.07的字元編碼為：1110
概率為0.08的字元編碼為：1111
3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用線性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
搜索成功的平均搜索長度為：
ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10
4.（6分）
答： 希爾排序(增量為5,2,1)

六、演算法設計題（第1小題10分，第2小題8分）
1. (10分)
include <iostream.h>
include」string.h」
int charnumber=128;
void frequency(string&s,int C[ ]){
for(int i=0;i< charnumber;i++) C[i]=0;
for( i=0;i< s.length();i++) C[atoi(s[i])]++;
for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<」(」<<i<<」):\t」<<C[i]<<」\t」;
}
2. (8分)
類型定義（略）
int Level(BiTree bt) //層次遍歷二叉樹，並統計度為1的結點的個數
{
int num=0; //num統計度為1的結點的個數
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉樹結點指針為元素的隊列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p->data); //出隊,訪問結點
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)
num++;//度為1的結點
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入隊
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入隊
}
}
return(num); //返回度為1的結點的個數
}

B：

06－07第一學期期末考試試卷

試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科

一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。)
1.數據結構被形式地定義為 (K, R)，其中K是____的有限集，R是K上的關系有限集。
A.演算法 B.數據元素 C.數據操作 D.邏輯結構
2.在數據結構中，從邏輯上可以把數據結構分成____。
A.動態結構和靜態結構 B.緊湊結構和非緊湊結構
C.線性結構和非線性結構 D.內部結構和外部結構
3.以下的敘述中，正確的是____。
A.線性表的存儲結構優於鏈式存儲結構
B.二維數組是其數據元素為線性表的線性表
C.棧的操作方式是先進先出
D.隊列的操作方式是先進後出
4.若一個棧的入棧序列是1、2、3、… 、n，其輸出序列為p1、p2、p3、… 、pn，若p1=n，則pi為____。
A. i B. n = i C. n - i +1 D.不確定
5.判斷一個循環隊列QU (最多元素為m) 為空的條件是____。
A. QU->front == QU->rear B. QU->front != QU->rear
C. QU->front == (QU->rear+1)%m D. QU->front != (QU->rear+1)%m
6.在某單鏈表中，已知p所指結點不是最後結點，在p之後插入s所指結點，則執行____。
A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s; D. p->next = s; s->next = p;
7.串是一種特殊的線性表，其特殊性體現在____。
A.可以順序存儲 B.數據元素是一個字元
C.可以鏈接存儲 D.數據元素可以是多個字元
8.已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是____。
A. acbed B. decab C. deabc D. cedba
9.對於一個滿二叉樹，m個樹葉，n個結點，深度為h，則____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1
10.一個有n個頂點的無向圖最多有____條邊。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
11.順序查找法適合於存儲結構為____的線性表。
A. 散列存儲 B. 順序存儲或鏈接存儲
C. 壓縮存儲 D. 索引存儲
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B.選擇排序 C.快速排序 D. 歸並排序
二、填空題(請在每小題的橫線上填入正確內容，每空1分，共7分。)
1.在線性結構中，第一個結點 前驅結點，其餘每個結點有且只有1個前驅結點。
2.在無權圖G的鄰接矩陣中，若A[i][j]等於1，則等於A[j][i] = 。
3.根據二叉樹的定義，具有三個結點的二叉樹有 種不同的形態。
4.空格串是指 ，其長度等於 。
5.在散列存儲中，裝填因子α的值越大，則存儲元素時發生沖突的可能性就 。
6.已知模式串t= 『abacabaaad』， 其用KMP法求得的每個字元對應的next函數值為 。
三、簡答題(本大題共3小題，每小題5分，共15分)
1.比較靜態查找與動態查找的主要區別，它們的基本運算有哪些不同？
2.邏輯結構分哪幾種，存儲結構有哪幾種？
3.在具有n(n>1)個結點的各棵不同形態樹中，其中深度最小的那棵樹的深度是多少？它共有多少葉子和非葉子結點？
四、判斷題(本大題共10小題，命題正確的在題後括弧內寫 「T」，錯誤的在題後括弧內寫「F」，每小題1分，共10分)
1.每種數據結構都應具備三種基本運算：插入、刪除、搜索( )。
2.滿二叉樹不一定是完全二叉樹。( )
3.帶權連通圖的最小生成樹的權值之和一定小於它的其它生成樹的權值之和。( )
4.任一棵二叉搜索樹的平均搜索時間都小於用順序搜索法搜索同樣結點的順序表的平均搜索時間。( )
5.線性鏈表中所有結點的類型必須相同。( )
6.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所佔用的存儲空間大小隻與圖中頂點個數有關，而與圖的邊數無關( )。
7.在散列法中解決沖突時，其裝載因子的取值一定在(0，1)之間。( )
8.任何一個關鍵活動延遲，那麼整個工程將會延遲。( )
9.平衡二叉樹的左右子樹深度之差的絕對值不超過1。( )
10.n個結點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。( )
五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.下述演算法的功能是什麼? （6分）
LinkList Demo(LinkList L)
{ // L 是無頭結點單鏈表
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}
2.將給定的圖簡化為最小的生成樹，要求從頂點1出發。（7分）

3.設散列表為HT[13], 散列函數為 H (key) = key %13。用雙散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函數為 RH (key) = (7*key) % 10 + 1, 尋找下一個地址的公式為 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。畫出相應的散列表, 並計算等概率下搜索成功的平均搜索長度。（7分）
4.設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},寫出使用快速排序法每趟排序後的結果。（6分）
六、演算法設計題（本題共18分，第1小題10分，第2小題8分）
1.試設計一個實現下述要求的查找運算函數Locate。設有一個帶表頭結點的雙向鏈表L， 每個結點有4個數據成員：指向前驅結點的指針llink、指向後繼結點的指針rlink，存放字元數據的成員data和訪問頻度freq。所有結點的freq 初始時都為0。每當在鏈表上進行一次Locate(L, x) 操作時，令元素值為x的結點的訪問頻度freq加1，並將該結點前移，鏈接到與它的訪問頻度相等的結點後面，使得鏈表中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。(10分)
2.設一棵二叉樹以二叉鏈表為存貯結構，設計一個演算法將二叉樹中所有結點的左，右子樹相互交換。要求給出二叉鏈表的類型定義。(8分)

答案：

06－07第一學期
期末考試參考答案與評分標准

試卷代碼：03266B 授課課時：112
課程名稱：數據結構與演算法 適用對象：本科

一、單項選擇題(每小題2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空題(每空1分，共7分。)
1. 無
2. 1
3. 5
4. 串中字元全為空格 ， 空格的個數
5. 大
6. 0112123422 。
三、簡答題(本大題共5小題，每小題5分，共15分)
1．答：兩種查找方法最大的區別在於：
靜態查找方法不修改查找表；動態查找在查找不成功時，將結點插入查找表中，即有可能修改查找表；
靜態查找的基本運算有建表、查找和讀表元；動態查找除上述基本操作外還有初始化、插入和刪除操作；
2.答：根據數據元素之間關系的不同特性，通常有下列四類基本結構：(1)集合；(2)線性結構；(3)樹形結構；(4)圖狀結構或網狀結構。有兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。
3.答：深度最小的那棵樹的深度為2。對於這n個結點，除了一個根結點之外，其餘得n-1個結點均為葉子結點，故其深度為2。該樹葉子結點數為n-1，非葉子結點數為1。

四、判斷題(每小題1分，共10分)
1. (T) 2. (F) 3. (T) 4. (F) 5. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)

五、分析應用題（本題共26分，1、4小題各6分，2、3小題各7分）
1.（6分）
答：該演算法的功能是：將開始結點摘下鏈接到終端結點之後成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。
2.（7分）
答:

3.（7分）
答：使用散列函數H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用雙散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)

0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均搜索長度為：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、演算法設計題（第1小題10分，第2小題8分）
1.(10分)
答：
(1) 定義鏈表結構
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始時，所有結點的freq域的值都為0。
(2) 定義函數
DoubleListNode * locate ( DoubleListNode *f ; char &x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳過表頭結點*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*從鏈中摘下p*/
while ( q != f &&q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q後面插入p*/
}
return p;
}
2． (8分)
答：類型定義（略）
void exchange(BiTree bt)//將二叉樹bt所有結點的左右子樹交換
{
if(bt)
{ BiTree s；
s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交換
exchange(bt->lchild); //交換左子樹上所有結點的左右子樹
exchange(bt->rchild); //交換右子樹上所有結點的左右子樹
}
}

8. 如何學好數據結構，去哪裡刷題

推薦 1.演算法與數據結構考研試題精析(不一定需要考研才能做) 2.數據結構高分筆記 以上也是我自己考試使用的參考資料

9. 如何學好數據結構，去哪裡刷題

大數據學習。檸檬學院大數據，注冊就可以學習了，還有大數據的基礎課程，java，linux，mysql。