數據結構試題2010度

1、煙臺大學20 09 20 10 學年第 二 學期數據結構 試卷A（注：第三大題答案請寫在后面的空白答題紙上）一、選擇題(每小題2分，共20分) 1. 以下四類基本的邏輯結構反映了四類基本的數據組織形式，解釋錯誤的是 ( )A、集合中任何兩個結點之間都有邏輯關系但組織形式松散B、線性結構中結點按邏輯關系依次排列形成一條"鎖鏈"C、樹形結構具有分支、層次特性，其形態(tài)有點像自然界中的樹D、圖狀結構中的各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接2. 若結點的存儲地址與其關鍵字之間存在某種映射關系，則稱這種存儲結構為( ) A、順序存儲結構 B、鏈式存儲結構 C、索引存儲結構

2、 D、散列存儲結構 3. 在長度為n的順序表的第i (1in+1)個位置上插入一個元素，元素的移動次數為( ) A、n-i+1 B、n-i C、i D、i-1 4. 對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為( ) A、順序表 B、用頭指針表示的單循環(huán)鏈表 C、用尾指針表示的單循環(huán)鏈表 D、單鏈表 ABCDEF圖15. 一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ） A 、e d c b a B、d e c b a C、d c e a b D、a b c d e 6. 已知圖1如右所示，若從頂點A出發(fā)按深度優(yōu)先搜索進行遍歷，則可能得到的頂點序列為（ ）

3、A、 A，B，E，C，D，F B、 A，C，F，E，B，DC、 A，E，B，C，F，D D、 A，E，D，F，C，B7. n個頂點的有向圖中含有向邊的數目最多為 ( ) A、n-1 B、n C、n(n-1)/2 D、n(n-1) 8. 若一個棧的輸入順序是1，2，n，輸出序列的第一個元素是n，則第i（1in）個輸出元素是（ ）A、n-i B、n-i-1 C、i+1 D、n-i+112345圖29. 已給圖2，（ ）是該圖的正確的拓撲排序序列 A、1，2，3，4，5 B、1，3，2，4，5 C、1，2，4，3，5 D、1，2，3，5，410. 為查找某一特定單詞在文本中出現的位置，可應用的串運算

4、是( ) A、插入 B、刪除 C、串聯接 D、子串定位 二、填空題(每小題2分，共30分)1. 存儲結構是邏輯結構的_實現。2. 若一個算法中的語句頻度之和為T(n)=n+4nlogn，則算法的時間復雜度為_。 3. 數組A1.10,-2.6,2.8以行優(yōu)先順序存儲，設基地址為100，每個元素占3個存儲單元，則元素A5,0,7的存儲地址是 。4. 在無向圖的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于_。 5. 對帶有頭結點的鏈隊列l(wèi)q，判定隊列中只有一個數據元素的條件是_。6. 設數組data0.m作為循環(huán)隊列sq的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指

5、針front的值為 。7. 設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e3，e5，e4,e6,e2,e1,則棧S的容量至少應該是 。8. 設有順序棧s0.m-1，若棧底設在下標最大的一端，則棧滿的條件是 （設棧頂指針為top，指向棧頂元素的位置）。9. 有一個10階對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲，A1,1為第一元素，其存儲地址為1，每個元素占一個地址空間，則A7,5的地址為 。10. 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找，查找元素11，需進行 次

6、元素之間的比較。 11. 深度為h的完全二叉樹至少有_個結點。12. 在對一組記錄（18，6，27，12，52，15，47，29）進行直接插入排序時，當把第6個記錄15插入到有序表時，為尋找插入位置需比較 次。13. 在直接插入排序和快速排序中，若初始數據基本有序，則選用_；在冒泡排序和堆排序中，若要求數據的穩(wěn)定性，則選用_。14. 廣義表運算式TAIL(a,b)，(c,d) 的運算結果為 。15. 一組記錄的關鍵字為(42,59,36,28,10,84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為 。三應用題（每小題5分，共35分）11. 設有序列(45，24，53，12，

7、28，90)，請構成一棵二叉排序樹，并求其查找成功時的平均查找長度。2. 對關鍵字序列(56，20，23，75，29，61，36，87) 進行堆排序，使之按關鍵字遞增次序排列，請寫出排序過程中建初始堆的過程。3. 已知散列表長度為13，散列函數為H(key)=key % 11，處理沖突的方法為線性探測法，請畫出依次插入關鍵字(10,8,40,27,21,57,46,23,19,56)以后的散列表，并計算查找成功和不成功時的平均查找長度。4. 已知某二叉樹按中序遍歷次序是BDCEAFHG，按后序遍歷次序是 DECBHGFA，試畫出該二叉樹的形狀，并寫出它的前序掃描序列。5. 以數據集（17，9，

8、2，6，3，24，10）為葉結點的權值，構造一棵哈夫曼樹。1234561921161471511465圖36. 已知如圖3所示的無向帶權圖，請用普里姆（Prim）算法求其從頂點1開始的最小生成樹，畫出生成過程。v6v5v310345632v1v2v4圖4128 已知一個網絡如圖4所示，利用Dijkstra算法求頂點v1到各頂點的最短路徑。四算法設計題（共2小題，共15分）1已知一個線性表中的元素按值非遞減有序排列，以鏈式存儲編寫一個算法刪除表中多余的值相同的元素。（8分）2寫出求一棵二叉樹的高度的算法。（7分）煙臺大學20 1o 20 11 學年第 二 學期數據結構試卷A參考答案及評分標準考試

9、方式： 閉卷 （開卷、閉卷、其他）院系： 計算機學院 年級： 02級專 專業(yè)： 計算機 .注：標準答案、參考答案要點及評分標準須寫清題號、每小題得分、共得分等。 此格式為題頭，如本頁不夠，后面請附相同規(guī)格（A4）的紙張。.一、選擇題(每小題2分，共20分) 1.A 2.D 3.A 4.C 5.C 6.D 7.D 8.D 9.A 10.D二、填空題(每小題2分，共30分) 1. 物理 2. nlogn 3. 913 4. 1 5. lq->front->next=lq->rear 6. (sq.front+1)%(m+1) 7. sq.front=(sq.front+1)%(m

10、+1) 8. 4 9. top=0 10. 3 11. 2h-1 12. 4 13. 直接插入、冒泡452453122890 14. (c,d) 15.(10,28,36,42,59,84)三、應用題(每小題5分，共35分)1.ASLsucc=(1*1+2*2+3*3)/6=7/35620237529613687562023872961367556206187292336752.568761752923362087756156292336203.地址0123456789101112元素2357465627408191021查找成功時的1724632109查找不成功時的ABFCHGDE4. 5.

11、 前序序列：ABCDEFGH6115712316544121611231651231654457123165446.V1V2V3V4V5V602/V1312µµ3/V17µµ6/V313111310/V413/V37.四算法設計題（共2小題，共15分）1. void DeleteEqual2(LinkekList L) 2. int BinTreeDepth(BitTree T) /刪除元素非遞減排列的鏈表L中所有值相同的元素 if(T=NULL)return 0; p=L->next;q=p->next; elsel=BinTreeDepth(T->lchild); while(p->nex