1鏈表不具備的特點是_______。
A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素
C）不必事先估計存儲空間 D）所需空間與其長度成正比
2已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。
A）ACBED B）DEABCC）DECAB D）EDBAC
3設有一個已按各元素的值排好序的線性表（長度大于2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。
A）s=b B）s>b C）s<b D）s≥b
4在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。
A）左、右兩個子表都已各自排好序B）左邊子表中的元素都不大于右邊子表中的元素
C） 左邊子表的長度小于右邊子表的長度D）左、右兩個子表中元素的平均值相等
農信社考試網整理
1.解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A。
2.解析：后序遍歷的順序是"左子樹－右子樹－根結點"；中序遍歷順序是"左子樹－根結點－右子樹"；前序遍歷順序是"根結點－左子樹－右子樹"。根據各種遍歷算法，不難得出前序遍歷序列是EDBAC。所以答案為D。
3.解析：對于順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為〔log2n〕+1。當n≥2時，顯然n+1>〔log2n〕+1。答案：B
4.解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小于或等于基準元素的排序碼，右子表的排序碼則大于基準元素的排序碼，然后分別對兩個子表繼續進行排序，直至整個表有序。答案：B
|
