考點(diǎn)1：數(shù)據(jù)結(jié)構(gòu)與算法

1、1.下列敘述中正確的是（ ）。答案：BA）所謂算法就是計(jì)算方法B）程序可以作為算法的一種描述方法C）算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果D）算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間題目解析:算法是一組有窮指令集，是解題方案的準(zhǔn)確而完整的描述。通俗地說，算法就是計(jì)算機(jī)解題的過程,重在解題方案的設(shè)計(jì)，并且不等于計(jì)算方法，故A和C選項(xiàng)不正確，程序的編制不可能優(yōu)于算法的設(shè)計(jì)，但算法的描述可以用程序、偽代碼、流程圖來描述，故B選項(xiàng)正確。算法要求執(zhí)行過程中所需要的基本運(yùn)算次數(shù)和時(shí)間最少，即時(shí)間復(fù)雜度最低，所以C選項(xiàng)不正確。正確答案為B。2.下列各序列中不是堆的是（ ）。答案：CA）(91,85,53,36,47,30,24

2、,12)B）(91,85,53,47,36,30,24,12)C）(47,91,53,85,30,12,24,36)D）(91,85,53,47,30,12,24,36)題目解析:堆可以看成一棵完全二叉樹：任一根節(jié)點(diǎn)>=左右孩子（或者<=）（大的叫大根堆，小的叫小根堆。）注意一個(gè)堆中的這種性質(zhì)有一致性，不能既有大于又有小于情況存在,這題可以這么做，把結(jié)點(diǎn)按照完全二叉樹畫出來就一目了然了。這個(gè)題目很明顯91是最大的根，而C選項(xiàng)是"左根右"的排序，那么91的左邊只有47，其他都在右邊，而右邊無法按照此順序排列，故選C。3.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是（ ）。

3、答案：AA）15B）16C）17D）18題目解析:對(duì)于滿二叉樹，葉子結(jié)點(diǎn)的數(shù)目等于2（n-1）,n為深度，這里就是2的5-1=4次方，就是16。4. 設(shè)二叉樹如下：則前序序列為（ ）。答案：AA）ABDEGCFHB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH題目解析:前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。故正確選項(xiàng)選A；B選項(xiàng)為中序遍歷。C選項(xiàng)為后序遍歷；D選項(xiàng)不正確。5.下列敘述中正確的是（ ）。答案：AA）循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)B）循環(huán)隊(duì)列是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)D）循環(huán)隊(duì)列的

4、插入運(yùn)算不會(huì)發(fā)生溢出現(xiàn)象題目解析:循環(huán)隊(duì)列屬于隊(duì)列的特例和棧同屬于線性結(jié)構(gòu)，C選項(xiàng)不正確。在順序隊(duì)列中,由于數(shù)組空間不夠而產(chǎn)生的溢出叫真溢出；順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)行入隊(duì)列操作的溢出稱為假溢出；假溢出是由于隊(duì)尾rear的值和隊(duì)頭front的值不能由所定義數(shù)組下界值自動(dòng)轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的，解決的辦法是把順序隊(duì)列所使用的存儲(chǔ)空間構(gòu)造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列，因此，順序隊(duì)列通常都采用順序循環(huán)隊(duì)列結(jié)構(gòu)；棧的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，故正確選項(xiàng)為A；B選項(xiàng)不正確。循環(huán)隊(duì)列雖然能解決由于假溢出，卻不能解決在順序隊(duì)列中,由于數(shù)組空間不夠而產(chǎn)生的溢出的真溢出，

5、故選項(xiàng)C不正確。6.下列敘述中正確的是（ ）。答案：DA）所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點(diǎn)B）所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）C）只有一個(gè)根結(jié)點(diǎn)，且只有一個(gè)葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D）沒有根結(jié)點(diǎn)或沒有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)題目解析:只有一個(gè)空節(jié)點(diǎn)的結(jié)構(gòu)也屬數(shù)據(jù)結(jié)構(gòu)，所以A和B選項(xiàng)不正確；有且只有一個(gè)根結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)才屬于線性結(jié)構(gòu)，其它的都屬于非線性結(jié)構(gòu)，故C選項(xiàng)不正確，正確選項(xiàng)為D。7.下列關(guān)于算法的描述中錯(cuò)誤的是（ ）。答案：DA）算法強(qiáng)調(diào)動(dòng)態(tài)的執(zhí)行過程，不同于靜態(tài)的計(jì)算公式B）算法必須能在有限個(gè)步驟之后終止C）算法設(shè)計(jì)必須考慮

6、算法的復(fù)雜度D）算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境題目解析:算法的優(yōu)劣取決自身的運(yùn)行效率，時(shí)間和空間復(fù)雜度高低，并不取決于運(yùn)行算法程序的環(huán)境，故D選項(xiàng)錯(cuò)誤。8. 設(shè)二叉樹如下：則中序序列為（ ）。答案：BA）ABDEGCFHB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH題目解析:中序遍歷（LDR）是指首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；故正確答案為B。9.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有（ ）。答案：BA）節(jié)省存儲(chǔ)空間B）插入與刪除運(yùn)算效率高C）便于查找D）排序時(shí)減少元素的比較次數(shù)題目解析:順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物

7、理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大（1），存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便效率高，使用靈活。缺點(diǎn)：存儲(chǔ)密度小（<1），存儲(chǔ)空間利用率低。故正確選項(xiàng)為B。10.深度為的完全二叉樹中共有125個(gè)結(jié)點(diǎn)，則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）。答案：BA）62B）63C）64D）65題目解析: 對(duì)于滿二叉樹，結(jié)點(diǎn)的數(shù)目等于2n-1，葉子結(jié)點(diǎn)數(shù)目為2n-1，n為深度，這里就是2的7次方-1，就是127個(gè)結(jié)點(diǎn)，葉子

