數(shù)據(jù)結(jié)構(gòu)試題(白明)試題+參考答案

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

2、存儲(chǔ)結(jié)構(gòu)是一種_A_的存儲(chǔ)結(jié)構(gòu)。A隨機(jī)存取B順序存取C索引存取D散列存取 5對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是_C_。AO(1) BO(n)CO(n2)DO(nlog2n)6關(guān)鍵路徑是AOE網(wǎng)中_A_。A從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑B從源點(diǎn)到終點(diǎn)的最短路徑C最長(zhǎng)的回路D最短的回路 7數(shù)據(jù)元素為34,76,45,18,26,54,92,65，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，那么該樹的深度為_B_。A3B5C7D9 8對(duì)數(shù)列25,84,21,47,15,27,68,35,20進(jìn)行排序，元素序列的變化情況如下：(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基數(shù)排序D希爾排序 9任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序_A_。A肯定不發(fā)生改變B肯定發(fā)生改變C不能確定D有時(shí)發(fā)生變化 10對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了_D_。A表達(dá)變得簡(jiǎn)單B對(duì)矩陣元素的存取變得簡(jiǎn)單C去掉矩陣中的多余元素D減少不必要的存儲(chǔ)空間二、判斷題(10小題，每題1分，共10分) 1一個(gè)圖的鄰接矩陣表示是惟一的，鄰接表表示也惟

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

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

6、達(dá)式為A/B-C*D+E。6一個(gè)有序表的關(guān)鍵字序列為1，8，12，25，29，32，40，62，98，當(dāng)二分查找值為29的元素時(shí)，需要_1_次比擬才能查找成功；假設(shè)采用順序查找時(shí)，需要_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，那么該樹的根結(jié)點(diǎn)是_C_，葉子結(jié)點(diǎn)共_7_ 個(gè)， 該樹的深度為_5_。8設(shè)待處理問(wèn)題的規(guī)模為n，假設(shè)一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，那么表示成數(shù)量級(jí)的形式為_O(1)_；假設(shè)為nlog25n, 那么表示成數(shù)量級(jí)的形式為_O(nlog2n)_。 9在由尾指針rear

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

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

9、相應(yīng)的哈夫曼樹，對(duì)該字符串用0，1進(jìn)行前綴編碼，給出5種字符的哈夫曼編碼，并計(jì)算其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，按表中元素順序構(gòu)造一棵AVL樹。7分每個(gè)平衡步驟1分。 6某圖的鄰接表如下7分：分別給出從A、B點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索的序列。畫出該圖。解答：分別給出從A、B點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索的序列。各2分A： A B C D B： B A C D對(duì)應(yīng)的圖如下： 3分7設(shè)有一組關(guān)鍵字72，35，124，1

10、53，84，57需要插入到表長(zhǎng)為12 的散列表中。試設(shè)計(jì)一個(gè)適當(dāng)?shù)纳⒘泻瘮?shù)；用此散列函數(shù)將上述關(guān)鍵字插入散列表，用線性探測(cè)法解決沖突。試畫出最終的散列表結(jié)構(gòu)。 說(shuō)明：哈希函數(shù)不同，數(shù)據(jù)在哈希表中的位置不同。多解假設(shè)設(shè)：H(key)=key%112分 那么最終的哈希表結(jié)構(gòu)為：3分所有關(guān)鍵字求散列值：2分0 1 2 3 4 5 6 7 872153124358457 3五、算法設(shè)計(jì)題(2小題，每題7分，共14分)1設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中的元素是否遞增有序。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個(gè)結(jié)點(diǎn)的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，編寫算法對(duì)該二叉樹進(jìn)行前序遍歷。 說(shuō)明：僅給出一種參考算法，可以用遞