(5/5)

# CS110 How many comparisons are required to search the following names using binary search and sequential search in the following

INSTRUCTIONS TO CANDIDATES
###### ANSWER ALL QUESTIONS

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

1. Aaron

1. Kevin

1. Eric

1. Krish

1. Neil

1. Melissa

1. Patricia

1. 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)

1. function definition
2. function call
3. formal parameters
4. 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:

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

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=_____.

1. 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.

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(n2 ) 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(n2)

O(n)

O(logn)

c. Perform the following binary additions.

10101011

+  01011110

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

1. 11010

1. 1110001

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

1. 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.

14          T

15        1C

1A     W

1B     1E

1C     O

1D     1A

1E    N

1F    4E

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

1. 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.

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

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)

## Related Questions

##### . Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

##### . The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

##### . SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

##### . 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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

Hire Me

Hire Me