資料結構

專業知識及核心能力

一、了解資料結構的整體概念與在軟體發展上的重要性。
二、熟悉各種資料結構的特性與相關操作方式。
三、了解在實際應用時,如何挑選適當的資料結構,以及各種資料結構較佳的實作方式。

一、資料結構基礎

  • * 演算法與效率分析(algorithm and performance analysis)
    • 演算法簡單的來說就是完成一個問題所需要的具體步驟和方法。
  • * 陣列(arrays)
  • * 指標概念(pointers)
  • * 字串處理(string manipulation)
  • * 遞迴(recursion)
  • * 堆疊(stacks)
  • * 佇列(queues)
  • * 串列(lists)

* 樹狀結構(trees)及其應用

  • * 二元樹(binary trees)
    • 後序遍歷(postorder traversal)
    • 陣列 A[1..15]實作二元樹
    • 完整二元樹(complete binary tree)
    • 完滿二元樹(full binary tree)
  • * m路樹(m-way trees)
  • * 查找樹(tries))
  • 紅黑樹(Red-Black Tree)
  • 擴張樹 Spanning Tree
  • 決策樹

* 圖(graphs)及其應用

* 排序與搜尋

將輸入【Inpit: n 個數字(每個都不重複)】經過處理後,輸出排序後的資料【Output: A sorted (從小到大) list of these number.】。

  • *排序演算法(sorting algorithms)
    • 穩定的排序
      • 插入排序法(insertion sort)—O(n2)
      • 合併排序(merge sort)—O(n log n);需要O(n)額外空間)
      • 氣泡排序法(bubble sort)- O(n2)
      • 雞尾酒排序(cocktail sort)—O(n2) 
      • 二叉排序樹排序(binary tree sort)— O(n log n)期望時間;O(n2)最壞時間;需要O(n)額外空間
      • 圖書館排序(library sort)— O(n log n)期望時間;O(n2)最壞時間;需要(1+ε)n額外空間
    • 不穩定的排序
  • Big O 介紹
  • * 搜尋演算法(searching algorithms)
  • * 雜湊(hashing)
    • Hash碰撞時可以採用的策略:
      • 「線性探測法」(open addressing with linear probing)
      • 「二次方探測法」(open addressing with quadratic probing)
      • 「雙探測法」(open addressing with double hashing)
      • 若雜湊表夠大(例如 slots = 2 或更大)但資料量多時,針對三種碰撞時所採取的處理方
        式,請說明那一種方式較能有效率的儲存或搜尋資料?請說明那一種處理方式效率最
        差?
  • * 優先佇列(priority queues)
  • 迴圈
    • 尤拉迴路(Euler Cycle)
    • 漢密爾頓迴路(Hamiltonian Cycle),
    • 旅行商人問題(Traveling Sales Man Problem)
    • 最短路徑
      • 例如 Dijkstra 演算法
    • 任兩點最短距離
      • 弗洛伊德(Floyd-Warshall)演算法

密碼學

* 綜合應用

  • * 外部儲存的資料處理(processing data in external storage)
  • * 資料壓縮(data compression)
  • * 選擇適當資料結構的策略

演算法