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.