Bergen Community College Data Structures Programming Questions

CSIT 254 Final Exam Info (Format and Contents)
You may have any of the following on the exam:
Short answer Definitions
About 10 short answer questions where you will write definitions or descriptions of the following
concepts, Data Structures, or Algorithms (definitions must be from our class and not from the internet):
•
•
•
•
•
•
•
•
•
Best Case of an Algorithm
Worst Case of an Algorithm
Linked List (singly)
o Fields in node: data/link
o Access point: head (minimally)
Stack
o Access point: top
o Actions:
▪ push to top
▪ pop from top
o Last In First Out (LIFO)
Queue
o Access points: front/rear
o Actions:
▪ Add to rear
▪ Remove from front
o First In First Out (FIFO)
Recursion
o Base case
o Recursive case
Binary Search Tree
o Fields in BST Node (data/left/right)
o Access point: root
o Each node contains no more than two children
o ‘order’ – from each node in Binary Search Tree:
▪ subtree to left is node
Graphs
o Consists of nodes/vertices and links/edges between nodes
o Graphs can be directional or non-directional
o Graphs can be weighted where edges/links have costs associated with them or nonweighted which do not have costs
o Graphs can be implemented:
▪ adjacency matrix ( 2-D array with source on left (row) and destination across top
(column) )
• non-weighted graph can be an array of boolean ( true/false)
• weighted graph can be an array of int or double or Cost
▪ linked lists – where each vertex/node maintains a linked list of vertices/nodes
that are adjacent to the node/vertex
Hash Function
1
CSIT 254 Final Exam Info (Format and Contents)
o
Transformation of a ‘key’ value into a physical location for data
A few examples of above:
•
•
•
•
Define the data structure Queue. Make sure you describe how add and remove works and to
what access point each uses.
Describe how nodes are arranged in a Binary Search Tree
Explain how a weighted graph differs from a non-weighted graph
Regarding Graphs, describe an adjacency matrix.
Data Structure ‘Diagrams’ – about 3 @ 10 pts each
Adding to an empty Data Structure: For the Data Structures listed above (Stack/Queue/Binary Search
Tree), show what the data structure will look like after a series of values are ‘added’ to the
structure.
Examples:
Suppose these are added in this order: Mango, Grape, Raisin, Apple, Plum, Lemon, Watermelon
Show a Stack, Queue, Binary Search Tree after these ‘adds’ take place – indicate access points
(top/front/rear/root)
Removing from an existing Data Structure: For the Data Structures listed above(Stack/Queue/Binary
Search Tree), if you are given a diagram, show what the data structure will look like after a
specific remove is done.
Examples (using the structures from the previous example):
•
•
•
perform a pop() from Stack – what value is removed, redraw Stack
perform a remove() from a Queue – what value is removed, redraw Queue
remove Mango from Tree, show the tree after Mango is removed
[ For the exam the key is to keep the tree as a Binary Search Tree, not to perform the
exact algorithm covered from the book ]
Create an Adjacency Matrix or Linked List ( 2 @ 10 points each ):
Given a Graph, create the adjacency matrix ( or vice-versa ), for weighted and non-weighted
(True / False, weights)
Example: See data structure labs
DFS or BFS ( 1 @ 5 points):
Given a Graph, show the nodes visited for DFS or BFS
Example: Like Data Structures Lab 9.5, the in-class exercise
Dijkstra’s Algorithm (1 @ 10 pts)
Given a Graph, show the shortest path showing Dijkstra’s algorithm. All work must be shown,
such as next, allowed vertices, and the matrix. Vertices may not be renamed to 1, 2 etc, the
original names must be written in a table form to show all the values, just like what was
expected on the data structure lab.
2
CSIT 254 Final Exam Info (Format and Contents)
Example: Like Data Structures Lab in-class exercise
Previous homework or Data Structure Lab Questions
NOTE: All work must be done as we learned it in class or else it will bemarked wrong. Googling
information on the internet is not acceptable. Googling definitions is not acceptable. It must be as it
applies to this class.
3