計算機二級Ms-office-第一部分-公共基礎(chǔ)知識-數(shù)據(jù)結(jié)構(gòu)與算法

計算機二級Msoffice第一部份公共基礎(chǔ)知識一一數(shù)據(jù)結(jié)構(gòu)與

算法

1.下列敘述中正確的是0。（）

A、算法的復(fù)雜度與問題的規(guī)模無關(guān)

B、算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)

C、對數(shù)據(jù)進(jìn)行壓縮存儲會降低算法的空間復(fù)雜度（正確答案）

I）、數(shù)值型算法只需考慮計算結(jié)果的可靠性

答案解析：參考解析：為了降低算法的空間復(fù)雜度，主要應(yīng)減少輸入數(shù)據(jù)所占的

存儲空間以及額外空間，通常采用壓縮存儲技術(shù)，C選項敘述正確。算法的計算工

作量是用算法所執(zhí)行的基本運算次數(shù)來度量的，而算法所執(zhí)行的基本運算次數(shù)是問

題規(guī)模（通常用整數(shù)）表示的函數(shù)，A選項敘述錯誤。算法的復(fù)雜度與程序的編制無

關(guān)，B選項敘述錯誤。算法需要考慮可行性、確定性、有窮性等，D選項敘述錯

誤。

2.設(shè)有一個棧與一個隊列的初始狀態(tài)均為空?，F(xiàn)有一個序列A,B,C,D,E,F,G,H。

先分別將序列中的前4個元素挨次入棧，后4個元素挨次入隊；然后分別將棧中的

元素挨次退棧，再將隊列中的元素挨次退隊。最后得到的序列為（）。0

A、A,B,C,D,E,F,G,H

B、A,B,C,D,H,G,F,E

C、D,C,B,A,H,G,F,E

D、D,C,B,A,E,F,G,H（正確答案）

答案解析：參考解析：棧按先進(jìn)后出的原則組織數(shù)據(jù)，所以入棧最早的元素最后

出棧。隊列按先進(jìn)先出的原則組織數(shù)據(jù)，所以入隊最早的元素最先退隊。入棧的順

序為A,B,C,D,則退棧的順序為D,C,B,A；入隊的順序為E,F,G,H,退隊

的順序為E,F,G,Ho

3.設(shè)某棵樹的度為3,其中度為3,2,1的結(jié)點個數(shù)分別為3,0,4。則該樹中的葉子

結(jié)點數(shù)為。。（）

A、6

B、7（正確答案）

D、不可能有這樣的樹

答案解析：參考解析:假設(shè)葉子結(jié)點個數(shù)為n。這棵樹的總結(jié)點數(shù)為度為3的結(jié)點

數(shù)十度為2的結(jié)點數(shù)十度為1的結(jié)點數(shù)十度為0的結(jié)點數(shù)，即為3+0+4+n。再根據(jù)樹

的性質(zhì):樹的總的結(jié)點數(shù)為樹中所有結(jié)點的度數(shù)之和再加1,則總結(jié)點數(shù)為

3x3+2x0+lx4+0xn+lo3x3+lx4+『3+4+n,則n=7,葉子結(jié)點數(shù)為7。

4.下列敘述中正確的是0。（）

A、循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)（正確答案）

B、循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)

C、循環(huán)隊列中的隊尾指針一定大于隊頭指針

D、循環(huán)隊列中的隊尾指針一定小于隊頭指針

答案解析：參考解析：循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)，用隊尾指針rear指

向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。因此，從排

頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均

為隊列中的元素。在循環(huán)隊列中隊頭指針可以大于隊尾指針，也可以小于隊尾指

針。

5.設(shè)棧與隊列初始狀態(tài)為空。將元素片8,&口1廳,6,11挨次輪流入棧和入隊，然后

挨次輪流出棧和退隊，則輸出序列為（）。0

A、A,B,C,D,H,G,F,E

B、B,G,D,E,F,C,H,A

C、D,C,B,A,E,F,G,H

D、G,B,E,D,C,F,A,H（正確答案）

答案解析：參考解析：棧按先進(jìn)后出的原則組織數(shù)據(jù)，所以入棧最早的元素最后

出棧；隊列按先進(jìn)先出的原則組織數(shù)據(jù)，所以入隊最早的元素最先退隊。將元素

A,B,C,D,E,F,G,H挨次輪流入棧和入隊，則入棧的順序為A,C,E,G,入隊的順序為

B,D,F,H,然后挨次輪流出棧和退隊，則G先出棧，然后B退隊，出棧的順序為

G,E,C,A,退隊的順序為B,D,F,H,輸出順序為G,B,E,D,C,F,A,G

6.設(shè)二叉樹的前序序列為ABDEGHCFI,中序序列為DBGEHACIFJ。則按層次輸出（從

