DSA final (FIT HANU)

Which of the following is wrong about

graph? Choose one answer.

• Weigh 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 the 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

list? Choose one answer.

• Array-based is faster than linked-list in case of accessing list’s items.

• Array-based is faster than linked-list in case of inserting new item into the list.

• Elements of array-based list can be located dynamically and discontinuously.

• They can be implemented by Java language only.

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

value? Choose one answer.

• Real number.

• String.

• Integer.

• Boolean.

A queue Q has 05 character items, Q={“A”, “B”, “C”, “D”, “E”} where “E” is

the rear and “A” is the front of the queue. What is the content of Q if we perform the following

list of operations on the queue: enqueue(“F”)-->dequeue()-->dequeue()-->dequeque()--

>enqueue(“D”)?

Choose one answer.

• 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 linear sorting

algorithm? Choose one answer.

• The sorted order is determined based on the 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: Choose one answer.

• 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.

Bubble sort algorithm is used to sort the array A={23,78,45,8,32,56} in

the ascending order. What are the items of A after 03 sort pass?

Choose one answer.

• A={8,23,32,45,56,78}

• A={23,45,8,32,56,78}

• A={8,32,23,45,56,78}

• A={23,32,78,56,45,8}

Answer explanation

1st iteration:

Comparing 23 and 78: 23 is smaller, so no swapping occurs.

Comparing 78 and 45: 78 is larger, so they swap positions.

Comparing 78 and 8: 78 is larger, so they swap positions.

Comparing 78 and 32: 78 is larger, so they swap positions.

Comparing 78 and 56: 78 is larger, so they swap positions.

Array after 1st iteration: A={23, 45, 8, 32, 56, 78}

2nd iteration:

Comparing 23 and 45: 23 is smaller, so no swapping occurs.

Comparing 45 and 8: 45 is larger, so they swap positions.

Comparing 45 and 32: 45 is larger, so they swap positions.

Comparing 45 and 56: 45 is smaller, so no swapping occurs.

Array after 2nd iteration: A={23, 8, 32, 45, 56, 78}

3rd iteration:

Comparing 23 and 8: 23 is larger, so they swap positions.

Comparing 23 and 32: 23 is smaller, so no swapping occurs.

Comparing 32 and 45: 32 is smaller, so no swapping occurs.

Array after 3rd iteration: A={8, 23, 32, 45, 56, 78}

After 3 sort passes, the items of A are A={8, 23, 32, 45, 56, 78}.

Which of the following is correct about array-based binary implementation using

perfect binary tree indexing scheme?

Choose one answer.

• The parent of node i is i/2.

• Array L is used to store node’s labels and array P is used to store the index of node’s

  parent.

• The left child and right child of node i are 2i+1 and 2i+2.

• The left child and right child of node i are 2i+2 and 2i+1.

Answer explanation

In an array-based binary implementation using a perfect binary tree indexing scheme, the left child of a node at index i can be calculated as 2i+1, and the right child can be calculated as 2i+2. This indexing scheme ensures that the nodes are stored in a way that preserves the properties of a binary tree.

Evaluate the following expression:* - + 7 3 + 9 1 5 + 2 8 3? Choose one answer.

• 150

• 105

• 510

• 501