(P1) Fundamentals of Data Structures Flashcards
Describe the steps involved in adding a record to a hash table.
- Try putting record in first available position, if not able to, move to another location.
- Hash algorithm applied to key value.
- Result is location in table where record should be stored.
- If location is not empty then use next free location.
Describe how a single stack could be used to evaluate an RPN expression.
- Push values on to stack.
- Each time an operator is reached, pop two values and apply operator to them.
- Push result to stack.
- When end of the expression is reached the top item of the stack is the result.
What is the formula for Dot Product?
A . B = (Ax × Bx) + (Ay × By)
True or false: All regular languages can be represented using a finite state machine without outputs.
True.
True or false: The set of strings defined by a regular language can be finite or infinite in size.
True.
True or false: There are some languages that can be represented in Backus-Naur Form that are not regular languages.
True.
Discuss the advantages and disadvantages of dynamic data structures (DDS) compared to static data structures.
Disadvantages of DDS: Uses more memory as it uses pointers. Can take longer to add a new item to the data structure as memory needs to be allocated.
Advantages of DDS: Can grow as more data is added to the data structure. No wasted memory.
Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array. Your answer should include a description of how any pointers are used and changed.
Check if queue is full. If it is not full then add one to the value of the rear pointer. Then add the new item to the position indicated by the rear pointer.
Describe the steps involved when adding an item to a priority queue, implemented as a static data using an array, that are not required when adding an item to a linear queue.
Starting with the item at the rear of the queue move each item back one place in the array. Until you reach the start of the queue or find an item with the same or higher priority than the item to add. Add the new item in the position before that item.
Explain the circumstances when it would be more appropriate to use an adjacency matrix instead of an adjacency list.
Adjacency matrix appropriate when there are many edges between vertices. When the presence/ absence of specific edges needs to be frequently tested.
Explain how a stack could be used in the process of evaluating an expression in Reverse Polish Notation.
Push operands onto stack. Each time operator reached pop two value off stack and apply operator to them. Add result to the stack.
Explain what is meant by a heuristic technique.
Heuristic approach employs a method of finding a solution that might not be the best.
Explain the difference between static and dynamic data structures.
Static data structures have storage size determinded at compile time, whereas dynamic data structure can grow/shrink at run time. Dynamic data structure usually require more memory for pointer which static data structure do not need.
Explain what an array is.
An indexed set of elements. An array must be finite, indexed and must contain only elements with the same data type.
When a 2d array is set out in a table format, which coordinate is listed first?
The x coordinate.
What is a file made up of?
Records.
What are records made up of?
Fields.
What is an abstract data structure?
Data structures that use other data structures to form a new way of storing data.
Give an example of an abstract data structure.
Queue.
What is a queue?
An abstract data structure based on an array. FIFO.
Give an example of when queues are used.
Keyboard buffers, where each key press is added to the queue and then removed when the computer has processed the key press. This ensures that the letter appears on the screen in the same order they pressed.
What abstract data structure does a breadth first transversal use?
Queue.
How many pointers does a linear queue have?
Two pointers, front and rear.
What are the front and rear pointer used for?
Front: Identify which item is at the front of the queue.
Rear: Identify where to place a new item in a queue.
What is the term for adding to a queue?
Enqueue.
What is C# code for adding to a queue?
Queue.Enqueue.(“Insert Value”)
What is the term for removing a value from a queue?
Dequeue.
What is the C# code for removing a value from a queue?
Queue.Dequeue()
What are the four operations that can be performed on a queue?
Enqueue
Dequeue
IsEmpty
IsFull
How can you check is a queue is empty?
Compare the front and rear pointer, and if they are the same the queue is empty.
What is a circular queue?
A queue in which the front and rear pointer can move over the two ends of the queue, making for a more memory efficient data structure.
Describe how a priority queue works.
Items are assigned a priority. Items with the highest priority are Dequeue before low priority items.
In the case that multiple items have the same priority, items are removed using FIFO.
Describe when priority queues are used.
Frequently used in computer systems. Processors assign time to applications according to their priority. Applications in use by the user take priority over background applications, allowing for a faster user experience.
What is a stack?
FILO abstract data structure, which is based off an array.
How many pointers does a stack have?
One pointer, called the top pointer.
What is term for adding an item to a stack?
Push.
What is the term for removing off a stack?
Pop.
What does the Peek function on a stack do?
Returns the value of the item at the top of the stack without removing the value.
What are the five functions that can be used on a stack?
Push
Pop
Peek
IsEmpty
IsFull
What is the C# code for adding a value to a stack?
Stack.Push(“Insert Value”)
What error is produced when you try to add a value to an already full stack?
Stack Overflow
When is does a Stack Underflow error occur?
Caused by attempting to pop a value off on already empty stack.
What is a graph?
An abstract data structure used to represent complex relationships.
What is the Internet?
A network of interconnected computer networks.
What is another term for nodes?
Vertices.