數(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. 存儲和抽象（2）在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成： （ C ）。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)C. 聯(lián)系和抽象D. 聯(lián)系與邏輯B. 緊湊結(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.（4）算法分析的兩個主要方面是（A. 空間復(fù)雜性和時間復(fù)雜性C. 可讀性和文檔性（5）下列時間復(fù)雜度中最壞的是（邏輯結(jié)構(gòu)A ）。D ）。C. 順序存儲結(jié)構(gòu)D. 鏈?zhǔn)酱鎯Y(jié)A. O（ 1）6）等概率情

2、況下，在有n）C ）。AnB.D.C.正確性和簡明性 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性O(shè)(log2n)2D. O( n2)B.n 個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為. （n-1）/2 C. n/2D. （n+1）/23， 4的四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可n/2能的出站順序為A. 1234( D )B .1243C. 1324D . 1423（8）如 果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧 操作時（B )A. 必須判別棧是否滿B.必須判別棧是否空C. 必須判別棧元素 類型D. 隊?？?不做任何判別（9）鏈 棧與順序棧相比，有一個比較明顯的 優(yōu)點是（B )7）設(shè)有編號為1， 2

3、，A.插入操作更加方便B.通常不 會出現(xiàn)棧O滿的情 況。C.不會出現(xiàn)?？盏那闆rD.刪除操 作根加方A .隊列B. 循環(huán)隊列C .棧D.循 環(huán)棧11)若進(jìn)隊的序列為：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 的值分別為 3和 0，當(dāng)10 ）插 入和刪 除只能 在一端進(jìn)行的線 性表，稱為 （ C）。）。從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為（BA . 5和 1B. 4和 2C . 2和 4D. 1和 51

4、3 ) S=morning，執(zhí)行求子串函數(shù)SubStr（S,2,2）后的結(jié)果為（B ）。B . orC. inD . ngA. mo(14)S1=good ，S2=morning，執(zhí)行串連接函數(shù) ConcatStr(S1,S2) 后的結(jié)果為( A )。A . goodmorningB . good morningC . GOODMORNINGD . GOOD MORNING(15)S1=good ，S2=morning，執(zhí)行函數(shù) SubStr(S2,4,LenStr(S1) 后的 結(jié)果為( B )。A goodB ningD . mornC. go( 16) 設(shè) 串 S1=ABCDEFG ，

5、S2=PQRST ,則 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)先順序存 的存儲地址是 1000，則 a00 的存儲地址是（B )。A 872B 860C 868D86418）在一棵具有五層的滿二叉樹中，結(jié)點的總數(shù)為（A. 16B. 3119）具有 64 個結(jié)點的完全二叉樹的深度為（A . 5B. 6C32C )C. 7D33（20）具有n （

6、 n1）個結(jié)點的完全二叉樹中，結(jié)點i( 2in)的左孩子結(jié)點是（D )。A . 2i B . 2i+1（若 2ip rior- n ext =p-nexto(6)A+B/C-D*E的后綴表達(dá)式是:ABC/+DE*- o解決順序隊列“假溢出”的方法是采用循環(huán)隊列。循環(huán)隊列的隊首指針為front，隊尾指針為rear，則隊空的條件為front =rear 。(8)設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN,則隊滿標(biāo)志為：fron t=(rear+1)%MAXLEN(9)設(shè)循環(huán)隊列的容量為 40 (序號從0到39),現(xiàn)經(jīng)過一系列的