8、結(jié)點(diǎn)是64個(gè)，然而題目中只有125個(gè)結(jié)點(diǎn)，說明少了兩個(gè)結(jié)點(diǎn)，那么就少了一個(gè)葉子結(jié)點(diǎn)，即63個(gè)。11.下列敘述中正確的是（ ）。答案：CA）所謂有序表是指在順序存儲(chǔ)空間內(nèi)連續(xù)存放的元素序列B）有序表只能順序存儲(chǔ)在連續(xù)的存儲(chǔ)空間內(nèi)C）有序表可以用鏈接存儲(chǔ)方式存儲(chǔ)在不連續(xù)的存儲(chǔ)空間內(nèi)D）任何存儲(chǔ)方式的有序表均能采用二分法進(jìn)行查找題目解析:有序表可以用順序存儲(chǔ)空間內(nèi)連續(xù)存放的元素序列來實(shí)現(xiàn)，也可以用鏈接存儲(chǔ)方式存儲(chǔ)在不連續(xù)的存儲(chǔ)空間內(nèi)，已達(dá)到邏輯上連續(xù)，存儲(chǔ)空間上不一定連續(xù)的效果。二分法進(jìn)行查找只適用于順序存儲(chǔ)的有序表。故選項(xiàng)C正確。12. 設(shè)二叉樹如下：則后序序列為（ ）。答案：CA）ABDEGCF

9、HB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH題目解析:后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。故正確選項(xiàng)為C。13.下列敘述中正確的是（ ）。答案：BA）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C）二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D）循環(huán)鏈表是非線性結(jié)構(gòu)題目解析:結(jié)點(diǎn)中盡管有兩個(gè)指針域但沒有分別指向兩個(gè)不同的結(jié)點(diǎn)就不是二叉鏈表，故A選項(xiàng)不正確；二叉樹是非線性結(jié)構(gòu)，即每個(gè)數(shù)據(jù)結(jié)點(diǎn)至多只有一個(gè)前驅(qū)，但可以有多個(gè)后繼。它可采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，故C選項(xiàng)不正確；循環(huán)鏈表是在單鏈表中，將終

10、端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)的線性結(jié)構(gòu)，故D選項(xiàng)不正確；當(dāng)結(jié)點(diǎn)中兩個(gè)指針分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)是為線性結(jié)構(gòu)，當(dāng)指向兩個(gè)不同的前驅(qū)或后繼結(jié)點(diǎn)時(shí)為非線性結(jié)構(gòu)，故B選項(xiàng)正確。14.設(shè)某二叉樹中共有140個(gè)結(jié)點(diǎn)，其中有40個(gè)度為1的結(jié)點(diǎn)。則（ ）。答案：DA）該二叉樹中有51個(gè)葉子結(jié)點(diǎn)B）該二叉樹中有50個(gè)葉子結(jié)點(diǎn)C）該二叉樹中有51個(gè)度為2的結(jié)點(diǎn)D）不可能有這樣的二叉樹題目解析:140個(gè)結(jié)點(diǎn)除去40個(gè)度為1的結(jié)點(diǎn)，說明有100個(gè)度為2的結(jié)點(diǎn)，而根據(jù)二叉樹性質(zhì)，這個(gè)數(shù)值無法得出故本題答案選D。15.帶鏈的棧與順序存儲(chǔ)的棧相比，其優(yōu)點(diǎn)是（ ）。答案：CA）入棧與退棧操作方便B）可

11、以省略棧底指針C）入棧操作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出D）以上都不對(duì)題目解析:帶鏈的棧與順序存儲(chǔ)的棧相比優(yōu)點(diǎn)是不受連續(xù)存儲(chǔ)空間大小的限制，即不需考慮棧滿的問題，故C選項(xiàng)正確。16.某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為（ ）。答案：BA）BADCB）DCBAC）CDABD）ABCD題目解析:在二叉樹前序遍歷中ABCD中A是根節(jié)點(diǎn)，二在后序遍歷中根結(jié)點(diǎn)位于最后，所以正確答案為B。17. 某系統(tǒng)結(jié)構(gòu)圖如下所示該系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)是（ ）。答案：AA）nB）1C）2D）3題目解析:系統(tǒng)結(jié)構(gòu)圖中的最大扇入數(shù)為系統(tǒng)圖中進(jìn)入某一節(jié)點(diǎn)的最大節(jié)點(diǎn)數(shù)，本系統(tǒng)圖中功能n.1節(jié)點(diǎn)輸

12、出節(jié)點(diǎn)為功能1到功能n,所以系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)為n,故正確選項(xiàng)為A。18.下列關(guān)于算法復(fù)雜度敘述正確的是（ ）。答案：BA）最壞情況下的時(shí)間復(fù)雜度一定高于平均情況的時(shí)間復(fù)雜度B）時(shí)間復(fù)雜度與所用的計(jì)算工具無關(guān)C）對(duì)同一個(gè)問題，采用不同的算法，則它們的時(shí)間復(fù)雜度是相同的D）時(shí)間復(fù)雜度與采用的算法描述語(yǔ)言有關(guān)題目解析:準(zhǔn)確把握算法復(fù)雜度的概念。19.設(shè)有棧S和隊(duì)列Q，初始狀態(tài)均為空。首先依次將A,B,C,D,E,F入棧，然后從棧中退出三個(gè)元素依次入隊(duì)，再將X,Y,Z入棧后，將棧中所有元素退出并依次入隊(duì)，最后將隊(duì)列中所有元素退出，則退隊(duì)元素的順序?yàn)椋?）。答案：BA）DEFXYZABCB）FED

13、ZYXCBAC）FEDXYZCBAD）DEFZYXABC題目解析:棧是一種特殊的線性表?xiàng)Ｖ械臄?shù)據(jù)時(shí)按照先進(jìn)后出或者是后進(jìn)先出的規(guī)則進(jìn)行的，隊(duì)列是同棧不太相同的線性結(jié)構(gòu)，進(jìn)出順序?yàn)橄冗M(jìn)先出的規(guī)則，根據(jù)題意要求本題正確答案為B選項(xiàng)。20.下列敘述中正確的是（ ）。答案：DA）有兩個(gè)指針域的鏈表稱為二叉鏈表B）循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C）帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表D）結(jié)點(diǎn)中具有多個(gè)指針域的鏈表稱為多重鏈表題目解析:結(jié)點(diǎn)中盡管有兩個(gè)指針域但沒有分別指向兩個(gè)不同的結(jié)點(diǎn)就不是二叉鏈表，故A選項(xiàng)不正確；循環(huán)鏈表是在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)的

