(5/5)

need help with this

**NAME **CS110 Review Guide Worth 1 quiz Grade

Date________________

Q1. How many comparisons are required to search the following names using binary search and sequential search in the following list of names

Q1 IS TO BE TAUGHT ON MONDAY

Aaron

Cinthia

Don

Eric

Gerald

Harry

Holly

Kevin

Luna

Melissa

Molly

Neil

Pamela

Tim

Venus

__NUMBER OF COMPARISIONS__

** BINARY SEARCH SEQUENTIAL SEARCH**

- Aaron

- Kevin

- Eric

- Krish

- Neil

- Melissa

- Patricia

- Venus

Q2a. **Print the messages** that the following program prints. Also **provide the values for A, B, C and D** after the following piece of code is executed.

* *

*A= 3*

*B=9*

*C=11*

*D=19*

* *

* *

*if ( A>B)*

* print “Don’t mess with A”*

*else*

* print “B might be the greatest”*

* *

*if (A > B )*

* C = A –B*

* *

*else*

* C = A + B*

*D = C +1*

Q2b. What are the values of the variables **x** **and count** after the loop is executed.

* *

*x=1*

*count = 2*

*while ( count < 5 ) *

* *

* x = x + 3*

* count = count +1*

Q2c. What gets printed after the following segment of code is executed?

*x=2*

*while (x < 5 )*

* x = 2 *x +1*

* *

*print “Value of x is “, x*

Q3. Consider the following code segment and indicate what gets printed.

a.)

*i = 5*

*j= 6*

*k = 7*

* *

*if (i < j ) and (k < 5 )*

* print “YES”*

*else*

* print “NO”*

b. )

* *

*i= 5*

*j = 6*

*k=7*

* *

*if (i < j) or (k < 5 )*

* print “YES”*

*else*

* print “NO”*

Q4. The following code segment has a function definition and a function call from the main program. Indicate where the following are in the code

.

*def rectangle_area (length , width )*

* area = 0*

* area = length * width*

* *

* *

* *

*print “ Program to compute the area of a rectangle “*

*rectangle_area(20,25)*

- function definition
- function call
- formal parameters
- actual parameters.

* *

* *

*def rectangle_area (length , width )*

* area = 0*

* area = length * width*

* *

* *

* *

* print “ Program to compute the area of a rectangle “*

* rectangle_area(20,25)*

e. Does the procedure print the values after calculating the area? If it doesn’t then add the code to print the value of area of the rectangle inside the procedure.

f. Indicate what changes need to be made if the procedure needs to be modified to return a value to the main program so that the area can be printed in the main program.

Q5. The procedure **modify** is defined by

*def modify ( y)*

* *

* y = 10*

* print” the value of y is “, y*

a. If parameters are passed by value, what values of x and y will be printed when the following program segment is executed?

*def modify ( y)*

* *

* y = 10*

* print” the value of y is “, y*

* *

*x = 15*

*modify ( x )*

*print “the value of x is “, x.*

b. If the procedure modify is changed to

* *

*def modify ( y )*

* y = 10*

* print “the value of y is”, y*

* return y*

What values of x and y variables gets printed when the following program is executed?

*def modify ( y)*

* *

* y = 10*

* print” the value of y is “, y*

* return y*

* *

* *

*x = 15*

*x = modify ( x )*

*print “the value of x is “, x*

* *

Q6. Suppose the memory cells at addresses F0 through FD in the machine

described in Appendix C contain the following bit patterns:

Address Content

A0 10

A1 A9

A2 21

A3 00

A4 22

A5 03

A6 53

A7 01

A8 54

A9 23

AA 34

AB AF

AC C0

AD 00

Assume that the machine starts with program counter equal to A0.

a. What will be the contents in the following registers when the machine halts?

Register 0= _____ , Register 1= _____ ,Register 2= _____ ,

Register 3= _____ , Register 4=_____.

- What will be in memory location AF when the machine halts?

c. What will be in PC when the machine halts?

Q7. Suppose the memory cells at addresses 00 through 05 in the machine contain the following bit patterns.

Address Content

00 10

01 06

02 30

03 45

