國家電網招聘-計算機(電網)真題庫_121、單選題通過CIDR技術，把4個主機地址110.18.168.5、110.18.169.10、110.18.172.15和110.18.173.254組織（江南博哥）成一個地址塊，則這個超級地址塊的地址是()。A、

110.18.170.0/21B、

110.18.168.0/21C、

110.18.169.0/20D、

110.18.175.0/20正確答案：

B

參考解析：CIDR（無類別域間路由）是一種用于將IP地址劃分為更小、更有意義的子網的技術。CIDR通過在IP地址后面添加一個斜杠和一個數字來指定子網掩碼的位數。給定的四個主機地址是110.18.168.5、110.18.169.10、110.18.172.15和110.18.173.254。要組織這些地址為一個CIDR地址塊，首先觀察這四個地址的前綴。這些地址的前綴都是110.18，也就是說，這些地址都屬于同一個前綴。接下來，我們需要找到一個子網掩碼，使得這四個地址都在同一個子網內。通過觀察這四個地址，我們可以發現它們的最后24位分別是5、10、15和254。這意味著這些地址都在子網掩碼為24位的網絡內，因為只有24位的子網掩碼才能容納從0到255的地址范圍。因此，我們將這個子網標記為“110.18.168.0/24”。然后，我們使用CIDR的規則來確定這個子網塊的大小。由于子網掩碼是24位，而主機地址的前綴是22位（前綴為110.18），因此這個子網塊的大小就是/22。因此，這個超級地址塊的地址是“110.18.168.0/22”。選項B“110.18.168.0/21”與我們的計算結果不符，因此不是正確答案。選項A“110.18.170.0/21”、C“110.18.169.0/20”和D“110.18.175.0/20”也不是正確答案，因為它們與給定的主機地址范圍不匹配。因此，正確答案是B“110.18.168.0/22”。2、單選題若對n階對稱矩陣A[1...n,1...n]以行序為主序方式將其下三角的元素(包括主對角線上的所有元素)依次存放于-維數組B[1...fl(n+1)/2]中，則在B中確定ass(iA、

i×(1-1)/2+jB、

j×(j-1)/2+iC、

i×(1+1)/2+jD、

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

B

參考解析：3、單選題若一個棧的輸入序列為1，2，3…，n，輸出序列的第一個元素是i，則第j個輸出元素是()。A、

i-j-1B、

i-jC、

j-i+lD、

不確定正確答案：

D

參考解析：棧是一種后進先出的線性表結構，但本題無法確定輸入和輸出的時間順序，即不一定是在所有元素輸入棧后再進行輸出。4、單選題某二叉樹的前序遍歷序列為UKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列為()。A、

JLKMNOIB、

LKNJOMIC、

LKJNOMID、

LKNoMI正確答案：

C

參考解析：5、單選題若一個具有n個結點、k條邊的非連通無向圖是一個森林(n＞k)，則該森林中必有()棵樹。A、

kB、

nC、

n-kD、

n+k正確答案：

C

參考解析：一個具有n個結點的樹有n-l條邊，結點數比邊數多1，則若一個森林中有m棵樹，其結點數比邊數多m。反過來，森林中樹的個數等于結點數減去邊數。6、單選題深度為k的完全二叉樹中最少有()個結點。A、

k-1B、

2C、

k+1D、

2-1正確答案：

B

參考解析：最少有兩個結點，一個為根結點，另一個為根結點的左子樹。7、單選題A、

LRNB、

NRLC、

RLND、

RNL正確答案：

D

參考解析：由7，5，6的順序可知遍歷順序為RNL。8、單選題一棵m階非空B-樹，每個結點最多有()棵子樹。A、

m/2B、

m-1C、

mD、

m+1正確答案：

C

參考解析：B-樹中每個結點之多有m棵子樹，m就是B-樹的階。9、單選題設森林F中有三棵樹，第一，第二，第三棵樹的結點個數分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是()。A、

M1B、

M1+M2C、

M3D、

M2+M3正確答案：

D

參考解析：森林轉換成二叉樹的原則：將第一棵樹的根結點作為根結點，所有結點的第一個左孩子作為左孩子，下一個兄弟結點作為右孩子，其它樹作為第一棵樹的右孩子。所以森林F對應的二叉樹根結點的右子樹上的結點個數是M2+M3。10、單選題m階B-樹是一棵()。A、

m叉排序樹B、

m叉平衡排序樹C、

m-l叉平衡排序樹D、

m+l叉平衡排序樹正確答案：

B

參考解析：B-樹又叫多路平衡查找樹，是一種組織和維護外存文件系統非常有效的數據結構。B-樹中每個結點之多有m棵子樹，m就是B-樹的階。m階B-樹就是一棵m叉平衡排序樹。11、單選題n個結點的線索二叉樹上含有的線索數為()。A、

nB、

2nC、

n-1D、

n+1正確答案：

D

參考解析：對于有n個結點的二叉樹，采用二叉鏈存儲結構時，每個結點有兩個指針域，總共有2n個指針域，由于只有n-1個結點被有效指針所指向.則共有2n-(n-1)=n+1個空鏈域。用這些空鏈域存放指向結點的前驅和后繼結點的指針，這些指針稱作線索。12、單選題在Windows系統中，若要將文件“D：\user\my.doc”設置成只讀屬性，可以通過修改該文件的()來實現。將文件設置為只讀屬性可控制用戶對文件的修改，這一級安全管理稱之為（請作答此空）安全管理。A、

用戶級B、

目錄級C、

文件級D、

系統級正確答案：

C

參考解析：從“設置成只讀屬性”可以看到，這是一個屬性。將文件設置為只讀屬性，顯然是針對文件級別的控制。13、單選題將某高級語言程序翻譯為匯編語言形式的目標程序，該過程稱為（）。A、

編譯B、

解釋C、

匯編D、

解析正確答案：

A

參考解析：這是編譯的基本概念。14、單選題SNMP管理模型由4部分組成，它們是管理站、()、網絡管理協議和管理信息庫。A、

管理控制臺B、

管理代理C、

管理標準D、

網絡管理員正確答案：

B

參考解析：網絡管理系統由以下4個要素組成：（1）管理站（NetworkManager）。管理站是位于網絡系統主干或者靠近主干的工作站，是網絡管理系統的核心，負責管理代理和管理信息庫，定期查詢代理信息，確定獨立的網絡設備和網絡狀態是否正常。（2）代理（Agent）。代理又稱為管理代理，位于被管理設備內部。負責收集被管理設備的各種信息和響應管理站的命令或請求，并將其傳輸到MIB數據庫中。代理所在地設備可以是網管交換機、服務器、網橋、路由器、網關及任何合法節點的計算機。（3）管理信息庫（ManagementInformationBase，MIB）。相當于一個虛擬數據庫，提供有關被管理網絡各類系統和設備的信息，屬于分布式數據庫。（4）網絡管理協議。用于管理站和代理之間傳遞、交互信息。常見的網管協議有SNMP和CMIS/CMIP。網管站通過SNMP向被管設備的網絡管理代理發出各種請求報文，代理則接收這些請求后完成相應的操作，可以把自身信息主動通知給網管站15、單選題從一個具有N個結點的單鏈表中查找其值等于X結點時，查找成功的情況下，需平均比較()結點。A、

NB、

N/2C、

(N-1)/2D、

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

D

參考解析：16、單選題在一個具有n個頂點的無向圖中，要連通全部頂點至少需要()條邊。A、

nB、

n+lC、

n-lD、

n/2正確答案：

C

參考解析：假設每頂點都和其他頂點有邊，則至少需要n-l條邊將所有頂點連通。17、單選題有n個記錄的文件，若關鍵字位數為d，基數為r，則基數排序共需進行()遍分配與收集。A、

nB、

rC、

dD、

d+r正確答案：

C

參考解析：18、單選題設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到HASH表中需要做()次線性探測。A、

n(n+1)B、

nC、

n(n+1)/2D、

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

C

參考解析：線性探測解決沖突的辦法指一旦目標空間被占有，則探測相鄰的下一個空間，如果空閑則插入，否則繼續向下一個探測，如果到了隊列末尾則返回隊列頭探測，一旦全部空間都被占據則無法插入。19、單選題設某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。A、

n(n-1)/2B、

n(n-1)C、

n+1D、

n正確答案：

A

參考解析：因為無向圖的邊是沒有方向的，所以完全無向圖有n(n-l)/2條邊。20、單選題在含有n個關鍵字的大頂堆中，關鍵字最小的記錄有可能存儲在()位置上。A、

n/2B、

n/2-1C、

1D、

n/2+2正確答案：

D

參考解析：21、單選題設某強連通圖中有n個頂點，則該強連通圖中至少有()條邊。A、

n+1B、

n(n-1)C、

nD、

n(n+1)正確答案：

C

參考解析：強連通圖是指在一個有向圖中，若從節點i到節點j有路徑，并且節點j到i有路徑，那么為強連通圖。22、單選題在有n個結點的二叉鏈表中，值為非空的鏈域的個數為()。A、

n-1B、

2n-1C、

n+1D、

2n+1正確答案：

A

參考解析：本題考查的是二叉樹的鏈式存儲。由于在有n個結點的二叉鏈表中，值為空的鏈域的個數為n+1個，而總的鏈域為2n(在二叉樹中每個結點頭2個鏈域)。所以，非空的鏈域的個數為2n-(n+1)=n-1。23、單選題含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過()。A、

n-1B、

nC、

1D、

n/2正確答案：

A

參考解析：若超過n-l，則路徑中必存在重復的頂點。24、單選題n個頂點的連通圖至少有多少條邊()。A、

n-1B、

nC、

n+1D、

0正確答案：

A

參考解析：至少要有(n-1)條邊(也就是樹)才能保證圖為連通圖。25、單選題生成樹協議(STP)的作用是()。A.通過阻塞冗余端口消除網絡中的回路A、

把網絡分割成多個虛擬局域網B、

通過學習機制建立交換機的MAC、

地址表D、

通過路由器隔離網絡中的廣播風暴正確答案：

A

參考解析：生成樹協議（SpanningTreeProtocol，STP）是一種鏈路管理協議，為網絡提供路徑冗余，同時防止產生環路。交換機之間使用網橋協議數據單元（BridgeProtocolDataUnit，BPDU）來交換STP信息。STP的作用有以下幾點：（1）邏輯上斷開環路，防止廣播風暴的產生。（2）當線路出現故障，斷開的接口被激活，恢復通信，起備份線路的作用。（3）形成一個最佳的樹型拓撲。但是要注意選項D的說法不是STP的功能，STp的實現是在交換機這種純粹的二層設備上。不需要借用三層設備來實現。26、單選題A、

n-iB、

n-i+lC、

n-i-lD、

i正確答案：

A

參考解析：順序表中的刪除操作是通過將當前結點用后面結點的值覆蓋來實現的，因此刪除第i個元素主要是前移第i個元素后的所有的元素，即n-i個元素。27、單選題對包含n個關鍵碼的散列表進行檢索，平均檢索長度為()。A、

O(logn)B、

O(n)C、

O(nlogn)D、

不直接依賴于n正確答案：

D

參考解析：散列表的平均檢索長度僅與裝填因子a有關，而與關鍵字個數n無關。28、單選題將長度為n的單鏈表接在長度為m的單鏈表之后的算法時間復雜度為()。A、

O(n)B、

0(1)C、

O(m)D、

O(m+n)正確答案：

C

參考解析：要將長度為n的單鏈表接在長度為m的單鏈表之后，必須從單鏈表的頭結點沿鏈找到長度為m的單鏈表的最后一個結點，所以時間復雜度為O(m)。29、單選題在用鄰接表表示圖時，拓撲排序算法時間復雜度為()。A、

O(n)B、

O(n+e)C、

On×nD、

O(n×n×n)正確答案：

B

參考解析：拓撲排序中每個頂點都需要出入棧(當用鄰接表表示圖時的執行次數為n)，然后把入度減1(當用鄰接表表示圖時的執行次數為e)，所以拓撲排序的時間復雜度為O(n+e)。30、單選題Hash表是用于數據存儲的一種有效的數據結構，Hash表的查找復雜度依賴于Hash值算法的有效性，在最好的情況下，Hash表的查找復雜度為()。A、

O(nlogn)B、

O(logn)C、

O(n)D、

O(1)正確答案：

D

參考解析：0(1)，哈希表是通過計算hashcode來定位元素位置，所以只需一次即可。31、單選題非空的循環單鏈表head的尾結點P滿足的條件是()。A、

P.link=headB、

p.link=NILC、

p=NIL，D、

p=head正確答案：

A

參考解析：對于循環單鏈表來說尾結點的指針指向第一個元素。32、單選題在一個單鏈表中，若p所指的結點不是最后結點，則刪除p所指的結點的后繼結點的正確操作是()。A、

p=p-＞nextB、

p-＞next=p-＞nextC、

p-＞next=p-＞next-＞nextD、

p-＞next=p正確答案：

C

參考解析：本題考查的是單鏈表的刪除操作。在已知鏈表中元素插入或刪除確切位置的情況下，在單鏈表中插入或刪除一個結點時，僅需修改指針而無須移動元素。33、單選題非空的循環單鏈表FIRST的尾結點(由P所指向)滿足：()。A、

P—＞EXT=NULL；B、

P=NULL；C、

P—NEXT-FIRST；D、

P=FIRST；正確答案：

C

參考解析：循環單鏈表是單鏈表的一種特殊形式，其結構特點是鏈表中最后一個結點的指針域不再是結束標記(NULL)，而是指向鏈表中的第一個結點，從而使鏈表形成一個環。在本題中，FIRST指向循環單鏈表的首結點，P指向尾結點，可知P—＞NEXI=FIRST。34、單選題線索化的二叉樹中，某結點*P沒有孩子的充要條件是()。A、

p-＞lchild=NULLB、

p-＞ltag=l&&p-＞rtag=1C、

p-＞ltag=0D、

p-＞lchild=NULL&&p-＞ltag=1正確答案：

B

參考解析：考查線索二叉樹。35、單選題在單鏈表中，指針p指向結點A，若要刪除A之后的結點(存在)，則指針的操作方式為()。A、

p—＞next=p—＞next—＞nextB、

p=p—＞nextC、

p=p—＞next—＞nextD、

p-＞next-p正確答案：

A

參考解析：要在單鏈表中刪除p指向的結點的后繼結點，需要將后繼結點的后繼交給p所指結點的指鏟域。具體實現語句為p—＞next=p—＞next—＞next。36、單選題動態主機配置協議(DHCP)的作用是（請作答此空）；DHCP客戶機如果收不到服務器分配的IP地址，則()。A.為客戶機分配一個永久的IP地址A、

為客戶機分配一個暫時的IP地址B、

檢測客戶機地址是否沖突C、

建立IP地址與MAD、

地址的對應關系正確答案：

B

參考解析：動態主機配置協議（DynamicHostConfigurationProtocol，DHCP）則是在其基礎之上進行了改良的協議，是一種用于簡化主機IP配置管理的IP管理標準。通過采用DHCP協議，DHCP服務器為DHCP客戶端進行動態IP地址分配。同時DHCP客戶端在配置時不必指明DHCP服務器的IP地址就能獲得DHCP服務。當同一子網內有多臺DHCP服務器時，在默認情況下，客戶機采用最先到達的DHCP服務器分配的IP地址。Windows系統在處理DHCP工作失效的情況下，定義了一種自動IP機制APIPA，在dhcp失效時，自動使用169.254.X.X這個范圍內的一個隨機地址。37、單選題設指針變量p指向雙向鏈表中節點A，指針變量s指向被插入的節點X，則在節點A的后面插入節點X的操作序列為()A、

p-＞right=s；s-＞left=p；p-＞right-＞left=s；s-＞right=p-＞right；B、

p-＞right=s；p-＞right-＞left=s；s-＞left=p；s-＞right=p-＞right；C、

s-＞left=p；s-＞right=p-＞right；p-＞right=s；p-＞right-＞left=s；D、

s-＞left=p；s-＞right=p-＞right；p-＞right-＞left=s；p-＞right=s；正確答案：

D

參考解析：為了防止在插入節點時鏈表斷裂，在修改指針時，需要先使s的后繼指針指向p原來的后繼節點，然后修改p的后繼指針。38、單選題用P代表入棧，O代表出棧。棧的初始狀態和最終狀態都為空，則下列棧操作正確的是()。A、

POOPOOPPB、

POPOPOOPC、

PPPOOOPPD、

PPPOOPOO正確答案：

D

參考解析：AB兩項，均會出現下溢，即出棧時棧為空。C項，導致出現最終狀態不為空。39、單選題求最短路徑常用的算法有()。A、

Prim算法和Kruskal算法B、

深度優先遍歷算法和廣度優先遍歷算法C、

Dijkstra算法和Floyd算法D、

拓撲排序算法正確答案：

C

參考解析：A項是最小生成樹的算法，B項是圖的遍歷算法，D項中的回溯法是求解遞歸過程的一種重要方法。40、單選題一個循環隊列Q最多可存儲m個元素，已知其頭尾指針分別是front和rear，則判定該循環隊列為滿的條件是()。A、

Q.rear-Q.front==mB、

Q.real！==Q.frontC、

Q.front==(Q.real+1)%mD、

Q.front==Q.rear%m+1正確答案：

C

參考解析：少用一個元素空間和空隊區別開：每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿，這種情況下隊滿的條件是：(Q.rear+1)%MAXSIZE==Q.front。41、單選題設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為()。A、

q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free(q)；B、

q=p-＞next；p-＞data=q-＞data；free(q)；C、

q=p-＞next；p-＞next=q-＞next；free(q)；D、

q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free(q)；正確答案：

A

參考解析：應先使指針q指向結點A之后的結點，以防鏈表斷裂，然后刪除結點q，最后將刪除的結點q的存儲空間釋放。42、單選題在一個具有n個頂點的有向圖中，若所有頂點的出度數之和為S，則所有頂點的入度數之和為()。A、

SB、

S-1C、

S+1D、

n正確答案：

A

參考解析：圖的所有頂點的出度數之和等于所有頂點的入度數之和。故本題選A。43、單選題設單循環鏈表中結點的結構為(data，link)，且rear是指向非空的帶表頭結點的單循環鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執行下列哪一個操作()。A、

s=rear；rear=rear-＞link；deletes；B、

rear=rear-＞link；deleterear；C、

rear=rear-＞link-＞link；deleterear；D、

s=rear-＞link-＞link；rear-＞link-＞link=s-＞link；deletes；s為第一個結點硫正確答案：

D

參考解析：若要刪除結點需要改變尾指針的指向。44、單選題設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為()。A、

s-＞next=rear；rear=s；B、

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

rear-＞next=s；rear=s；D、

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

C

參考解析：向隊列插入元素，即入隊操作，應該在隊尾進行，所以需要修改尾指針，實現新結點的人隊。45、單選題在向下生成的堆棧中，如果入棧指令PUSHX的操作定義為：SP←(SP)+1，M(SP)←M(X)，則出棧指令POPX應定義為()。A、

SP←(SP)-1，M(X)←M(SP)B、

SP←(SP)+1，M(X)←M(SP)C、

M(X)←M(SP)，SP←(SP)-1D、

M(X)←M(SP)，SP←(SP)+1正確答案：

C

參考解析：入棧是先定位棧頂指針然后存儲數據，出棧是先出數據，然后再定位棧頂指針。46、單選題若一個棧以向量V[1.n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是()。A、

top=top+1；V[top]=xB、

V[top]=x；top=top+1C、

top=top-1；V[top]=xD、

V[top]=x；top=top-1正確答案：

C

參考解析：棧是運算受限的線性表，只允許在棧頂進行插入和刪除操作。本題中棧頂指針為n+1，該數組將棧頂放在了下標大的一端，所以在進行人棧操作時top指針應該進行減1操作。通常元素進棧的操作為：先移動棧頂指針后存入元素。47、單選題某PC的Internet協議屬性參數如下圖所示，默認網關的IP地址是()A、

8.8.8.8B、

202.117.115.3C、

192.168.2.254D、

202.117.115.18正確答案：

C

參考解析：本題實際上就是計算192.168.2.1這個地址使用255.255.255.0這個掩碼的時候，同一個網段的其他IP地址有哪些。因為網關必須與主機的IP地址在同一網段。48、單選題在一個具有n個單元的順序棧中，假定以地址低端(即下標為0的單元)作為棧底，以top作為棧頂指針，當出棧時，top的變化為()。A、

top=top-1；B、

top=top+1；C、

不變D、

top=0；正確答案：

A

參考解析：以top作為棧頂指針，當出棧時，top的變化為top=top-1。49、單選題設鏈式棧中節點的結構為(data，link)，且top是指向棧頂的指針。若想摘除鏈式棧的棧頂節點，并將被摘除節點的值保存到x中，則應執行下列()操作。A、

x=top-＞data；top=top-＞link；B、

top=top-＞link；x=top-＞data；C、

x=top；top=top-＞link；D、

x=top-＞data；正確答案：

A

參考解析：若想摘除鏈式棧的棧頂節點，并將被摘除節點的值保存到x中，則應執行x=top-＞data；top=top-＞link.50、單選題設結點x和y是二叉樹中任意的兩個結點，在該二叉樹的前序遍歷序列中x在y之前，而在其后序遍歷序列中x在y之后，則x和y的關系是()。A、

x是y的左兄弟B、

x是y的右兄弟C、

x是y的祖先D、

x是y的后裔正確答案：

C

參考解析：前序遍歷序列中x在y之前，有兩種情況，即x是y的祖先，或者x、y有某個共同祖先，并且x在其左子樹中，y在其右子樹中。而第二種情況在后序遍歷序列中，x必定在y之前，所以只能是x是y的祖先。51、單選題如果以鏈表作為棧的存儲結構，則退鏈棧操作時()A、

必須判斷鏈棧是否滿B、

判斷鏈棧元素的類型C、

必須判斷鏈棧是否空D、

對鏈棧不做任何判斷正確答案：

C

參考解析：在鏈表的退鏈棧操作時，如果棧已空.就沒有元素可供退棧，返回退棧失敗信息，所以必須判斷鏈棧是否空。52、單選題在具有n個結點的單鏈表中，實現()的操作，其算法的時間復雜度都是O(n)。A、

遍歷鏈表和求鏈表的第i個結點B、

在地址為P的結點之后插入一個結點C、

刪除開始結點D、

刪除地址為P的結點的后繼結點正確答案：

A

參考解析：A項，由于單鏈表是非隨機存取的存儲結構，遍歷鏈表和求鏈表的第i個結點都必須從頭指針出發尋找，其時間復雜度為0(n)；B項，由于已知待插入結點的前驅結點，可以直接實現插入，其時間復雜度為0(1)；CD兩項，可以直接實現刪除操作，其時間復雜度為O(1)。53、單選題鏈表不具有的特點是()。A、

不必事先估計存儲空間B、

可隨機訪問任一元素C、

插入刪除不需要移動元素D、

所需空間與線性表長度成正比正確答案：

B

參考解析：鏈表采用的是鏈式存儲結構，它克服了順序存儲結構的缺點：①它的結點空間可以動態申請和釋放；②它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。但是鏈式存儲結構也有不足之處：①每個結點中的指針域需額外占用存儲空間；②鏈式存儲結構是一種非隨機存儲結構。54、單選題在平衡二叉樹中()。A、

不存在度為1的節點B、

任意節點的左、右子樹節點數目相同C、

任意節點的左、右子樹高度相同D、

任意節點的左右子樹高度之差的絕對值不大于1正確答案：

D

參考解析：平衡二叉樹又稱AVL樹，它或者是一棵空樹，或具有下列性質的二叉樹：(1)左子樹和右子樹都是平衡二叉樹：(2)左子樹和右子樹的高度之差的絕對值不超過1。二叉樹上節點的平衡因子定義為該節點的右子樹的高度減去它的左子樹的高度。可見，平衡二叉樹上所有節點的平衡因子只可能是-1，0，1。只要二叉樹上有一個節點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。55、單選題循環鏈表的主要優點是()。A、

不再需要頭指針B、

已知某個結點的位置后，能很容易找到它的直接前驅結點C、

在進行刪除操作后，能保證鏈表不斷開D、

從表中任一結點出發都能遍歷整個鏈表正確答案：

D

參考解析：A項，頭指針不能省略，因為沒有頭指針就沒有辦法引用該鏈表了；B項，循環鏈表還是單鏈表，要找到直接前驅結點，必須至少循環遍歷整個鏈表一次才行；C項，無論鏈表是不是循環的，都能保證在刪除時鏈表不斷開；D項，因為循環鏈表首尾相接，形成一個環，從循環鏈表中任何一個結點開始都能遍歷整個鏈表。56、單選題對于具有n個頂點、6條邊的圖()。A、

采用鄰接矩陣表示圖時，查找所有頂點的鄰接頂點的時間復雜度為O(n2)B、

進行廣度優先遍歷運算所消耗的時間與采用哪一種存儲結構無關C、

采用鄰接表表示圖時，查找所有頂點的鄰接頂點的時間復雜度為O(n*e)D、

進行深度優先遍歷運算所消耗的時間與采用哪一種存儲結構無關正確答案：

A

參考解析：57、單選題與單鏈表相比，雙鏈表的優點之一是()。A、

插入、刪除操作更簡單B、

可以進行隨機訪問C、

可以省略表頭指針或表尾指針D、

訪問前后相鄰結點更靈活正確答案：

D

參考解析：對于插入、刪除操作單鏈表更簡單，因為需要改動的指針域少，而隨機訪問是順序表的特點。無論是單鏈表還是雙鏈表都要有表頭指針或表尾指針，在雙鏈表中可以訪問任一結點的前后相鄰結點，而單鏈表中只能訪問任意結點的后繼結點。58、單選題SNMP屬于OSI/RM的()協議。A、

管理層B、

應用層C、

傳輸層D、

網絡層正確答案：

B

參考解析：SNMP是簡單網絡管理協議，主要用于網絡管理進程與被管設備之間的通信，是一個應用層的協議。59、單選題()在其最好情況下的算法時間復雜度為O(n)。A、

插入排序B、

歸并排序C、

快速排序D、

堆排序正確答案：

A

參考解析：60、單選題最好情況下的算法時間復雜度為O(n)的是()。A、

插入排序B、

歸并排序C、

快速排序D、

堆排序正確答案：

A

參考解析：61、單選題如下陳述中正確的是()。A、

串是一種特殊的線性表B、

串的長度必須大于零C、

串中元素只能是字母D、

空串就是空白串正確答案：

A

參考解析：串的長度可以等于0，等于0時叫作空串。空串和空白串是不同的，例如：Strings=“”，是空串；Strings=NULL，是空白串。串中的元素只能是字符，但不僅僅是字母。62、單選題在AOE網絡中關鍵路徑敘述正確的是()。A、

從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間B、

從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最短時間C、

從開始頂點到完成頂點的具有最大長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間D、

從開始頂點到完成頂點的具有最小長度的路徑，關鍵路徑長度是完成整個工程所需的最長時間正確答案：

A

參考解析：關鍵路徑是指從有向圖的源點到匯點的最長路徑。某些關鍵活動提前完成，那么整個工程將會提前完成，但不是任何一個關鍵活動提前完成，就能保證整個工程將會提前完成。63、單選題以下各種存儲結構中，最適合用作鏈隊的鏈表是()。A、

帶隊首指針和隊尾指針的循環單鏈表B、

帶隊首指針和隊尾指針的非循環單鏈表C、

只帶隊首指針的非循環單鏈表D、

只帶隊首指針的循環單鏈表正確答案：

B

參考解析：因為隊列的入隊和出隊操作都在端點進行。即在隊首和隊尾進行。所以帶隊首指針和隊尾指針的非循環單鏈表最適合用作鏈隊的鏈表。64、單選題快速排序最不利于發揮其長處的情況是()。A、

待排序的數據中含有多個相同值B、

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

待排序的數據量太大D、

被排序的數據數量為奇數正確答案：

B

參考解析：各種排序方法對待排序的數據中是否含有多個相同值、被排序的數據數量為奇數或偶數都沒有影響。快速排序等改進的排序方法均適用于待排序數據量較大的情況。65、單選題若線性表最常用的運算是查找第i個元素及其前驅的值，則下列存儲方式最節省時間的是()。A、

單鏈表B、

雙鏈表C、

單循環鏈表D、

順序表正確答案：

D

參考解析：在順序表中查找第i個元素的前驅很方便。雙鏈表雖然能快速查找第i個元素的前驅，但不能實現隨機存取。單鏈表和單循環鏈表既不能實現隨機存取，查找第i個元素的前驅也不方便。66、單選題若某線性表中最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則下面最合適的存儲方式是()。A、

單鏈表B、

循環雙鏈表C、

單循環鏈表D、

帶有尾指針的單循環鏈表正確答案：

B

參考解析：在鏈表中的最后一個結點之后插入個結點要知道終端結點的地址，所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點要知道終端結點的前驅結點的地址，所以，帶有尾指針的單循環鏈表不合適，而循環雙鏈表滿足條件。67、單選題棧在()中應用。A.遞歸調用B.子程序調用A、

表達式求值B、

C、

D、

C正確答案：

D

參考解析：棧的特點是先入后出。A項，遞歸調用的特點是最外層的調用最后執行，最內層的調用最先執行，遞歸調用符合棧的特點，即先將外層的調用依次入棧，然后從最內層調用出棧執行；B項，子程序的調用與遞歸調用的特點類似；C項，表達式求值將數據入棧，遇到運算符時與棧頂的運算符比較優先級，級別高則數據出棧，進行運算。68、單選題設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為()。A、

第i列0元素的個數之和B、

第i列非0元素的個數之和C、

第i行0元素的個數之和D、

第i行非0元素的個數之和正確答案：

B

參考解析：考察圖的鄰接矩陣的特點，在有向圖的鄰接矩陣中，第i列非0元素的個數之和即為第i個節點的入度。69、單選題由Wi-Fi聯盟制定的無線局域網（WLAN）最新安全認證標準是()。A.WEPA、

WPB、

PSKC、

WPA2PSKD、

802.1x正確答案：

C

參考解析：從題干意思中的“最新”這個關鍵字就可以選擇答案。因為最早的無線安全協議是標準是WEP，存在諸多的問題，因此推出升級的WPApsk協議。WPA2PSK協議則是最新的WPA標準。因此選C。802.1x是一種身份認證協議。70、單選題在向圖的鄰接矩陣表示中，計算第i個頂點八度的方法是()。A、

第i行非零元素個數B、

第i列非零元素個數C、

第i行零元素個數D、

第i列零元素個數正確答案：

B

參考解析：先用一個二維數組Edge存儲表示鄰接矩陣，輸入文件中頂點的序號是從1開始，當輸入一條有向邊＜u，v＞時，將Edge[u-1][v-1]=1即可；第i+1個頂點的出度等于鄰接矩陣中第i行所有元素中元素值為1的個數，把第i行所有元素值累加起來，得到的結果也是該頂點的出度，同理，在計算第i+1個頂點的入度時，也只需要將第i列所有元素值累加起來即可。71、單選題A、

頂點序列B、

邊序列C、

權值總和D、

邊的條數正確答案：

A

參考解析：72、單選題棧和隊列的共同點是()。A、

都是先進先出B、

都是先進后出C、

只允許在端點處插入和刪除元素D、

沒有共同點正確答案：

C

參考解析：棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。73、單選題A、

堆排序B、

快速排序C、

希爾排序D、

冒泡排序正確答案：

A

參考解析：堆排序無論是最好情況還是最壞情況，時間復雜度都是相等的。74、單選題下列四種排序中()的空間復雜度最大。A、

堆排序B、

冒泡排序C、

插入排序D、

歸并排序正確答案：

D

參考解析：在題干中的四種排序中歸并排序的空間復雜度最大，為O(n)。75、單選題下列排序算法中，時間復雜度不受數據初始狀態影響恒為O(nlogn)的是()。A、

堆排序B、

冒泡排序C、

快速排序D、

直接插入排序正確答案：

A

參考解析：堆排序和快速排序是O(nlogn)的復雜度，但是快速排序在數據初始狀態有序的情況下蛻化為冒泡排序。76、單選題占用的額外空間的空間復雜度為0(1)的排序算法是()。A、

堆排序算法B、

歸并排序算法C、

快速排序算法D、

以上答案都不對正確答案：

A

參考解析：歸并排序中，由于每一趟都要一個TR數組來復制，因此需要與待排記錄等量的輔助空間O(n)；而快速排序中的遞歸所耗費的棧空間最好情況下也要O(logn)；堆排序僅在交換是需要一個記錄的輔助空間。77、單選題無向圖的鄰接矩陣是一個()。A、

對稱矩陣B、

無規律C、

上三角矩陣D、

下三角矩陣正確答案：

A

參考解析：兩個頂點鄰接是相互的，1和2鄰接，2和1也就鄰接了。78、單選題下面()不屬于特殊矩陣。A、

對角矩陣B、

三角矩陣C、

稀疏矩陣D、

對稱矩陣正確答案：

C

參考解析：稀疏矩陣不屬于特殊矩陣。79、單選題下面的說法中，不正確的是()。A、

廣義表是一種共享結構B、

廣義表是一種遞歸C、

廣義表是一種多層次的結構D、

廣義表是一種非線性結構正確答案：

D

參考解析：從各層元素各自具有的線性關系講，廣義表屬于線性結構。80、單選題靜態VLAN的配置方式是()。A.基于MAA、

地址配置的B、

由網絡管理員手工分配的C、

根據IP地址配置的D、

隨機配置的正確答案：

B

參考解析：Vlan的劃分主要有兩大類，分別是靜態和動態：靜態劃分Vlan主要是基于端口的形式，需要管理員手工配置每一個端口。動態劃分可以基于多種方式，典型的可以基于MAC地址，IP地址，上層協議等。81、單選題有關二叉樹下列說法正確的是()。A、

二叉樹的度為2B、

一棵二樹的度可以小于2C、

二叉樹中至少有一個結點的度為2D、

二叉樹中任何一個結點的度都為2正確答案：

B

參考解析：二叉樹的特點是每個結點至多有兩棵子樹，即不存在度大于2的結點。B項是說可以小于2，符合二叉樹的特點。82、單選題下面敘述正確的是()。A、

二叉樹是特殊的樹B、

二叉樹等價于度為2的樹C、

完全二叉樹必為滿二叉樹D、

二叉樹的左右子樹有次序之分正確答案：

D

參考解析：二叉樹是一類與樹不同的數據結構。兩者的區別在于：二叉樹可以是空集；二叉樹的任一結點都有兩棵子樹，并且這兩棵子樹之間有次序關系，也就是說，它們的位置不能交換。83、單選題下列敘述中，不符合m階B樹定義要求的是()。A、

根節點最多有m棵子樹B、

所有葉結點都在同一層上C、

各結點內關鍵字均升序或降序排列D、

葉結點之間通過指針鏈接正確答案：

D

參考解析：B樹的定義。84、單選題判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用()。A、

廣度優先遍歷算法B、

深度優先遍歷算法C、

求關鍵路徑的方法D、

求最短路徑的方法正確答案：

B

參考解析：當有向圖中無回路時，從某頂點出發進行深度優先遍歷時，出棧的順序(退出DFSTraverse算法)即為逆向的拓撲序列。85、單選題下面的說法中，不正確的是()。A、

廣義表是一種多層次的結構B、

廣義表是一種非線性結構C、

廣義表是一種共享結構D、

廣義表是一種遞歸正確答案：

B

參考解析：從各層元素各自具有的線性關系講，廣義表屬于線性結構。86、單選題下列不屬于內部排序的算法是()。A、

歸并排序B、

拓撲排序C、

樹型排序D、

折半插入排序正確答案：

B

參考解析：歸并排序、樹型排序、折半插入排序屬于內部排序算法，拓撲排序不屬于內部排序算法。87、單選題順序查找法適合于()結構的線性表。A、

哈希存儲B、

順序存儲或鏈式存儲C、

壓縮存儲D、

索引存儲正確答案：

B

參考解析：順序查找法適合于線性表(不論線性表采用順序存儲還是鏈式存儲)。而哈希存儲查找是根據哈希函數值直接查找。壓縮存儲是通過對應關系進行查找。索引存儲是通過索引表進行查找。88、單選題下面關于哈希查找的說法正確的是()。A、

哈希函數構造的越復雜越好，因為這樣隨機性好、沖突小B、

除留余數法是所有哈希函數中最好的C、

不存在特別好與壞的哈希函數，要視情況而定D、

若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單地將該元素刪去即可正確答案：

C

參考解析：AB兩項，哈希函數的構造要視具體情況而定，對于不同的序列，選擇不同的哈希函數，采用不同的解決沖突的方法，沒有絕對的好壞。D項，當刪除元素時，如果刪除元素的位置剛好發生了沖突，需要將因發生沖突而移動的元素重新計算哈希值進行存儲，要找到這些元素現在的位置就需要看解決沖突的方法。89、單選題以下敘述不正確的是()。A、

后序線索二叉樹是不完善的，要對它進行遍歷，不需使用棧B、

任何一棵二叉樹的后序線索樹進行后序遍歷時都必須使用棧C、

任何一棵二叉樹都可以不用棧實現先序線索樹的先序遍歷D、

任何一棵二叉樹都可以不用棧實現中序線索樹的中序遍歷正確答案：

B

參考解析：遍歷后序線索二叉樹不需要使用棧。90、單選題在最好和最壞情況下的時間復雜度均為0(