數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2教材

1、、選擇題1）數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A ）及它們之間的相互聯(lián)系。A. 存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B. 存儲和抽象C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯2）在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成： （ C ）。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)3）數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ C ）。A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu)C. 順序存儲結(jié)構(gòu) D. 鏈式存儲結(jié)4）算法分析的兩個主要方面是（A ）。A. 空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C. 可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5）下列時間復(fù)雜度中最壞的是（D

2、 ）。A. O( 1)B. O(n）C.2O(log2n)D. O( n2)6）等概率情況下，在有n 個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為C ）。A nB （n-1）/2C n/2 D （n+1）/27）設(shè)有編號為 1，2， 3， 4的四輛列車，順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為( D )A 1234B1243C 1324D 1423（8）如 果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧 操作時（B )A必須判別棧是否滿B必 須 判別棧是否空C必須判別棧元素類型D 隊棧可 不做任何判別（9）鏈 棧與順序棧相比，有一個比較明顯的 優(yōu)點是（B )A插入 操作更 加方便B通常 不

3、 會出現(xiàn)棧 滿的情 況。front 和 rear 的值分別為 3和 0，當(dāng)C不會 出現(xiàn)棧 空的情 況 D 刪除 操 作根加方 便10 ）插 入和刪 除只能在一端進行的線性表， 稱為 （C) 。A 隊列 B 循環(huán)隊列C棧D循 環(huán)棧11）若進隊的序列為：A，B，C，D，則出隊的序列是（C ）。A B， C， D， AB A，C，B，DC A， B， C， DD C，B，D，A12 ）若用一個大小為 6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前從隊列中 刪除一 個元素 ，再加入 兩個元 素后， front 和 rear 的值分別為 （ B ）A 5和1B 4和2C2和4D1和5( 13) S=morning ，執(zhí)

4、行求子串函數(shù) SubStr(S,2,2) 后的結(jié)果為( B )。A moB orCinD ng( 14 ) S1=good ， S2=morning ， 執(zhí) 行 串 連 接 函 數(shù) ConcatStr(S1,S2) 后 的 結(jié) 果 為 ( A )。A goodmorningC GOODMORNINGB good morningD GOOD MORNING( 15) S1=good ， S2=morning ，執(zhí)行 函數(shù) SubStr(S2,4,LenStr(S1) 后的 結(jié) 果為 ( B ) 。A goodB ningC go16 ) 設(shè) 串 S1=ABCDEFGD morn， S2=PQRS

5、T ,則 ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的結(jié)果串為( D)。A BCDEFB BCDEFGCBCPQRSTD. BCDEFEF（17） 已知二維數(shù)組 放數(shù)組元素 a35A610 ，每個數(shù)組元素占 4個存儲單元， 若按行優(yōu)先順序存 B的存儲地址是 1000，則 a00 的存儲地址是（）。A 872B 860868D86418）在一棵具有五層的滿二叉樹中，結(jié)點的總數(shù)為A 16B3119 ）具有 64 個結(jié)點的完全二叉樹的深度為（A 5B6C32C )C7D3320）具有 n（ n1）個結(jié)點的完全二叉樹中，結(jié)點i( 2

6、in)的左孩子結(jié)點是（D ）。A 2iB 2i+1（若 2iprior-next=p-next5) A+B/C-D*E 的后綴表達式是： ABC/+DE*- 。6) 解決順序隊列“假溢出”的方法是采用 循環(huán)隊列。7) 循環(huán)隊列的隊首指針為 front ，隊尾指針為 rear ，則隊空的條件為front =rear 。8) 設(shè)循環(huán)隊列的頭指針front 指向隊首元素，尾指針 rear 指向隊尾元素后的一個 空 閑 元 素 ， 隊 列 的 最 大 空 間 為 MAXLEN， 則 隊 滿 標(biāo) 志 為 ： front=(rear+1)%MAXLEN 。9) 設(shè)循環(huán)隊列的容量為 40(序號從 0到 39

7、)，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11 ，rear=19 ，則循環(huán)隊列中還有8個元素。(L= (N rear front)%N=(401911)% 40=8)10) 設(shè)S=My Music ，則 LenStr(s)= _ 8 。11 ) 兩 個 字 符 串 分 別 為 ： S1=Today is ， S2=30 July,2005,ConcatStr(S1,S2) 的結(jié)果是：Today is 30 July,2005。12 ) 求 子 串 函 數(shù) SubStr(Today is 30 July,2005,13,4) 的 結(jié) 果 是 ： July 。13) 在串 的運算 中，

8、EqualStr(aaa,aab) 的返回 值為 data= x ; p=head-next; while (p!=NULL) & ( p-data!=a ) p=p-next ;if (p=NULL)coutnext=p-next ; p-next=s ;(2) 假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設(shè)一個隊尾指針 rear ，試填空完成向循環(huán)隊列中插入一個元素為 x 的結(jié)點的函數(shù)。typedef struct queuenode int data;struct queuenode *next; QueueNode; InQueue(QueueNode *rear,int x) Qu

9、eueNode *rear;QueueNode *head,*s;s= new QueueNode ; s-data= x ; if(rear=NULL) rear=s; rear-next;else head= rear-next rear-next= s ; rear=s;rear-next =head;/ 定義隊列的存儲結(jié)構(gòu)/ 向隊列插入元素為 x 的函數(shù)/ 循環(huán)隊列為空，則建立一個結(jié)點的循環(huán)隊列/ 循環(huán)隊列非空，則將 s 插到后面3）下面程序是把兩個串 r1 和 r2 首尾相連的程序，即： r1=r1+r2 ，試完成程序填空。typedef Struct char vecMAXLEN;

