國家電網招聘-計算機(電網)真題庫_111、單選題使用圖像掃描儀以300DPI的分辨率掃描一幅3英寸×3英寸的圖片，可以得到()內存像素的數字圖像。A、

100×100B、

300×30（江南博哥）0C、

600×600D、

900×900正確答案：

D

參考解析：一幅畫是由很多像素點組成的，每一行有300*3個像素點，一共有300*3這么多行，因此總的像素點行數*每行像素點=900*9002、單選題為了攻擊遠程主機，通常利用()技術檢測遠程主機狀態。A、

病毒查殺B、

端口掃描C、

QQ聊天D、

身份認證正確答案：

B

參考解析：進行攻擊之前，需要了解被攻擊主機的相關信息，通常采用端口掃描的方式收集數據。3、單選題如果一棵完全二叉樹共有26個結點，則必定有()個結點的度為1。A、

0B、

1C、

3D、

13正確答案：

B

參考解析：26個結點，可知該二叉樹有5層。由于前4層組成一棵滿二叉樹，共15個結點，則共有11個葉子結點，可知只有1個結點的度為1。4、單選題一個有n個結點的圖，最多有()個連通分量。A、

0B、

1C、

n-1D、

n正確答案：

D

參考解析：無向圖中的極大連通子圖稱為圖的連通分量。圖的連通分量的個數小于或等于圖的結點數。當圖的各個結點彼此都沒有邊相連時，連通分量數最大為n。5、單選題在有向圖中，所有頂點的度數之和是所有邊數的()倍A、

0.5B、

1C、

2D、

4正確答案：

C

參考解析：在有向圖中，所有頂點的度數之和是所有邊數的2倍，因為一條邊的兩個端點具有兩個“度”。6、單選題已知串S=′aaab′，其next數組值為()。A、

0123B、

0213C、

0231D、

1211正確答案：

A

參考解析：7、單選題串′ababaaababaa′的next數組值為()。A、

01234567899B、

012121111212C、

011234223456D、

0123012322345正確答案：

C

參考解析：8、單選題下列的敘述不正確的個數是()。(1)9階B-樹，除根以外的任一結點的關鍵字個數不少于4(2)理想情況下，在散列表中查找一個元素的時間復雜度為0(1)(3)在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰(4)在索引順序表的查找中，對索引表既可以采用順序查找方法，也可采用=分查找方法A、

1B、

2C、

3D、

4正確答案：

A

參考解析：如果發生多次沖突，則同義詞在表中就不會相鄰，因此(3)是錯誤的，其它正確。9、單選題設有向無環圖G中的有向邊集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，則下列屬于該有向圖G的一種拓撲排序序列的是()。A、

1，2，3，4B、

2，3，4，1C、

1，2，4，3D、

1，4，2，3正確答案：

A

參考解析：10、單選題已知一個線性表為(38，25，74，63，52，48)，假定采用H(K)=Kmod7計算散列地址進行散列存儲，若利用線性探測的開放定址法處理沖突，則在該散列表上進行查找的平均查找長度為()；若利用鏈地址法處理沖突，則在該散列上進行查找的平均查找長度為()。A、

1.5，1B、

1.7，3/2C、

2，4/3D、

2.3，7/6正確答案：

C

參考解析：若用開放定址法處理沖突，發生0次沖突的關鍵字有3個，1次沖突的1個，2次沖突的1個，3次沖突的1個，因而在該散列表上進行查找的平均查找長度為ASL-(3*1+1*2+1*3+1*4)/6=2；若用鏈地址法處理沖突，同一鏈表上有1個元素的線性鏈表有2個，有2個元素的線性鏈表有2個，因此ASL=(4*1+2*2)/6=4/3。11、單選題在一個無向圖中，所有頂點的度數之和等于所有邊數()倍。A、

1/2B、

2C、

1D、

4正確答案：

B

參考解析：無向圖中每條邊都有兩個頂點，所以所有頂點的度數之和等于所有邊數的2倍。12、單選題采用分塊查找時.若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊時，每塊應分()個結點最佳。A、

10B、

25C、

6D、

625正確答案：

B

參考解析：13、單選題假設用戶U有2000臺主機，則必須給他分配()個C類網絡，如果分配給用戶U的網絡號為，則指定給用戶U的地址掩碼為（請作答此空）。A、

B、

C、

D、

正確答案：

C

