《计算机专业英语 教学课件 ppt 作者 霍宏涛 Chapter3》由会员分享，可在线阅读，更多相关《计算机专业英语 教学课件 ppt 作者 霍宏涛 Chapter3（15页珍藏版）》请在金锄头文库上搜索。
1、Professional English in Computer Field,Chapter Three Data Structure,内容,正文 Balanced Tree Data Structures Quicksort 阅读材料 Linked List New Algorithms for Maintaining All-Pairs Shortest Paths,1 Balanced Tree Data Structures,Computer sizes and power Supercomputer and Mainframe Minicomputer Workstation Per
2、sonal computer,Key Words,red-black tree 红黑树, 是一种平衡树 branching factor 分支因子 branchiness n. 分支性 asymptotic adj. 趋近 worst case 最差状况 single pass 单遍，单次 analogous adj. 同样功能的 binary tree 二叉树 inventory n. 目录、存货清单 terabyte 1 Terabyte=1024 GB disburse 支付,支出,Notes,For example, a b-tree with a height of 2 and a
3、branching factor of 1001 can store over one billion keys but requires at most two disk accesses to search for any node. If t is this minimization factor, every node must have at least t - 1 keys. Under certain circumstances, the root node is allowed to violate this property by having fewer than t -
4、1 keys.,例如，一个高度为2、分支因子为1001的树可以储存高达十亿个键， 而最多只需要访问磁盘两次就可以访问到任意一个节点。,如果t是最小因子, 每个节点都必须有至少t-1个键。在特定的环境 下，根节点的键少于t-1并不违反这个属性。,Notes,If the node is not full prior to the insertion, no special action is required; however, if the node is full, the node must be split to make room for the new key. Since each
5、 access to a node may correspond to a costly disk access, it is desirable to avoid the second pass by ensuring that the parent node is never full. To accomplish this, the presented algorithm splits any full nodes encountered while descending the tree.,如果结点在插入前不满，则不需要做特殊处理。但是，如果结 点是满的，为了给新的键提供空间，就需要将
6、结点拆分。,由于每一次对结点的存取都可能导致高成本的磁盘存取，因此应该 尽量使父结点永不满以避免第二次访问。为了达到这个目的，以上 算法在向下遍历树结构时拆分所有已满的结点。,2 Quicksort,Key Words,sorting algorithm 排序算法 quadratic adj. 二次的 divide and conquer strategy 分而治之 pivot n. 中心点 partition n. 分割 pseudocode n. 伪码 sequentially adv. 连续地 auxiliary adj. 辅助的 nested call 嵌套调用,Key Words,r
7、ecurrence n. 循环,递归 theorem n. 定理 yield v. 产生 flip a coin v. (为作出决定而)掷硬币 infinitesimally adv. 微不足道地 permutation n. 排列 elid v. 修正 not-in-place 不在原来的地方 variant n. 不同版本,Notes,The additional memory allocations required can also drastically impact speed and cache performance in practical implementations.
8、A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done.,在实现中，所需的额外内存分配也会严重的影响速度和 缓存的性能。,当一个子列表可用时，一个新的线程就会被立即启动去 处理它，并且这个线程不会与其他线程交换信息.当所 有线程都结束后，排序完成。,Reading Material 1 Linked List,Read
9、ing Material 1 Linked List,Reading Material 2 New Algorithms for Maintaining All-Pairs Shortest Paths,Exercises,For an ideal balanced tree with n nodes in it, the height will be _. Unlike a binary-tree, each node of a b-tree may have a variable number of _ and _. A b-tree has a minimum number of all
10、owable children for each node known as the _. For n1, the height of an n-key b-tree T with minimum degree of t will be no more than _. The _ operation creates an empty b-tree by allocating a new root node that has no keys and is a leaf node. Quicksort sorts by employing a divide and conquer strategy
11、 to divide a _ into two _. The disadvantage of the simple version above is that it requires_ extra storage space, which is as bad as mergesort. The version of quicksort with _ partitioning uses only constant additional space before making any recursive call. Once we know a worst-case O(n) selection
12、algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a _ with worst-case O(n log n) running time.,questions,Describe the structure of B-Trees. List several operations on B-Trees. Give the algorithm of B-Tree-Search operation and its time co
13、mplexity. Why there are two kinds of algorithms for inserting a node into a B-Tree? Give a strategy to avoid the concurrent access to B-trees. Briefly describe the steps of quicksort algorithm. Give the algorithm of quicksort in simple pseudocode. Please describe the disadvantage of the simple version quicksort. What does the space used by quicksort depend on?,
