Summary for upcoming final exam | Data structure | CS

This post is a summary for the upcoming final exam of Data structure in Computer Science course in Fall, 2014.

Summary

Range of the final exam

Chapter 8?15 in the text book.

About chapters

Chapter 8: Queues ***
Chapter 9: Recursive Thinking ***
Chapter 10: Trees ****<
Chapter 11: Tree Projects ****
Chapter 12: Searching **
Chapter 13: Sorting **
Chapter 15: Graphs *****

Chapter 8: Queues ***
  • Definition
  • STL Queue class template
  • Queue application 1: Recognizing palindromes
  • Queue application 2 : Car wash simulation
  • Implemetation 1: Array
    • (1) Simple array
    • (2)
    • (3) Circular array
  • Implementation 2: Linked list
  • “Priority Queue”
    • Definition
  • “Deque”
    • Definition
Chapter 9: Recursive Thinking ***
  • recursive thinking. recursive programming.
  • Recursion
    1. Initial statement (stopping case in a recursive function)
    2. recursive relation (recursive calls in a recursive function)
  • Example 1: Fractals and Mazes
Chapter 10: Trees ****
  • Tree
  • terminology
    • node, branch
    • root, leaf[terminal]
    • the parent, child, sibling
    • ancestor, descendant
    • subtree
    • depth, level
    • Binary tree
    • Full binary tree
    • Complete binary tree
  • Tree representations
    • array
    • class
      • member variables
      • member functions
  • Binary tree node class
  • Tree traversals of binary trees
    • 3 common ways of traversal
      1. Pre-order
        • Root(pre) >> Left >> Right
      2. In-order
        • Left >> Root(in) >> Right
      3. Post-order
        • Left >> Right >> Root(post)
    • (a function as a parameter in another function)
  • Binary search tree
    • conditions
      1. a binary tree
      2. #(nodes in its left subtree) >= #(nodes in its right subtree)
      3. for every node,
        left node <= the node <= right node
    • a bag class with a binary search tree
Chapter 11: Tree Projects ****
  • Heap
    • definition
      • “a complete binary tree that every node in the tree is never less than the data of its children”
    • 2 important heap algorithms
      • insertion: add to the bottom >> reheapication
      • removal: remove the data >> add the last data to the deleted node >> reheapication
    • a heap can be used to implement a priority queue.
  • B-tree
    • Definition
      • 6 Rules
    • algorithms of data insertion and deletion
Chapter 12: Searching **
  • ?Searching methods
    1. serial search
    2. binary search
    3. search by hashing
  • Serial search
    • = squential search
    • big-O(N)
  • Binary search
    • Format of the data : sorted array
    • big-O(logN)
  • Search by hashing
    • Format of the data : array with indexes
    • Hash function H : {Key values} –> {indexes}
    • problem : Collision
    • solution : just add posterior to where the collision occured
    • Hash table : a table mapping key values to indexes by a hash function
    • Table class template
    • 3 types of Hash functions
      • Division
        • H(key) = key % table_size
      • Mid-sqaure
        • H : key -> key*key -> the converted binary number?-> the selected continuous middle digits -> the converted decimal middle digits(this is the index)
      • Multiplicative
        • H : key -> the first few digits of a*key (0<a<1)
    • 3 types of open-address hashing
      1. Linear probing
      2. Double hashing
      3. Chained hashing
Chapter 13: Sorting **
  • 2 types of sorting
    1. Selection sort
    2. Insertion sort
  • Selection sort
    • maximum or minimum search for all (n-1) steps
    • time complexity : O(n?2)
      • an average case algorithm
  • Insertion sort
    • insert a number to a right front sorted numbers
    • time complexity
      • worst case : n*(n-1)/2 times for comparision : when sorted
      • best case : n-1 times for comparision : when reversely sorted
Chapter 15: Graphs *****
  • Graph definitions
    • graph
      • a nonlinear data structure
      • 2 components
        • objects : nodes
        • connections : links
    • node/vertex, link/edge/arc
    • label : in data structure this is data.
    • direct graph, undirected graph
    • directed link/edge/arc :?source?→ target
    • undirected state graphs
    • loop : a link which source == target
    • path : a sequence of vertices
    • cycle : a path where initial vertex == final vertex
    • multiple edge
    • simple graph : no loops and no multiple edges
  • Graph implementations
    • 3 data structures for graphs
      1. Adjacency matrix
      2. Adjacency list
      3. Edge set
    • functions (methods for a graph class
  • Graph traversal
    • 2 common ways of graph traversal
      1. depth-first search
        • source?→ target(deeper)
        • one in level n?→ one?in level n+1
      2. breadth-first search
        • all in level n?→ all in level n+1
  • Path algorithms
    • Determining whether a path exists
    • Finding the shortest distance path
      • Dijkstra’s algorithm
        • Finding single source shortest path

 

Leave a Reply

Your email address will not be published. Required fields are marked *