全國2010年10月高等教育自學考試

　　數據結構導論試題

　　課程代碼：02142

　　一、單項選擇題(本大題共15小題，每小題2分，共30分)

　　在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

　　1.下列描述中正確的是( )

　　A.數據元素是數據的最小單位

　　B.數據結構是具有結構的數據對象

　　C.數據結構是指相互之間存在一種或多種特定關系的數據元素的集合

　　D.算法和程序原則上沒有區別，在討論數據結構時兩者是通用的

　　2.歸并排序的時間復雜度是( )

　　A.O(n2)

　　B.O(nlog2n)

　　C.O(n)

　　D.O(log2n)

　　3.二分查找的時間復雜度是( )

　　A.O(n2)

　　B.O(nlog2n)

　　C.O(n)

　　D.O(log2n)

　　4.順序存儲的表中有90000個元素，已按關鍵字值升序排列，假設對每個元素進行查找的概率相同，且每個元素的關鍵字值皆不相同，用順序查找法查找時，需平均比較的次數為( )

　　A.25000

　　B.30000

　　C.45000

　　D.90000

　　5.散列文件是一種( )

　　A.順序文件

　　B.索引文件

　　C.鏈接文件

　　D.計算尋址文件

　　6.兩個矩陣A：m×n，B：n×p相乘，其時間復雜度為( )

　　A.O(n)

　　B.O(mnp)

　　C.O(n2)

　　D.O(mp)

　　7.常用于函數調用的數據結構是( )

　　A.棧

　　B.隊列

　　C.鏈表

　　D.數組

　　8.二維數組A[n][m]以列優先順序存儲，數組A中每個元素占用1個字節，A[1][1]為首元素，其地址為0，則元素A[i][j]的地址為( )

　　A.(i-1)×m+(j-1)

　　B.(j-1)×n+(i-1)

　　C.(j-1)×n+i

　　D.j×n+i

　　9.圖的廣度優先搜索使用的數據結構是( )

　　A.隊列

　　B.樹

　　C.棧

　　D.集合

　　10.序列(21,19,37,5,2)經冒泡排序法由小到大排序，在第一次執行交換后所得結果為( )

　　A.(19，21，37，5，2)

　　B.(21，19，5，37，2)

　　C.(21，19，37，2，5)

　　D.(2，21，19，37，5)