上到下，同一層從左到右）的序列為。。0

A、ABCDEFGHIJ（正確答案）

B、DGHEBUFCA

C、JIIIGFEDCBA

D、GHIUDEFBCA

答案解析：參考解析：二叉樹遍歷可以分為3種:前序遍歷（訪問根結(jié)點在訪問左

子樹和訪問右子樹之前）、中序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹兩者之

間）、后序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹之后）。本題中二叉樹的前

序序列為ABDEGHCFIJ,可確定根結(jié)點為A,按層次輸出（從上到下，同一層從左到右）

時訪問的第一個結(jié)點也應(yīng)該是A,所以可排除B、C、D三項。

7.下列敘述中錯誤的是0。（）

A、循環(huán)鏈表中有一個表頭結(jié)點

B、循環(huán)鏈表的存儲空間是連續(xù)的（正確答案）

C、循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點

D、循環(huán)鏈表實現(xiàn)了空表與非空表運算的統(tǒng)一

答案解析：參考解析：線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是，用一組不連續(xù)的存儲單元

存儲線性表中的各個元素。線性鏈表的存儲單元是任意的，即各數(shù)據(jù)結(jié)點的存儲序

號可以是連續(xù)的，也可以是不連續(xù)的。循環(huán)鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，因此存儲空間

也可以是不連續(xù)的。

8.設(shè)棧的存儲空間為S（l:50）,初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退

棧操作后，top=50,則棧中的元素個數(shù)為（）。（）

A、0

B、1（正確答案）

C、50

D、49

答案解析：參考解析：棧的存儲空間為S（l:50）,初始狀態(tài)為top=51,即棧的初始

狀態(tài)為空。當(dāng)?shù)谝粋€元素進(jìn)棧后，top=50,第二個元素進(jìn)棧后，top=49,第三個元

素進(jìn)棧后，top=48,以此類推；若第三個元素出棧后，top=48,第二個元素出棧后，

top=50?即每進(jìn)棧一個元素，topT;每出棧一個元素，top+lo當(dāng)top=50時,，棧中

惟獨一個元素。

9.某二叉樹共有399個結(jié)點，其中有199個度為2的結(jié)點，則該二叉樹中的葉子結(jié)

點數(shù)為。。。

A、不存在這樣的二叉樹

B、198

C、199

D、200（正確答案）

答案解析：參考解析：根據(jù)二叉樹的性質(zhì):對任何一棵二叉樹，度為的結(jié)點（即葉

子結(jié)點）總是比度為2的結(jié)點多一個。本題中，度為2的結(jié)點個數(shù)為199,則葉子結(jié)

點數(shù)為199+1=200。199+200=399,即這棵二叉樹中只存在度為0和度為2的結(jié)點，

不存在度為1的結(jié)點。

10.在長度為的有序鏈表中進(jìn)行查找，最壞情況下需要比較的次數(shù)為（）。（）

A、n-1

B、n/2

C、n（正確答案）

D、與有序順序表的對分查找相同

答案解析：參考解析：最壞情況為:查找的元素為表中最后一個元素或者查找的元

素不在表中，則需要比較表中所有元素，所以最壞情況下需要比較次數(shù)為n。

1L循環(huán)隊列的存儲空間為Q（l：50）o經(jīng)過一系列正常的入隊與退隊操作后，

front=rear=25o后又成功地將一個元素入隊，此時隊列中的元素個數(shù)為0。（）

A、1（正確答案）

B、50

C、26

D、2

答案解析：參考解析：設(shè)循環(huán)隊列的存儲空間為Q（l：m）,當(dāng)front=rear=m時;循

環(huán)隊列為空；當(dāng)front=rear且不等于m時，循環(huán)隊列可能為空，也可能為滿。當(dāng)

為空時，可以插入元素；當(dāng)為滿時:插入元素會發(fā)生“上溢”錯誤。題目中已經(jīng)說

明“成功地將一個元素入隊”，說明之前循環(huán)隊列的狀態(tài)為空，插入一個元素后，

隊列中共有1個元素。

12.設(shè)二叉樹的前序列為ABCDEF,中序序列為ABCDEF,則該二叉樹的后序序列為（）。

0

A、ABCDEF

B、FEDCBA（正確答案）

C、DEFCBA

D、CBAFED

答案解析：參考解析：二叉樹遍歷可以分為3種:前序遍歷（訪問根結(jié)點在訪問左

子樹和訪問右子樹之前）、中序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹兩者之

間）、后序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹之后）。本題中，二叉樹的

前序序列為ABCDEF,可確定二叉樹的根結(jié)點為A,由于后序序列最后訪問根結(jié)點，可

排除A、D兩項；由中序序列為ABCDEF可知，以A為根的這棵二叉樹不存在左子

樹，且由前序序列和中序序列相同可判斷出每棵子樹均不存在左子樹（即惟獨右子

