對資料元素的有序順序表進行折半查詢,當查詢失敗時,至少需要比較 次關鍵字急急急

2022-02-20 11:50:41 字數 1026 閱讀 8876

1樓:三兩菊花

至少4次,至多5次。

把22個資料畫成二叉樹,然後和mid比較一次,就知道是相等,大於還是小於要查詢的key。

因為它不是滿二叉樹,所以葉子結點的層次不一樣,有的在4層有的在5層(層次遍歷)。所以至少要4次就知道key不在資料中。

比如:找比資料最大值還大的數,比較4次發現都比每次的結點數大,這樣就是比4次。

比如:找比資料最小值還小的數,比較5次發現都比每次的結點數小,這樣就是比5次。

2樓:匿名使用者

至少需要4次,

第一次與第11個位置上的數進行比較 mid = (0 + 21)/2 = 10,不相等進入[0,9]區域進行查詢

第二次與第5個位置上的數進行比較 mid = (0 + 9)/2 = 4,不相等進入[0,3]區域進行查詢

第三次與第2個位置上的數進行比較 mid = (0 + 3)/2 = 1,不相等進入[0,0]區域進行查詢

第四次與第1個位置上的數進行比較 查詢不到說明不存在該關鍵字

用折半查詢在有序表(1,3,5,7,9,10,12,14,16,18,19) 中查詢關鍵字3,需要比較的次數是? 10

3樓:匿名使用者

一共11個關鍵字,設第一個數1在陣列r中的位置是r[0],剩餘的數依次存放,數19在r[10]。

第一趟,取中間位置為(0+10)/2=5,數為10,比3大,此時看左半區間。

第二趟,取中間位置(0+4)/2=2,數為5,比3大,看左半區間。

第三趟,取中間位置(0+1)/2=0,數為1,比3小,看右半區間。

第四趟,查詢成功。

所以需要比較4趟。

4樓:匿名使用者

構造折半查詢的判定樹就可以了

第1層1個結點

第2層2個結點

第3層4個結點

第4層8個結點,共計1+2 + 4 + 8 = 15剩餘30-15 = 15在第5層,也就是說比較次數為5次,因此答案正確

如何對資料透視表中的標籤進行排序

第一種方法 在佈局圖裡面對行標籤或列標籤裡面的欄位進行拖動即回可,需要排在前面的答 拖到橫標籤或者列標籤的最上面位置,以此類推。第二種方法 在資料透視表欄位列表行列標籤中,滑鼠左鍵單擊,選擇上移或者下移執行 在佈局圖裡面對行標籤或列標籤裡面的欄位進行拖動即可,需要排在前面的拖到橫標籤或者列標籤的最上...

線性表 a1,a2an 中的元素遞增有序,採用帶表頭結

node p l next p指向來第自一個 bai資料 du節zhi點 int i 0 while p dao null return 1 有一個線性表 a1,a2,an 其中n 2,採用帶頭結點的單連結串列儲存,頭指標為l,每個結點存放線性表中 1 線性表中的元素無序 pnode p l whi...

Excel2019中如何對資料透視表中的資料進行排序

與在正常資料中排序一樣操作 活動單元格在資料透視表中定位到某列,點排序按鈕,就可以實現排序 把資料選中,再執行資料 排序。你可以試試。excel資料透視表怎麼排序 首先,建立一個簡單的 bai資料 單擊菜du單欄 插入 資料透視表zhi 資料透視表。建立資料透視dao表,選擇分析資料區域和放置資料透...