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

“STRUCTURE”B、

“DATA”C、

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

“ASTRUCTUR”正確答案：

A

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

TCP請求B、

TCP響應C、

ICMP請求與響應D、

ICMP源點抑制正確答案：

D

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

AB、

BC、

CD、

D正確答案：

C

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

n在m右方B、

n是m祖先C、

n在m左方D、

n是m子孫正確答案：

C

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

5B、

6C、

3D、

4正確答案：

A

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

43512B、

12345C、

54321D、

45321正確答案：

A

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

LLB、

LRC、

RLD、

RR正確答案：

C

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

同時具備B、

和C、

兩個條件D、

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

C

參考解析：兩個字符串相等是指兩個字符串不僅長度相等，而且在對應位置上的字符也要相等。9、單選題m階B+樹中除根節點外，其他節點的關鍵字個數至少為()。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

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

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

深度優先搜索和廣度優先搜索對無向圖和有向圖都適用C、

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

深度優先搜索是一個遞歸的過程，廣度優先搜索的過程中需附設隊列正確答案：

C

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

先進先出B、

后進先出C、

后進后出D、

不分順序正確答案：

B

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

B、

C、

D、

25正確答案：

B

參考解析：當網絡連接不可用時，為了測試編寫好的網絡程序，通常使用的目的主機IP地址為（環回地址）。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

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

DCBAFGEB、

DCBFGEAC、

DCBFEGAD、

DCBGFEA正確答案：

B

參考解析：本題考查的是二叉樹的遍歷過程。在本題中，由于前序遍歷首先訪問的是根結點，所以根結點是A，又由于后序遍歷最后訪問的是根結點，所以排除選項A；根據中序序列知道，DBC是左子樹的結點，FEG是右子樹的結點。17、單選題表長為n的順序存儲的線性表，當在任何位置上刪除一個元素的概率相等時，刪除一個元素所需移動元素的平均個數為()。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+樹中，每個非葉結點的兒子數S應滿足()。A、

AB、

BC、

CD、

D正確答案：

A

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

參考解析：選擇排序是指每一趟從待排序的數據元素中選出最小(或最大)的一個元素，順序地放在已排好序的數列的最后，直到待排序數據元素全部排完。按字典順序排序的排序過程如下:第一趟: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個葉子結點的哈夫曼樹所具有的結點數為()。A、

mB、

m+1C、

2mD、

2m-1正確答案：

D

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

先序遍歷二叉樹B、

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

層次遍歷二叉樹D、

根據結點的值查找其存儲位置正確答案：

B

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

AB、

BC、

CD、

D正確答案：

B

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

59B、

91C、

192.168.2l.224D、

55正確答案：

B

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

1B、

2C、

3D、

4正確答案：

D

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

11B、

10C、

11至1025之間D、

10至1024之間正確答案：

C

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

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

參考解析：歸并排序的每趟排序將相鄰的兩個子序列合并，直至剩兩個子序列，合并后產生一個序列，即為最終排序結果。29、單選題采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為()。A、

(n-1)/2B、

(n+1)/2C、

nD、

n/2正確答案：

B

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

AB、

BC、

CD、

D正確答案：

C

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

1000B、

860C、

1140D、

1200正確答案：

A

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

數據元素B、

數據對象C、

原子類型D、

存儲結構正確答案：

B

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

一定都是同義詞B、

一定都不是同義詞C、

不一定都是同義詞D、

都相同正確答案：

C

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

循環隊列B、

鏈表C、

哈希表D、

棧正確答案：

D

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

調波B、

調幅C、

調頻D、

調相正確答案：

A

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

21B、

23C、

25D、

110正確答案：

C

參考解析：SMTP使用的端口號是25。37、單選題設有一個二維數組A[m][n]，假設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、單選題下面關于Prim算法和KruskAl算法的時間復雜度正確的是()。A、

Prim算法的時間復雜度與網中的邊數有關，適合于稀疏圖B、

Prim算法的時間復雜度與網中的邊數無關，適合于稠密圖C、

KruskAl算法的時間復雜度與網中的邊數有關，適合于稠密圖D、

KruskAl算法的時間復雜度與網中的邊數無關，適合于稀疏圖正確答案：

B

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

必須是連續的B、

部分地址必須是連續的C、

一定是不連續的D、

連續與否均可以正確答案：

D

參考解析：線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也可以不連續，甚至可以零散分布在內存中任意位置。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、單選題二叉排序樹中左子樹上所有結點的值均()根結點的值。A、

＜B、

=C、

＞D、

！=正確答案：

A

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

Ⅰ、ⅡB、

Ⅱ、ⅢC、

Ⅰ、ⅢD、

只有Ⅲ正確答案：

D

參考解析：順序查找法可以在順序存儲結構和鏈式存儲結構上進行，而二分查找只能在順序存儲的有序表上進行即可以進行隨機存取的存儲結構上進行。43、單選題時間復雜度不受數據初始狀態影響而恒為0(nlog2n)的是()。A、

堆排序B、

快速排序C、

希爾排序D、

冒泡排序正確答案：

A

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

堆排序B、

冒泡排序C、

快速排序D、

插入排序正確答案：

D

