數據結構選擇復習測試卷

第頁數據結構選擇復習測試卷1.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（）比較大小，查找結果是失敗。A、20，70，30，50B、30，88，70，50C、20，50D、30，88，50【正確答案】：A2.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址()。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)或不連續(xù)都可以【正確答案】：D3.在一個含有n個頂點的有向圖中，最多會有()條邊。A、n-1B、nC、n(n-1)D、n+1【正確答案】：C4.一棵完全二叉樹上有5000個結點，其中葉子結點的個數是（）。A、2500B、2501C、2499D、2450【正確答案】：A5.二叉樹的第k層的結點數最多為()個。A、2k-1B、2K+1C、2K-1D、2^(K-1)【正確答案】：D6.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是（）。A、39B、52C、111D、119【正確答案】：C7.設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A、1和1B、1和3C、1和2D、2和3【正確答案】：C8.以下數據結構中，（）是非線性數據結構。A、樹B、字符串C、隊列D、棧【正確答案】：A9.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為()A、O（1）B、O（n）C、O（1og2n）D、O（n2）【正確答案】：C10.用鏈接方式存儲的隊列，在進行插入運算時（）。A、僅修改頭指針B、頭、尾指針都要修改C、僅修改尾指針D、頭、尾指針可能都要修改【正確答案】：D11.若用數組A[0?5]來實現循環(huán)隊列，且當前rear和front的值分別為1和5，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）。A、3和4B、3和0C、5和0D、5和1【正確答案】：B12.算法的時間復雜度取決于()。A、問題規(guī)模B、待處理數據的初態(tài)C、編譯程序的質量D、A和B【正確答案】：D13.鏈接存儲的存儲結構所占存儲空間（）。A、分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B、只有一部分，存放結點值C、只有一部分，存儲表示結點間關系的指針D、分兩部分，一部分存放結點值，另一部分存放結點所占單元數【正確答案】：A14.對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數，則散列地址為1的元素有（）個。A、1B、2C、3D、4【正確答案】：D15.設哈希表長m=14,哈希函數h(key)=keymod11,表中已有4個元素，addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址為空，如果用二次探測法處理沖突，則關鍵字49的結點的地址是()。A、8B、3C、5D、9【正確答案】：D16.線性表L在（）情況下適用于使用鏈式結構實現。A、需經常修改L中的結點值B、需不斷對L進行刪除插入C、L中含有大量的結點D、L中結點結構復雜【正確答案】：B17.以下說法正確的是（）。A、串是一種特殊的線性表B、串的長度必須大于零C、串中的元素只能是字母D、空串就是空白串【正確答案】：A18.設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。()A、688B、678C、692D．696【正確答案】：C19.若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（）A、79,46,56,38,40,84B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,38【正確答案】：B20.與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）。A、存儲結構B、存儲實現C、邏輯結構D、運算實現【正確答案】：C21.若一組記錄的排序碼為（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【正確答案】：C22.G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A、7B、8C、9D、10【正確答案】：C23.設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A、5B、6C、7D、8【正確答案】：A24.數據結構在計算機內存中的表示是指（）。A、數據的存儲結構B、數據結構C、數據的邏輯結構D、數據元素之間的關系【正確答案】：A25.從邏輯上可以把數據結構分為（）兩大類。A、動態(tài)結構、靜態(tài)結構B、順序結構、鏈式結構C、線性結構、非線性結構D、初等結構、構造型結構【正確答案】：C26.下列關鍵字序列中，（）是堆。A、16,72,31,23,94,53B、94,23,31,72,16,53C、16,53,23,94,31,72D、16,23,53,31,94,72【正確答案】：D27.若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A［3］的比較序列的下標依次為()。A、1，2，3B、9，5，2，3C、9，5，3D、9，4，2，3【正確答案】：D28.設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL【正確答案】：A29.設二維數組A[1..m，1..n]（即m行n列）按行存儲在數組B[1..m*n]中，則二維數組元素A[i,j]在一維