Kingdom of Saudi Arabia
Ministry of Education
Prince Sattam Bin Abdulaziz University وزارة اﻟﺘﻌﻠﯿﻢ
College of Computer ﺟﺎﻣﻌﺔ اﻻﻣﯿﺮ ﺳﻄﺎم ﺑﻦ ﻋﺒﺪ اﻟﻌﺰﯾﺰ
Engineering and sciences ﻛﻠﯿﺔ ھﻨﺪﺳﺔ وﻋﻠﻮم اﻟﺤﺎﺳﺐ
Department of Computer Sciences ﻗﺴﻢ ﻋﻠﻮم اﻟﺤﺎﺳﺐ
Course Title and Code:
Data Structures and Algorithms, CS2321
: اﻟﻄﺎﻟﺒﺔ/اﺳﻢ اﻟﻄﺎﻟﺐ
Second Exam 2
Instructor Name:Dr. Mahdi Khemakhem
Semester I :اﻟﺮﻗﻢ اﻟﺠﺎﻣﻌﻲ
& Mrs Jabeen Hussain
1438/1439
Date: December 14, 2017
:رﻗﻢ اﻟﺸﻌﺒﺔ
Time: 60 minutes
Instructions ﺗﻌﻠﯿﻤﺎت
ﺻﻔﺤﺎت5 ( اﺳﺌﻠﺔ ﻋﻠﻰ4 ) ھﺬا اﻻﺧﺘﺒﺎر ﻣﺆﻟﻒ ﻣﻦ §
§ This exam consists of 4 questions 5 pages. ﺟﺎوب ﻋﻠﻰ ﺟﻤﯿﻊ اﻷﺳﺌﻠﺔ ﻋﻠﻰ ﻧﻔﺲ اﻻوراق §
§ All questions should be answered on the same sheets
§ Electronic devices that could have a memory is not
ﯾﻤﻨﻊ اﺳﺘﻌﻤﺎل اﻻﺟﮭﺰة اﻻﻟﻜﺘﺮوﻧﯿﺔ اﻟﺘﻲ ﺗﺤﺘﻮي ﻋﻠﻰ ذاﻛﺮة §
allowed (ﯾﺴﻤﺢ ﺑﺎﺳﺘﻌﻤﺎل اﻻﻟﺔ اﻟﺤﺎﺳﺒﺔ )دون ذاﻛﺮة §
§ Traditional calculator is allowed .ﯾﺠﺐ اﻻﻟﺘﺰام ﺑﺠﻤﯿﻊ ﻗﻮاﻧﯿﻦ وﻟﻮاﺋﺢ اﻻﻣﺘﺤﺎﻧﺎت §
§ Examination rules must be adhered. ﻻ ﯾﺴﻤﺢ ﺑﺎﻟﻜﺘﺐ أو اﻟﻤﻮاد ذات اﻟﺼﻠﺔ داﺧﻞ ﻏﺮﻓﺔ اﻻﻣﺘﺤﺎن §
§ Books or other related materials are NOT allowed اﻟﻜﺘﺎﺑﺔ ﺗﻜﻮن ﺑﺎﻟﻘﻠﻢ اﻷزرق ﻓﻘﻂ §
§ Use blue pen only
For Official Use Only
First Marking Second Marking
Course Max Obtained Instructor’s Obtained
Question No. Second Signature
Outcome Marks Marks Signature Marks
Q1 CLO#1 5
Q2 CLO#3 3
Q3 CLO#5 4
Q4 CLO#4 3
Total Marks 15
Total Marks in words
1. Dr. Mahdi Khemakhem.
Name of Instructors
2. Mrs. Jabeen Hussain
Name of Peer-Reviewer
Data Structures and Algorithms, CS2321– Second Exam, Semester 1, 2017/2018 Page: 1 of 5
, Q. 1: I need to know the technical words - أﺣﺘﺎج إﻟﻰ ﻣﻌﺮﻓﺔ اﻟﻜﻠﻤﺎت اﻟﺘﻘﻨﯿﺔ (6.5 marks)
@Fill in the blanks using the following words (0.25 for each):
traversal insertion height depth
children length edge O(log N)
pre-order larger deletion sub-trees
O(1) parent smaller binary-heap
leaf balanced left deepest
longest right O(N) sibling
single-rotations double-rotations
1. A tree consists of a distinguished node r (the root), and zero or more nonempty sub-trees 𝑇" , 𝑇$ , … 𝑇& ,
each of whose roots are connected by a directed edge.
2. For every node X, in a binary search tree, all the keys in its left sub-tree are smaller than the key value
in X, and all the keys in its right sub-tree are larger than the key value in X.
3. When the AVL-Tree structure changes (e.g., insertion or deletion), we need to transform the tree to
restore the AVL-Tree property. This is done using single-rotations or double-rotations.
4. The tree traversal is used to print out the data in the tree in a certain order.
5. When we implement a priority queue of size N using unsorted linked list, the insert operation takes
O(1) time and the deleteMin operation takes O(N) time.
6. Pre-order traversal:
a. Print the data at the root.
b. Recursively print out all data in the left sub-tree.
c. Recursively print out all data in the right sub-tree.
7. An AVL-Tree is a balanced binary search tree.
8. When we implement a priority queue of size N using a minimum binary-heap, the insert operation takes
O(log N) time and the deleteMin operation takes O(log N) time.
9. In a tree:
a. The depth of a tree is equal to the depth of the deepest leaf.
b. Every node except the root has one parent.
c. The length of a path is the number of edges on the path.
d. A node can have an arbitrary number of children.
e. The height of a node is equal to the length of the longest path from that node to a leaf.
f. Node with no children is called a leaf.
g. Nodes with same parent are called sibling.
h. The depth of a node is the length of the unique path from the root to that node.
i. The height of a tree is equal to the height of the root.
Data Structures and Algorithms, CS2321– Second Exam, Semester 1, 2017/2018 Page: 2 of 5
Ministry of Education
Prince Sattam Bin Abdulaziz University وزارة اﻟﺘﻌﻠﯿﻢ
College of Computer ﺟﺎﻣﻌﺔ اﻻﻣﯿﺮ ﺳﻄﺎم ﺑﻦ ﻋﺒﺪ اﻟﻌﺰﯾﺰ
Engineering and sciences ﻛﻠﯿﺔ ھﻨﺪﺳﺔ وﻋﻠﻮم اﻟﺤﺎﺳﺐ
Department of Computer Sciences ﻗﺴﻢ ﻋﻠﻮم اﻟﺤﺎﺳﺐ
Course Title and Code:
Data Structures and Algorithms, CS2321
: اﻟﻄﺎﻟﺒﺔ/اﺳﻢ اﻟﻄﺎﻟﺐ
Second Exam 2
Instructor Name:Dr. Mahdi Khemakhem
Semester I :اﻟﺮﻗﻢ اﻟﺠﺎﻣﻌﻲ
& Mrs Jabeen Hussain
1438/1439
Date: December 14, 2017
:رﻗﻢ اﻟﺸﻌﺒﺔ
Time: 60 minutes
Instructions ﺗﻌﻠﯿﻤﺎت
ﺻﻔﺤﺎت5 ( اﺳﺌﻠﺔ ﻋﻠﻰ4 ) ھﺬا اﻻﺧﺘﺒﺎر ﻣﺆﻟﻒ ﻣﻦ §
§ This exam consists of 4 questions 5 pages. ﺟﺎوب ﻋﻠﻰ ﺟﻤﯿﻊ اﻷﺳﺌﻠﺔ ﻋﻠﻰ ﻧﻔﺲ اﻻوراق §
§ All questions should be answered on the same sheets
§ Electronic devices that could have a memory is not
ﯾﻤﻨﻊ اﺳﺘﻌﻤﺎل اﻻﺟﮭﺰة اﻻﻟﻜﺘﺮوﻧﯿﺔ اﻟﺘﻲ ﺗﺤﺘﻮي ﻋﻠﻰ ذاﻛﺮة §
allowed (ﯾﺴﻤﺢ ﺑﺎﺳﺘﻌﻤﺎل اﻻﻟﺔ اﻟﺤﺎﺳﺒﺔ )دون ذاﻛﺮة §
§ Traditional calculator is allowed .ﯾﺠﺐ اﻻﻟﺘﺰام ﺑﺠﻤﯿﻊ ﻗﻮاﻧﯿﻦ وﻟﻮاﺋﺢ اﻻﻣﺘﺤﺎﻧﺎت §
§ Examination rules must be adhered. ﻻ ﯾﺴﻤﺢ ﺑﺎﻟﻜﺘﺐ أو اﻟﻤﻮاد ذات اﻟﺼﻠﺔ داﺧﻞ ﻏﺮﻓﺔ اﻻﻣﺘﺤﺎن §
§ Books or other related materials are NOT allowed اﻟﻜﺘﺎﺑﺔ ﺗﻜﻮن ﺑﺎﻟﻘﻠﻢ اﻷزرق ﻓﻘﻂ §
§ Use blue pen only
For Official Use Only
First Marking Second Marking
Course Max Obtained Instructor’s Obtained
Question No. Second Signature
Outcome Marks Marks Signature Marks
Q1 CLO#1 5
Q2 CLO#3 3
Q3 CLO#5 4
Q4 CLO#4 3
Total Marks 15
Total Marks in words
1. Dr. Mahdi Khemakhem.
Name of Instructors
2. Mrs. Jabeen Hussain
Name of Peer-Reviewer
Data Structures and Algorithms, CS2321– Second Exam, Semester 1, 2017/2018 Page: 1 of 5
, Q. 1: I need to know the technical words - أﺣﺘﺎج إﻟﻰ ﻣﻌﺮﻓﺔ اﻟﻜﻠﻤﺎت اﻟﺘﻘﻨﯿﺔ (6.5 marks)
@Fill in the blanks using the following words (0.25 for each):
traversal insertion height depth
children length edge O(log N)
pre-order larger deletion sub-trees
O(1) parent smaller binary-heap
leaf balanced left deepest
longest right O(N) sibling
single-rotations double-rotations
1. A tree consists of a distinguished node r (the root), and zero or more nonempty sub-trees 𝑇" , 𝑇$ , … 𝑇& ,
each of whose roots are connected by a directed edge.
2. For every node X, in a binary search tree, all the keys in its left sub-tree are smaller than the key value
in X, and all the keys in its right sub-tree are larger than the key value in X.
3. When the AVL-Tree structure changes (e.g., insertion or deletion), we need to transform the tree to
restore the AVL-Tree property. This is done using single-rotations or double-rotations.
4. The tree traversal is used to print out the data in the tree in a certain order.
5. When we implement a priority queue of size N using unsorted linked list, the insert operation takes
O(1) time and the deleteMin operation takes O(N) time.
6. Pre-order traversal:
a. Print the data at the root.
b. Recursively print out all data in the left sub-tree.
c. Recursively print out all data in the right sub-tree.
7. An AVL-Tree is a balanced binary search tree.
8. When we implement a priority queue of size N using a minimum binary-heap, the insert operation takes
O(log N) time and the deleteMin operation takes O(log N) time.
9. In a tree:
a. The depth of a tree is equal to the depth of the deepest leaf.
b. Every node except the root has one parent.
c. The length of a path is the number of edges on the path.
d. A node can have an arbitrary number of children.
e. The height of a node is equal to the length of the longest path from that node to a leaf.
f. Node with no children is called a leaf.
g. Nodes with same parent are called sibling.
h. The depth of a node is the length of the unique path from the root to that node.
i. The height of a tree is equal to the height of the root.
Data Structures and Algorithms, CS2321– Second Exam, Semester 1, 2017/2018 Page: 2 of 5