參考解析：插入排序在最后一個元素被插入時，所有元素都要后移，即在最后一趟開始之前，所有元素都不在其最終的位置上。45、單選題A[N，N]是對稱矩陣，將下三角(包括對角線)以行序存儲到一維數組T[N(N+l)/2]q中，則對任一上三角元素A[i][j]對應T[k]的下標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]下三角以行序存儲到一維數組T[N(N+1)/2]中。對應的A[i][j]啪與T[k]的下標k的關系為k=i(i-1)/2+j；但題目中是求任一上三角元素A[i][j]對應T[k]的下標k，在對稱矩陣中A[i][D]=A[i][i]，即上三角中的元素的A[i][j]存儲位置對應下三角A[i][j]的存儲位置，所以k=j(j-1)/2+i。46、單選題如果一棵二叉樹結點的先根遍歷序列是A、B、C，后根遍歷序列是C、B、A，則該二叉樹結點的中根遍歷序列()。A.必為A、B、CB.必為A、C、BA、

必為B、

C、

AD、

不能確定正確答案：

D

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

AB、

BC、

CD、

D正確答案：

A

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

27B、

38C、

51D、

75正確答案：

D

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

AB、

BC、

CD、

D正確答案：

D

參考解析：50、單選題向一個帶頭結點HS的鏈棧中插入一個s所指結點時需執行()。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

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

iB、

n-iC、

n-i+lD、

不確定正確答案：

C

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

刪除棧頂元素B、

刪除棧底元素C、

判斷棧是否為空D、

將棧置為空棧正確答案：

B

參考解析：棧的基本運算有人棧、出棧(刪除棧頂元素)、初始化、置空、判斷是否為空或滿、提取棧頂元素等，對棧元素的操作都是在棧頂進行的53、單選題假設執行語句S的時間為0(1)，則執行下列程序段的時間為()。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的執行頻度為T(n)=n^2，得時間復雜度T(n)=O(n^2)。54、單選題在一個單鏈表HL中，若要向表頭插入一個由指針P指向的結點，則執行()。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

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

被排序的數據中含有多個相同排序碼B、

被排序的數據已基本有序C、

被排序的數據完全無序D、

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

C

參考解析：56、單選題已知有一維數組A[0.m×n-1]，若要對應為m行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個元素，對應的下標k=nXi+j(因為下標從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協議體系結構中，網際層的主要協議為()A、

IPB、

TCPC、

HTTPD、

SMTP正確答案：

A

參考解析：在TCP/IP協議體系結構中，網際層的主要協議為IP。59、單選題A、

21/7B、

28/7C、

15/6D、

21/6正確答案：

A

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

aedfcbB、

aedfbcC、

aebcfdD、

acfebd正確答案：

A

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

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

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

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

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

D

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

3B、

6C、

9D、

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

A

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

3B、

4C、

1D、

2正確答案：

B

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

S*SS*S**B、

SSS****SC、

S**S*SS*D、

SSS*S*S*正確答案：

A

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

根結點無左子樹的二叉樹B、

根結點無右子樹的二叉樹C、

只有根結點的二叉樹或非子結點只有左子樹的二叉樹D、

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

D

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

AB、

BC、

CD、

D正確答案：

C

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

AB、

BC、

CD、

D正確答案：

C

參考解析：68、單選題設二叉排序樹中關鍵字由1～1000的整數構成，現要查找關鍵字為363的結點，下列關鍵字序列不可能是在二叉排序樹上查找到的序列是()。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

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

同軸電纜B、

雙絞線C、

多模光纖D、

單模光纖正確答案：

D

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

k-1B、

kC、

k+1D、

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

D

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

加快查找結點的前驅或后繼的速度B、

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

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

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

A

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

5B、

6C、

7D、

8正確答案：

B

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

不會變大B、

不會變小C、

都有可能D、

無法判斷正確答案：

B

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

第i行中值為1的元素個數B、

所有值為1的元素個數C、

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

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

D

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

多個直接前驅B、

多個直接后繼C、

多個前驅D、

一個后繼正確答案：

B

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

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

高于二分查找C、

低于鏈接法處理沖突D、

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

D

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

AB、

BC、

CD、

D正確答案：

D

參考解析：本題考查歸并排序時間復雜度相關問題。根據歸并排序的特點可以得到答案。78、單選題一組記錄的關鍵字為{25，50，15，35，80，85，20，40，36，70}，其中含有5個長度為2的有序表，用歸并排序方法對該序列進行一趟歸并后的結果是()。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、單選題某學校為防止網絡游戲沉迷，通常采用的方式不包括()A、

安裝上網行為管理軟件B、

通過防火墻攔截規則進行阻斷C、

端口掃描，關閉服務器端端口D、

賬戶管理，限制上網時長正確答案：

C

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

串中不同字母的個數B、

串中字符不同的個數C、

串中不同數字的個數D、

串中所含字符的個數正確答案：

D

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

指向最左孩子B、

指向最右孩子C、

空D、

非空正確答案：

C

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

AB、

BC、

CD、

D正確答案：

D

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

nB、

n×nC、

n×n/2D、

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

D

參考解析：在上三角矩陣中，第一行有1個元素，第二行有2個元素，…，第n行有n個元素，則共n(n+1)/2個。85、單選題下列程序段的時間復雜度為()。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

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

插入排序B、

選擇排序C、

快速排序D、

歸并排序正確答案：

D

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

線性表B、

棧C、

隊列D、

二叉樹正確答案：

D

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

2n+1B、

n+1C、

2n-1D、

2n正確答案：

C

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

23B、

37C、

44D、

46正確答案：

C

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

240B、

540C、

90D、

180正確答案：

B

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

為了解決廣播風暴，出現了交換機B、

三層交換機采用硬件實現報文轉發，比路由器速度快C、

交換機實現網段內幀的交換，路由器實現網段之間報文轉發D、

交換機工作在數據鏈路層，路由器工作在網絡層正確答案：

A

參考解析：路由器用于解決網絡風暴。92、單選題已知一算術表達式的中