參考解析：為了給用戶U分配2000臺主機，需要將C類網絡劃分為2000個網絡單位。C類網絡的最大網絡數為2^16-2=65534，因此需要將其劃分為65534/2000=32.75≈33個網絡單位。考慮到實際的網絡劃分需要以及子網內部的可用主機數，需要分配給用戶U一個連續的33位地址空間。所以分配給用戶U的網絡號為：/33，并且指定給用戶U的地址掩碼為：C類網絡的默認掩碼，即A選項：。14、單選題設某哈夫曼樹中有199個結點，則該哈夫曼樹中有()個葉子結點。A、

101B、

100C、

99D、

102正確答案：

B

參考解析：在哈夫曼樹中的結點只有兩種，一種是度為零的結點，另一種是度為1的結點。15、單選題下面關于m階B-樹說法正確的是()。①每個結點至少有兩棵非空子樹；②樹中每個結點至多有m-l個關鍵字；③所有葉子在同一層上；④當插入一個數據項引起B樹結點分裂后，樹長高一層。A、

①②③B、

②③C、

②③④D、

③正確答案：

B

參考解析：16、單選題設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有()個結點。A、

13B、

12C、

26D、

25正確答案：

D

參考解析：哈夫曼樹的特點：具有n個葉子結點的哈夫曼樹共有2×n-1個結點。17、單選題對任意7個關鍵字進行排序，至少要進行()次關鍵字之間的兩兩比較。A、

13B、

14C、

15D、

16正確答案：

C

參考解析：18、單選題設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主進行存儲，a1，1為第一元素，其存儲地址為1，每個元素占一個地址空間，則a8·5的地址是()。A、

13B、

33C、

18D、

40正確答案：

B

參考解析：數組下標從1開始，只存儲其下三角形元素，在A，5的前面有7行，第1行有1個元素，第2行有2個元素，…，第7行有7個元素，這7行共有(1+7)×7/2=28個元素，在第8行中，a8·5的前面有4個元素，所以a8·5前有28+4=32個元素，其地址為33。19、單選題設線性表(順序存儲方式)的每個元素占8個存儲單元。第一個單元的存儲地址為100，則第6個元素占用的最后一個存儲單元的地址為()。A、

139B、

140C、

147D、

148正確答案：

C

參考解析：6個元素，每個元素8個存儲單元.一共需要48個存儲單元。第一個單元的存儲地址為100，所以第6個元素占用的最后一個存儲單元的地址為100+48-1=147(-1是因為地址100是第一個存儲位置)。20、單選題A、

14B、

19C、

21D、

26正確答案：

C

參考解析：本題考查最小生成樹算法。21、單選題設有序表中有1000個元素，則用二分查找元素X最多需要比較()次。A、

15B、

10C、

17D、

25正確答案：

B

參考解析：二分查找每趟都使用序列的中間值與關鍵字比較，直至查找成功或失敗。22、單選題將一個a[100][100]的三對角矩陣以行主序存入一維數組B[298]中，元素a[65][64]在B數組中的位置等于()。A、

198B、

197C、

196D、

195正確答案：

D

參考解析：將三對角矩陣a[i][j]存入b[k]中，矩陣壓縮地址計算公式為k=2i十j。所以a[65][64]對應的k=2×65+64=194，194是一維數組b的下標，而數組下標是從0開始計數的.所以元素的位置應該是195。23、單選題以下有關算法的說法錯誤的是()。Ⅰ.算法原地工作的含義是指不需要任何額外的輔助空間；Ⅱ，在相同的規模n下，復雜度O(n)的算法在時間上總是優于復雜度O(2n)的算法；Ⅲ.所謂最壞時間復雜度是指最壞情況下估算算法執行時間的一個上界；Ⅳ，同一個算法，實現語言的級別越高，執行效率就越低。A、

ⅠB、

Ⅰ和ⅡC、

Ⅰ和ⅣD、

Ⅲ正確答案：

C

參考解析：算法原地工作的含義是指算法的空間復雜度為O(1)，同一個算法實現語言的級別越高執行效率并不一定越低。24、單選題動態主機配置協議(DHCP)的作用是()；DHCP客戶機如果收不到服務器分配的IP地址，則（請作答此空）。A、

分配一個網段的地址B、

繼續尋找可以提供服務的DHCP服務器C、

獲得一個自動專用IP地址APIPAD、

獲得一個私網地址正確答案：