10、 int len;/ 定義合并后串的最大長度/ len 為串的長度Stvoid ConcatStr(Str *r1,Str *r2) int i; coutvecvec; if(r1-len+r2-len MAXLEN ) cout 兩個串太長，溢出！ / 字符串連接函數(shù)else for(i=0;ilen ;i+)/ 把 r2 連接到 r1r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; r1-len= r1-len+r2-len ;/ 添上字符串結(jié)束標(biāo)記/ 修改新串長度（4） 下面算法是判斷字符串是否為回文（即正讀和倒讀相同），試完成程序填空。#in

11、clude stdio.h typedef struct char vecMAXLEN;int len;str;void Palindrome (str s) int i=0;ing j= s.len-1 ;while ( j-i=1 ) if ( s.veci= s.vecj )/ (或 j=j+1 )i+; j- ;continue elsebreak;if ( j-i=1 )coutIt is not a palindromen;elsecoutIt is a palindromen;(5)void BInsSort( )/ int i, j, low, high, m;for( i=2

12、;i= n ; i+) R0=Ri;low=1;high= n ； while(low = high) m=(low+high)/2 ; if(R0=high+1;j-)R j +1= R j ;Rhigh=R0; /按遞增序?qū)?R1R n 進行二分插入排序/ 設(shè)定 R0 為監(jiān)視哨/ 元素后移 插入四、應(yīng)用題ACDBGIHFE和 ABCDEFGH。I（1）已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：請畫出該二叉樹，并寫出它的前序遍歷的序列。解：恢復(fù)的二叉樹為：H其前序遍歷的序列為： E B A D C F H G I2) 把下列一般樹轉(zhuǎn)換為二叉樹解：3)K解：A解：還原后的二叉樹為：5）假

13、設(shè)用于通信的電文僅由A、B、C、D、E、F、G 8 個字母組成，字母在電文中出現(xiàn)的頻率分別為 7，19，2，6，32，3，21，10。試為這 8 個字母設(shè)計哈夫曼編碼。解：左子為 0，右子為 1。）以權(quán)值： 2、3、6、7、10、19、21、32 構(gòu)造哈夫曼樹：10001400011010111701 0字母編號對應(yīng)編碼出現(xiàn)頻率A10107B0019C100002D10016E1132D100013E01216)有向圖如下圖所示，畫出鄰接矩陣和鄰接表解：鄰接矩陣鄰接表，(0,2)(0,4) ，(0,5) ， 分別寫出按深101010001000010(1,2) ，(2,3) ，(2,4) ，(

14、3,4) ，(4,5) 。試畫出該無向圖，并從頂點 0 出發(fā)， 度優(yōu)先搜索和按廣度優(yōu)先搜索進行遍歷的結(jié)點序列。解：從頂點 0 出發(fā)的深度優(yōu)先搜索遍歷的結(jié)點序列： 0 1 2 3 4 5（答案不唯一）從頂點 0 出發(fā)的廣度優(yōu)先搜索遍歷的結(jié)點序列： 0 1 2 4 5 3（答案不唯一） 8）網(wǎng) G 的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。1）試構(gòu)造一棵二叉排序樹；（2）求等概率情況下的平均查找長度解：（ 1）構(gòu)造二叉排序樹 ：ASL 。( 2) ASL=(1*1+2*2+3*4+4*3)/10=2.90810110803013103040110407013070（10） 給定結(jié)點的關(guān)

15、鍵字序列為： 19，14，23，1，68，20，84，27， 55，11，10，79。 設(shè)散列表的長度為 13，散列函數(shù)為： H（K）=K % 13。試畫出線性探測再散列解決沖突時 所構(gòu)造的散列表，并求出其平均查找長度。解：線性探測再散列解決沖突時所構(gòu)造的散列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110 平均查找長度 ASL= ( 1*6+2*1+3*3+4*1+9*1 )/12=30/3=3（11） 給定結(jié)點的關(guān)鍵字序列為： 47， 7，29，11，16，92，22，8，3，哈希表的長度為 11。 設(shè)散列函數(shù)為： H（K）=K %

16、 11 。試畫出平方探測再散列解決沖突時所構(gòu)造的散列表，并求 出其平均查找長度。解：平方探測再散列解決沖突時所構(gòu)造的散列表。012345678910112234792167298平均查找長度 ASL= （1*5+2*4 ）/9 = 13/9 = 5/3（或 1.44）12）已知數(shù)據(jù)序列 12，02，16，30，28，10，17，20，06，18 ，寫出希爾排序每一趟排10 02 16 06 18 12 17 20 30 28d=212 02 16 06 17 12 18 20 30 28d=1 02 06 10 12 16 17 18 20 28 30（13）已知數(shù)據(jù)序列 10，18，4，3，6，12，9，15 ，寫出二路歸并排序的每一趟排序結(jié)果。10 18 4 3 6 12 9 1510 18 3 4 6 12 9 15 第一趟排序結(jié)果3 41018691215第二趟排序結(jié)果3 469 10121518第三趟排序結(jié)果（14）已知數(shù)據(jù)序列53，36，48，36，60，7，18，41 ，寫出采用簡單選擇排序的每一趟排序結(jié)果。解： 53 36 4836607 18 41（7）36 483660531841（7