1、試卷編號試卷編號命題人： 白明 試卷分類A卷或B卷 A 五邑大學 試 卷學期： 2021 至 2021 學年度 第 二 學期課程： 數據結構 專業： 班級： AP0706 姓名： 學號： 題號一二三四五總分得分一、單項選擇題(10小題，每題1分，共10分)1假設一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n ，那么第i個輸出元素是_D_。A不確定Bn-iCn-i-1Dn-i+12設計一個判別表達式中左右括號是否配對的算法，采用_B_數據結構最正確。A順序表B棧C隊列 D鏈表3設有兩個串p和q，求q在p中首次出現的位置的運算稱作_C_。A連接B求子串C模式匹配D求串長 4線性表的順序

2、存儲結構是一種_A_的存儲結構。A隨機存取B順序存取C索引存取D散列存取 5對于n個元素組成的線性表，建立一個有序單鏈表的時間復雜度是_C_。AO(1) BO(n)CO(n2)DO(nlog2n)6關鍵路徑是AOE網中_A_。A從源點到終點的最長路徑B從源點到終點的最短路徑C最長的回路D最短的回路 7數據元素為34,76,45,18,26,54,92,65，按照依次插入結點的方法生成一棵二叉排序樹，那么該樹的深度為_B_。A3B5C7D9 8對數列25,84,21,47,15,27,68,35,20進行排序，元素序列的變化情況如下：(1) 25，84，21，47，15，27，68，35，20(

3、2) 20，15，21，25，47，27，68，35，84(3) 15，20，21，25，35，27，47，68，84(4) 15，20，21，25，27，35，47，68，84那么采用的排序方法是_A_。A快速排序B歸并排序C基數排序D希爾排序 9任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序_A_。A肯定不發生改變B肯定發生改變C不能確定D有時發生變化 10對特殊矩陣采用壓縮存儲的目的主要是為了_D_。A表達變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間二、判斷題(10小題，每題1分，共10分) 1一個圖的鄰接矩陣表示是惟一的，鄰接表表示也惟

4、一。 2設有5000個元素，希望用最快的速度挑選出前10個最大的，采用快速排序方法比采用堆排序更好。 3在散列函數H(k)=k mod m 中，一般來講，m應取素數。 4從邏輯關系上講，數據結構主要分為集合、線性結構、樹結構和圖結構。 5一維數組A采用順序存儲結構，每個元素占用4個存儲單元，第9個元素的地址為144，那么第1個元素的地址為112。 6數組Qn用來表示一個循環隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數的公式為(rearfrontn)%n。 7將數組稱為隨機存取結構是因為數組元素是隨機的。 8排序的主要目的時為了以后對已排序的數據進行查找。

5、 9在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。 10拓撲排序算法和廣度優先遍歷算法都能判斷一個有向圖是否存在回路。三、填空題(10小題，每空1分，共16分)1表示有100個頂點，1000條邊的有向圖的鄰接矩陣有_1000_個非零矩陣元素。2如果要將序列50,16,23,68,94,70,73建成堆，只須把16與_50_交換。3具有6個頂點的無向圖至少應該有_5_條邊才能確保是一個連通圖。4含A、B、C這3個結點的不同形態的樹有_2_棵，不同形態的二叉樹有_5_棵。5 中綴表達式(5620)(42)轉換為后綴表達式為56#20-4#2+/，后綴表達式A BC D E 轉換為中綴表

6、達式為A/B-C*D+E。6一個有序表的關鍵字序列為1，8，12，25，29，32，40，62，98，當二分查找值為29的元素時，需要_1_次比擬才能查找成功；假設采用順序查找時，需要_5_次比擬才能查找成功。7一棵樹T的邊集為I,M,I,N,E,I,B,E,B,D,C,B,G ,J,G ,K,A,G,A,F,H,L,A,H,C,A，那么該樹的根結點是_C_，葉子結點共_7_ 個， 該樹的深度為_5_。8設待處理問題的規模為n，假設一個算法的時間復雜度為一個常數，那么表示成數量級的形式為_O(1)_；假設為nlog25n, 那么表示成數量級的形式為_O(nlog2n)_。 9在由尾指針rear

7、指示的單循環鏈表中，在表尾插入一個結點s的操作序列是s-next=rear-next; rear-next=s;和rear=s。10二叉樹的前序序列和后序序列正好相反，那么該二叉樹一定是_高度等于其結點數_的二叉樹。四、應用題(共有7小題，共計50分)一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，畫出該二叉樹，并給出該二叉樹的前序遍歷序列，畫出該二叉樹對應的森林。(10分)解答：二叉樹如下5分： 對應的森林如下3分：ECAGFDECAGFDBECADBGF前序遍歷序列是：EACBDGF 2分證明：對于一棵非空的二叉樹，如果葉結點數為n0，度為2的結點數為n2，那么有n

8、0=n2+1。5分證明：設n為二叉樹的結點總數，n1為二叉樹中度為1的結點數，那么有： nn0n1n2 2分在二叉樹中，除了根結點外，其余結點都有唯一的一個分枝進入，由于這些分枝是由度為1和度為2的結點射出的，一個度為1的結點射出一個分枝，一個度為2的結點射出兩個分枝，所以有： nn12n21 2分合并兩式，可以得到：n0n21 。1分假設輸入序列是3，5，1，9，4，10，2，8，7，6，試畫出所產生的大根堆和所對應的二叉排序樹。7分大根堆：4分二叉排序樹：3分 1313456971082某字符串S中共有5種字符(A，B，C，D，,E)，各種字符出現的頻率分別是15，36，3，6，20，建立

9、相應的哈夫曼樹，對該字符串用0，1進行前綴編碼，給出5種字符的哈夫曼編碼，并計算其WPL。7分哈夫曼樹：4分哈夫曼編碼：2分WPL：1分A：111A：111B：0C：1100D：1101E：10WPL=36+40+45+36=157 給定表19,14,22,01,66,21,83,27,56,13,10，按表中元素順序構造一棵AVL樹。7分每個平衡步驟1分。 6某圖的鄰接表如下7分：分別給出從A、B點出發進行廣度優先搜索的序列。畫出該圖。解答：分別給出從A、B點出發進行廣度優先搜索的序列。各2分A： A B C D B： B A C D對應的圖如下： 3分7設有一組關鍵字72，35，124，1

10、53，84，57需要插入到表長為12 的散列表中。試設計一個適當的散列函數；用此散列函數將上述關鍵字插入散列表，用線性探測法解決沖突。試畫出最終的散列表結構。 說明：哈希函數不同，數據在哈希表中的位置不同。多解假設設：H(key)=key%112分 那么最終的哈希表結構為：3分所有關鍵字求散列值：2分0 1 2 3 4 5 6 7 872153124358457 3五、算法設計題(2小題，每題7分，共14分)1設計一個算法，判斷一個單鏈表中的元素是否遞增有序。templateint order(Node *h)Node *p=h; 以上1分while(p-next!=NULL)if(p-datanext-data)p=p-next; 以上3分elsebreak;if(p-next=NULL)return 1;elsereturn 0; 以上3分 2一棵具有n個結點的二叉樹采用順序存儲結構，編寫算法對該二叉樹進行前序遍歷。 說明：僅給出一種參考算法，可以用遞