C

參考解析：動態主機配置協議（DynamicHostConfigurationProtocol，DHCP）則是在其基礎之上進行了改良的協議，是一種用于簡化主機IP配置管理的IP管理標準。通過采用DHCP協議，DHCP服務器為DHCP客戶端進行動態IP地址分配。同時DHCP客戶端在配置時不必指明DHCP服務器的IP地址就能獲得DHCP服務。當同一子網內有多臺DHCP服務器時，在默認情況下，客戶機采用最先到達的DHCP服務器分配的IP地址。Windows系統在處理DHCP工作失效的情況下，定義了一種自動IP機制APIPA，在dhcp失效時，自動使用169.254.X.X這個范圍內的一個隨機地址。25、單選題以下關于二叉排序樹的說法正確的是()。Ⅰ.在二叉排序樹中，每個結點的關鍵字都比左孩子關鍵字大，比右孩子關鍵字小Ⅱ.每個結點的關鍵字都比左孩子關鍵字大，比右孩子關鍵字小，這樣的二叉樹都是二叉排序樹Ⅲ，在二叉排序樹中，新插入的關鍵字總是處于最底層Ⅳ.在二叉排序樹中，新結點總是作為葉子結點來插入的Ⅴ.二叉排序樹的查找效率和二叉排序樹的高度有關A、

Ⅰ、Ⅱ、Ⅳ、ⅤB、

Ⅱ、Ⅲ、ⅣC、

Ⅰ、Ⅲ、ⅤD、

Ⅰ、Ⅳ、Ⅴ正確答案：

D

參考解析：在二叉排序樹中，新插入的關鍵字總是作為葉子結點來插入的，但是葉子結點不一定總是處于最底層。對于二叉排序樹，左子樹上所有記錄的關鍵字均小于根記錄的關鍵字；右子樹上所有記錄的關鍵字均大于根記錄的關鍵字。而不是僅僅與左、右孩子的關鍵字進行比較。26、單選題已知10個數據元素為(54，28，16，34，73，62，95，60，23，43)，按照依次插入結點的方法生成一棵二叉排序樹后，查找值為62的結點所需比較的次數為()。A、

2B、

3C、

4D、

5正確答案：

B

參考解析：將這10個元素按照依次插入結點的方法生成一棵二叉排序樹后，62位于這棵二叉排序樹的第三層，查找值為62的結點所需要的次數恰好是從二叉排序樹的根到被查結點的樹的深度。27、單選題若對27個元素只進行三趟多路歸并排序，則選取的歸并路數為()。A、

2B、

3C、

4D、

5正確答案：

B

參考解析：28、單選題在由4棵樹組成的森林中，第一、第二、第三和第四棵樹中的結點個數分別為30，10，20，5，當把森林轉換成二叉樹后，對應的二叉樹中根結點的左子樹中結點個數為()。A、

20B、

29C、

30D、

35正確答案：

B

參考解析：當把森林轉換成二叉樹后，第二、第三和第四棵樹均在第一棵樹的根結點的右子樹上。29、單選題一棵完全二叉樹上有1001個結點.其中葉子結點的個數是()。A、

250B、

500C、

505D、

501正確答案：

D

參考解析：30、單選題設高度為H的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為()。A、

2HB、

1H-1C、

2H+1D、

H+1正確答案：

C

參考解析：由題可知該二叉樹上只有度為0和度為2的結點即每個結點要么是葉子結點要么有兩個子結點因此該二叉樹的葉子結點數目為2的h次方又因為每個非葉子結點都有兩個子結點所以非葉子結點數目為葉子結點數目減1即2的h次方減1因此該二叉樹中所包含的結點數為2的h次方加上2的h次方減1即2的h+1次方減1故選項C為正確答案而選項AD都小于2的h+1次方減1不符合題意選項B為2的h次方減1不符合題意31、單選題二叉樹的第k層的結點數最多為()。A、

2K-1B、

2K+1C、

2KD、

2正確答案：

A

參考解析：二叉樹第k層最多有2k-1個結點。32、單選題下列敘述正確的個數是()。(1)m=2的平衡m路查找樹是AVL樹(2)m=3的平衡m路查找樹是2-3樹(3)m=2的平衡m路查找樹的葉結點不一定在同一層(4)m階B-樹的葉結點必須在同一層(5)m階B-樹是平衡m路查找樹(6)平衡m路查找樹不一定是B-樹A、