04 C0

05 00

06 34

What bit pattern is in the memory cell at address 45 when the machine halts.

What bit pattern is in the program counter when the machine halts?

Q8.

a. There are three algorithms of the order O(n), O(n^{2} ) and O(n3 ). Which of these algorithm will be fastest with the least number of comparisons and which one will be the slowest?

b. Give one example of algorithms of order

O(n^{2})

O(n)

O(logn)

c. Perform the following binary additions.

10101011

__+ 01011110 __

- What base 10 numbers are represented by the following two’s complement representations?

- 11010

- 1110001

e. How many possible memory addresses can you generate with 7 bits?

- How many bits can be stored in a memory space of 200 bytes?

** **

** **

** **

** **

** **

** **

** **

** **

** **

**Q9. Considering the node pointed to by the root in the binary search tree is 50, answer the following problems.**

** **

** **

**Construct a tree by adding following values in the order in which they appear**

**50,45,70,40,30,48,60,75**

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

**a. Indicate what positions do the keys 25, 65 and 49 will go in the above tree if added in that ordered.**

** **

** **

** **

** **

** **

** **

** **

**b. What are the children of the node containing 60 in the above tree.**

** **

** **

** **

** **

** **

**e. What are the siblings of the node with value 40?**

** **

** **

** **

** **

**f. What are the leaf nodes in the new tree?**

** **

** **

** **

**g. How can the above tree be stored in an array?**

** **

** **

** **

**Q 10 Using the following nodes make a link list.**

** **

**Address Contents**

**14 **** T**

**15 **** 1C**

**1A W**

**1B 1E**

**1C O**

** 1D 1A**

** 1E N**

** 1F 4E**

** **

** **

** **

**Delete the node with data W from the link list and print the new list with new pointers assignments.**

** **

** **

** **

** **

** **

** **

** **

** **

**Add the following node containing R in the above list between nodes containing data O and N and print the new link list with new pointer assignments.**

** **

**Address Contents**

**10 R**

**11 8E**

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** d. What is the advantage of using linklist for data structure instead of an array?**

** **

** **

** **

** **

**Q11. **

** 0 1 2 3 4 5 6**

** **

** Stack Pointer**

** **

**Show how stack appears and the location of stack pointer after the following operations are performed on the stack.**

** **

**a. ****Push C**

** **

** **

** **

**b. ****Push R**

** **

** **

** **

**c. ****Push A**

** **

** **

**d. ****Pop C**

** **

** **

**e. ****Push C**

** **

** **

** **

**f. ****Push K**

** **

** **

** **

**g. ****Push L**

** **

** **

** **

**h. ****Push E**

** **

** **

** **

** **

** **

** **

** **

**Q12 Following is a queue implemented using arrays.**

** **

** 0 1 2 3 4 5 6**

** **

** Head Pointer**

** **

** **

**a. What cell does the Tail Pointer point to ?**

** **

** **

** **

**Draw the queue and indicate the position of the head pointer and the tail pointer after each of the following operations are performed on the above queue.**

** **

** **

**a) ****Enqueue W**

** **

** **

**b) ****Dequeue W**

** **

** **

**c) ****Dequeue N**

** **

** **

**d) ****Dequeue E**

** **

** **

**e) ****Enqueue Z,**

** **

** **

**f) ****Enqueue E**

** **

** **

**g) ****Enqueue A**

** **

** **

**h) ****Enqueue L**

** **

** **

**i) ****Dequeue W**

** **

** **

**j) ****Enqueue A**

** **

** **

** **

** **

**k) ****Enqueue N**

** **

** **

** **

**l) ****Enqueue D**

** **

** **

** **

** **

** **

**Q13. The following program calculates the total amount of snow for the month of January. Does the program work correctly, if not make the appropriate changes so that it calculates**

** **

**i. total amount of snow.**

**ii. prints daily_snow amount for each day.**

** **

** day_num=0**

** total_snow=0**

** daily_snow = 0**

** while ( day_num < 31 )**

** total_snow = total_snow + daily_snow**

** **

** print “The total amount of snow for January is “, total_snow**

** **

** **

** **

** **

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of