DP Computer Science Questionbank

Identify two characteristics of a dynamic data structure.

Sketch a balanced binary tree that would allow the following output when traversed using in order traversal:

Zebra, Tango, Hotel, Foxtrot, Delta, Bravo, Alpha. 

Describe the features of a dynamic data structure.

Determine the output produced by the method call mystery(4).

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

A third stack, FLOFRU, is needed. It should contain all the data from FLOWERS  and FRUITS and will store it as shown below

Describe how the FLOFRU stack could be created.

Explain how “Primrose” could be inserted into this doubly linked list. You should draw a labelled diagram in your answer.

State the index in $\mathrm{VALUES}$ of the first non-zero element in row $5$ of $\mathrm{BIGMAT}.$

Sketch a single linked list holding these vegetables.

Explain the importance of the method isEmpty() when constructing an algorithm which performs operations on a stack data structure.

State Paul’s total score. 

State where Hugh’s score in the fourth round can be found. 

Compare the use of a dynamic linked list for holding these names of vegetables with a static one-dimensional array.

List the steps required to insert cabbage into the linked list.

State the dynamic data structure suitable for maintaining this list of vegetables which will allow faster searching for a given vegetable name.

All the data stored in memory should be sorted in ascending order of total score using selection sort.

For example, after sorting, the data given opposite will be held in memory as follows

Construct an algorithm that will sort all the data in ascending order.

In your solution you should call methods swap() and swapRows() given in part (a) and part (b).

Explain why deleting the first node in this list is different to deleting other nodes.

The vegetable names are input in the following order

potato, asparagus, lettuce, radish.

Sketch the data structure suggested in part (d) containing the vegetable names sorted in alphabetical order.

Sketch a double linked list that holds the following sequence of names: Anne, Lana, Mary.

Construct an efficient algorithm for the method isValidMatrix().

Determine the value of variable X after execution of the following method call:

X = mystery(MAT,5)

where MAT is the two-dimensional array given. You must show your working.

Deduce the purpose of the method mystery(A,R).

State the result of postorder traversal.

State the value of MAT[3][4].

State two applications of stacks.

Draw the binary tree after deleting the root node.

Compare the use of static and dynamic data structures.

Explain the use of a one-dimensional array as a static stack. Your answer should include brief outlines of the push and pop operations and the tests for empty and full stacks. 

Given the following binary search tree (BST), draw the resulting BST after the deletion of the root node.

Outline how the last node of the circular linked list is identified.

Describe the steps required to calculate the sum of all numbers held in this circular linked list.

Compare the use of arrays and linked lists.

Identify one difference between a binary tree and a non-binary tree.

Sketch a diagram showing the resulting circular linked list.

State the distance between Kiko and Longlines.

Construct an algorithm in pseudocode that inputs the names of two bus stations and outputs the distance between them. If any of the inputted names are not found, the method should output an appropriate message.

A linked list can be used to implement a data structure queue.

Identify two applications of a queue data structure.

Construct an algorithm in pseudocode that checks the elements of the array ROUTE_X_DISTANCES and outputs whether the array is valid or not.

The array ROUTE_X_TIMES (Figure 3) stores the approximate number of minutes it takes for a bus to travel to a bus station from the previous one. For example, ROUTE_X_TIMES [6] stores the number of minutes it takes for a bus to travel from Kingsley to Allapay: 7 minutes.

Figure 3: The array ROUTE_X_TIMES

Explain how this data could be used to determine the number of minutes it takes for a bus to travel between any two bus stations.

Identify one disadvantage of using a two-dimensional array for this purpose.

Identify one advantage of using a two-dimensional array for this purpose.

State the result of preorder traversal of this binary tree.

Describe one difference between stack and queue data structures.

State the purpose of the following queue method:

enqueue()

Assume that the queue Q holds the following data:

The reversed queue Q would be:

Construct an algorithm in pseudocode for reversing the queue using a stack data structure.

You may assume that the data in the queue is input and a new empty stack is created.
Only the standard queue and stack operations are allowed.

Consider the following recursive method:

mystery(N)
    if N>0 then
        return 3 + mystery(N-3)
    else
        return 3
    end if
end mystery

where N is an integer.

Determine the value of mystery(7). Show all your working.

State the result of inorder traversal of this binary tree.

State the purpose of the following queue method:

dequeue()

Outline one disadvantage of solving problems recursively.

Construct an algorithm in pseudocode for the method invert(N,A).

Outline why it is more efficient that the loop in the given algorithm fragment executes (K mod 4) times instead of K times. You may give an appropriate example in your answer.

Construct the algorithm in pseudocode for the method rotate(N,A) described above.

To avoid inefficient use of memory, a new algorithm for the method rotate(N,A) is constructed.

The N × N two-dimensional array A should be rotated clockwise by 90°, without the use of any additional arrays.

One way of rotating the two-dimensional array A clockwise by 90° is to transpose A, and then reverse each row of A.

The transpose of A is formed by turning all the rows of A into columns. For example, the value in the first row and third column (A[1][3]) is swapped with the value in the third row and first column (A[3][1]).

Construct the new algorithm in pseudocode for the method rotate(N,A) described above.

State the purpose of the following queue method:

isEmpty()

State the number of degrees by which the image will be rotated if the input value of K is 3.

Describe the characteristics of a queue.

Explain the benefits of using a binary search tree, compared to a stack, when searching for a specific item.

If the tree is populated with the data from the stack, the first item popped off will become the root. For each subsequent item popped from the stack, a recursive procedure is followed until the item is correctly placed in the tree.

Without writing code, describe this recursive procedure.

By considering only the data visible in the stack shown above, sketch the binary search tree that has been created from the items removed from the stack.

Construct the pseudocode that will search the stack for a specific name, and output its position in the stack. You may assume that all names in the stack are unique.

Construct pseudocode that will read PASSENGERS into the two-dimensional array, 2D_ARRAY.

Construct the pseudocode for the procedure total, that takes as input a column number of this two-dimensional array and returns the sum of the elements in that column.

The transport authority wishes to know how many passengers, on average, travel on each day of the week.

Using the procedure total construct the pseudocode to output the day of the week with the highest average number of passengers, and the value of this average.

You should make use of the sub procedure convert() which converts the numbers 0 to 6 into days of the week, for example convert(1) will return “Tuesday”.

The transport authority stores details about the ticket prices in a one-dimensional array, FEES, where FEES[0] contains the price of a ticket for Monday to Friday, while FEES[1] contains the price of a ticket for Saturday and Sunday.

The procedure salesCalculate() takes as input the column and row indices that define two specific days during the 30 weeks, and outputs the total amount of money generated from ticket sales between those two days (inclusive).

Construct, in pseudocode, the procedure salesCalculate().

Outline why a binary tree would be a good choice of data structure for maintaining an address book.

State the output from the binary tree using postorder traversal.

Construct an algorithm that will enable the company to print the mailing labels for all customers called Jones who live in Cardiff.

Explain the steps to insert “Jones” into this singly linked list. You may draw a labelled diagram in your answer.

Outline one example of where a circular linked list would be used in preference to a linear linked list.

Construct the pseudocode that will find how many customers live in the city of Cardiff and display the results.

State the output from the given tree using inorder tree traversal.

Identify one characteristic of a queue.

Identify one application of a queue.

Outline the steps involved in traversing the given tree using postorder tree traversal.

Define the term child in relation to a binary tree.

Explain why a stack is used in the process of evaluating the expression in the algorithm.