練習題-參考附標準答案

1、第一、二章的練習題一、選擇題1數(shù)據(jù)結(jié)構(gòu)可以用二元組來表示，它包括（A）集合 K和 K 上的（ C）集合 R。A、數(shù)據(jù)元素B 、存儲結(jié)構(gòu) C 、元素之間的關(guān)系 D 、邏輯結(jié)構(gòu) 矚慫潤厲釤瘞睞櫪廡賴。2數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（A）。A、數(shù)據(jù)的存儲結(jié)構(gòu) B、數(shù)據(jù)結(jié)構(gòu)C、數(shù)據(jù)的邏輯結(jié)構(gòu) D、數(shù)據(jù)元素之間的關(guān)系 3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（A）結(jié)構(gòu)。A、邏輯B 、存儲 C、邏輯和存儲 D、物理4以下說法中正確的是（ D）。A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B 、數(shù)據(jù)項是數(shù)據(jù)的基本單位C、數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的各數(shù)據(jù)項的集合D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)5線性表的順序

2、存儲結(jié)構(gòu)是一種 （ A ）的存儲結(jié)構(gòu)， 線性表的鏈式存儲結(jié)構(gòu)是一種 （ B ） 的存儲結(jié)構(gòu)。 聞創(chuàng)溝燴鐺險愛氌譴凈。A、隨機存取B 、順序存取 C 、索引存取 D 、散列存取6對于一個線性，既要求能夠進行較快的插入和刪除，又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯 關(guān)系，則應(yīng)該選擇（ B ）。 殘騖樓諍錈瀨濟溆塹籟。A、順序存儲方式B、鏈式存儲方式C、散列存儲方式D、索引存儲方式7已知， L是一個不帶頭結(jié)點的單鏈表， p 指向其中的一個結(jié)點，選擇合適的語句實現(xiàn)在p 結(jié)點的后面插入 s 結(jié)點的操作（ B ）。 釅錒極額閉鎮(zhèn)檜豬訣錐。A、p-next=s ; s-next=p-next ;、 s-n

3、ext=p-next ; p-next=s ;彈貿(mào)攝爾霽斃攬磚鹵廡。p-next=s ; s-next=p ; D、 s-next=p ; p-next=s ;謀蕎摶篋飆鐸懟類蔣薔。8單鏈表中各結(jié)點之間的地址（）。 該題做了修改！A、必須連續(xù)、部分地址必須連續(xù)必須不連續(xù)、連續(xù)與否都可以9在一個長度為n 的順序表中向第i 個元素（0i1） 的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（鵝婭盡損鵪慘歷蘢鴛賴。A、刪除單鏈表中的第一個元素B 、刪除單鏈表中的最后一個元素C、在單鏈表第一個元素前插入一個新元素D、在單鏈表最后一個元素后插入一個新元素12在 n 個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作

4、是（ A ）。A、訪問第 i 個結(jié)點（ 1i n）和求第 i 個結(jié)點的直接前驅(qū)（ 2i n）B、在第 i 個結(jié)點后插入一個新結(jié)點（ 1 i n）C、刪除第 i 個結(jié)點（ 1i n）D 、將 n 個結(jié)點從小到大排序13向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（B ）個元素。A、 8B、63.5C、 63 D 、 7 籟叢媽羥為贍僨蟶練淨。14單鏈表的存儲密度（C）A、大于 1；B、等于 1；C 、小于 1； D 、不能確定15、鏈表不具備的特點（A）。A、可隨機訪問任結(jié)點B、插入刪除不需要移動元素C、不必事先估計存儲空間D、所需空間與其長度成正比16、非空的

5、單循環(huán)鏈表head的尾結(jié)點（由p 所指向）滿足（ C ）。A、 p-NULLB、p=NULLC、 p-next=head D 、p=head 預(yù)頌圣鉉儐歲齦訝驊糴。17若某表最常用的操作是在最后一個結(jié)點之后插入一個新結(jié)點或刪除最后一個結(jié)點，則采用 （ D ）存儲方式最節(jié)省時間。 滲釤嗆儼勻諤鱉調(diào)硯錦。A、單鏈表B、給出表頭結(jié)點的單循環(huán)鏈表 鐃誅臥瀉噦圣騁貺頂廡。C、雙向鏈表D、帶頭結(jié)點的雙循環(huán)鏈表 擁締鳳襪備訊顎輪爛薔。18、在一個長度為n（n1）的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（ ）操作與鏈表長度有關(guān)。贓熱俁閫歲匱閶鄴鎵騷。A、刪除單鏈表中第一個結(jié)點B、刪除單鏈表是最后一個結(jié)點C、在單鏈

