數據結構試卷試卷及答案5套

第12頁共13頁PAGE答案參見我的新浪博客：/s/blog_3fb788630100muda.html數據結構試卷試1解釋下列術語（每小題4分，共20分）1.頭指針2.二叉排序樹的定義3.頭結點4.數據的邏輯結構5.排序方法的穩(wěn)定性二、選擇填空（每小題2分，共20分）（在每小題的4個備選答案中，選出一個正確的答案，多選少選均不得分）1.在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時順向后移動()個元素A.n-iB.n-i+1C.n-i-12.某個棧的輸入序列為1，2，3，4，下面的四個序列中()不可能是它的輸出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,23.對二叉排序進行()遍歷可以得到結點的排序序列A.前序B.中序C.后序D.按層次4．有64個結點的完全二叉樹的深度為（）。A8B7C6D55．折半查找法的時間復雜度是()A.(n2)B.O(n)C.O(n㏒n)D.O(㏒n)6．A(1:5,1:6)的每個元素占5個單元，將其按行優(yōu)先次序儲存在起始地址為1000的連續(xù)的內存單元中，則元素A[5，5]的地址為（）。A1140B1145C1120D11257.有n個葉子結點的哈夫曼樹的結點總數為（）。A不確定B2nC2n+1D2n-18.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前遍歷序列是（）。AacbedBdecabCdeabcDcedba9．若循環(huán)隊列用數組A(0:m-1)存放其元素值，已知其頭、尾指針分別是f和r,則當前隊列中的元素個數是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f10.一個二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹（樹中結點個數大于1）。A空或只有一個結點B高度等于其結點數C任一結點無左孩子D任一結點無右孩子判斷題（每小題2分，對的打√，錯的打×，共10分）1．若圖G的最小生成樹不唯一，則G的邊數一定多于n-1，并且權值最小的邊有多條（其中n為G的頂點數）。()2．對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷可訪到該圖的每個頂點。()3．若某二叉樹的葉子結點數為1（樹中只有一個結點的情況除外），則其先序序列和后序序列一定相反。（）4．在隊列中，隊頭指針總是指向第一個數據元素。（）5．線性表的唯一存儲形式是鏈表。（）四，解答題（每小題6分，共24分）從一的平衡二叉樹開始，把關鍵字（5，19，6，22，16，15，30）按出現的先后順序逐一插入，從而構造一棵平衡二叉樹排序樹，每插入一個關鍵字后，若需要進行平衡旋轉，則標明其旋轉類型及旋轉后的結果。滿足下列條件的二叉樹具有什么形狀？前序和中序遍歷次序相同；中序和后序遍歷次序相同；前序和后序遍歷次序相同；寫出所給數據表，采用快速排序方法按升序排序的每一趟的結果：（25，10，20，31，5，28）。具有144個記錄的文件，若采用分塊查找法查找，則分成幾塊最好？每塊的最佳長度是多少？假定每塊的長度是8，確定所在塊、塊中均采用順序查找法查找，則平均查找長度是多少？編寫算法（共16分）寫出，建立一個具有n個頂點的無向網的鄰接矩陣的算法。提示：先將矩陣A的每個元素都初始化成0，然后，讀入邊及數值（i,j,w）,將A的相應元素置成w。（8分）線性表V采用順序存儲結構，試編寫刪除V中的第i個元素起的k個元素的算法。（8分）數據結構試卷試2一、填空題（共20分，每空1分）數據結構是研究數據元素之間抽象化的相互關系和這種關系在計算機中的存儲結構表示，通常有下列四種存儲結構：（1）、（2）、（3）和（4）。評價算法的標準很多，通常是以執(zhí)行算法所需要的（5）和所占用的（6）來判別一個算法的優(yōu)劣。隊列操作的原則是（7），棧的插入和刪除操作在（8）進行。對循環(huán)隊列Q，它的最大存儲空間是MAXSIZE，隊頭指針是front，隊尾指針是rear，采用少用一個存儲單元的方法解決假溢出時，隊滿的判斷條件是（9），隊空的判斷條件是（10）。在以Head為表頭指針的帶有頭結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為（11）和（12）。假設二維數組A[6][8]，每個元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址，已知A的開始存儲位置為100，按行優(yōu)先順序存儲的元素A[2][5]的第一個字節(jié)的地址為（13）。空格串的長度為串中所包含（14）字符的個數，空串的長度為（15）。有向圖G用鄰接矩陣A[n，n]存儲表示，其第i行的所有元素之和等于頂點i的（16）。在關鍵字序列(12，23，34，45，56，67，78，89，91)中折半查找關鍵字為89和25的結點時，所需進行的比較次數分別為（17）和（18）。請說出兩種處理哈希沖突的方法（19）、_（20）_。二、選擇題（共20分，每題2分）對線性表，在下列哪種情況下應采用鏈式存儲結構？（）A．經常需要隨機存取元素B．經常需要進行插入和刪除操作C．表中元素的個數不變D．表中元素需要占據一片連續(xù)的存儲空間從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功情況下，則平均比較（）個結點。A．nB．n/2C．(n-1)/2若對某線性表最常進行的操作是在最后一個元素之后插入和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A．單鏈表B．雙鏈表C．僅有頭指針的單循環(huán)鏈表D．僅有尾指針的單循環(huán)鏈表在一個單鏈表中，若要刪除p指針所指結點的后繼結點，則執(zhí)行（）。A．p->next;p->next=p->next->next；B．p->next=p->next->next；C．p=p->next；D．p=p->next->>next；在具有n個結點的二叉鏈表中，非空的鏈域個數為（）。A．n-1B．nC．n+1D．不確定有64個結點的完全二叉樹的深度為（）（假設根結點的層次為1）。A．8B．7C．6邊遠山區(qū)的那個小村莊，現要為他們建成能互相通信的網，并且總的花費最少，這可以歸結為什么問題（）。A．最短路徑B．關鍵路徑C．拓撲排序D．最小生成樹折半查找法要求查找表中各元素的鍵值必須是（）。A．遞增或遞減B．遞增C．遞減D．無序下列排序算法中，（）算法在進行一趟相應的排序處理結束后不一定能選出一個元素放到其最終位置上。A．直選擇排序B．冒泡排序C．歸并排序D．堆排序對于鍵值序列（2，33，21，18，65，38，7，49，24，86），用篩選法建堆，必須從鍵值為（）的結點開始。A．86B．2C．65三、判斷題（共10分，每題2分）已知指針P指向鏈表L中的某結點，執(zhí)行語句P=P->next不會刪除該鏈表中的結點。()如果一個串中的所有字符均在另一串中出現，則說前者是后者的子串。()若一棵二叉樹的任一非葉結點度均為2，則該二叉樹為滿二叉樹。()任一AOE網中至少有一條關鍵路徑，且是從源點到匯點的路徑中最短的一條。()在采用線性探測法處理沖突的散列表中所有同義詞在表中相鄰。（）四、簡答題（共24分,每題8分）二叉樹的先序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI，畫出這棵二叉樹。輸入一個結點序列{300，100，80，52，40，64，350}，試畫出構造平衡二叉樹的過程，并說明平衡旋轉類型。已知一組記錄的排序碼為（46，79，56，38，40，80，95，24），寫出對其進行快速排序的每一趟排序的結果。五、算法設計題（共16分）試寫一建立單鏈表的算法。（8分）已知一個非空線性鏈表第一個結點的指針為L，請寫一算法，將鏈表中數據域值最大的那個結點移到鏈表最后面。（8分）數據結構試卷試3一、填空（20分，每小題2分）1、若用S[1]~S[m]作為順序棧的存儲空間，棧空的標志是棧頂指針t=m+1，則每進行一次（）操作，需將t的值加1。2、隊列的特征是()。3、在單向鏈表中增加一個表頭節(jié)點的目的是（）。４、3個結點可以構成（）種不同形狀的樹，可以構成（）種不同形狀的二叉樹。５、在平衡二叉排序樹中，每個結點的平衡因子等于（）。６、可以進行拓撲排序的有向圖一定是（）。７、為了實現折半查找，線性表必須采用（）方法存儲。８、若以{4,5,6,7,8}作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是（）９、在排序過程中，任何情況下都不比較排序碼大小的排序方法是（）。二、選擇填空（20分，每小題2分）1、鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（）