3B、

4C、

5D、

6正確答案：

D

參考解析：33、單選題按照二叉樹的定義，具有3個結點的二叉樹有()種。A、

3B、

4C、

5D、

6正確答案：

C

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

3B、

6C、

9D、

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

A

參考解析：鄰接矩陣是表示頂點之間相鄰關系的矩陣。設G=(V，E)是具有n個頂點的圖，頂點序號依次為1，2，……，n，則G的鄰接矩陣是n階方陣，所以該圖有3個頂點。35、單選題下列服務中，傳輸層使用UDP的是()。A、

HTTP瀏覽頁面B、

VoIP網絡電話C、

SMTP發送郵件D、

FTP文件傳輸正確答案：

B

參考解析：從幾個選項來看，http使用的tcp協議，端口80.SMTP也是tcp協議，端口25.FTP文件傳輸協議，也是使用tcp21號端口。因此只能選B。36、單選題設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行()趟的分配和回收才能使得初始關鍵字序列變成有序序列。A、

3B、

8C、

5D、

6正確答案：

A

參考解析：因為待排序列中最大的數為三位數，所以需要進行3次。37、單選題設循環隊列的存儲空間為Q(1：30)，初始狀態front=rear=30，先經過一系列入隊和退隊運算后，front=10，rear=10，則循環隊列中的元素個數為()。A、

30B、

0C、

29D、

0或30正確答案：

D

參考解析：當frontrear時，循環隊列中的元素個數為N-front+rear(N為循環隊列容量)。當front=rear時，循環隊列中的元素個數可能為空，也可能為滿。38、單選題高度為7的AVL樹最少有()個結點。A、

31B、

32C、

33D、

34正確答案：

C

參考解析：39、單選題有一個長度為12的有序表，按二分查找法對該表進行查找，在表內各元素等概率情況下，查找成功所需的平均比較次數為()。A、

37/12B、

35/12C、

39/12D、

43/12正確答案：

A

參考解析：用二分法查找有序表，相當于在一個完全二叉樹中查找元素，查找成功的比較次數相當于到查找結點的路徑長度加1。12個結點的完全二叉樹前三層是滿二叉樹，第四層有5個結點。整棵樹的查找次數總和為：1+22+4×3+5×4=37。查找某個元素的概率是37/12。40、單選題若一組記錄的關鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為()。A、

38，40，46，56，79，84B、

40，38，46，79，56，84C、

40，38，46，56，79，84D、

40，38，46，84，56，79正確答案：

C

參考解析：由于選擇第一個記錄為基準，第一次排序即對整個序列進行一趟快速排序。使得位于基準左側的關鍵碼均小于基準，位于基準右側的關鍵碼均大于基準。41、單選題設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經過()次比較。A、

4B、

2C、

3D、

1正確答案：

C

參考解析：二分查找法的每一次查找都要與中間值進行比較，所以24第一次與35比較，因為24小于35，所以接下來在35的左半部分中進行查找，左半部分的中間值為18，4大于18，接下來去18的右半部分查找，24與24進行比較，此時，查找成功，共比較了3次。42、單選題下列敘述正確的個數是()。(1)向二叉排序樹中插入一個結點，所需比較的次數可能大于此二叉排序樹的高度。(2)對B-樹中任一非葉子結點中的某關鍵字K，比K小的最大關鍵字和比K大的最小關鍵字一定都在葉子結點中。(3)所謂平衡二叉樹是指左、右子樹的高度差的絕對值不大于1的二叉樹。(4)刪除二叉排序樹中的一個結點，再重新插入，一定能得到原來的二又排序樹。A、

4B、

3C、

2D、

1正確答案：

D

參考解析：只有第3項是正確的。43、單選題在一棵度為3的樹中，度為3的結點個數為2，度為2的結點個數為1，則度為0的結點個數為()。A、

4B、

5C、

6D、

7正確答案：

C

參考解析：根據題干中的描述可以畫出樹，度為零的結點共6個。44、單選題將有關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度為()。A、

4B、

5C、

6D、

7正確答案：

C

參考解析：45、單選題設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為()。A、

4B、

6C、

5D、

7正確答案：

A

參考解析：46、單選題在以太網標準規范中，以太網地址長度是（請作答此空）字節；數據速率達到千兆的標準是()。A、

2B、

4C、

6D、

8正確答案：

C