14、線性結(jié)構(gòu)，故B選項(xiàng)不正確；當(dāng)結(jié)點(diǎn)中兩個(gè)指針分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)是為線性結(jié)構(gòu)，當(dāng)指向兩個(gè)不同的前驅(qū)或后繼結(jié)點(diǎn)時(shí)為非線性結(jié)構(gòu)，故B選項(xiàng)正確。雙重鏈表的結(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前驅(qū)，一個(gè)指向后繼，從一個(gè)結(jié)點(diǎn)既可以向前也可以向后才是雙重鏈表，故C選項(xiàng)不正確。D選項(xiàng)正確。21.某二叉樹共有845個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有45個(gè)，則度為1的結(jié)點(diǎn)數(shù)為（ ）。答案：CA）400B）754C）756D）不確定題目解析:二叉樹中，度為0的結(jié)點(diǎn)（即葉子節(jié)點(diǎn)）比度為2的結(jié)點(diǎn)多1個(gè)，而度為0、1、2的結(jié)點(diǎn)相加等于總結(jié)點(diǎn)數(shù)845，所以度為1的結(jié)點(diǎn)數(shù)為845-45-（45-1）=756。22.深度為7的二叉樹共有127個(gè)

15、結(jié)點(diǎn)，則下列說法中錯(cuò)誤的是（ ）。答案：AA）該二叉樹有一個(gè)度為1的結(jié)點(diǎn)B）該二叉樹是滿二叉樹C）該二叉樹是完全二叉樹D）該二叉樹有64個(gè)葉子結(jié)點(diǎn)題目解析:大家一定要記清楚這幾個(gè)二叉樹的性質(zhì)。23.下列敘述中正確的是（ ）。答案：DA）非線性結(jié)構(gòu)只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B）非線性結(jié)構(gòu)只能用多重鏈表表示C）所有數(shù)據(jù)結(jié)構(gòu)既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D）有的非線性結(jié)構(gòu)也能采用順序存儲(chǔ)結(jié)構(gòu)題目解析:鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)，非線性結(jié)構(gòu)也可以用連續(xù)存儲(chǔ)空間順序存儲(chǔ)。所以AB選項(xiàng)不正確在所有的數(shù)據(jù)結(jié)構(gòu)中并非所有的結(jié)構(gòu)都能用順序存儲(chǔ)結(jié)構(gòu)和采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示，故

16、選項(xiàng)C不正確，D選項(xiàng)正確。24.某二叉樹的中序序列為BDCA，后序序列為DCBA，則前序序列為（ ）。答案：CA）DCBAB）BDCAC）ABCDD）BADC題目解析:在二叉樹后序遍歷中DCBA中A是根節(jié)點(diǎn)，二在前序遍歷中根結(jié)點(diǎn)位于首位，所以正確答案為B。25. 某系統(tǒng)結(jié)構(gòu)圖如下圖所示該系統(tǒng)結(jié)構(gòu)圖的最大扇出數(shù)是（ ）。答案：DA）1B）2C）3D）n題目解析: 系統(tǒng)結(jié)構(gòu)圖中的最大扇出數(shù)為系統(tǒng)圖中某一節(jié)點(diǎn)輸出的最大節(jié)點(diǎn)數(shù)，本系統(tǒng)圖中某系統(tǒng)輸出節(jié)點(diǎn)為功能1到功能n,所以系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)為n,故正確選項(xiàng)為D。26.設(shè)有序線性表的長(zhǎng)度為n，則在有序線性表中進(jìn)行二分查找，最壞情況下的比較

17、次數(shù)為（ ）。答案：DA）n(n-1)/2B）nC）nlog2 nD）log2 n題目解析:二分法查找只適用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比較log2n次，而順序查找需要比較n次。故正確選項(xiàng)為D。27.某完全二叉樹共有256個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（ ）。答案：CA）7B）8C）9D）10題目解析: 根據(jù)"二叉樹的第i層至多有2(i ? 1)個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2k ? 1個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)的深度為1）".這個(gè)性質(zhì)：因?yàn)榍熬艑拥慕Y(jié)點(diǎn)就有29-1=511個(gè)；而第九層的結(jié)點(diǎn)數(shù)是2(9-1)

18、=256。28.設(shè)序列長(zhǎng)度為n,在最壞情況下比較次數(shù)低于O（n2）的排序方法是（ ）。答案：DA）快速排序B）直接插入排序C）冒泡排序D）希爾排序題目解析:大家一定要熟悉這幾種排序方法的性質(zhì)。29.某二叉樹的前序序列為ABCD，中序序列為BDCA，則該二叉樹的深度為（ ）。答案：AA）4B）3C）2D）不確定題目解析:首先還原二叉樹，然后再次進(jìn)行排序。30.下列排序方法中，最壞情況下時(shí)間復(fù)雜度最低的是（ ）。答案：DA）冒泡排序B）快速排序C）希爾排序D）堆排序題目解析:堆排序法，最壞情況需要O(nlog2n)次比較。  相比以上幾種(除希爾排序法外)，堆排序法的時(shí)間復(fù)雜度

19、最小，故D選項(xiàng)正確。31.設(shè)循環(huán)隊(duì)列為Q(1:m)，初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)一系列入隊(duì)與退隊(duì)操作后，front=rear=m-1，則（ ）。答案：DA）該循環(huán)隊(duì)列已空B）該循環(huán)隊(duì)列已滿C）該循環(huán)隊(duì)列中有1個(gè)元素D）該循環(huán)隊(duì)列已空或已滿題目解析:循環(huán)隊(duì)列m=0表示隊(duì)列空；s=1且front=rear表示隊(duì)列滿。所以選項(xiàng)D正確。32.設(shè)序列長(zhǎng)度為n，在最壞情況下，時(shí)間復(fù)雜度為O（log2n）的算法是（ ）。答案：AA）二分法查找B）順序查找C）分塊查找D）哈希查找題目解析:二分法查找只適用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比較log2n次，而順序查找需要比較

