廣工2015數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目及答案

1、1《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)CC語言版語言版》第一章緒論單項選擇題單項選擇題1在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是_________。A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量2數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系被稱為______。A.數(shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)的基本操作C.程序的算法D.數(shù)據(jù)的邏輯結(jié)構(gòu)3在數(shù)據(jù)結(jié)構(gòu)中，與所使用計算機(jī)無關(guān)的是數(shù)據(jù)的_______。A.存儲結(jié)構(gòu)B.邏輯和物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理結(jié)構(gòu)4在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)之間的關(guān)系是通

2、過________體現(xiàn)的。A.數(shù)據(jù)在內(nèi)存的相對位置B.指示數(shù)據(jù)元素的指針C.數(shù)據(jù)的存儲地址D.指針5計算算法的時間復(fù)雜度是屬于一種_______。A.事前統(tǒng)計的方法B.事前分析估算的方法C.事后統(tǒng)計的方法D.事后分析估算的方法6在對算法的時間復(fù)雜度進(jìn)行估計的時候，下列最佳的時間復(fù)雜度是______。A.n2B.nlognC.nD.logn7設(shè)使用某算法對n個元素進(jìn)行處理，所需的時間是T(n)=100nlog2n200n2000，則該算法

3、的漸近時間復(fù)雜度為_______。A.O(1)B.O(n)C.O(200n)D.O(nlog2n)33.14.ni15.O(n)例題解析例題解析【例21】編寫一個算法將一個單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。解：該算法可以在遍歷原表的時候?qū)⒏鹘Y(jié)點的指針逆轉(zhuǎn)，從原表的第一個結(jié)點開始，頭結(jié)點的指針在最后修改成指向原表的最后一個結(jié)點，即新表的第一個結(jié)點。實現(xiàn)本題功能的函數(shù)如下：voidinverse(Lnodeh)s=hnexti

4、f(s==NULL)returnq=NULLp=swhile(p!=NULL)p=pnextsnext=q逆轉(zhuǎn)指針q=s指針前移s=phnext=q頭指針h的后繼是p【例22】編寫一算法將兩個按元素值遞增有序排列的單鏈表A和B歸并成一個按元素值遞增有序排列的單鏈表C。解：對于兩個或兩個以上的，結(jié)點按元素值有序排列的單鏈表進(jìn)行操作時，應(yīng)采用“指針平行移動，依次掃描完成”的方法。從兩表的第一個結(jié)點開始順鏈表逐個將對應(yīng)數(shù)據(jù)元素進(jìn)行比較，復(fù)制小