數據結構c語言版期末複習,數據結構c語言版期末考試題及答案

本文目錄一覽：

• 1、數據結構c語言版複習資料 數據結構課程設計 第二個最要緊(⊙o⊙)哦。。希望有這方面資料的大神。
• 2、急需數據結構C語言版（清華大學出版社）的期末考試試題及答案
• 3、我是大二的學生期末要考計算機組成原理和數據結構（c語言版） 這兩門課一般會考到哪些知識點？
• 4、怎麼複習數據結構C語言版
• 5、考研數據結構怎麼複習？
• 6、誰有數據結構（C語言版）的期末上機試題 啊？跪求。。。。

數據結構c語言版複習資料 數據結構課程設計 第二個最要緊(⊙o⊙)哦。。希望有這方面資料的大神。

在網上下載c語言編寫的小系統，一定就用到了數據結構，如鏈表，樹等。就可作為數據結構的課程設計

急需數據結構C語言版（清華大學出版社）的期末考試試題及答案

《數據結構》期末考試試卷（ A ）

一、 選擇題（每小題2分，共24分）

1．計算機識別、存儲和加工處理的對象被統稱為( A )

A.數據 B.數據元素

C.數據結構 D.數據類型

2．棧和隊列都是（ A ）

A．限制存取位置的線性結構 B．順序存儲的線性結構

C．鏈式存儲的線性結構 D．限制存取位置的非線性結構

3．鏈棧與順序棧相比，比較明顯的優點是( D )

A.插入操作更加方便 B.刪除操作更加方便

C.不會出現下溢的情況 D.不會出現上溢的情況

4．採用兩類不同存儲結構的字符串可分別簡稱為( B )

A.主串和子串 B.順序串和鏈串

C.目標串和模式串 D.變量串和常量串

5． 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是：B

A. 110 B .108

C. 100 D. 120

6．串是一種特殊的線性表，其特殊性體現在：B

A.可以順序存儲 B .數據元素是一個字符

C. 可以鏈接存儲 D. 數據元素可以是多個字符

7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： C

A. 2h B .2h-1

C. 2h+1 D. h+1

軟件開發網

8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這裡，我們把 由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ A

A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同

B .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同

C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同

D. 以上都不對

9．一個有n個頂點的無向圖最多有多少邊？C

A. n B .n(n-1)

C. n(n-1)/2 D. 2n

10．在一個圖中，所有頂點的度數之和等於所有邊數的多少倍?C

A. 1/2 B .1

C. 2 D. 4

11．當在二叉排序樹中插入一個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ A ）

A．左子樹的葉子結點 B．左子樹的分支結點

C．右子樹的葉子結點 D．右子樹的分支結點

軟件開發網

12．對於哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( D )

A.35和41 B.23和39

C.15和44 D.25和51

二、已知某棵二叉樹的前序遍歷結果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結果為D,B,G,E,A,H,F,I,J,C。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）

原理見課本128頁

三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分)

深度優先；C0-C1-C3-C4-C5-C2

寬度優先：C0-C1-C2-C3-C4-C5

四、有圖如下，按Kruskal算法求出其最小生成樹。要求寫出完整的步驟。（10分）

原理見課本250頁

五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查找關鍵字值12，93，166的過程。並寫出二分查找的算法。（20分）

0 1 2 3 4 5 6 7 8

12 23 45 66 76 88 93 103 166

過程：

mid=(0+8)/2=4

high=3,low=0 mid=1

high=0,low=0 mid=0（找到12）

high=8,low=5,mid=6（找到93）

high=8,low=7,mid=7

high=8 low=8 mid=8

算法：見課本84頁上

六、知單鏈表的結點結構為

Data next

下列算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。

請在空缺處填入合適的內容，使其成為完整的算法。 (可用文字說明該算法的基本思想及執行的過程，10分)

void SelectSort(LinkedList L)

{

LinkedList p,q,min;

DataType rcd;

p= (1) ;

while(p!=NULL) {

min=p;

q=p-next;

while(q!=NULL){

if( (2) )min=q;

q=q-next;

}

if( (3) ){

rcd=p-data;

p-data=min-data;

min-data=rcd;

}

(4) ;

}

}

本題不會。嘿嘿。。。。

七、一個完整的算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)

輸入：

四個基本性質：1.輸入：有零個或多個有外部提供的量作為算法的輸入

2：輸出：算法產生至少一個量作為輸出

3.：確定性：組成算法的每條指令是清晰的，無歧異的。

4.：有限性：算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的

八、何謂隊列的”假溢”現象？如何解決？（5分）

隊列的假溢現象是指數組實現的順序隊列中，隊尾指針已到達數組的下表上界產生上溢而隊頭指針之前還有若干 空間閑置的現象。解決的辦法之一是利用循環隊列技術使數組空間的首尾相連。