20、n次。故正確選項(xiàng)為A。33.某二叉樹的深度為7，其中有64個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為1的結(jié)點(diǎn)數(shù)為（ ）。答案：AA）0B）1C）2D）63題目解析:2的7-1次方已經(jīng)是64了，所以度為1的結(jié)點(diǎn)一定是0。34.堆排序最壞情況下的時(shí)間復(fù)雜度為（ ）。答案：BA）O(n1.5)B）O(nlog2n)C）D）O(log2n)題目解析:堆排序法，最壞情況需要O(nlog2n)次比較，堆排序法的時(shí)間復(fù)雜度最小，故B選項(xiàng)正確。35.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間一般是不連續(xù)的，并且（ ）。答案：CA）前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)小于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)B）前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)C）前件結(jié)點(diǎn)的存

21、儲(chǔ)序號(hào)可以小于也可以大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)D）以上都不對(duì)題目解析:鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使得節(jié)點(diǎn)在內(nèi)存中不收位置的限制，結(jié)點(diǎn)存儲(chǔ)號(hào)可以是任意的，并且能夠保證邏輯上的線性關(guān)系。故C選項(xiàng)正確。36.某二叉樹中有15個(gè)度為1的結(jié)點(diǎn)，16個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（ ）。答案：CA）32B）46C）48D）49題目解析:二叉樹有一個(gè)性質(zhì)是：對(duì)任何二叉樹，如果其終端結(jié)點(diǎn)數(shù)位n0，度為2的結(jié)點(diǎn)數(shù)為n2則n0=n2+1，所以度為0的一共有17個(gè)，總的結(jié)點(diǎn)數(shù)即時(shí)17+15+16=48個(gè)。37. 某系統(tǒng)結(jié)構(gòu)圖如下圖所示該系統(tǒng)結(jié)構(gòu)圖中最大扇入是（ ）。答案：CA）0B）1C）2D）3題目解析: 系統(tǒng)

22、結(jié)構(gòu)圖中的最大扇入數(shù)為系統(tǒng)圖中輸入某一節(jié)點(diǎn)的最大節(jié)點(diǎn)數(shù)，本系統(tǒng)圖中某系統(tǒng)輸入節(jié)點(diǎn)為功能1到功能3n,所以系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)為3,故正確選項(xiàng)為C。38.下列敘述中正確的是（ ）。答案：DA）每一個(gè)結(jié)點(diǎn)有兩個(gè)指針域的鏈表一定是非線性結(jié)構(gòu)B）所有結(jié)點(diǎn)的指針域都為非空的鏈表一定是非線性結(jié)構(gòu)C）循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D）線性結(jié)構(gòu)的存儲(chǔ)結(jié)點(diǎn)也可以有多個(gè)指針題目解析:當(dāng)結(jié)點(diǎn)中兩個(gè)指針分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)是為線性結(jié)構(gòu)，當(dāng)指向兩個(gè)不同的前驅(qū)或后繼結(jié)點(diǎn)時(shí)為非線性結(jié)構(gòu)，指針域?yàn)榉强盏逆湵硪部梢允蔷€性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。故A、B、C選項(xiàng)不完全正確。線性結(jié)

23、構(gòu)的存儲(chǔ)結(jié)點(diǎn)可以由多個(gè)指針只有保證有且只有指向一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)就是線性結(jié)構(gòu)。故D選項(xiàng)正確；。39.在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù)（ ）。答案：AA）相同，元素的存儲(chǔ)順序與邏輯順序一致B）相同，但其元素的存儲(chǔ)順序可以與邏輯順序不一致C）不同，但元素的存儲(chǔ)順序與邏輯順序一致D）不同，且其元素的存儲(chǔ)順序可以與邏輯順序不一致題目解析:線性表的順序存儲(chǔ)結(jié)構(gòu)的兩個(gè)特點(diǎn)（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。另在線性表中數(shù)據(jù)元素所占的字節(jié)數(shù)都是一致的，所以正確選項(xiàng)為A。40.設(shè)循環(huán)隊(duì)列為Q(1: m)

24、，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=30，rear=10?，F(xiàn)要在該循環(huán)隊(duì)列中作順序查找，最壞情況下需要比較的次數(shù)為（ ）。答案：DA）19B）20C）m-19D）m-20題目解析:二分法查找只適用于順序存儲(chǔ)的有序表，對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比較log2n次，而順序查找需要比較n次。已知循環(huán)隊(duì)列為Q(1: m)，其初始狀態(tài)為front=rear=m，而節(jié)點(diǎn)個(gè)數(shù)為m-(front-rear),且順序查找的比較次數(shù)與實(shí)際節(jié)點(diǎn)個(gè)數(shù)一致，故正確選項(xiàng)為D。41.某二叉樹中共有935個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有435個(gè)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)

25、數(shù)為（ ）。答案：DA）64B）66C）436D）434題目解析:大家記住一個(gè)公式，n0=n2+1，所以n2有434個(gè)。42. 某系統(tǒng)結(jié)構(gòu)圖如下圖所示該系統(tǒng)結(jié)構(gòu)圖中最大扇出數(shù)是（ ）。答案：CA）1B）23C）3D）4題目解析:系統(tǒng)結(jié)構(gòu)圖中的最大扇出數(shù)為系統(tǒng)圖中某一節(jié)點(diǎn)輸出的最大節(jié)點(diǎn)數(shù)，本系統(tǒng)圖中某系統(tǒng)輸出節(jié)點(diǎn)為功能1到功能3,所以系統(tǒng)結(jié)構(gòu)圖的最大扇入數(shù)為3,故正確選項(xiàng)為C。43.算法的有窮性是指（ ）。答案：AA）算法程序的運(yùn)行時(shí)間是有限的B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長(zhǎng)度是有限的D）算法只能被有限的用戶使用題目解析:算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后