參考解析：以太網地址長度為48位，即6個字節（4個字節代表一個64位二進制數）。在以太網標準規范中，數據速率達到千兆的標準被稱為1000BASE-T，其中的1000表示傳輸速率為1Gbps，而后面的字母表示使用雙絞線作為傳輸介質。因此，選項C是正確的答案。47、單選題具有5個葉子結點的二叉樹中，度為2的結點的個數為()。A、

4B、

6C、

5D、

不確定正確答案：

A

參考解析：二叉樹的性質1：非空二叉樹上葉結點數等于雙分支結點數加1。因此度為2的結點的個數為5-1=4。48、單選題設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數不超過1.5，則散列表項應能夠至少容納()個表項。A、

400B、

526C、

624D、

676正確答案：

A

參考解析：采用線性探查法解決沖突查找成功時的平均查找長度S≈0.5×(1+1/(1-a))，其中a是哈希表的裝填因子，定義為a=表中裝入的記錄數，哈希表的長度。若要求查詢成功的平均查找次數不超過1.5，即S≤1.5，而且哈希表中裝入的記錄數為200，故哈希表長度不小于400。49、單選題設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是()。A、

42，40，45，80，85，88B、

40，42，45，55，80，85C、

42，40，45，55，80，85D、

42，40，45，85，55，80正確答案：

C

參考解析：快速排序是通過一趟排序將待排序的記錄分割為獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，然后再分別對這兩部分記錄繼續進行排序，以達到整個序列有序。本題選擇第一個數為基準進行劃分，分別從右邊查找小于45的數和從左邊找大于或等于45的數，不斷進行交換，第一趟結束后，即得到第一次劃分結果。50、單選題設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有()個空指針域。A、

4m-1B、

2mC、

2m-1D、

4m正確答案：

B

參考解析：因哈夫曼樹的結點的度，只有0和2兩種情況，所以，空指針域為2m個。51、單選題設樹T的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1，則T中的葉子數是()。A、

5B、

6C、

7D、

8正確答案：

D

參考解析：52、單選題若用一個大小為6的一維數組來實現循環隊列，且當前front和rear的值分別為3，0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為()。A、

5，1B、

4，2C、

2，4D、

1，5正確答案：

B

參考解析：刪除front=(front+1)mod6，加入：rear=(rear+1)mod6。53、單選題設一個棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是()。A、

51234B、

45123C、

43125D、

32154正確答案：

D

參考解析：棧的進出原則是先進后出原則，要不就是先進先出原則。A選項中5最先出，說明1234都在棧里，這樣說明1是在棧低，則先不出來。BD的原因一樣，所以答案選擇D。54、單選題由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為()。A、

53B、

73C、

48D、

24正確答案：

B

參考解析：根據赫夫曼樹的構造方法可構造出赫夫曼樹，經計算可得帶權路徑長度為73。55、單選題有六個元素6，5，4，3，2，1的順序進棧.下列選項中，()不是合法的出棧序列。A、

543612B、

453126C、

346521D、

234156正確答案：

C

參考解析：根據棧的后進先出的特點，對于C選項中前兩個元素得出棧順序可以看出，4在5和6前先出棧，有根據入站順序，4在5和6后入棧，因此4出棧時，5和6必定在棧內，且5在6之上，所以出棧時5要比6先出棧。56、單選題設有一個10階的下三角矩陣A(包括對角線)，按照從上到下、從左到右的順序存儲到連續的55個存儲單元中，每個數組元素占1個字節的存儲空間，則A[5][4]地址與A[0][0]的地址之差為()。A、

55B、

19C、

28D、

10正確答案：

B

參考解析：最后一行的第四列有4個元素，第五行前共有5行，而每個元素占一個字節，并且存儲單元共有55個。57、單選題下列隧道協議中，工作在網絡層的是()。A、

L2TPB、

SSLC、

PPTPD、

IPSec正確答案：

D

參考解析：IPsec是基于網絡層的安全協議。L2tp,pptp是基于數據鏈路層的安全協議。SSL傳輸層的安全協議。58、單選題A、

6B、

4C、

3D、

2正確答案：

C

參考解析：59、單選題設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4，es，e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是()。A、

6B、

4C、

3D、

2正確答案：

C

參考解析：60、單選題設某棵三叉樹中有40個結點，則該三叉樹的最小高度為()A、

6B、

4C、

5D、

3正確答案：

B

