一、判斷題

1、所謂“循環隊列”是指用單向循環鏈表或者循環數組表示的隊列。(2分)

解：錯誤。將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列（Circular Queue）


2、將$N$個數據按照從小到大順序組織存放在一個單向鏈表中。如果采用二分查找，那么查找的平均時間復雜度是$O(logN)$。(3分)

解： 錯誤。數組二分查找的平均復雜度是O（logN）沒有錯，一看到這個就跳坑了= =然后知道陷阱來了！按順序存放在【單項鏈表】中。二分查找是不可以用鏈表存儲的。為什么呢，請看下面解釋：

<span style="font-size:14px;"> 這是由鏈表的特性決定的。鏈表是很典型的順序存取結構，數據在鏈表中的位置只能通過從頭到尾的順序檢索得到，即使是有序的，要操作其中的某個數據也必須從頭開始。這和數組有本質的不同。數組中的元素是通過下標來確定的，只要你知道了下標，就可以直接存儲整個元素，比如a[5],是直接的。鏈表沒有這個，所以，折半查找只能在數組上進行。</span>

二、選擇題

給定$N\times N$的二維數組A，則在不改變數組的前提下，查找最大元素的時間復雜度是：(4分)

?O(N2)O(N^2)O(N?2??)

?O(NlogN)O(NlogN)

?O(N)O(N)

?O(N2logN)O(N^2 logN)

解：選擇第四個。

給定程序時間復雜度的遞推公式：$T(1)=1$，$T(N)=2T(N/2)+N$。則程序時間復雜度是：(4分)

O(logN)O(logN)

$O(N)$

?O(NlogN)O(NlogN)

O(N2)O(N^2)O(N?2??)

解：選擇第三個。
????舉個栗子：
????? T(8)->T(4)+T(4)+8->T(2)+T(2)+T(2)+T(2) +8+8->T(1)*8+8+8+8 = 8*4
?????? 遞歸深度為logn每層執行n次

總結

以上是生活随笔為你收集整理的数据结构练习题及答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。