九、說明並比較文件的各種物理結構。（6分）

我是大二的學生期末要考計算機組成原理和數據結構（c語言版） 這兩門課一般會考到哪些知識點？

數據結構

會考到 樹 圖 鏈表 排序 哈希 等知識

組成原理

會考到

第1章

1．計算機系統的層次結構模型，及各層次功能

2．馮.諾依曼結構計算機的組成及特徵

3、計算機組成與計算機結構研究的內容分別是什麼？

第2章

1．二、十、十六進制數據之間的相互轉換

2．原碼整數、補碼整數、原碼小數、補碼小數的表示

3．浮點數的表示及規格化。

4．數據編碼及基本運算：(1)真值—原碼、補碼（2）原碼、補碼— 真值(3)補碼移位運算：*2n或/2n（4）[x]補—[-x]補（5）補碼填充運算：8位補碼求16位補碼

5．

6．對數據做奇偶校驗

7．對數據做海明校驗

8．已知生成多項式，對數據做循環冗餘校驗

第3章

1．4位先行進位加法器的推導過程

2．由4位先行進位加法器的組成組間先行進位加法器的邏輯電路圖

3．74181功能及控制信號含義

4．74182功能及控制信號含義

5．補碼加減法及判斷溢出

6．已知2個數據，採用原碼1位乘法求乘積

7．已知2個數據，採用補碼1位乘法求乘積

8．已知2個數據，採用恢復餘數法求商

9．已知2個數據，採用不恢復餘數法（加減交替法）求商

10．浮點數加減運算。

第4章

1．存儲系統的層次結構及特徵

2．已知SRAM存儲芯片容量，構成存儲器電路圖。

3．DRAM特徵。

4．DRAM三種刷新方式計算及比較

5．cache直接映象方式的地址對應關係，及數據訪問的命中率計算

6．cache組相聯映象方式的地址對應關係，及數據訪問的命中率計算

7．直接映象方式和組相聯映象方式在採用FIFO和LRU替換算法時的cache數據替換命中情況

第5章

1．根據指令格式，將指令翻譯為二進制編碼

2．根據指令格式，將二進制編碼翻譯為指令，求指令的有效地址，各種尋址方式的尋址範圍，指令的執行結果等

3．根據題目中的指令種類，指令尋址方式，指令地址碼個數等要求，設計固定操作碼的指令格式，以及分配編碼

4．根據題目中的指令種類，指令尋址方式，指令地址碼個數等要求，設計擴展操作碼的指令格式，以及分配編碼

第6章

1．寫出程序在機器硬件上的執行過程（操作序列或者控制信號序列）

2．.微程序控制器的組成部分及功能

3．根據信號數量及信號產生時序，設計水平直接表示型微指令格式

4. 根據信號數量及信號產生時序，設計水平字段直接編碼型微指令格式

怎麼複習數據結構C語言版

弄些以前的習題做做，特別是上幾屆的考試習題，發的那本書也該翻一翻了首先應該搞懂那些數據結構的定義，搞懂線性表，鏈表，隊列，棧，各種排序算法，樹的幾種表示法以及樹的遍歷，哈希表，應該就差不多了，太難得估計也不會考。

考研數據結構怎麼複習？

考研數據結構可以根據以下幾點來複習：

1、看清華大學出版社 嚴蔚敏 《數據結構》的教材，C語言版本，這個是最基本的。清華大學計算機考碩士、博士都是考這本書，也是考研官方推薦的教材。數據結構有些是C++語言描述的，有些是JAVA語言描述的，如果你報考的高校沒有特別要求，一般就用嚴的C語言版本的教材。

2、買一本專門的考研數據結構科目的複習指導，盡量把裏面的題目都做一遍，這個有幾個系列的，基本每年考研都出一版，裏面有國家統考和各個大學歷年考研題目，答案詳細。比如《天勤計算機考研高分筆記系列》，還有王道系列等。

3、推薦一本很有深度的數據結構習題集，李春葆的《數據結構習題與解析》。

4、你所報考的大學的歷年專業課真題是重中之重，每年考試的題目類型可能相似。

誰有數據結構（C語言版）的期末上機試題 啊？跪求。。。。

線性表

1、 某軟件公司大約有30名員工，每名員工有姓名、工號、職務等屬性，每年都有員工離職和入職。

把所有員工按照順序存儲結構建立一個線性表，建立離職和入職函數，當有員工離職或入職時，修改線性表，並且打印最新的員工名單。

2、 約瑟夫（Josephus）環問題：編號為1,2,3,…,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選一個正整數作為報數的上限值m，從第一個人開始按順時針方向自1開始順序報數,報到m時停止。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一人開始重新從1報數，如此下去，直到所有人全部出列為止。