參考解析：樹高度最小時即為每一層都是滿的，只有最下層不滿的情況是樹的高度最小的情況。61、單選題已知數據元素為(34，76，45，18，26，54，92，65)，按照依次插入結點的方法生成一棵二叉排序樹，則該樹的深度為()。A、

6B、

7C、

4D、

5正確答案：

D

參考解析：根據二叉排序樹插入結點算法，將上述8個數據元素按照依次插入結點的方法構造出一棵二叉排序樹后，該樹的最大層次為5，故該樹的深度為5。62、單選題求解Hanoi問題時，若初始有5個圓盤，則移動圓盤的次數是()。A、

7B、

15C、

31D、

5正確答案：

C

參考解析：63、單選題對下列4個序列用快速排序方法進行排序，以序列的第1個元素為基準進行劃分。在第1趟劃分過程中，元素移動次數最多的是()。A、

70，75，82，90，23，16，10，68B、

70，75，68，23，10，16，90，82C、

82，75，70，16，10，90，68，23D、

23，10，16，70，82，75，68，90正確答案：

A

參考解析：快速排序第一趟劃分的方法是：將第1個元素放在最終排好序列的最終位置上，則在這個位置右邊小于該元素值的元素都移到其左邊，則在這個位置左邊小于該元素值的元素都移到其右邊。64、單選題設散列表表長m=14，散列函數H(k)=kmod11。表中已有15，38，61，84四個元素，如果用線性探測法處理沖突，則元素49的存儲地址是()。A、

8B、

3C、

5D、

9正確答案：

A

參考解析：元素15，38，61，84分別存儲在4，5，6，7單元，而元素49的散列地址為5，發生沖突，向后探測3個單元，其存儲地址為8。65、單選題設哈希表長為14，哈希函數是H(key)=key%ll，表中已有數據的關鍵字為15，28，61，84共四個，現要將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是()。A、

8B、

3C、

5D、

9正確答案：

D

參考解析：66、單選題設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有()個度數為0的結點。A、

8B、

6C、

7D、

5正確答案：

C

參考解析：度為O的結點個數為1+2×1+2×2=7。67、單選題設一組初始記錄關鍵字的長度為8，則最多經過()趟插入排序可以得到有序序列。A、

8B、

7C、

9D、

6正確答案：

B

參考解析：插入排序的每一趟在待排元素中取出第一個元素，移至有序序列的適當的位置，所以共八個關鍵字的序列，最多經過7趟插入排序就可以得到一個有序序列。68、單選題下列病毒中，屬于腳本病毒的是()。A、

Trojan.QQ3344B、

SasserC、

VBS.HappytimeD、

Macro.Melissa正確答案：

C

參考解析：69、單選題G是一個非連通無向圖，共有28條邊，則該圖至少有()個頂點。A、

8B、

9C、

6D、

7正確答案：

B

參考解析：n個頂點的無向圖中，邊數e≤n(n-l)/2，將e=28代入，有n≥8，現已知無向圖非連通，則n=9。70、單選題若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A[3]的比較序列的下標依次為()。A、

9，5，3B、

9，5，2，3C、

1，2，3D、

9，4，2，3正確答案：

D

參考解析：二分查找的基本思想是將n個元素分成大致相等的兩部分，取中間位置的節點值與關鍵字做比較，如果相等，則查找成功；如果關鍵字的值小于中間節點，則只要在數組的左半部分繼續搜索，重復與中間值進行比較，直至查找成功或失敗；如果關鍵字大于中間值，則只要在數組的右半部搜索即可。71、單選題設有廣義表D(a，b，D)，其長度為3，深度為()A、

∞B、

3C、

2D、

5正確答案：

A

參考解析：長度為3，但是因第三個元素是一個廣義表，所以深度為無窮。72、單選題一個隊列的入隊順序是a，b，c，d，則出隊順序是()。A.a，b，C，dB.b，C，d，aA、

d，B、

b，aC、

D、

d，a，b正確答案：

A

參考解析：隊列的特點是先進先出，因此出隊的序列于入隊的序列完全相同，這點與棧不同。73、單選題<p>無向圖G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(e，d)}，對該圖進行深度優先遍歷，得到的頂點序列正確的是()。</p>A、

a，b，e，c，d，fB、

a，c，f，e，b，dC、

a，e，b，c，f，dD、

a，e，d，f，c，b正確答案：

D

