阿摩線上測驗
登入
首頁
>
研究所、轉學考(插大)-資料結構
>
102年 - 102 淡江大學 轉學考 資料結構#53109
>
題組內容
5. 二元搜尋樹(Binary Search Tree): (12%)
(b) 7?〈(a),寫出此二元樹的中序巡行(inorder traversal)與後序巡行(postorder traversal)結 果,假設巡行的目的爲印出節點對應的鍵値。(4%)
其他申論題
(a)若堆疊的特質可用"Last In First Out"來描述,如何以類似的說法來描述Queue特質? (2%)
#193495
(b)有--堆疊S的內容爲(a^cAe),其屮e在頂端(top),又有一f宁列Q的內容爲(w,x,y,z), 其中z在末尾。先在S進行三次pop,再在Q中進行二次dequeue,最後依序將由S 中pop出來的元素加入Q中。請問此時S與Q的內容分別爲何? (4%)
#193496
(c)寫出以下算術運算式F的前置式(prefix expression)與後置式(postfix expression)。(6%) F= a-(b+c/d-e)*f+g/h*j
#193497
(a)依序將以下鍵値加入一空的二搜尋元樹(鍵値的大小依照字典順序),畫出最後的樹狀結 構 ° (4%) NYY, KITTY, GET, JAN, HEX, SAM, POT, SOP, MET, VIS
#193498
(c)若僅知一棵二元搜尋樹的中序與後序尋行結果,能否唯一決定此二元樹的結構?說明 原因,否則不給分。(4%)
#193500
(a)某陣列的初始內容爲88,17,45, 98, 32,使用Bubble Sort進行由小到大排序,共需幾次 的元素互換(swap)?需寫出排序過程,否則不給分。(4%)
#193501
(b)在MergeSort中,若需合倂二段已經排好的整數序列(7, 19, 33, 35)與(12,15, 23, 31),共 需進行多少次的元素比較?需寫出過程,否則不給分。(4%)
#193502
(c)假設使用Quicksort排序一整數序列,若挑選最靠近平均値的元素做爲樞紐(pivot),可 倉g有利於分割時的平衡性,但此舉是否會對排序的時間複雜度造成影響?說明原因, 否則不給分。(4%)
#193503
(a)依序將以下整數鍵値加入一個大小(TableSize)爲11的Hash table,使用h(key)=key mod TableSize 做爲 Hash function,並以 quadratic probing 做爲碰撞排解(collision resolution) 方法,畫出Hash table最後的內容,並寫出鍵値加入時的計算過程。(5%) 77, 23, 35,20, 78, 54, 98
#193504
(b)同(a) ’但改用double hashing來進行碰撞排解’公式如下,其中hl(key)爲primary hash function: (5%) hi(key) = hl(key)+i*h2(key), i:第 i 次碰撞 hl(key)=key mod TableSize, h2(key)=7-(key%7)
#193505