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

請回答下列Big O 的相關問題： Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸 進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在 數量上的漸進趨勢。某個問題可採用5 個演算法A～E 求解，各演算法執 行時間的Big O 分別如下：A 為O（N2），B 為O（Nlog（log N）），C 為O（N1.5），D 為O（N2log（N）），E 為O（SQRT（N））。當N 很 大時，請根據演算法的執行時間，由慢至快排序這5 個演算法。（10 分） 給定100 萬個介於0 到100（含0 及100）的整數，請利用任一種高階 程式語言寫出一個O（N）的由大至小的排序演算法，並說明此演算法 為何是O（N）的方法。（15 分）

以下是一中序運算式（Infix expression）轉換（Convert）成後序運算式 （Postfix expression）的演算法 operstk = the empty stack; while(not end of input){ symb = next input character; if(symb is an operand) add symb to the postfix string; else{ while(!empty(operstk) && precedence(stacktop(operstk),symb)){ topsymb = pop(operstk); add topsymb to the postfix string; } /*end while*/ if (empty(operstk) || symb != ‘)’) push(operstk, symb); else topsymb = pop(operstk); } /*end else*/ } /*end while*/ ｗhile(!empty(operstk)){ topsymb = pop(operstk); add topsymb to the postfix string; } /*end while*/ 其中資料結構： “operstk”：用來儲存運算子的堆疊（Stack）； “stacktop(operstk)”：表示top 指標所指堆疊operstk 的運算子； 程序（Procedures）或函數（Functions）： “empty(operstk)”：檢查堆疊operstk 是否為空的布林函數； “pop(operstk)”：從堆疊operstk 中取出一運算子； “push(operstk, symb)”：將運算子symb 存入堆疊operstk； “precedence(op1,op2)”：布林函數，定義在一沒有左右括弧的中序運算 式中，op1 運算子出現在op2 運算子的左邊時，當op1 運算子優先順序不 低於op2 運算子，則設定成TRUE，否則為FALSE。例如，我們給定 precedence(‘*’, ‘+’)=TRUE ，precedence(‘+’, ‘+’)=TRUE ， precedence(‘+’, ‘*’)=FALSE，為了處理運算式左右括弧，設定下列 的precedence: precedence(‘(’, op) = FALSE /*op 為任一運算子*/ precedence(op, ‘(’) = FALSE /*op 為除’)’外的任一運算子*/ precedence(op, ‘)’) = TRUE /*op 為除’(’外的任一運算子*/ precedence(‘)’, op) = undefined /*op 為任一運算子*/ 以中序運算式(2+3)*4 為例，執行上述演算法，依處理每一個運算子或運 算元時，輸出postfix string 及operstk 內容為何（“eos”表示end of string）？ （25 分） symbol postfix string operstk (

以下7 個數字[21, 1, 16, 11, 25, 9, 35]，要儲存到Hash Table 中，Hash Table 的儲存空間是一個索引從0 開始的一維陣列（Array）。假設Hash 函數為 H（Key）=（Key * 3）mod 7，裝填因子（Load Factor）為0.7。 若處理Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的線性探測法（Linear Probing）：增量函數F（i）= i（i 為衝突的次 數）。請依序列出每存入一個數字後的Hash Table 的內容。接著計算在 相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分） 若處理Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的平方探測法（Quadratic Probing）：增量函數F（i）= i2（i 為衝突 的次數）。請依序列出每存入一個數字後的Hash Table 的內容。接著計 算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分）

+

請寫出對以下8 個數字[44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹 （Min Heap Tree）的過程。為方便最小堆積樹的建構，我們通常會使用一 個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆 積樹的建構。最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小 到大的排序過程。請說明此種排序法的計算複雜度Big O 為何？（25 分）

) *

下圖中有4 個城市8 條公路，公路上的數字表示這條公路的長短。請注意 這些公路是單向的。若使用Floyd Warshall 的動態規劃法求解從任意兩個 城市之間的最短路徑，請回答下列問題： 首先將圖的信息建成一個N*N 的初始距離矩陣，其中N 是節點的個 數，矩陣的各列（Rows）代表From Nodes，矩陣的各行（Columns） 代表To Nodes，矩陣中的值則分別代表上圖中從From Node 到To Node 的距離。（5 分） 其次列舉從D 到C 的最短路徑求解過程（需輸出最短路徑的值及路徑）， 並說明此方法的計算複雜度Big O 為何。（15 分）

eos 二、利用鏈結串列（Linked list）實做佇列（Queues），給予如下鏈結串列節 點及佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最 後一個節點，請使用C 語言完成insert(pq, x)程序，將整數值x 加 入（Insert）到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可 使用函數getnode() 配置（Allocate）一新節點。（25 分） struct node{ int info; struct node *next; }; typedef struct node *NODEPTR; struct queue{ NODEPTR front, rear; }; struct queue q; NODEPTR getnode() { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return(p); } insert(pq, x) struct queue *pq; int x; { NODEPTR p; } 三、一個二元搜尋樹（Binary search tree）的前序追蹤（Preorder traversal）結 果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20 請建構此二元搜尋樹。接著利用如下C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式sortTree（NODEPTR tree），輸入二元樹的根節點， 來處理此二元樹的節點資料，並將資料依由小至大輸出。（25 分） struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void sortTree(NODEPTR tree){ } 四、用G = (V, E)表示一個無方向性圖形，其中V 是點的集合，E 是一組節 點（Vertices）形成邊及對應權重（Weights）所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對 應連接矩陣(Adjacency matrix)表示中的值 #define MAX_EDGES 100 typedef struct { int col; int row; int weight; } edge; edge a[MAX_EDGES]; 已知陣列a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫 出陣列a 所儲存的圖形，然後，利用Prim 演算法從節點0 開始依加入其 它節點的順序，畫出此圖之最小擴張樹（Minimum spanning tree），並計 算其最低權重或成本值。（25 分）

下圖是一個加權圖G=(V, E)，其中V 是點集合而E 是邊集合。 請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖G。（5 分） 不考慮權重，從節點g 開始並按照字母順序對G 進行廣度優先尋 訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的BFS 樹 （BFS Tree）。（5 分） 請利用Prim's 演算法，從節點d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明Prim's 演算法的時間複雜度。（10 分）

利潤 40 15 60 20 45 10 55 最後期限 2 4 3 2 1 3 1 以文本（text）X=“AGTCATTCGATTC”，樣式（pattern）Y=“ATTC”兩字 串為例，請問使用暴力比較/窮舉法（exhaustive search）中的樣式前向法 （forward）及後向法（backward）各需比較幾次？（10 分） m,n N   ,已知三維陣列（three-dimensional array）A[1：8, 1：9, 1：4]每一 個元素占用2 個儲存單元，並且A[1,2,1]的儲存地址為234，A[2,3,1]的儲 存地址是m，A[2,3,4]的儲存地址為n。 採用列序為主序（row major）方式儲存，則m、n 分別為何？（10 分） 採用行序為主序（column major）方式儲存，則m、n 分別為何？（10 分）