26、即可完成。有窮性是指算法程序的運(yùn)行時(shí)間是有限的。44.對(duì)長(zhǎng)度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n1)/2的排序方法是（ ）。答案：DA）快速排序B）冒泡排序C）直接插入排序D）堆排序題目解析:在最壞的情況下，堆排序需要比較的次數(shù)為O(nlog2n)，所以選擇D.45.下列關(guān)于棧的敘述正確的是（ ）。答案：BA）棧按"先進(jìn)先出"組織數(shù)據(jù)B）棧按"先進(jìn)后出"組織數(shù)據(jù)C）只能在棧底插入數(shù)據(jù)D）不能刪除數(shù)據(jù)題目解析:棧是按照"先進(jìn)后出"的原則組織數(shù)據(jù)的，只能在棧頂插入或刪除數(shù)據(jù)，所以選擇B。46.一個(gè)棧的初始狀態(tài)為空。現(xiàn)將元素1

27、、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。答案：BA）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA題目解析:棧是先進(jìn)后出的原則組織數(shù)據(jù)，所以入棧最早的最后出棧，所以選擇B。47.下列敘述中正確的是（ ）。答案：DA）循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)B）在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況C）在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D）循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定題目解析:循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，但是循環(huán)隊(duì)列

28、仍是線性結(jié)構(gòu)的，所以A）錯(cuò)誤；在循環(huán)隊(duì)列中只需要隊(duì)頭指針與隊(duì)尾兩個(gè)指針來共同反映隊(duì)列中元素的動(dòng)態(tài)變化情況，所以B）與C）錯(cuò)誤。48.在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是（ ）。答案：CA）O(n)B）C）D）題目解析:當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能用二分法查找?？梢宰C明的是對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分法查找只需要比較O(nlog2n)次，而順序查找需要比較n次。49.下列敘述中正確的是（ ）。答案：AA）順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的B）順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)C）順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)

29、有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間題目解析:鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以針對(duì)線性結(jié)構(gòu)也可以針對(duì)非線性結(jié)構(gòu)，所以B）與C）錯(cuò)誤。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)都由數(shù)據(jù)域與指針域兩部分組成，增加了存儲(chǔ)空間，所以D）錯(cuò)誤。50.在數(shù)據(jù)管理技術(shù)發(fā)展的三個(gè)階段中，數(shù)據(jù)共享最好的是（ ）。答案：CA）人工管理階段B）文件系統(tǒng)階段C）數(shù)據(jù)庫(kù)系統(tǒng)階段D）三個(gè)階段相同題目解析:據(jù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。其中最后一個(gè)階段結(jié)構(gòu)簡(jiǎn)單，使用方便邏輯性強(qiáng)物理性少，在各方面的表現(xiàn)都最好，一直占據(jù)數(shù)據(jù)庫(kù)領(lǐng)域的主導(dǎo)地位，所以選擇C）。51.下列敘述中正確

30、的是（ ）。答案：DA）棧是"先進(jìn)先出"的線性表B）隊(duì)列是"先進(jìn)后出"的線性表C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)D）有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)題目解析:棧是先進(jìn)后出的線性表，所以A）錯(cuò)誤；隊(duì)列是先進(jìn)先出的線性表，所以B）錯(cuò)誤；循環(huán)隊(duì)列是線性結(jié)構(gòu)的線性表，所以C）錯(cuò)誤。52.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（ ）。答案：AA）棧B）樹C）隊(duì)列D）二叉樹題目解析:棧支持子程序調(diào)用。棧是一種只能在一端進(jìn)行插入或刪除的線性表，在主程序調(diào)用子函數(shù)時(shí)要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，最終把子程序的執(zhí)行結(jié)果返回到主程序中調(diào)用子程序的位置，繼

31、續(xù)向下執(zhí)行，這種調(diào)用符合棧的特點(diǎn)，因此本題的答案為A）。53.某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是（ ）。答案：CA）10B）8C）6D）4題目解析:根據(jù)二叉樹的基本性質(zhì)3：在任意一棵二叉樹中，度為0的葉子節(jié)點(diǎn)總是比度為2的節(jié)點(diǎn)多一個(gè)，所以本題中是516個(gè)。54.下列排序方法中，最壞情況下比較次數(shù)最少的是（ ）。答案：DA）冒泡排序B）簡(jiǎn)單選擇排序C）直接插入排序D）堆排序題目解析:冒泡排序與簡(jiǎn)單插入排序與簡(jiǎn)單選擇排序法在最壞情況下均需要比較n(n1)/2次，而堆排序在最壞情況下需要比較的次數(shù)是nlog2n。55.下列敘述中正確的是（ ）。答案：CA）在棧中，棧中元素隨棧底指

32、針與棧頂指針的變化而動(dòng)態(tài)變化B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化D）在棧中，棧中元素不會(huì)隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化題目解析:棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，在整個(gè)過程中，棧底指針不變，入棧與出棧操作均由棧頂指針的變化來操作，所以選擇C)。56.某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為（假設(shè)根結(jié)點(diǎn)在第1層）（ ）。答案：DA）3B）4C）6D）7題目解析:根據(jù)二叉樹的基本性質(zhì)3：在任意一棵二叉樹中，度為0的葉子節(jié)點(diǎn)總比度為2的節(jié)點(diǎn)多一個(gè)，所以本題中度為2的節(jié)點(diǎn)為110個(gè)，所以可以知道本題目

33、中的二叉樹的每一個(gè)節(jié)點(diǎn)都有一個(gè)分支，所以共7個(gè)節(jié)點(diǎn)共7層，即深度為7。57.下列敘述中正確的是（ ）。答案：DA）算法就是程序B）設(shè)計(jì)算法時(shí)只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)C）設(shè)計(jì)算法時(shí)只需要考慮結(jié)果的可靠性D）以上三種說法都不對(duì)題目解析:算法是指解題方案的準(zhǔn)確而完整的描述，算法不等于程序，也不等于計(jì)算方法，所以A）錯(cuò)誤。設(shè)計(jì)算法時(shí)不僅要考慮對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)，所以B）和C）錯(cuò)誤。58.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（ ）。答案：CA）循環(huán)隊(duì)列B）帶鏈隊(duì)列C）二叉樹D）帶鏈棧題目解析:樹是簡(jiǎn)單的非線性結(jié)構(gòu)，所以二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)。59.下列數(shù)據(jù)結(jié)構(gòu)中，

