《计算机专业英语》霍宏涛Chapter3.

1、Professional Englishin Computer Field内容:正文Balanced Tree Data StructuresQuicksort阅读材料Linked ListNew Algorithms for Maintaining All-Pairs ShortestPathsChapt1Balanced Tree Data Structures Computer sizes and power Supercomputer and Main frame Minicomputer Workstatio n Personal computerKeyWordsred-blackt

2、reebr红黑树， 是一种平衡树 分支因子adj.趋近最差状况单遍，单次adj.同样功能的 二叉树1Terabyte=1024GB支付，支出Notes: For example, a b-tree with a height of 2 and a branchingfactor of 1001 can store over one billion keys but requiresat most two disk accesses to search for any node.例如，一个高度为 2、分支因子为 1001 的树可以储存高达十亿个键， 而最多只需要访问磁盘两次就可以访问到任意一个节

3、点。 If t is this minimization factor, every node must have atleast t 1 keys. Under certain circumstances, the rootnode is allowed to violate this property by having fewerthan t 1 keys.如果 t 是最小因子，每个节点都必须有至少 t-i 个键。在特定的环境 下，根节点的键少于 t-i 并不违反这个属性。Notes: If the node is not full prior to the insertion, no

4、specialaction is required; however, if the node is full, the nodemust be split to make room for the new key.如果结点在插入前不满，则不需要做特殊处理。但是，如果结 点是满的，为了给新的键提供空间，就需要将结点拆分。 Since each access to a node may correspond to a costlydisk access, it is desirable to avoid the second pass byensuring that the parent nod

5、e is never full. To accomplishthis, the presented algorithm splits any full no desencountered while descendi ng the tree.由于每一次对结点的存取都可能导致高成本的磁盘存取，因此应该 尽量使父结点永不满以避免第二次访问。为了达到这个目的，以上 算法在向下遍历树结构时拆分所有已满的结点。2 Quicksort378 | 5 219 5 4378421|9 5|5|342)7819 5 |5|厂二34215798 5 |342 | 15 | 5 | 9 87Key Words so

6、rting algorithm quadratic divide and conquer strategy pivot partiti on pseudocode sequentially auxiliary nested call排序算法 adj.二次的 分而治之 n.中心点n.分割n.伪码 adv.连续地 adj.辅助的 嵌套调用n.循环，递归n.定理v.产生v.（为作出决定而）掷硬币 adv.微不足道地n.排列v 修正不在原来的地方n.不同版本Notes: The additional memory allocations required can alsodrastically imp

7、act speed and cache performance inpractical implementations.在实现中，所需的额外内存分配也会严重的影响速度和 缓存的性能。 A new thread is started as soon as a sublist is available forit to work on and it does not communicate with otherthreads. When all threads complete, the sort is done.当一个子列表可用时，一个新的线程就会被立即启动去 处理它，并且这个线程不会与其他线程

8、交换信息当所 有线程都结束后，排序完成。Key Words recurrence theorem yield flip a coin infinitesimally permutation elid no t-in-place variantReading Material 1 Linked ListI，2| 4,99| 4 刃| 亠枢lBIIReading Material 1 Linked Listin IHZT3HZTHAI H81cI rvode nodemxt twh，next, nextnrn-ISoderwnMddnodidpmv doln mrfeXioode wde nesW

9、 node next.nextnodeReading Material 2New Algorithms for MaintainingAll-Pairs Shortest PathsExercises1.For an ideal balanced tree with n nodes in it, the height will be2.Unlike a binary-tree, each node of a b-tree may have a variable numberof_and_.3.A b-tree has a minimum number of allowable children

10、 for each nodeknown as the_ .4.For n1, the height of an n-key b-tree T with minimum degree of f will beno more than_ .5.Theoperation creates an empty b-tree byallocating a new root node that has no keys and is a leaf node 6.Quicksort sorts by employing a divide and conquer strategy to divide a_ into

11、 two_ 7.The disadvantage of the simple version above is that itrequires_ extra storage space, which is as bad as mergesort.8.The version of quicksort with_ partitioning uses onlyconstant additional space before making any recursive call.9.Once we know a worst-case O(n) selection algorithm is availab

12、le, wecan 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:1.Describe the structure of B-Trees 2.List several operations on B-Trees 3.Give the algorithm of B-Tree-Search operation and its timecomplexit y.4.Why there are two kinds of algorithms for inserting a node into aB-Tree?5.Give a strategy to avoid the concurrent access to B-trees 6.Briefly describe the ste