數(shù)據(jù)結(jié)構(gòu)樣題及答案.doc

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