樹），后序序列先訪問處于右子樹上的結(jié)點Fo

13.對長度為8的數(shù)組進(jìn)行快速排序，最多需要的比較次數(shù)為（）。（）

A、8

B、28（正確答案）

C、56

D、64

答案解析：參考解析：對長度為的線性表進(jìn)行快速排序，最壞情況下需要比較的

次數(shù)為n（n-l）/2o數(shù)組屬于線性表，故對長度為8的數(shù)組進(jìn)行快速排序，最多需

要的比較次數(shù)為8（87）/2=28。

14.循環(huán)隊列的存儲空間為Q（1:50）初始狀態(tài)為空。經(jīng)過一系列正常的入隊與退隊

操作后，front=24,rear=25。此時該循環(huán)隊列中的元素個數(shù)為（）。（）

A、1（正確答案）

B、49

C、50

D、25

答案解析：參考解析：若循環(huán)隊列的存儲空間為在循環(huán)隊列運轉(zhuǎn)起來后，

如果front<rear,則隊列中的元素個數(shù)為rear-front;如果front>rear,則隊列中

的元素個數(shù)為rear-front+mo本題中front〈rear,則隊列中的元素個數(shù)為25-

24=1。

15.設(shè)二叉樹共有375個結(jié)點，其中度為2的結(jié)點有187個。則度為1的結(jié)點個數(shù)

是0。0

A、不可能有這樣的二叉樹

B、1

C、188

D、0（正確答案）

答案解析：參考解析：對任何一棵二叉樹，度為0的結(jié)點（即葉子結(jié)點）總是比度

為2的結(jié)點多一個。本題中，度為2的結(jié)點個數(shù)為187,則度為0的結(jié)點個數(shù)為

187+1=188,則度為1的結(jié)點個數(shù)為375-187-188=0。

16.在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換（或者挪移）后0。（）

A、不會產(chǎn)生新的逆序

B、只能消除一個逆序

C、能消除多個逆序（正確答案）

D、消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多

答案解析：參考解析：在一個羅列中，如果一對數(shù)的先后位置與大小順序相反，

即前面的數(shù)大于后面的數(shù)，那末它們就稱為一個逆序?？焖倥判虻乃枷胧?從線性

表中選取一個元素，設(shè)為T,將線性表中后面小于T的元素移到前面，而前面大于T

的元素移到后面；結(jié)果就將線性表分成兩部份（稱兩個子表），1'插入到其分割線的

位置處，這個過程稱為線性表的分割，然后再用同樣的方法對分割出的子表再進(jìn)行

同樣的分割?？焖倥判虿皇菍蓚€相鄰元素進(jìn)行比較，可以實現(xiàn)通過一次交換而消

除多個逆序，但由于均與T（基準(zhǔn)元素）比較，也可能會產(chǎn)生新的逆序。

17.帶鏈棧空的條件是0。（）

A、top=bottom=-l

B、top二T且bottom=NULL

C、top=NULL且bottom二T

D、top=bottomnNULL（正確答案）

答案解析：參考解析：帶鏈的棧是具有棧屬性的鏈表。線性鏈表的存儲單元是不

連續(xù)的。因為是不連續(xù)的存儲空間，所以指針將不會有規(guī)律地連續(xù)變化。當(dāng)

top二bottom=NULL時、棧為空；當(dāng)top=bottom且不等于NULL時；棧中存在一個元

素，其他情況無法判斷。

18.某徹底二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該徹底二叉樹

的前序序列為。。（）

A、ABCDEFGH

B、ABDHECFG（正確答案）

C、HDBEAFCG

D、HDEBFGCA

答案解析：參考解析：徹底二叉樹是指除最后一層外，每一層上的節(jié)點數(shù)均達(dá)到

最大值，在最后一層上只缺少右邊的若干結(jié)點。本題中，徹底二叉樹按層次輸出

（同一層從左到右）的序列為ABCDEFGH,則這棵二叉樹如下圖所示，其前序序列為

ABDHECFG?

A

BC

19.下列敘述中錯誤的是0。0

A、線性結(jié)構(gòu)也能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

B、線性結(jié)構(gòu)一定能采用順序存儲結(jié)構(gòu)

C、有的非線性結(jié)構(gòu)也能采用順序存儲結(jié)構(gòu)

D、非線性結(jié)構(gòu)一定不能采用順序存儲結(jié)構(gòu)（正確答案）

答案解析：參考解析：二叉樹屬于非線性結(jié)構(gòu)，但滿二叉樹與徹底二叉樹可以按

層次進(jìn)行順序存儲。

20.帶鏈隊列空的條件是0。（）

A、front=rear=NULL（正確答案）

B、front=T且rear=NULL

C、front=NULL且rear=-l

D、front=rear=-l

