Microsoft PowerPoint

Size: px

Start display at page:

Download "Microsoft PowerPoint"

允平浦
4 years ago
Views:

1 书面作业讲解 TC 第 10.1 节练习 TC 第 10.2 节练习 TC 第 10.3 节练习 4 5 TC 第 10.4 节练习 TC 第 10 章问题 3 1

2 TC 第节练习 4 Rewrite ENQUEUE to detect overflow. if (Q[Q.tail]!= null) 对不对? if (Q.tail == Q.head) Qhead) 有没有问题? 不能区分队列是满还是空总是预留一个空位置 if (Q.tail%Q.length+1 == Q.head) overflow if (Q.head == Q.tail) underflow if ((Q.tail+1)%Q.length == Q.head) overflow 对不对? 2

3 TC 第节练习 5 deque_from_tail x = Q[Q.tail]; Q.tail ;... 对不对? 3

4 TC 第节练习 6 方法 1 方法 2 4

5 TC 第 10.2 节练习 1 DELETE p = L.head; while hl (p.next!= x) { p = p.next; } 对不对? p = L.head; while (p!=x && p!=null) { p = pnext; p.next; } 5

6 TC 第 10.2 节练习 6 Support UNION in O(1) time using a suitable list data structure. s1.head.prev = s2.head; s2.head.prev = s1.head; s = s1.head; p p return s; 对不对? s2.head 2h s1.head n p n p np n p s.head = s1.head; s1.tail.next = s2.head; s.tail = s2.tail; 6

7 TC 第 10.3 节练习 4 5 Using the first m index locations in the multiple array l representation Hint: Use the array implementation of a stack. 插入 : 分配第 m+1 个位置删除 : 如果删除的不是第 m 个位置, 与第 m 个位置交换 COMPACTIFY LIST: 搜索和移位 7

8 TC 第 10.4 节练习 3 4 Nonrecursive traversal, using a stack push(root); while(stack is not empty) { curr = pop(); print(curr); if (curr.left!= null) push(curr.left); if (curr.right!= null) push(curr.right); } loop invariant 是什么? Arbitrary rooted tree, using the left child, right sibling representation: 与 binary tree 一样处理 8

9 TC 第 10 章问题 3 CLS:( 跳 )) 走 (( 跳 )) 走 CLS :( 跳 )( 跳 ) 走走 CLS 的总里程 = 最后一次成功的跳 + 之后所有的走 ( while 执行次数 ) (a) CLS 执行 t 次 while 之后, 有三种结果 CLS 没找到 (Line 10):CLS 执行 t 次 for t 次 while CLS 走到了 (Line 11):CLS 执行 t 次 for t 次 while CLS 跳到了 (Line 7):CLS 执行 t 次 for 9

10 TC 第 10 章问题 3 ( 续 ) TC 第 10 章问题 3 ( 续 ) (b) E=E(for+while)=E(for)+E(while)=O(t)+E(X t )=O(t+E(X t )) n t n d d r (c) r r t r t r t t n r r X P r X P r X rp X E

11 教材答疑和讨论 TC 第 11 章 CS 第 5 章第 5 节 11

12 问题 1:dictionary dictionary 是什么? 它要求具备哪些操作? Insert Search Delete 它有哪些用途? 你能举出一些实际例子吗? 12

13 问题 1:dictionary ( 续 ) direct address table 是如何实现 dictionary 的? 它有哪些优缺点?( 时间空间实现难度 ) 13

14 问题 1:dictionary ( 续 ) hash table 与 direct address table 的本质区别是什么? 因此, 它有哪些相对的优缺点?( 时间空间实现难度 ) 14

15 以下我们只讨论 simple uniform hashing 15

16 问题 2:collision expected number of items per location 16

17 问题 2:collision ( 续 ) expected number of empty locations 17

18 问题 2:collision ( 续 ) expected number of collisions 18

19 问题 3:collision resolution chaining 是如何解决 collision 的? insert search delect 的运行时间分别是多少? 因此, 它有哪些优缺点?( 时间空间实现难度 ) 19

20 问题 3:collision resolution ( 续 ) open addressing 与 chaining 的本质区别是什么? 因此, 它有哪些相对的优缺点?( 时间空间实现难度 ) 20

21 问题 3:collision resolution ( 续 ) open addressing 的三种方法的基本思路分别是什么? linear probing quadratic probing double hashing 它们在效果上有什么区别? 21

22 问题 3:collision resolution ( 续 ) chaining 和 open addressing 的运行时间主要取决于什么? 因此, 当速度变得很慢时, 你有什么对策? 22

23 问题 3:collision resolution ( 续 ) perfect hashing 与 chaining 的本质区别是什么? search 的运行时间是多少? 因此, 它有哪些相对的优缺点?( 时间空间实现难度 ) 23

24 如果 resolution 是对 collision 的治疗, 那么如何尽可能预防 collision 呢? 24

25 问题 4:hash function 你觉得一个好的 hash function 应该具有哪些特点? Satisfies (approximately) the assumption of simple uniform hashing. Depends on all the bits of the key. Runs fast. 25

26 问题 4:hash function ( 续 ) 如果有人跟你捣乱, 构造出的 key 总是引发 collision, 你准备怎么应对? universal hashing: to choose the hash function randomly in a way that is independent of the keys that are actually going to be stored 26

演算法導入、ソート、データ構造、ハッシュ

演算法導入、ソート、データ構造、ハッシュ培訓 - 1 演算法導入ソートデータ構造ハッシュ演算法導入ソートデータ構造ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI