國家電網(wǎng)招聘-計算機 (電網(wǎng))真題庫-14

國家電網(wǎng)招聘-計算機(電網(wǎng))真題庫_141、單選題函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為()。A、

“STRUCTURE”B、

“DATA”C、

“DATASTR（江南博哥）UCTURE”D、

“ASTRUCTUR”正確答案：

A

參考解析：substr函數(shù)的作用是找到從第5個字符開始，長度為9的子串。2、單選題當(dāng)出現(xiàn)擁塞時路由器會丟失報文，同時向該報文的源主機發(fā)送()類型的報文A、

TCP請求B、

TCP響應(yīng)C、

ICMP請求與響應(yīng)D、

ICMP源點抑制正確答案：

D

參考解析：當(dāng)出現(xiàn)擁塞時路由器會丟失報文，同時向該報文的源主機發(fā)送ICMP源點抑制類型的報文。3、單選題二路歸并排序的時間復(fù)雜度為()。A、

AB、

BC、

CD、

D正確答案：

C

參考解析：4、單選題設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是()。A、

n在m右方B、

n是m祖先C、

n在m左方D、

n是m子孫正確答案：

C

參考解析：中序遍歷時，先訪問左子樹，再訪問根結(jié)點。n在m前，則n必須在m的左子樹中。5、單選題假定一棵度為3的樹中結(jié)點數(shù)為50，則其最小高度應(yīng)為()。A、

5B、

6C、

3D、

4正確答案：

A

參考解析：6、單選題一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是()。A、

43512B、

12345C、

54321D、

45321正確答案：

A

參考解析：此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序(指的是元素的序號)的兩個元素。7、單選題在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作()型調(diào)整以使其平衡。A、

LLB、

LRC、

RLD、

RR正確答案：

C

參考解析：平衡二叉樹是在構(gòu)造=叉排序樹的過程中，每當(dāng)插入一個新結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系。進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。具體步驟如下：(1)每當(dāng)插入一個新結(jié)點，從該結(jié)點開始向上計算各結(jié)點的平衡因子，即計算該結(jié)點的祖先結(jié)點的平衡因子，若該結(jié)點的祖先結(jié)點的平衡因子的絕對值均不超過1，則平衡=叉樹沒有失去平衡，繼續(xù)插入、結(jié)點；(2)若插入結(jié)點的某祖先結(jié)點的平衡因子的絕對值大于1，則找出其中最小不平衡子樹的根結(jié)點；(3)判斷新插入的結(jié)點與最小不平衡子樹的根結(jié)點的關(guān)系，確定是哪種類型的調(diào)整；(4)如果是LL型或RR型，只需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)一次，在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；如果是LR型或LR型，則需應(yīng)用扁擔(dān)原理旋轉(zhuǎn)兩次，第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在子樹，第二次再調(diào)整最小不平衡子樹。在旋轉(zhuǎn)過程中，如果出現(xiàn)沖突，應(yīng)用旋轉(zhuǎn)優(yōu)先原則調(diào)整沖突；(5)計算調(diào)整后的平衡二叉樹中各結(jié)點的平衡因子，檢驗是否因為旋轉(zhuǎn)而破壞其他結(jié)點的平衡因子，以及調(diào)整后的平衡二叉樹中是否存在平衡因子大于1的結(jié)點。結(jié)合上面的知識點，對于題目中的情況應(yīng)該選擇RL型調(diào)整。8、單選題兩個字符串相等的充要條件是()。A.兩個字符串中對應(yīng)位置上的字符相等B.兩個字符串的長度相等A、

同時具備B、

和C、

兩個條件D、

兩個字符串的大小相等正確答案：

C

參考解析：兩個字符串相等是指兩個字符串不僅長度相等，而且在對應(yīng)位置上的字符也要相等。9、單選題m階B+樹中除根節(jié)點外，其他節(jié)點的關(guān)鍵字個數(shù)至少為()。A、

[m/2]B、

[m/2]-1C、

[m/2]+1D、

任意正確答案：

A

參考解析：這是B+樹的定義。10、單選題A、

O(m×n×t)B、

O(m+n+t)C、

O(m×t+n)D、

O(m+n×t)正確答案：

A

參考解析：在程序段中，有兩段循環(huán)程序，第一段是一個雙層嵌套循環(huán)，另一個是三層嵌套循環(huán)，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共執(zhí)行m×t×n次。11、單選題下面關(guān)于圖的遍歷說法不正確的是()。A、

遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程B、

深度優(yōu)先搜索和廣度優(yōu)先搜索對無向圖和有向圖都適用C、

深度優(yōu)先搜索和廣度優(yōu)先搜索對頂點訪問的順序不同，它們的時間復(fù)雜度也不相同D、

深度優(yōu)先搜索是一個遞歸的過程，廣度優(yōu)先搜索的過程中需附設(shè)隊列正確答案：

C

參考解析：深度優(yōu)先搜索和廣度優(yōu)先搜索的時間算雜度相同，均為O(n+e)。12、單選題對于棧操作數(shù)據(jù)的原則是()。A、

先進先出B、

后進先出C、

后進后出D、

不分順序正確答案：

B

參考解析：棧的特點就是后進先出，入棧和出棧的操作只能在棧頇進行.而隊列的特點是先進先出，這兩點容易混淆，要注意區(qū)分。13、單選題在一臺安裝好TCP/IP協(xié)議的PC上，當(dāng)網(wǎng)絡(luò)連接不可用時，為了測試編寫好的網(wǎng)絡(luò)程序，通常使用的目的主機IP地址為()A、

B、

C、

D、

25正確答案：

B

參考解析：當(dāng)網(wǎng)絡(luò)連接不可用時，為了測試編寫好的網(wǎng)絡(luò)程序，通常使用的目的主機IP地址為（環(huán)回地址）。14、單選題廣義表(a，b，(c，(d)))的表尾是()。A、

(b，(c，(d))B、

(b，(c，(d)))C、

(d)D、

(c，(d))正確答案：

B

參考解析：廣義表的第一個表元素為表頭，由表中除表頭外的其他元素組成的表稱為廣義表的表尾。15、單選題若G是一個具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G至少有()個頂點。A、

11B、

10C、

9D、

8正確答案：

B

參考解析：要使圖的頂點數(shù)最少，應(yīng)該盡量構(gòu)造一個完全圖，具有36條邊的無向完全圖的頂點數(shù)是9，又因為圖示非連通的，所以再加一個孤立的頂點即可。所以至少有10個頂點。16、單選題已知二叉樹的前序序列為ABCDEFG，中序序列為DBCAFEG，則后序序列為()。A、

DCBAFGEB、

DCBFGEAC、

DCBFEGAD、

DCBGFEA正確答案：

B

參考解析：本題考查的是二叉樹的遍歷過程。在本題中，由于前序遍歷首先訪問的是根結(jié)點，所以根結(jié)點是A，又由于后序遍歷最后訪問的是根結(jié)點，所以排除選項A；根據(jù)中序序列知道，DBC是左子樹的結(jié)點，F(xiàn)EG是右子樹的結(jié)點。17、單選題表長為n的順序存儲的線性表，當(dāng)在任何位置上刪除一個元素的概率相等時，刪除一個元素所需移動元素的平均個數(shù)為()。A、

nB、

n/2C、

(n-1)/2D、

(n+1)/2正確答案：

C

參考解析：18、單選題A、

(1)，(2)，(3)B、

(1)C、

(1)，(3)D、

(2)，(3)正確答案：

C

參考解析：19、單選題在一裸m階的B+樹中，每個非葉結(jié)點的兒子數(shù)S應(yīng)滿足()。A、

AB、

BC、

CD、

D正確答案：

A

參考解析：m階B+樹包含如下兩個特點：(1)每個分支結(jié)點至多有m棵子樹。(2)除根結(jié)點外的所有非終端結(jié)點每個結(jié)點至少有1(m+1)/21棵子樹。20、單選題若對序列(tang，deng，an，wang，shi，bai，fang，liu)采用選擇排序法按字典順序進行排序，下面給出的四個序列中，()是第三趟的結(jié)果。A、

an.bai，deng，wang，tang，fang，shi，huB、

an，bai，deng，wang，shi，tang，fang，liuC、

an.bai，deng，wang，shi，fang，tang，liuD、

an.bai，deng，wang，shi，liu，tang，fang正確答案：

B

參考解析：選擇排序是指每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素，順序地放在已排好序的數(shù)列的最后，直到待排序數(shù)據(jù)元素全部排完。按字典順序排序的排序過程如下:第一趟:an,deng,tang,wang，shi,bai,fang,liu;.第二趟，an,bai,tang,wang，shi，deng,fang,liu;第三趟:an,bai，deng,wang，shi,tang,fang,liup第四趟:an,bai,deng,fang，shi,tang,wang,liu;第五趟，an,bai，deng,fang，liu,tang,wang，shi;第六趟:an,bai,deng,fang,liu,slu,wang,tang;第七趟:an.bai,deng,fang,liu,shi,tang,中ang。21、單選題有m個葉子結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為()。A、

mB、

m+1C、

2mD、

2m-1正確答案：

D

參考解析：哈夫曼樹中僅有度為0和2的結(jié)點，由二叉樹的性質(zhì)可知，具有m個葉子結(jié)點的哈夫曼樹具有m-1個度為2的結(jié)點，因此，具有m個葉子結(jié)點的哈夫曼樹所具有的節(jié)點數(shù)為2m-1。22、單選題二叉樹若用順序方法存儲，則下列四種算法中運算時間復(fù)雜度最小的是()。A、

先序遍歷二叉樹B、

判斷兩個指定位置的結(jié)點是否在同一層上C、

層次遍歷二叉樹D、

根據(jù)結(jié)點的值查找其存儲位置正確答案：

B

參考解析：23、單選題設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為()。A、

AB、

BC、

CD、

D正確答案：

B

參考解析：24、單選題網(wǎng)絡(luò)28/26的廣播地址為(請作答此空)，可用主機地址數(shù)()A、

59B、

91C、

192.168.2l.224D、

55正確答案：

B

參考解析：網(wǎng)絡(luò)28/26的廣播地址為91，可用主機地址數(shù)62。25、單選題設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H(key)=keyMOD13，散列地址為1的鏈中有()個記錄。A、

1B、

2C、

3D、

4正確答案：

D

參考解析：由散列函數(shù)H(key)=keyMOD13計算每個記錄的散列地址，散列地址為1的關(guān)鍵字有14，1，27，79，共4個記錄。26、單選題一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為()。A、

11B、

10C、

11至1025之間D、

10至1024之間正確答案：

C

參考解析：在具有n個結(jié)點的二叉樹中完全二叉樹的樹高最小，其為[logn]+1，單支二叉樹，即每層只有一個結(jié)點，樹高最大，其為n。因此，具有1025個結(jié)點的二叉樹樹高應(yīng)在11至1025之間。27、單選題設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。A、

10，15，14，18，20，36，40，21B、

15，10，14，18，20，36，40，21C、

10，15，14，20，18，40，36，21D、

10，15，14，18，20，40，36，21正確答案：

A

參考解析：快速排序的每趟排序在待排序列中選取一個數(shù)為基準(zhǔn)，將序列劃分為兩段，一段的值比基準(zhǔn)值小，另一段大于或等于基準(zhǔn)值。在快速排序中通常有兩個指針分別為i和j，j從后向前遍歷，找第一個小于基準(zhǔn)值的節(jié)點，將值交換，i從前向后遍歷，找到第一個大于或等于基準(zhǔn)值的節(jié)點，將值交換，重復(fù)此過程，直至i和j指向同一節(jié)點，一趟排序結(jié)束。28、單選題設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為()。A、

15，25，35，50，20，40，80，85，36，70B、

15，25，35，50，80，20，85，40，70，36C、

15，25，35，50，80，20，36，40，70，85D、

15，25，35，50，80，85，20，36，40，70正確答案：

A

參考解析：歸并排序的每趟排序?qū)⑾噜彽膬蓚€子序列合并，直至剩兩個子序列，合并后產(chǎn)生一個序列，即為最終排序結(jié)果。29、單選題采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為()。A、

(n-1)/2B、

(n+1)/2C、

nD、

n/2正確答案：

B

參考解析：搜索的最好情況是第一個元素即想要查找的元素，最壞的情況是最后一個元素即想要查找的元素，所以平均查找長度是(n+l)/2。30、單選題某高度為k的完全二叉樹中，所含葉子結(jié)點的個數(shù)最少為()。A、

AB、

BC、

CD、

D正確答案：

C

參考解析：31、單選題設(shè)二維數(shù)組A[6][0]，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素，a[0][0]的存儲地址為860，則a[3][5]的存儲地址為()。A、

1000B、

860C、

1140D、

1200正確答案：

A

參考解析：每個數(shù)組元素占用4個存儲單元，按行優(yōu)先順序存放的數(shù)組元素，則a[3][5]的存儲地址為860+(3×10+5)×4=1000。32、單選題可以用()、數(shù)據(jù)關(guān)系和基本操作集定義一個完整的抽象數(shù)據(jù)類型。A、

數(shù)據(jù)元素B、

數(shù)據(jù)對象C、

原子類型D、

存儲結(jié)構(gòu)正確答案：

B

參考解析：抽象數(shù)據(jù)類型可用(數(shù)據(jù)對象，數(shù)據(jù)關(guān)系，基本操作集)三元組來表示。33、單選題在采用線性探測法處理沖突所構(gòu)成的散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值()。A、

一定都是同義詞B、

一定都不是同義詞C、

不一定都是同義詞D、

都相同正確答案：

C

參考解析：采用線性探測法處理沖突會產(chǎn)生堆積，即非同義詞爭奪同一個后繼地址。34、單選題以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。A、

循環(huán)隊列B、

鏈表C、

哈希表D、

棧正確答案：

D

參考解析：數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，它們是數(shù)據(jù)的兩種最基本的存儲結(jié)構(gòu)。ABC三項，都屬于鏈?zhǔn)酱鎯Y(jié)構(gòu)。D項，棧則是指從應(yīng)用的角度來說的一種后進先出的線性表結(jié)構(gòu)，與具體的存儲結(jié)構(gòu)無關(guān)。35、單選題模擬信號調(diào)制為模擬信號時，由于基帶信號包含許多低頻信息或直流信息，而很多傳輸介質(zhì)并不能傳輸這些信息，因此需要使用調(diào)制器對基帶信號進行調(diào)制，下面選項中不屬于模擬信號調(diào)制為模擬信號方法的是()。A、

調(diào)波B、

調(diào)幅C、

調(diào)頻D、

調(diào)相正確答案：

A

參考解析：*模擬信號調(diào)制為模擬信號的方法有：調(diào)幅（AM）：依據(jù)傳輸?shù)脑寄M數(shù)據(jù)信號變化來調(diào)整載波的振幅。調(diào)頻（FM）：依據(jù)傳輸?shù)脑寄M數(shù)據(jù)信號變化來調(diào)整載波的頻率。調(diào)相（PM）：依據(jù)傳輸?shù)脑寄M數(shù)據(jù)信號變化來調(diào)整載波的初始相位。36、單選題SMTP使用的端口號是()A、

21B、

23C、

25D、

110正確答案：

C

參考解析：SMTP使用的端口號是25。37、單選題設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3]存放在什么位置？腳注(10)表示用10進制表示。()A、

678B、

688C、

692D、

696正確答案：

C

參考解析：A[2][2]是A[0][0]后面的第2n+2個元素，即2n+2=676-644，解得n=15。A[3][3]是A[2][2]后面的第n+1個元素，676+n+1=692，則A[3][3]存放位置是692。38、單選題下面關(guān)于Prim算法和KruskAl算法的時間復(fù)雜度正確的是()。A、

Prim算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稀疏圖B、

Prim算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)無關(guān)，適合于稠密圖C、

KruskAl算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稠密圖D、

KruskAl算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)無關(guān)，適合于稀疏圖正確答案：

B

參考解析：39、單選題線性表采用鏈接存儲時，其地址()。A、

必須是連續(xù)的B、

部分地址必須是連續(xù)的C、

一定是不連續(xù)的D、

連續(xù)與否均可以正確答案：

D

參考解析：線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。40、單選題下面幾個符號串編碼集合中，不是前綴編碼的是()。A、

{0，10，110，1111}B、

{11，10，001，101，0001}C、

{00，010，0110，1000}D、

{b，c，aa，aba，abb，abc}正確答案：

B

參考解析：前綴編碼的定義：任一個字符的編碼都不是另一個字符的編碼的前綴。B選項中10是101的前綴，因此其不是前綴編碼。41、單選題二叉排序樹中左子樹上所有結(jié)點的值均()根結(jié)點的值。A、

＜B、

=C、

＞D、

！=正確答案：

A

參考解析：二叉排序樹的左子樹的結(jié)點的值全部小于根結(jié)點的值，并且根結(jié)點的值小于右子樹左右結(jié)點的值。42、單選題以下關(guān)于查找方法的說法正確的是()。Ⅰ.順序查找法只能在順序存儲結(jié)構(gòu)上進行Ⅱ.二分查找法可以在有序的雙向鏈表上進行Ⅲ.分塊查找的效率與線性表被分為多少塊有關(guān)A、

Ⅰ、ⅡB、

Ⅱ、ⅢC、

Ⅰ、ⅢD、

只有Ⅲ正確答案：

D

參考解析：順序查找法可以在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上進行，而二分查找只能在順序存儲的有序表上進行即可以進行隨機存取的存儲結(jié)構(gòu)上進行。43、單選題時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。A、

堆排序B、

快速排序C、

希爾排序D、

冒泡排序正確答案：

A

參考解析：堆排序無論是最好情況還是最壞情況，時間復(fù)雜度都是相等的。44、單選題下列排序算法中，()算法可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A、

堆排序B、

冒泡排序C、

快速排序D、

插入排序正確答案：

D

參考解析：插入排序在最后一個元素被插入時，所有元素都要后移，即在最后一趟開始之前，所有元素都不在其最終的位置上。45、單選題A[N，N]是對稱矩陣，將下三角(包括對角線)以行序存儲到一維數(shù)組T[N(N+l)/2]q中，則對任一上三角元素A[i][j]對應(yīng)T[k]的下標(biāo)k是()。A、

i(1-1)/2+jB、

j(j-1)/2+iC、

i(j-i)/2+1D、

j(1-1)/2+1正確答案：

B

參考解析：將對稱矩陣A[N，N]下三角以行序存儲到一維數(shù)組T[N(N+1)/2]中。對應(yīng)的A[i][j]啪與T[k]的下標(biāo)k的關(guān)系為k=i(i-1)/2+j；但題目中是求任一上三角元素A[i][j]對應(yīng)T[k]的下標(biāo)k，在對稱矩陣中A[i][D]=A[i][i]，即上三角中的元素的A[i][j]存儲位置對應(yīng)下三角A[i][j]的存儲位置，所以k=j(j-1)/2+i。46、單選題如果一棵二叉樹結(jié)點的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹結(jié)點的中根遍歷序列()。A.必為A、B、CB.必為A、C、BA、

必為B、

C、

AD、

不能確定正確答案：

D

參考解析：47、單選題以下關(guān)于TCP/IP協(xié)議和層次對應(yīng)關(guān)系的表示，正確的是()A、

AB、

BC、

CD、

D正確答案：

A

參考解析：TCP和UDP均基于IP協(xié)議協(xié)議棧中的傳輸層協(xié)議，其中TCP是面向連接的，UDp是無連接的。48、單選題由元素序列(27，16，75，38，51)構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根(即離插入結(jié)點最近且平衡因子的絕對值為2的結(jié)點)為()。A、

27B、

38C、

51D、

75正確答案：

D

參考解析：49、單選題對于一個長度為n的任憊表進行排序，至少需要進行的比較次數(shù)是()。A、

AB、

BC、

CD、

D正確答案：

D

參考解析：50、單選題向一個帶頭結(jié)點HS的鏈棧中插入一個s所指結(jié)點時需執(zhí)行()。A、

HS-＞next=s；B、

s-＞next=HS-＞next；HS-＞next=s；C、

s-＞next=HS：HS=s；D、

s-＞next=HS；HS=HS-＞next；正確答案：

B

參考解析：為了將結(jié)點s插入到帶頭結(jié)點HS的鏈棧中，首先需要修改s的指針域，使得s的下一個結(jié)點為鏈棧中的第一個有效結(jié)點，即數(shù)據(jù)域中存放有效數(shù)據(jù)的結(jié)點，該結(jié)點可由HS的指針域獲得，因此相應(yīng)的語句為s-＞next=HS-＞next，之后使s結(jié)點成為鏈棧中的第一個有效結(jié)點，即HS的指針域指向s，相應(yīng)的語句為HS-＞next=S。51、單選題A、

iB、

n-iC、

n-i+lD、

不確定正確答案：

C

參考解析：根據(jù)題中所敘述情況，棧的輸出序列一定是輸入序列的逆序。52、單選題以下哪一個不是棧的基本運算()。A、

刪除棧頂元素B、

刪除棧底元素C、

判斷棧是否為空D、

將棧置為空棧正確答案：

B

參考解析：棧的基本運算有人棧、出棧(刪除棧頂元素)、初始化、置空、判斷是否為空或滿、提取棧頂元素等，對棧元素的操作都是在棧頂進行的53、單選題假設(shè)執(zhí)行語句S的時間為0(1)，則執(zhí)行下列程序段的時間為()。for(i=l;k=n;it+)for(j=l;jA、

0(n)B、

0(n^2)C、

O(n×i)D、

0(n+1)正確答案：

B

參考解析：觀察可知，程序段S的執(zhí)行頻度為T(n)=n^2，得時間復(fù)雜度T(n)=O(n^2)。54、單選題在一個單鏈表HL中，若要向表頭插入一個由指針P指向的結(jié)點，則執(zhí)行()。A、

HL=P；P—＞next=HL；B、

P—＞next=HL；HL=P；C、

P—＞next=HL；P=HL；D、

P—＞next=HL—＞next；HL—＞next=P；正確答案：

B

參考解析：根據(jù)插入運算的定義，需要修改頭指針HL，令其指向結(jié)點P，同時結(jié)點P的指針域應(yīng)指向原來的頭結(jié)點。修改了頭指針HL會影響后面操作，所以必須先將P的指針域指向頭結(jié)點(P—＞next=HL)，再修改HL(即HL=P)。55、單選題快速排序最易發(fā)揮其長處的情況是()。A、

被排序的數(shù)據(jù)中含有多個相同排序碼B、

被排序的數(shù)據(jù)已基本有序C、

被排序的數(shù)據(jù)完全無序D、

被排序的數(shù)據(jù)中的最大值和最小值相差懸殊正確答案：

C

參考解析：56、單選題已知有一維數(shù)組A[0.m×n-1]，若要對應(yīng)為m行n列的矩陣，則下面的對應(yīng)關(guān)系()，可將元素A[k](O≤＜k≤＜m×n)表示成矩陣的第i行、第j列的元素(0≤i≤m，0勻≤n)。A、

i=k/n，j=k%mB、

i=k/m，j=k%mC、

i=k/n，j=k%nD、

i=k/m，j=k%n正確答案：

C

參考解析：矩陣每一行有n個元素，則第i+l行、第j+l到的元素～在A中是第n×i+j+l個元素，對應(yīng)的下標(biāo)k=nXi+j(因為下標(biāo)從0開始)。反過來：i=k/n，j=k%n。57、單選題A、

{(1，4)，(2，3)，(2，5)}B、

{(3，5)，(3，4)，(4，5)}C、

{(1，3)，(3，4)，(3，5)}D、

{(2，3)，(3，4)，(2，5)}正確答案：

A

參考解析：58、單選題在TCP/IP協(xié)議體系結(jié)構(gòu)中，網(wǎng)際層的主要協(xié)議為()A、

IPB、

TCPC、

HTTPD、

SMTP正確答案：

A

參考解析：在TCP/IP協(xié)議體系結(jié)構(gòu)中，網(wǎng)際層的主要協(xié)議為IP。59、單選題A、

21/7B、

28/7C、

15/6D、

21/6正確答案：

A

參考解析：60、單選題設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()。A、

aedfcbB、

aedfbcC、

aebcfdD、

acfebd正確答案：

A

參考解析：61、單選題關(guān)于AVL(平衡二叉樹)，下列說法錯誤的是()。A、

左子樹與右子樹高度差最多為1B、

插入操作的時間復(fù)雜度為0(logn)C、

平衡二叉樹是二叉排序樹中的一種D、

使用平衡二叉樹的目的是為了節(jié)省空間正確答案：

D

參考解析：平衡二叉樹是平衡二又排序樹的簡稱。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：①左、右子樹的高度之差不超過1；②左、右子樹也是平衡二叉樹；平衡二叉樹沒有節(jié)省空間，引入其目的是防止排序二叉樹左、右子樹高度失衡。62、單選題A、

3B、

6C、

9D、

以上答案均不正確正確答案：

A

參考解析：鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V，E)是具有n個頂點的圖，頂點序號依次為l，2，……，n，則G的鄰接矩陣是n階方陣，所以該圖有3個頂點。63、單選題如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是()A、

3B、

4C、

1D、

2正確答案：

B

參考解析：結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是4。64、單選題用s表示入棧操作，*表示出棧操作，棧的初態(tài)、終態(tài)均為空，人棧和出棧的操作序列可表示成僅為由S和*組成的序列。下面的序列中合法的操作序列有()。A、

S*SS*S**B、

SSS****SC、

S**S*SS*D、

SSS*S*S*正確答案：

A

參考解析：要使棧的初態(tài)、終態(tài)均為空，入棧和出棧的操作次數(shù)應(yīng)該相等，因此排除D項。而BC兩項項都出現(xiàn)某一時刻棧已空的情況下執(zhí)行出棧操作。65、單選題先序遍歷序列和中序遍歷序列相同的二叉樹為()。A、

根結(jié)點無左子樹的二叉樹B、

根結(jié)點無右子樹的二叉樹C、

只有根結(jié)點的二叉樹或非子結(jié)點只有左子樹的二叉樹D、

只有根結(jié)點的二叉樹或非葉子結(jié)點只有右子樹的二叉樹正確答案：

D

參考解析：先序遍歷的次序為根一左一右，而中序遍歷的次序為左一根一右，樹中肯定有根結(jié)點，要使先序遍歷序列和中序遍歷序列相同，兩種遍歷次序可以相同的次序為根一右。所以滿足條件的樹為只有根結(jié)點的二叉樹或非葉子結(jié)點只有右子樹的二叉樹。66、單選題設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為()。A、

AB、

BC、

CD、

D正確答案：

C

參考解析：數(shù)組是隨機存取的結(jié)構(gòu)，所以讀取第i個節(jié)點的時間復(fù)雜度為0(1)。67、單選題A、

AB、

BC、

CD、

D正確答案：

C

參考解析：68、單選題設(shè)二叉排序樹中關(guān)鍵字由1～1000的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點，下列關(guān)鍵字序列不可能是在二叉排序樹上查找到的序列是()。A、

2，252，401，398，330，344，397，363B、

924，220，911，244，898，258，362，363C、

925，202，911，240，912，245，363D、

2，399，387，219，266，382，381，278，363正確答案：

C

參考解析：把這四個序列各插入到一個初始為空的二叉排序樹中，可以發(fā)現(xiàn)，C序列形成的不是一條路徑，而是有分支的，可見它是不可能在查找過程中訪問到的序列。69、單選題可支持10公里以上傳輸距離的介質(zhì)是()A、

同軸電纜B、

雙絞線C、

多模光纖D、

單模光纖正確答案：

D

參考解析：可支持10公里以上傳輸距離的介質(zhì)是單模光纖。70、單選題假設(shè)有k個關(guān)鍵字互為同義詞，若用線性探查法把這k個關(guān)鍵字存入，至少要進行的探查次數(shù)是()。A、

k-1B、

kC、

k+1D、

k(k+1)/2正確答案：

D

參考解析：假設(shè)有k個關(guān)鍵字互為同義詞，若用線性探查法把這k個關(guān)鍵字存入，探查次數(shù)最少的情況是第1個關(guān)鍵字通過1次比較后插入，第2個關(guān)鍵字通過2次比較后插入，…，第k個關(guān)鍵字通過k次比較后插入。總的比較次數(shù)=1+2+…+k=k(k+1)/2。71、單選題引入二叉線索樹的目的是()。A、

加快查找結(jié)點的前驅(qū)或后繼的速度B、

為了能在二叉樹中方便地進行插入與刪除C、

為了能方便地找到雙親D、

使二叉樹的遍歷結(jié)果唯一正確答案：

A

參考解析：當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)存儲非線索化的二叉樹時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在任一遍歷序列中的直接前驅(qū)和直接后繼的結(jié)點信息，這種信息只有在遍歷的動態(tài)過程中才能得到。二叉線索樹利用空鏈域存放結(jié)點的前驅(qū)和后繼結(jié)點的信息，這樣能保存遍歷過程中得到的信息?？梢姡攵婢€索樹的目的是方便查找結(jié)點的前驅(qū)或后繼結(jié)點的速度。72、單選題堆排序分為兩個階段，其中第一階段將給定的序列建成一個堆，第二階段逐次輸出堆頂元素。設(shè)給定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一階段將該序列建成一個堆(大根堆)，那么交換元素的次數(shù)為()。A、

5B、

6C、

7D、

8正確答案：

B

參考解析：73、單選題KMP算法的特點是在模式匹配時指示主串的指針()。A、

不會變大B、

不會變小C、

都有可能D、

無法判斷正確答案：

B

參考解析：在KMP算法中，模式匹配時主串不會回溯，所以主串的指針不會變小。74、單選題若采用鄰接矩陣來存儲簡單有向圖，則其某一個頂點i的入度等于該矩陣()。A、

第i行中值為1的元素個數(shù)B、

所有值為1的元素個數(shù)C、

第i行及第i列中值為1的元素總個數(shù)D、

第i列中值為l的元素個數(shù)正確答案：

D

參考解析：對于無向圖，其鄰接矩陣的第i行的和即為第i個頂點的度。對于有向圖，鄰接矩陣的第i行元素的和即為第i個頂點的出度，而鄰接矩陣的第j列元素的和即為第j個頂點的出度。75、單選題樹形結(jié)構(gòu)的特點是：一個結(jié)點可以有()。A、

多個直接前驅(qū)B、

多個直接后繼C、

多個前驅(qū)D、

一個后繼正確答案：

B

參考解析：樹的唯一根節(jié)點無前驅(qū)，葉子結(jié)點可以有多個且無后繼，樹的其他結(jié)點可以有多個后繼但只能有一個前驅(qū)。76、單選題采用開放定址法處理散列表的沖突時，其平均查找長度()。A、

與鏈接法處理沖突相同B、

高于二分查找C、

低于鏈接法處理沖突D、

高于鏈接法處理沖突正確答案：

D

參考解析：開放定址法處理沖突的平均查找長度高于鏈接法。77、單選題文件有m個初始?xì)w并段，采用k路歸并時，所需的歸并遍數(shù)是()。A、

AB、

BC、

CD、

D正確答案：

D

參考解析：本題考查歸并排序時間復(fù)雜度相關(guān)問題。根據(jù)歸并排序的特點可以得到答案。78、單選題一組記錄的關(guān)鍵字為{25，50，15，35，80，85，20，40，36，70}，其中含有5個長度為2的有序表，用歸并排序方法對該序列進行一趟歸并后的結(jié)果是()。A、

15，25，35，50，20，40，80，85，36，70B、

