CPSC 2108 - Data Structures - Midterm Study Guide

Study Material

Chapters 1-5 of Object-Oriented Data Structures using Java by Dale, Joyce, & Weems

Material from programming assignments and notes
CHAPTER EXERCISES!!!

Test Format (October 9, 2008 in CCT406)
Short Answer Questions (60 points) - evaluate, compute, write Java code, what is the output?
1 Programming Problem (40 pts)

• Students will learn to understand the principles of efficiency of algorithms
• Students will learn to understand how to specify, design and implement Abstract Data Types
• Students will learn to be able to implement and use data structures such as Lists, Stacks and Queues Data Structures
• Students will learn about and learn to use the concept of Recursion

• Getting Organized
  • Software Engineering
  • Object Orientation
  • Classes, Objects, and Applications
  • Organizing Classes (inheritance, packages)
  • Data Structures (implementation dependent and independent structures)
  • Basic STructuring Mechanisms (arrays, references)
  • Comparing Algorithms (Big-O Analysis)
• Abstract Data Types
  • Abstraction
  • ADT Specification
  • Array-based ADT Implementation
  • Linked List ADT Implementation
  • Software Testing
  • Software Design (Identification of classes)
• Stack ADT
  • Stacks (operations and uses)
  • Collection Elements
  • Exception Handling
  • Formal Specification
  • Array-based Implementation
  • Linked List Implementation
• Recursion
  • Recursive Definitions, Algorithms, and Programs
  • Three Questions
  • Recursive Linked-List Processing
  • Removing Recursion
  • Deciding whether to use recursion
• Queue ADT
• Queues (operations and uses)
• Formal Specification
• Array-based Implementation
• Linked List Implementation