莊2008數(shù)據(jù)結(jié)構習題集

《莊2008數(shù)據(jù)結(jié)構習題集》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構習題冊（僅供計算機和信息專業(yè)同學參考）計算機科學技術教研室二ＯＯ八年十一月44基礎篇習題1一、選擇題1計算機算法必須具備輸入、輸出、（B）等5個特性。A可行性、可移植性和可擴展性B可行性、確定性和有窮性C確定性、有窮性和穩(wěn)定性D易讀性、安全性和穩(wěn)定性2在數(shù)據(jù)結(jié)構中，從邏輯上可以把數(shù)據(jù)結(jié)構分為（D）A動態(tài)結(jié)構和靜態(tài)結(jié)構B緊湊結(jié)構和非緊湊結(jié)構C內(nèi)容結(jié)構和外部結(jié)構D線性結(jié)構和非線性結(jié)構3下面程序段的時間復雜性的量級為（D）For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)x=x+1;AO(1)BO(n)CO(n2)DO(

2、n3)4在數(shù)據(jù)結(jié)構中，與所使用的計算機無關的是數(shù)據(jù)的（A）結(jié)構A邏輯B存儲C邏輯和存儲D物理5數(shù)據(jù)結(jié)構在計算機中的表示是指（C）A數(shù)據(jù)的邏輯結(jié)構B數(shù)據(jù)結(jié)構C數(shù)據(jù)的存儲結(jié)構D數(shù)據(jù)元素之間的關系6下面（B）的時間復雜性最好，即執(zhí)行時間最短。AO(n)BO(logn)CO(nlogn)DO(n2)7下面程序段的時間復雜性的量級為（D）。Intfun(intn){I=1,s=1;While(s

3、;j

4、,f,g,h}R={r}r={,,,,,,}(2)B=(K,R),其中K＝{a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(3)B=(K,R),其中K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}三、計算題設n為整數(shù)，求下列各程序段的時間復雜度（1）i=1;k=2;While(i

5、1;j=0;While(i+j<=n)If(i>j)j=j+1;Elsei=i+1;(3)x=91;y=100While(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;44習題2一、選擇題1線性表是（A）A一個有限序列，可以為空B一個有限序列，不能為空C一個無限序列，可以為空D一個無限序列，不能為空2在一個長度為n的順序表中，向第iI個元素（1≤i≤n+1）位置插入一個新元素時，需要從后向前依次后移（B）個元素。An-iBn-i+1Cn-i-1Di3在一個順序表的表尾插入一個元素的時間復度的量級為（B）。AO(n)BO(1)CO(n2)DO(l

6、ogn)4表長為n的順序存儲的線性表，當在任意位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（D），刪除一個元素需要移動元素的平均個數(shù)為（A）A(n-1)/2BnC(n+1)/2Dn/25設單鏈表中指針p指向結(jié)點a，若要刪除p之后的結(jié)點（若存在），則需修改指針的操作為（A）。Ap->next=p->next->nextBp=p->nextCp=p->next->nextDnext=p6單鏈表的存儲密度為（C）。A大于1B等于5C小于1D不能確定7在一個單鏈表中，若要在p所指向的結(jié)點之后插入一個新結(jié)點，則需要相繼修改（B）個指針域的值。A1B2C3

7、D48在一個單鏈表中，若要在p所指向的結(jié)點之前插入一個新結(jié)點，則此算法的時間復雜度的量級為（A）。AO(n)BO(n/2)CO(1)DO(n1/2)9在一個帶頭結(jié)點的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點之前插入一個新結(jié)點，則需要相繼修改（C）個指針域的值。A2B3C4D6二、簡答題1什么叫線性表？它有哪些特點？2在鏈表的設計中，為什么通常采用帶頭結(jié)點的鏈表結(jié)構？3對比順序表與單鏈表，說明順序表與單鏈表的主要優(yōu)點和主要缺點。444試編寫算法實現(xiàn)順序表的逆置，即把順序表A中的數(shù)據(jù)元素（a1,a2,…,an）逆置為（an