Computer Science Quiz

What is the time complexity of the following algorithm with respect to the input size N?

• O(1)

• O(N)

• O(N^2)

• O(2N)

Which of the following is wrong about graphs?

• Weight of an edge must be positive.

• Weight of an edge can be negative.

• Adjacency matrix is an appropriate representation of a graph.

• Adjacency list is an appropriate representation of a graph.

In a hash table of size N using linear probing, what is the probing hash function hi(k)?

• hi(k) = h(k) mod N.

• hi(k) = (h(k) + i) mod N.

• hi(k) = i + k.

• hi(k) = i mod N.

Which statement is correct about array-based lists?

• Array-based is faster than linked-list in accessing items.

• Array-based is faster than linked-list in inserting new items.

• Elements of array-based lists can be dynamically located.

• They can be implemented by Java only.

In the ADT of the list data structure, isEmpty() method returns a/an _______ value.

• Real number.

• String.

• Integer.

• Boolean.

Which of the following describes the number of paths of length K from vertex Vi to vertex Vj?

• The weight of the path from vertex Vi to vertex Vj going exactly through K vertices.

• The number of paths of length K from vertex Vi to vertex Vj.

• The length of the Hamiltonian cycle that has K vertices including Vi and Vj.

• The weight of the shortest path from Vi to Vj using intermediate vertices in {V1..Vk}.

Given the following tree, what is the result of pre-order traversal?

• A,B,C,D,E,F,G,H,I,J

• A,D,B,C,J,G,E,F,I,H

• A,B,D,C,E,G,J,F,H,I

• A,B,D,C,E,F,G,J,H,I

A queue Q has 5 character items, Q={"A", "B", "C", "D", "E"}, where "E" is the rear and "A" is the front. What is the content of Q after the operations enqueue("F") → dequeue() → dequeue() → dequeue() → enqueue("D")?

• Q={"D", "E" ,"F" ,"D"}

• Q={"D", "F", "A", "B"}

• Q={"C", "D", "E", "F"}

• Q={"A", "B", "C", "D"}

Which statement below is wrong in the context of a linear sorting algorithm?

• The sorted order is based on comparisons between sort keys.

• Counting sort and Radix sort are linear sorting algorithms.

• The time complexity is linear.

• The sort key must be numeric.

One difference between a queue and a stack is:

• Stacks require linked lists, but queues do not.

• Queues require linked lists, but stacks do not.

• Queues use two ends of the structure; stacks use only one.

• Stacks use two ends of the structure; queues use only one.