答案解析：參考解析：帶鏈的隊列是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的隊列。鏈?zhǔn)酱鎯Φ?/p>

存儲單元是不連續(xù)的，因為是不連續(xù)的存儲空間，所以指針將不會有規(guī)律地連續(xù)變

化。當(dāng)front=rear=NULL時，隊為空；當(dāng)front=rear且不等于NULL時，隊列中存

在一個元素，其他情況無法判斷。

21.在具有2n個結(jié)點的徹底二叉樹中，葉子結(jié)點個數(shù)為0。（）

A、n-l

B、n（正確答案）

C>n+1

D、n/2

答案解析：參考解析:對任何一棵二叉樹，度為0的結(jié)點（即葉子結(jié)點）總是比度為

2的結(jié)點多一個。在徹底二叉樹中，只在最后一層上缺少右邊的若干結(jié)點，所以度

為1的結(jié)點個數(shù)為或者1。假設(shè)度為2的結(jié)點個數(shù)為x,則葉子結(jié)點個數(shù)為x+1。

若度為1的結(jié)點個數(shù)為0,x+x+1+O無法和2n相等，不存在這樣的二叉樹，則度

為1的結(jié)點個數(shù)為1,x+x+l+l=2n,x=nT,所以葉子結(jié)點個數(shù)為n。

22.設(shè)順序表的長度為16,對該表進(jìn)行簡單插入排序。在最壞情況下需要的比較次

數(shù)為0。。

A、30

B、60

C、120（正確答案）

D、15

答案解析：參考解析:對長度為n的線性表進(jìn)行簡單插入排序，最壞情況下需要比

較的次數(shù)為n（n-l）/2?故對長度為16的線性表進(jìn)行簡單插入排序，最壞情況下需

要比較的次數(shù)為16（16-1）/2=120。

23.循環(huán)隊列的存儲空間為Q（l:50）?經(jīng)過一系列正常的入隊與退隊操作后，

front=rear=25o后又成功地將一個元素退隊，此時隊列中的元素個數(shù)為0。（）

A、24

B、49（正確答案）

C、26

D、0

答案解析：參考解析:設(shè)循環(huán)隊列的存儲空間為Q（l：m）,當(dāng)front=rear=m時，循環(huán)

隊列為空；當(dāng)front=rear且不等于m時，循環(huán)隊列可能為空，也可能為滿。當(dāng)為空

時，可以插入元素；當(dāng)為滿時，插入元素會發(fā)生“上溢”錯誤。題目中已經(jīng)說明

“成功地將一個元素退隊”，說明之前循環(huán)隊列的狀態(tài)為滿，退出一個元素后，隊

列中還有50-1=49個元素。

24.設(shè)二叉樹的后序序列與中序序列均為ABCDEFGH,則該二叉樹的前序序列為0。

0

A、HGFEDCBA（正確答案）

B、ABCDEFGH

C、ABCDHGFE

D、DCBAHGFE

答案解析：參考解析:二叉樹遍歷可以分為3種:前序遍歷（訪問根結(jié)點在訪問左子

樹和訪問右子樹之前）、中序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹兩者之

間）、后序遍歷（訪問根結(jié)點在訪問左子樹和訪問右子樹之后）。本題中，二叉樹的

后序序列為ABCDEFGH,可確定該二叉樹的根結(jié)點為H,由于前序序列首先要訪問根

結(jié)點H,可直接排除B、C、D三項。

25.設(shè)順序表的長度為40,對該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為

（）。0

A、40

B、41

C、780（正確答案）

D、820

答案解析：參考解析:對長度為n的線性表進(jìn)行冒泡排序，最壞情況下需要比較的

次數(shù)為n（n-l）/2o故對長度為40的線性表進(jìn)行冒泡排序，最壞情況下需要比較的

次數(shù)為40（40-1）/2=780。

26.在帶鏈隊列中，經(jīng)過一系列正常的操作后，如果front=rear,則隊列中的元素

個數(shù)為0。。

A、0

B、1

C、0或者1（正確答案）

D、隊列滿

答案解析：參考解析:帶鏈的隊列是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的隊列。鏈?zhǔn)酱鎯Φ拇?/p>

儲單元是不連續(xù)的，因為是不連續(xù)的存儲空間，所以指針將不會有規(guī)律地連續(xù)變

化。當(dāng)front=rear=NULL時，隊為空；當(dāng)front=rear且不等于NULL時，隊列中只

存在一個元素，其他情況無法判斷。

27.設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點值均小于根結(jié)點值，而右子樹

上的結(jié)點值均不小于根結(jié)點值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷

結(jié)果為有序序列的是0。（）

A、前序序列

B、中序序列（正確答案）

C、后序序列

D、前序序列或者后序序列

答案解析：參考解析:在該二叉樹中，左