Data Structures and Manipulation

Question 1

State the term used to describe data structures where the size is fixed when created.

Answer 1

Static

Question 2

State an example of a static data structure.

Answer 2

Array

Question 3

What are the advantages of using static data structures?

Answer 3

• Compiler can allocate space in memory during compilation
• Easy to program
• Easy to check for overflow
• Allows random access

Question 4

What are the disadvantages of using static data structures?

Answer 4

• Program has to estimate maximum space needed

- Space can be wasted via over-estimation

Question 5

What are the advantages of using dynamic data structures?

Answer 5

• Only uses the space needed at any time
• Makes efficient use of memory
• Storage no longer required can be returned to the system for other use

Question 6

What are the disadvantages of using dynamic data structures?

Answer 6

• Difficult to program
• Can be slow to implement searches on data
• A linked list only allows serial access (time consuming for long lists)

Question 7

Under what condition is a queue empty?

Answer 7

When front and next pointers point to the same location.

Question 8

Write an algorithm to remove one data item from a queue.

Answer 8

1. Check to see if the queue is not empty.
2. If empty, report error and stop.
3. Otherwise read the data pointed to by front pointer
4. Increment front pointers

Question 9

Write an algorithm to merge two sorted files.

Answer 9

1. Open existing files
2. Create new file
3. Use points to identify records for comparison
4. Compare records indicated to by pointers
5. Copy earlier/smaller value record to new file
6. Increment point from copied record
7. Repeat until reach the end of one file
8. Copy remaining records to new file

Question 10

What is the main advantage to binary search?

Answer 10

• (usually) faster than serial because fewer items are checked/more efficient for large files

Question 11

What is the main disadvantage for binary search?

Answer 11

• items must be in an order to allow appropriate items to be discarded

Question 12

State two features of files that can be merged.

Answer 12

• records have a common key
• files each have records sorted into the same order
• same data type

Question 13

Describe a queue data structure.

Answer 13

• first in, first out/FIFO/data items are added at one end & removed from the other
• two pointers are required

Question 14

State uses of a queue in a computer system.

Answer 14

• spool queue/jobs waiting for printer
• job queue in batch processing system
• Handling of jobs in a round robin system

Question 15

What validation must be done before adding data to a queue?

Answer 15

Check if full, if full report error and stop

Question 16

What validation must be done before removing data from a queue?

Answer 16

Check if empty, if empty report error and stop

Question 17

Write an algorithm to add a data item to an existing binary tree.

Answer 17

start at root
repeat
compare new data with current data
if new data

Question 18

What data structure is FIFO?

Answer 18

Queue

Question 19

What data structure is FILO?

Answer 19

Stack

Question 20

State features of a quick sort that is not used in insertion sort.

Answer 20

• set of numbers broken into multiple sets

- uses pivots

Question 21

List the steps needed to pop a data item from a stack.

Answer 21

• if stack is empty…
• …report error and stop
• output data(stack_pointer)
• decrement stack_pointer