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

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

3、的漸近時(shí)間復(fù)雜度為_______。A.O(1)B.O(n)C.O(200n)D.O(nlog2n)33.14.ni15.O(n)例題解析例題解析【例21】編寫一個(gè)算法將一個(gè)單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。解：該算法可以在遍歷原表的時(shí)候?qū)⒏鹘Y(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的第一個(gè)結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針在最后修改成指向原表的最后一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。實(shí)現(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】編寫一算法將兩個(gè)按元素值遞增有序排列的單鏈表A和B歸并成一個(gè)按元素值遞增有序排列的單鏈表C。解：對(duì)于兩個(gè)或兩個(gè)以上的，結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行操作時(shí)，應(yīng)采用“指針平行移動(dòng)，依次掃描完成”的方法。從兩表的第一個(gè)結(jié)點(diǎn)開始順鏈表逐個(gè)將對(duì)應(yīng)數(shù)據(jù)元素進(jìn)行比較，復(fù)制小