当前位置:首页 >> 理学 >>

计算机科学导论原书第二版答案第十一章


CHAPTER 11

Data Structures
(Solutions to Practice Set)

Review Questions
1. Arrays, records, and linked lists are three types of data structures discussed in this chapter. 2. All elements of an array in most languages are of the same type. Elements of a record can be of the same or different types but all elements must be related to each other. 3. Elements of an array are contiguous in memory and can be accessed by use of an index. Elements of a linked list are stored in nodes that may be scattered throughout memory and can only be accessed via the access functions for the list (i.e., the address of a specific node returned by a search function). 4. Using indices in a pair of brackets, rather than subscripts, allows us to use variable for these indices. 5. An array is stored contiguously in memory. Most computers use row-major storage to store a two-dimension array. 6. A field is the smallest element of named data that has meaning. 7. The fields of a node in a linked list are the data and a pointer (address of) the next node. 8. The pointer identifies the next element in the linked list. 9. We use the head pointer to point to the first node in the linked list. 10. The pointer in the last node of a linked list is a null pointer, which means it points to nowhere.

Multiple-Choice Questions
11. d 17. a 12. b 18. a 13. c 19. d 14. b 20. b 15. c 16. d

1

2

Exercises
21. Algorithm S11.21 shows the routine in pseudocode that compares two arrays. Algorithm S11.21 Exercise 21
Algorithm: CompareArrays(A, B) Purpose: Test if every element in array A equals to its corresponding element in array B Pre: Arrays A and B of 10 integers Post: None Return: true or false { i ← 1 while (i ≤ 10) { if A[ i ] ≠ B[ i ] return false // A is not equal to B i ← i + 1 } return true // A is equal to B }

22. Algorithm S11.22 shows the routine in pseudocode that reverses an array. Algorithm S11.22 Exercise 22
Algorithm: ReverseArray(A, n) Purpose: Reverse the elements of an array Pre: Arrays A with n elements Post: None Return: { i ← 1 j ← n while (i < j) { Temp ← A[ j ] A [ j ] ← A[ i ] A[ i ] ← Temp i ← i+1 j ← j?1 } }

23. Algorithm S11.23 shows the routine in pseudocode that prints an array.

3

Algorithm S11.23 Exercise 23
Algorithm: PrintArray (A, r, c ) Purpose: Print the contents of 2-D array Pre: Given Array A, and values of r (number of rows) and c (number of columns) Post: Print the values of the elements of A Return: { i ← 1 while (i ≤ r) { j ← 1 while (j ≤ c) { print A [ i ][ j ] j ← j+1 } i ← i+1 } }

24. Algorithm 11.24 shows the sequential search routine in pseudocode (see Chapter 8). Note that we perform sequential search on unsorted arrays. In the beginning, we set the flag to false. If the search finds the target in the array, it sets the flag to true, moves out of the loop. It returns i (location of the target) and the value of the flag (true). After checking the entire list, if the search does not find the value, it moves out of the loop and returns value of the i as n + 1 and the value of the flag (false). Algorithm S11.24 Exercise 24
Algorithm: SequentialSearchArray(A, n, x) Purpose: Apply a sequential search on an array A of n elements Pre: A, n, x // x is the target we are searching for Post: None Return: flag, i { flag ← false i ← 1 while ((i ≤ n) or (flag = false)) { if (A [ i ] = x) flag ← true i ← i+1 } return (flag, i) // If x is not found, flag is false }

25. Algorithm S11.25 shows the binary search routine in pseudocode (see Chapter 8). Note that we perform the binary search on sorted array.

4

Algorithm S11.25 Exercise 25
Algorithm: BinarySearchArray(A, n, x) Purpose: Apply a binary search on an array A of n elements Pre: A, n, x // x is the target we are searching for Post: None Return: flag, i { flag ← false first ← 1 last ← n while (first ≤ last) { mid = (first + last) / 2 if (x < A [mid]) Last ← mid ? 1 if (x > A [mid]) first ← mid + 1 if (x = A [mid]) first ← Last + 1 // x is found } if (x > A [mid]) i = mid + 1 if (x ≤ A [mid]) i = mid if (x = A [mid]) flag ← true return (flag, i) } // If flag is true, it means x is found and i is its location. // If flag is false, it means x is not found; i is the location where the target supposed to be.

26. Algorithm 11.26 shows the insert routine in pseudocode. Note that this algorithm first calls BinarySearch algorithm (Algorithm S11.25) and then ShiftDown algorithm (Algorithm S11.26b). Algorithm S11.26a Exercise 26
Algorithm: InsertSortedArray(A, n, x) Purpose: Insert an element in a sorted array Pre: A, n, x Post: None Return: A { {flag, i} ← BinarySearch (A, n, x) if (flag = true) { print (x is already in the array) return } ShiftDown (n, A, i) A[ i ] ← x return }

// x is the value we want to insert

// Call binary search algorithm // x is already in A

// Call shift down algorithm

5

Algorithm S11.26b Exercise 26
Algorithm: ShiftDown(A, n, i) Purpose: Shift all elements starting from element with index i one place Pre: A, n, i Post: None Return: { j←n while ( j > i ? 1) { A [ j + 1] ← A [ j ] j←j?1 } }

27. Algorithm S11.27a shows the delete routine in pseudocode. Note that this algorithm calls BinarySearch algorithm (Algorithm S11.25) and ShiftUp algorithm (Algorithm S11.27b). Algorithm S11.27a Exercise 27
Algorithm: DeleteSortedArray(A, n, x) Purpose: Delete an element from a sorted array Pre: A, n, x Post: None Return: { {flag, i} ← BinarySearch (A, n, x) if (flag = false) { print (x is not in the array) return } ShiftUp (A, n, i) return }

// x is the value we want to delete

// Call binary search algorithm // x is not in A

// call shift up algorithm // call shift up algorithm

Algorithm S11.27b Exercise 27
Algorithm: ShiftUp (A, n, i) Purpose: Shift up all elements one place from the last element up to element with index i. Pre: A, n, i Post: None Return: A { j←i

6

Algorithm S11.27b Exercise 27
while ( j ≤ n + 1) { A [ j ] ← A [ j + 1] j←j+1 } return }

28. Algorithm S11.28 shows the routine in pseudocode that multiplies each element of an array by a constant. Algorithm S11.28 Exercise 28
Algorithm: MultiplyConstant(A, n, C) Purpose: Multiply all elements of an array by a constant Pre: A, n, C // C is the constant Post: None Return: { i←1 while (i ≤ n) { A[i] ← C × A[i] i←i+1 } }

29. Algorithm S11.29 shows the routine in pseudocode that adds two fractions. Algorithm S11.29 Exercise 29
Algorithm: AddFraction(Fr1, Fr2) Purpose: Add two fractions Pre: Fr1, Fr2 // Assume denominators have nonzero values Post: None Return: The resulting fraction (Fr3) { x ← gcd (Fr1.denom, Fr2.denom) // Call gcd (see Exercise 8.57) y ← (Fr1.denom × Fr2.denom) / x // y is the least common denominator Fr3.num ← (y / Fr1.denom) × Fr1.num + (y / Fr2.denom) × Fr2.num Fr3.denom ← y z ← gcd (Fr3.num, Fr3.denom) // Simplifying the fraction Fr3.num ← Fr3.num / z Fr3.denom ← Fr3.denom / z return (Fr3) }

7

30. Algorithm S11.30 shows the routine in pseudocode that subtract two fractions. To subtract, we change the sign of Fr1 and then add it to Fr2 by calling AddFraction algorithm (Algorithm S11.29). Algorithm S11.30 Exercise 30
Algorithm: SubtractFraction(Fr1, Fr2) Purpose: Subtract two fractions (Fr2 ? Fr1) Pre: Fr1, Fr2 // Assume denominators have nonzero values Post: None Return: Fr3 { Fr1.num ← ? Fr1.num // Change the sign of the first fraction Fr3 ← AddFraction (Fr1, Fr2) // Call AddFraction return (Fr3) }

31. Algorithm S11.31 shows the routine in pseudocode that multiplies two fractions. Algorithm S11.31 Exercise 31
Algorithm: MultiplyFraction (Fr1, Fr2) Purpose: Multiply two fractions Pre: Fr1, Fr2 // Assume denominators with nonzero values Post: None Return: Fr3 { Fr3.num ← Fr1.num × Fr2.num Fr3.denom ← Fr1.denom × Fr2.denom z ← gcd (Fr3.num, Fr3.denom) Fr3.num ← Fr3.num / z Fr3.denom ← Fr3.denom / z return (Fr3) } // Simplifying the fraction

32. Algorithm S11.32 shows the routine in pseudocode that divide two fractions. First, we inverse the second fraction and then multiply them by calling MultiplyFraction algorithm (Algorithm S11.31) Algorithm S11.32 Exercise 32
Algorithm: DivideFraction (Fr1, Fr2) Purpose: Divide two fractions (Fr1 ÷ Fr2) Pre: Fr1, Fr2 Post: None Return: Fr3

// Assume nonzero values

8

Algorithm S11.32 Exercise 32
{ Temp ← Fr2.denom Fr2.denom ← Fr2.num Fr2.num ← Temp Fr3 ← MultiplyFraction (Fr1, Fr2) return (Fr3) }

// Call MultiplyFraction

33. Figure S11.33 shows the linked list of records. Figure S11.33 Exercise 33
id name Data grade Link

34. SearchLinkedList algorithm returns pre = null, cur pointing to the only node, and flag = true. Since pre = null, the action is list ← (*cur).link, which is equivalent to list ← null. The result is an empty list as shown in Figure S11.34. Figure S11.34 Exercise 34
(*cur).link list list pre cur (*cur).link Action pre cur list (*cur).link

35. Since list = null, the SearchLinkedList algorithm performs new ← list. This creates a list with a single node. 36. Algorithm S11.36 shows the routine in pseudocode for building a linked. The routing uses the InsertLinkedList algorithm. Algorithm S11.36 Exercise 36
Algorithm: BuildLinkedList(data records) Purpose: Build a linked list from scratch Pre: given list of data records Post: None Return: list, which is a pointer pointing to the first node { list ← null

9

Algorithm S11.36 Exercise 36
while (more data records) { InsertLinkedList (list, next record.key, next record) } return (list) }

37. Algorithm S11.37 shows the routine for finding the average of a linked list. Algorithm S11.37 Exercise 37
Algorithm: LinkedListAverage (list) Purpose: Evaluate average of numbers in a linked list Pre: list Post: None Return: Average value

{
counter ← 1 sum ← 0 walker ← list while (walker ≠ null)

{
sum ← sum + (*walker).data walker ← (*walker).link counter ← counter + 1

}
average ← sum / counter return average

} 38. Figure S11.38 shows the list of scores before and after scores ← (*scores).link statement. The statement drops the first node. This exercise shows that we should never move the head pointer. If we do so, we lose a part of our list. Figure S11.38 Exercise 38
*scores scores *scores scores (*scores).link Before

After

10

39. Figure S11.39a shows that if pre is not null, the two statements cur ← (*cur).link and pre ← (*pre).link move the two pointers together to the right. In this case the two statements are equivalent to the ones we discussed in the text. Figure S11.39a Exercise 39
(*pre).link *cur *pre (*cur).link

Before
pre cur

After
pre cur

However, the statement pre ← (*pre).link does not work when pre is null because, in this case, (*pre).link does not exist (Figure S11.39b). For this reason, we should avoid using this method. Figure S11.39b Exercise 39
list *cur (*cur).link pre cur


相关文章:
计算机科学导论原书第二版答案第十一章.pdf
计算机科学导论原书第二版答案第十一章 - CHAPTER 11 Data Str
计算机科学导论原书第二版答案第十二章.pdf
计算机科学导论原书第二版答案第十二章 - CHAPTER 12 Abstract
计算机科学导论原书第二版答案第十三章.pdf
计算机科学导论原书第二版答案第十三章 - CHAPTER 13 File Str
计算机科学导论原书第二版答案第十四章.pdf
计算机科学导论原书第二版答案第十四章 - CHAPTER 14 Database
计算机科学导论原书第二版答案第二章.pdf
计算机科学导论原书第二版答案第 - CHAPTER 2 Number Sys
计算机科学导论原书第二版答案第十五章.pdf
计算机科学导论原书第二版答案第十五章 - CHAPTER 15 Data Com
计算机科学导论原书第二版答案第十八章.pdf
计算机科学导论原书第二版答案第十八章 - CHAPTER 18 Artifici
计算机科学导论原书第二版答案第七章.pdf
计算机科学导论原书第二版答案第七章 - CHAPTER 7 Operating
计算机科学导论原书第二版答案第十七章.pdf
计算机科学导论原书第二版答案第十七章 - CHAPTER 17 Theory o
计算机科学导论答案.doc
计算机科学导论答案_哲学_高等教育_教育专区。计算机科学导论答案 2011 年计算机导论修订第二版课后练习答案 第一章 一、简答题 1、什么是计算机? 计算机系统是一种...
计算机科学导论第2版答案.doc
第1章 概述习题(答案) 一.选择题 1. D 6. A 2. B 7. B 3. CD 8...计算机科学导论原书第二... 7页 1下载券 计算机科学导论第13章参... ...
计算机科学导论原书第二版答案第十六章.pdf
计算机科学导论原书第二版答案第十六章 - CHAPTER 16 Security
计算机科学导论课本答案(完整版).doc
第1章 概述 习题(答案 习题 答案) 答案一.选择题 1. D 6. A 2. B 7...计算机科学导论原书第二... 4页 1下载券 计算机科学导论原书第二... ...
计算机科学导论习题答案.pdf
计算机科学导论习题答案_IT/计算机_专业资料。计算机科学导论习题答案 原书第二版 英文 CHAPTER 1 Introduction (Solutions to Practice Set) Review Questions 1. ...
计算机科学导论第2章-答案.doc
计算机科学导论第2章-答案 - 第 2 章 计算机体系结构与组织 习题(答案) 一. 选择题 1.D 5.C 6.B 10.C 11.A 15.A 16.A 17.B 18.A 12.C 13....
计算机科学导论 (第二版 清华大学出版社)第12章 社会和....doc
计算机科学导论 (第二版 清华大学出版社)第12章 社会和职业问题(答案)_工学_高等教育_教育专区。第二版 清华大学出版社 第12 章 社会和职业问题习题(答案) ...
大学计算机基础课课本计算机科学导论课后答案.doc
大学计算机基础课课本计算机科学导论课后答案_理学_高等教育_教育专区。自己综合汇总的计算机科学导论第二版课后答案 以下答案多方资料做的,仅供参考。 第一章 绪论 ...
计算机科学导论习题答案.doc
计算机科学导论习题答案 - 第1章 概述 习题(答案) 一.选择题 1. D 2. B 3. CD 6. A 7. B 8. B 4. C 5. ABC 9. ABCD 10. ABCDE ...
计算机科学导论第三版答案.doc
计算机科学导论第版答案_电脑基础知识_IT/计算机_专业资料。第1章 概述 习题...答案略。 第 11 章 人机交互 习题(答案) 一.选择题 1. ABC 6. A 2. ...
2016下《计算机科学导论》第2次作业答案.doc
2016下《计算机科学导论第2次作业答案 - 《计算机科学导论第 2 次作业答案 (第 8 章第 15 章) 一、选择题 1.与批处理系统相比较,分时系统的最大...