第一篇：數(shù)據(jù)結(jié)構(gòu)復習資料
數(shù)據(jù)結(jié)構(gòu)復習資料
模塊一：計算題
一.一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。
二叉樹自畫！
二．試列出如下圖中全部可能的拓撲排序序列。
123456 解：全部可能的拓撲排序序列為：152364、152634、156234、561234、516234、512634、512364 三．已知哈希表地址空間為0..8，哈希函數(shù)為H(key)=key%7，采用線性探測再散列處理沖突，將數(shù)據(jù)序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入時的比較次數(shù)，并求出在等概率下的平均查找長度以及查找因子。
解：哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：
ASL=1(4×1+1×2+1×4+2×5)=2.5
8a=8/9
四．已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。
解：
五．設(shè)有序列：w={23,24,27,80,28}，試給出哈夫曼樹； 哈夫曼樹如下圖所示：
六：已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI
解：先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子結(jié)點，由類似的方法可確定其他結(jié)點，如下圖所示。
七．（本題8分）
對于如下圖所示的G，用Kruskal算法構(gòu)造最小生成樹，要求圖示出每一步的變化情況。
解：用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示：
八．給出一組關(guān)鍵字29、18、25、47、58、12、51、10，寫出歸并排序方法進行排序時的變化過程。
解：
(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58)
九．
三、（本題8分）
請畫出如下圖所示的鄰接表。
解：鄰接表如下圖所示：
***45454∧∧∧∧5∧ 十．判斷以下序列是否是小根堆? 如果不是，將它調(diào)整為小根堆。（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 解：（1）不是小根堆。調(diào)整為：{12,24,33,65,33,56,48,92,86,70}
（2）是小根堆。
十一． 設(shè)有如下圖所示的AOE網(wǎng)（其中vi（i=l，2，…，6）表示事件，弧上表示活動的天數(shù)）。
v26v14v48217v311v693v5 找出所有的關(guān)鍵路徑。
解：所有的關(guān)鍵路徑有：v1→v2→v3→v5→v6，以及v1→v4→v6。十二.對給定的有7個頂點的有向圖的鄰接矩陣如下：（l）畫出該有向圖；
（2）若將圖看成是AOE-網(wǎng)，畫出關(guān)鍵路徑。
??????????????????252?2???1?????????????????8???35???
5????39????5??????
解：（1）由鄰接矩陣所畫的有向圖如下圖所示：
2212523***5）關(guān)鍵路徑如下圖所示：
22213715945 4（2
第二篇：數(shù)據(jù)結(jié)構(gòu)期末復習資料
《數(shù)據(jù)結(jié)構(gòu)》課程復習資料
第一章：數(shù)據(jù)結(jié)構(gòu)概述
1、掌握數(shù)據(jù)結(jié)構(gòu)的定義，即數(shù)據(jù)結(jié)構(gòu)三要素：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作；
2、數(shù)據(jù)結(jié)構(gòu)包括：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；
3、數(shù)據(jù)之間的關(guān)系：表（一對一之間的關(guān)系）、樹（一對多之間的關(guān)系）、圖（多對多之間的關(guān)系）；
4、算法的定義：算法衡量的標準：時間復雜度和空間復雜度；
5、算法時間復雜度的求法：給定一段程序，求其時間復雜度；時間復雜度的比較；
6、為什么學習“數(shù)據(jù)結(jié)構(gòu)”？“數(shù)據(jù)結(jié)構(gòu)”課程主要學了哪些知識？
第二章：線性表
1、線性表按照存儲結(jié)構(gòu)不同分為順序表、鏈式表；順序表的特點：邏輯上相鄰的兩個元素在物理上也相鄰；鏈式表的特點：邏輯上相鄰的兩個元素在物理上未必相鄰；（“未必”的含義是可相鄰也可以不相鄰）
2、比較線性表順序存儲和鏈式存儲的優(yōu)缺點。
第三章：棧和隊列
1、棧和隊列的特點：棧：后進先出，隊列：先進先出
2、熟悉棧和隊列的基本操作：初始化棧、入棧操作、出棧操作、判斷棧是否為空、取棧頂元素等。
3、根據(jù)實例，能夠容易的判斷出是棧的應(yīng)用還是隊列的應(yīng)用？
4、重點掌握棧的應(yīng)用：進制轉(zhuǎn)換算法的思想或程序。
第四章：數(shù)組
1、牢記對稱矩陣、三角矩陣、對角矩陣的特點，掌握矩陣中的元素Aij與一維數(shù)組SA[K]的對應(yīng)關(guān)系。
2、掌握稀疏矩陣的三元組表示法。
第五章：串
1、掌握上課介紹的9種函數(shù)名稱及其實現(xiàn)結(jié)果；
第六章：樹
1、二叉樹的5個性質(zhì)；
2、二叉樹前序、中序和后序遍歷，根據(jù)2種遍歷結(jié)果求第3種遍歷結(jié)果。
3、完全二叉樹、滿二叉樹、哈弗曼樹的定義；
4、給定一組葉子權(quán)值，求帶權(quán)路徑長度最小的多少？
第七章：圖
1、掌握圖的術(shù)語：無向完全圖、有向完全圖、頂點的度等；
2、圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷；
3、圖的鄰接矩陣存儲，給定一個圖，求出鄰接矩陣；或者給定一個鄰接矩陣，構(gòu)造圖；
4、圖的最小生成樹；
第八章：查找
1、查找的定義：靜態(tài)查找和動態(tài)查找
2、折半查找算法的思想；
第九章：排序
1、掌握排序的分類：插入排序、交換排序、選擇排序；
2、重點掌握希爾排序、快速排序、簡單選擇排序；
第三篇：數(shù)據(jù)結(jié)構(gòu)參考材料
數(shù)據(jù)結(jié)構(gòu)參考題目
一、選擇
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）
A.棧 B.隊列 C.樹 D.圖 2.下面程序段的時間復雜度為（）for(i=0;i
A.串的長度相等 B.含有相同的字符集
C.都是非空串 D.串的長度相等且對應(yīng)的字符相同 5．若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M行的棧操作系列是（）
A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為（）A.0 B.1 C.48 D.49 7.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結(jié)果為
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
A.插入排序 B.冒泡排序 C.快速排序 D.歸并排序
8.已知散列表的存儲空間為T[0..16]，散列函數(shù)H（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關(guān)鍵字：T[5]=39，T[6]=57和T[7]=7，則下一個關(guān)鍵字23插入的位置是（）
A.T[2] B.T[4] C.T[8] D.T[10] 9.如果將矩陣An×n的每一列看成一個子表，整個矩陣看成是一個廣義表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為Dout，則所有頂點的入度之和為（）
A.Dout B.Dout-1 C.Dout+1 D.n 11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）A線性結(jié)構(gòu) B.樹形結(jié)構(gòu) C.線性結(jié)構(gòu)和樹型結(jié)構(gòu) D.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)
12．棧的插入和刪除操作在()進行。
A．棧頂 B.棧底 C.任意位置 D指定位置 13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A.24 B.71 C.48 D.53 14．一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．關(guān)于棧和隊列的說法中正確的是（）
A．棧和隊列都是線性結(jié)構(gòu) B.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu) C.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu) D.棧和隊列都不是線性結(jié)構(gòu) 16．關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（）A．順序存儲比鏈式存儲少占空間 B.順序存儲比鏈式存儲多占空間
C.順序存儲和鏈式存儲都要求占用整塊存儲空間 D.鏈式存儲比順序存儲難于擴充空間
17．已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q；
18．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）A.1 B.2 C.3 D.4 19．執(zhí)行下面程序段時，S語句被執(zhí)行的次數(shù)為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結(jié)點的時間復雜度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）
A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．關(guān)于串的敘述中，正確的是（）A．空串是只含有零個字符的串 B.空串是只含有空格字符的串
C.空串是含有零個字符或含有空格字符的串
D.串是含有一個或多個字符的有窮序列
23．在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）
A．front==rear
B.(front+1)%m==rear
C.rear+1==front
D.(rear+1)%m==front 24．設(shè)有二維數(shù)組
?1????A［n］［n］表示如下：?23456??????????，則A［i］［i］（0≤i≤n-1）的D.i2/2 值為（）
A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）
hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）
A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）A.n B.n-1 C.n+1 D.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）A.矩陣中非全零元素的行數(shù)等于圖中的頂點數(shù)
B.第i行上與第i列上非零元素總和等于頂點Vi的度數(shù) C.矩陣中的非零元素個數(shù)等于圖的邊數(shù)
D.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等
29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）A.1 B.2 C.3 D.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關(guān)鍵字值為基準得到的一次劃分為（）
A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81
二、填空題
1.數(shù)據(jù)是計算機加工處理的對象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面()。
3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進先出的線性表（）。
5.從循環(huán)鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的前驅(qū)結(jié)點（）。6.單鏈表設(shè)置頭結(jié)點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）。
9.從非循環(huán)鏈表的某一結(jié)點出發(fā)，既能找到它的后繼結(jié)點，又能找到它的前驅(qū)結(jié)點（）。
10.單鏈表結(jié)點的指針域是用來存放其直接后繼結(jié)點的首地址的（）
11.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象（）。
12.用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。
13.在非線性結(jié)構(gòu)中，至少存在一個元素不止一個直接前驅(qū)或不止一個直接后驅(qū)（）。14.樹的最大特點是一對多的層次結(jié)構(gòu)（）。15.隊列的特點是先進先出（）。
16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨立于計算機（）。18.線性表簡稱為”順序表”。（）
19.對數(shù)據(jù)的任何運算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點出發(fā)，可以找到表中的所有結(jié)點（）。21.棧是一種先進先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。
27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學模型（）。
28.線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進后出的線性表（）。
30.將插入和刪除限定在表的同一端進行的線性表是隊列（）。
三、畫圖題
1.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={A,B,C,D,E,F,G,H,I,J} R={
K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}
四、運算題
1．已知一個圖的頂點集V和邊集H分別為：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。
2.一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。
平均查找長度：（寫出計算過程）
3．已知一個圖的頂點集V和邊集H分別為：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發(fā)）
____
__，___
_，___
___，__
____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：
前序： 中序： 后序：
5.設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。
五、編程題
1.請編寫一個算法，實現(xiàn)十進制整數(shù)與二進制數(shù)的轉(zhuǎn)換。Void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：
Int search_bin(Keytype k,sstable st){ 3.請編寫一個算法，實現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點）。LINKLIST *INVERTLINK(LINKLIST *H){
第四篇：數(shù)據(jù)結(jié)構(gòu)C語言版期末考試試題(附帶復習資料)
“數(shù)據(jù)結(jié)構(gòu)”期末考試試題
一、單選題(每小題2分，共12分)1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行()。A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL；
D． p一>next＝HL一>next;HL一>next＝p； 2．n個頂點的強連通圖中至少含有()。A.n—l條有向邊 B.n條有向邊
C.n(n—1)／2條有向邊 D.n(n一1)條有向邊
3.從一棵二叉搜索樹中查找一個元素時，其時間復雜度大致為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A．24 B．48 C． 72 D． 53 5．當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。
A.整形 B.引用型
C.指針型 D.常值引用型·
6．向一個長度為n的順序表中插人一個新元素的平均時間復雜度為()。A．O(n)B．O(1)C．O(n2)D．O(10g2n)
二、填空題(每空1分，共28分)1．數(shù)據(jù)的存儲結(jié)構(gòu)被分為——、——、——和——四種。
2．在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)?yīng)不同，各自分別為——域和——域。
3．——中綴表達式 3十x*(2.4／5—6)所對應(yīng)的后綴表達式為————。4．在一棵高度為h的3叉樹中，最多含有——結(jié)點。
5．假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為——，最大深度為——·
6．在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定——該結(jié)點的值，右子樹上所有結(jié)點的值一定——該結(jié)點的值。
7．當向一個小根堆插入一個具有最小值的元素時，該元素需要逐層——調(diào)整，直到被調(diào)整到——位置為止。
8．表示圖的三種存儲結(jié)構(gòu)為——、——和———。9．對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時，其時間復雜度為——，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為——。
10．從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時，其查找長度分別為——和——· 11．假定對長度n＝144的線性表進行索引順序查找，并假定每個子表的長度均為，則進行索引順序查找的平均查找長度為——，時間復雜度為——· 12．一棵B—樹中的所有葉子結(jié)點均處在——上。
13．每次從無序表中順序取出一個元素，把這插入到有序表中的適當位置，此種排序方法叫做——排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做——排序。
14．快速排序在乎均情況下的時間復雜度為——，最壞情況下的時間復雜度為——。
三、運算題(每小題6分，共24分)1．假定一棵二叉樹廣義表表示為a(b(c，d)，c(((，8)))，分別寫出對它進行先序、中序、后序和后序遍歷的結(jié)果。
先序：
中序；
后序：
2．已知一個帶權(quán)圖的頂點集V和邊集G分別為： V＝{0，1，2，3，4，5}；
E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}，則求出該圖的最小生成樹的權(quán)。
最小生成樹的權(quán)；
3．假定一組記錄的排序碼為(46，79，56，38，40，84，50，42)，則利用堆排序方法建立的初始堆為——。
4．有7個帶權(quán)結(jié)點，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。
帶權(quán)路徑長度：—— 高度：—— 雙分支結(jié)點數(shù)：——。
四、閱讀算法，回答問題(每小題8分，共16分)1．VOldAC(List&L){ InitList(L)；
InsertRear(L;25)； InsertFront(L，50)；
IntaL4]＝{5，8，12，15，36};for(inti＝0;i<5;i++)if(a[i]％2＝＝0)InsertFront(L，a[i])； elselnsertRear(L，a[i])； } 該算法被調(diào)用執(zhí)行后，得到的線性表L為： 2．void AG(Queue&Q){ InitQueue(Q)；
inta[5]＝{6，12，5，15，8}；
for(int i＝0;i<5;i++)QInsert(Q，a[i])； QInsert(Q，QDelete(Q))； QInsert(Q，20)；
QInsert(Q，QDelete(Q)十16)；
while(!QueueEmpty(Q))cout< 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分)1．從一維數(shù)組A[n)中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應(yīng)元素的下標，否則返回一1。 IntBinsch(ElemTypeA[]，Intlow，int high，KeyTypeK){ if(low<＝high){ int mid＝(low+high)／2； if(K＝＝A[mid].key)——； else if(K structBinTreeNode{ElemType data；BinTreeNode*left，*right}； 其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為x的結(jié)點所在的層號，請在劃有橫線的地方填寫合適內(nèi)容。Int NodeLevel(BinTreeNode * BT，ElemType X){ if(BT：＝NULL)return 0； ／／空樹的層號為0 else if(BT一>data＝＝X)return 1;／／根結(jié)點的層號為1 ／／向子樹中查找x結(jié)點 else{ int cl＝NodeLevel(BT一>left，X)； if(cl>＝1)return cl+1;int c2＝ ； if——； ／／若樹中不存在X結(jié)點則返回o else return 0； } } 六、編寫算法(8分)按所給函數(shù)聲明編寫一個算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點，該最大值由函數(shù)返回，若單鏈表為空則中止運行。EIemType MaxValue(LNOde*HL); “數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案 一、單選題(每小題2分，共12分)評分標準；選對者得2分，否則不得分。 1．B 2．B 3．C 4．D 5．B 6．A 二、填空題(每空1分，共28分)1．順序結(jié)構(gòu) 鏈接結(jié)構(gòu) 索引結(jié)構(gòu) 散列結(jié)構(gòu)(次序無先后)2．值(或data)子表指針(或sublist)3．3 x 2．4 5／6一*十 4．(3h一1)／2 5． 5 18 6．小于 大于(或大于等于)7．向上 堆頂 8．鄰接矩陣 鄰接表 邊集數(shù)組(次序無先后)9．O(n2)O(e)10． 1 3 11．13 O()12．同一層 13．插人 選擇 14．O(nlog2n)O(n2) 三、運算題(每小題6分，共24分)1．先序：a，b，c，d，e，f，e ／／2分 中序：c，b，d，a，f，8，e ／／2分 后序：c，d，b，e，f，e，a ／／2分 2．最小生成樹的權(quán)：31 ／／6分 3．(84，79，56，42，40，46，50，38)／／6分 4．帶權(quán)路徑長度：131 ／／3分 高度：5 ／／2分 雙分支結(jié)點數(shù)：6 ／／1分 四、閱讀算法，回答問題(每小題8分，共16分)評分標準：每小題正確得8分，出現(xiàn)一處錯誤扣4分，兩處及以上錯誤不得分。1．(36，12，8，50，25，5，15)2．5 15 8 6 20 28 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分)1．feturn mid ／／2分 returnBinsch(A，low，mid一1，K)／／2分 returnBmsch(A，mid+1，high，K)／／2分 2．NodeLevel(BT一>right，X)／／3分(c2>=1)returnc2十1 ／／3分 六、編寫算法(8分)評分標準：請參考語句后的注釋，或根據(jù)情況酌情給分。ElemType MaxValue(LNodeO* HL。){ if(HL＝=NUlL){ ／／2分 cerr<<"Linked llst is empty!”< if(max data)max＝p一>data； p＝p一>next； } returnmax； ／／8分 } 數(shù)據(jù)結(jié)構(gòu)復習資料 一、填空題 1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 操作對象 以及它們之間的 關(guān)系 和運算等的學科。 2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的關(guān)系 有限集合。 3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。 4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu)。5.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。 6． 在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。 7.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。8.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個。 9．數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引 和 散列。 10.數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。11.一個算法的效率可分為 時間 效率和 空間 效率。 12.在順序表中插入或刪除一個元素，需要平均移動 表中一半元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。 13.線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。 14.向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 n-i+1 個元素。 15.向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。 16.在順序表中訪問任意一結(jié)點的時間復雜度均為 O(1)，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。 17.順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。 18．在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。19． 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O（n）。 20.向量、棧和隊列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。21.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂。不允許插入和刪除運算的一端稱為 棧底。 22.隊列 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。23.不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。 24.子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標串，子串 稱為模式。25.假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為(8+4)×6+1000=1072 ；若按列存儲時，元素A47的第一個字節(jié)地址為(6×7＋4)×6＋1000）＝1276。 26． 由３個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 27.一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結(jié)點和 26-1 =32 個葉子。注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。28． 一棵具有２５７個結(jié)點的完全二叉樹，它的深度為 9。（注：用? log2(n)?+1= ? 8.xx ?+1=9 29．設(shè)一棵完全二叉樹有700個結(jié)點，則共有 350 個葉子結(jié)點。答：最快方法：用葉子數(shù)＝[n/2]＝350 30． 設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 500 個葉子結(jié)點，有 499 個度為2的結(jié)點，有 1 個結(jié)點只有非空左子樹，有 0 個結(jié)點只有非空右子樹。 答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結(jié)點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數(shù)＝0.31．在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是 順序查找（線性查找）。32.線性有序表（a1，a2，a3，?，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個結(jié)點，用二分法查找時，最大比較次數(shù)是 7。 33.假設(shè)在有序線性表a[20]上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1；比較兩次查找成功的結(jié)點數(shù)為 2 ；比較四次查找成功的結(jié)點數(shù)為 8 ；平均查找長度為 3.7。解：顯然，平均查找長度＝O（log2n）<5次（25）。但具體是多少次，則不應(yīng)當按照公式 ASL?n?1log2(n?1)來計算（即（21×log221）/20＝4.6n次并不正確！）。因為這是在假設(shè)n＝2m-1的情況下推導出來的公式。應(yīng)當用窮舉法羅列： 全部元素的查找次數(shù)為＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7??！34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。 35.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找。36.散列法存儲的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲地址。 二、判斷正誤（在正確的說法后面打勾，反之打叉）（×）1.鏈表的每個結(jié)點中都恰好包含一個指針。 答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。 （×）2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序。 （×）3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。 （×）4.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（×）5.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜” （×）6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。（×）7.線性表在物理存儲空間中也一定是連續(xù)的。 錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。 （×）8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。 （×）9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。 錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。（后一節(jié)介紹）（×）10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。 （×）11.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈式存儲，與元素數(shù)據(jù)類型無關(guān)。（×）12.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。 （√）13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。（√）14.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（×）15.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（×）16.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）17.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （√）18.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （×）19.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。 錯，后半句不對。 （×）20.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。（√）21.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n—1個非空指針域。 （×）22.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。（√）23.二叉樹中每個結(jié)點的兩棵子樹是有序的。 （×）24.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。（×）25.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。（應(yīng)當是二叉排序樹的特點）（×）26.二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （×）27.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。 （×）28.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i—1個結(jié)點。（應(yīng)2i-1） （√）29.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。 （√）30.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。 三、單項選擇題 （B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種： A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)； A)存儲 B)物理 C)邏輯 D)物理和存儲（C）3.算法分析的目的是： A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)研究算法中的輸入和輸出的關(guān)系 C)分析算法的效率以求改進 D)分析算法的易懂性和文檔性（A）4.算法分析的兩個主要方面是： A)空間復雜性和時間復雜性 B)正確性和簡明性 C)可讀性和文檔性 D)數(shù)據(jù)復雜性和程序復雜性（C）5.計算機算法指的是： A)計算方法 B)排序方法 C)解決問題的有限運算序列 D)調(diào)度方法（B）6.計算機算法必須具備輸入、輸出和 等5個特性。A)可行性、可移植性和可擴充性 B)可行性、確定性和有窮性 C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wěn)定性和安全性 （C）7．數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）順序存儲結(jié)構(gòu)（D）鏈式存儲結(jié)構(gòu) （B）8.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110（B）108（C）100（D）120（A）9.在n個結(jié)點的順序表中，算法的時間復雜度是O（1）的操作是：（A）訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）（B）在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）（C）刪除第i個結(jié)點（1≤i≤n）（D）將n個結(jié)點從小到大排序（B）10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素 （A）8（B）63.5（C）63（D）7（A）11.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： （A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針（B）只有一部分，存放結(jié)點值 (C）只有一部分，存儲表示結(jié)點間關(guān)系的指針 （D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（B）12.鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序（B）鏈式（C）星式（D）網(wǎng)狀 （D）13.線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以 （B）14． 線性表Ｌ在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。（Ａ）需經(jīng)常修改Ｌ中的結(jié)點值（Ｂ）需不斷對Ｌ進行刪除插入（Ｃ）Ｌ中含有大量的結(jié)點（Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復雜（B）15.棧中元素的進出原則是 Ａ．先進先出 Ｂ．后進先出 Ｃ．?？談t進 Ｄ．棧滿則出 （C）16.若已知一個棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不確定（B）17.判定一個棧ST（最多元素為m0）為空的條件是 Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 （C）18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍。A．1/2 B.1 C.2 D.4（B）19.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。A．1/2 B.1 C.2 D.4（B）20.有8個結(jié)點的無向圖最多有 條邊。 A．14 B.28 C.56 D.112（C）21.有8個結(jié)點的有向完全圖有 條邊。 A．14 B.28 C.56 D.112（B）22．在表長為ｎ的鏈表中進行線性查找，它的平均查找長度為 Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝n＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ （A）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50（C）24．對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較 次關(guān)鍵字。 A．3 B．4 C．5 D． 6（A）25.鏈表適用于 查找 A．順序 B．二分法 C．順序，也能二分法 D．隨機 《數(shù)據(jù)結(jié)構(gòu)與算法》復習題 一、選擇題。 1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2．數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指 A。 A．數(shù)據(jù)的存儲結(jié)構(gòu) B．數(shù)據(jù)結(jié)構(gòu) C．數(shù)據(jù)的邏輯結(jié)構(gòu) D．數(shù)據(jù)元素之間的關(guān)系 3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。A．邏輯 B．存儲 C．邏輯和存儲 D．物理 4．在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 C。A．數(shù)據(jù)的處理方法 B．數(shù)據(jù)元素的類型 C．數(shù)據(jù)元素之間的關(guān)系 D．數(shù)據(jù)的存儲方法 5．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮 A。A．各結(jié)點的值如何 B．結(jié)點個數(shù)的多少 C．對數(shù)據(jù)有哪些運算 D．所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。6．以下說法正確的是 D。A．數(shù)據(jù)項是數(shù)據(jù)的基本單位 B．數(shù)據(jù)元素是數(shù)據(jù)的最小單位 C．數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) 7．算法分析的目的是 C，算法分析的兩個主要方面是 A。 （1）A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 C．分析算法的效率以求改進 C．分析算法的易讀性和文檔性（2）A．空間復雜度和時間復雜度 B．正確性和簡明性 C．可讀性和文檔性 D．數(shù)據(jù)復雜性和程序復雜性 8．下面程序段的時間復雜度是 O(n2)。 s =0;for(I =0;i for(j=0;j s +=B[i][j];sum = s; 9．下面程序段的時間復雜度是 O(n*m)。 for(i =0;i for(j=0;j A[i][j] ＝ 0; 10．下面程序段的時間復雜度是 O(log3n)。 i ＝ 0； while（i<=n） i = i * 3； 11．在以下的敘述中，正確的是 B。A．線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu) B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C．棧的操作方式是先進先出 D．隊列的操作方式是先進后出 12．通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 B。A．數(shù)據(jù)元素具有同一特點 B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致 C．每個數(shù)據(jù)元素都一樣 D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 13．鏈表不具備的特點是 A。 A．可隨機訪問任一結(jié)點 B．插入刪除不需要移動元素 C．不必事先估計存儲空間 D．所需空間與其長度成正比 14．不帶頭結(jié)點的單鏈表head為空的判定條件是 A。A．head == NULL B head->next ==NULL C．head->next ==head D head!=NULL 15．帶頭結(jié)點的單鏈表head為空的判定條件是 B。A．head == NULL B head->next ==NULL C．head->next ==head D head!=NULL 16．若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用 D 存儲方式最節(jié)省運算時間。 A．單鏈表 B．給出表頭指針的單循環(huán)鏈表 C．雙鏈表 D．帶頭結(jié)點的雙循環(huán)鏈表 17．需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是 B。A．單鏈表 B．靜態(tài)鏈表 C．線性鏈表 D．順序存儲結(jié)構(gòu) 18．非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足 C。A．p->next == NULL B．p == NULL C．p->next ==head D．p == head 19．在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是 D。A．p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s 20．如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用 D 存儲方式最節(jié)省時間。A．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D． 順序表 21．在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是 B。A．O（1）B．O（n）C．O（n2）D．O（nlog2n） 22．在一個長度為n（n>1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。 A．刪除單鏈表中的第一個元素 B．刪除單鏈表中的最后一個元素 C．在單鏈表第一個元素前插入一個新元素 D．在單鏈表最后一個元素后插入一個新元素 23．與單鏈表相比，雙鏈表的優(yōu)點之一是 D。A．插入、刪除操作更簡單 B．可以進行隨機訪問 C．可以省略表頭指針或表尾指針 D．順序訪問相鄰結(jié)點更靈活 24．如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B。 A．只有表頭指針沒有表尾指針的循環(huán)單鏈表 B．只有表尾指針沒有表頭指針的循環(huán)單鏈表 C．非循環(huán)雙鏈表 D．循環(huán)雙鏈表 25．在長度為n的順序表的第i個位置上插入一個元素（1≤ i ≤n+1），元素的移動次數(shù)為： A。 A．n – i + 1 B．n – i C．i D．i – 1 26．對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為 C。A．順序表 B． 用頭指針表示的循環(huán)單鏈表 C．用尾指針表示的循環(huán)單鏈表 D．單鏈表 27．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？ C。 A插入運算方便 B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示 C存儲密度大 D刪除運算方便 28．下面關(guān)于線性表的敘述中，錯誤的是哪一個？ B。 A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元 B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元 D線性表采用鏈式存儲，便于進行插入和刪除操作。 29．線性表是具有n個 B 的有限序列。 A．字符 B．數(shù)據(jù)元素 C．數(shù)據(jù)項 D．表元素 30．在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是O（1）的操作是 A。 A．訪問第i（1<=i<=n）個結(jié)點和求第i個結(jié)點的直接前驅(qū)（1 31．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為 C。 A．O(0)B．O(1)C．O(n)D．O(n2)32．對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為 C。 A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1) 33．線性表（a1,a2, ? ,an）以鏈式方式存儲，訪問第i位置元素的時間復雜度為 C。 A．O(0)B．O(1)C．O(n)D．O(n2) 34．單鏈表中，增加一個頭結(jié)點的目的是為了 C。 A．使單鏈表至少有一個結(jié)點 B．標識表結(jié)點中首結(jié)點的位置 C．方面運算的實現(xiàn) D．說明單鏈表是線性表的鏈式存儲 35．在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是 B。 A．p->next=s；s->next=p->next B． s->next=p->next ；p->next=s;C．p->next=s；p->next=s->next D．p->next=s->next；p->next=s 36．線性表的順序存儲結(jié)構(gòu)是一種 A。 A．隨機存取的存儲結(jié)構(gòu) B．順序存取的存儲結(jié)構(gòu) C．索引存取的存儲結(jié)構(gòu) D．Hash存取的存儲結(jié)構(gòu) 37．棧的特點是 B，隊列的特點是 A。A．先進先出 B．先進后出 38．棧和隊列的共同點是 C。 A．都是先進后出 B．都是先進先出 C．只允許在端點處插入和刪除元素 D．沒有共同點 39．一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C。A．edcba B．decba C．dceab D．a(chǎn)bcde 40．設(shè)有一個棧，元素依次進棧的順序為A、B、C、D、E。下列 C 是不可能的出棧序列。A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A 41．以下 B 不是隊列的基本運算？ A．從隊尾插入一個新元素 B．從隊列中刪除第i個元素 C．判斷一個隊列是否為空 D．讀取隊頭元素的值 42．若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，?，pn，若p1＝n，則pi為 C。 A．i B．n－i C．n－i＋1 D．不確定 43．判定一個順序棧st（最多元素為MaxSize）為空的條件是 B。A．st->top!=-1 B．st->top ==-1 C．st->top!= MaxSize D． st->top == MaxSize 44．判定一個順序棧st（最多元素為MaxSize）為滿的條件是 D。A．st->top!=-1 B．st->top ==-1 C．st->top!= MaxSize D．st->top == MaxSize 45．一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是 B。A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 46．判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是 C。 A．qu->rear – qu->front ==MaxSize B．qu->rear – qu->front-1==MaxSize C．qu->rear ==qu->front D． qu->rear =qu->front-1 47．在循環(huán)隊列中，若front與rear 分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是 C。 A．front==rear+1 B．rear==front+1 C．front==rear D．front==0 48．向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)執(zhí)行 D 操作。A．h->next=s;B．s->next=h;C．s->next=h;h =s;D．s->next=h->next;h->next=s; 49．輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為 B。 A．push，pop，push，pop，push，pop B．push，push，push，pop，pop，pop C．push，push，pop，pop，push，pop D．push，pop，push，push，pop，pop 50．若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1 m]，top[1]、top[2]分別代表第1和第2個棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是 B。 A．|top[2]-top[1]|=0 B． top[1]+1=top[2] C．top[1]+top[2]=m D．top[1]=top[2] 51．設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲結(jié)構(gòu) B．隊列 C．線性表的鏈式存儲結(jié)構(gòu) D．棧 52．允許對隊列進行的操作有 D。 A．對隊列中的元素排序 B．取出最近進隊的元素 C．在隊頭元素之前插入元素 D．刪除隊頭元素 53．對于循環(huán)隊列 D。 A．無法判斷隊列是否為空 B．無法判斷隊列是否為滿 C．隊列不可能滿 D．以上說法都不對 54．若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 B。 A．1和5 B．2和4 C．4和2 D．5和1 55．隊列的“先進先出”特性是指 D。 A．最早插入隊列中的元素總是最后被刪除 B．當同時進行插入、刪除操作時，總是插入操作優(yōu)先 C．每當有刪除操作時，總是要先做一次插入操作 D．每次從隊列中刪除的總是最早插入的元素 56．和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是 A。 A．通常不會出現(xiàn)棧滿的情況 B． 通常不會出現(xiàn)棧空的情況 C．插入操作更容易實現(xiàn) D．刪除操作更容易實現(xiàn) 57．用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進行出隊操作時 C。 A．僅修改隊頭指針 B．僅修改隊尾指針 C．隊頭、隊尾指針都可能要修改 D．隊頭、隊尾指針都要修改 58．若串S=‘software’，其子串的數(shù)目是 B。 A．8 B．37 C．36 D．9 59．串的長度是指 B。 A．串中所含不同字母的個數(shù) B．串中所含字符的個數(shù) C．串中所含不同字符的個數(shù) D．串中所含非空格字符的個數(shù) 60．串是一種特殊的線性表，其特殊性體現(xiàn)在 B。A．可以順序存儲 B．數(shù)據(jù)元素是一個字符 C．可以鏈式存儲 D．數(shù)據(jù)元素可以是多個字符 61．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為 B。A．連接 B． 模式匹配 C．求子串 D．求串長 62．數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始地址為 C。A．SA＋141 B． SA＋144 C．SA＋222 D．SA＋225 63．數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始地址為 C。A．SA＋141 B． SA＋180 C．SA＋222 D．SA＋225 64．若聲明一個浮點數(shù)數(shù)組如下： froat average[]=new float[30];假設(shè)該數(shù)組的內(nèi)存起始位置為200，average[15]的內(nèi)存地址是 C。A．214 B．215 C．260 D．256 65．設(shè)二維數(shù)組A[1? m,1? n]按行存儲在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為 A。 A．n*(i-1)+j B． n*(i-1)+j-1 C．i*(j-1)D．j*m+i-1 66．有一個100×90的稀疏矩陣，非0元素有10，設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是 B。 A．20 B． 66 C．18 000 D．33 67．數(shù)組A[0 ? 4，-1 ?-3，5 ?7]中含有的元素個數(shù)是 A。A．55 B． 45 C．36 D．16 68．對矩陣進行壓縮存儲是為了 D。 A．方便運算 B． 方便存儲 C．提高運算速度 D．減少存儲空間 69．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a1，1為第一個元素，其存儲地址為1，每個元素占1個地址空間，則a8，5的地址為 B。A．13 B． 33 C．18 D．40 70．稀疏矩陣一般的壓縮存儲方式有兩種，即 C。A．二維數(shù)組和三維數(shù)組 B． 三元組和散列 C．三元組和十字鏈表 D． 散列和十字鏈表 71．樹最適合用來表示 C。 A．有序數(shù)據(jù)元素 B．無序數(shù)據(jù)元素 C．元素之間具有分支層次關(guān)系的數(shù)據(jù) D．元素之間無聯(lián)系的數(shù)據(jù) 72．深度為5的二叉樹至多有 C 個結(jié)點。A．16 B． 32 C． 31 C． 10 73．對一個滿二叉樹，m個葉子，n個結(jié)點，深度為h，則 D。 hA．n = h+m B h+m = 2n C m = h-1 D n = 2-1 74．任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序 A。A．不發(fā)生改變 B．發(fā)生改變 C．不能確定 D．以上都不對 75．在線索化樹中，每個結(jié)點必須設(shè)置一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標識樹結(jié)構(gòu)信息，1標識線索，對應(yīng)葉結(jié)點的左右鏈域，應(yīng)標識為__ D __。A．00 B．01 C．10 D．11 76．在下述論述中，正確的是 D。 ①只有一個結(jié)點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換； ④深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A．①②③ B．②③④ C．②④ D．①④ 77．設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點的個數(shù)是 A。 A．m-n B．m-n-1 C．n+1 D．不能確定 78．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是 B。 A．9 B．11 C．15 D．不能確定 79．具有10個葉子結(jié)點的二叉樹中有 B 個度為2的結(jié)點。 A．8 B．9 C．10 D．11 80．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 C 倍。A．1/2 B 1 C 2 D 4 81．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 B 倍。A．1/2 B 1 C 2 D 4 82．某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為： C A．3 B．2 C．4 D．5 83．已知一算術(shù)表達式的中綴形式為A＋B *C–D/E，后綴形式為ABC *+DE/–，其前綴形式為 D。 A．–A+B*C/DE B．–A+B*CD/E C –+*ABC/DE D．–+A*BC/DE 84．已知一個圖，如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，a則可能得到的一種頂點序列為____D___；按廣度搜索法進行遍歷，則可能得到的一種頂點序列為___A___； bec①A．a(chǎn)，b，e，c，d，f B．a(chǎn)，c，f，e，b，d C．a(chǎn)，e，b，c，f，d，D．a(chǎn)，e，d，f，c，b df②A．a(chǎn)，b，c，e，d，f B．a(chǎn)，b，c，e，f，d C．a(chǎn)，e，b，c，f，d，D．a(chǎn)，c，f，d，e，b 85．采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的___A____。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷 86．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的___D____。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷 87．具有n 個結(jié)點的連通圖至少有 A 條邊。 A． n-1 B． n C． n(n-1)/2 D． 2n 88．廣義表（（a），a）的表頭是 C，表尾是 C。A．a(chǎn) B（）C（a）D（（a）） 89．廣義表（（a））的表頭是 C，表尾是 B。A．a(chǎn) B（）C（a）D（（a）） 90．順序查找法適合于存儲結(jié)構(gòu)為 B 的線性表。 A 散列存儲 B 順序存儲或鏈式存儲 C 壓縮存儲 D 索引存儲 91．對線性表進行折半查找時，要求線性表必須 B。 A 以順序方式存儲 B 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列 C 以鏈式方式存儲 D 以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列 92．采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為 D。A O(n2)B O(nlog2n)C O(n)D O(log2n) 93．有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查找值為82的結(jié)點時，C 次比較后查找成功。 A． 11 B 5 C 4 D 8 94．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法 B。A 正確 B 錯誤 95．下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是 A。 A B樹和B+樹都能有效的支持順序查找 B B樹和B+樹都能有效的支持隨機查找 C B樹和B+樹都是平衡的多叉樹 D B樹和B+樹都可用于文件索引結(jié)構(gòu) 96．以下說法錯誤的是 B。 A．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址 B．散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。 C．負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。 D．散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。 97．查找效率最高的二叉排序樹是 C。A．所有結(jié)點的左子樹都為空的二叉排序樹。B．所有結(jié)點的右子樹都為空的二叉排序樹。C．平衡二叉樹。 D．沒有左子樹的二叉排序樹。 98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 C。 A．希爾排序 B。冒泡排序 C插入排序 D。選擇排序 99．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是 D。A．希爾排序 B．冒泡排序 C．直接插入排序 D．直接選擇排序 100．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 D 是一個堆。A．94,31,53,23,16,72 B．94,53,31,72,16,23 C．16,53,23,94,31,72 D．16,31,23,94,53,72 101．堆排序是一種 B 排序。 A．插入 B．選擇 C．交換 D．歸并 102． D 在鏈表中進行操作比在順序表中進行操作效率高。A．順序查找 B．折半查找 C．分塊查找 D．插入 103．直接選擇排序的時間復雜度為 D。（n 為元素個數(shù)）A．O（n)B．O(log2n)C．O(nlog2n)D． O(n2) 二、填空題。 1．數(shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu)、樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu)。 2．數(shù)據(jù)的邏輯結(jié)構(gòu)分為 集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 4種。3．在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有 1 個后續(xù)結(jié)點。 4．線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。 5．在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以 任意多個。 6．數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是 順序、鏈式、索引 和 散列 存儲。 7．衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時間復雜度與 空間復雜度。8．評估一個算法的優(yōu)劣，通常從 時間復雜度 和 空間復雜度 兩個方面考察。9．算法的5個重要特性是 有窮性、確定性、可行性、輸入和輸出。10．在一個長度為n的順序表中刪除第i個元素時，需向前移動 n-i-1 個元素。11．在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的 前驅(qū) 結(jié)點。 12．在雙鏈表中，每個結(jié)點有兩個指針域，一個指向 前驅(qū) 結(jié)點，另一個指向 后繼結(jié)點。13．在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動 n 個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與 位置 有關(guān)。 14．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲結(jié)構(gòu)。 15．根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成 單鏈表 和 雙鏈表。16．順序存儲結(jié)構(gòu)是通過 下標 表示元素之間的關(guān)系的；鏈式存儲結(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。 17．帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是 L->next->next=L。 18． 棧 是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循 后進先出 的原則。19．空串是 零個字符的串，其長度等于 零?？瞻状怯梢粋€或多個空格字符組成的串，其長度等于其包含的空格個數(shù)。 20．組成串的數(shù)據(jù)元素只能是 單個字符。 21．一個字符串中 任意個連續(xù)字符構(gòu)成的部分 稱為該串的子串。22．子串 ”str” 在主串 ”datastructure” 中的位置是 5。 23．二維數(shù)組M的每個元素是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要 540個字節(jié)；M的第8列和第5行共占108個字節(jié)。24．稀疏矩陣一般的壓縮存儲方法有兩種，即 三元組表 和 十字鏈表。25．廣義表（（a），（（b），c），（（（d））））的長度是 3，深度是 4。 26．在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2 的結(jié)點的個數(shù)為n2，則有n0＝ n2+1。 27．在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為__n+1__。28．一棵有n個葉子結(jié)點的哈夫曼樹共有__2n-1_個結(jié)點。29．深度為5的二叉樹至多有 31 個結(jié)點。 30．若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為 69。 31．某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為 gdbehfca。32．線索二叉樹的左線索指向其 遍歷序列中的前驅(qū)，右線索指向其遍歷序列中的后繼。33．在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找法。34．在分塊索引查找方法中，首先查找 索引表，然后查找相應(yīng)的 塊表。35．一個無序序列可以通過構(gòu)造一棵 二叉排序 樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。 36．具有10個頂點的無向圖，邊的總數(shù)最多為__45__。 37．已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6__。 v1v2v3v4v5v6∧∧v2v3v6∧v5v5∧v4∧v4v6v3∧ 38．索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址。 39．Prim 算法生成一個最小生成樹每一步選擇都要滿足 邊的總數(shù)不超過n-1，當前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路 三項原則。40．在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有 m 棵子樹，最少有 m/2 棵子樹。 三、判斷題。 1．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（√） 2．抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。(√)3．抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（√） 4．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（×）5．線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（×）6．對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（×）7．順序存儲方式只能用于存儲線性結(jié)構(gòu)。（×）8．集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（×）9．線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（×）10．線性表就是順序存儲的表。（×） 11．取線性表的第i個元素的時間同i的大小有關(guān)。（×）12．循環(huán)鏈表不是線性表。（×） 13．鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。（√） 14．雙向鏈表可隨機訪問任一結(jié)點。（×）15．在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點s插入結(jié)點p的后面 ：p->next = s;s->next = p->next;(×)16．隊列是一種插入和刪除操作分別在表的兩端進行的線性表，是一種先進后出的結(jié)構(gòu)。（×）17.串是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。（×）18．長度為1的串等價于一個字符型常量。(×)19．空串和空白串是相同的。（×） 20．數(shù)組元素的下標值越大，存取時間越長。(×)21．用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。(√)22．一個廣義表的表頭總是一個廣義表。（×）23．一個廣義表的表尾總是一個廣義表。（√） 24．廣義表(((a), b), c)的表頭是((a), b)，表尾是(c)。（√）25．二叉樹的后序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的后面。（√）26．度為2的有序樹是二叉樹。（×） 27．二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（√）28．用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。（×） 29．若已知一棵二叉樹的前序遍歷序列和后序遍歷序列，則可以恢復該二叉樹。（×）30．在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。(×)31．強連通圖的各頂點間均可達。（√）32．對于任意一個圖，從它的某個結(jié)點進行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（×） 33．在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序為穩(wěn)定排序。(√)34．在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。(√)35．拓撲排序是按AOE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進行排序。(×)36．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（×）37．對線性表進行折半查找時，要求線性表必須以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列。（×）38．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址。（√） 39．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。（×） 40．具有n個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。（√） 數(shù) 據(jù) 結(jié) 構(gòu) 課程設(shè)計報告 題 目： 一元多項式計算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學 號： 201201011367 姓 名： 左帥帥 指導老師： 郝慎學 時 間： 一、課程設(shè)計題目分析 本課程設(shè)計要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項式的加法、減法、乘法、除法運算等功能。 二、設(shè)計思路 本程序采用C語言來完成課程設(shè)計。 1、首先，利用順序存儲結(jié)構(gòu)來構(gòu)造兩個存儲多項式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運算分成五個主要的模塊：實現(xiàn)多項式輸入模塊、實現(xiàn)加法的模塊、實現(xiàn)減法的模塊、實現(xiàn)乘法的模塊、實現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實現(xiàn)其功能，盡量減少程序運行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實現(xiàn)對多項式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設(shè)計算法分析 1、相關(guān)函數(shù)說明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈式存儲結(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項式，void Print(Polyn P) 銷毀多項式函數(shù)釋放內(nèi)存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個結(jié)構(gòu)體變量中coef表示每一項前的系數(shù)，expn表示每一項的指數(shù)，polyn為結(jié)點指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對象名。 (2)當用戶輸入兩個一元多項式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數(shù)為m的一元多項式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點 這就建立一元多項式的關(guān)鍵步驟 (3)由于多項式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項式按指數(shù)進行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進行處理，此處由于反復使用指針對各個結(jié)點進行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進行插入操作。(4)加、減、乘、除、的算法實現(xiàn)： 在該程序中，最關(guān)鍵的一步是實現(xiàn)四則運算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負的加法實現(xiàn)；對于乘除算法的大致流程都是：首先建立多項式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實現(xiàn)了多項式計算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計算合并的鏈表逐個結(jié)點依次輸出，便得到整鏈表，也就是最后的計算式計算結(jié)果。由于考慮各個結(jié)點的指數(shù)情況不同，分別進行了判斷處理。 四、程序新點 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺運行時總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。 五、設(shè)計中遇到的問題及解決辦法 首先是，由于此次課程設(shè)計里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進行 4 代碼編寫。 其次是，在寫除法模塊時比較復雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計時的一個經(jīng)驗吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應(yīng)用C語言設(shè)計一元多項式基本計算程序，使我更加鞏固了C語言程序設(shè)計的知識，以前對指針這一點使用是比較模糊，現(xiàn)在通過此次課程設(shè)計對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識的加深。本次的課程設(shè)計，一方面提高了自己獨立思考處理問題的能力；另一方面使自己再設(shè)計開發(fā)程序方面有了一定的小經(jīng)驗和想法，對自己以后學習其他語言程序設(shè)計奠定了一定的基礎(chǔ)。 八、指導老師評語及成績 附錄：（課程設(shè)計代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結(jié)點 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結(jié)點插入 } 7 } //建立一個頭指針為head、項數(shù)為m的一元多項式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點以接收數(shù)據(jù) printf(“請輸入第%d項的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點 } return head;} //銷毀多項式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項數(shù)計數(shù)器 if(!q)//若多項式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項式已空，但b多項式非空 else return 1;//b多項式已空，但a多項式非空 } //求解并建立多項式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當相加系數(shù)為0時，釋放該結(jié)點 } return headc;} //求解并建立多項式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項 } } return hf;} //求解并建立多項式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點,存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點，存儲余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請輸入A(x)的項數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項式B printf(“n”);printf(“**********************************************n”);printf(“* 多項式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項式A(x):“);Print(pa);*n”); printf(“多項式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);}第五篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
點擊咨詢 