數(shù)據(jù)結(jié)構(gòu)模擬試卷及參考答案

數(shù)據(jù)結(jié)構(gòu)模擬試卷(一)及參考答案單項選擇題（本大題共15小題，每小題2分，共30分）1．如果只想得到1024個元素組成的序列中的前5個最小元素，那么用(A)方法最快。A、起泡排序B、快速排序C、堆排序D、直接選擇排序2．算法分析的目的是（B）A．辨別數(shù)據(jù)結(jié)構(gòu)的合理性B．評價算法的效率C．研究算法中輸入與輸出的關(guān)系D．鑒別算法的可讀性3．在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（C）A．插入 B．刪除C．定位 D．排序4．若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現(xiàn)的出棧序列為（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．設串sl=″DataStructureswithJava″,s2=″it″，則子串定位函數(shù)index(s1,s2)的值為（A）A．15 B．16 C．17 D．186．一個順序存儲的線性表的第一個元素的存儲地址是100，每個元素的長度為4，則第4個元素的存儲地址是（B）。A.108B.112C.116D.1207．從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點，在查找成功的情況下，平均需要比較（C）個結(jié)點。A.nB.n/2C.(n+1)/2D.(n-1)/28．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（D）A．不一定相同 B．互為逆序C．都不相同 D．都相同9．高度為5的二叉樹至多有結(jié)點數(shù)為（A）A.63B.32C.24D.6410．若用鄰接矩陣表示一個有向圖，則其中每一列包含的″1″的個數(shù)為（B）A．圖中每個頂點的出度 B．圖中每個頂點的入度C．圖中弧的條數(shù) D．圖中連通分量的數(shù)目11．圖的鄰接矩陣表示法適用于表示（C）A．無向圖 B．有向圖 C．稠密圖 D．稀疏圖12．在一個單鏈表中，若p所指的結(jié)點不是最后一個結(jié)點，在p之后插入s所指的結(jié)點，則執(zhí)行（D）。A.s->next=p;p->next=sB.p-next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->next;p->next=s13．下列排序算法中，其時間復雜度和記錄的初始排列無關(guān)的是（A）A．直接選擇排序 B．插入排序C．快速排序 D．冒泡排序14．若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過程中，先后進行比較的關(guān)鍵字依次為（B）A．f,d,b B．f,c,b C．g,c,b D．g,d,b15．如下圖所示的4棵二叉樹中，（C）不是完全二叉樹。ABCDABCD填空題（本大題共15小題，每小題2分，共30分）在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分線性結(jié)構(gòu)和非線性結(jié)構(gòu)。稱算法的時間復雜度為O(f(n))，其含義是指算法的執(zhí)行時間和___f(n)____的數(shù)量級相同。在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點的時間復雜度為_____O(n)____。假設為循環(huán)隊列分配的向量空間為Q[20]，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為__10____。對于棧只能在___棧頂_____插入和刪除元素。通常從正確性、____可使用性___、可讀性、效率和健壯性等5個方面評價算法（包括程序）的質(zhì)量。在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。若對關(guān)鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為3的希爾排序，則得到的結(jié)果為(15,02,21,24,26,57,43,66,80,48,73)。在索引存儲中，若一個索引項對應數(shù)據(jù)對象表中的一個表項（記錄），則稱此索引為稠密索引，若對應數(shù)據(jù)對象表中的若干個表項，則稱此索引為稀疏索引。二叉樹中度為0的結(jié)點數(shù)為30，度為1的結(jié)點數(shù)為30，總結(jié)點數(shù)為89。廣義表A((a，b，c)，(d，e，f))的表尾為（(d，e，f)）。設有一個順序棧S，元素sl，s2，s3，s4，s5，s6依次進棧，如果6個元素的出棧順序為s2，s3，s4，s6，s5，sl，則順序棧的容量至少應為3。根據(jù)一組記錄(56，42，50，64，48)依次插入結(jié)點生成一棵AVL樹(高度平衡的二叉搜索樹)時，當插人到值為50的結(jié)點時需要進行旋轉(zhuǎn)調(diào)整。n（n＞0）個頂點的無向圖最多有n(n-1)／2條邊。設無向圖的鄰接表如下圖所示，則該圖的邊的數(shù)目是5。判斷題(本大題共10小題，每小題1分，共10分)（×）鏈式存儲在插人和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序。（√）在用循環(huán)單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。（×）通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。（√）一個廣義表的表尾總是一個廣義表。（×）對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O（h）。（√）當從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（×）存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（√）進行折半搜索的表必須是順序存儲的有序表。（×）直接選擇排序是一種穩(wěn)定的排序方法。（×）在用單鏈表表示的鏈式隊列中，隊頭在鏈表的鏈尾位置。問答題(本大題共5小題，每小題6分，共30分)1．由如圖所示的二叉樹，回答以下問題。a.其中序遍歷序列為dgbaechif。b.其先序遍歷序列為abdgcefhi。c.其后序遍歷序列為gdbeihfca。aadcbefghi2．已知圖G=(V,E)，其中V＝{a,b,c,d,e,f,g}，E＝｛<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f>｝，請畫出圖G，并寫出其鄰接矩陣和鄰接表表示。aabcgfedabcdefg鄰接矩陣：abcdefg100001000001100000010010100001000001100000010010001000000100011010abcdefg010123456abcdefg16Λ6Λ1Λ25Λ3Λ04Λ235Λ3．寫出利用直接選擇排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20)進行從小到大排序的每一趟結(jié)果。參考答案：18,24,80,39,43,40,2018,20,80,39,43,40,2418,20,24,39,43,40,8018,20,24,39,43,40,8018,20,24,39,40,43,8018,20,24,39,40,43,804．設A、B、C是不同的關(guān)鍵字且A>B>C，可組成6種不同的輸入順序。問其中哪幾種輸入順序所構(gòu)造的二叉排序樹的高度為2?參考答案：4種。ABCACBCABCBA評分標準：次序不限，寫對一種得1分，4種全寫對得6分。若在4種正確答案之外，又多寫一種則只能得4分，若6種排列順序全寫上則0分。5．在如圖所示的AOE網(wǎng)中，試回答如下問題：（1）計算出每個頂點所表示的事件的最早發(fā)生時間和最遲發(fā)生時間；（2）計算出每條邊所表示的活動的最早開始時間和最遲開始時間；（3）找出此網(wǎng)絡中的關(guān)鍵活動和關(guān)鍵路徑。664521187244abcehgkdf 事件的最早發(fā)生時間和最遲發(fā)生時間： 活動的最早開始時間和最遲開始時間：網(wǎng)絡中的關(guān)鍵活動：ab,be,eh,hk關(guān)鍵路徑:aàbàeàhàk數(shù)據(jù)結(jié)構(gòu)模擬試卷(二)單項選擇題（每小題2分，共30分）1.線性結(jié)構(gòu)的邏輯特征是除第一個節(jié)點和最后一個節(jié)點，其它節(jié)點都有。A．一個直接前趨和一個直接后繼B．多個直接前趨和一個直接后繼C．一個直接前趨和多個直接后繼D．多個直接前趨和多個直接后繼算法必須具備輸入、輸出和。A．計算方法B．排序方法C．解決問題的有限運算步驟D．程式序設計方法3.將遞歸過程轉(zhuǎn)化為非遞歸過程需用到。A．棧B．隊C．線性表D．鏈表4.在順序表上做增、刪節(jié)點運算的平均時間復雜度是。A．O(1)B．O(n)C．O(log2n)D．O(n2)5.設二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先順序存儲，則元素A[i][j]的地址為。A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)C．LOC(A[0][0])+[(i-1)*n+j-1]D．LOC(A[0][0])+[(i-1)*m+j-1]設目標串T=“aababbadbbaa”，模式P=“bba”，則該模式匹配的有效位移為。A.4B.5C.7 D.107.把長度為m的單鏈表接在長度為n的單鏈表之后的算法的時間復雜度為。A．O(m)B．O(n)C．O(m+n)D．O(1)在一個單鏈表中，若P所指節(jié)點不是最后節(jié)點，在P之后插入S所指節(jié)點，則執(zhí)行。A．S->next=P->next;P->next=S;B．P->next=S->next;S->next=P;C．S->next=P;P->next=S;D．P->next=S;S->next=P;9.設將整數(shù)1,2,3,4,5依次進棧，最后都出棧，出?？梢栽谌魏螘r刻（只要棧不空）進行，則出棧序列不可能是。A．23415B．54132C．23145D．1543210.循環(huán)隊列是空隊列的條件是。A．Q->rear==Q->frontB．(Q->rear+1)%maxsize==Q->frontC．Q->rear==0D．Q->front==011.設有一廣義表E=（a,b,(c,d)），其長度為。A．2B．3C．4D．512.某二叉樹的前序遍歷序列為ABDEFC，中序遍歷序列為DBEFAC，則后序遍歷序列為。A．DFEBCAB．DBECFAC．BDAECFD．DBEFCA下列哪項不是利用查找表中數(shù)據(jù)元素的關(guān)系進行查找的方法。A．有序表的查找B．二叉排序樹的查找C．平衡二叉樹D．散列查找下述幾種排序方法中，要求內(nèi)存量最大的是。A．插入排序B．快速排序C．歸并排序D．選擇排序在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A．1/2B．1C．2D．4填空題(每空2分，共20分)16．數(shù)據(jù)結(jié)構(gòu)一般包括三個方面內(nèi)容：數(shù)據(jù)的，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算。17．在包含n個結(jié)點的順序表上做等概率插入運算，平均要移動_____個結(jié)點。18．隊列的特性是______。19．已知二叉樹中葉子數(shù)為30，僅有一個孩子的結(jié)點數(shù)為20，則總結(jié)點數(shù)為____。20．_______遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（選填“先序”、“中序”或“后序”）。21．n個節(jié)點的連通圖至少有_________條邊。22．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮，應最好選擇排序。23．帶有一個頭結(jié)點的單鏈表head為空的條件是（假設指針域的名稱為next）_____。24．設一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為___________________。25．在拓撲排序中，拓撲序列的第一個頂點必定是的頂點。簡答題（每題6分，共36分）26．已知一棵樹邊的集合為｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，畫出這棵樹，并回答下列問題：哪個是根結(jié)點？哪些是葉子結(jié)點？哪些是結(jié)點g的祖先？樹的深度是多少？樹的度數(shù)是多少？27．以下面數(shù)據(jù)作為葉子結(jié)點的權(quán)值構(gòu)造一Huffman樹，畫出該樹并計算出其帶權(quán)路徑長度。2，4，5，828．給定關(guān)鍵字集合(45,28,52,20,10,35,40,70,30,75,63,32)，從一棵空的二叉搜索樹開始，按表中元素的次序構(gòu)造一棵二叉搜索樹。畫出從該二叉搜索樹中刪除關(guān)鍵碼28和52后的結(jié)果。29．試畫出下面帶權(quán)無向圖的一棵最小生成樹。95576843297abdcef30．寫出利用希爾排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20,10,90,70)進行從小到大排序的每一趟結(jié)果。（假設gap取值分別為5、3、1）31．設一散列表長為13，采用線性探查法解決沖突。散列函數(shù)h(key)=key%13。（1）畫出在空表中依次插入關(guān)鍵字25,20,36,15,41,52,29,72,67后的散列表。（2）該散列表在等概率查找成功和不成功的平均查找長度。綜合題（共14分）32．試對下圖所示的AOE網(wǎng)絡回答下列問題：這個工程最早可能在什么時間結(jié)束。（2分）求每個活動的最早開始時間e()和最遲開始時間l().（8分）確定哪些活動是關(guān)鍵活動。（4分）652101941512345611652101941512345611數(shù)據(jù)結(jié)構(gòu)模擬試卷(二)參考答案單項選擇題（每小題2分，共30分）1~5ACABB6~10ABABA11~15BADCB填空題(每空2分，共20分)16．數(shù)據(jù)結(jié)構(gòu)一般包括三個方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算。17．在包含n個結(jié)點的順序表上做等概率插入運算，平均要移動__n/2____個結(jié)點。18．隊列的特性是____先進先出__。19．已知二叉樹中葉子數(shù)為30，僅有一個孩子的結(jié)點數(shù)為20，則總結(jié)點數(shù)為__79__。20．______中序_遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（選填“先序”、“中序”或“后序”）。21．n個節(jié)點的連通圖至少有_____n-1____條邊。22．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮，應最好選擇快速排序排序。23．帶有一個頭結(jié)點的單鏈表head為空的條件是（假設指針域的名稱為next）__head->next==NULL___。24．設一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為_______10,13,27,76,65,97,38____________。25．在拓撲排序中，拓撲序列的第一個頂點必定是入度為零的頂點。簡答題（每題6分，共36分）26．已知一棵樹邊的集合為｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，畫出這棵樹，并回答下列問題：哪個是根結(jié)點？哪些是葉子結(jié)點？哪些是結(jié)點g的祖先？樹的深度是多少？樹的度數(shù)是多少？參考答案：根結(jié)點是：a葉子結(jié)點是：difjklg的祖先：ac樹的深度：4樹的度數(shù)：327．以下面數(shù)據(jù)作為葉子結(jié)點的權(quán)值構(gòu)造一Huffman樹，畫出該樹并計算出其帶權(quán)路徑長度。2，4，5，8參考答案：198116425198116425帶權(quán)路徑長度：WPL=(2+4)*3+5*2+8=3628．給定關(guān)鍵字集合(45,28,52,20,10,35,40,70,30,75,63,32)，從一棵空的二叉搜索樹開始，按表中元素的次序構(gòu)造一棵二叉搜索樹。畫出從該二叉搜索樹中刪除關(guān)鍵碼28和52后的結(jié)果。參考答案：(1)(2)（評分標準：每個圖3分）29．試畫出下面帶權(quán)無向圖的一棵最小生成樹。55768432997abdcef參考答案：554326abdcef(對1根線得1分，全對得6分)30．寫出利用希爾排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20,10,90,70)進行從小到大排序的每一趟結(jié)果。（假設gap取值分別為5、3、1）參考答案：Gap=5時18,20,10,39,43,40,24,80,90,70Gap=3時18,20,10,24,43,40,39,80,90,70Gap=1時10,18,20,24,39,40,43,70,80,90(每對1行得2分)31．設一散列表長為13，采用線性探查法解決沖突。散列函數(shù)h(key)=key%13。（1）畫出在空表中依次插入關(guān)鍵字25,20,36,15,41,52,29,72,67后的散列表。（2）該散列表在等概率查找成功和不成功的平均查找長度。參考答案：(1)散列表：（2分）00123456789101112521541296720723625 (2)ASLSUCC=(5*1+3*2+1*4)/9=5/3（2分） ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13（2分）綜合題（共14分）32．試對下圖所示的AOE網(wǎng)絡回答下列問題：這個工程最早可能在什么時間結(jié)束。（2分）求每個活動的最早開始時間e()和最遲開始時間l().（8分）確定哪些活動是關(guān)鍵活動。（4分）652101941512345611652101941512345611數(shù)據(jù)結(jié)構(gòu)模擬試卷(三)單項選擇題（每小題2分，共30分）1．一個非空廣義表的表頭A．一定是子表B.一定是原子C．不能是子表D.可以是原子，也可以是子表2．下列排序算法中時間復雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是A．堆排序B.冒泡排序C．直接選擇排序D.快速排序3．設將整數(shù)1,2,3,4,5依次進棧，最后都出棧，出棧可以在任何時刻（只要棧不空）進行，則出棧序列不可能是A．23415B.15432C．23145D.541324.算法必須具備輸入、輸出和A.計算方法B.排序方法C．解決問題的有限運算步驟D.程序設計方法5．拓撲排序運算只能用于A．帶權(quán)有向圖B.連通無向圖C．有向無環(huán)圖D.無向圖6.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是A.O(1)B.O(n)C.O(n2)D.O(nlogn)7．在一個無向圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的倍A．1/2B.1C.2D.48.設二維數(shù)組A[0..m-1][0..n-1]按行優(yōu)先順序存儲，則元素A[i][j]的地址為A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)LOC(A[0][0])+[(i-1)*n+j-1]D.LOC(A[0][0])+[(i-1)*m+j-1]9．單鏈表的存儲密度A．大于1B.等于1C．小于1D.不能確定10.有n個節(jié)點的順序表中，算法的時間復雜度是O(1)的操作是訪問第i個節(jié)點（1≤i≤n）在第i個節(jié)點后插入一個新節(jié)點（1≤i≤n）刪除第i個節(jié)點（1≤i≤n）將n個節(jié)點從小到大排序11.循環(huán)隊列SQ的存儲空間是數(shù)組d[m]，隊頭、隊尾指針分別是front和rear，則執(zhí)行出隊后其頭指針front值是A．front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m12．下列排序算法中時間復雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是A．堆排序B.冒泡排序C．直接選擇排序D.快速排序13.若要惟一地確定一棵二叉樹，只需知道該二叉樹的A．前序序列B.中序序列C．前序和后序序列D.中序和后序序列14．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是A．希爾排序B.冒泡排序C．插入排序D.選擇排序15．具有n個節(jié)點的完全二叉樹的深度為A．élog2(n+1)ù-1B.log2n+1C.log2nD.?log2n?填空題（每小題2分，共20分）1．數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類，它們是線性結(jié)構(gòu)和。2．在單鏈表中（假設結(jié)點指針域名稱為next），刪除指針P所指結(jié)點的后繼結(jié)點的語句是。3．已知循環(huán)隊列用數(shù)組data[n]存儲元素值，用front,rear分別作為頭尾指針，則當前元素個數(shù)為。4．若n為主串長，m為子串長，則串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)為____。5．廣義表((a),((b),j,(((d)))))的表尾是。6．已知二叉樹有61個葉子節(jié)點，且僅有一個孩子的節(jié)點數(shù)為45，則總節(jié)點數(shù)為。7．解決計算機與打印機之間速度不匹配問題，須要設置一個數(shù)據(jù)緩沖區(qū)，應是一個結(jié)構(gòu)。8．n個頂點e條邊的圖采用鄰接表存儲，深度優(yōu)先遍歷算法的時間復雜度為____________。9．對于n個關(guān)鍵字的集合進行冒泡排序，在最壞情況下所需要的時間為________。10．在一個長度為n的順序表中的第i個元素（1≤i≤n）之前插入一個元素時，需向后移個元素。算法閱讀題（每空2分，共10分）1．設線性表的n個結(jié)點定義為（a0,a1,…,an-1），在順序表上實現(xiàn)的插入和刪除算法如下，請在空白處填入適當內(nèi)容。(順序表的最大可容納項數(shù)為MaxSize)Template<classType>intSeqList<Type>::Insert(Type&x,inti){If(i<0||i>last+1||last==(1))return0;Else{Last++;For(intj=last;j<i;j--)data[j]=(2);(3);Return1;}}Template<classType>intseqList<Type>::Remove(Type&x){inti=Find(x);if(i>=0){last--;for(intj=(4);j<=last;j++)data[j]=(5);return1;}return0;}答題:(1)(2)(3)(4)(5)四、問答題（共40分）1.已知一棵二叉樹的中序序列和序序列分別如下，請寫出它的后序序列。（10分）前序序列： ABDECRGMHK 中序序列：DBEARGCHKM答題:后序序列：2．