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

 

 

2. Kevin

 

 

3. Eric

 

 

4. Krish

 

 

5. Neil

 

 

6. Melissa

 

 

7. Patricia

 

 

8. 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:

 

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

2. 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² ) 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²)

O(n)

O(logn)

 

 

      c. Perform the following binary additions.

 

             10101011                        

         +  01011110                

 

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

 

1. 11010

 

 

2. 1110001

 

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

 

 

 

 

 

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

 

 

 

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

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

Attachments:

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