資料結構

專業知識及核心能力

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

一、資料結構基礎

  • * 演算法與效率分析(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)及其應用

  • * 包括圖的表示方式
  • * 圖形演算法(graph algorithms)

* 排序與搜尋

  • Big O 介紹
  • *排序演算法(sorting algorithms)
    • 穩定的排序
      • 氣泡排序法(bubble sort)- O(n2)
      • 插入排序法(insertion sort)—O(n2)
      • 雞尾酒排序(cocktail sort)—O(n2
      • 合併排序(merge sort)—O(n log n);需要O(n)額外空間)
      • 二叉排序樹排序(binary tree sort)— O(n log n)期望時間;O(n2)最壞時間;需要O(n)額外空間
      • 圖書館排序(library sort)— O(n log n)期望時間;O(n2)最壞時間;需要(1+ε)n額外空間
    • 不穩定的排序
  • * 搜尋演算法(searching algorithms)
    • 深度優先搜尋法 Depth-first search (DFS)
    • 深度限制搜尋法 Depth-limited search (DLS)
    • 加深式搜尋法 Iterative deepening search (IDS)
    • 廣度優先搜尋法 Breadth-first search (BFS)
    • A搜尋法 A searc
  • * 雜湊(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)
    • * 選擇適當資料結構的策略

    演算法