7、入隊和出隊運算后，有front=11 , rear=19 ,則循環(huán)隊列中還有8個元素。(L= (N + rear front)%(10)(11)N=( 40+ 19- 11)設(shè) S=My Music兩個字符% 40=8)，貝U LenStr(s)= _8串分另U為S1=Today isS2=30Today is 30 Julv,2005July,2005,13,4) 的結(jié)果是：July,2005,Co ncatStr(S1,S2)的結(jié)果是:求子串函數(shù) SubStr(Today is 30July o在串的運算中，EqualStr(aaa,aab) 的返回值為 data=xp=head-n ex

8、t;while (p !=NULL) & ( p-data!=a )p=p-nextif (p=NULL)coutnextp-n ext=s(2)假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設(shè)一個隊尾指針rear，試填空完成向循環(huán)隊列中插入一個元素為x的結(jié)點的函數(shù)。typ edef struct queue node int data;struct queue node *n ext;QueueNode;In Queue(QueueNode *rear,i nt x) QueueNode *rear;QueueNode *head,*s;s= new QueueNode/定義隊列的存儲結(jié)構(gòu)/

9、向隊列插入元素為x的函數(shù)s-data= X : if(rear=NULL) rear=s; rear-n ext; else head=rear- nextrear- n ext=srear=s;rear- n ext=head;/循環(huán)隊列為空，則建立一個結(jié)點的循環(huán)隊列/循環(huán)隊列非空，則將s插到后面(3)下面程序是把兩個串 r1和r2首尾相連的程序，即：r1=r1+r2，試完成程序填空。typ edef Struct char vecMAXLEN;int len;St ;void Con catStr(Str *r1,Str *r2) /定義合并后串的最大長度/ len為串的長度/字符串連接函

10、數(shù)int i;coutvecvec;if(r1-le n+r2-le nMAXLEN )cout兩個串太長，溢出！ elseH.for(i=0;ilen;i+)r1-vec r1-len+i =r2-veci; r1-vecr1-le n+i=0;r1-le n=r1-le n+r2-le n:/把r2連接到r1/添上字符串結(jié)束標(biāo)記/修改新串長度(4)下面算法是判斷字符串是否為回文(即正讀和倒讀相同)，試完成程序填空。#in eludestdio.htyp edefstruct charvecMAXLEN;intlen;str;voidP ali ndrome (str s) int i=0;

11、ing j=s.le n-1while(i-i=1)if ( s.veci=s.vecN)i+;j-;c ontinue11(或 j=j+1)elsebreak;if (j-i=1)coutlt is not a p ali ndromen;elsecoutIt is a p ali ndromen;(5)void Bln sSort()/按遞增序?qū)1R n 進(jìn)行二分插入排序 int i, j, low, high, m;for( i=2;i=n ; i+) R0=Ri;/設(shè)定R0為監(jiān)視哨low=1;high=while(low=high)m=(low+high)/2if(R0=high+1

12、;j-)Ri+1= R j /元素后移Rhigh=R0;/插入ACDBGIHF和 ABCDEFGHI四、應(yīng)用題（1）已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為:請畫出該二叉樹，并寫出它的前序遍歷的序列。解：恢復(fù)的二叉樹為：其前序遍歷的序列為：E B A D C F H G I(2) 把下列一般樹轉(zhuǎn)換為二叉樹解:H解:ABGCDK解：還原后的二叉樹為:（5）假設(shè)用于通信的電文僅由 的頻率分別為7， 解：以權(quán)值：19, 2, 6, 32, 3, 21,B、C、D、E、F、G 8個字母組成，字母在電文中出現(xiàn)10）試為這8個字母設(shè)計哈夫曼編碼）32構(gòu)造哈夫曼樹：（左子為0，右子為1。）2、3、6、

13、7、 10、 19、 21、字母編號對應(yīng)編碼出現(xiàn)頻率1A10107B0019C100002D10016E1132D100013E0121(6)有向圖如下圖所示，畫出鄰接矩陣和鄰接表解:鄰接矩陣1(010鄰接表度優(yōu)先搜索和按廣度優(yōu)先搜索進(jìn)行遍歷的結(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的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。08解:10110131011L。13(9)對于給定結(jié)點的關(guān)鍵字集合K=5(1),7, 3,1(2)解:試構(gòu)造一棵二叉

14、排序樹；求等概率情況下的平均查找長度(1)構(gòu)造二叉排序樹ASL。(2)ASL=(1*1+2*2+3*4+4*3)/10=2.91， 68， 20， 84， 27， 55， 11， 10， 79。 設(shè)散列表的長度為 13,散列函數(shù)為：H ( K)=K % 13。試畫出線性探測再散列解決沖突時 所構(gòu)造的散列表，并求出其平均查找長度。解：線性探測再散列解決沖突時所構(gòu)造的散列表：(10)給定結(jié)點的關(guān)鍵字序列為:19， 14， 23,141682755192084792311100123456789101112 平均查找長度 ASL= ( 1*6+2*1+3*3+4*1+9*1)/12=30/3=320

15、,（或 1.44）06, 18，寫出希爾排序每一趟排12 02 16 30 28 10 17 20 06 18d=21002160618121720302812021606171218 2030 28d=1(13)02 06 10已知數(shù)據(jù)序列10 18 412161718 20283010 , 18, 4, 3, 6 , 12 , 9 , 15,9 15寫出二路歸并排序的每一趟排序結(jié)果。3 6 121018 3 4 612 915第一趟排序結(jié)果341018 691215第二趟排序結(jié)果46910121518已知數(shù)據(jù)序列53，36，48,3(14)排序結(jié)果。解：53 36 48 36 60_ 7

16、18 4136,第三趟排序結(jié)果60 , 7, 18 , 41，寫出采用簡單選擇排序的每一趟（11）給定結(jié)點的關(guān)鍵字序列為：47, 7, 29, 11, 16, 92, 22, 8, 3,哈希表的長度為 11。設(shè)散列函數(shù)為：H （ K）=K % 11。試畫出平方探測再散列解決沖突時所構(gòu)造的散列表，并求 出其平均查找長度。解：平方探測再散列解決沖突時所構(gòu)造的散列表。01234567891011223 14792167 1298平均查找長度 ASL= （ 1*5+2*4）/9 = 13/9 = 5/3 （12）已知數(shù)據(jù)序列12 , 02, 16, 30, 28, 10, 17, 序的結(jié)果。（設(shè)d=5、2、1）解： d=5(7)316483660531841(718)418