CS 2150 Final Exam, fall 2020 for mst3k (27 questions, 102 total points)
Exam time has ended; no answer changes will be recorded.
Progress: N/A

READ THIS: This page is an example of a final exam given at the end of the fall 2020 semester. Students had different questions -- either different values for some of them (the coding questions or graph questions), entirely different questions entirely (for the multiple choice questions), etc. It's not feasible to provide all 500 exams given in the fall 2020 semester, and what is here is meant to give students an idea of the format that the current semester's final exam will be in, and an example of the types of questions that might be asked. There will be all different questions this semester, though.
 
A week or two before the final exam, all students will be provided with a sample exam to test out this exam system. In particular, all the questions are auto-graded, and if the formatting the fill-in answers is not exactly what is expected, it will be marked wrong. To help with this, the exam system provides the answer validation -- it ensures that the answer is in the right format; whether the answer is correct or not is a separate issue. This validation is what the 'answer color codes' box, below, is referring to. Students will be able to test-drive this exam system, and understand the the answer validation aspect, about a week or two prior to taking the actual final exam. More explanation about the answer formats and answer validation will be available then.

Question types
Multiple choice
A
B
C
D
E
1 correct
answer
True/false
True
False
1 correct
answer
Multiple answer
A
B
C
D
E
2+ correct
answers
Numerical fill-in
Must be a
number
Text fill-in
Question specific
format

Answer color codes
The answer is bordered by a black line for each question.
The background color of the answer indicates it's status:
 
White means an answer has not yet been entered or it is blank
Yellow means an answer has been entered but not yet auto-saved
Blue means the answer has been entered and also auto-saved
Red means there is an error with the formatting of the answer

CS 2150 Final Exam, fall 2020 for mst3k (27 questions, 102 total points)

Introduction

This is the final exam for CS 2150, fall 2020. The question types are shown above. Note that you can tell multiple choice from multiple answer based on the shape of the buttons (circles or squares), as shown above. The background color of the answers will color themselves to indicate the saved or error status; these colors are described above. Note that fill-in questions, both numeric and text, have very specific formats that the exam will check.

There is a save button at the bottom of this page, and it auto-saves every 30 seconds.

Good luck on the exam!

Question 1. (3 points): C++ question

Where in your C++ code would you see int* num?

in a variable declaration

when dereferencing a pointer

in a function header / prototype

in a mathematical formula


Question 2. (3 points): C++ question

Suppose we have come up with a new data type called: mint (short for mini int). Mints represent 24 bit signed integers. Perfect for those moments when ints are too long are shorts are too short. What would the following theoretical code snippet print out to the console? (You may use a calculator -- online or otherwise -- to determine a power of 2 for this question)

Q6

-8388602

8388602

8388604

-8388604


Question 3. (3 points): C++ question -- swap.cpp

Consider the swap function below. If a and b are both passed to swap(), what will the contents of the variable that a points to be after the function returns? The answer is an integer.

code



Question 4. (6 points): C++ question -- VectorResize.cpp

Consider the custom vector shown below (not everything is shown to you) with the resize method provided. If the code segment at the bottom is executed, list out the size, capacity, and value at index size/2 of this vector (space separated, see example in comments below).

code



Question 5. (6 points): C++ question -- LLInsert.cpp

Consider a singly-linked list with a pointer to a head node (NO dummy node); the head node is initially set to nullptr. Given the insertAtHead() method below (which may contain bugs), what would the following code segment print? If the program produces no output, write "no output" (without the quotes).

code



Question 6. (3 points): List question

Why would you ever want to use a singly linked list over a doubly linked list?

Faster look-up times

Doubly linked lists are always better

When you are heavily constrained for memory

When you are implementing a Huffman tree

When you only need to access one end of the list

When you are implementing a postfix tree


Question 7. (3 points): List question

Assume a linked list implementation the same as Lab 2. What is wrong with this implementation of insertAtTail()?

Q13

The pointers are set incorrectly

The new node is statically allocated, possibly causing future errors

There is nothing wrong

The the node is missing "this" before "tail"

The pointers are set in the wrong order, causing some to be set incorrectly


Question 8. (3 points): Numbers question binary -> octal

