1.設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度（）
A. O(log2n)
B. O(1)
C. O(n2)
D. O(n)
單鏈表插入不需要移動元素，時間復雜度為O（1），但是要保持有序狀態，順序存取需要按位置訪問元素時間復雜度為O（n）,故選D，
2.一個堆疊的初始狀態為空，首先將元素5，4，3，2，1 依次入堆疊，然后退堆疊一次，再將元素A,B,C,D依次入堆疊，之后將所有元素全部退堆疊，則所有元素退堆疊（包括中間退堆疊的元素）的順序為？
A. 1DCAB2345
B. 1DCBA2345
C. 54321ABCD
D. DCBA12345
堆疊的基本特點就是：先進后出，將5，4，3，2，1依次入堆疊后，再退堆疊一次，取出的元素就為1，然后A，B，C，D入堆疊，依次出堆疊，順序為DCBA2345，故選B，
3.設堆疊S和佇列Q的初始狀態為空，元素e1，e2，e3，e4，e5，e6依次壓入堆疊S,一個元素出堆疊后即進入佇列Q，若出佇列的順序為e2,e4,e3,e6,e5,e1則堆疊S的容量要求最小值為
A. 2
B. 3
C. 4
D. 5
出隊先出e2表示e1，e2進堆疊后出e2(這時堆疊的容量最大為2)，接著出e4，e3表示e3，e4進堆疊后出e4，e3(這時堆疊的容量最大為3)，再出e6，e5表示e5，e6進堆疊后出e6，e5(這時堆疊的容量最大為3)，最后出e1，所以答案應該是 3，故選B，
4.給定下列程式，那么執行printf("%d\n", foo(20, 13));的輸出結果是（）
int foo(int x, int y){
if (x <= 0 || y <= 0)
return 1;
return 3 * foo( x-6, y/2 );
}
A. 3
B. 9
C. 27
D. 81
36 < 20 < 46,遞回 4層，
log13 < log16 = 4;
所以結果為 3^4 = 81，故選D，
5.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A. n
B. n+1
C. n-1
D. n/2
完全二叉樹是指除最后一層外，每一層上的結點數均達到最大值，在最后一層上只缺少右邊的若干結點，根據完全二叉樹性質，如果共 2n 個結點，從根結點開始按層序用自然數 1 ， 2 ，…， 2n 給結點編號，則編號為 n 的結點左子結點編號為 2n ，因此葉子結點編號為 n+1,n+2, … ,2n ，故葉子結點個數為 n ，故答案為 A ，
6.有權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（），
A. 24
B. 71
C. 48
D. 53
通過哈夫曼樹的構造規則構建出如下的一棵樹，在第三層的節點有2 5 在第二層節點的有 6 8 11 ，
23+53+62+82+11*2=71
故答案為B，
7.下述二叉樹中,哪一種滿足性質:從任一結點出發到根的路徑上所經過的結點序列按其關鍵字有序（）
A. 二叉排序樹
B. 哈夫曼樹
C. AVL樹
D. 堆
A，二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
所以可以看出二叉排序樹只有中序遍歷結果是一個有序序列，
B，哈夫曼樹：當用 n 個結點（都做葉子結點且都有各自的權值）試圖構建一棵樹時，如果構建的這棵樹的帶權路徑長度最小，稱這棵樹為“最優二叉樹”，有時也叫“赫夫曼樹”或者“哈夫曼樹”，根據赫夫曼樹的結構特點我們可以知道，在赫夫曼樹中所有的關鍵字只出現在葉結點上，其非葉結點上并沒有關鍵字值，
C，avl樹（平衡二叉樹又稱AVL樹，）：本質上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹），所以也不能滿足需求，
D，堆：是一種特殊的完全二叉樹，例如：堆總是滿足下列性質：
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，
最終得到的正是一個從任一結點出發到根的路徑上所經過的結點序列按其關鍵字有序的樹狀結構，
所以本題答案為D，
8.為提高散列（Hash）表的查找效率，可以采取的正確措施是（ ），
Ⅰ．增大裝填（載）因子
Ⅱ．設計沖突（碰撞）少的散列函式
Ⅲ．處理沖突（碰撞）時避免產生聚集（堆積）現象
A. 僅Ⅰ
B. 僅Ⅱ
C. 僅Ⅰ、 Ⅱ
D. 僅Ⅱ、 Ⅲ
影響散串列性能：
- 散串列是否均勻；
- 處理沖突的方法：鏈地址法處理沖突不會產生任何堆積，因而具有更加平均查找性能；
- 散串列的裝填因子：填入表中記錄越多，裝填因子越大，產生沖突的可能性越大
故本題答案為D，
9.將整數陣列（7-6-3-5-4-1-2）按照堆排序的方式原地進行升序排列，請問在第一輪排序結束之后，陣列的順序是（），
A. 2-6-3-5-4-1-7
B. 6-2-3-5-4-1-7
C. 6-5-3-2-4-1-7
D. 1-5-3-2-4-6-7
E. 5-4-3-2-1-6-7
F. 5-1-3-2-4-6-7
原陣列已經是一個大頂堆，可直接開始排序，
（大頂堆：每個節點的值都不小于自己兩個左右子節的完全二叉樹）
每輪輸出堆頂元素后，以堆中最后一個元素代替之（由于此題要求原地排序，即不產生額外的空間，堆頂元素與最后一個元素交換），再將新的頂點元素不斷與其子節點中大于該元素的較大者交換，直到該元素大于其左右兩個子節點，或成為葉子節點，此時將剩余元素調整成一個新的大頂推，
由此得出，第一輪結束后的順序是：6,5,3,2,4,1,7，故選C，
10.要連通具有 n 個頂點的有向圖，最少需要（）條邊，
A. n+l
B. n-l
C. 2n
D. n
有向圖有三種連通概念，強連通，單相連通和弱連通，這個題目的答案對應的是強連通，而一邊連通有向圖定義為單相連通
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/294457.html
標籤：java