CS ADT's GAME

A queue is a data structure that operates on a ____ principle.

The input sequence of a stack is 1, 2, 3...n, if the first element of the output sequence is n, the i-th (1<= i <=n) element of the output is

• A. not sure

• B. n-i+1

• C. i

• D. n-i

Following pseudocode writes about accessing all nodes stored in the linked list. Read the code and fill in the blank.

PEOCEDURE OutputAllNodes

CurrentNodePtr <-- StartPointer

WHILE CurrentNodePtr <> NullPointer

OUTPUT List[CurrentNode].Data

CurrentNodePtr <-- _______________

ENDWHILE

ENDPROCEDURE

What is the result of the inorder traversal in this binary tree?

• ABDEC

• DEBCA

• DBEAC

• None of the above answers are correct

In linked lists, elements are not stored in ____ memory location.

The four elements enter into queue consecutively in order A, B, C, and D. After an out of the queue operation, the front element of the queue is

• A

• B

• C

• D

Which two storage structures can be used for a general binary tree？

• Sequential storage (using arrays)

• Sequential storage (using queue)

• Sequential storage (using stack)

• Chain structure (using linked lists)

State a disadvantage of linked lists.

Answer explanation

Requires additional storage to save data and a pointer.

When storing a queue sequentially with an array of size N, the index of the last element of the queue is

• A. N+1

• B. N

• C. N-2

• D. N-1

1. Following pseudocode writes about finding an element in an ordered linked list. Read the code and fill in the blank.

 

FUNCTION FindNode(DataItem) RETURNS INTEGER

CurrentNodePtr <-- StartPointer

WHILE CurrentNodePtr <> NullPointer AND _______

CurrentNodePtr <-- List[CurrentNodePtr].Pointer

ENDWHILE

RETURN CurrentNodePtr

ENDFUNCTION