Chapter 7 Exercises and Answers For Exercises 1–15, mark the answers true and false as follows: A. True B. False 1. Arithmetic can be performed in the instruction register. B 2. Arithmetic can be performed in the A register. A 3. Arithmetic can be performed in the accumulator. A 4. The Z bit is 1 if the accumulator is 0. A 5. The N bit is 0 of the accumulator is negative. B 6. The program counter and the instruction register are two names for the same place. B 7. The A register and the accumulator are two names for the same place. A 8. The instruction register is three bytes long. A 9. The program counter is three bytes long. B 10. The status bits are each one byte long. B 11. The instruction specifier is two bytes long. B 12. If the data to be loaded into the accumulator is stored in the operand, the instruction specifier is 00. A 13. If the data in the accumulator is to be stored in the place named in the operand, the instruction specifier is 00. B 14. All Pep/7 instructions occupy three bytes. B 15. The branching instructions test the status bits. A Given the following state of memory (in hexadecimal), answer Exercises 16–20 by matching the problem to the solution shown. 0001 A2 0002 11 0003 FF 0004 00 A. 10100010 00010010 B. 11111111 00000000 C. 00000000 00000011 D. 11101101 00000001 E. 00010010 00000000 16. What are the contents of the A register after the execution of this instruction? 00001000 00000000 00000011 C 17. What are the contents of the A register after the execution of this instruction? 00001001 00000000 00000011 B 18. What are the contents of the A register after the execution of the following two instructions? 00001001 00000000 00000001 00011000 00000000 00000001 A 19. What are the contents of the A register after the execution of the following two instructions? 00001000 00000000 00000001 00011001 00000000 00000010 E 20. What are the contents of the A register after the execution of the following two instructions? 00001001 00000000 00000011 00100001 00000000 00000010 D Exercises 21–53 are programs or short-answer questions. 21. What does it mean when we say that a computer is a programmable device? Programmable means that data and instructions are logically the same and are stored in the same place. The consequence of this fact is that the program the computer executes is not wired into the hardware but entered from outside. 22. List five operations that any machine language must include. There must be machine-language instructions to store, retrieve, and process data, to input data and to output data. These instructions mirror the operations of the von Neumann machine. 23. The distinction between concrete and abstract steps in algorithms is not always clear-cut. Discuss this dilemma and give concrete examples to support your discussion. Algorithms are eventually coded in a programming language. Different programming languages represent different levels of abstraction. What takes a single step in one language may take many steps in another language. Thus, a concrete step in one language may be an abstract step in another. 24. What is a virtual machine? Discuss this definition in terms of the Pep/7 computer. A virtual machine is a hypothetical machine designed to illustrate important features of a real computer. The Pep/7 computer is a virtual machine designed to illustrate the features of the von Neumann architecture. It has instructions to store, retrieve, and process data as well as instructions to input and output data. 25. We said that you should have guessed that a Pep/7 instruction would use 5 bits when we said that there were 32 instructions. Explain. It takes exactly 5 bits to represent 32 different things, instructions in this case. 26. Describe the features of the Pep/7 CPU that we covered in this chapter. There is one register for arithmetic and logical operations: the A register (the accumulator). There is a Program Counter that contains the address of the next instruction to be executed and the Instruction Register that contains the instruction being executed. There are two status bits: N and Z which are one if the accumulator is negative or zero respectively. Memory is byte addressable. 27. We covered only two of the four addressing modes. If we had not stated this explicitly, could you have deduced that this was true? Explain. If there were only two addressing modes, one bit would have been used instead of two. Because two bits are used, there must be four modes. 28. Where is the data (operand) if the address mode specifier is: a. 00 If the address mode specifier is 00, the data is in the operand specifier. b. 01 If the address mode specifier is 01, the data is stored in the place named in the operand specifier. 29. Distinguish between the IR (instruction register) and the PC (program counter). The IR contains an instruction (the one being executed); the PC contains an address (the address of the next instruction to be executed). 30. How many bits are required to address the Pep/7 memory? The Pep/7 memory contains 4096 bytes, so 12 bits are required to address each one. 31. How many more cells could be added to memory without having to change the instruction format? Justify your answer. The operand specifier is 16 bits long. Therefore 216 different bytes could be addressed without changing the instruction format. Thus, 61440 more bytes could be added. 32. Some Pep/7 instructions are unary, taking only one byte. Other instructions require three bytes. Given the instructions that we have covered in this chapter, would it be useful to define instructions that require only two bytes? The instructions we have covered, other than the Stop instruction, use the operand specifier of the instruction. The operand specifier is two bytes long, so three bytes are required for the instruction: the instruc tion specifier and the operand specifier. Therefore, two-byte instruc tions would not be useful. 33. If the input character is A, what is the result of executing the following two instructions? 0001 11011001 00000000 00000110 0004 11100000 00000000 00001010 A is written on the screen. 34. If the input character is A, what is the result of executing the following two instructions? 0001 11011001 00000000 00000110 0004 11100001 00000000 00001010 What ever is stored in location 01000001 is written on the screen. 35. Write the algorithm for writing out your name, given that the implementation language is Pep/7 machine code. Write “Nell” Write “Nell” Write “N” Write “e” Write “l” Write “l” Write “N” Write 4E (hex) Write “e” Write 65 (hex) Write “l” Write 6C (hex) Write “l” Write 6C (hex) 36. Write the machine-language program to implement the algorithm in Exercise 35. E0 00 4E E0 00 65 E0 00 6C E0 00 6C zz 37. Write the algorithm for writing out your name, given that the implementation language is Pep/7 assembly language. Write “Nell” Write “Nell” Write “N” Write “e” Write “l” Write “l” 38. Write the assembly-language program to implement the algorithm in Exercise 37. CHARO h#0010,d ;Output ‘N’ CHARO h#0011,d ;Output ‘e’ CHARO h#0012,d ;Output ‘l’ CHARO h#0013,d ;Output ‘l’ STOP .ASCII /Nell/ ;Store ‘Hello’ into proper places .END 39. Rewrite the machine language program in 7.4, using direct addressing. E1 00 10 E1 00 11 E1 00 12 E1 00 13 E1 00 14 00 48 65 6C 6C 6F zz 40. Distinguish between the Pep/7 menu options Load, Load/Execute, and Execute. Load puts the program in memory ready to execute. Load/Execute loads the program into memory and executes it. If a program is loaded, an Execute command executes the program. If the active window contains a machine language program and there is no loaded program, the Execute command loads and executes it. 41. The following program seems to run, but does strange things with certain input values. Can you find the bug? BR Main sum: .WORD d#0 num1: .BLOCK d#1 num2: .BLOCK d#1 num3: .BLOCK d#1 Main: LOADA sum,d DECI num1,d DECI num2,d DECI num3,d ADDA num3,d ADDA num2,d ADDA num1,d STOREA sum,d DECO sum,d STOP .END One byte of storage is set up for each input value. If the value that is read is grater than one byte, the excess spills over to the byte above giving the wrong answer. 42. Correct the code in Exercise 41 and run the test plan outlined in the chapter. BR Main sum: .WORD d#0 num1: .BLOCK d#2 num2: .BLOCK d#2 num3: .BLOCK d#2 Main: LOADA sum,d DECI num1,d DECI num2,d DECI num3,d ADDA num3,d ADDA num2,d ADDA num1,d STOREA sum,d DECO sum,d STOP .END The test plan gives the correct answers with this code. 43. Finish executing the test plan for the algorithm in the text that reads and sums three values. The answers are correct. 44. Write an algorithm that reads in three values and writes out the result of subtracting the second value from the sum of the first and the third values. Read num1 Read num2 Read num3 Load num1 Add num3 Sub num2 Store in answer Write answer 45. Implement the algorithm in Exercise 44 as an assembly-language program. BR Main answer: .WORD d#0 num1: .BLOCK d#2 num2: .BLOCK d#2 num3: .BLOCK d#2 Main: DECI num1,d DECI num2,d DECI num3,d LOADA num1,d ADDA num3,d SUBA num2,d STOREA answer,d DECO answer,d STOP .END 46. Write and implement a test plan for the program in Exercise 45. Reason for Test Case Input Values Expected Output Observed Output Assumption: Input values are no greater than 215 –1 or less than – 215. Input three positive numbers 4, 6, 1 –1 –1 Input three negative numbers –4, –6, –1 1 1 Input mixed numbers 4, 6, –1 –3 –3 4, –6, 1 11 11 4, –6, –1 –9 –9 –4, 6, 1 –9 –9 –4, 6, –1 –11 –11 –4, –6, 1 3 –3 Large numbers 32767, –1, +1 overflows overflows 32767, 1, –1 32767 47. Design and implement, in assembly language, an algorithm that reads four values and prints the sum. Set count to 0 Set sum to 0 While count < 4 Read num Add num to sum Increment count Write sum BR Read ;branch to location Read sum: .WORD d#0 ;set zero word count: .WORD d#0 ;set up a two byte block for count limit: .WORD d#4 ;set up a block for value 4 number:.WORD d#0 ;set up word for value read Read: LOADA sum,d ;load a copy of sum into accumulator DECI number,d ;read and store a decimal number ADDA number,d ;add the number to the accumulator STOREA sum,d ;store accumulator in sum LOADA count,d ;load a copy of limit in accumulator ADDA d#1,i ;add 1 to the accumulator STOREA count,d ;store contents in count SUBA limit,d ;subtract 4 COMPA d#0,i ;compare accumulator to 0 BREQ Quit ;branch to Quit if accumulator is 0 BR Read ;go back to read in another number Quit: DECO sum,d ;output contents of sum STOP ;end of the program .END 48. Is the test plan for a machine-language program valid for the same solution written in assembly language? Explain your answer. A data-coverage plan is written without looking at the code, so the same test plan would be valid. A code-coverage plan looks at the code, but because there is a one to one relationship between a machine code instruction and an assembly language instruction, the same test plan would be valid. 49. Distinguish between the pseudo-code instructions .BLOCK and .WORD. The pseudo-code instruction .BLOCK takes a decimal argument and sets aside that many bytes of storage and set them to zero. A .WORD pseudo-code instruction takes a decimal argument and generates one word of storage with the decimal value stored in it. 50. Distinguish between assembly-language pseudocode instructions and mnemonic instructions. Pseudo-code instructions are instructions to the assembler; mnemonic instructions are to be translated by the assembler. 51. Distinguish between test plans based on code coverage and data coverage. A code-coverage test plan is based on examining and covering the statements in the code. A data-coverage test plan is based on the input data to the program. 52. Explain the meaning of the Pep/7 menu option Execution Input. The Execution Input menu asks if you want the input data to come from the current window for from the keyboard. 53. Write the Pep/7 assembly-language statement for the following instructions: a. Branch to location Branch1 if the accumulator is zero. BREQ Branch1 b. Branch to location Branch1 if the accumulator is negative. BRLT Branch1 c. Branch to location Branch1 if the accumulator is negative and to Branch2 if the accumulator is not negative. BRLT Branch1 Branch2: That is, go to location Branch1 if the accumulator is negative. If the accumulator is not negative, the next instruction is executed, so it must be labeled Branch2. Chapter 8 ==================================================== For Exercises 1–14, match the question with the appropriate translation or execution system. A. Interpreter B. Assembler C. Compiler D. Machine code 1. What translates a high-level language into machine code? C 2. What translates a Java program into Bytecode? C 3. What executes Bytecode? A 4. What translates an assembly-language program? B 5. What is the output of an assembler? D 6. What takes input in a high-level language and directs the computer to perform the actions specified in each statement? A 7. What executes the Java Virtual Machine? D 8. What is used to translate a program in ALGOL? C 9. What is used to translate a program in APL? A 10. What is used to translate a program in COBOL? C 11. What is used to translate a program in FORTRAN? C 12. What is used to translate a program in Lisp? A 13. What is used to translate a program in SNOBOL4? A 14. Which translator runs the slowest? A For Exercises 15–36, match the language paradigm and the language or the language description. A. Imperative or procedural B. Functional C. Logic D. Object oriented E. Procedural language with some object-oriented features F. Object-oriented language with some procedural features 15. Which paradigm most accurately describes FORTRAN? A 16. Which paradigm most accurately describes C++? E 17. Which paradigm most accurately describes PASCAL? A 18. Which paradigm most accurately describes Java? F 19. Which paradigm most accurately describes Lisp? B 20. Which paradigm most accurately describes BASIC? A 21. Which paradigm most accurately describes PROLOG? C 22. Which paradigm most accurately describes SIMULA? D 23. Which paradigm most accurately describes ALGOL? A 24. Which paradigm most accurately describes ML? B 25. Which paradigm most accurately describes Scheme? B 26. Which paradigm most accurately describes Ada? A 27. Which paradigm most accurately describes C? A 28. Which paradigm most accurately describes Smalltalk? D 29. The dominant languages used in industry throughout the history of computing software come from which paradigm? A 30. Which paradigm did Japanese researchers choose for the fifth-generation computer? C 31. Which paradigm allows the programmer to express algorithms as a hierarchy of objects? D 32. Which paradigm allows the programmer to express algorithms as a hierarchy of tasks? A 33. Which paradigm allows the programmer to express algorithms as mathematical functions? B 34. Which paradigm has no assignment statement? B 35. Which paradigm uses recursion exclusively to express repetition? B 36. Which paradigm has no variables? B Exercises 37–82 are problems or short-answer questions. 37. What is the hallmark of an assembly language? The hallmark of an assembly language is that each assembly language instruction is translated into one machine language instruction. 38. Distinguish between an assembler and a compiler. An assembler translates assembly-language instructions into machine code. A compiler translates high-level language instructions into machine code. The translation of an assembler is one to one: One statement in assembly language is translated into one statement in machine code. The translation of a compiler is one to many: One high- level language instruction is translated into many machine language instructions. 39. Distinguish between a compiler and an interpreter. The output from a compiler is a machine-language program. That program may be stored for later use or immediately executed, but the execution is a distinct process from the translation. The output from an interpreter is a solution to the original problem, not a program that when executed gives you the solution. 40. Compare and contrast an assembler, a compiler, and an interpreter. All three are translators. They differ in the complexity of the languages they translate and in the output from the translator. Assemblers and compilers produce machine-language programs, which when run solve the original problem; interpreters produce solutions to the original problem. Assemblers translate very simple languages; compilers and interpreters can translate very complex languages. 41. Describe the portability provided by a compiler. A program written in a high-level language that is compiled can be translated and run on any machine that has a compiler for the language. 42. Describe the portability provided by the use of Bytecode. Bytecode is the output from (usually) a Java compiler. There is a virtual machine for which Bytecode is the machine language. A program compiled into Bytecode can be executed on any system that has a simulator for the virtual machine. The Java Virtual Machine (JVM) executed Bytecode. 43. Describe the process of compiling and running a Java program. A Java program is compiled into Bytecode, which can be executed on any system with a JVM. 44. Discuss the word paradigm as it relates to computing. Programming languages reflect differing views of reality, which we call paradigms. We use these views (paradigms) to classify the languages. 45. Name four programming language paradigms and give an example language in each. Imperative or procedural paradigm: Fortran, Basic, Cobol, C, C++ Functional paradigm: Lisp, Scheme, ML, FP Logic paradigm: PROLOG Object-oriented paradigm: Simula, Smalltalk, Java 46. What are the characteristics of the imperative paradigm? Programs describe the processes necessary to solve the problem. 47. What are the characteristics of the functional paradigm? Programs are expressed as the evaluation of functions. 48. What are the characteristics of the logic paradigm? Rules of logic are used to deduce answers from facts and rules. 49. How does the view of an object-oriented program differ from the view of an imperative program? An object-oriented view of a program is that of interacting objects; the imperative view of a program is that of interacting tasks. 50. How do you ask questions in a programming language? To ask a question in a programming language, you make an assertion. If the assertion is true, the answer is true. If the assertion is false, the answer is false. 51. What is a Boolean variable? A Boolean variable is a place in memory, referenced by an identifier, that can contain true or false. 52. What is a Boolean expression? A Boolean expression is a sequence of identifiers, separated by compatible operators, that evaluates to true or false. 53. Given Boolean variables one, two, and three, write an assertion for each of the following questions. a. Is one greater than both two and three? (one> two) AND (one> three) b. Is one greater than two, but less than three? (one > two) AND (one < three) c. Are all three variables greater than zero? (one > 0) AND (two > 0) AND (three > 0) d. Is one less than two or one less than three? (one < two) OR (one < three) e. Is two greater than one and three less than two? (two > one) AND (three < two) 54. Write the operation table for Boolean operation AND. AND 0 1 0 0 0 1 0 1 55. Write the operation table for Boolean operation OR. OR 0 1 0 0 1 1 1 1 56. Write the operation table for Boolean operation NOT. NOT 0 1 1 0 57. What is a data type? A data type is the description of a set of values and the basic set of operations that can be applied to values of the type. 58. What is strong typing? Strong typing means that each variable is assigned a data type and only values of that type can be stored in the variable. 59. Define the following data types. a. integer The range of integer values that a machine can represent. b. real The range of rational numbers that a machine can represent. c. character The characters in the character set that the machine supports. d. Boolean The values true and false. 60. Is the string data type an atomic data type? Justify your answer. A string can be output like an atomic data type, but it is made up of characters, each of which can be accessed separately. Thus, you can argue either side. 61. If the same symbol is used for both single characters and strings, how can you distinguish between a single character and a one-character string? If the same symbol is used, a character cannot be distinguished from a one-character string. 62. What is a declaration? A declaration is an instruction to the compiler that associates an identifier with a variable, an action, or some other entity within the language that can be given a name. The programmer can then refer to that entity by name. 63. Fill in the following table showing the appropriate syntactic marker or reserved word for the language shown based on your observations of the tables in this chapter. See the Answers as book. 64. How do the .WORD and .BLOCK assembler directives in the Pep/7 assembly language differ from the declarations in high-level languages? .WORD allows us to associate an identifier with a word in storage and specify what should go into that word. .BLOCK allows us to asso ciate an identifier with a specified number of bytes. In each case the programmer knows the actual address associated with the identifier. Declarations in high-level languages give you the same functionality, but the programmer does not need to worry about the actual address. 65. Distinguish be between instructions to be translated and instructions to the translating program. Instructions to the translating program tell the program to associate identifiers with objects, and if the objects are data, tell the program the data type of what can be stored in that place. 66. Consider the following identifiers: Address, ADDRESS, AddRess, Name, NAME, NamE a. How many different identifiers are represented if the language is Ada? 2 b. How many different identifiers are represented if the language is VB.NET? 6 c. How many different identifiers are represented if the language is C++ or Java? 6 67. Explain the operation of the sequence control structure. The sequence control structure say to execute the statements in sequence, one after the other. 68. Explain the flow of control of the if statement. If the Boolean expression is true, execute the first statement. If the Boolean expression in false, execute the second statement. In either case continue with the statement following the second statement. 69. Explain the difference between the then branch and the else branch in the if statement. An if statement is based on an expression being true or false. A case statement matches the contents of an expression with a series of values to find the statement to execute next. 70. What is the flow of control in a while statement? The statements within the while statement are repeated as long as the while expression is true. When the expression becomes false, the statement following the end of the loop body is executed. 71. What is recursion? Recursion is the ability of a subprogram to call itself. 72. How does recursion act as a repetition structure? The program uses a selection statement to determine whether to repeat the code by calling the subprogram again or to stop the process. 73. A looping structure uses a __while (loop)____________ statement; a recursive structure uses a ___if (selection)_________ statement. 74. Explain the statement, “Subprograms are a powerful tool for abstraction.” A subprogram is a named task. The calling program can be designed and written using the subprogram name without knowing how the subprogram is implemented. 75. Describe how a parameter list is used to communicate information from the calling unit to the subprogram. A parameter list is a list of identifiers, separated by commas. These identifiers are just place holders. When the subprogram is called, the calling program sends the actual data the subprogram is to use. The variables in the argument list replace the identifiers in the parameter list. 76. Distinguish between a parameter and an argument. A parameter is a dummy name listed on the subprogram’s heading. An argument is the data the calling program sends to the subprogram to use. 77. Distinguish between a value parameter and a reference parameter. The calling program sends a copy of the data to the subprogram if the parameter is a value parameter. If the subprogram’s parameter is a reference parameter, the calling program sends the address of the data. 78. Which three elements must be present in the definition of a record? The record name, the names of the individual data items and their respective data types. 79. Ada uses a range of index values to define an array, but VB.NET and C++ specify the number of places in the array. Explain. Ada lets the user explicitly define how the values in the array are to be indexed; the number of items is determined from this range. VB.NET and C++ specify the number of elements in the array, and accessing is always from [0] through [number of elements - 1] 80. Examine the following three array declarations: type Index is range –1..10; — Ada type Data_Array is array (Index) of Integer; Data : Data_Array; — Ada Dim data(11) As Integer ‘ VB.NET int data[11]; // C++ Are the arrays declared the same? Justify your answer. The Ada array contains 12 slots, indexed from (-1)..(10). The VB.NET and C++ arrays contain 11 slots, indexed from (0)..(10) in VB.NET and [0]..[10] in C++. 81. Distinguish between the definition of an object in the design phase and in the implementation phase. An object in the design phase is an entity that has meaning within the context of the problem. An object in the implementation phase is an instance of a class. 82. Distinguish between the definition of a class in the design phase and in the implementation phase. A class in the design phase is a description of a group of objects with similar properties and behaviors. A class in the implementation phase is a pattern for an object. Chapter 9 Exercises and Answers ===================================================== For exercises 1–10, match the class of operation with the operation described. A. Constructor: Creates a new instance of a container. B. Transformer: Changes the contents of a container. C. Iterator: Allows access to each item in a container one at a time. D. Observer: Asks information about a container without changing it. 1. Add into a container. B 2. Create a new container. A 3. How many objects are in the container? D 4. Is the container empty? D 5. Get the next item in the container. C 6. Have we looked at all the items in the container? D 7. Delete an item from the container. B 8. Is the item in the container? D 9. Set the container to empty. B 10. Is the container full? D For exercises 11–20, match the type of list implementation with the given implementation step. A. Array-based B. Linked C. Either D. Neither 11. Initialize by setting length to zero. A 12. In an unsorted container, put the item into the beginning of the list. B 13. In a sorted container, put the item at the end of the list. D 14. To insert in a sorted list, first find the appropriate position. C 15. Initialize by setting pointer to null. B 16. Get next item involves incrementing a counter. A 17. Get next item involves moving a pointer. B 18. more items involves comparing length to a counter. A 19. more items involves comparing something to null. B 20. Find the item involves searching the list. C For Exercises 21–37, mark the answers true or false as follows: A. True B. False 21. A binary search cannot be applied to a linked list. A 22. A linear search cannot be applied to an array-based list. B 23. A binary search cannot be applied to an array-based list. B 24. A binary search is always faster than a linear search. B 25. A binary search cannot be applied to an unsorted list. A 26. A stack exhibits LIFO behavior. A 27. A queue exhibits FIFO behavior. A 28. A stack and a queue are different versions of the same abstract data type. B 29. A binary search tree allows log2N searching in a linked structure. A 30. In a graph, the vertices represent the objects being modeled. A 31. The bubble sort algorithm involves finding the smallest item in the unsorted portion of the array and swapping it with the current item. B 32. The selection sort algorithm involves finding the smallest item in the unsorted portion of the array and swapping it with the current item. A 33. The bubble sort algorithm swaps every out-of-order pair it sees. A 34. The Quicksort algorithm swaps every out-of-order pair encountered from different ends of the array. A 35. The Quicksort algorithm is always quick. B 36. The shape of a binary search tree depends on the order in which the items are inserted. A 37. The edges in a graph represent relationships. A Exercises 38–58 are problems or short-answer questions. 38. Abstract data types, data structures, and containers: a. Define these terms Abstract data types are data types whose properties (domains and operations) are specified independently of any particular implemen tation. A data structure is the implementation of the composite data fields of an abstract data type. A container is an object whose role is to hold and manipulate other objects. b. What do they have in common? Each represents the concept of collections of data objects. c. What distinguishes each from the others? Each represents a different level. An ADT is the logical view of the properties of a class of data. A data structure is the implementation level of this logical view. A container is the description given to all logical views of this type of object; it represents how an application program might view the ADT at a higher level. 39. Name and describe the three views of data. Application, logical, and implementation are the three views of data. The application is the view of the data within a particular problem. The logical is the view that sees the data as objects with similar prop erties and behaviors and specifies them at an abstract level. The imple mentation view is a specific representation of the data and the actions to manipulate them. 40. Array-based implementation and linked implementation: a. Define these terms. An array-based implementation is one that uses an array to hold the data items. Each item is accessed by its place in the structure. A linked implementation is one that uses a structure made up of nodes in which the nodes are explicitly linked one to another. b. What do they have in common? They are both storage structures to hold collections of homoge neous items. c. What distinguishes one from the other? They are distinguished by how the items are stored. In the array- based implementation data items are stored in contiguous locations in memory and accessed by position. In a linked implementation data items are stored in nodes along with the information of where to find the next node in the structure. 41. Draw the unsorted list containing the following strings: blue, black, green, yellow, red, purple, white, and violet. a. In an unsorted array-based list. b. In a sorted array-based list. c. In an unsorted linked list. d. In a sorted linked list. a. An unsorted array-based list. 8 blue black green red purple white violet yellow [0] [1] [2] [3] [4] [5] [6] [7] b. A sorted array-based list. 8 black blue green red violet white yellow purple [0] [1] [2] [3] [4] [5] [6] [7] c. An unsorted linked list. blue black green yellow red purple violetwhite d. A sorted linked list. blue black green redpurple violent yellowwhite 42. Give the meaning of the following expressions in an array-based implementation: a. Put item Put item means that given an index shift the items that follow down one slot in the array and store the item at the index position. b. Remove the item Remove the item means that given an index shift the items that follow up one slot in the array. c. Get next item Get next item means to increment the value used as an index and access that indexed position. d. more items More items means that the variable used as an index is less than length – 1. 43. Give the meaning of the following expressions in a linked implementation: a. Put item Get next item means given current insert a new node with item in the info part of the node between current and next(current). b. Remove the item Remove the item means given current remove the next(current). c. Get next item Get next item means to set current to next(current). d. more items More items means that current does not contain null. Questions 44–46 use the following list of values. length 11 list [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 23 41 66 20 2 90 9 34 19 40 99 44. Show the state of the list when current is first set equal to the fourth item in the selection sort. Array when current is first set to 4th item. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 2 9 19 20 23 90 41 34 66 40 99 45. Show the state of the list when current is first set equal to the fifth item in the bubble sort algorithm. Array when current is first set to 5th item. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 2 9 19 20 23 41 66 34 40 90 99 46. Show the state of the list when the first recursive call is made in Quicksort using list[0] as the split value. Array when first recursive call is made. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 2 19 9 20 23 90 66 34 41 40 99 Questions 47 and 48 use the following list of values. length [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 11 5 7 20 33 44 46 48 99 101 102 105 47. How many comparisons does it take using a sequential search to find the following values or determine that the item is not in the list? a. 4 11 b. 44 5 c. 45 11 d. 105 11 e. 106 11 48. How many comparisons does it take using a binary search to find the following values or determine that the item is not in the list? a. 4 4 b. 44 4 c. 45 4 d. 105 4 e. 106 4 49. Write the algorithm for Enque in an array-based implementation. There are several solutions. The easiest is to keep the front of the queue always in the [0] position. // rear is index of last element put on the structure Increment rear Set items[rear] to newItem 50. Write the algorithm for Pop in a linked implementation. Set current to stack Set outItem to info(current) Remove item 51. Write the algorithms for Deque in a linked implementation. Set current to front Set outItem to info(front) Remove item Exercises 52–57 use the following tree 52. Name the content of each of the leaf nodes. alex, christopher, john robert june, kit, nell, susy 53. List the contents of each node that has just a right child. al, chris, mari, sarah 54. List the contents of each node that has just a left child. There are none. 55. What is the height of the tree? 5 56. Name the content of the nodes that are the ancestors of the node containing kit. kate, lila, phil, john 57. How many descendents does the node containing jim have? 3 58. Draw the tree that results from inserting the following value in this order: 25 15 30 7 26 40 2 8 35 Chapter 10 Exercises and Answers ================================================================= For Exercises 1–18, mark the answers true or false as follows: A. True B. False 1. An operating system is an example of application software. B 2. An operating system provides a basic user interface that allows the user to use the computer. A 3. A computer can have more than one operating system, but only one is in control at any given time. A 4. Multiprogramming is the technique of using multiple CPUs to run programs. B 5. In the 1960s and 70s, a human operator would organize similar computer jobs into batches to be run. A 6. Batch processing implies a high level of interaction between the user and the program. B 7. A timesharing system allows multiple users to interact with a computer at the same time. A 8. A dumb terminal is an I/O device that connects to a mainframe computer. A 9. A logical address specifies an actual location in main memory. B 10. An address in a single contiguous memory management system is made up of a page and an offset. B 11. In a fixed partition system, main memory is divided into several partitions of the same size. B 12. The bounds register contains the last address of a partition. B It contains the length of the partition. 13. The first page in a paged memory system is page 0. A 14. A process in the running state is currently being executed by the CPU. A 15. The process control block (PCB) is a data structure that stores all information about a process. A 16. CPU scheduling determines which programs are in memory. B 17. The first-come, first-served scheduling algorithm is probably optimal. B 18. A time slice is the amount of time each process is given before being preempted in a round-robin scheduler. A For Exercises 19–23, match the operating system with information about it. A. Mac OS B. UNIX C. Linux D. DOS E. Windows 19. Which is the operating system of choice for Apple Computers? A 20. Historically, which is the operating system of choice for serious programmers? B 21. Which is the PC version of UNIX? C 22. What is the Microsoft operating system family provided on PCs called? E 23. What is the original PC operating system called? D For Exercise 24–26, match the following software type with its definition. A. Systems software B. Operating system C. Application software 24. Programs that help us solve real-world problems. C 25. Programs that manage a computer system and interact with hardware. A 26. Programs that manage computer resources and provide interfaces for other programs B Exercises 27–72 are problems or short-answer questions. 27. Distinguish between application software and system software. Systems software are tools to help others write programs; they manage a computer system and interact with hardware. Application software are programs to solve specific problems. 28. What is an operating system? An operating system is a piece of software that manages a computer’s resources and provides an interface for system interaction. 29. Explain the term multiprogramming. Multiprogramming is the technique of keeping multiple programs in main memory at the same time, each competing for time on the CPU. 30. The following terms relate to how the operating system manages multiprogramming. Describe the part each plays in this process. a. Process A process is a program in execution. b. Process management Process management is keeping track of necessary information for active processes. c. Memory management Memory management is keeping track of how and where programs are loaded into main memory. d. CPU scheduling CPU scheduling is determining which process in memory is given access to the CPU so that it may execute. 31. What constitutes a batch job? A batch job was made up of the program and the instructions regarding the system software and other resources needed to execute the job. 32. Describe the evolution of the concept of batch processing from the human operator in the 1960s and 1970s to the operating systems of today. Originally the instructions regarding the system software needed for a program were given to the human operator. Today the instructions are given directly to the computer through OS commands that are part of the file containing the program. Today, batch processing has come to mean a system in which programs and system resources are coordinated and executed without interaction between the user and the program. 33. Define timesharing. Timesharing is a technique by which CPU time is shared among multiple interactive users at the same times. 34. What is the relationship between multiprogramming and timesharing? Multiprogramming allows multiple processes to be active at once. Timesharing allows the multiple processes to be interactive ones. 35. Why do we say that users in a timesharing system have their own virtual machine? Users have the illusion of having the computer all to themselves. 36. In Chapter 7, we defined a virtual machine as a hypothetical machine designed to illustrate important features of a real machine. In this chapter, we define a virtual machine as the illusion created by a timesharing system that each user has a dedicated machine. Relate these two definitions. The illusion created in a timesharing situation is that the user owns a single hypothetical machine. The hypothetical machine illustrates the important features of the single machine the user needs. 37. How does the timesharing concept work? Each user is represented by a login process that runs on the main frame. When the user runs a program, another process is created that competes for CPU time with other processes. The rationale is that the computer is so fast that it can handle multiple users without anyone having to wait. 38. What is a real-time system? A real-time system is a system in which the speed of an answer is crucial. 39. What is response time? Response time is how long it takes to get an answer. The expression comes from the delay between receiving a stimulus (asking a question) and producing a response (answering the question). 40. What is the relationship between real-time systems and response time? Time is critical in many real-time situations, so the response time must be kept to a minimum. 41. In a multiprogramming environment, many processes may be active. What are the tasks that the operating system must accomplish to manage the memory requirements of active processes? The OS must keep track of where and how a program resides in memory and convert logical program addresses into actual memory addresses. 42. Distinguish between logical addresses and physical addresses. A physical address is an actual address in the computer’s main memory device. A logical address is an address relative to the program. A logical address is sometimes called a relative address for obvious reasons. 43. What is address binding? Address binding is the mapping of a logical address into a physical address. 44. Name three memory-management techniques and describe the general approach taken in each. Single contiguous memory management: Only the OS and one applica tion program are loaded into memory at the same time. Static and dynamic partitions: More than one program is loaded into memory with the OS at the same time. Each application program is given its own partition of memory. Paging: Main memory is divided into fixed-sized blocks called frames and processes are divided into fixed-sized blocks called pages. Any number of programs can be loaded with the OS, but a process does not necessarily have to be in contiguous memory and not all of a process need be in memory at the same time. 45. When is a logical address assigned to a variable? When the program is compiled. 46. When does address binding occur? When the program is loaded into memory. 47. How is memory divided in the single contiguous memory management approach? Memory is divided into two sections, one for the operating system and one for the application program. 48. When a program is compiled, where is it assumed that the program will be loaded into memory? That is, where are logical addresses assumed to begin? At location 0. 49. If, in a single contiguous memory management system, the program is loaded at address 30215, compute the physical addresses (in decimal) that correspond to the following logical addresses: a. 9223 39438 b. 2302 32517 c. 7044 37259 50. In a single contiguous memory management approach, if the logical address of a variable is L and the beginning of the application program is A, what is the formula for binding the logical address to the physical address? L + A 51. If, in a fixed-partition memory management system, the current value of the base register is 42993 and the current value of the bounds register is 2031, compute the physical addresses that correspond to the following logical addresses: a. 104 43097 b. 1755 44748 c. 3041 Address out of bounds of partition. 52. If more than one partition is being used (either fixed or dynamic), what does the base register contain? The base register contains the beginning address of the current parti tion. 53. Why is the logical address compared to the bounds register before a physical address is calculated? The bounds register contains the length of the current partition. If the logical address is greater than the bounds register, then the physical address is not within the current partition. 54. If, in a dynamic partition memory management system, the current value of the base register is 42993 and the current value of the bounds register is 2031, compute the physical addresses that correspond to the following logical addresses: a. 104 43097 b. 1755 44748 c. 3041 Address out of bounds of partition. Exercises 55 and 56 use the following state of memory. Operating system Process 1 Process 2 Process 3 Empty 60 blocks Empty 52 blocks Empty 100 blocks 55. If the partitions are fixed and a new job arrives requiring 52 blocks of main memory, show memory after using each of the following partition selection approaches: a. First fit b. Best fit c. Worst fit a. first fit Operating system Process 1 Process 2 Process 3 New process Empty 52 blocks Empty 100 blocks b. best fit Operating system Process 1 Process 2 Process 3 New process Empty 60 blocks Empty 100 blocks c. worst fit Operating system Process 1 Process 2 Process 3 New process Empty 60 blocks Empty 52 blocks 56. If the partitions are dynamic and a new job arrives requiring 52 blocks of main memory, show memory after using each of the following partition selection approaches: a. First fit b. Best fit c. Worst fit a. first fit New process Empty 52 blocks Empty 100 blocks Empty 8 blocks Operating system Process 1 Process 2 Process 3 b. best fit Empty 60 blocks Empty 100 blocks Operating system Process 1 Process 2 New process Process 3 c. worst fit Empty 60 blocks Empty 52 blocks Empty 48blocks Operating system Process 1 Process 1 New process Process 3 57. If a logical address in a paged memory management system is <2, 133>, what do the values mean? This address means the 133 byte on page 2. Page Frame 0 5 1 2 2 7 3 3 58. If the frame size of 1024, what is the physical address associated with the logical address <2, 85>? 7253 59. If the frame size of 1024, what is the physical address associated with the logical address <3, 555>? 3627 60. If the frame size of 1024, what is the physical address associated with the logical address <3, 1555>? Illegal address. The offset is larger than the page size. 61. What is virtual memory and how does it apply to demand paging? Virtual memory is the illusion that memory is limitless and thus there is no limit on the size of a program. Demand paging is the technique where pages are brought into memory only when they are referenced (needed). Demand paging allows programs of any size, thus giving the illusion of infinite memory. 62. What are the conceptual stages through which a process moves while being managed by the operating system? new, ready, running, waiting, and terminated 63. Describe how a process might move through the various process states. Create specific reasons why this process moves from one state to another. A new process begins in the new state. When the process has no bars to its execution, it moves into the ready state. It waits in the ready state until it gets time in the running state. It runs for a while and issues a command for file input. The process is moved into the waiting state until the I/O has been completed, at which time it moves into the ready state to await another turn in the running state. Eventually it gets back to the CPU and runs until it needs access to a part of the program that is on secondary storage. It moves into the waiting state until the needed pages are brought in; then it moves back to the ready state. It gets its third shot at the CPU and finishes, and moves into the terminated state. 64. What is a process control block? A process control block (PCB) is a data structure that contains information about a process. A PCB is created for each new process. When a process moves from one state to another, its PCB is moved with it. 65. How is each conceptual stage represented in the operating system? Each conceptual stage is represented by a list of the PCBs in that stage. 66. What is a context switch? When a process is moved out of the CPU, the current contents of the registers including the program counter must be saved in the process’s PCB. When a new process moves into the CPU, the contents of the registers from this process’s PCB are restored. This process of saving and restoring registers is called a context switch. 67. Distinguish between preemptive scheduling and nonpreemptive scheduling. With nonpreemptive scheduling, once a process is in the running state it remains there until it voluntarily leaves. With preemptive scheduling, the OS can move a process from the running state to the waiting state or ready state. 68. Name and describe three CPU scheduling algorithms. First-come, first-served: The processes are moved into the running state in the order in which they arrive in the ready. Shortest job next: When the CPU is ready for anther job, the process in the ready state that takes the shortest time is moved into the running state. The estimated length of time that a process needs the CPU may or may not be accurate. Round robin: Each process stays in the running state for a predetermined amount of time, called a time slice. When a process’s time slice is over, it is moved back into the ready state, where it stays until it is its turn again for the CPU. Use the following table of processes and service time for Exercises 69 through 72. Process p1 p2 p3 p4 p5 Service time 120 60 180 50 300 69. Draw a Gantt chart that shows the completion times for each process using first-come, first-served CPU scheduling. p1 p2 p3 p4 p5 0 120 410 710180 360 70. Draw a Gantt chart that shows the completion times for each process using shortest job next CPU scheduling. 0 50 110 230 410 710 p1p2 p3p4 p5 71. Draw a Gantt chart that shows the completion times for each process using round robin CPU scheduling with a time slice of 60. 0 60 120 180 230 290 350 410 470 530 590 650 710 p1 p2 p3 p4 p5 p1 p3 p3p5 p5 p5 p5 The answer is the same in all three partition selection approaches. 72. Distinguish between fixed partitions and dynamic partitions. The sizes of the partitions are fixed in a fixed partition scheme, although they are not necessarily the same size. In a dynamic partition scheme, the partitions are allocated as needed. Chapter 11 Exercises and Answers ========================================================== For Exercises 1–15, mark the answers true or false as follows: A. True B. False 1. A text file stores binary data that is organized into groups of 8 or 16 bits that are interpreted as characters. A 2. A program written in a high-level language is stored in a text file that is also called a source file. A 3. The type of a file determines what kinds of operations can be performed on it. A 4. The current file pointer indicates the end of a file. B 5. Sequential access and direct access take about the same amount of time to retrieve data. B 6. Some operating systems maintain a separate read pointer and write pointer for a file. A 7. Unix file permissions allow a group of users to access a file in various ways. A 8. In most operating systems, a directory is represented as a file. A 9. Two files in a directory system can have the same name if they are in different directories. A 10. A relative path is relative to the root of the directory hierarchy. B 11. An absolute path and a relative path will always be the same length. B 12. An operating system is responsible for managing the access to a disk drive. A 13. The seek time is the amount of time it takes for the heads of a disk to reach a particular cylinder. A 14. The shortest-seek-time-first disk-scheduling algorithm moves the heads the minimum amount it can to satisfy a pending request. A 15. The first-come, first-served disk-scheduling algorithm moves the heads the minimum amount it can to satisfy a pending request. B For Exercises 16–20, match the file extensions with the appropriate file. A. txt B. mp3, au, and wav C. gif, tiff, and jpg D. doc and wp3 E. java, c, and cpp 16. Audio file B 17. Image file C 18. Text data file A 19. Program source file E 20. Word processing file D For Exercises 21–23 , match the symbol with its use. A. / B. \ C. .. 21. Symbol used to separate the names in a path in a Windows environment B 22. Symbol used to separate the names in a path in a UNIX environment A 23. Symbol used to represent the parent directory in a relative path name C Exercises 24 –57 are problems or short answer questions. 24. What is a file? A file is the smallest amount of information that can be written to secondary memory. It is a named collection of data, used for organ izing secondary memory. 25. Distinguish between a file and a directory. A file is a named collection of data. A directory is a named collection of files. 26. Distinguish between a file and a file system. A file is a named collection of data. A file system is the operating system’s logical view of the files it manages. 27. Why is a file a generic concept and not a technical one? A file is just a named collection of bits (data) in storage. Because there are different operating systems, there are different technical views of a file. Because we are talking from the user’s view not the implementation view, the concept is generic. 28. Name and describe the two basic classifications of files. Text files: Files that contain text. Each byte is an ANSII character or each 2 types is a Unicode character. Binary files: The bytes in a binary file do not necessarily contain char acters. These files require a special interpretation. 29. Why is the term binary file a misnomer? All files ultimately are just a collection of bits, so why call one file type “binary?” In a binary file, the bits are not interpreted at text. A binary file would just be a stream of uninterpreted bits unless there is an interpretation provided. If a binary file is printed without interpretation, it looks like garbage. 30. Distinguish between a file type and a file extension. A file type is a description of the information contained in the file. A file extension is a part of the file name that follows a dot and identifies the file type. 31. What would happen if you give the name myFile.jpg to a text file? It depends on what application program you use to open the file. If you use a program that expects an image file, you would get an error. If you use a program that expects a text file, there would be no problem. 32. How can an operating system make use of the file types that it recognizes? If you click on a file on your desktop and the OS recognizes the file type, then the appropriate application program can be called to open the file. If you are writing Java programs using an integrated environment, then the files saved in the IDE are tagged and clicking on a file automatically opens the file in the IDE. 33. How does an operating system keep track of secondary memory? The OS maintains a table indicating which blocks of memory are free. The OS also maintains a table for each directory that contains infor mation about the files in that directory. 34. What does it mean to open and close a file? Operating systems keep a table of currently open files. The open oper ation enters the file into this table and places the file pointer at the beginning of the file. The close operation removes the file from the table of open files. 35. What does it mean to truncate a file? Truncating a file means that all the information on the file is erased but the administrative entries remain in the file tables. Occasionally, the truncate operation removes the information from the file pointer to the end. 36. Compare and contrast sequential and direct file access. Both sequential and direct file access find and access a record. In sequential access the file pointer begins at the beginning of the file and can only move in one direction. Thus sequential access is linear: The only record that can be accessed is the first or the one immediately following the last one accessed. In direct access the file pointer can be moved to any specific record and the data accessed from that place. 37. File access is independent of any physical medium. a. How could you implement sequential access on a disk? Sequential access always accesses the next record. You implement sequential access on a disk by not giving the user an access command that takes a record address as a parameter. b. How could you implement direct access on a magnetic tape? Each record on a magnetic tape is conceptually numbered from the first to the last. Keep a counter of which record was read last. When a user gives an access command to read a specific record, if the record number is beyond the last record read, then records are read and skipped until the correct record is found. If the record number comes before the last record read, the tape is rewound and records are read and skipped until the correct record is found. 38. What is a file protection mechanism? A file protection mechanism is one that an operating system imple ments that ensures the only valid users can access a particular file. 39. How does UNIX implement file protection? Unix implements file protection by associating with each file a 3x3 table in which the rows are Owner, Group, and World and the columns are Read, Write/Delete, and Execute. The contents of each cell in the table are boolean values meaning yes and no. For example, a yes in the cell (Owner, Execute) means that the owner of the file can execute it. A no in the cell (World, Write/Delete) means that permission to write or delete a file is not granted to anyone that is not the owner of the file or within a specified group. (Group is a list of those considered part of the group.) 40. Given the following file permission, answer these questions. Read Write/Delete Execute Owner Group World Yes Yes Yes Yes Yes No Yes No No a. Who can read the file? Any one can read the file. b. Who can write or delete the file? The owner and members of the group can write or delete the file. c. Who can execute the file? Only the owner can execute the file. d. What do you know about the content of the file? Because the owner has permission to execute the file, it must contain an executable program. 41. What is the minimum amount of information a directory must contain about each file? A directory must contain the file name, the file type, the address on disk where the file is stored, the current size of the file, and permission information. 42. How do most operating systems represent a directory? As a file. 43. Answer the following questions about directories. a. A directory that contains another directory is called what? parent directory b. A directory contained within another directory is called what? subdirectory c. The directory that is not contained in any other directory is called what? root directory d. The structure showing the nested directory organization is called what? directory tree e. Relate the structure in (d) to the binary tree data structure exam ined in Chapter 9. A directory tree and a binary tree are both hierarchical structures in which there is only one way to reach any subtree. The root direc tory is equivalent to the root of the binary tree. In a binary tree, each node can have none, one, or two child nodes. In a directory tree, each node can have any number of subdirectories. 44. What is the directory called in which you are working at any one moment? working directory 45. What is a path? A path is a text string that specifies the location of a file or subdirec tory. 46. Distinguish between an absolute path and a relative path. An absolute path is a path that begins at the root directory and includes all successive subdirectories. A relative path is a path that begins at the current working directory and includes all successive subdirectories. 47. Show the absolute path to each of the following files or directories using the directory tree shown in Figure 11.4: a. QTEffects.qtx C:\WINDOWS\System\QuickTime\QTEffects.qtx b. brooks.mp3 C:\My Documents\downloads\brooks.mp3 c. Program Files C:\Program Files d. 3dMaze.scr C:\WINDOWS\System\3dMaze.scr e. Powerpnt.exe C:\Program Files\MS Office\Powerpnt.exe 48. Show the absolute path to each of the following files or directories using the directory tree shown in Figure 11.5: a. tar /bin/tar b. access.old /etc/mail/access.old c. named.conf /etc/named.conf d. smith /home/smith e. week3.txt /home/smith/reports/week1.txt f. printall /home/jones/utilities/printall 49. Assuming the current working directory is C:\WINDOWS\System, give the relative path name to the following files or directories using the directory tree shown in Figure 11.4: a. QTImage.qtx QuickTime\QTImage.qtx b. calc.exe ..\calc.exe c. letters ..\..\My Documents\letters d. proj3.java ..\..\My Documents\csc101\proj3.java e. adobep4.hlp adobep4.hlp f. WinWord.exe ..\..\Program Files\MS Office\Winword.exe 50. Show the relative path to each of the following files or directories using the directory tree shown in Figure 11.5. a. localtime when working directory is the root directory /etc/localtime b. localtime when the working directory is etc localtime c. printall when the working directory is utilities printall d. week1.txt when the working directory is man2 ../reports/week1.txt 51. What is the worst bottleneck in a computer system? Transferring data to and from secondary memory is the worst bottle neck. 52. Why is disk scheduling concerned more with cylinders than with tracks and sectors? Seek time (the time to find the right cylinder) is more time consuming than locating which track or which sector, so seek time is the time to minimize. 53. Name and describe three disk-scheduling algorithms. First-come, first-serve (FCSC): The requests are handled in the order in which they are generated. Shortest seek time first (SSTF): The request closest to the read/write heads is handled next. SCAN: The read/write heads move back and forth handling the closest in the direction in which they are moving. Use the following list of cylinder requests in Exercises 54–56. They are listed in the order in which they were received. 40, 12, 22, 66, 67, 33, 80 54. List the order in which these requests are handled if the FCFS algorithm is used. Assume that the disk is positioned at cylinder 50. 40, 12, 22, 66, 67, 33, 80 55. List the order in which these requests are handled if the SSTF algorithm is used. Assume that the disk is positioned at cylinder 50. 40, 33, 22, 12, 66, 67, 80 56. List the order in which these requests are handled if the SCAN algorithm is used. Assume that the disk is positioned at cylinder 50 and the read/write heads are moving toward the higher cylinder numbers. 66, 67, 80, 40, 33, 22, 12 57. Explain the concept of starvation. In the SSTF algorithm, it is possible for some requests never to be serv iced because requests closer to the read/write heads keep being issued.