6、表第一個結(jié)點前插入一個新結(jié)點D 、在單鏈表最后一個結(jié)點后插入一個新結(jié)點19、設(shè)有兩個長度為 n 的不帶頭結(jié)點的單鏈表，結(jié)點類型相同。其中，一個單鏈表 h1 是循環(huán)鏈表，而 另一個單鏈表 h2 是非循環(huán)鏈表，則（ B ）。 壇摶鄉(xiāng)囂懺蔞鍥鈴氈淚。A、對于兩個鏈表來說，刪除第一個結(jié)點的操作，其時間復(fù)雜度都是O（1）B、對于兩個鏈表來說，刪除最后一個結(jié)點的操作，其時間復(fù)雜度都是O（n）C、循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間D、h1和 h2是不同類型的變量20、下面程序段的時間復(fù)雜度為（C ）。void prime（int n）int i=2;shile（n%i!=0&isqrt（n） cout

7、n ”是一個素數(shù)！ ”endl;dlse coutn ”是一個素數(shù)！ ”endl;A、O（1）B、O（n）C、O（ n ）D、O（n2） 蠟變黲癟報倀鉉錨鈰贅。二、填空題1線性結(jié)構(gòu)中元素之間存在（ 1： 1）關(guān)系，樹型結(jié)構(gòu)中元素之間存在（1 ： n）關(guān)系，圖型結(jié)構(gòu)中元素之間存在（ m:n）關(guān)系。 買鯛鴯譖曇膚遙閆擷凄。2一個算法的時間復(fù)雜度是該算法包含的（簡單操作或原操作）的多少，一個算法的空間復(fù)雜度是指 該算法在運行過程中臨時占用的（存儲空間 ）的大小。 綾鏑鯛駕櫬鶘蹤韋轔糴。3當一個算法的時間復(fù)雜度與問題的 n 大小無關(guān)時，則表示為（ o（1） ）；成正比時，表示為（ o（n） ）， 成平

8、方時，則表示為（ 0（n 2） ）。 驅(qū)躓髏彥浹綏譎飴憂錦。4順序存儲的長度為 n 的線性表，在任何位置上插入和刪除操作的時間復(fù)雜度基本上都一樣。插入一 個元素大約移動表中的（ n/2 ）個元素，刪除一個元素時大約移動表中的（ （n-1）/2 ）個元素。 貓蠆驢繪 燈鮒誅髏貺廡。5在線性表的順序存儲方式中， 元素之間的邏輯關(guān)系是通過 （物理位置 ）來體現(xiàn)的； 在鏈式存儲方式， 元素之間的邏輯關(guān)系是通過（ 指針）體現(xiàn)的。 鍬籟饗逕瑣筆襖鷗婭薔。6對于一個長度為 n 的單鏈表，在已知的 p 結(jié)點后面插入一個新結(jié)點的時間復(fù)雜度為（ o（1） ），在 p 結(jié)點之前插入一個新結(jié)點的時間復(fù)雜度為（ o（n

9、） ），在給定值為 e 的結(jié)點之后插入一個新結(jié)點的時 間復(fù)雜度為（ o（n） ）。 構(gòu)氽頑黌碩飩薺齦話騖。7在雙向鏈表中，每個結(jié)點包含兩個指針域，一個指向（ 該結(jié)點的前驅(qū) ）結(jié)點，另一個指向（ 該結(jié) 點的后繼 ）結(jié)點。 輒嶧陽檉籪癤網(wǎng)儂號澩。8對于循環(huán)鏈表來講，逐個訪問各個結(jié)點的結(jié)束判斷條件是（最后一個結(jié)點的 next= 頭指針 ）。9. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 （ 前驅(qū) ） 結(jié)點，其余每個結(jié)點有且只有 （ 一個 ）個前驅(qū)結(jié)點；葉子結(jié) 點沒有 （ 后繼 ） 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以 （ 0 個或多個 ） 。 堯側(cè)閆繭絳闕絢勵蜆贅。10. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)

10、點數(shù)可以（ 0 個或多個 ） 。三、應(yīng)用題1閱讀下面程序段，計算它的時間復(fù)雜度，要求寫出計算過程。（1）for （j=1;j=n;j+）for （k=1;k=m;k+） +x; s+=x; n m n解：1= m=n*m 時間復(fù)雜度： o（n*m）j 1 k 1 j 1（ 2） i=s=0;while（sn） i+;s+=i; 解：假設(shè)共循環(huán) x次，則循環(huán)次數(shù)123 xi123 xs+11+21+2+3 1+2+3+ +x 識饒鎂錕縊灩筧嚌儼淒。循環(huán)結(jié)束條件： (1+2+3+ +x)n x(x+1)/2nx22n x 2n 時間復(fù)雜度： O( n )( 3) i=1;while(i=n) i=

