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

1、試卷編號 擬題教研室（或教師）簽名 教研室主任簽名 課程名稱（含檔次） 數(shù)據(jù)結(jié)構(gòu)A課程代號 課程編號 專 業(yè) 層次（本、專） 本科 考試方式（開、閉卷） 閉卷 一、 應(yīng)用題(3小題,共20分)1.設(shè)有一個棧，元素進棧的次序為：A，B，C，D，E，用I表示進棧操作，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è)計一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）（2）計算其帶權(quán)路徑長度WPL。（8分）3. 已知無向圖G的鄰接表如圖所

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

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

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

5、隊頭和隊尾指針分別為front和rear，則判斷循環(huán)隊列為空的條件是（ ）。A.front=rear B.front=0 C.rear=0 D.front=rear+19. 二叉樹的深度為k，則二叉樹最多有（ ）個結(jié)點。A.2k B.2k-1 C.2k-1 D.2k-110兩個指針P和Q，分別指向單鏈表的兩個元素，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. 表達式

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

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

8、排序的前兩趟的劃分結(jié)果。2. 請說明順序表和單鏈表各有何優(yōu)缺點。湖北警官學(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.（×）三、單項選擇題(15小題,共30分)1A 2D 3C 4C 5D 6A 7A 8A 9C 10.B 11.C 12.B 13.A 14.A 15.B 四、算法設(shè)計題(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個元素p=head; / p指向要刪除的結(jié)點 head=head->next; Free(p); elsep=head;for (j=1;

10、j<=i-2;j+)p=p->next;   / p指向要刪除的結(jié)點的前一個結(jié)點for (j=1;j<=k;j+)q=p->next;    / q 指向要刪除的結(jié)點p->next=q->next;free(q); 五、填空題(5小題,共10分)1節(jié)省存儲空間，降低上溢發(fā)生的機率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)點： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空