Review data structure for midterm @Kasetsart

data-structure-midterm.md

[x] Primitive Type

• Basic Data Type
  • Primitive Data Type (e.g. char, int, float)
  • Structure Data Type (e.g. array, struct)
  • Pointer
• Abstract Data Type
  • Linear Data Structure (e.g. linked list)
  • Non-linear Data Structure (e.g. tree)
• Integer (Number System)
  • Signed magnitude representation
  • 1’s complement system
  • 2’s Complement System (1's com +1)
  • Operation (+, -)
  • Range & Overflow / Underflow
• Real Number
  • Binary Represent (IEEE)
  • Floating point operation
• Boolean
  • Logical operators
  • Boolean operator
  • Relational operator

[x] Array

• One Dimension Array
  • Range (Lower Bound, Upper Bound)
    • arr[L:U]
  • Calculate array total member
    • U - L + 1
  • Calculate Memory Address
    • LOC(A[i]) = B + w x (i - L)
• Two Dimension Array
  • Range
    • arr[L1:U1, L2:U2] || K[row, column]
  • Calculate array total member
    • (U1 - L1 + 1) * (U2 - L2 + 1)
  • Two Dimension Array in Memory
    • Row major order
    • Column major order
  • Calculate Memory Address
    • Row major order
      • LOC(K[i,j]) = B + w[C(i - L1) + (j - L2)]
    • Column major order
      • LOC(K[i,j]) = B + w[R(i - L1) + (j - L2)]
• Three Dimension Array
  • Calculate array total member
    • (U1 - L1 + 1) * (U2 - L2 + 1) * (U3 - L3 + 1)

[x] Struct Pointer

• Struct vs Array
• Struct Declaration
• Reference to member
• How struct stored in memory
  • Memory Alignment (4-byte boundary)
• Array of Struct
• Pointers & Addresses
• Pointers and Function Arguments
  • pass by Value
  • pass by Reference
• Double Pointers
• Pointer Struct

[x] String and String Manipulation

• String declaration in C
• get string from standard input
  • scanf("%s", str);
  • gets(str);
• print string (show result)
  • printf("%s", str);
  • puts(str);
• String Manipulation
• String Library
  • int strcmp(char *str1, char *str2);
  • char * strcpy(char *dest, char *src);
  • char * strcat(char *dest, char *src);
  • int strlen(str);
  • char * strcnpy(char *dest, char *src, size_t maxlen);

[x] Stack

• Implementation Stack
  • Array Implementation
  • Linked List Implementation
• Stack Operation
  • Push
  • Pop
• Stack to interpret Math Expressions
  • Infix to Postfix Algorithm
  • Operator Precedence
  • Tree Abstraction & Search

[x] Queue

• Queue Operation
  • Enqueue
  • Dequeue
• Circular Queue
  • Enqueue of Circular Queue
  • Dequeue of Circular Queue
• Priority Queue

[x] Linked List

• Implementation of Linked List in C
  • Add
  • Delete
  • Search
  • Print
• Singly Linked List (SLL)
  • Ordinary Singly Linked List (Default)
  • CircularSinglyLinkedList (CLL)
• Doubly Linked List
  • Ordinary Doubly Linked List (ODLL)
  • Circularly Doubly Linked List (CDLL)

[x] Recursion

• Linear Recursion
  • Base step
  • Induction step
• Tail Recursion
• Binary Recursion
  • e.g. Fibonacci
• Multiple Recursion
  • e.g. Ackermann
• Greatest Common Division(GCD)

  let gcd = (a, b) => b == 0 ? a : gcd(b, a % b)

• Tower of Hanoi Problem

  function Hanoi(n, from, to , via)
  {
    if (n==0) return;
  
    Hanoi(n-1, from, via , to);
  
    console.log(from, to);
  
    Hanoi(n-1, via, to , from);
  }

[x] Searching

• Sequential Searching (Linear Search)

  const linearSearch = (arr = [], data) => {
    for (let i = 0; i < arr.length; ++i) {
      if (arr[i] === data) return i;
    }
    return -1;
  }

• Complexity of algorithm
  • Average case
  • Rate of growth
  • Big Oh Notation
• Binary Search

    const binarySearch = (arr = [], data) => {
      let left = 0;
      let right = arr.length - 1;
      let mid = Math.floor((right + left) / 2);
  
      while (arr[mid] !== data && left < right) {
        if (data > arr[mid]) left = mid + 1;
        if (data < arr[mid]) right = mid - 1;
  
        mid = Math.floor((right + left) / 2);
      }
  
      return (arr[mid] !== data) ? -1 : mid
    }

• Hashing Search
  • Hashing Function
    • Mod
    • Mid-Square
    • Folding Method
  • การชนกันของข้อมูล
    • Linear Probing
    • Double Hashing
    • Chaining