15，25，35，50，80，20，85，40，70，36C、

15，25，50，35，80，85，20，36，40，70D、

15，25，35，50，80，20，36，40，70，85正確答案：

A

參考解析：歸并排序是多次將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。79、單選題二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是()A、

EB、

FC、

GD、

H正確答案：

C

參考解析：80、單選題某學(xué)校為防止網(wǎng)絡(luò)游戲沉迷，通常采用的方式不包括()A、

安裝上網(wǎng)行為管理軟件B、

通過防火墻攔截規(guī)則進行阻斷C、

端口掃描，關(guān)閉服務(wù)器端端口D、

賬戶管理，限制上網(wǎng)時長正確答案：

C

參考解析：通過端口掃描，關(guān)閉服務(wù)器端端口方法不能有效阻止代理上網(wǎng)，游戲。81、單選題字符串的長度是指()。A、

串中不同字母的個數(shù)B、

串中字符不同的個數(shù)C、

串中不同數(shù)字的個數(shù)D、

串中所含字符的個數(shù)正確答案：

D

參考解析：字符串的長度是指串中所含的字符的個數(shù)。82、單選題利用二叉鏈表存儲樹，則根結(jié)點的右指針為()。A、

指向最左孩子B、

指向最右孩子C、

空D、

非空正確答案：

C

參考解析：83、單選題A、

AB、

BC、

CD、

D正確答案：

D

參考解析：考查雙鏈表中插入操作，要注意保存后繼節(jié)點。84、單選題設(shè)n階方陣是一個上三角矩陣，則需存儲的元素個數(shù)為()。A、

nB、

n×nC、

n×n/2D、

n(n+1)/2正確答案：

D

參考解析：在上三角矩陣中，第一行有1個元素，第二行有2個元素，…，第n行有n個元素，則共n(n+1)/2個。85、單選題下列程序段的時間復(fù)雜度為()。for(i=0；i＜m；i++)for(j=0；j＜t；j++)e[i][j]=0；for(i=0；i＜m；i++)for(j=0；j＜t；j++)for(k=0；k＜n；k++)c[i][j]_c[i][j]+a[i][k]×b[k][j]；A、

O(m×n×t)B、

O(m+n+t)C、

O(m×t+n)D、

O(m+n×t)正確答案：

A

參考解析：在程序段中，有兩段循環(huán)程序，第一段是一個雙層嵌套循環(huán)，另一個是三層嵌套循環(huán)，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共執(zhí)行m×t×n次。86、單選題要求內(nèi)存量最大的排序算法是()。A、

插入排序B、

選擇排序C、

快速排序D、

歸并排序正確答案：

D

參考解析：選擇排序和插入排序的空間復(fù)雜度為O(1)；快速排序中的遞歸所耗費的?？臻g在最好情況下也為O(logn)；歸并排序中，由于每一趟都要一個TR數(shù)組來復(fù)制，所以需要與待排記錄等量的輔助空間為O(n)。87、單選題以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()A、

線性表B、

棧C、

隊列D、

二叉樹正確答案：

D

參考解析：線性表、棧、隊列都是線性結(jié)構(gòu)，樹、圖是非線性結(jié)構(gòu)。88、單選題設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n.則這棵二叉中共有()個結(jié)點。A、

2n+1B、

n+1C、

2n-1D、

2n正確答案：

C

參考解析：在二叉樹中度為2的結(jié)點個數(shù)為度為零的結(jié)點數(shù)減一，所以二叉樹共有2n-1個結(jié)點。89、單選題由圈權(quán)值為的四個葉子結(jié)點構(gòu)造一顆哈夫曼樹，該樹的帶權(quán)路徑長度為()。A、

23B、

37C、

44D、

46正確答案：

C

參考解析：90、單選題二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0～8，列下標(biāo)的范圍是從0～9，則存放A至少需要()個字節(jié)。A、

240B、

540C、

90D、

180正確答案：

B

參考解析：數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元。91、單選題以下關(guān)于路由器和交換機的說法中，錯誤的是()A、

為了解決廣播風(fēng)暴，出現(xiàn)了交換機B、

三層交換機采用硬件實現(xiàn)報文轉(zhuǎn)發(fā)，比路由器速度快C、

交換機實現(xiàn)網(wǎng)段內(nèi)幀的交換，路由器實現(xiàn)網(wǎng)段之間報文轉(zhuǎn)發(fā)D、

交換機工作在數(shù)據(jù)鏈路層，路由器工作在網(wǎng)絡(luò)層正確答案：

A

參考解析：路由器用于解決網(wǎng)絡(luò)風(fēng)暴。92、單選題已知一算術(shù)表達式的中