國家電網招聘考試計算機類專業知識（數據結構與算法）模擬試卷5一、單項選擇題(本題共30題，每題1.0分，共30分。)1、設無向圖G中的邊的集合E={(a,b)，(a,e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發進行深度優先遍歷可以得到的一種頂點序列為()。A、aedfcbB、aedfbcC、aebcfdD、acfebd標準答案：A知識點解析：根據題干描述，可畫出無向圖如下：B項中，aedf之后下一個遍歷頂點為c，而不是b；C項中，aeb之后應該回溯到頂點e，下一個遍歷頂點為d，而不是c；D項中，acf之后下一個遍歷頂點為d，而不是e。2、廣義表((a，(b，c))，d,e)的表頭是()。A、aB、(a)C、(b，c)D、(a，(b，c))標準答案：D知識點解析：廣義表中的第一個元素為表頭，其他元素組成的表為表尾，故本題中的廣義表的表頭為(a，(b，c))。3、設一個順序有序表A[1．．14]中有14個元素，則采用二分查找法查找元素A[4]的過程中，比較元素的順序為()。A、A[7],A[5],A[3],A[4]B、A[1],A[1A],A[7],A[4]C、A[7],A[3],A[5],A[4]D、A[1],A[2],A[3],A[4]標準答案：C知識點解析：二分查找法每次都與中間值進行比較。4、下列關于棧和隊列的敘述，錯誤的是()。A、棧可以為空B、棧的使用原則是先進后出C、可以用順序存儲的線性表來表示隊列D、根據循環隊列的頭指針與尾指針是否相等，可判斷循環隊列是否為空標準答案：D知識點解析：當棧中沒有元素時，稱為空棧。棧的使用原則是后進先出，也就是先進后出。可以用順序存儲的線性表來表示隊列，通常還會添加隊頭指針和隊尾指針。不能僅根據循環隊列的隊頭指針與隊尾指針是否相等判斷循環隊列是否為空，隊頭指針與隊尾指針相等，循環隊列可能為空，也可能為滿。5、設一棵三叉樹中有2個度為1的節點，2個度為2的節點，2個度為3的節點，則該三叉樹中有()個度為0的節點。A、8B、6C、7D、5標準答案：C知識點解析：設度為0的節點數為n，根據樹中節點總數與總度數的關系可列方程為2+2+2+n=2×1+2×2+2×3+n×0+1，解得n=7。6、下列排序方法中，比較次數與待排序記錄的初始狀態無關的是()。A、選擇排序和歸并排序B、插入排序和歸并排序C、插入排序和快速排序D、歸并排序和快速排序標準答案：A知識點解析：選擇排序在最好、最壞、平均情況下的時間復雜度均為O(n2)，歸并排序在最好、最壞、平均情況下的時間復雜度均為O(logn)。7、設有5000個元素，希望用最快的速度挑選出前10個最大的元素，采用()方法最好。A、希爾排序B、歸并排序C、快速排序D、堆排序標準答案：D知識點解析：堆排序不必將整個序列排序即可確定前若干個最大(或最小)元素。8、已知一個有序表為(12，18，24，35，47，50，62，83，90，115，134)，當折半查找值為90的元素時，經過()次比較后查找成功。A、2B、3C、4D、5標準答案：A知識點解析：根據二分查找法進行查找，第1次將90與表中中間元素50進行比較，由于90大于50，所以在線性表的后半部分查找；第2次與90比較的元素是后半部分的中間元素，即90，這時兩者相等，即查找成功。9、已知10個元素(54，28，16，34，73，62，95，60，26，43)，按照依次插入的方法生成一棵二叉排序樹，查找值為62的節點所需要的比較次數為()。A、2B、3C、4D、5標準答案：B知識點解析：根據題干描述，可畫出二叉排序樹如下：在該二叉排序樹中查找值為62的節點，從根節點開始，將62與54進行比較，由于62大于54，所以在根節點的右子樹中查找；將62與73進行比較，由于62小于73，所以在值為73的節點的左子樹中查找；將62與62進行比較，由于62等于62，查找成功。因此，查找值為62的節點所需要比較的次數為3。10、已知數據元素為(34，76，45，18，26，54，92，65)，按照依次插入節點的方法生成一棵二叉排序樹，則該樹的深度為()。A、6B、7C、4D、5標準答案：D知識點解析：根據題干描述，可畫出二叉排序樹如下：該二叉排序樹的最大層次為5，因此深度為5。11、在平衡二叉樹中，節點的平衡因子的絕對值不超過()。A、1B、2C、3D、4標準答案：A知識點解析：在平衡二叉樹中，任一節點的平衡因子的可能取值為－1、0和1，故其絕對值不超過1。12、二叉排序樹中，最小值節點的()。A、左、右指針均為空B、左、右指針均不為空C、左指針一定為空D、右指針一定為空標準答案：C知識點解析：在二叉排序樹中，最小值節點一定是中序遍歷序列中第一個被訪問的節點，即二叉排序樹的最左下方節點，該節點的左指針一定為空。13、散列技術中的沖突是指()。A、兩個元素具有相同的序號B、數據元素過多C、兩個元素的鍵值不同，而其他屬性相同D、不同鍵值的元素對應相同的存儲地址標準答案：D知識點解析：暫無解析14、設散列表表長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。15、判定一個有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用()。A、廣度優先遍歷算法B、深度優先遍歷算法C、求關鍵路徑的方法D、求最短路徑的方法標準答案：B知識點解析：當有向圖中無回路時，從某頂點出發進行深度優先遍歷，出棧的順序即為逆向的拓撲序列。16、下列關于工程計劃的AOE網絡的敘述，不正確的是()。A、某些關鍵活動若提前完成，那么整個工程將會提前完成B、關鍵活動不按期完成就會影響整個工程的完成時間C、任何一個關鍵活動提前完成，那么整個工程將會提前完成D、所有的關鍵活動都提前完成，那么整個工程將會提前完成標準答案：C知識點解析：AOE網絡中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前完成整個工程，則必須同時提前完成在幾條關鍵路徑上的關鍵活動。17、某無向圖的鄰接矩陣A=，可以看出，該圖共有()個頂點。A、3B、6C、9D、12標準答案：A知識點解析：鄰接矩陣是表示頂點之間鄰接關系的矩陣。設G=(V,E)是具有n個頂點的圖，頂點序號依次為1，2，…，n，則G的鄰接矩陣是n階方陣，所以該圖有3個頂點。18、無向圖的鄰接矩陣是一個()。A、對稱矩陣B、無規律矩陣C、上三角矩陣D、下三角矩陣標準答案：A知識點解析：在無向圖的鄰接矩陣中，兩個頂點鄰接是相互的，即l和2鄰接，則2和1也鄰接，因此無向圖的鄰接矩陣是一個對稱矩陣。19、下列敘述正確的是()。A、一個圖的鄰接矩陣表示是不唯一的，鄰接表表示也是不唯一的B、一個圖的鄰接矩陣表示是唯一的，鄰接表表示也是唯一的C、一個圖的鄰接矩陣表示是唯一的，鄰接表表示不是唯一的D、一個圖的鄰接矩陣表示是不唯一的，鄰接表表示是唯一的標準答案：C知識點解析：暫無解析20、關鍵路徑是AOE網絡中()。A、最長的回路B、最短的回路C、從源點到終點的最長路徑D、從源點到終點的最短路徑標準答案：C知識點解析：在AOE網絡中，從源點到終點具有最大路徑長度的路徑稱為關鍵路徑。關鍵路徑的工期是指關鍵路徑上的各個活動所持續的時間之和，它決定了整個項目的最短工期。21、靜態查找與動態查找的根本區別在于()。A、所包含的數據元素的類型不一樣B、存儲實現方式不一樣C、邏輯結構不一樣D、施加在其上的操作不一樣標準答案：D知識點解析：靜態查找不涉及插入和刪除操作，而動態查找涉及插入和刪除操作。22、假定一棵度為3的樹中的節點個數為50，則其最小高度應為()。A、5B、6C、3D、4標準答案：A知識點解析：節點數相同而高度最小的三叉樹是滿三叉樹或完全三叉樹(深度為h的三叉樹，若前h一1層是滿的，只有第h層從右邊起，連續缺若干個節點的三叉樹稱為完全三叉樹)。設根節點的層次為1，則第1層有1個節點，第2層最多有3個節點，第3層最多有9個節點，第4層最多有27個節點，第5層最多有81個節點，1+3+9+27=40＜50，1+3+9+27+81=121＞50，因此最小高度為5。23、在線索二叉樹中，一個節點是葉節點的充要條件是()。A、左、右線索標志均為0B、左、右線索標志均為1C、左線索標志為0，右線索標志為1D、左線索標志為1，右線索標志為0標準答案：B知識點解析：一個節點是葉節點的充要條件是沒有左孩子節點，并且沒有右孩子節點。24、含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過()。A、n－1B、nC、1D、n／2標準答案：A知識點解析：若簡單路徑的長度超過n一1，則路徑中必存在重復的頂點。25、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是()。A、nB、(n－1)2C、n－1D、n2標準答案：D知識點解析：暫無解析26、設無向圖G=(V，E)和G′=(V′，E′)，如果G′是G的生成樹，則下列說法錯誤的是()。A、G′為G的極小連通子圖，且V=V′B、G′為G的一個無環子圖C、G′為G的子圖D、G′為G的連通分量標準答案：D知識點解析：由于G＇為G的生成樹，因此G＇為G的極小連通子圖，包含G中所有的頂點，即V=V＇；如果G中有n個頂點，則G＇由n一1條邊構成，因此不存在回路，G＇為G的無環子圖。連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，因此連通分量中可能存在回路。27、G是一個非連通無向圖，共有28條邊，則該圖至少有()個頂點。A、8B、9C、6D、7標準答案：B知識點解析：在含有n個頂點的無向圖中，邊數e≤n(n－1)／2，將e=28代入，得n≥8，現已知無向圖非連通，則該圖至少有9個頂點。28、線索二叉樹中某節點R沒有左孩子節點的充要條件是()。A、R．1tag=1B、R．rchild=NULLC、R．1child=NULLD、R．1tag=0標準答案：A知識點解析：線索二叉樹中某節點是否有左孩子節點，不能通過左指針域lchild是否為空來判斷，而要判斷左標志1tag是否為1。29、討論樹、森林和二叉樹的關系，目的是()。A、借助二叉樹上的運算方法去實現對樹的一些運算B、將樹