私立中原大學八十八學年度研究所資管系資料結構與資料庫試題

所組別 :	資訊管理學系	科目 :	資料結構與資料庫	考試時間 :	05月01日第3節

1. Define the following terms: (30%)
   
   1. Stack
   2. Queue
   3. Binary search tree
   4. AOV network
   5. B-tree
   6. ISAM
   
   
2. Write the postfix form of the following expressions: (10%)
   
   1. (A + B) * D + E / (F + A * D) + C
   2. A and B or C or not (E > F)
   
   
3. Design a data representation sequentially mapping a circular queue into an array q[0..n-1].
   Write Procedure addq to insert item into the circular queue stored in q[0..n-1] and
   Procedure deleteq to remove front element from q and put into item. (20%)
   
   
4. Devise a representation for a linked list where insertions and deletions can be made at either end. Such a structure is called a deque. Write a Procedure for inserting at either end. (20%)
   
   
5. Write the status of the file F = ( 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 ) at the end of each phase of the following algorithms: (20%)
   1. QuickSort
   2. HeapSort

　　　　　--- END---