110年 - 110 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#104251

試卷資訊

選擇題 (0)

申論題 (6)

1.【此題15分】我們用陣列實作heap。圖一是heap陣列裡頭的內容,每個元素皆為正整數,並且我們設定「正整數值愈小，priority愈高」。現在,我們想將heap裡頭prority最高的元素刪除；請問刪除之後,heap陣列裡頭的內容為何?畫出heap陣列裡頭每個index的內容。
圖一:

2.【此題15分】請寫出中序(infix)運算式2*((13-6/2)*(7+6)) 所對應的後序(postfix)運算式。

3.【此題20分】圖二為doublylinkedlis資料結構,其中每個 Node 結構包含三個欄位「prev、key、next」更具地說,下為de的宣告:

現在,如圖二,給定一個doublylinked list，裡頭包含5個 Node;Node 裡頭的數字為該 Node的key欄位值。請寫出一段程式碼,能夠在輸入i的值之後,删除圖二裡頭第i個 Node,其中1≤i≤5。
註1:圖二裡頭,第1個Node為指標變數head所指出的Node,第5個Node為指標變數 tail所指到的Node:NULL表示空指標(nullpointer) 。
註2:限定程式碼裡頭必須有迴圈,否則此題以0分計算。
圖二:

4.【此題20分】在圖三所示的tree裡頭,每個node裡頭的英文字母為node的key值,我們假設root的key值為a。當我們分別按breadth-first search(BFS)preorderinorder、 postorder 次序拜訪圖三的tree時nodes被拜訪的次序為何?
圖三:

5.【此題15分】圖四為一個AVLtee,每個node儲存一筆料,node裡頭的數字,代表資料的key值；root的key值為42。畫出「删除key值為42的資料」之後的AVL tree。
圖四:

6.【此題15分】陣列所能儲存的元素個數稱為capacity。向量(vector是一種能擴增 capacity的陣列。我們採用向量、open addressing、linear probing的方式實作 hash table,並保持loadfactor最多為0.6;此外,每次執行rehashing時,向量的capacity都擴增為「大於原本capacity值1.5倍的最小質數」。假設我們打算放入 hashtable的資料,key值為正整數,並且hashfunction為h(key)=key%capacity:此外,實作 hashtable的向量,其 capacity的起始值為5。那麼,當我們依序把key值為54、23、41、57、19、36、47的資料依序放入hashtable之後，hashtable的內容為何?畫出每一筆資料的最後所在位置。