數據結構樣題及答案.doc

一填空題（每題2 分，共20 分）；1. 數據結構算法中，通常用時間復雜度和_空間復雜度_兩種方法衡量其效率。2. 下面程序段的時間復雜度為_ O(n2)_。(n1)for(i = 1; i = n; i+)for(j = 1; j = i; j+)x = x + 1;3. 在一個長度為 n 的順序表中第i 個元素（1=i=n）之前插入一個元素時，需向后移動_ n-i+1_個元素。4. 在 n 個結點的單鏈表中要刪除已知結點*p，需找到它的_前驅_。5. 在具有 n 個元素空間的循環(huán)隊列中，隊滿時共有_n-1_個元素。6. 兩個串相等的充分必要條件是_串長相等且對應字符相等_。7. 具有 256 個結點的完全二叉樹的深度為_9_。8. G 是一個非連通無向圖，共有36 條邊，則該圖至少有_9_個頂點。 邊數=N(N-1)/29. 在順序表（8,11,15,19,21,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值20，需做的關鍵碼比較次數為_4_。10. 直接插入排序用監(jiān)視哨的作用是_始終存放待插入的記錄，免去查找過程中每一步都要檢測整個表是否查找完畢_。二單項選擇題1. 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（A ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結點的雙循環(huán)鏈表 D單循環(huán)鏈表2. 設 a1、a2、a3 為3 個結點，則如下的鏈式存儲結構稱為：(A)表元編號 結點表元間關系1a132a213a32A循環(huán)鏈表 B單鏈表 C雙向循環(huán)鏈表 D雙向鏈表3. 有六個元素 6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（B）A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3 1 2 6 D. 2 3 4 1 5 64. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間 V1.m，topi代表第i 個棧( i =1,2)棧頂，棧1 的底在v1，棧2 的底在Vm，則棧滿的條件是（B ）。A. top2-top1|=0 B. top1+1=top2C. top1+top2=m D. top1=top25. 數組用來表示一個循環(huán)隊列，front 為當前隊列頭元素的前一位置，rear 為隊尾元素的位置，假定隊列中元素的個數小于，計算隊列中元素的公式為(D)A. rearfront B.（nfrontrear）% nC. nrearfront D.（nrearfront）% n6. 設棧 S 和隊列Q 的初始狀態(tài)為空，元素e1，e2，e3，e4,e5 和e6 依次通過棧S，一個元素出棧后即進隊列Q，若6 個元素出隊的序列是e2，e4,e6,e5，e3,e1 則棧S 的容量至少應該是(B )。A 6 B. 4 C. 3 D. 27. 設有數組 Ai,j，數組的每個元素長度為3 字節(jié)，i 的值為1 到8 ，j 的值為1 到10，數組從內存首地址BA 開始順序存放，當用以列為主存放時，元素A5，8的存儲首地址為( B)。A. BA+141 B. BA+180 C. BA+222 D. BA+2258. 已知廣義表 L=(x,y,z),a,(u,t,w)，從L 表中取出原子項t 的運算是（D）。A. head（tail（tail（L） B. tail（head（head（tail（L）C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）9. 一棵樹高為 K 的完全二叉樹至少有（C）個結點?A2k 1 B. 2k-1 1 C. 2k-1 D. 2k10. 某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（C ）的二叉樹。A空或只有一個結點 B任一結點無左子樹C高度等于其結點數 D任一結點無右子樹11. 無向圖 G=(V,E),其向V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是(A ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b12. 下面關于求關鍵路徑的說法不正確的是（ B）。A求關鍵路徑是以拓撲排序為基礎的B一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D關鍵活動一定位于關鍵路徑上13. 在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A,并已知A 的左孩子的平衡因子為 0 右孩子的平衡因子為1,則應作( C) 型調整以使其平衡。A. LL B. LR C. RL D. RR14. 設哈希表長為 14，哈希函數是H(key)=key%11,表中已有數據的關鍵字為15，38，61，84 共四個，現(xiàn)要將關鍵字為49 的結點加到表中，用平方探測再散列法解決沖突，則放入的位置是(D)A8 B3 C5 D915. 對一組數據（84，47，25，15，21）排序，數據的排列次序在排序的過程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21（3） 15 21 25 84 47 （4） 15 21 25 47 84則采用的排序是 (A )。A. 選擇 B. 冒泡 C. 快速 D. 插入三、判斷題（每題1 分，共5 分，正確的打，錯誤的打）( T) 1數據元素是數據的最小單位。(F ) 2線性表在鏈式存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。(T ) 3棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。( F) 4帶權無向圖的最小生成樹必是唯一的。(F ) 5排序的穩(wěn)定性是指排序算法中的比較次數保持不變，且算法能夠終止。四綜合題（共 45 分）1. 線性表具有兩種存儲方式，即順序方式和鏈接方式。現(xiàn)有一個具有五個元素的線性表L=23，17，47，05，31，若它以單鏈表方式存儲在下列100119 號地址空間中，每個結點由數據（占2 個字節(jié)）和指針（占2 個字節(jié),由大寫字母表示）組成，如下所示：100 120 47p23q05r31s17t其中指針 p，q，r，s，t 的值分別為多少？該線性表的首結點起始地址為多少？末結點的起始地址為多少？(共7 分)答：p= 108 q = 116 r =112 s=0 或NULLt= 100 首址= 104 末址=1122. 如果想將輸入的一個字符序列逆序輸出，如輸入“abcdef ”，輸出“fedcba”，請分析用線性表、堆棧和隊列等方式正確輸出的可能性？ (共6 分)答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)3. 設二叉樹后根遍歷為 BAC，畫出所有可能的二叉樹。(共5 分)4. 有一份電文中共使用 6 個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,6,7,4,3,5，試寫出為這六個字母設計的哈夫曼編碼, 并畫出對應的哈夫曼樹。(共 5. 某田徑賽中各選手的參賽項目表如下:姓名參 賽 項ZHAOA B EQIANC DSHUNC E FLID F AZHOUB F設項目A ,B ,，F(xiàn) 各表示一數據元素,若兩項目不能同時舉行,則將其連線(約束條件).（1）根據此表及約束條件畫出相應的圖狀結構模型,并畫出此圖的鄰接表結構; (共5 分)（2）寫出從元素A 出發(fā)按“廣度優(yōu)先搜索”算法遍歷此圖的元素序列. (共3 分)ABDEFC6. 一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。(共6 分）7. 給出一組關鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進行排序時的變化過程：（6 分）(1) 冒泡排序（3 分）第一趟排序結果： 18，25，29，47，12，51,10,58試按上面的描述形式說明排序全過程（動態(tài)過程,寫出每趟排序后數列的變化結果）要求按遞增順序排序。第一： 18，25，29，47，12，51,10,58第二： 18，25，29，12，47，10，51第三： 18，25，12，29，10，47第四： 18，12，25，10，29第五： 12，18