34、能夠按照"先進(jìn)后出"原則存取數(shù)據(jù)的是（ ）。答案：BA）循環(huán)隊(duì)列B）棧C）隊(duì)列D）二叉樹題目解析:棧是按先進(jìn)后出的原則組織數(shù)據(jù)的。隊(duì)列是先進(jìn)先出的原則組織數(shù)據(jù)。因此，本題答案為B）。60.對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是（ ）。答案：DA）隊(duì)頭指針是固定不變的B）隊(duì)頭指針一定大于隊(duì)尾指針C）隊(duì)頭指針一定小于隊(duì)尾指針D）隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針題目解析:循環(huán)隊(duì)列的隊(duì)頭指針與隊(duì)尾指針都不是固定的，隨著入隊(duì)與出隊(duì)操作要進(jìn)行變化。因?yàn)槭茄h(huán)利用的隊(duì)列結(jié)構(gòu)所以對(duì)頭指針有時(shí)可能大于隊(duì)尾指針有時(shí)也可能小于隊(duì)尾指針。61.算法的空間復(fù)雜度是指（ ）。答案：AA）算法在執(zhí)

35、行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語(yǔ)句或指令條數(shù)D）算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)題目解析:算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。所以選擇A）。62.下列敘述中正確的是（ ）。答案：BA）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間是相同的B）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)C）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)D）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間與順序存儲(chǔ)結(jié)構(gòu)沒有任何關(guān)系題目解析:線性鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)都由數(shù)據(jù)域與指針域兩部分組成，增加了存儲(chǔ)空間，所以一般要多于順序存儲(chǔ)結(jié)

36、構(gòu)。63.下列敘述中正確的是（ ）。答案：DA）棧是一種先進(jìn)先出的線性表B）隊(duì)列是一種后進(jìn)先出的線性表C）棧與隊(duì)列都是非線性結(jié)構(gòu)D）棧與隊(duì)列都是線性結(jié)構(gòu)題目解析:棧是一種先進(jìn)后出的線性表，隊(duì)列是一種先進(jìn)先出的線性表，棧與隊(duì)列都是線性結(jié)構(gòu)。64.下列敘述中正確的是（ ）。答案：BA）有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B）只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C）循環(huán)鏈表是非線性結(jié)構(gòu)D）雙向鏈表是非線性結(jié)構(gòu)題目解析:線性結(jié)構(gòu)應(yīng)滿足：有且只有一個(gè)根結(jié)點(diǎn)與每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件，所以B）正確。所以有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)，所以A）錯(cuò)誤。循環(huán)鏈表和雙向鏈表

37、都是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，所以C）和D）錯(cuò)誤。65.下列關(guān)于二叉樹的敘述中，正確的是（ ）。答案：BA）葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)B）葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)C）葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍D）度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍題目解析:根據(jù)二叉樹的基本性質(zhì)：在任意一棵二叉樹中，度為0的葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。所以選擇B）。66.某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是：（ ）。答案：CA）7B）6C）3D）2題目解析:根據(jù)總體結(jié)構(gòu)圖可以看出該樹的深度為3，比如：XY系統(tǒng)功能2功能2.1，就是最深的度數(shù)的一個(gè)表現(xiàn)。67.下列敘述中正確的是（ ）。答案：B

38、A）循環(huán)隊(duì)列是隊(duì)列的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B）循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)D）循環(huán)隊(duì)列是一種邏輯結(jié)構(gòu)題目解析:在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。68.下列關(guān)于線性鏈表的敘述中，正確的是（ ）。答案：CA）各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B）各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C）進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D）各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，它們的存儲(chǔ)空間也可以不一致題目解析:一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的

39、位置關(guān)系與邏輯關(guān)系也不一致。線性鏈表中數(shù)據(jù)的插入和刪除都不需要移動(dòng)表中的元素，只需改變結(jié)點(diǎn)的指針域即可。69.一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為（ ）。答案：AA）16B）10C）6D）4題目解析:根據(jù)二叉樹的性質(zhì)3：在任意一棵二叉樹中，度為0的葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)，所以本題中度為2的結(jié)點(diǎn)是5-14個(gè)，所以度為1的結(jié)點(diǎn)的個(gè)數(shù)是25-5-416個(gè)。70.在滿足實(shí)體完整性約束的條件下（ ）。答案：AA）一個(gè)關(guān)系中應(yīng)該有一個(gè)或多個(gè)候選關(guān)鍵字B）一個(gè)關(guān)系中只能有一個(gè)候選關(guān)鍵字C）一個(gè)關(guān)系中必須有多個(gè)候選關(guān)鍵字D）一個(gè)關(guān)系中可以沒有候選關(guān)鍵字題目解析:實(shí)體完整性