存儲方式最省時間。

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶尾指針的單循環(huán)鏈表2、棧和隊列都是()A．順序存儲的線性結構B．鏈式存儲的非線性結構C．限制存取點的線性結構D．限制存取點的非線性結構３、若對有18個元素的有序表作折半查找。則查找A[3]的比較序列的下標為（）。A．1，2，3B．9，5，2，3C．9，4，2，3D．10，5，３，２4、設n，m為某二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是()A．n在m右方B．n是m祖先C．n在m左方D．n是m子孫5、對長度為10的有序表進行折半查找，設在等概率時查找成功的平均查找長度是()A．2.9B．3.1C．3.46、帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中第i()。

A行非∞的元素之和B.列非∞的元素之和

C.行非∞且非0的元素個數D.列非∞且非0的元素個數7.在有n個葉子結點的哈夫曼樹中，其結點總數為()。

A不確定B2nC2n+1D2n-18、任何一個無向連通圖的最小生成樹()。

A只有一棵B有一棵或多棵C一定有多棵D可能不存在9、設有1000個無序的元素，希望用最快的速度挑出其中前10個最大元素，在以下排序方法中用哪一種最好（）。A、選擇排序B、冒泡排序C、堆排序D、快速排序10、直接插入排序在最好情況下的時間復雜度為（）

