Q.1) The key technique in dynamic-programming [algorithm] to store the solution to each subproblem in case it should reappear.
Group of answer choices
True
False
Q.2) True or false:
Dynamic programming is a kind of greedy algorithm?
Group of answer choices
True
False
Q.3) True or false:
Dynamic programming works best when solutions to subproblems can be memorized.
.
Group of answer choices
True
False
Q.4) Traveling Salesman Problem is a problem whose objective is to find the longest possible route that visits each city exactly once and returns to the starting city.
Group of answer choices
True
False
Q.5) Weight – A number assigned to an edge of a graph as a way of representing a cost, time, distance, etc. associated with traveling that edge.
.
Group of answer choices
True
False
Q.6) What is the output [result] of the algorithm below:
1 def fib_rec(n):
2 if n == 1:
3 return [0]
4 elif n == 2:
5 return [0,1]
6 else:
7 x = fib_rec(n-1)
8 # the new element the sum of the last two elements
9 x.append(sum(x[:-3:-1]))
10 return x
11 x=fib_rec(5)
12 print(x)
0, 1, 1, 2, 3,
1, 1, 2, 3, 4
0, 0, 1, 1, 2, 2, 3, 3
Q.7) Divide-and-conquer algorithms – The algorithms partition the problem into separate subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem.
–
Group of answer choices
True
False
Q.8) True or false:
Dynamic programming works best when solutions to subproblems can be memoized.
Group of answer choices
True
False
Q.9) Sort the list below using LSD Radix sort.
1347, 1610, 162, 1300, 733, 62, 4, 1688, 2254, 1347, 860, 1647, 1600, 1444
Show all work – Details please.
Q.10) Sort the list below using MSD Radix sort.
1347, 1610, 162, 1300, 733, 62, 4, 1688, 2254, 1347, 860, 1647, 1600, 1444
Show all work – Details please.
Q.11) Your given the compressed files and the table below. What is the message in the file?
01001001101011010110010111010011110111101000000101111010011100111010000101101100010001011001110111000001001001100111111011101111101100101101111010001011011110100010110000101111011101111101001110011101000101101111011000001100110001110011000111
Q,12) The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 6 are ….
Group of answer choices
128 and 8, respectively
128 and 7, respectively
127 and 6, respectively
127 and 7, respectively
Q.13) Which of the following sequences represents the post order traversal sequence of the given tree below?
a
/
b e
/ /
c d f
/
g
Group of answer choices
g c b d a f e
g c d b f e a
f e d g c b a
f e g c d b a
Q.14) Which of the following statement is true about Binary Trees
A Every binary tree is either complete or full.
B Every complete binary tree is also a full binary tree.
C Every full binary tree is also a complete binary tree.
D No binary tree is both complete and full.
E None of these answers are true.
Group of answer choices
E
A
B
D
C
Q.15) What is a full binary tree?
Group of answer choices
All nodes have exactly two children
Each node has exactly zero or two children
All the leaves are at the same level
A tree In which all nodes have degree 3
Q.16) TRUE/FALSE
In a binary search tree, a new element is always added as a leaf.
Group of answer choices
True
False
Q.17) The number of edges from the root to the node is called ______________ of the tree.
Group of answer choices
Circumference C= 2πR
Depth
Width
Length
Height
Q.18) In a full binary tree if there are L leaves, then total number of nodes N is derived by the formula _________________________.
Group of answer choices
N = 2*L – 1
N = 2*L
N= n log n
N = L – 1
Q.19) FILL IN THE BLANK
A ___________ is a complete binary tree in which each element is greater than or equal to both of its children.
Q.20) FILL IN THE BLANK
A binary search tree that is highly unbalanced is called a ___________ tree.
Q.21) Match the following definitions of a binary tree….
Group of answer choices
Directed Edge
Root Node
Leaf Node
Depth
Level
Height
Q.22) Research Question:
- What is Counting Sort? (4)
- Write the pseudocode for counting sort. (8)
- What is the worst case for counting sort? (4)
- Use counting sort, sort the following items. (24)
2, 3, 1, 4, 1, 7, 8, 1, 2, 2, 3, 9, 1, 7, 1
Show all work – full diagrams.
0 comments