EECE7205_Exam1 Review Questions
pdf
keyboard_arrow_up
School
Northeastern University *
*We aren’t endorsed by this school
Course
7205
Subject
Electrical Engineering
Date
Apr 3, 2024
Type
Pages
4
Uploaded by BaronSummer2048
Page 1
of 4
Northeastern University College of Engineering Department of Electrical & Computer Engineering EECE7205: Fundamentals of Computer Engineering First Midterm Exam Review Questions
For questions Q1
to Q17 choose the best
answer. Make a circle around your letter choice. Q1. In the shown INSERTION-SORT algorithm, to sort list
A
into a decreasing instead of an increasing order, the following change(s) is(are) needed: a. Step 4: i
= j
+1
b. Step 5: while i
> 0 and A
[
i
] < key
c. Step 7: i
= i
+ 1
d. All of the above. Q2. For the INSERTION-SORT algorithm in the previous question. Assume list A has ten
elements and it is already sorted. How many actual lines of code will be executed? a. 45 b. 46 c. 70 d. 80 Q3. The linear search algorithm checks every element in a list sequentially until the desired element is found. If the algorithm is applied on a list of n
elements, then its asymptotic worst and best running times are: a. Θ
(
n
2
) and Θ
(
n
) b. Θ
(2
n
) and Θ
(
n
) c. Θ
(
n
) and Θ
(1) d. None of the above. Q4. Assume f
(
n
) = 2
n
and g
(
n
) = 2
n
/2
, then the following is true: a. f
(
n
) =
Θ
(
g
(
n
))
b. f
(
n
) =
O
(
g
(
n
))
c. f
(
n
) =
Ω
(
g
(
n
))
d. All of the above. Q5. What are the minimum and maximum numbers of elements in a heap of height h
? a. 2
h
and 2
h
+1
- 1
b. 2
h
- 1
and 2
h
+1
c. 2
h-
1
and 2
h
- 1
d. None of the above. Q6. Is the heap represented by an array with values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] a max-heap? a.
Yes
b. No Q7. What are the leaves of the heap represented by an array with values: [23, 17, 14, 6, 13, 10, 1, 5, 7, 12]? a. [5, 7, 12] b. [7, 12] c. [1, 5, 7, 12] d. [10, 1, 5, 7, 12] Q8. A heap is represented by an array with values A
= [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]. The following will be the contents of A
after applying the operation of MAX-HEAPIFY(
A
, 3)
. a. [27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0] b. [27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0] c. [27, 17, 16, 3, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0] d. None of the above
Page 2
of 4
Q9. What is the running time of the HEAPSORT algorithm on an array A
of length n
that is already sorted? a. Θ
(
n
) b. Θ
(
n
lg n
) c. Θ
(lg n
) d. None of the above. Q10. What is the running time of the HEAPSORT algorithm on an array A
of length n
that is initially in reverse sorted order? a. Θ
(
n
) b. Θ
(
n
lg n
) c. Θ
(lg n
) d. None of the above. Q11. Assume an initially empty stack S
stored in array S
[1 .. 6] and the top of the stack is initially S
[1]. What will be the content of S
after the following operations in the sequence PUSH(S,4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S)? a. [4, 1, 3, 8] b. [8, 3, 1, 4] c. [4, 1] d. [3, 8] Q12. Assume an initially empty queue Q
stored in array Q
[1 .. 6] and both its head and tail are pointing to Q
[1]. What will be the content of Q
after the following operations in the sequence ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8), and DEQUEUE(Q)? a. [4, 1, 3, 8] b. [8, 3, 1, 4] c. [4, 1] d. [3, 8] Q13. For hashing by the division method, which of the following is the best choice for the modulus m
? a. 256 b. 181 c. 128 d. 10 Q14. Given a hash table with size m
= 13 and starting index 0
, and a hash function h
(
k
) = k
mod m
. For
k
= 25
, state the hash position (home slot) and the following three positions if linear probing is used for collision resolution. a. 12, 13, 14, 15 b. 11, 12, 13, 14 c. 12, 0, 1, 2 d. 11, 12, 0, 1 Q15. Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not
be the sequence of nodes examined? a.
2, 252, 401, 398, 330, 344, 397, 363.
b.
924, 220, 911, 244, 898, 258, 362, 363.
c.
925, 202, 911, 240, 912, 245, 363.
d.
2, 399, 387, 219, 266, 382, 381, 278, 363.
e.
935, 278, 347, 621, 299, 392, 358, 363.
Q16. What is the maximum number of keys that can be stored in a B-tree of height 2 and minimum degree 3? a. 24 b. 35 c. 124
d. 215 Q17. For a B-tree with a minimum degree 3,
what is its possible maximum height to store 17 keys? a. 2 b. 3 c. 4
d. 5 End of multiple-choice questions
Page 3
of 4
Q18.
Solve the following recurrence equations to find the big O
asymptotic notation of the running time as a function of n
: a)
T(n) = T(n-1) + n , and T(1) = 1 b)
T(n) = T(n/2) + c, and T(1) = c (assume that n
= 2
k
for a positive integer k
) Q19. Rewrite the shown ENQUEUE and DEQUEUE algorithms to detect underflow and overflow of a queue. Make any necessary assumptions. Q20. Answer the following questions about the Quicksort algorithm: a)
Illustrate the operation of PARTITION on the array A
= (13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11) b)
How would you modify QUICKSORT to sort into decreasing order? c)
Can we replace the previous QUICKSORT pseudo code with the following TAIL-RECURSIVE pseudo code, which has one recursive call within a loop? Explain why.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Page 4
of 4
Q21. Answer the following questions about the Binary Search trees:
a)
Without drawing any trees, what are the minimum and maximum heights of binary trees with 63 nodes. b)
Starting from an empty binary search tree (BST), draw the tree after inserting the following values in the order given (from left to right). M, H, D, A, G, K, L, T, R, W, V, U
c)
On the same BST you created in part (b), add the following values B
then
C
d)
Redraw the BST you have from part (c) after removing the following values: G
K
M
(in this order) Q22. Show the results of deleting C, P, and V , in order, from the following B-Tree that has a minimum degree t
= 3: End of the Review Questions
Related Documents
Related Questions
Design a code converter that converts a decimal digit from
BCD to excess-3 code, the input variables are organized as
(A BC D) respectively with A is the MSB, the output
variables are organized as (W XY Z) respectively with W is
the MSB, put the invalid decimal numbers as don't care.
X= BCD'+B'D+B'C
X= BC'D'+B'D+BC
X= BC'D'+B'D+B'C
X= BC'D'+BD+B'C
arrow_forward
Design a code converter that converts a decimal
digit from BCD to excess-3 code, the input variables
are organized as (A B C D) respectively with A is the
MSB, the output variables are organized as (W XY
Z) respectively with W is the MSB, put the invalid
decimal numbers as don't care.
W=A+BD+BC'
W=A+BD+BC,
W=A'+BD+BC
W= BC'D'+B'D+B'C
arrow_forward
1. An arithmetic system operates with 3-digit decimal numbers with sign presented in BCD (12 bits),
negative numbers utilize the 10's complement form, one decimal digit (4 bits) is occupied by sign: 0 for
"+" and 9 for "-".
1a) Show the most positive and the most negative numbers in both decimal and BCD forms.
1b) Present numbers A=+36 and B= -42 in BCD.
1c) Present the 10's complements of A and B in BCD.
1d) Perform the following operations bit-by-bit, show carries, apply BCD correction (add 6) when
necessary (the sum of two decimal digits is greater than 9).
1d1) A+B in BCD.
1d2) A - B = A+(-B) in BCD by addition of A and the 10's complement of B.
1d3) B-A= B + (-A) in BCD by addition of B and the 10's complement of A.
arrow_forward
Signed integers are represented in two's complementary formats. Does the same
arithmetic hardware (or algorithm) work exactly the same between
a. Unsigned addition and signed addition?
b. Unsigned subtraction and signed subtraction?
c. Unsigned multiplication and signed multiplication(if the product obtained
the same length as the operands)?
d. Unsigned division and signed division?
Please give your answer as "true" or "false" for the above 4 questions.
arrow_forward
1) Here is a Digital Logic question on analysis of clocked sequential circuits with the answer. Please explain what the teacher did and why they did it. I need you to explain how they got the answer.
arrow_forward
| Solve all parts. Will give thumb's up|
If you can't do all please don't attempt the questions.
arrow_forward
Needs Complete solution with 100 % accuracy.
arrow_forward
Please help me to do this
arrow_forward
QUESTION 8
(NEED A NEAT HAND WRITING SOLUTION ONLY OTHERWISE WILL LEAVE A DOWNVOTE)
arrow_forward
Moving to the next question prevents changes to this answer.
Question 2
What are the two most common methods of PLD design entry?
logic simulator and AND gates
O logic simulator and design entry
design entry and schematic entry
O schematic entry and AND gates
arrow_forward
design a two-way traffic light system with prototype using 4-bit down counter circuit. use 7-segment as an output to represent the timer.i need help.. pls make a circuit diagram for this. i will do this on the breadboardand also explain how u did it. thank youthe photo attached is how i will do it
arrow_forward
SEE MORE QUESTIONS
Recommended textbooks for you
Power System Analysis and Design (MindTap Course ...
Electrical Engineering
ISBN:9781305632134
Author:J. Duncan Glover, Thomas Overbye, Mulukutla S. Sarma
Publisher:Cengage Learning
Related Questions
- Design a code converter that converts a decimal digit from BCD to excess-3 code, the input variables are organized as (A BC D) respectively with A is the MSB, the output variables are organized as (W XY Z) respectively with W is the MSB, put the invalid decimal numbers as don't care. X= BCD'+B'D+B'C X= BC'D'+B'D+BC X= BC'D'+B'D+B'C X= BC'D'+BD+B'Carrow_forwardDesign a code converter that converts a decimal digit from BCD to excess-3 code, the input variables are organized as (A B C D) respectively with A is the MSB, the output variables are organized as (W XY Z) respectively with W is the MSB, put the invalid decimal numbers as don't care. W=A+BD+BC' W=A+BD+BC, W=A'+BD+BC W= BC'D'+B'D+B'Carrow_forward1. An arithmetic system operates with 3-digit decimal numbers with sign presented in BCD (12 bits), negative numbers utilize the 10's complement form, one decimal digit (4 bits) is occupied by sign: 0 for "+" and 9 for "-". 1a) Show the most positive and the most negative numbers in both decimal and BCD forms. 1b) Present numbers A=+36 and B= -42 in BCD. 1c) Present the 10's complements of A and B in BCD. 1d) Perform the following operations bit-by-bit, show carries, apply BCD correction (add 6) when necessary (the sum of two decimal digits is greater than 9). 1d1) A+B in BCD. 1d2) A - B = A+(-B) in BCD by addition of A and the 10's complement of B. 1d3) B-A= B + (-A) in BCD by addition of B and the 10's complement of A.arrow_forward
- Signed integers are represented in two's complementary formats. Does the same arithmetic hardware (or algorithm) work exactly the same between a. Unsigned addition and signed addition? b. Unsigned subtraction and signed subtraction? c. Unsigned multiplication and signed multiplication(if the product obtained the same length as the operands)? d. Unsigned division and signed division? Please give your answer as "true" or "false" for the above 4 questions.arrow_forward1) Here is a Digital Logic question on analysis of clocked sequential circuits with the answer. Please explain what the teacher did and why they did it. I need you to explain how they got the answer.arrow_forward| Solve all parts. Will give thumb's up| If you can't do all please don't attempt the questions.arrow_forward
- Moving to the next question prevents changes to this answer. Question 2 What are the two most common methods of PLD design entry? logic simulator and AND gates O logic simulator and design entry design entry and schematic entry O schematic entry and AND gatesarrow_forwarddesign a two-way traffic light system with prototype using 4-bit down counter circuit. use 7-segment as an output to represent the timer.i need help.. pls make a circuit diagram for this. i will do this on the breadboardand also explain how u did it. thank youthe photo attached is how i will do itarrow_forward
arrow_back_ios
arrow_forward_ios
Recommended textbooks for you
- Power System Analysis and Design (MindTap Course ...Electrical EngineeringISBN:9781305632134Author:J. Duncan Glover, Thomas Overbye, Mulukutla S. SarmaPublisher:Cengage Learning
Power System Analysis and Design (MindTap Course ...
Electrical Engineering
ISBN:9781305632134
Author:J. Duncan Glover, Thomas Overbye, Mulukutla S. Sarma
Publisher:Cengage Learning