建立n個人的單循環鏈表存儲結構，運行結束後，輸出依次出隊的人的序號。

棧和隊列

3、 某商場有一個100個車位的停車場，當車位未滿時，等待的車輛可以進入並計時；當車位已滿時，必須有車輛離開，等待的車輛才能進入；當車輛離開時計算停留的的時間，並且按照每小時1元收費。

汽車的輸入信息格式可以是（進入/離開，車牌號，進入/離開時間），要求可以隨時顯示停車場內的車輛信息以及收費歷史記錄。

4、 某銀行營業廳共有6個營業窗口，設有排隊系統廣播叫號，該銀行的業務分為公積金、銀行卡、理財卡等三種。公積金業務指定1號窗口，銀行卡業務指定2、3、4號窗口，理財卡業務指定5、6號窗口。但如果5、6號窗口全忙，而2、3、4號窗口有空閑時，理財卡業務也可以在空閑的2、3、4號窗口之一辦理。

客戶領號、業務完成可以作為輸入信息，要求可以隨時顯示6個營業窗口的狀態。

5、4階斐波那契序列如下：f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4，

利用容量為k=4的循環隊列，構造序列的前n+1項（f0, f1 , f2 ,… fn ），要求滿足fn ≤200而fn+1 200。

6、八皇后問題：設8皇后問題的解為 (x1, x2, x3, …,x8), 約束條件為：在8×8的棋盤上，其中任意兩個xi 和xj不能位於棋盤的同行、同列及同對角線。要求用一位數組進行存儲，輸出所有可能的排列。

7、迷宮求解：用二維矩陣表示迷宮，自動生成或者直接輸入迷宮的格局，確定迷宮是否能走通，如果能走通，輸出行走路線。

8、英國人格思里於1852年提出四色問題(four colour problem，亦稱四色猜想），即在為一平面或一球面的地圖着色時，假定每一個國家在地圖上是一個連通域，並且有相鄰邊界線的兩個國家必須用不同的顏色，問是否只要四種顏色就可完成着色。現在給定一張地圖，要求對這張地圖上的國家用不超過四種的顏色進行染色。

要求建立地圖的鄰接矩陣存儲結構，輸入國家的個數和相鄰情況，輸出每個國家的顏色代碼。

9、以下問題要求統一在一個大程序里解決。

從原四則表達式求得後綴式，後綴表達式求值，從原四則表達式求得中綴表達式，從原四則表達式求得前綴表達式，前綴表達式求值。

數組與廣義表

10、 鞍點問題： 若矩陣A中的某一元素A[i,j]是第i行中的最小值，而又是第j列中的最大值，則稱A[i,j]是矩陣A中的一個鞍點。寫出一個可以確定鞍點位置的程序。

11、 稀疏矩陣轉置： 輸入稀疏矩陣中每個元素的行號、列號、值，建立稀疏矩陣的三元組存儲結構，並將此矩陣轉置，顯示轉置前後的三元組結構。

12、 用頭尾鏈表存儲表示法建立廣義表，輸出廣義表，求廣義表的表頭、廣義表的表尾和廣義表的深度。

樹和二叉樹

以下問題要求統一在一個大程序里解決。

13、 按先序遍歷的擴展序列建立二叉樹的存儲結構

14、 二叉樹先序、中序、後序遍歷的遞歸算法

15、 二叉樹中序遍歷的非遞歸算法

16、 二叉樹層次遍歷的非遞歸算法

17、 求二叉樹的深度(後序遍歷)

18、 建立樹的存儲結構

19、 求樹的深度

圖

20、 輸入任意的一個網，用普里姆(Prim)算法構造最小生成樹。

21、 要求建立圖的存儲結構（鄰接表或鄰接矩陣），輸入任意的一個圖，顯示圖的深度優先搜索遍歷路徑。

22、 要求建立圖的存儲結構（鄰接表或鄰接矩陣），輸入任意的一個圖，顯示圖的廣度優先搜索遍歷路徑。

查找

23、 設計一個讀入一串整數構成一顆二叉排序樹的程序，從二叉排序樹中刪除一個結點，使該二叉樹仍保持二叉排序樹的特性。

24、設定哈希函數 H(key) = key MOD 11 ( 表長=11 )，輸入一組關鍵字序列，根據線性探測再散列解決衝突的方法建立哈希表的存儲結構，顯示哈希表，任意輸入關鍵字，判斷是否在哈希表中。

排序

以下問題要求統一在一個大程序里解決。

25、折半插入排序

26、冒泡排序

27、快速排序

28、簡單選擇排序

29、歸併排序

30、堆排序

這些是我們的上機題目 請參考