國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2（共315題）

國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷2（共9套）（共315題）國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第1套一、單項(xiàng)選擇題(本題共37題，每題1.0分，共37分。)1、下列敘述中正確的是A、循環(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、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元素?cái)?shù)量。2、下列關(guān)于線性鏈表的敘述中，正確的是A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?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)系是由指針域來(lái)確定的。3、下列敘述中正確的是A、線性表鏈?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、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。4、下列敘述中正確的是A、線性表的鏈?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、以上都不正確標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)煮分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。5、下列敘述中正確的是A、線性表的鏈?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、上述三種說(shuō)法都不對(duì)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。6、下列對(duì)于線性鏈表的描述中正確的是A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。在線性鏈表中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head=NULL(或0)時(shí)稱為空表。7、下列敘述中正確的是A、順序存儲(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ǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。8、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是A、二叉鏈表B、循環(huán)鏈表C、雙向鏈表D、帶鏈的棧標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。9、下列敘述中正確的是A、有～一個(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)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。10、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是A、7B、6C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。11、下列關(guān)于二叉樹的敘述中，正確的是A、葉子結(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ù)的兩倍標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。12、某二叉樹中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、n+1B、n-1C、2nD、n／2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。所以該二叉樹的葉子結(jié)點(diǎn)數(shù)等于n+1。13、某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是A、10B、8C、6D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。14、一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為l的結(jié)點(diǎn)數(shù)為A、16B、10C、6D、4標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故此度為1的結(jié)點(diǎn)個(gè)數(shù)=總結(jié)點(diǎn)數(shù)-葉子節(jié)點(diǎn)數(shù)．度為2的節(jié)點(diǎn)數(shù)=25-5-4=16。15、一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、229C、230D、231標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)=葉子節(jié)點(diǎn)數(shù)+度為2的節(jié)點(diǎn)數(shù)+度為1的節(jié)點(diǎn)數(shù)=80+79+70=229。16、一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、221C、229D、231標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為n0，則度為2的結(jié)點(diǎn)數(shù)n2=n0—1。本題中葉子結(jié)點(diǎn)的個(gè)數(shù)為70，所以度為2的結(jié)點(diǎn)個(gè)數(shù)為69，因而總結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。17、某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第1層)A、3B、4C、6D、7標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。18、某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為(根結(jié)點(diǎn)在第1層)A、3B、6C、8D、12標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。19、設(shè)二叉樹T的深度為4，其中度為1，2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為A、8B、7C、6D、5標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：深度為m二叉樹其總結(jié)點(diǎn)數(shù)為2m-1=24一1=15?？偨Y(jié)點(diǎn)數(shù)減去度為1，2,3，4的結(jié)點(diǎn)個(gè)數(shù)就是葉子結(jié)點(diǎn)數(shù)。15—4-2一1一1=7。20、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則此二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、85B、120C、250D、350標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：①具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1，計(jì)算出該完全二叉樹的深度為10。②設(shè)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))為n0，度為1的結(jié)點(diǎn)為n1，度為2的結(jié)點(diǎn)為n2，總結(jié)點(diǎn)數(shù)為n，深度為k。n=n1+n2+n0，由于n0=n2+1則n2=n0-1，故n=n1+n0-1+n0=n1+2n0-1。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能：0或1。⑧假設(shè)度為1的結(jié)點(diǎn)數(shù)為0即滿二叉樹，根據(jù)滿二叉樹的定義，其2m-1個(gè)結(jié)點(diǎn)，根據(jù)以上計(jì)算所得的深度10來(lái)計(jì)算，應(yīng)有210-1=1024-1=1023個(gè)結(jié)點(diǎn)，顯然與題目中700個(gè)結(jié)點(diǎn)不符。因此，度為1的結(jié)點(diǎn)數(shù)必然為1。故n=n1+2n0-1=1+2n0-1=2n0，則n0=n／2=700／2=350。21、在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。對(duì)于深度為7的滿二叉樹，葉子結(jié)點(diǎn)所在的是第7層，一共有27-1=64個(gè)葉子結(jié)點(diǎn)。全部結(jié)點(diǎn)共27-1=127個(gè)。22、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡(jiǎn)單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問(wèn)根結(jié)點(diǎn)；②前序遍歷左子樹：③前序遍歷右子樹?？梢?，前序遍歷二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。23、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問(wèn)根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸過(guò)程。其簡(jiǎn)單描述為：若二叉樹為空，則結(jié)束返回；否則，先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。對(duì)于后序遍歷，第一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)D)為正確答案。24、對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為A、log2nB、n／2C、nD、n+1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在進(jìn)行順序查找過(guò)程中，如果被查的元素是線性表中的最后一個(gè)元素，或者被查元素根本不在線性表中，則為了查找這個(gè)元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。25、在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長(zhǎng)度。26、下列敘述中正確的是A、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n/2)C、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(log2n)D、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(nlog2n)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題主要考查的知識(shí)點(diǎn)為查找技術(shù)。順序查找的使用情況：①線性表為無(wú)序表；②表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，并不適用于線性鏈表。27、在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。28、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是A、順序存儲(chǔ)的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二分法查找只適應(yīng)于順序存儲(chǔ)的有序表。有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。29、冒泡排序在最壞情況下的比較次數(shù)是A、n(n+1)／2B、nlog2nC、n(n-1)／2D、n／2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)n個(gè)結(jié)點(diǎn)的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n—1)／2。30、對(duì)長(zhǎng)度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為A、9B、10C、45D、90標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的長(zhǎng)度為n，最壞情況下冒泡排序需要比較的次數(shù)為n(n-1)／2。31、對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是A、冒泡排序?yàn)閚／2B、冒泡排序?yàn)閚C、快速排序?yàn)閚D、快速排序?yàn)閚(n-1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。32、對(duì)長(zhǎng)度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為A、nB、n一1C、n(n一1)D、n(n一1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。33、對(duì)長(zhǎng)度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序n(n一1)／2、快速排序n(n-1)／2、簡(jiǎn)單插入排序n(n-1)／2、希爾排序O(n1.5)、簡(jiǎn)單選擇排序n(n-1)／2、堆排序O(nlog2n)。34、下列排序方法中，最壞情況下比較次數(shù)最少的是A、冒泡排序B、簡(jiǎn)單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：冒泡排序、簡(jiǎn)單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n一1)／2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆排序的比較次數(shù)最少。35、下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲(chǔ)結(jié)構(gòu)的是A、棧B、堆C、隊(duì)列D、非完全二叉樹標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值、堆總是一棵完全二叉樹，可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)分為鏈?zhǔn)酱鎯?chǔ)、順序存儲(chǔ)兩種；棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表，可以以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。36、設(shè)二叉樹共有375個(gè)結(jié)點(diǎn)，其中度為2的結(jié)點(diǎn)有187個(gè)。則度為1的結(jié)點(diǎn)個(gè)數(shù)是A、0B、1C、188D、不可能有這樣的二叉樹標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2i-1個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。本題中，度為2的結(jié)點(diǎn)有187個(gè)，葉子結(jié)點(diǎn)應(yīng)該有187+1=188個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)=375一187-188=0。37、在帶鏈隊(duì)列中，經(jīng)過(guò)一系列正常的操作后，如果front=rear，則隊(duì)列中的元素個(gè)數(shù)為A、0或1B、0C、1D、隊(duì)列滿標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端(舶nt)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)也稱為鏈隊(duì)列。為了便于操作，可給鏈隊(duì)列添加1個(gè)頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。隊(duì)列為空的判斷條件是頭指針和尾指針的值相同，且均指向頭結(jié)點(diǎn)。當(dāng)隊(duì)列為空(0)或1時(shí)，front=rear。國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第2套一、單項(xiàng)選擇題(本題共30題，每題1.0分，共30分。)1、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：35)，初始狀態(tài)為front=rear=35。現(xiàn)經(jīng)過(guò)一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為A、15B、16C、20D、0或35標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：循環(huán)隊(duì)列的隊(duì)頭指針和尾指針都等于15，此循環(huán)隊(duì)列中元素的個(gè)數(shù)有兩種情況，第一種情況是隊(duì)頭指針和尾指針都是第一次到達(dá)15，此時(shí)元素個(gè)數(shù)為0；第二種情況是隊(duì)頭指針第一次到達(dá)15，而尾指針第二次到達(dá)15，此時(shí)元素個(gè)數(shù)為35。2、在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為A、2B、3C、4D、5標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：循環(huán)隊(duì)列中，rear表示尾指針，front表示頭指針，當(dāng)有元素入隊(duì)時(shí)，rear=rear+1，而元素出隊(duì)的時(shí)候，front=front+1，當(dāng)rear值大于front值時(shí)，隊(duì)列中的元素個(gè)數(shù)為rear-front，當(dāng)rear的值小于front時(shí)，列隊(duì)中的元素個(gè)數(shù)為rear-front+m(m表示隊(duì)列的容量)。3、下列敘述中正確的是A、棧是一種先進(jìn)先出的線性表B、隊(duì)列是一種后進(jìn)先出的線性表C、棧與隊(duì)列都是非線性結(jié)構(gòu)D、棧與隊(duì)列都是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。棧和隊(duì)列都是一種線性表，屬于線性結(jié)構(gòu)。4、下列敘述中正確的是A、棧是“先進(jìn)先出”的線性表B、隊(duì)列是“先進(jìn)后出”的線性表C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧是“先進(jìn)后出”，隊(duì)列“是先進(jìn)先出”。棧和隊(duì)列都是一種線性表，屬于線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱之為線性鏈表。5、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是A、函數(shù)的遞歸調(diào)用B、數(shù)組元素的引用C、多重循環(huán)的執(zhí)行D、先到先服務(wù)的作業(yè)調(diào)度標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪除。6、下列敘述中正確的是A、循環(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、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元素?cái)?shù)量。7、下列關(guān)于線性鏈表的敘述中，正確的是A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?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)系是由指針域來(lái)確定的。8、下列敘述中正確的是A、線性表鏈武存儲(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、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。9、下列敘述中正確的是A、線性表的鏈?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、以上都不正確標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。10、下列敘述中正確的是A、線性表的鏈?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、上述三種說(shuō)法都不劉標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。11、下列對(duì)于線性鏈表的描述中正確的是A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的B、存儲(chǔ)空間不一定連續(xù)，且前件冗素一定存儲(chǔ)在后件元素的前面C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一一致。在線性鏈表中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head=NULL(或0)時(shí)稱為空表。12、下列敘述中正確的是A、順序存儲(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ǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。13、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線件結(jié)構(gòu)的是A、二叉鏈表B、循環(huán)鏈表C、雙向鏈表D、帶鏈的棧標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。14、下列敘述中正確的是A、有一個(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)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。15、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是A、7B、6C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。16、下列關(guān)于二叉樹的敘述中，正確的是A、葉子結(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ù)的兩倍標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。17、某二叉樹中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、n+1B、n-1C、2nD、n／2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。所以該二叉樹的葉子結(jié)點(diǎn)數(shù)等于n+1。18、某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是A、10B、8C、6D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。19、一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為A、16B、10C、6D、4標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故此度為1的結(jié)點(diǎn)個(gè)數(shù)=總結(jié)點(diǎn)數(shù)-葉子節(jié)點(diǎn)數(shù)-度為2的節(jié)點(diǎn)數(shù)=25—54=16。20、一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、229C、230D、231標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)=葉子節(jié)點(diǎn)數(shù)+度為2的節(jié)點(diǎn)數(shù)+度為1的節(jié)點(diǎn)數(shù)=80+79+70=229。21、一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、221C、229D、231標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為n0，則度為2的結(jié)點(diǎn)數(shù)n2=n0-1。本題中葉子結(jié)點(diǎn)的個(gè)數(shù)為70，所以度為2的結(jié)點(diǎn)個(gè)數(shù)為69，因而總結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。22、某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第1層)A、3B、4C、6D、7標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。23、某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為(根結(jié)點(diǎn)在第1層)A、3B、6C、8D、12標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為O的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。24、設(shè)樹T的深度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為A、8B、7C、6D、5標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：深度為m二叉樹其總結(jié)點(diǎn)數(shù)為2m一1=24—1=15?？偨Y(jié)點(diǎn)數(shù)減去度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)就是葉子結(jié)點(diǎn)數(shù)。15-4-2-1-1=7。25、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則此二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、85B、120C、250D、350標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：①具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[long2n]+1，計(jì)算出該完全二叉樹的深度為10。②設(shè)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))為n0，度為1的結(jié)點(diǎn)為n1，度為2的結(jié)點(diǎn)為n2，總結(jié)點(diǎn)數(shù)為n，深度為k。n=n1+n2+n0，由于n0=n2+1，則n2=n0—1，故n=n1+n0—1+n0=n1+2n0一1。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能：0或1。③假設(shè)度為]的結(jié)點(diǎn)數(shù)為0即滿二叉樹，根據(jù)滿二叉樹的定義，其2m—1個(gè)結(jié)點(diǎn)，跟據(jù)以上計(jì)算所得的深度10來(lái)計(jì)算，應(yīng)有210-1=1024一1=1023個(gè)結(jié)點(diǎn)，顯然與題目中700個(gè)結(jié)點(diǎn)不符。因此，度為1的結(jié)點(diǎn)數(shù)必然為1。故n=n1+2n0-1=1+2n0-1=2n0，則n0=n／2=700／2=350。26、在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：所渭滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二義樹有2m-1個(gè)結(jié)點(diǎn)。對(duì)于深度為7的滿二叉樹，葉子結(jié)點(diǎn)所在的是第7層，一共有27-1=64個(gè)葉子結(jié)點(diǎn)。全部結(jié)點(diǎn)共27-1=127個(gè)。27、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡(jiǎn)單描述：若二叉樹為空，則結(jié)束返回：甭則：①訪問(wèn)根結(jié)點(diǎn)；②前序遍歷左子樹；③前序遍歷右子樹?？梢姡靶虮闅v二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。28、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問(wèn)根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右予樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸過(guò)程。其簡(jiǎn)單描述為：若二叉樹為空，則結(jié)束返回；否則，先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。對(duì)于后序遍歷，第一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)D)為正確答案。29、對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為A、log2nB、n／2C、nD、n+1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在進(jìn)行順序查找過(guò)程中，如果被查的元素是線性表中的最后一個(gè)元素，或者被查元素根本不在線性表中，則為查找這個(gè)元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。30、在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長(zhǎng)度。國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第3套一、單項(xiàng)選擇題(本題共36題，每題1.0分，共36分。)1、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是()。A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡(jiǎn)單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問(wèn)根結(jié)點(diǎn)：②前序遍歷左子樹；⑤前序遍歷右子樹?？梢姡靶虮闅v二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。2、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為()。A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問(wèn)根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者巾，首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸過(guò)程。其簡(jiǎn)單描述為：若二叉樹為空，則結(jié)束返回；否則，先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。對(duì)于后序遍歷，第一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)D為正確答案。3、對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為()。A、log2nB、n／2C、nD、n＋1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在進(jìn)行順序查找過(guò)程中，如果被查的元素是線性表中的最后一個(gè)元素，或者被查元素根本不在線性表中，則為了查找這個(gè)元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。4、在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為()。A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功：但如果要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長(zhǎng)度。5、下列敘述中正確的是()。A、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n／2)C、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(1og2n)D、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(nlog2n．)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題主要考查的知識(shí)點(diǎn)為查找技術(shù)。順序查找的使用情況：①線性表為無(wú)序表；②表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，并不適用于線性鏈表。6、在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是()。A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。7、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是()。A、順序存儲(chǔ)的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二分法查找只適應(yīng)于順序存儲(chǔ)的有序表。有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。8、冒泡排序在最壞情況下的比較次數(shù)是()。A、n(n＋1)／2B、nlog2nC、n(n－1)／2D、n／2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)n個(gè)結(jié)點(diǎn)的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n－1)／2。9、對(duì)長(zhǎng)度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為()。A、9B、10C、45D、90標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的長(zhǎng)度為n，最壞情況下冒泡排序需要比較的次數(shù)為n(n－1)／2。10、對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是()。A、冒泡排序?yàn)閚／2B、冒泡排序?yàn)閚C、快速排序?yàn)閚D、快速排序?yàn)閚(n－1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n－1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。11、對(duì)長(zhǎng)度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為()。A、nB、n－1C、n(n－1)D、n(n－1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n－1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。12、對(duì)長(zhǎng)度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n－1)／2的排序方法是()。A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序n(n－1)／2、快速排序n(n－1)／2、簡(jiǎn)單插入排序n(n－1)／2、希爾排序O(n1.5)、簡(jiǎn)單選擇排序n(n－1)／2、堆排序O(nlog2n)。13、下列排序方法中，最壞情況下比較次數(shù)最少的是()。A、冒泡排序B、簡(jiǎn)單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：冒泡排序、簡(jiǎn)單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n－1)／2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆排序的比較次數(shù)最少。14、下列對(duì)隊(duì)列的描述中正確的是()。A、隊(duì)列屬于非線性表B、隊(duì)列按“先進(jìn)后出”原則組織數(shù)據(jù)C、隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D、隊(duì)列按“先進(jìn)先出”原則組織數(shù)據(jù)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：隊(duì)列(queue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾；允許刪除的一端稱為隊(duì)頭。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除；反之，最后插入的元素將最后才能被刪除。因此，隊(duì)列又稱“先進(jìn)先出”或“后進(jìn)后出”的線性表。15、下列敘述中正確的是()。A、棧是一種先進(jìn)先出的線性表B、隊(duì)列是一種后進(jìn)先出的線性表C、棧與隊(duì)列都是非線性結(jié)構(gòu)D、以上三種說(shuō)法都不對(duì)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧是先進(jìn)后出的線性表，隊(duì)列是先進(jìn)先出的線性表，二者均為線性結(jié)構(gòu)。16、下列敘述中正確的是()。A、棧是“先進(jìn)先出”的線性表B、隊(duì)列是“先進(jìn)后出”的線性表C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：本題主要考查了棧、隊(duì)列、循環(huán)隊(duì)列的概念，棧是先進(jìn)后出的線性表，隊(duì)列是先進(jìn)先出的線性表。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。17、下列關(guān)于棧的描述中正確的是()。A、在棧中只能插入元素而不能刪除元素B、在棧中只能刪除元素而不能插入元素C、棧是特殊的線性表，只能在一端插入或刪除元素D、棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧是限定在一端進(jìn)行插入與刪除的線性表，在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。18、下列敘述中正確的是()。A、循環(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ì)尾指針共同決定標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定的，元素的動(dòng)態(tài)變化也是通過(guò)隊(duì)頭指針和隊(duì)尾指針來(lái)反映的。19、對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是()。A、隊(duì)頭指針是固定不變的B、隊(duì)頭指針一定大于隊(duì)尾指針C、隊(duì)頭指針一定小于隊(duì)尾指針D、隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置。循環(huán)隊(duì)列的主要操作是：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)一。每進(jìn)行一次退隊(duì)運(yùn)算，隊(duì)頭指針就進(jìn)一。當(dāng)rear或front等于隊(duì)列的長(zhǎng)度加l時(shí)，就把rear·或front值置為l。所以在循環(huán)隊(duì)列中，隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針。20、下列敘述中正確的是()。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)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題主要考查循環(huán)隊(duì)列的概念，循環(huán)隊(duì)列作為隊(duì)列的一種也應(yīng)該是線性結(jié)構(gòu)。隊(duì)列是一種邏輯結(jié)構(gòu)，而循環(huán)隊(duì)列是一種順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列。21、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：35)，初始狀態(tài)為front＝rear＝35。現(xiàn)經(jīng)過(guò)一系列入隊(duì)與退隊(duì)運(yùn)算后，front＝15，rear＝15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、15B、16C、20D、0或35標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：循環(huán)隊(duì)列的隊(duì)頭指針和尾指針都等于15，此循環(huán)隊(duì)列中元素的個(gè)數(shù)有兩種情況，第一種情況是隊(duì)頭指針和尾指針都是第一次到達(dá)15，此時(shí)元素個(gè)數(shù)為0；第二種情況是隊(duì)頭指針第一次到達(dá)15，而尾指針第二次到達(dá)15，此時(shí)元素個(gè)數(shù)為35。22、在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針fron＝6，尾指針rear＝9，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、2B、3C、4D、5標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：循環(huán)隊(duì)列中，rear表示尾指針，front表示頭指針，當(dāng)有元素入隊(duì)時(shí)，rear＝rear＋1。而元素出隊(duì)的時(shí)候，front＝front＋1，當(dāng)rear值大于front值時(shí)，隊(duì)列中的元素個(gè)數(shù)為rear－front，當(dāng)rcar的值小于front時(shí)，列隊(duì)中的元素個(gè)數(shù)為rear－front＋m(m表示隊(duì)列的容量)。23、下列敘述中正確的是()。A、棧是一種先進(jìn)先出的線性表B、隊(duì)列是一種后進(jìn)先出的線性表C、棧與隊(duì)列都是非線性結(jié)構(gòu)D、棧與隊(duì)列都是線性結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧是先進(jìn)后出，隊(duì)列是先進(jìn)先出。棧和隊(duì)列都是一種線性表，屬于線性結(jié)構(gòu)。24、下列敘述中正確的是()。A、棧是“先進(jìn)先出”的線性表B、隊(duì)列是“先進(jìn)后出”的線性表C、循環(huán)隊(duì)列是非線性結(jié)構(gòu)D、有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧是“先進(jìn)后出”，隊(duì)列“是先進(jìn)先出”。棧和隊(duì)列都是一種線性表，屬于線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱之為線性鏈表。25、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是()。A、函數(shù)的遞歸調(diào)用B、數(shù)組元素的引用C、多重循環(huán)的執(zhí)行D、先到先服務(wù)的作業(yè)調(diào)度標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪除。26、下列敘述中正確的是()。A、循環(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、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元素?cái)?shù)量。27、下列關(guān)于線性鏈表的敘述中，正確的是()。A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?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)系是由指針域來(lái)確定的。28、下列敘述中正確的是()。A、線性表鏈?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、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。29、下列敘述中正確的是()。A、線性表的鏈?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、以上都不正確標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。30、下列敘述中正確的是()。A、線性表的鏈?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、上述三種說(shuō)法都不對(duì)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。31、下列對(duì)于線性鏈表的描述中正確的是()。A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。在線性鏈表中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head＝NuLL(或0)時(shí)稱為空表。32、下列敘述中正確的是()。A、順序存儲(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ǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。33、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是()。A、二叉鏈表B、循環(huán)鏈表C、雙向鏈表D、帶鏈的棧標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。34、下列敘述中正確的是()。A、有一個(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)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。35、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是()。A、7B、6C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第l層，同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。36、下列關(guān)于二叉樹的敘述中，正確的是()。A、葉子結(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ù)的兩倍標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。國(guó)家二級(jí)公共基礎(chǔ)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷第4套一、單項(xiàng)選擇題(本題共35題，每題1.0分，共35分。)1、下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是A、函數(shù)的遞歸調(diào)用B、數(shù)組元素的引用C、多重循環(huán)的執(zhí)行D、先到先服務(wù)的作業(yè)調(diào)度標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪除。2、下列敘述中正確的是A、循環(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、循環(huán)隊(duì)列中的元素個(gè)數(shù)不會(huì)變化標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：所謂循環(huán)結(jié)構(gòu)就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置上，形成邏輯上的環(huán)狀空間，循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，隊(duì)列中的元素?cái)?shù)等于從隊(duì)頭指針front指向的后一個(gè)位置與隊(duì)尾指針rear指向位置之間的元素?cái)?shù)量。3、下列關(guān)于線性鏈表的敘述中，正確的是A、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致B、各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)C、進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素D、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在鏈?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)系是由指針域來(lái)確定的。4、下列敘述中正確的是A、線性表鏈?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、以上都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。5、下列敘述中正確的是A、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空問(wèn)是相同的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、以上都不正確標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的。而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。6、下列敘述中正確的是A、線性表的鏈?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、上述三種說(shuō)法都不對(duì)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：線性表的存儲(chǔ)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。在順序存儲(chǔ)中，所有元素所占的存儲(chǔ)空間是連續(xù)的，各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。所以每個(gè)元素只存儲(chǔ)其值就可以了，而在鏈?zhǔn)酱鎯?chǔ)的方式中，將存儲(chǔ)空間的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域：另一部分用于存儲(chǔ)下一個(gè)元素的存儲(chǔ)序號(hào)，稱為指針域。所以線性表的鏈?zhǔn)酱鎯?chǔ)方式比順序存儲(chǔ)方式的存儲(chǔ)空間要大一些。7、下列對(duì)于線性鏈表的描述中正確的是A、存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的B、存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面C、存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面D、存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。在線性鏈中，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)指示的，指向線性表中第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head=NuLL(或0)時(shí)稱為空表。8、下列敘述中正確的是A、順序存儲(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ǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的。9、下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是A、二叉鏈表B、循環(huán)鏈表C、雙向鏈表D、帶鏈的棧標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。10、下列敘述中正確的是A、有一個(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)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：住數(shù)據(jù)結(jié)構(gòu)中，樹這類的的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。11、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是A、7B、6C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：這個(gè)系統(tǒng)總體結(jié)構(gòu)圖是一棵樹結(jié)構(gòu)，在樹結(jié)構(gòu)中，根結(jié)點(diǎn)在第1層，同一層上所有子結(jié)點(diǎn)都在下一層，由系統(tǒng)總體結(jié)構(gòu)圖可知，這棵樹共3層。在樹結(jié)構(gòu)中，樹的最大層次稱為樹的深度。所以這棵樹的深度為3。12、下列關(guān)于二叉樹的敘述中，正確的是A、葉子結(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ù)的兩倍標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：由二叉樹的性質(zhì)可以知道在二叉樹中葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。13、某二叉樹中有n個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、n+1B、n一1C、2nD、n／2標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在任意一棵二又樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。所以該二叉樹的葉子結(jié)點(diǎn)數(shù)等于n+1。14、某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是A、10B、8C、6D、4標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。15、一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為A、16B、10C、6D、4標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故此度為1的結(jié)點(diǎn)個(gè)數(shù)=總結(jié)點(diǎn)數(shù)一葉子節(jié)點(diǎn)數(shù)一度為2的節(jié)點(diǎn)數(shù)=25．5—4=16。16、一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、229C、230D、231標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)=葉子節(jié)點(diǎn)數(shù)+度為2的節(jié)點(diǎn)數(shù)+度為1的節(jié)點(diǎn)數(shù)=80+79+70=229。17、一棵二叉樹中共有70個(gè)葉子結(jié)點(diǎn)與80個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為A、219B、221C、229D、231標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為n0，則度為2的結(jié)點(diǎn)數(shù)n2=n0一1。本題中葉子結(jié)點(diǎn)的個(gè)數(shù)為70，所以度為2的結(jié)點(diǎn)個(gè)數(shù)為69，因而總結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù)=70+80+69=219。18、某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第1層)A、3B、4C、6D、7標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為7層，每層只有一個(gè)結(jié)點(diǎn)。19、某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為(根結(jié)點(diǎn)在第1層)A、3B、6C、8D、12標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。20、設(shè)樹T的深度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為A、8B、7C、6D、5標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：深度為m二叉樹其總結(jié)點(diǎn)數(shù)為2m-1=24-1=15?？偨Y(jié)點(diǎn)數(shù)減去度為1，2,3,4的結(jié)點(diǎn)個(gè)數(shù)就是葉子結(jié)點(diǎn)數(shù)。15—4-2—1—1=7。21、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則此二叉樹中的葉子結(jié)點(diǎn)數(shù)為A、85B、120C、250D、350標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：①具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[long2n]+1，計(jì)算出該完全二叉樹的深度為10。②設(shè)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))為n0,度為1的結(jié)點(diǎn)為n1，度為2的結(jié)點(diǎn)為n2，總結(jié)點(diǎn)數(shù)為n，深度為k。n=n1+n2+n0，由于n0=n2+1則n2=n0—1，故n=n1+n0-1+n0=n1+2n0一1。由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能：0或1。③假設(shè)度為1的結(jié)點(diǎn)數(shù)為0即滿二叉樹，根據(jù)滿二叉樹的定義，其2m一1個(gè)結(jié)點(diǎn)，根據(jù)以上計(jì)算所得的深度10來(lái)計(jì)算，應(yīng)有210-1=1024—1=1023個(gè)結(jié)點(diǎn)，顯然與題目中700個(gè)結(jié)點(diǎn)不符。因此，度為1的結(jié)點(diǎn)數(shù)必然為1。故n=n1+2n0-1=1+2n0-1=2n0，則n0=n／2=700/2=350。22、在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。也就是在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都是雖大結(jié)點(diǎn)數(shù)，即在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。對(duì)于深度為7的滿二叉樹，葉子結(jié)點(diǎn)所在的是第7層，一共有27-1=64個(gè)葉子結(jié)點(diǎn)。全部結(jié)點(diǎn)共27-1=127個(gè)。23、對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果是A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：二叉樹前序遍歷的簡(jiǎn)單描述：若二叉樹為空，則結(jié)束返回；否則：①訪問(wèn)根結(jié)點(diǎn)：②前序遍歷左子樹：③前序遍歷右子樹?？梢姡靶虮闅v二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。根據(jù)題目中給出的二叉樹的結(jié)構(gòu)可知前序遍歷的結(jié)果是ABDYECFXZ。24、對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：所謂后序遍歷是指在訪問(wèn)根據(jù)結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸過(guò)程。其簡(jiǎn)單描述為：若二叉樹為空，則結(jié)束返回；否則，先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。對(duì)于后序遍歷，第一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是最左下的結(jié)點(diǎn)，最后一個(gè)訪問(wèn)的結(jié)點(diǎn)一定是根結(jié)點(diǎn)，所以選項(xiàng)D)為正確答案。25、對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為A、log2nB、n／2C、nD、n+1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在進(jìn)行順序查找過(guò)程中，如果被查的元素是線性表中的最后一個(gè)元素，或者被查元素根本不在線性表中，則為了查找這個(gè)元素需要與線性表中的所有元素進(jìn)行比較，這是順序查找的最壞情況，需要比較的次數(shù)為n次。26、在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法是：從線性表的第一元素開始，依次將線性表中的元素與被查找的元素進(jìn)行比較，若相等則表示找到(即查找成功)，若線性表中所有元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素(即查找失敗)。如果線性表中的第一個(gè)元素就是要查找的元素，則只需要做一次比較就查找成功；但如果要查找的元素是線性表中的最后一個(gè)元素，或者要查找元素不在線性表中，則需要與線性表中所有元素進(jìn)行比較，這是順序查找的最壞情況，比較次數(shù)為線性表的長(zhǎng)度。27、下列敘述中正確的是A、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為nB、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(n／2)C、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(log2n)D、對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞情況下需要的比較次數(shù)為(nlog2n)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題主要考查的知識(shí)點(diǎn)為查找技術(shù)。順序查找的使用情況：①線性表為無(wú)序表；②表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表，并不適用于線性鏈表。28、在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是A、O(n)B、O(n4)C、O(log2n)D、O(nlog2n)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次。29、下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是A、順序存儲(chǔ)的有序線性表B、線性鏈表C、二叉鏈表D、有序線性鏈表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：二分法查找只適應(yīng)于順序存儲(chǔ)的有序表。有序表是指線性表中的元素按值非遞減排序(即從小到大，但允許相鄰元素值相等)的表。30、冒泡排序在最壞情況下的比較次數(shù)是A、n(n+1)／2B、nlog2nC、n(n—1)／2D、n／2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：對(duì)n個(gè)結(jié)點(diǎn)的線性表采用冒泡排序，在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n一1)／2。31、對(duì)長(zhǎng)度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為A、9B、10C、45D、90標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：線性表的長(zhǎng)度為n，最壞情況下冒泡排序需要比較的次數(shù)為n(n—1)／2。32、對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是A、冒泡排序?yàn)閚／2B、冒泡排序?yàn)閚C、快速排序?yàn)閚D、快速排序?yàn)閚(n一1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n—1)／2。快速排序法也是一種互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。33、對(duì)長(zhǎng)度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為A、nB、n一1C、n(n一1)D、n(n一1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n／2遍的從前往后的掃描和n／2遍的從后往前的掃描，需要的比較次數(shù)為n(n一1)／2?？焖倥判蚍ㄒ彩且环N互換類的排序方法，但由于它比冒泡排序法的速度快，因此，稱為快速排序法。34、對(duì)長(zhǎng)度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序n(n-1)／2、快速排序n(n-1)／2、簡(jiǎn)單插入排序n(n-1)／2、希爾排序O(n1.5)、簡(jiǎn)單選擇排序n(n一1)／2、堆排序O(nlog2n)。35、下列排序方法中，最壞情況下比較次數(shù)最少的是A、冒泡排序B、簡(jiǎn)單選擇排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：冒泡排序、簡(jiǎn)單選擇排序和直接插入排序法在最壞的情況下比較次數(shù)為：n(n一1)／2。而堆排序法在最壞的情況下需要比較的次數(shù)為O(nlog2n)。其中堆排序的比較次數(shù)最少。國(guó)家二級(jí)公共基礎(chǔ)知識(shí)