CIS 153 - Data Structures

Outcome 2:   Apply the principles of recursive functions to solve problems when appropriate. 
       Task 1:  Trace the execution of a recursive function and determine its results.
       Task 2:   Write a recursive function given a description of the action it is to perform. 

Outcome 3:   Apply linked lists, stacks, and queues to solve problems. 
       Task 1:   Write routines that perform given operations on stacks at the application level. 
       Task 2:   Write routines that access data stored in a linked list. 
       Task 3:   Write statements or routines that will make changes in a linked list. 
       Task 4:   Trace the effect of given statements on a linked list. 
       Task 5:   Trace the execution of a routine that uses stack operations. 
       Task 6:   Trace the changes in a stack for given operations using an array- based implementation. 
       Task 7:   Write routines that perform given operations on an array-based stack at the implementation level. 
       Task 8:   Write routines that perform given operations on a pointer-based stack at the implementation level. 
       Task 9:   Write statements that could be used in a list-based implementation of a stack. 
       Task 10: Evaluate postfix expressions. 
       Task 11: Convert infix expressions to postfix expressions. 
       Task 12: Convert postfix expressions to infix expressions. 
       Task 13: Trace the execution of a routine that uses queue operations. 
       Task 14: Write routines that perform given operations on queues at the application level. 
      Task 15: Trace the changes in a queue for given operations using an array-based implementation. 
      Task 16: Write statements that could be used in a list-based implementation of a queue. 

Outcome 4:   Implement binary search tree data structures using C++ constructs. 
       Task 1:   Draw a binary search tree for a given set of data. 
       Task 2:   Use the terminology of trees. 
       Task 3:   Describe specific types of trees. 
       Task 4:   Perform preorder, inorder and postorder traversals of a tree. 
       Task 5:   Write a function that performs given operations on the nodes of a tree. 
       Task 6:   Draw a tree to show the effect of inserting a node. 
       Task 7:   Draw a tree to show the effect of deleting a node. 
       Task 8:   Show how a tree can be stored in an array using either explicit or implicit links.
 
Outcome 5:   Implement heap and graph data structures using C++ constructs. 
       Task 1:   Form a heap using given values. 
       Task 2:   Draw a heap to show the effect of inserting and deleting nodes. 
       Task 3:   Show how a graph can be stored in an adjacency matrix. 
       Task 4:   Traverse a graph using depth-first and breadth-first methods. 
       Task 5:   State a topological order of a directed graph.

Outcome 6:   Compare routines for the sorting of data with regard to the way they  manipulate data, their efficiency and their appropriateness for  specific applications. 
       Task 1:   Trace the execution of a specified sort routine for a given array. 
       Task 2:   Determine which sort routine was used for a given change in an array. 
       Task 3:   Determine the number of times that elements in a given array will be swapped for a specific sort routine.