參考解析：易老師認為，假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，并將其標記為已訪問過：然后依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。74、單選題已知有向圖G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，對該圖進行拓撲排序，下面序列中()不是拓撲排序A、

a，d，c，b，eB、

d，a，b，c，eC、

a，b，d，c，eD、

a，b，c，d，e正確答案：

D

參考解析：75、單選題設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是()。A.A，D，C，R，F，Q，M，S，Y，P，H，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.H，A、

Q，P，B、

M，S，R，C、

D、

X，Y正確答案：

D

參考解析：每一趟冒泡排序從第一個元素開始，相鄰的兩個元素進行比較，若是降序則進行交換，一趟排序完成后，值最大的元素被移至序列的末尾。76、單選題一棵有n個結點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數組A[1.n]中，則二叉樹中第i個結點(i從1開始用上述方法編號)的右孩子在數組A中的位置是()。A、

A[2i](2i＜=n)B、

A[2i+1](2i+1＜=n)C、

A[i-2]D、

條件不充分，無法確定正確答案：

D

參考解析：題目并未明確所給二叉樹的形狀，因此不能根據第i個結點在數組A中的存儲位置確定其右孩子在數組A中的位置。77、單選題設一個順序有序表A[1：14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。A、

A[7]，A[5]，A[3]，A[4]B、

A[1]，A[14]，A[7]，A[4]C、

A[7]，A[3]，A[5]，A[4]D、

A[1]，A[2]，A[3]，A[4]正確答案：

C

參考解析：二分查找法的每次比較都與中間值進行比較，第一次與位置7的元素比較，依次類推。78、單選題用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組A[1]～A[n]中，結點A[i]若有左子樹，則左子樹的根結點是()。A、

A[i/2]B、

A[2i]C、

A[2i-1]D、

A[2i+1]正確答案：

B

參考解析：據二叉樹的性質5，對完全二叉樹從上到下、從左至右給結點編號，若編號為2i的結點存在，則i的左子樹一定是A[2i]。79、單選題家庭網絡中，下面IP地址()能被DHCP服務器分配給終端設備。A、

1B、

C、

1D、

28正確答案：

C

參考解析：家庭網絡地址，必須是私有地址，同時也不能是自動IP地址，因此只有C可以。80、單選題中綴表達式A-(B+C/D)*E的后綴形式是()。A、

AB-C+D/E*B、

ABC+D/-E*C、

ABCD/E*+-D、

ABCD/+E*-正確答案：

D

參考解析：將中綴表達式表示成二叉樹的形狀，則這棵二叉樹的后序遍歷序列即為表達式的后綴形式。81、單選題表達式a*(b+c)-d的后綴表達式是()。A、

abcd*+-B、

abc+*d-C、

abc*+d-D、

-+*abcd正確答案：

B

參考解析：根據優先級應該先算(b+c)，將其改為bc+，并將其看成新的操作數，此時中間結果為a*(bc+)-d；下一步應該算a*(bc+)，照上法改為abc+*，中間結果變為abc+*-d；最后算一，最終結果為abc+*d——a82、單選題A、

abcfdegB、

abcgfdeC、

abcdefgD、

abcfgde正確答案：

A

參考解析：本題考查深度優先算法。83、單選題假設以S和X分別表示進棧和出棧操作，則對輸入序列a，B，c，d，E進行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為()。A.B，c，E，d，aB.B，E，c，a，dC.E，c，A、

d，aB、

c，C、

D、

a，d正確答案：

A

參考解析：a，B進棧(SS)，B出棧(X)，輸出“B”，c進棧(S)，c出棧(X)，輸出“c”，d，E進棧(SS)，E，d，a出棧(XXX)，輸出“E，d，a”，所以結果為B，c，E，d，a。84、單選題簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個結點，其鄰接矩陣為A[1.n，1.n]，且壓縮存儲在B[1.n(n-1)/2]。若按行壓縮存儲對稱矩陣的上三角元素，則當n等于10時，邊(V6，V3)的信息存儲在()。A、

B[18]B、

B[19]C、

B[20]D、

B[21]正確答案：

C

參考解析：邊(V6，V3)與邊(V3，V6)是同一條邊。原第i行第j列元素在矩陣B(上三角形式)中的下標為：(n-1)+(n-2)+…+(n-(i-1))+(j-i)。將數值代入，(10-1)+(10-2)+(6-3)=20。邊(V6，V3)的信息存儲在B[20]中。85、單選題下面關于B和B+樹的敘述中，不正確的是()。A、

B樹和B+樹都是平衡的多叉樹B、

B樹和B+樹都可用于文件的索引結構C、

B樹和B+樹都能有效地支持順序檢索D、

B樹和B+樹都能有效地支持隨機檢索正確答案：

C

參考解析：B-樹又叫多路平衡查找樹，是一種組織和維護外存文件系統非常有效的數據結構。在索引文件組織中，常使用B-樹的變形——B+樹，屬于平衡的多叉樹。兩者都支持隨機檢索，但不能有效地支持順序檢索。86、單選題有種關系模式R=＜U，F＞，U={C，T，H，X，S}，F={C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}則表示模式R的碼是()。A.CB.(H，S)A、

B、

Y)C、

