Scribd
Upload
135 views2 pages

Date: - 01 - 2021: Final Examination Fall 2020

This document contains details of a final exam for a Data Structures and Algorithms course including: 1. Three questions in Section A worth 15 marks testing graph representations, binary trees, and quicksort vs mergesort algorithms. 2. Two questions in Section B worth 15 marks testing hash table capacities, AVL tree insertion order, and breadth-first search (BFS) and depth-first search (DFS) vertex ordering on a sample graph starting from vertex G.

Uploaded by

Noman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
135 views2 pages

Date: - 01 - 2021: Final Examination Fall 2020

This document contains details of a final exam for a Data Structures and Algorithms course including: 1. Three questions in Section A worth 15 marks testing graph representations, binary trees, and quicksort vs mergesort algorithms. 2. Two questions in Section B worth 15 marks testing hash table capacities, AVL tree insertion order, and breadth-first search (BFS) and depth-first search (DFS) vertex ordering on a sample graph starting from vertex G.

Uploaded by

Noman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Reg.

No: Final Examination Fall 2020 Date: - -01 -2021


_______________
Program: BSC Class & Section: 3B

Course Name: Data structures and Algorithms Duration: 2 Hours

Instructor Name: Dr. Isma Masood Total Marks: 30

Section A: Attempt all Questions (3*5=15 Marks )


1. Draw the directed graph that corresponds to this adjacency matrix:

0 1 2 3
0 | true false true false |
1 | true false false false |
2 | false false false true |
3 | true false true false |
2. Draw a binary taxonomy tree that can be used for these four animals: Rabbit,
Horse, Whale, Snake.
3. Compare the quick-sort and merge-sort algorithms in terms of their time and
space complexity. Which is better in terms of time complexity? Which is better in
terms of space complexity?

Section B: Attempt all Questions (7.5*2=15 Marks )


1. a. Suppose that the universe U of possible keys is {0, 1, . . . , n2 − 1}. For a hash
table of size n, what is the greatest number of distinct keys the table can hold with
each of these collision resolution strategies? 1)Chaining and 2) Linear probing.
b. What order should we insert the elements {1, 2, . . . , 7} into an empty AVL
tree so that we don’t have to perform any rotations on it?
3. Given the following graph

For the following problems, assume alphabetical edge order


I. Write (in order) the list of vertices that would be visited by running a
breadth-first search (BFS) starting from G.
II. Write (in order) the list of vertices that would be visited by running a
depth-first search (DFS) starting from G.

You might also like