數(shù)據(jù)結(jié)構(gòu)A卷含答案

1、試卷編號(hào) 擬題教研室（或教師）簽名 教研室主任簽名 課程名稱（含檔次） 數(shù)據(jù)結(jié)構(gòu)A課程代號(hào) 課程編號(hào) 專 業(yè) 層次（本、專） 本科 考試方式（開、閉卷） 閉卷 一、 應(yīng)用題(3小題,共20分)1.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)椋篈，B，C，D，E，用I表示進(jìn)棧操作，O表示出棧操作，設(shè)初始狀態(tài)棧為空，寫出下列出棧的操作序列。（8分）（1）C，B，A，D，E（2）A，C，B，E，D2. 一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為16，5，9，3，30，1，完成問題：（1）設(shè)計(jì)一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）（2）計(jì)算其帶權(quán)路徑長度WPL。（8分）3. 已知無向圖G的鄰接表如圖所

2、示，分別寫出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列。（4分）二、判斷正誤(10小題,共20分)1順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 ( )2一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。( )3棧和隊(duì)列都是受限的線性結(jié)構(gòu)。P（ ）4. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（ ）5線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。（ ） 6. 完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。（ ）7. 鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。O（ ）8. 圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。P（ ）9

3、. 折半查找只適用于有序表，包括有序的順序表和鏈表。（ ）10. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。（ ）三、單項(xiàng)選擇題(15小題,共30分)1.算法分析的兩個(gè)主要方面是（ ）。A. 空間復(fù)雜度和時(shí)間復(fù)雜度 B.正確性和簡單性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ ）。A.圖 B.樹 C.廣義表 D.棧3.下面程序段的時(shí)間復(fù)雜度是（ ）。for(i=0;i<m;i+)for(j=0;j<n;j+)aij=i*j;A.O(m2) B.O(n2) C. O(m*n) D. O(m+n)4. 線性表是n個(gè)（ ）的有限序列。A.表元素

4、B.字符 C. 數(shù)據(jù)元素 D.數(shù)據(jù)項(xiàng)5. 線性表L=(a1,a2,an)，下列說法正確的是（ ）。A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.線性表中至少要有一個(gè)元素C.表中諸元素的排列順序必須是由小到大或由大到小D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都由一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼6. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）。A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL7. 隊(duì)列的插入操作是在（ ）。A.隊(duì)尾 B. 隊(duì)頭 C. 隊(duì)列任意位置 D. 隊(duì)頭元素后 8. 循環(huán)隊(duì)列的

5、隊(duì)頭和隊(duì)尾指針分別為front和rear，則判斷循環(huán)隊(duì)列為空的條件是（ ）。A.front=rear B.front=0 C.rear=0 D.front=rear+19. 二叉樹的深度為k，則二叉樹最多有（ ）個(gè)結(jié)點(diǎn)。A.2k B.2k-1 C.2k-1 D.2k-110兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是（ ）。AP->next=Q->next BP->next= QCQ->next= P DP= Q11樹最適合用來表示( )。A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù)12. 表達(dá)式

6、a*(b+c)-d的后綴表達(dá)式是（ ）。A.abcd+- B. abc+*d- C.abc*+d- D.-+*abcd13每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，這種存儲(chǔ)結(jié)構(gòu)稱為（ ）結(jié)構(gòu)。A. 順序存儲(chǔ) B. 鏈?zhǔn)酱鎯?chǔ) C. 索引存儲(chǔ) D.散列存儲(chǔ)14.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A.從源點(diǎn)到匯點(diǎn)的最長路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長的回路 D.最短的回路15設(shè)有以下四種排序方法，則（ ）的空間復(fù)雜度最大。A.冒泡排序 B.快速排序 C.堆排序 D.希爾排序四、算法設(shè)計(jì)題(1小題,共8分)1已知一個(gè)單鏈表，編寫一個(gè)函數(shù)從單鏈表中刪除自第i個(gè)結(jié)點(diǎn)起的k

7、個(gè)結(jié)點(diǎn)。（8分）五、填空題(5小題,共10分)1由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是（ ）2在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是 。3.對(duì)n個(gè)元素進(jìn)行起泡排序，在 情況下比較的次數(shù)最少，其比較次數(shù)為 。在 情況下比較次數(shù)最多，其比較次數(shù)為 。4已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半查找90時(shí)，需進(jìn)行 次查找可確定成功。5在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其 結(jié)點(diǎn)，另一個(gè)指向其 結(jié)點(diǎn)。六、簡答題(2小題,共12分)1已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對(duì)其進(jìn)行快速

8、排序的前兩趟的劃分結(jié)果。2. 請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)。湖北警官學(xué)院信息技術(shù)系2017-2018學(xué)年數(shù)據(jù)結(jié)構(gòu)A期末考試試卷(A卷)（答案部分）一、應(yīng)用題(3小題,共20分)1（8分）解：（1）IIIOOOIOIO （2）IOIIOOIIOO2.（8分）（1）樹形態(tài)：（2）帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129。3. （4分）【答案】深度優(yōu)先遍歷序列為：1，2，3，4，5，6廣度優(yōu)先遍歷序列為：1，2，4，3，5，6二、判斷正誤(10小題,共20分)1（×）2（×）3（）4（）5（）6.（）7.（

9、×）8.（）9.（×）10.（×）三、單項(xiàng)選擇題(15小題,共30分)1A 2D 3C 4C 5D 6A 7A 8A 9C 10.B 11.C 12.B 13.A 14.A 15.B 四、算法設(shè)計(jì)題(1小題,共8分)1解：void Del(ListNode *head,int i,int k) node *p,*q;int j;if (i=1) For (j=1;j<=k;j+)   / 刪除前k個(gè)元素p=head; / p指向要?jiǎng)h除的結(jié)點(diǎn) head=head->next; Free(p); elsep=head;for (j=1;

10、j<=i-2;j+)p=p->next;   / p指向要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)for (j=1;j<=k;j+)q=p->next;    / q 指向要?jiǎng)h除的結(jié)點(diǎn)p->next=q->next;free(q); 五、填空題(5小題,共10分)1節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率2哈希查找3正序，n-1，反序，n(n-1)/2425前趨 后繼六、簡答題(2小題,共12分)1. 【答案】 第一趟： 24 40 38 46 56 80 95 79第二趟： 24 40 40 46 56 80 95 792. 【答案】（1）順序表的優(yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空