資訊處理 97 年資料結構考古題

現有變數宣告如下：（每小題5 分，共25 分） int intArray[3][2] = {{10, 20}, {15, 25}, {50, 40}}; int ** intPtr1 = intArray; int * intPtr2 = &intArray[1][1]; int * intPtr3[2] = &intArray[2]; intArray 的記憶體位址是0x0008600，int 為sizeof(int) = 4； 試回答下列問題（如果是正確的敘述請寫出左邊變數的數值，錯誤請說明原因，但 每題題目是有關連性的）： *intPtr2 = intArray[1][1]; intPtr1 + 1 = intArray[0]； ++intPtr = &intArray[1]; *(*intPtr + 1) = intArray[1][0]; *(*intPtr3 + 1) = intArray[2][1];

2

2 1 3 一、假設一個圖（graph）的各個邊（edge）依下列順序輸入：（20 分） A, B A, D A, E B, C B, D D, C D, F E, F E, G F, G 以A 為起始點，利用堆疊（stack）依字母順序做深度優先搜尋（depth-first search）， 請寫出搜尋結果。 以A 為起始點，利用佇列（queue）依字母順序做廣度優先搜尋（breadth-first search）， 請寫出搜尋結果。 二、對下圖的2-3-4 樹（2-3-4 tree）刪除60，加入8，再轉為紅黑樹（red black tree），請畫出 紅黑樹結果〔3-節點（3-node）分裂時，以較大鍵值為父節點（parent）〕。（20 分） 三、請畫出如何使用堆疊（stack），將下面中序表示法（infix notation）a + b * c / d - e 轉成 後序表示法（postfix notation）。（20 分）

右圖中，邊（edge）之數字代表成本（cost）：（20 分） 請用相鄰矩陣（adjacency matrix）表示此圖之成本。 請用相鄰串列（adjacency list）表示此圖之成本。

某系課程可視為N 個資料元素構成的一個集合，裏面每個資料元素即一門課，含課 號（四位數字）名稱（四個中文字）等資料欄位，以“課號”為鍵，假設依序加 入下面四門課：1234 資料結構、2345 軟體工程、3456 網際網路、2333 離散結構。分 別用下面三種資料結構表示該集合，請分別畫圖表示之：（20 分） 陣列（array）。 雙鏈結環狀串列（double linked circular list）〔要有頭節點（head node）〕。 二元搜尋樹（binary search tree）。 50 10 5 70 80 7 9 30 40 60 75 85 90 92