第一篇：數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案
、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案
中南大學(xué)現(xiàn)代遠程教育課程考試（專科）復(fù)習(xí)題及參考答案 數(shù)據(jù)結(jié)構(gòu)
一、判斷題：
1． 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。（）2． 鏈?zhǔn)酱鎯υ诓迦撕蛣h除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序。
（）
3． 在只有度為0和度為k的結(jié)點的k叉樹中，設(shè)度為0的結(jié)點有n0個，度為k的結(jié)點有nk個，則有n0=nk+1。（）4． 折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（）5． 如果兩個串含有相同的字符，則這兩個串相等。
（）
6． 數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進行插入、刪除等運算。（）7． 在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄校梢圆辉O(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。（）8． 通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。
（）9． 一個廣義表的表尾總是一個廣義表。
（）10． 當(dāng)從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。
（）
11． 對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復(fù)雜度為O（h）。
（）
12． 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。
（）
13． 直接選擇排序是一種穩(wěn)定的排序方法。
（）14． 閉散列法通常比開散列法時間效率更高。
（）15． 有n個結(jié)點的不同的二叉樹有n!棵。（）16． 直接選擇排序是一種不穩(wěn)定的排序方法。（）17． 在2048個互不相同的關(guān)鍵碼中選擇最小的5個關(guān)鍵碼，用堆排序比用錦標(biāo)賽排序更快。（）18． 當(dāng)3階B_樹中有255個關(guān)鍵碼時,其最大高度(包括失敗結(jié)點層)不超過8。（）19． 一棵3階B_樹是平衡的3路搜索樹,反之,一棵平衡的3路搜索樹是3階非B_樹。（）20． 在用散列表存儲關(guān)鍵碼集合時，可以用雙散列法尋找下一個空桶。在設(shè)計再散列函數(shù)時，要求計算出的值與表的大小m互質(zhì)。（）21． 在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每一塊中元素個數(shù)有關(guān)。（）
22． 在順序表中取出第i個元素所花費的時間與i成正比。
（）23． 在棧滿情況下不能作進棧運算，否則產(chǎn)生“上溢”。
()24． 二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。（）25． 對任意一個圖，從它的某個頂點出
發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.（）26． 二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點的值大于其左孩子的值;若它的右子樹非空，則根結(jié)點的值小于其右孩子的值。（）27． 在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（）
28． 一個有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)一定相等。（）
二、選擇題：
1． 在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復(fù)雜度為（）。A.O(n)
B.O(n／2)
C.O(1)
D.O(n2)2． 帶頭結(jié)點的單鏈表first為空的判定條件是：（）A.first==NULL B.first一>1ink＝＝NULL C.first一>link==first D.first!＝NUlL 3． 當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）。
A.n-2
B.n-l C.n
D.n+1 4． 在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應(yīng)形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的（），在被調(diào)用程序中可直接操縱實際參數(shù)。
A.空間
B.副本 C.返回地址
D.地址
5． 在一棵樹中，（）沒有前驅(qū)結(jié)點。A.分支結(jié)點
D.葉結(jié)點
C.樹根結(jié)點
D.空結(jié)點
6． 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）。
A.2
B.1
C.0
D.-1 7． 對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（）的值除以9。A.20
B.18
C.25
D.22 8． 在有向圖中每個頂點的度等于該頂點的（）。A.入度
B.出度
C.入度與出度之和
D.入度與出度之差
9． 在基于排序碼比較的排序算法中，（）算法的最壞情況下的時間復(fù)雜度不高于O(n10g2n)。A.起泡排序
B.希爾排序
C.歸并排序
D.快速排序
10． 當(dāng)α的值較小時，散列存儲通常比其他存儲方式具有（）的查找速度。A.較慢
B.較快
C.相同
D.不清楚
11． 設(shè)有一個含200個表項的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5，則散列表項應(yīng)能夠至少容納（）個表項。(設(shè)搜索成功的平均搜索長度為Snl＝{1+l／(1一α)}／2，其中α為裝填因子)
A.400
B.526
C.624
D.676
12． 堆是一個鍵值序列{k1,k2,.....kn},對I=1,2,....|_n/2_|,滿足（）A.ki≤k2i≤k2i+1
B.ki 1(2i+1≤n) 13． 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上() A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關(guān)系的有限集合 14． 在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為() A.n-i+1 B.i C.i+1 D.n-i 15． 若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是() A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 16． 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是() A.出隊 B.入隊 C.取隊頭元素 D.取隊尾元素 17． 若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現(xiàn)的出棧序列是() A.2，4，3，1，5，6 B.3，2，4，1，6，5 C.4，3，2，1，5，6 D.2，3，5，1，6，4 18． 字符串通常采用的兩種存儲方式是() A.散列存儲和索引存儲 B.索引存儲和鏈?zhǔn)酱鎯?/p> C.順序存儲和鏈?zhǔn)酱鎯?/p> D.散列存儲和順序存儲 19． 設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進行的無效位移次數(shù)為() A.m B.n-m C.n-m+D.n 20． 二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為() A.429 B.432 C.435 D.438 21． 對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是() A.(e,f) B.((e,f)) C.(f) D.()22． 下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是() 23． n個頂點的強連通圖中至少含有()A.n-1條有向邊 B.n條有向邊 C.n(n-1)/2條有向邊 D.n(n-1)條有向邊 24． 對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結(jié)果為() A.(19，23，56，34，78，67，88，92)B.23，56，78，66，88，92，19，34) C.(19，23，34，56，67，78，88，92) D.(19，23，67，56，34，78，92，88)25． 若在9階B-樹中插入關(guān)鍵字引起結(jié)點分裂，則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為() A.4 B.5 C.8 D.9 26． 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹() A.其形態(tài)不一定相同，但平均查找長度相同 B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同 27． ISAM文件和VSAM文件的區(qū)別之一是() A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進行順序存取，后者只能進行隨機存取 C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu) D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤 28． 下列描述中正確的是（） A． 線性表的邏輯順序與存儲順序總是一致的 B． 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找 C． 數(shù)據(jù)結(jié)構(gòu)實質(zhì)上包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容 D． 選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟 29． 下面程序段的時間復(fù)雜度是（） i=s=0 while(s {i++; s+=i; } A．O(1)B.O(n)C.O(log2n)D.O(n2)30． 對于順序表來說，訪問任一節(jié)點的時間復(fù)雜度是（） A．O(1)B.O(n)C.O(log2n)D.O(n2)31． 在具有n個節(jié)點的雙鏈表中做插入、刪除運算，平均時間復(fù)雜度為（） A．O(1)B.O(n)C.O(log2n)D.O(n2)32． 經(jīng)過下列運算后，QueueFront(Q)的值是（） InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x); A.a B.b C.1 D.2 33． 一個棧的入棧序列是a,b,c，則棧的不可能輸出序列是（） A.acb B.abc C.bca D.cab 34． 循環(huán)隊列是空隊列的條件是（） A．Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 35． 設(shè)s3=“I AM”,s4=“A TERCHER”.則strcmp(s3,s4)=() A.0 B.小于0 C.大于0 D.不確定 36． 一維數(shù)組的元素起始地址loc[6]=1000，元素長度為4，則loc[8]為（） A．1000 B.1004 C.1008 D.8 37． 廣義表（（a,b）,c,d）的表尾是（） A．a(chǎn) B.b C.(a,b)D.(c,d)38． 對于二叉樹來說，第I層上至多有____個節(jié)點（） A．2i B.2i-1 C.2i-1 D.2i-1-1 39． 某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為（） A．BDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA 40． M叉樹中，度為0的節(jié)點數(shù)稱為（） A．根 B.葉 C.祖先 D.子孫 41． 已知一個圖如下所示，若從頂點a出發(fā)按寬度搜索法進行遍歷，則可能得到的一種頂 點序列為（） 42． 堆的形狀是一棵（） A．二叉排序樹 B.滿二叉樹 C.完全二義樹 D.平衡二叉樹 43． 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（） A．希爾排序 B.歸并排序 C.插入排序 D.選擇排序 44． 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（） A．n B.n/2 C.(n+1)/2 D.（n-1)/2 45． 散列查找是由鍵值______確定散列表中的位置，進行存儲或查找（） A．散列函數(shù)值 B.本身 C.平方 D.相反數(shù) 46． 順序文件的缺點是（） A．不利于修改 B.讀取速度慢 C.只能寫不能讀 D.寫文件慢 47． 索引文件的檢索方式是直接存取或按_____存取（） A．隨機存取 B.關(guān)鍵字 C.間接 D.散列 48． 堆是一個鍵值序列{k1,k2,.....kn},對i=1,2,....|_n/2_|,滿足（） A.ki≤k2i≤k2i+1 B.ki C.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i 或ki≤k2i+1(2i+1≤n) 三、計算與算法應(yīng)用題（本大題每小題9分） 1.給定表（119，14，22，1，66，21，83，27，56，13，10） 請按表中元素的順序構(gòu)造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長度。（9分）2.已知一個有向圖的頂點集V和邊集G分別為： V={a,b,c,d,e,f,g,h} E={ 3.設(shè)散列表的長度為13，散列函數(shù)為H（h）= k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。（8分） 0 4.對7個關(guān)鍵字進行快速排序，在最好的情況下僅需進行10次關(guān)鍵字的比較。 (1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結(jié)果的初始關(guān)鍵字序列； (2)對所舉序列進行快速排序，寫出排序過程。（９分）5.如圖所示二叉樹，回答下列問題。（9分） 6.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結(jié)點后的結(jié)果。7.已知一組記錄的排序碼為（46，79，56，38，40，80，95，24），寫出對其進行快速排序的每一次劃分結(jié)果。 8.一個線性表為 B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為 HT[0..12]，散列函數(shù)為 H（key）= key % 13 并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 9.已知一棵二叉樹的前序遍歷的結(jié)果序列是 ABECKFGHIJ，中序遍歷的結(jié)果是 EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。 10.假定對線性表(38，25，74，52，48，65，36)進行散列存儲，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應(yīng)的平均查找長度分別為 和 。11．假定一組記錄的排序碼 為(46，79，56，38，40，80，25，34，57，21)，則對其進行快速排序的第一次劃分后又對左、右兩個子區(qū)間分別進行一次劃分，得到的結(jié)果為：。 12.下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點V1出發(fā)，深度遍歷圖G所得結(jié)點序列為（A），廣度遍歷圖G所得結(jié)點序列為（B）；G的一個拓撲序列是（C）；從結(jié)點V1到結(jié)點V8的最短路徑為（D）；從結(jié)點V1到結(jié)點V8的關(guān)鍵路徑為（E）。其中A、B、C的選擇有： V1,V2,V3,V4,V5,V6,V7,V8 V1,V2,V4,V6,V5,V3,V7,V8 V1,V2,V4,V6,V3,V5,V7,V8 V1,V2,V4,V6,V7,V3,V5,V8 V1,V2,V3,V8,V4,V5,V6,V7 V1,V2,V3,V8,V4,V5,V7,V6 V1,V2,V3,V8,V5,V7,V4,V6 D、E的選擇有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8 13.畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。14.已知如圖所示的有向網(wǎng)，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。 15.假定用于通信的電文由８個字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為５，２５，３，６，１０，１１，３６，４。試為這８個字母設(shè)計不等長Huffman編碼，并給出該電文的總碼數(shù)。 16.已知一棵二叉樹的中序和前序序列如下，試畫出該二叉樹并求該二叉樹的后序序列。（9分）中序序列：c，b，d，e，a，g，i，h，j，f 前序序列：a，b，c，d，e，f，g，h，i，j 17.假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設(shè)計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。 四、算法設(shè)計題 1.已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲結(jié)構(gòu)。請寫一算法，求該二叉樹中葉結(jié)點的個數(shù)。 2.編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結(jié)點的非遞歸算法，若查找item帶回整個結(jié)點的值并返回ture，否則返回false。bool Find（BtreeNode*BST，ElemType&item） 3.編寫算法，將一個結(jié)點類型為 Lnode 的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為 a 1，......a n-1，a n，則逆序鏈接后變?yōu)?, a n，a n-1，......a 1。 4.根據(jù)下面函數(shù)原型，編寫一個遞歸算法，統(tǒng)計并返回以BT為樹根指針的二叉樹中所有 葉子結(jié)點的個數(shù)。int Count(BTreeNode * BT)； 5.設(shè)A=(a1,...,am)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B' ≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A 6.已知單鏈表a和b的元素按值遞增有序排列, 編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。 7.編寫遞歸算法，對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。 8.編寫算法判別T是否為二叉排序樹.9.試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實現(xiàn)。 參考答案 一、判斷題 1．√ 2．× 3．√ 4．× 5．√ 6．√ 7．× 8．× 9．× 11 × 12√ 13 × 14 √ 15 × 16 √ 17 × 18 × 19.× 20.× 21.√ 22.× 23.√ 24.√ 25.× 26.× 27.× 28.√ 二、單項選擇題 1．A 2．B 3．B 4．D 5．C 6．A 7．C 8．C 9．C 10．B 11．A 12 C 13.B 14.D 15.A 16.A 17.D 18.C 19.C 20.A 21.B 22.A 23.B 24.D 25.C C 28.D 29.B 30.A 31.A 32.B 33.D 34.A 35.C 36.C 37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B 48.C 三 計算與算法應(yīng)用題 １．［解答］ 平均長度為4.2、解：畫圖（略） 深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e 廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g 3、解：計算機關(guān)鍵碼得到的散列地址 關(guān)鍵碼 19 14 23 01 68 20 84 27 散列地址 6 10．× 26.B 1 3 7 6 1 在散列表中散列結(jié)果 0 01 68 27 19 20 84 23 4.對n個關(guān)鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準(zhǔn)和其他n-1個關(guān)鍵字比較。 這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)按自己序列完成 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6) (2)搜索成功的平均搜索長度為 l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／12 5．答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca 6.在這個AVL樹中刪除根結(jié)點時有兩種方案: 【方案1】在根的左子樹中沿右鏈走到底,用5遞補根結(jié)點中原來的6,再刪除5所在的結(jié)點.【方案2】在根的右子樹中沿左鏈走到底,用7遞補根結(jié)點中原來的6,再刪除7所在的結(jié)點.7.劃分次序 劃分結(jié)果 一、單項選擇題 （B）1.計算機算法必須具備輸入、輸出和 等5個特性。A)可行性、可移植性和可擴充性 B)可行性、確定性和有窮性 C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wě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)空間復(fù)雜性和時間復(fù)雜性 B)正確性和簡明性 C)可讀性和文檔性 D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 （C）5.計算機算法指的是： A)計算方法 B)排序方法 C)解決問題的有限運算序列 D)調(diào)度方法 6．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（A）和（B）以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的（C），設(shè)計出相應(yīng)的（D），從而確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)是（E）結(jié)構(gòu)類型。供選擇的答案 A.B: 1.理想結(jié)構(gòu) 2.抽象結(jié)構(gòu) 3.物理結(jié)構(gòu) 4邏輯結(jié)構(gòu) C.D.E: 1.運算 2.算法 3.結(jié)構(gòu) 4.規(guī)則 5.現(xiàn)在的 6.原來的 解答：34126 7.（A）是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中被計算機程序加工處理的符號的結(jié)合。（B）是數(shù)據(jù)的基本單位，即數(shù)據(jù)結(jié)合中的個體。有時一個（B）由若干個（C）組成，在這種情況下，稱（B）為記錄。（C）是數(shù)據(jù)的最小單位。（D）是具有相同特性的數(shù)據(jù)元素的集合。（E）是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的結(jié)合。 被計算機加工的數(shù)據(jù)元素不是孤立無關(guān)的，它們彼此之間一般存在著某種聯(lián)系，通常將數(shù)據(jù)元素的這種聯(lián)系關(guān)系稱為（G）。算法的計算量和問題規(guī)模的聯(lián)系用（H）表示。供選擇的答案： A-F: 1.數(shù)據(jù)元素 2.符號 3.記錄 4.文件 5.數(shù)據(jù) 6.數(shù)據(jù)項 7.數(shù)據(jù)對象 8.關(guān)鍵字 9.數(shù)據(jù)結(jié)構(gòu) G: 1.規(guī)則 2.集合 3.結(jié)構(gòu) 4.運算 H: 1.現(xiàn)實性 2.難度 3．復(fù)雜性 4.效率 解答：5167933 二、判斷題 1, 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 解答：錯，因為數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常它是由若干個數(shù)據(jù)項組成，數(shù)據(jù)項才是數(shù)據(jù)的最小單位。 2, 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。解答：正確 3, 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像（或表示）分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。解答：正確 4, 數(shù)據(jù)項是數(shù)據(jù)的基本單位。 解答：錯，因為數(shù)據(jù)元素才是數(shù)據(jù)的基本單位 5, 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)之間的邏輯關(guān)系，是用戶按使用需要而建立的。解答：正確 6, 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。解答：正確 三、簡答題 1、簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。解答： ● 數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。 ● 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。●數(shù)據(jù)項是不可分割的最小單位。 ● 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。● 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。 ● 存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 ● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都有且只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。 ● 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 2、按增長率由小至大的順序排列下列各函數(shù)： 2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)解答： 常見的時間復(fù)雜度按數(shù)量級遞增排列,依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。 先將題中的函數(shù)分成如下幾類： 常數(shù)階：2100 對數(shù)階：lgn K次方階：n0.5、n(3/2) 指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn 注意：(2/3)^n由于底數(shù)小于1，所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下： (2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn 3、試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。解答：略 4、常用的存儲表示方法有哪幾種? 解答：順序和鏈?zhǔn)剑÷?00字 5、設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大? 解答： 6、算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎? 解答：是 第一章 作業(yè) 1.任何計算機系統(tǒng)的主存可以看作是一個一維數(shù)組，多維數(shù)組實際存儲仍是一組連續(xù)單元。請從數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的角度分析? 答：通過一個下標(biāo)計算公式將二維數(shù)組的下標(biāo)(i，j)映成一維數(shù)組的下標(biāo)。例圖b，下標(biāo)=4×(J—l)十I 2.選擇解決某種問題的最佳數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么? 1）算法所需要的時間； ①程序運行時所需輸入的數(shù)據(jù)總量； ②對源程序進行編譯所需的時間； ③計算機執(zhí)行每條指令所需的時間； ④程序中的指令重復(fù)執(zhí)行的次數(shù)（數(shù)據(jù)結(jié)構(gòu)中討論算法時的重點）2）所需的存儲空間量。 3.有一疊撲克脾，在計算機中存儲這一疊撲克牌的內(nèi)容(信息)答：用一個結(jié)點表示一張牌，每張撲克牌的內(nèi)容包括牌的正反面（0、1）、花色（梅花 1、方塊 2、紅心 3、黑桃4）、點數(shù)、名稱、下一張牌 邏輯結(jié)構(gòu)是線性表；存儲結(jié)構(gòu)可以用鏈表或者順序表表示 I=1執(zhí)行n次 4、語句S的執(zhí)行次數(shù)(B) I=2執(zhí)行n-1次 （1）for(i=1;i<=n-1;i++) I=n-1執(zhí)行2次 for(j=n;j>=i;j--)n+(n-1)+………..2 S;(A)n(n+2)/2(B) (n-1)(n+2)/2 (C) n(n+1)/2(D) (n-1)(n+2)(2)I=0; (A) Do{ J=I;Do{ S; J++; }while(j<=n);I++; }while(i<=n);(A)（n+2）(n+1)/2(B) n(n-1)/2 (C) n!(D) n2 5、計算下面程序的時間復(fù)雜度（1）for(i=1;i<=m;i++) （C） for(j=1;j<=n;j++) A[i][j]=i*j;(A) O(m2)(B) O(n2) (C) O(m*n)(D) O(m+n) （2）I=0; （A） s=0;while(s<=n){ I++;S+=I;} (3)語句S的時間復(fù)雜度為O(1)，(D)for(i=1;i<=n-1;i++) for(j=n;j>=i;j--) S;(A)O(n2/2)(B) O((n-1)(n+2)/2) (C) O(n2+n)(D)O(n2) 同題4（1） S=1+2+3。。。。X=n X為執(zhí)行次數(shù) I=0，j 0~n，執(zhí)行n+1次 I=1，j 1~n，執(zhí)行n次 I=n，j n~n，執(zhí)行1次(n+1)+………..1 x(x?1)?n2x2?x?2n?0x??1?1?8n2(A) O(n)(B)O(2n) (C) O(n)(D) O(n2) 6、寫出下面程序的時間復(fù)雜度（1）for(i=1;i<=n,i++) for(j=1;j<=i,j++)for(k=1;k<=j,k++)x+=delta; 1+（1+2）+（1+2+3）…..(1+2+….n) 答：O(n3) (2)i=1;j=0;while(i+j<=n){ if(i>j)j++;else i++; } 答：O(n) 把（i+j）看成整體，每次遞增1，頻率n 數(shù)據(jù)結(jié)構(gòu)試卷 （二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。 (A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn) 2．設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（）。 (A)9(B)10(C)11(D)12 7．設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點。 (A)n-1(B)n(C)n+1(D)2n-1 8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進行一趟快速排序的結(jié)果為（）。 (A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空題(24分)1.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。 2.2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。 typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。5.5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。 6.6.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。 7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。 v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。 三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。 2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。 3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。 4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。 數(shù)據(jù)結(jié)構(gòu)試卷 （二）參考答案 一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空題 1.1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 三、應(yīng)用題 1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 數(shù)據(jù)結(jié)構(gòu)試卷 （三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時間復(fù)雜為（） for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序列為（）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)； 4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。 (A)1(B)n(C)nlog2n(D)n2 5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達到此目的。 (A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。 2.2.設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。 3.3.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。 4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。 5.5.設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點。6.6.設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為_________。 7.7.__________遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。 8.8.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。 9.9.不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。 10.10.設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為____________，右孩子結(jié)點的編號為___________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。 12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。 13.13.下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。 struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} if(_______________________)return(j);else return(-1);} 14.14.下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。 typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。 第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。 二、填空題 1.1.順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 } 數(shù)據(jù)結(jié)構(gòu)試卷 （四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）條有向邊。 (A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。 (A)快速排序(B)冒泡排序(C)希爾排序(D)堆 9．設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空題(42分)1． 1． 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。 2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結(jié)點。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。 6． 6． 設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。 7． 7． 設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當(dāng)前實際存儲________________個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。 8． 8． 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。 10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。 11．11．設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是______________________。 12．12．設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。 13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。 typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i 數(shù)據(jù)結(jié)構(gòu)試卷 （四）參考答案 一、選擇題 1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 二、填空題 1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 數(shù)據(jù)結(jié)構(gòu)試卷 （五）一、選擇題(30分) 1．?dāng)?shù)據(jù)的最小單位是（）。 (A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為（）。 (A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。 (A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。 (A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空題(共30分)1.1.設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。 2.2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是____________________。 3.3.設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。 4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。 5.5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。 6.6.設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為________，有__________個葉子結(jié)點。 7.7.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。 8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。 9.9.下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++) if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1; } return(0);} 三、應(yīng)用題(24分) 1.1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。 3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。 4.4.設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 數(shù)據(jù)結(jié)構(gòu)試卷 （五）參考答案 一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C 二、填空題 1.1.top1+1=top2 2.2.可以隨機訪問到任一個頂點的簡單鏈表 3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度 8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k 三、應(yīng)用題 1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3 數(shù)據(jù)結(jié)構(gòu)試卷 （六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。 (A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。 (A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序 5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結(jié)點(B)高度等于其結(jié)點數(shù) (C)任一結(jié)點無左孩子(D)任一結(jié)點無右孩子 6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）。 (A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結(jié)點。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔槪羔樧兞縮指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（）。 (A)front->next=s；front=s；(B)s->next=rear；rear=s； (C)rear->next=s；rear=s；(D)s->next=front；front=s； 12.設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。 (A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（）。 (A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和 二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（） 2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（） 5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（） 7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（） 9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為_________。 2．設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為__________________________（設(shè)結(jié)點的指針域為next）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_______個結(jié)點數(shù)。 6．設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。 7．設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。 9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。 數(shù)據(jù)結(jié)構(gòu)試卷 （六）參考答案 一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B 二、判斷題 1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對 三、填空題 1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題(30分)1．設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結(jié)點。 (A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。 (A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。 (A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。 (A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷 5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。 (A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。 (A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。 (A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。 3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。 4.4.解決散列表沖突的兩種方法是________________和__________________。 5.5.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有______個。 6.6.高度為h的完全二叉樹中最少有________個結(jié)點，最多有________個結(jié)點。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。 8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。 9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。 10.10.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。 struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t;struct record x=r[s];i=s; while(i while(i while(____________________)i=i+1;if(i } _________________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空題 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 數(shù)據(jù)結(jié)構(gòu)試卷 （八）一、選擇題(30分)1.1.字符串的長度是指（）。 (A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù) (C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。 (A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等 (C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點，2個度數(shù)為2的結(jié)點，2個度數(shù)為3的結(jié)點，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點。 (A)5(B)6(C)7(D)8 9.9.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。 (A)先進先出(B)先進后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。 2． 2． 下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。 5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 6． 完全二叉樹中第5層上最少有__________個結(jié)點，最多有_________個結(jié)點。7． 7． 設(shè)有向圖中不存在有向邊 8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 9． 9． 設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 數(shù)據(jù)結(jié)構(gòu)試卷 （八）參考答案 一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空題 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 簡述蔣經(jīng)國對臺灣發(fā)展的重要貢獻。1969年，60歲的蔣經(jīng)國接任“行政院”副院長，開始接手管理整個政府。1973年，在臺灣社會處于強烈的外交挫折感之際，他宣布提出一項大規(guī)模的經(jīng)濟發(fā)展計劃“十大建設(shè)”等能源、交通和重工業(yè)制造等基礎(chǔ)建設(shè)，以快速地將臺灣推入高度開發(fā)的社會。蔣經(jīng)國在臺灣發(fā)展經(jīng)濟，使臺灣成為亞洲四小龍之一。 蔣經(jīng)國總是強調(diào)，抓人槍斃不能解決問題，而他倡導(dǎo)的包容態(tài)度，更為臺灣奠定了民主改革的基石。面對來自臺灣島內(nèi)人民的不同聲音，他采取了接納、包容的態(tài)度，他愿意承擔(dān)民主改革失敗或成功的所有責(zé)任。1987年7月14日，由蔣經(jīng)國正式簽署發(fā)表，宣布將從7月15日零點起在臺灣地區(qū)“解嚴”，可以稱之為世界戒嚴之最的、持續(xù)38年的“戒嚴令”的就此撤銷。 簡述李登輝上臺后國民黨的三次分裂。李登輝初任“總統(tǒng)”時，重用郝伯村等外省籍大老任“行政院長”及其他重要職位，使外省派對李登輝放松戒心，但李登輝則暗中架空外省派的權(quán)力，到最后李登輝與郝伯村的斗爭明朗化，演變成一場黨內(nèi)的斗爭，造成“新國民黨連線”出走，并創(chuàng)立新黨，郝伯村則為新黨的精神領(lǐng)袖。宋楚瑜成為第一任民選“省長”。不過這第一任也在李登輝運作的“精省”下成了最后一任。宋楚瑜與“省府”系統(tǒng)人士出走，成立親民黨，成為國民黨第二次的分裂。 國民黨的第三次分裂，是李登輝與連戰(zhàn)之爭，連戰(zhàn)可說是李登輝一手提拔，從“行政院長”到“副總統(tǒng)”，但是去年“大選”的失敗，李登輝被黨內(nèi)指責(zé)輔選不力，黯然下臺，連戰(zhàn)則接任失去政權(quán)后的國民黨黨主席。 簡述連戰(zhàn)訪問大陸的意義。 一、連戰(zhàn)借“和平之旅”推動兩岸關(guān)系發(fā)展，爭取島內(nèi)民心，也為個人政治生涯創(chuàng)造歷史。 二、臺當(dāng)局誣蔑“和平之旅”，淡化連戰(zhàn)大陸行的積極意義和對“臺獨”的沖擊，鞏固泛綠選票。 三、連戰(zhàn)訪問大陸將取得重大成果，不僅將建立國共兩黨高層對話機制，建立“黨對黨”的交流對話新渠道，更將對兩岸關(guān)系的發(fā)展起到積極的推動作用。 四、連戰(zhàn)大陸行說明緩和、發(fā)展兩岸關(guān)系仍是島內(nèi)主流民意，更說明大陸“以人為本”的對臺政策深得民心。 簡述臺獨思潮的主要社會根源。“臺獨”思潮是關(guān)于解決臺灣問題的一種政治主張或思想傾向，即謀求將臺灣從中國分離出去，成為一個“獨立國家”。臺獨思潮及臺獨運動是一種非常復(fù)雜的社會政治意識及行動，它的產(chǎn)生有著深刻的社會、歷史、政治及文化的背景。 （一）“臺灣意識”的負面作用被膨脹利用 （二）國民黨的獨裁及其封閉式的反共的大陸政策 （三）經(jīng)濟的畸形發(fā)展與其國際地位的不相稱性 （四）美國對臺的“雙軌政策” （五）李登輝主政后的國民黨主流派日趨“臺獨”化，助長、縱容了臺獨勢力的發(fā)展 簡述臺灣問題的由來、本質(zhì)。中華人民共和國成立后，美國政府原本可以從中國內(nèi)戰(zhàn)的泥潭中拔出來，但它沒有這樣做，而是對新中國采取了孤立、遏制的錯誤政策。它在中國人民積極準(zhǔn)備解放臺灣時，利用朝鮮戰(zhàn)爭爆發(fā)的機會，公然派遣第七艦隊侵入臺灣海峽，阻撓中國人民解放臺灣的正義行動，武裝干涉純屬中國內(nèi)政的海峽兩岸關(guān)系，并通過與臺灣當(dāng)局簽訂所謂“共同防御條約”，將中國領(lǐng)土臺灣置于美國的“保護”之下。美國政府的政策，造成了臺灣當(dāng)局在其庇護下，與大陸軍對峙超過50年。臺灣海峽地區(qū)局勢因之長期緊張，臺灣問題也由此成為中美兩國間的重大爭端 臺灣在第二次世界大戰(zhàn)之后，不僅在法律上而且在事實上已歸還中國。之所以又出現(xiàn)臺灣問題，與隨后中國國民黨發(fā)動的反人民內(nèi)戰(zhàn)有關(guān)，但更重要的是外國勢力的介入。臺灣問題的實質(zhì)是中國的內(nèi)政問題。臺灣問題長期得不到解決，美國政府負有重大責(zé)任。 簡述ECFA協(xié)議對兩岸關(guān)系的影響。兩岸簽署的ECFA協(xié)議，它對于兩岸關(guān)系和平發(fā)展所產(chǎn)生的影響將是深遠而重大的，它標(biāo)志兩岸關(guān)系和平發(fā)展的進程取得了重大歷史性突破。 ①通過ecfa，兩岸互信進一步加強，有利兩岸制度化協(xié)商向縱深推進 ②在一定程度上削弱了“臺獨”的社會根基，提升臺灣民眾對大陸的好感與認同，為未來進行政治協(xié)商不斷累積制度性合作的基礎(chǔ) ③ecfa的簽署不但打破兩岸經(jīng)貿(mào)關(guān)系的隔閡，也使兩岸和平共同發(fā)展更進一步。 一是簽署ECFA是兩岸關(guān)系和平發(fā)展的里程碑。ECFA是兩岸60年以來簽訂的最重要、最復(fù)雜、影響最廣的協(xié)議。島內(nèi)主流媒體一致認為此次協(xié)議對兩岸關(guān)系和平發(fā)展具有“里程碑意義”。 二是兩岸互信進一步加強，有利兩岸制度化協(xié)商向縱深推進。ECFA將為兩岸經(jīng)濟合作制度化奠定良好的基礎(chǔ)，是今后向更深層制度合作的良好開端，對兩岸形成一個有效的區(qū)域經(jīng)濟合作體系和共同市場架構(gòu)具有重要價值。島內(nèi)輿論認為，通過ECFA的簽署將為兩岸關(guān)系開啟“互信協(xié)商”新時代。 三是一定程度削弱“臺獨”社會根基。大陸透過釋放善意與誠意，將提升臺灣民眾對大陸的好感與認同，讓“臺獨”勢力在島內(nèi)造勢的市場進一步受到限制。《聯(lián)合報》評論認為，隨著兩岸關(guān)系進一步緊密，兩岸“化敵為友”的民眾情緒逐漸濃厚，這將使“臺獨”意識形態(tài)“接近破除”。 四是為未來兩岸政治協(xié)商開展積累“和平善因”。ECFA商簽過程為兩岸以協(xié)商方式解決政治問題提供了豐富的成功經(jīng)驗。同時，未來兩岸將進一步密集開展更多的經(jīng)貿(mào)、文化交流，特別是ECFA協(xié)議確定兩岸經(jīng)貿(mào)社團將互設(shè)機構(gòu)，籌設(shè)“兩岸經(jīng)濟合作委員會”等官方、半官方的合作機制，這為未來進行政治協(xié)商不斷累積制度性合作的基礎(chǔ)。 總之，ECFA簽署標(biāo)志著兩岸經(jīng)濟關(guān)系進入一個新階段，對未來兩岸關(guān)系發(fā)展產(chǎn)生深遠影響。正如國臺辦主任王毅所言，ECFA簽訂將“有利于兩岸共同提升經(jīng)濟競爭力，有利于兩岸共同增進廣大民眾福祉，有利于兩岸共同促進中華民族整體利益，有利于兩岸共同應(yīng)對區(qū)域經(jīng)濟一體化的機遇和挑戰(zhàn)”。 論述題： 1.結(jié)合相關(guān)資料，論述兩岸實現(xiàn)“大三通”的重要歷史意義。兩岸實現(xiàn)全面直接雙向三通，是兩岸關(guān)系發(fā)展中一件具有重要歷史意義的事件。“三通”的實現(xiàn)，大大減少了飛行航行兩岸的時間，縮短了路程，節(jié)約了成本，提高了效率，極大的促進了兩岸民眾的相互往來，促進了兩岸各領(lǐng)域的交流和合作，密切了兩岸的經(jīng)貿(mào)關(guān)系，增進了兩岸同胞的福祉，推進了兩岸關(guān)系和平發(fā)展的進程。當(dāng)然隨著“三通”的推進，會不斷地改善，更好地滿足兩岸人民的需求。比如進一步增加航班的問題，因為票價的問題說到底還是一個供求關(guān)系的問題。隨著兩岸關(guān)系迅速的發(fā)展，隨著兩岸三通的深入推進，這些問題都會得到更好的解決。 第一，“三通”是兩岸和平發(fā)展及良性互動的成果，也是兩岸關(guān)系可持續(xù)發(fā)展的保證。且勿論政治上、軍事上的意義，單是經(jīng)濟上、民生上的意義，已使兩岸人民“拍爛手掌”。無論是世界格局或兩岸格局，和平都是主流，都是民眾的要求和期盼。假如以“和平”及“戰(zhàn)爭”給兩岸人民選擇，筆者敢說，除了陳水扁等極端偏激的“臺獨”原教旨主義者，兩岸人民只會選擇和平，絕對拒絕戰(zhàn)爭。臺灣人民不會像陳水扁那樣叫囂“決戰(zhàn)境外”，這是喪心病狂的吹牛之言，以兩岸的總體實力，試問有可能“決戰(zhàn)境外”嗎？阿扁是在“癡人說夢”。只有兩岸保持和平狀態(tài)，才是臺灣長治久安之道。既以和平為圭臬，軍事上已沒有什么大問題。政治上，下一步可能是朝向簽訂和平協(xié)議前進。目標(biāo)明確，但不必著急，更不必強求，只要雙方都有誠意和善意，條件成熟時，水到渠就成。和平，一切從和平出發(fā)，這是兩岸未來關(guān)系發(fā)展的最高準(zhǔn)則，這也是兩岸雙方的共識。 第二，“三通”開始后，兩岸將迎來大交流、大合作、大共融、大發(fā)展的新局面。就兩岸關(guān)系而言，這是半個多世紀(jì)以來前所未有的大時代，甚至是由日據(jù)時代起一個多世紀(jì)以來前所未有的大時代。剛剛開始不久的二十一世紀(jì)，有可能就是臺海兩岸大力發(fā)展經(jīng)濟，并且在國際經(jīng)濟層面大展拳腳的世紀(jì)。世上早就有“二十一世紀(jì)是中國人的世紀(jì)”這一說法。的確，全面實現(xiàn)“三通”后，兩岸關(guān)系的發(fā)展，將向世人展示，對于中國，二十一世紀(jì)是一個大時代的來臨。 第三，兩岸“三通”之后，臺海的形勢肯定不再是“火藥庫”，戰(zhàn)爭的可能性即被極度地淡化，真正符合“中國人不打中國人”這樣一個崇高的目標(biāo)。近六十年來，兩岸關(guān)系有時見好，有時僵持，有時緊張，偶而甚至出現(xiàn)劍拔弩張或擦槍走火的高危情景，國際上因而將臺海形容為“火藥庫”之一，與伊朗及朝鮮的“核武”問題并列。 “三通”之后，兩岸建立軍事互信，對話取代對抗，談判取代對立，和解取代沖突。時機成熟時，兩岸可展開和平協(xié)議的談判，最終必會簽訂，以符兩岸人民的期盼。長遠而言，兩岸將會統(tǒng)一，這也就是馬英九所說的“終極統(tǒng)一”。“大中華經(jīng)濟圈”基礎(chǔ)堅實 第四，在“三通”之中，通商早已在半明半暗中進行，通郵則較少轟轟烈烈的效果，最受人注意的則是通航，包括空運直航和海運直航。這次直航首日，兩岸的空港、海港均有隆重盛大的啟航儀式。例如中臺辦、國臺辦主任王毅在天津港，馬英九在高雄港，分別主持兩岸海運直航儀式。直航的最大意義是省時省成本，體現(xiàn)了兩岸同胞本是一家人。比之于過去的“曲航”，無論是航機或貨輪，均必須經(jīng)香港或日本中轉(zhuǎn)，那是方便多了。 第五，兩岸人民以至全世界的華人，長期以來一直憧憬“大中華經(jīng)濟圈”，這可以說是民族性使然，也是中華民族向心力、凝聚力的表現(xiàn)。大陸和臺灣，無疑是“大中華經(jīng)濟圈”的骨干和支柱。過去很長一段時間，“大中華經(jīng)濟圈”談得多而做得少，非不為也，乃不能也，因兩岸有隔閡，甚至有“獨派”人物蓄意“阻頭阻勢”。“三通”之后，阻路的石頭已經(jīng)搬開，甚至已經(jīng)砸碎，兩岸的合作共融，將成為金融合作、拓展全球經(jīng)貿(mào)的重要平臺，成為實現(xiàn)“大中華經(jīng)濟圈”的堅實基礎(chǔ)。 2.結(jié)合兩岸關(guān)系現(xiàn)狀，綜述2008年馬英九執(zhí)政以來兩岸關(guān)系的發(fā)展變化。馬英九執(zhí)政一年來,兩岸關(guān)系步入和平發(fā)展軌道,取得重大突破。兩岸民眾情感日益加深,島內(nèi)主流民意期盼兩岸和平發(fā)展。未來兩岸關(guān)系必將圍繞經(jīng)濟合作、文化教育交流、民間往來等議題繼續(xù)推進,取得更大進展。 一、兩岸雙方把握歷史契機,努力推動兩岸關(guān)系發(fā)展馬英九上臺后承認“九二共識”、反對“法理臺獨”。3.2012臺灣地區(qū)大選后，臺灣社會走向及兩岸關(guān)系展望。馬英九以近80萬優(yōu)勢的高票后的連任，而這選舉的結(jié)果是為維護兩岸關(guān)系前四年和平發(fā)展的成果，并確保今后四年沿著和平發(fā)展的道路繼續(xù)前進，爭取到了寶貴的先機。毫無疑問，兩岸執(zhí)政當(dāng)局應(yīng)抓住機遇，從政治、文化、經(jīng)濟和社會層面障礙深入交流，這樣必然會推動兩岸關(guān)系朝著更加緊密關(guān)系邁進。政治互信會更加鞏固。在經(jīng)濟方面，會有更加緊密的聯(lián)系。在文化方面，兩岸文化本屬同源，也共同繼承中華文化及歷史情感。未來四年兩岸的文化交流不僅指現(xiàn)有的民間各項交流應(yīng)繼續(xù)，每年一次的兩岸大型經(jīng)貿(mào)文化論壇和海峽論壇應(yīng)照常舉辦，還會在制度化、機制化、正常化上有所突破。 4.綜論臺灣民主化的歷程 形成：1949年國民黨敗退到了臺灣。為了穩(wěn)固統(tǒng)治，臺灣一直實行“軍事戒嚴”，國民黨在臺灣施行的是專制統(tǒng)治。從1960年知識分子主導(dǎo)的“自由中國”到1971年大眾參與的“保釣運動”，從1979黨外人士與國民黨政府抗?fàn)幍摹懊利悕u事件”到美國影響下的“江南案”，從1986年民進黨成立到1987年7月14日年蔣經(jīng)國宣布正式取消持續(xù)了38年的“戒嚴令”，象征著臺灣正式進入了一個自由民主的社會。 原因：臺灣民主化的發(fā)生，有兩個重要的原因，一是臺灣社會面對的內(nèi)外變化，二是臺灣領(lǐng)導(dǎo)人的決斷。 （首先是臺灣社會的發(fā)展，給了國民黨政府很大的壓力。當(dāng)臺灣的經(jīng)濟在70年代取得大發(fā)展的同時，臺灣的中產(chǎn)階級也成長起來，同時臺灣也逐漸開始對外開放，大量的人走出臺灣，了解世界。在這種情況下，臺灣社會內(nèi)部要求言論自由、結(jié)社自由，要求民主的呼聲在不斷加大。社會要求開放公眾政治參與之路，讓公民進行政治參與，而不是國民黨壟斷權(quán)力。社會各界辦的各種各樣的媒體不斷涌現(xiàn)，隨封隨開，政府無法禁止；非政府組織也大量出現(xiàn)。與此同時，國際形勢發(fā)生了巨大的變化，中國大陸進入聯(lián)合國，臺灣退出聯(lián)合國，引起臺灣內(nèi)部巨大的震動；中國大陸從70年代末實行的改革開放政策帶來了國際大格局的轉(zhuǎn)變，對臺灣帶來更為巨大的外來壓力。） 這些內(nèi)外壓力，形成了對國民黨政府的巨大挑戰(zhàn)，迫使臺灣地區(qū)領(lǐng)導(dǎo)人經(jīng)過再三考慮，終于在1987年果斷地宣布解除戒嚴，順應(yīng)民意，開放媒體和社會空間，并開放臺灣民眾到大陸探親訪問。 發(fā)展：雖然臺灣1987年“解嚴”，標(biāo)志著臺灣從此進入一個自由的社會。但選舉制度的完善還有很長的路要走：1990年，萬年國代取消；1994年，省市長直選；1996年，“總統(tǒng)”直選。2000年，陳水扁勝選，民進黨執(zhí)政，臺灣首次通過民主的方式完成政黨輪替；2004年，兩顆子彈讓陳水扁轉(zhuǎn)敗為勝，讓我們看到了民主帶來的亂象；臺灣民主混亂的一面，統(tǒng)獨、族群、省籍均成操縱民意的手段，而經(jīng)濟凋零、貪腐橫行。一個成功的反對黨不一定能同樣成為一個成功的執(zhí)政黨。 2008年，馬英九勝選，曾經(jīng)的威權(quán)政黨又通過民主的方式卷土重來，臺灣民主，也一步步走向成熟。臺灣民主開始走向成熟： 一、臺灣選民抵制住煽動和誘惑，表現(xiàn)出了成熟和理性，讓全球華人對民主有了信心。 二、一個威權(quán)的政黨因推行民主失去政權(quán)之后，在民主的浴火中完成自身鳳凰涅磐，再次卷土重來。 （臺灣開放民主的道路也逐漸引起了國民黨內(nèi)部的變化。蔣經(jīng)國去世以后，對于臺灣民主的走向，在國民黨內(nèi)部形成了委任直選和公民直選兩大派的爭論，導(dǎo)致第一次國民黨的分裂，新黨出走，并成為一個有實力的反對黨。臺灣的民主化最終導(dǎo)致領(lǐng)導(dǎo)人的全民直接選舉。1996年，臺灣進行了有史以來的第一次全民大選。如果從理解民主最主要的內(nèi)容是選舉來看的話，這就是臺灣民主的真正開始。在1996年的選舉中，雖然面對各路人馬的競爭，國民黨還是輕易取得了勝利，繼續(xù)執(zhí)政。但是在2000年的大選中，執(zhí)政的國民黨內(nèi)部發(fā)生分裂。當(dāng)時，宋楚瑜和國民黨領(lǐng)導(dǎo)人鬧翻，結(jié)果以獨立候選人身份參選。宋楚瑜的參選再次分裂了國民黨，分散了國民黨的支持票，結(jié)果民進黨候選人陳水扁贏得了大選的勝利，當(dāng)時陳水扁的得票率只有39.3%。在2004年的選舉中，國民黨和其它泛藍力量進行整合，由連戰(zhàn)和宋楚瑜聯(lián)袂出馬競選，本來大有希望贏得選舉的勝利，但是或許是由于選舉中出現(xiàn)的“兩顆子彈”事件，使得民進黨以微弱多數(shù)再次贏得選舉勝利。一直到2008年，馬英九和蕭萬長再次統(tǒng)合泛藍力量，才奪回了丟失8年之久的臺灣政權(quán)） 一、選擇題（每小題2分，共30分）1.數(shù)據(jù)結(jié)構(gòu)是（D）。 A．一種數(shù)據(jù)類型 B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu) C．一組性質(zhì)相同的數(shù)據(jù)元素的集合 D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 2．以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（D）。 A．鏈隊列 B.鏈表 C.順序表 D.棧 3．以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu) A．樹 B．字符串 C．隊 D．棧 4．一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（B）。 A．98 B．100 C．102 D．106 5．在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（D）。A．插入 B．刪除 C．排序 D．查找 6．線性表采用鏈?zhǔn)酱鎯r，其地址(D)。 A．必須是連續(xù)的 B．一定是不連續(xù)的 C．部分地址必須連續(xù) D．連續(xù)與否均可以 7．線性表是(A)。 A．一個有限序列，可以為空 B．一個有限序列，不可以為空 C．一個無限序列，可以為空 D．一個無限序列，不可以為空 8．若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現(xiàn)的出棧序列為（B）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 9.若一個棧的輸人序列是1，2，3，…，n，輸出序列的第一個元素是n，則第k個輸出元素是（C）。 A．k B．n-k-1 C．n-k+1 D．不確定 10.對于隊列操作數(shù)據(jù)的原則是（A）。 A.先進先出 B.后進先出 C.先進后出 D.不分順序 11.棧和隊列的共同點是（C）。 A.都是先進先出 B.都是先進后出 C.只允許在端點處插入和刪除元素 D.沒有共同點 12．在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結(jié)點的操作是（A）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13.空串與空格串（B）。 A．相同 B．不相同 C．可能相同 D．無法確定 14.串與普通的線性表相比較，它的特殊性體現(xiàn)在（C）。A．順序的存儲結(jié)構(gòu) B．鏈接的存儲結(jié)構(gòu) C．?dāng)?shù)據(jù)元素是一個字符 D．?dāng)?shù)據(jù)元素可以任意 15.串的長度是指（B）。 A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù) C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù) 二、填空題（每空2分，共20分） 1． 線性表、棧和隊列，串都是__線性_____結(jié)構(gòu)。2． 數(shù)據(jù)的基本單位是__數(shù)據(jù)元素_______________。 3． 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_順序______存儲結(jié)構(gòu)。4． 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單元，第一個元素的地址為Loc(a1)，那么，第i個元素的存儲地址Loc(ai)= Loc(a1)+(i-1)*k。5． 棧（stack）是限定在表尾進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為__棧頂________，而另一端稱為_棧底________。6． 一個循環(huán)隊列Q中，頭指針和尾指針分別為Q.front和Q.rear，且最大隊列長度為MaxQSize，則判斷隊空的條件為 Q.rear==Q.front,判斷隊滿的條件為(Q.rear+1)%MaxQSize==Q.front。隊列的長度為(.rear-Q.front+MaxQSize)%MaxQSize 7． 兩個串相等的充分必要條件是 兩個串的長度相等，且各個對應(yīng)位置的字符都相等。 三、程序填空題（每空3分，共30分） 1.在帶頭結(jié)點的單鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。 typedef struct node {int data； struct node *next； }linknode,*link； int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0； while(p && j < i-1){ p=p->next ； ++j； } // 尋找第i-1個結(jié)點 if(!p || j > i-1)return 0； s=(link)malloc(sizeof(linknode))；// 生成新結(jié)點s s->data = e； s->next=p->next ； p->next = s； // 插入L中 return 1； } 2.對順序棧的C語言描述算法如下，其中top為棧頂指針，請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，插入元素e為新的棧頂元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack; int Push(SqStack &S, char e){ // if((s.top-s.base)>=s.stacksize)//棧滿，追加存儲空間 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0； S.top = s.base+s.stacksize ； //修改棧頂指針 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； } 3.對鏈隊列的C語言描述算法如下，請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，刪除隊列Q 的隊頭元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr； typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue； int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p； if(Q.front==Q.rear)retrun 0；//隊列空，返回 p = Q.front-> next； e = p->data； Q.front-> next=p->next；//修改指針 if(Q.rear==p)Q.rear= Q.front ； //隊列只有一個元素的情況 free(p)；//釋放結(jié)點空間 return 1； } 三、算法設(shè)計與分析題（每題10分，共20分） 1、簡述下列算法實現(xiàn)的功能：（每題5分，共10分）（1）typedef struct LNode{ Char data; struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是無頭結(jié)點單鏈表 LNode *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;}// Demo 答：將單鏈表的第一個結(jié)點刪除，放到鏈尾。 ——————————————————————————————————————————————————— （2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize; } Stack;void Demo1(Stack &S, int m){ Stack T;int i; InitStack(T);//初始化棧 while(!StackEmpty(S))//判斷棧是否為空 if((i=Pop(S))!=m)Push(T,i);//入棧操作 while(!StackEmpty(T)) { i=Pop(T);//出棧操作 Push(S,i); } } 答：刪除棧S中所有值為m的數(shù)據(jù)元素 2.有一個帶頭結(jié)點的單鏈表，頭指針為head，編寫一個算法計算所有數(shù)據(jù)域為X的結(jié)點的個數(shù)（不包括頭結(jié)點）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;}第二篇：數(shù)據(jù)結(jié)構(gòu)(Java)復(fù)習(xí)題及答案 1緒論
第三篇：數(shù)據(jù)結(jié)構(gòu)試題及答案
第四篇：2012復(fù)習(xí)題答案
第五篇：數(shù)據(jù)結(jié)構(gòu)期中試卷及答案
點擊咨詢 