D、

T)正確答案：

B

參考解析：由題可得如下推導：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)為關系模式的碼。87、單選題有A，B，C，D，E5個元素按次序入棧，在各種可能的出棧次序中，以元素C，D最先出棧的序列中，下列正確的一組是()。A、

CDBAECDABEB、

CDEBACDBEAC、

CDEABCDABED、

CEBAECDAEB正確答案：

B

參考解析：只有A、B、C先入棧，才能CD作為第一、二個元素出棧。C出棧，D入棧，D出棧；接著就剩下A、B在棧中，E未入棧，共3個元素，此三者序列為BAE，BEA，EBA。88、單選題在二叉樹的順序存儲中，每個結點的存儲位置與其父結點、左右子樹結點的位置都存在一個簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有n個結點，采用三叉鏈表存儲時，每個結點的數據域需要d個字節，每個指針域占用4個字節，若采用順序存儲，則最后一個結點下標為k(起始下標為1)，采用順序存儲更節省空間的情況是()。A、

d＜12n/(k-n)B、

d＞12n/(k-n)C、

d＜12n/(k+n)D、

d＞12n/(k+n)正確答案：

A

參考解析：89、單選題已知輸入序列為abcd，經過輸出受限的雙端隊列后，能得到的輸出序列是()。A、

dacbB、

cadbC、

dbcaD、

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

B

參考解析：輸出受限的雙端隊列是指刪除限制在一端進行，而插入允許在兩端進行的隊列。A項，輸入序列為abcd，輸出序列為dacb，由輸出受限性質可知以da開頭的結果只有dabc。B項，輸入序列為abcd，輸出序列為cadb，其輸入輸出順序為：先在輸出端輸入a，然后在非輸出端輸入b，這時隊列中的序列為ba，再在輸出端輸入c，這時隊列中的序列為bac；輸出c，再輸出a；再在輸出端輸入d，這時隊列中的序列為bd；輸出d，再輸出b。最后得到輸出序列為cadb。C項，輸入序列為abcd，輸出序列為dbca，由輸出受限性質可知以db開頭的結果只有dbac。90、單選題RIP協議通過路由器之間的()計算通信代價。A、

鏈路數據速率B、

物理距離C、

跳步計數D、

分組隊列長度正確答案：

C

參考解析：RIP協議是一種典型的距離矢量協議，RIP協議的度量值是以跳數來計算的，即每經過一跳，度量值就會加1，RIP的最大跳數為15，也就是說RIP協議所能傳遞路由信息的最大跳數就是15跳，超過15跳就表示不可達。91、單選題已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA，則該二叉樹的后序序列為()。A、

DBACEFB、

DABECFC、

BCDEAFD、

ABDCEF正確答案：

D

參考解析：按照遍歷左子樹要在遍歷右子樹之前進行的原則，根據訪問根節點位置的不同，可得到二叉樹的前序，中序和后序3種遍歷方法。層序遍歷是從根節點(第1層)出發，首先訪問第1層的樹根節點，然后從左到右依次訪問第2層上的節點，其次是第3層上的節點，依此類推，自上而下，自左向右逐層訪問各層上的節點。對于二叉樹來說，第n層節點最多為2m1。由層序序列可得:F是樹根節點，D.E是第2層節點:結合中序序列有DBA構成F的左子樹，CE構成F的右子樹，進-一步有C是E的左節點、B無右節點:這樣A是第4層節點，據DBA序列有B是D的右節點.A是B的右節點。易知后序序列為ABDCEF.92、單選題某二叉樹中序序列為A，B，C，D，