• 2元彩票网图表走势 > 自測卷答案
  • 自測卷答案

    免費下載 下載此文檔 文檔格式:DOC   更新時間:2002-11-02   下載次數:0   點擊次數:7
    文檔基本屬性
    文檔語言:Simplified Chinese
    文檔格式:doc
    文檔作者:LiuYu
    關鍵詞:
    主題:
    備注:
    點擊這里顯示更多文檔屬性
    第8章 查找 自測卷答案 姓名 班級 A
    題號





    總分
    題分
    10
    27
    16
    24
    23
    100
    得分
    一,填空題(每空1分,共10分)
    1. 在數據的存放無規律而言的線性表中進行檢索的最佳方法是 順序查找(線性查找) .
    2. 線性有序表(a1,a2,a3,…,a256)是從小到大排列的,對一個給定的值k,用二分法檢索表中與k相等的元素,在查找不成功的情況下,最多需要檢索 8 次.設有100個結點,用二分法查找時,最大比較次數是 7 .
    3. 假設在有序線性表a[20]上進行折半查找,則比較一次查找成功的結點數為1;比較兩次查找成功的結點數為 2 ;比較四次查找成功的結點數為 8 ;平均查找長度為 3.7 .
    解:顯然,平均查找長度=O(log2n)<5次(25).但具體是多少次,則不應當按照公式
    來計算(即(21×log221)/20=4.6次并不正確!).因為這是在假設n=2m-1的情況下推導出來的公式.應當用窮舉法羅列:
    全部元素的查找次數為=(1+2×2+4×3+8×4+5×5)=74; ASL=74/20=3.7 !!!
    4.【計研題2000】折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它將依次與表中元素 28,6,12,20 比較大小.
    5. 在各種查找方法中,平均查找長度與結點個數n無關的查找方法是 散列查找 .
    6. 散列法存儲的基本思想是由 關鍵字的值 決定數據的存儲地址.
    7. 有一個表長為m的散列表,初始狀態為空,現將n(nhigh) return 0; //查找不到時返回0
    mid=(low+high)/2;
    if(ST.elem[mid].key= =key) return mid;
    else if(ST.elem[mid].key>key)
    www.ivqnnj.twarch_Bin_Recursive(ST, key, low, mid-1);
    else www.ivqnnj.twarch_Bin_Recursive(ST, key, mid+1, high);
    }
    }//Search_Bin_Recursive
    2. 【嚴題集9.31④】試寫一個判別給定二叉樹是否為二叉排序樹的算法,設此二叉樹以二叉鏈表作存儲結構.且樹中結點的關鍵字均不同.
    解:注意仔細研究二叉排序樹的定義.易犯的典型錯誤是按下述思路進行判別:"若一棵非空的二叉樹其左,右子樹均為二叉排序樹,且左子樹的根的值小于根結點的值,又根結點的值不大于右子樹的根的值,則是二叉排序樹"
    (劉注:即不能只判斷左右孩子的情況,還要判斷左右孩子與雙親甚至根結點的比值也要遵循(左小右大)原則).
    若要采用遞歸算法,建議您采用如下的函數首部:
    bool BisortTree(BiTree T, BiTree&PRE),其中PRE為指向當前訪問結點的前驅的指針.
    (或者直接存儲前驅的數值,隨時與當前根結點比較)
    一個漂亮的算法設計如下:

    2元彩票网图表走势 www.ivqnnj.tw 下一頁

  • 下載地址 (推薦使用迅雷下載地址,速度快,支持斷點續傳)
  • 免費下載 DOC格式下載
  • 贊助商鏈接