Consider the two binary values 011010 and 110010 (these are just regular binary values, not two's complement binary values). Add them together, and convert the result to octal (base 8). Your answer should just be the octal digits of the number; no leading '0' digits.



Question 9. (3 points): Numbers question -- largest value in a base

What is the largest possible value that a 3 digit number in base 7 can hold? Put your answer in base 10.



Question 10. (6 points): Numbers question -- minimum negative float

Consider a new floating point format with 14 mantissa bits, 7 exponent bits, and 1 sign bit, for a total of 22 bits. The 10 remaining bits (the least significant bits) in the 32-bit word should all be 0 bits. Other than the size of the exponent and mantissa, it encodes the same way as what we studied in class (although with a different exponent offset (aka exponent bias)). Find the big-Endian 32-bit hex corresponding to the minimum negative value (meaning the negative value with the smallest absolute value). Your answer should be in the format "0x12345678"; use lower case for hex digits a-f.



Question 11. (3 points): Numbers question -- valid number in base

Is 111 a valid number in base 6?

True

False


Question 12. (3 points): Arrays question -- integer memory location

The following (4 byte) 2-D integer array starts at 0x30: {{77, 98, 51, 1}, {81, 29, 20, 15}, {14, 68, 6, 32}, {58, 11, 8, 69}}. What is the memory address of the value 32? (if 32 appears multiple times, then the address of the first occurrence)

0x58

0x60

0x54

0x50

0x5c


Question 13. (3 points): big-Oh question -- is F big-Oh of G

Is f(n) = equation big-OH of g(n) = equation?

True

False


Question 14. (3 points): Big-Oh question

What is the runtime of the x86 code snippet below? Assume the input is passed into rdi and rsi.

Q7

Linear

Logarithmic

LogLinear

Quadratic


Question 15. (3 points): Trees question -- AVL tree rotations

Consider the following AVL tree:

avl tree

What type of rotation would be performed, if any, when 14 is inserted?

Single left

Single right

Double (right first, then left)

Double (left first, then right)

None


Question 16. (3 points): Trees question -- traversals

Given the following tree:

What is the postorder traversal of this tree? Your answer must be in a space-separated list of the values, such as "A B C D E F G H I J". The letters must be capitalized.



Question 17. (6 points): Hashes question -- insertion

Assume a hash table that uses quadratic probing has a size of 10 with the hash funtion of h(x) = x * 6 + 3. What is the resultant hash table after inserting the following integer values: [4, 9, 3, 7, 0, 6, 2]? There will not be any rehashing with the inserting of those values. Your answer must be in a space-separated list of the values in the hash table array of size 10 with '#' for an empty cell. For example: "1 # 2 # 3 # 4 # 5 # 6" (without the quotes, of course).



Question 18. (3 points): Assembly question

What is the result of the recursive code shown below? Assume the function prototype is int recur(int x);? Note that the formuals in the answers use the floor (⌊⌋) and ceiling (⌈⌉) functions, and the log functions in the answers are all base 2..

Q12

⌊ log (x) ⌋

⌈ log (x) ⌉

⌈ x / 2 ⌉

1 + x / 2

None of the above


Question 19. (3 points): Assembly question

Which of the following properly reads a value from an array with the base address in rdx and the index in rcx into the register rax? Assume the array elements are 8 bytes in size.

mov rax, [rdx + rcx*4]

mov rax, [rdx*rcx + 4]

mov rax, [edx + rcx*4]

mov rax, [rdx + rcx*4]

mov rax, [rdx + rcx*8]


Question 20. (6 points): Assembly question -- mysteryFunc()

Consider the _mysteryFunc assembly function below. This function takes in an array and a size of that array as parameters. List the contents of the array (space separated) after the function returns on the input below. The input below is the size of the array, followed by the initial contents of the array.

Array: 3 2 6 4 6 (size: 5)

Code


Question 21. (3 points): Heaps / Huffman question

How does the asymptotic complexity analysis (i.e., big-Theta analysis) change in a min heap if it is implemented via an array versus using dynamic memory with HeapNodes (or equivalent)? Consider the operations insert(), 'findMin(), anddeleteMin()`.

all array-based operations are slower than node-based operations

all operations have the same runtime

all array-based operations are faster than node-based operations

some array-based operations are faster as node-based, while other array-based operations are slower than node-based operations

some array-based operations have the same runtime as node-based, while some array-based operations others are slower than the node-based operations

some array-based operations have the same runtime as node-based, while some array-based operations others are faster than the node-based operations


Question 22. (6 points): Heaps / Huffman question -- encoding

Consider the following Huffman coding tree:

huffman tree

Encode 'baby yoda' using this tree. Note that left is 0 and right is 1. Your answer should only include the digits 0 and 1; do NOT include any other characters, such as spaces. Note that each node in the tree shows the character (if not an internal node) and the frequency.



Question 23. (3 points): Heaps / Huffman question -- is heap valid

Heaps are typically stored in arrays or vectors, with the 0th index discarded. Is the following vector representation a valid min-heap stored this way? ['-', 5, 7, 18, 9, 16, 16]

True

False


Question 24. (6 points): Graphs question -- MST

Consider the graph shown in the two images below:

graph graph

The first image shows the weights of the edges, and the second image shows the letter names of the edges. The answer will need to use the letter names of the edges (i.e., the letters A-L).

Compute the minimum spanning tree using either algorithm discussed in class. Your answer is to be a space-separated list of the edges in the MST, and must a be of the form "A B C D" (without the quotes); edge letters should be captialized. However, the order of your edges in the minimum spanning tree MUST BE SORTED alphabetically (so "A C B" would not be the correct format, but "A B C" would be).



Question 25. (6 points): Graphs question -- Dijkstra's

Consider the following graph:

graph

Perform Dijkstra's shortest path algorithm on this graph, starting at vertex 1. In Dijkstra's, all vertices start with infinite distance, and are updated throughout the running of the algorithm; all vertices are updated at least once (from infinity to a finite value). Which of the vertices has their shortest distances updated more than once during the running Dijkstra's algorithm?

vertex v0

vertex v1

vertex v2

vertex v3

vertex v4

vertex v5

vertex v6


Question 26. (3 points): Memory question

There are multiple variables in a program that are never used. What will likely happen when the compiler compiles the code?

The compiler optimizes out the unused variables and will not compile

The compiler optimizes out the unused variables and will compile

The compiler will compile the code without modification and will compile

The compiler will compile the code without modification and will compile


Question 27. (0 points): Comments

Any other comments or issues with this exam? Such as unreadable diagrams, problems you encountered, etc. If none, just put "none" or "N/A" in the box below.