40、約束要求關(guān)系的主鍵中屬性值不能為空值，所以選擇A）。71.下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是（ ）。答案：AA）二叉鏈表B）循環(huán)鏈表C）雙向鏈表D）帶鏈的棧題目解析:二叉鏈表是二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，屬于非線性結(jié)構(gòu)，其余選項(xiàng)均屬于線性結(jié)構(gòu)，所以選擇A）。72.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1: 35)，初始狀態(tài)為front=rear=35?，F(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。答案：DA）15B）16C）20D）0或35題目解析:front=rear，說明隊(duì)列為滿或者為空，所以答案選擇D）。73.下列關(guān)于棧的敘述中，正確的是（ ）。答案

41、：CA）棧底元素一定是最后入棧的元素B）棧頂元素一定是最先入棧的元素C）棧操作遵循先進(jìn)后出的原則D）以上三種說法都不對(duì)題目解析:棧操作遵循先進(jìn)后出的原則，棧底元素一定是最先入棧的元素，棧頂元素一定是最后入棧的元素，所以選擇C）。74.下列敘述中正確的是（ ）。答案：AA）程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D）以上三種說法都不對(duì)題目解析:采用的存儲(chǔ)結(jié)構(gòu)不同，其數(shù)據(jù)處理的效率是不同的，程序執(zhí)行的效率也就不同，因此選項(xiàng)A）是正確的。程序執(zhí)行的效率不僅與程序的控制結(jié)構(gòu)有關(guān)，而且與所處理的數(shù)據(jù)量有關(guān)，因此選項(xiàng) B）、C）

42、、D）都不正確。75.下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是（ ）。答案：DA）函數(shù)的遞歸調(diào)用B）數(shù)組元素的引用C）多重循環(huán)的執(zhí)行D）先到先服務(wù)的作業(yè)調(diào)度題目解析:隊(duì)列是按照先進(jìn)先出的原則組織數(shù)據(jù)的，可以看出以下四個(gè)選項(xiàng)中，與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是D）選項(xiàng)。76.（ ）。答案：CA）DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ題目解析:前序遍歷的過程是首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。根據(jù)圖可以分析出，該二叉樹的前序遍歷結(jié)果為C）。77.一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1,2,3,A,

43、B,C依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。答案：CA）1,2,3,A,B,CB）C,B,A,1,2,3C）C,B,A,3,2,1D）1,2,3,C,B,A題目解析:棧是先進(jìn)后出的原則組織數(shù)據(jù)，所以入棧最早的最后出棧，所以選擇C)。78.下列敘述中正確的是（ ）。答案：DA）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大B）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小D）算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系題目解析:算法的時(shí)間復(fù)雜度是指之行算法所需要的計(jì)算工作量；算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，兩者之間沒有直接

44、關(guān)系。79.下列敘述中正確的是（ ）。答案：AA）循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化B）循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針的變化而動(dòng)態(tài)變化C）循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)尾指針的變化而動(dòng)態(tài)變化D）以上說法都不對(duì)題目解析:循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化，選A）。80.一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為（ ）。答案：BA）219B）229C）230D）231題目解析:根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)，葉子結(jié)點(diǎn)為80，度為2的結(jié)點(diǎn)為79，所以總結(jié)點(diǎn)數(shù)為：80+70+79=229，選B

45、）。81.對(duì)長(zhǎng)度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為（ ）。答案：CA）9B）10C）45D）90題目解析:在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為n(n-1)/2，為45，答案選C）。82.下列敘述中正確的是（ ）。答案：BA）算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)B）算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D）算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)題目解析:算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)，與算法的空間復(fù)雜度沒有關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)位置無關(guān)，即與存儲(chǔ)結(jié)構(gòu)無關(guān)，所以選擇B）。83

46、.下列敘述中正確的是（ ）。答案：CA）線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)B）線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的C）線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的D）以上說法都不對(duì)題目解析:在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的，所以選擇C）。84.某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為（根結(jié)點(diǎn)在第1層）（ ）。答案：DA）3B）6C）8D）12題目解析:根據(jù)二叉樹的性質(zhì)，葉子結(jié)點(diǎn)比度為2的結(jié)點(diǎn)個(gè)數(shù)多一個(gè)，葉子結(jié)

47、點(diǎn)只有1個(gè)，那么度為2的結(jié)點(diǎn)為0個(gè)，可以得出共有11個(gè)度為1的結(jié)點(diǎn)，那么該二叉樹每一層上只能有一個(gè)結(jié)點(diǎn)，共12層，即深度為12。85.對(duì)長(zhǎng)度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為（ ）。答案：DA）nB）n-1C）n(n-1)D）n(n-1)/2題目解析:在最壞情況下，快速排序需要比較n(n-1)/2次。86.下列敘述中正確的是（ ）。答案：DA）有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)B）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)C）有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)D）有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)題目解析:有且只

48、有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)，如隊(duì)列，也可以是非線性結(jié)構(gòu)，如二叉樹，所以選項(xiàng)D）正確。選項(xiàng)B）中，如果有兩個(gè)根結(jié)點(diǎn)，則不符合線性結(jié)構(gòu)的條件，說法錯(cuò)誤。本題答案選D）。87.下列敘述中錯(cuò)誤的是（ ）。答案：CA）在雙向鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)B）在循環(huán)鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)C）在線性單鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)D）在二叉鏈表中，可以從根結(jié)點(diǎn)開始遍歷到所有結(jié)點(diǎn)題目解析:在線性單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后件結(jié)點(diǎn)，但不能找到前件結(jié)點(diǎn)，選項(xiàng)C）說法錯(cuò)誤。88.某二叉樹共有13個(gè)結(jié)點(diǎn)，其中有4個(gè)度為

49、1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為（ ）。答案：AA）5B）4C）3D）2題目解析:在線性單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后件結(jié)點(diǎn)，但不能找到前件結(jié)點(diǎn)，選項(xiàng)C）說法錯(cuò)誤。89.設(shè)棧的順序存儲(chǔ)空間為S(1: 50),初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列入棧與退棧運(yùn)算后，top=20，則當(dāng)前棧中的元素個(gè)數(shù)為（ ）。答案：CA）30B）29C）20D）19題目解析:在棧中，top位置直接反映棧中元素的個(gè)數(shù)，top=20，則說明當(dāng)前棧中的元素個(gè)數(shù)為20。90.下列敘述中正確的是（ ）。答案：BA）棧與隊(duì)列都只能順序存儲(chǔ)B）循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)C）循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D）以

50、上說法都不對(duì)題目解析:棧和隊(duì)列都可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，選項(xiàng)A）錯(cuò)誤。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式，所以循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)，選項(xiàng)B正確，選項(xiàng)C）錯(cuò)誤。答案選B）。91.設(shè)某二叉樹的前序序列為ABC，中序序列為CBA，則該二叉樹的后序序列為（ ）。答案：BA）BCAB）CBAC）ABCD）CAB題目解析:前序序列為ABC，中序序列為CBA，說明根結(jié)點(diǎn)為A，且B和C均在該A的左子樹上；結(jié)點(diǎn)B和C的前序序列為BC，中序序列為CB，則說明結(jié)點(diǎn)C在結(jié)點(diǎn)B的左子樹上，根據(jù)以上分析，該二叉樹的后序序列為CBA，答案選B）。92.下列排序方法中，最壞情況下時(shí)間復(fù)雜度最小的是（ ）。答案：C