11、i*3; 解：計算過程與上一題類似，所以省略。時間復(fù)雜度：o(log 3n)( 4) fact(int n) if(n=1)return 1;/ 語句 1elsereturn fact(n-1)*n;/ 語句 2解：語句 1 的運行時間是 o(1) ，語句 2 的運行時間是 fact(n-1) 的運行時間 T(n-1)+ 乘法運行 o(1) 。 凍鈹鋨勞臘鍇癇婦脛糴。所以 T(n)=T(n-1)+ o(1)=T(n-2)+ o(1)+ o(1)=T(n-2)+ 2*o(1)/T(1) 表示 n=1 時的運行時間，等于 o(1)=T(1)+ (n-1)*o(1)=n*o(1)= o(n) 時間復(fù)

12、雜度： o(n)(5) for (j=1;j=n;j+)for (k=1;k=j;k+) +x; s+=x; n j n解：1=j =1+2+3+ +n=n(n+1)/2j 1 k 1 j 12給定的數(shù)據(jù)結(jié)構(gòu)如圖所示，回答以下問題:(1)屬于哪一種邏輯結(jié)構(gòu)？ 恥諤銪滅縈歡煬鞏鶩錦。時間復(fù)雜度： 0(n 2)用二元組表示法給出該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)？ (2) 判斷(1)二元組表示A=(K，R)，其中：K=1,2,3,4,5,6R=rr=, 溈懼統(tǒng)庫。(2)二元組表示邏輯結(jié)構(gòu)：線性結(jié)構(gòu)(一對一關(guān)系) 鯊腎鑰詘褳鉀A=（K，R），其中：K=a,b,c,d,e,f,g,h,iR=r r=, 碩癘鄴頏謅攆

13、檸攜驤蘞。邏輯結(jié)構(gòu)：圖型結(jié)構(gòu)（多對多關(guān)系）提示：注意 g 結(jié)點的前驅(qū)和后繼3對下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出對應(yīng)的邏輯結(jié)構(gòu)圖形表示，并指出屬于哪一種結(jié)構(gòu)。（1）A= （ K， R），其中：K=a,b,c,d,e,f,g,hR=rr=,邏輯結(jié)構(gòu)：順序結(jié)構(gòu)(2) B= ( K， R)，其中：K=1,2,3,4,5,6R=rr=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) 閿擻輳嬪諫遷擇楨秘騖。邏輯結(jié)構(gòu)：圖型結(jié)構(gòu)(3) C= ( K，R)，其中：K=48,25,64,57,82,36,75R=r1,r2r1=, 氬嚕躑竄貿(mào)懇彈瀘頷澩。r2=,

14、釷鵒資贏車贖孫滅獅贅。其中，實線表示關(guān)系 r1 ，虛線表示關(guān)系 r2邏輯結(jié)構(gòu)：關(guān)系 r1 表示線性結(jié)構(gòu)，關(guān)系 r2 表示樹型結(jié)構(gòu)四、算法題1編寫有序表的插入算法，包括順序表和單鏈表。順序表：typedef structDataType dataMAXSIZE;int last;SeqList;int Insert_SeqList_sort(SeqList &L,DataType x)if(MAXSIZE=L.last+1)return -1;int i=0;while(i=L.last&L.datai=i;j-)L.dataj+1=L.dataj;L.datai=x;L.last+;retur

15、n 1;鏈表：typedef struct NodeDataType data;struct Node *next;LNode,*LinkList;void Insert_LinkList(LinkList LDataType x)LNode *s,*p=L;while(p-next&p-next-datanext ;s=new LNode;s-data =x;s-next =p-next ;p-next =s; 2編寫線性表的合并算法，包括順序表和單鏈表。 順序表： P22 算法 2-6 鏈表： P36 算法 2-193編寫刪除線性表中所有值為 x 的元素的算法，包括順序表和單鏈表。 順序表：void Delete(SeqList &L,DataType x) int i=0;while(i=L.last) if(L.datai=x) for(int k=i+1;knext!=NULL)if(p-next-data=x)q=p-next;p-next=q-next;delete q;elsep=p-next;4編寫刪除線性表中值相同的多余元素的算法，包括順序表