A.O(logn)

B.O(n)

C.O(n*logn)

D(n2)三、判斷正誤（10分，每小題2分。對得打“√”，錯的打“╳”）1、如果一個串中所有字符均在另一串中出現，則說前者是后者的子串。（）2、（101，88，46，70，34，39，45，58，66，10）是堆。（）3、

哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離很較近。（）4、用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。（）5、在執(zhí)行某個排序算法過程中，出現了排序碼朝著最終排序序列相反的方向移動，從而可以認為該算法時不穩(wěn)定的。（）四、簡答題（35分）１、將關鍵字集合K={60，40，49，23，25，13，95，196，85}，創(chuàng)建平衡二叉排序樹。2、設一數列的順序是1、2、3、4、5、6，通過棧結構能否排成順序為3、2、5、6、4、1的數列？2）能否排成順序為1、5、4、6、2、3的數列？3、一棵共有n個結點的樹，其中所有分枝結點的度均為k，求該樹中葉子結點的個數。4、有關鍵字集合K{37，15，50，01，55，25，84，30，44，24，27，38}，α=0.75，采用除留余數法，解決沖突用線性探測，將K散列到哈希表。給定一組記錄的關鍵詞，其順序是13、7、9、15、8、16、12、4、11、20、10、14，試寫出：用快速排序算法操作時，第一趟結束后的狀態(tài)。用希爾排序算法操作時（逐減增量序列是6、3、2、1），第一趟和第二趟結束后的狀態(tài)。用選擇排序算法操作時，第一趟和第二趟（即選擇最大和次大者送到最后排序位置）結束后的狀態(tài)（兩趟分別寫出）。五、算法（15分）１、寫出一個將二叉樹左、右孩子交換的算法。（7分）２、試寫出一個利用遍歷圖的方法輸出一條無向圖G中從頂點Vi到Vj長度為L的簡單路徑的算法。（8分）數據結構試卷試4一、選擇填空（每小題2分，共20分）（在每小題的4個備選答案中，選出一個正確的答案，多選少選均不得分）1．有64個結點的完全二叉樹的深度為（）。A8B7C6D52．折半查找法的時間復雜度是()A.(n2)B.O(n)C.O(n㏒n)D.O(㏒n)3.在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時順向后移動()個元素A.n-iB.n-i+1C.n-i-14.某個棧的輸入序列為1，2，3，4，下面的四個序列中()不可能是它的輸出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,25.對二叉排序進行()遍歷可以得到結點的排序序列A.前序B.中序C.后序D.按層次6．A(1:5,1:6)的每個元素占5個單元，將其按行優(yōu)先次序儲存在起始地址為1000的連續(xù)的內存單元中，則元素A[5，5]的地址為（）。A1140B1145C1120D11257.有n個葉子結點的哈夫曼樹的結點總數為（）。A不確定B2nC2n+1D2n-18.一個二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹（樹中結點個數大于1）。A空或只有一個結點B高度等于其結點數C任一結點無左孩子D任一結點無右孩子9.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前遍歷序列是（）。AacbedBdecabCdeabcDcedba10．若循環(huán)隊列用數組A(0:m-1)存放其元素值，已知其頭、尾指針分別是f和r,則當前隊列中的元素個數是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f二、判斷題（每小題2分，對的打√，錯的打×，共8分）若某二叉樹的葉子結點數為1（樹中只有一個結點的情況除外），則其先序序列和后序序列一定相反。（）2．對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷可訪到該圖的每個頂點。()3．線性表的唯一存儲形式是鏈表。（）4．在隊列中，隊頭指針總是指向第一個數據元素。（）三、解釋下列術語（每小題5分，共25分）1.關鍵路徑2樹的路徑長度3.頭結點4.數據的存儲結構5.排序方法的穩(wěn)定性四、解答題（每小題6分，共24分）1.滿足下列條件的二叉樹具有什么形狀？前序和中序遍歷次序相同；中序和后序遍歷次序相同；前序和后序遍歷次序相同；2.有一組關鍵字，如果以不同的次序輸入，這時建立起來的二叉排序樹是否相同？當以中序遍序這些二叉排序樹時，其遍序的結果是否相同？為什么？3.具有144個記錄的文件，若采用分塊查找法查找，則分成幾塊最好？每塊的最佳長度是多少？假定每塊的長度是8，確定所在塊、塊中均采用順序查找法查找，則平均查找長度是多少？4.寫出所給數據表，采用快速排序方法按升序排序的每一趟的結果：（25，10，20，31，5，28）。五，編寫算法（共23分）寫出，建立一個具有n個頂點的無向網的鄰接矩陣的算法。提示：先將矩陣A的每個元素都初始化成0，然后，讀入邊及數值（I,j,w）,將A的相應元素置成w.（13分）線性表V采用順序存儲結構，試編寫刪除V中的第i個元素起的k個元素的算法。（10分）數據結構試卷試5一、解釋下列術語（每小題4分，共20分）1.頭指針2.二叉排序樹的定義3.頭結點4.數據的邏輯結構5.排序方法的穩(wěn)定性二、選擇填空（每小題2分，共20分）（在每小題的4個備選答案中，選出一個正確的答案，多選少選均不得分）1.在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時順向后移動()個元素A.n-iB.n-i+1C.n-i-12.某個棧的輸入序列為1，2，3，4，下面的四個序列中()不可能是它的輸出序列A.1,2,3,4B.2,3,4,1C.4,3,2,1D.3,4,1,23.對二叉排序進行()遍歷可以得到結點的排序序列A.前序B.中序C.后序D.按層次4．有64個結點的完全二叉樹的深度為（）。A8B7C6D55．折半查找法的時間復雜度是()A.(n2)B.O(n)C.O(n㏒n)D.O(㏒n)6．A(1:5,1:6)的每個元素占5個單元，將其按行優(yōu)先次序儲存在起始地址為1000的連續(xù)的內存單元中，則元素A[5，5]的地址為（）。A1140B1145C1120D11257.有n個葉子結點的哈夫曼樹的結點總數為（）。A不確定B2nC2n+1D2n-18.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前遍歷序列是（）。AacbedBdecabCdeabcDcedba9．若循環(huán)隊列用數組A(0:m-1)存放其元素值，已知其頭、尾指針分別是f和r,則當前隊列中的元素個數是（）。A(r-f+m)modmBr-f+1Cr-f-1Dr-f10.一個二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹（樹中結點個數大于1）。A空或只有一個結點B高度等于其結點數C任一結點無左孩子D任一結點無右孩子三、判斷題（每小題2分，對的打√，錯的打×，共10分）1．若圖G的最小生成樹不唯一，則G的邊數一定多于n-1，并且權值最小的邊有多條（其中n為G的頂點數）。()2．對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷可訪到該圖的每個頂點。()3．若某二叉樹的葉子結點數為1（樹中只有一個結點的情況除外），則其先序序列和后序序列一定相反。（）4．在隊列中，隊頭指針總是指向第一個數據元素。（）5．線性表的唯一存儲形式是鏈表。（）四、解答題（每小題6分，共24分）從一的平衡二叉樹開始，把關鍵字（5，19，6，22，16，15，30）按出現的先后順序逐一插入，從而構造一棵平衡二叉樹排序樹，每插入一個關鍵字后，若需要進行平衡旋轉，則標明其旋轉類型及旋轉后的結果。滿足下列條件的二叉樹具有什么形狀？前序和中序遍歷次序相同；中序和后序遍歷次序相同；前序和后序遍歷次序相同；寫出所給數據表，采用快速排序方法按升序排序的每一趟的結果：（25，10，20，31，5，28）。具有144個記錄的文件，若采用分塊查找法查找，則分成幾塊最好？每塊的最佳長度是多少？假定每塊的長度是8，確定所在塊、塊中均采用順序查找法查找，則平均查找長度是多少？五，編寫算法（共16分）寫出，建立一個具有n個頂點的無向網的鄰接矩陣的算法。提示：先將矩陣A的每個元素都初始化成0，然后，讀入邊及數值（i,j,w）,將A的相應元素置成w。（8分）線性表V采用順序存儲結構，試編寫刪除V中的第i個元素起的k個元素的算法。（8分）數據結構試卷試6一、填空題（共20分，每空1分）數據結構是研究數據元素之間抽象化的相互關系和這種關系在計算機中的存儲結構表示，通常有下列四種存儲結構：（1）、（2）、（3）和（4）。評價算法的標準很多，通常是以執(zhí)行算法所需要的（5）和所占用的（6）來判別一個算法的優(yōu)劣。隊列操作的原則是（7），棧的插入和刪除操作在（8）進行。對循環(huán)隊列Q，它的最大存儲空間是MAXSIZE，隊頭指針是front，隊尾指針是rear，采用少用一個存儲單元的方法解決假溢出時，隊滿的判斷條件是（9），隊空的判斷條件是（10）。在以Head為表頭指針的帶有頭結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為（11）和（12）。假設二維數組A[6][8]，每個元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址，已知A的開始存儲位置為100，按行優(yōu)先順序存儲的元素A[2][5]的第一個字節(jié)的地址為（13）?？崭翊拈L度為串中所包含（14）字符的個數，空串的長度為（15）。有向圖G用鄰接矩陣A[n，n]存儲表示，其第i行的所有元素之和等于頂點i的（16）。在關鍵字序列(12，23，34，45，56，67，78，89，91)中折半查找關鍵字為89和25的結點時，所需進行的比較次數分別為（17）和（18）。請說出兩種處理哈希沖突的方法（19）、_（20）_。二、選擇題（共20分，每題2分）對線性表，在下列哪種情況下應采用鏈式存儲結構？（）A．經常需要隨機存取元素B．經常需要進行插入和刪除操作C．表中元素的個數不變D．表中元素需要占據一片連續(xù)的存儲空間從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功情況下，則平均比較（）個結點。A．nB．n/2C．(n-1)/2若對某線性表最常進行的操作是在最后一個元素之后插入和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A．單鏈表B．雙鏈表C．僅有頭指針的單循環(huán)鏈表D．僅有尾指針的單循環(huán)鏈表在一個單鏈表中，若要刪除p指針所指結點的后繼結點，則執(zhí)