51、A）冒泡排序B）快速排序C）堆排序D）直接插入排序題目解析:在最壞情況下，堆排序時(shí)間復(fù)雜度為O(nlog2n)，其余選項(xiàng)均為O(n2)，所以答案選C）。93.為了對(duì)有序表進(jìn)行對(duì)分查找，則要求有序表（ ）。答案：AA）只能順序存儲(chǔ)B）只能鏈?zhǔn)酱鎯?chǔ)C）可以順序存儲(chǔ)也可以鏈?zhǔn)酱鎯?chǔ)D）任何存儲(chǔ)方式題目解析:對(duì)分查找必須滿足用順序存儲(chǔ)結(jié)構(gòu)，且線性表是有序表兩個(gè)條件，答案選A）。94.設(shè)某二叉樹的后序序列為CBA，中序序列為ABC，則該二叉樹的前序序列為（ ）。答案：CA）BCAB）CBAC）ABCD）CAB題目解析:后序序列為CBA，中序序列為ABC，則說明，A為根結(jié)點(diǎn)，并且B和C均在A的右子樹上；結(jié)點(diǎn)

52、B和C中，后序序列為CB，中序序列為BC，則說明結(jié)點(diǎn)C在結(jié)點(diǎn)B的右子樹上，根據(jù)分析可得，該二叉樹的前序序列為ABC，答案選C）。95.下列敘述中正確的是（ ）。答案：DA）存儲(chǔ)空間不連續(xù)的所有鏈表一定是非線性結(jié)構(gòu)B）結(jié)點(diǎn)中有多個(gè)指針域的所有鏈表一定是非線性結(jié)構(gòu)C）能順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)D）帶鏈的棧與隊(duì)列是線性結(jié)構(gòu)題目解析:判斷一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)是否為線性結(jié)構(gòu)必須滿足以下兩個(gè)條件： 有且只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。根據(jù)這兩個(gè)條件，可知選項(xiàng)A）、B）和C）都不能判定是否是線性結(jié)構(gòu)，選項(xiàng)D）正確，答案選D）。96.算法時(shí)間復(fù)雜度的度量方法是（ ）。答案：

53、BA）算法程序的長(zhǎng)度B）執(zhí)行算法所需要的基本運(yùn)算次數(shù)C）執(zhí)行算法所需要的所有運(yùn)算次數(shù)D）執(zhí)行算法所需要的時(shí)間題目解析:算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量，算法的工作量用算法所執(zhí)行的基本運(yùn)行次數(shù)來度量，答案選B）。97.設(shè)循環(huán)隊(duì)列為Q(1: m)，初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)過一系列的入隊(duì)與退隊(duì)運(yùn)算后，front=rear=1，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。答案：DA）1B）2C）m-1D）0或m題目解析:在循環(huán)隊(duì)列中，當(dāng)front=rear時(shí)，有兩種情況，一種是隊(duì)列為空，另一種是隊(duì)列為滿，所以答案選D）。98.在最壞情況下（ ）。答案：CA）快速排序的時(shí)間復(fù)雜度比

54、冒泡排序的時(shí)間復(fù)雜度要小B）快速排序的時(shí)間復(fù)雜度比希爾排序的時(shí)間復(fù)雜度要小C）希爾排序的時(shí)間復(fù)雜度比直接插入排序的時(shí)間復(fù)雜度要小D）快速排序的時(shí)間復(fù)雜度與希爾排序的時(shí)間復(fù)雜度是一樣的題目解析:在最壞情況下，快速排序、冒泡排序和直接插入排序所需要的比較次數(shù)為O(n2)，希爾排序所需要的比較次數(shù)為O(n1.5)，所以答案選C）。99.在深度為7的滿二叉樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)為（ ）。答案：BA）64B）63C）32D）31題目解析:根據(jù)滿二叉樹的性質(zhì)，深度為7的滿二叉樹共有27-1=127個(gè)結(jié)點(diǎn)。根據(jù)二叉樹的性質(zhì)，該滿二叉樹在第7層上，共有27-1=64個(gè)結(jié)點(diǎn)，即共有64個(gè)葉子結(jié)點(diǎn)，那么度為2的結(jié)

55、點(diǎn)個(gè)數(shù)為127-64=63個(gè)。100.設(shè)棧的順序存儲(chǔ)空間為S(1: m)，初始狀態(tài)為top=m+1?，F(xiàn)經(jīng)過一系列入棧與退棧運(yùn)算后，top=20，則當(dāng)前棧中的元素個(gè)數(shù)為（ ）。答案：CA）30B）20C）m-19D）m-20題目解析:初始狀態(tài)為top=m+1，經(jīng)過運(yùn)算之后，top=20，則當(dāng)前棧中元素個(gè)數(shù)為m+1-20=m-19個(gè)。101.算法空間復(fù)雜度的度量方法是（ ）。答案：DA）算法程序的長(zhǎng)度B）算法所處理的數(shù)據(jù)量C）執(zhí)行算法所需要的工作單元D）執(zhí)行算法所需要的存儲(chǔ)空間題目解析:算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，答案選D）。102.下面不屬于軟件開發(fā)階段任務(wù)的是（ ）。答案：BA）測(cè)試B）可行性研究C）設(shè)計(jì)D）實(shí)現(xiàn)題目解析:可行性研究是屬于軟件定義階段的任務(wù)，所以答案選B）。103.設(shè)循環(huán)隊(duì)列為Q(1: m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=20。現(xiàn)要在該循環(huán)隊(duì)列中尋找最大值的元素，最壞情況下需要比較的次數(shù)為（ ）。答案：