下载文档原格式
Chapter11:Amortized Analysis11.1When the number of trees after the insertions is more than the number before.11.2Although each insertion takes roughly log N ,and each DeleteMin takes2log N actualtime,our accounting system is charging these particular operations as2for the insertion and3log N −2for the DeleteMin. The total time is still the same;this is an accounting gimmick.If the number of insertions and DeleteMins are roughly equivalent,then it really is just a gimmick and not very meaningful;the bound has more significance if,for instance,there are N insertions and O (N / log N )DeleteMins (in which case,the total time is linear).11.3Insert the sequence N ,N +1,N −1,N +2,N −2,N +3,...,1,2N into an initiallyempty skew heap.The right path has N nodes,so any operation could takeΩ(N )time. 11.5We implement DecreaseKey(X,H)as follows:If lowering the value of X creates a heaporder violation,then cut X from its parent,which creates a new skew heap H 1with the new value of X as a root,and also makes the old skew heap H smaller.This operation might also increase the potential of H ,but only by at most log N .We now merge H andH 1.The total amortized time of the Merge is O (log N ),so the total time of theDecreaseKey operation is O (log N ).11.8For the zig −zig case,the actual cost is2,and the potential change isR f ( X )+ R f ( P )+ R f ( G )− R i ( X )− R i ( P )− R i ( G ).This gives an amortized time bound ofAT zig −zig =2+ R f ( X )+ R f ( P )+ R f ( G )− R i ( X )− R i ( P )− R i ( G )Since R f ( X )= R i ( G ),this reduces to=2+ R f ( P )+ R f ( G )− R i ( X )− R i ( P )Also,R f ( X )> R f ( P )and R i ( X )< R i ( P ),soAT zig −zig <2+ R f ( X )+ R f ( G )−2R i ( X )Since S i ( X )+ S f ( G )< S f ( X ),it follows that R i ( X )+ R f ( G )<2R f ( X )−2.ThusAT zig −zig <3R f ( X )−3R i ( X )11.9(a)Choose W (i )=1/ N for each item.Then for any access of node X ,R f ( X )=0,andR i ( X )≥−log N ,so the amortized access for each item is at most3log N +1,and the net potential drop over the sequence is at most N log N ,giving a bound of O (M log N + M + N log N ),as claimed.(b)Assign a weight of q i /M to items i .Then R f ( X )=0,R i ( X )≥log(q i /M ),so theamortized cost of accessing item i is at most3log(M /q i )+1,and the theorem follows immediately.11.10(a)To merge two splay trees T 1and T 2,we access each node in the smaller tree andinsert it into the larger tree.Each time a node is accessed,it joins a tree that is at leasttwice as large;thus a node can be inserted log N times.This tells us that in any sequence of N −1merges,there are at most N log N inserts,giving a time bound of O (N log2N ).This presumes that we keep track of the tree sizes.Philosophically,this is ugly since it defeats the purpose of self-adjustment.(b)Port and Moffet[6]suggest the following algorithm:If T 2is the smaller tree,insert itsroot into T 1.Then recursively merge the left subtrees of T 1and T 2,and recursively merge their right subtrees.This algorithm is not analyzed;a variant in which the median of T 2is splayed to the rootfirst is with a claim of O (N log N )for the sequence of merges.11.11The potential function is c times the number of insertions since the last rehashing step,where c is a constant.For an insertion that doesn’t require rehashing,the actual time is 1,and the potential increases by c ,for a cost of1+ c .If an insertion causes a table to be rehashed from size S to2S ,then the actual cost is 1+ dS ,where dS represents the cost of initializing the new table and copying the old table back.A table that is rehashed when it reaches size S was last rehashed at size S / 2, so S / 2insertions had taken place prior to the rehash,and the initial potential was cS / 2.The new potential is0,so the potential change is−cS / 2,giving an amortized bound of(d − c / 2)S +1.We choose c =2d ,and obtain an O (1)amortized bound in both cases.11.12We show that the amortized number of node splits is1per insertion.The potential func-tion is the number of three-child nodes in T .If the actual number of nodes splits for an insertion is s ,then the change in the potential function is at most1− s ,because each split converts a three-child node to two two-child nodes,but the parent of the last node split gains a third child(unless it is the root).Thus an insertion costs1node split,amor-tized.An N node tree has N units of potential that might be converted to actual time,so the total cost is O (M + N ).(If we start from an initially empty tree,then the bound is O (M ).)11.13(a)This problem is similar to Exercise3.22.Thefirst four operations are easy to imple-ment by placing two stacks,S L and S R ,next to each other(with bottoms touching).We can implement thefifth operation by using two more stacks,M L and M R (which hold minimums).If both S L and S R never empty,then the operations can be implemented as follows:Push(X,D):push X onto S L ;if X is smaller than or equal to the top of M L ,push X onto M L as well.Inject(X,D):same operation as Push ,except use S R and M R .Pop(D):pop S L ;if the popped item is equal to the top of M L ,then pop M L as well.Eject(D):same operation as Pop ,except use S R and M R .FindMin(D):return the minimum of the top of M L and M R .These operations don’t work if either S L or S R is empty.If a Pop or E j ect is attempted on an empty stack,then we clear M L and M R .We then redistribute the elements so that half are in S L and the rest in S R ,and adjust M L and M R to reflect what the state would be.We can then perform the Pop or E j ect in the normal fashion.Fig. 11.1shows a transfor-mation.Define the potential function to be the absolute value of the number of elements in S L minus the number of elements in S R .Any operation that doesn’t empty S L or S R can3,1,4,6,5,9,2,61,2,63,1,4,65,9,2,6 1,4,65,2S L S R M L RL S RM L M R Fig.11.1.increase the potential by only1;since the actual time for these operations is constant,so is the amortized time.To complete the proof,we show that the cost of a reorganization is O (1)amortized time. Without loss of generality,if S R is empty,then the actual cost of the reorganization is | S L | units.The potential before the reorganization is | S L | ;afterward,it is at most1. Thus the potential change is1− | S L | ,and the amortized bound follows.。
第11章数据结构的传输和XDR标准在复杂的网络应用中，在客户进程和服务器进程间可能需要传递一些复杂的数据结构，这些数据结构可能用于控制进程的动作或者返回进程处理的结果。
本章首先说明在网络中传送数据结构中，存在的问题。
比如各种数据类型的不同处理、指针的传递等等。
接着我们示例一个使用我们自己定义的简单规则进行数据结构传送的程序片断。
然后我们将说明在数据结构传送中实际上被使用的标准XDR（extern data representation），外部数据表示。
我们介绍了XDR转换库函数的使用。
11.1 数据结构的传送我们在UDP数据报一章曾经演示了一个视频点播的模拟，在模拟中，我们使用了非常简单的控制命令，而实际的系统中，可能需要传递更多的信息。
比如在客户进程和服务器进程连接TCP连接后，用户必须输入自身的用户标识和用户密码等等身份确认信息，然后通过TCP 连接将这些信息发送给服务器端，在服务器进程根据这些信息对用户的身份进行确认后，才能允许用户进入系统，使用系统中的各种资源。
因而，对于较复杂的网络应用，我们常常需要复杂的数据结构，而不是简单的几个字节。
11.1.1 数据结构传送的问题下面，我们将说明在数据结构传递中可能存在的问题。
1.网络字序的问题不同类型的计算机对于数据的存储格式可能不同，这将导致它们对相同整数（或其他类型数）的2进制序列理解不同，这个问题在以前我们已经详细说明了。
2.浮点数的传递图11.1 将浮点数的小数部分和整数部分分别传递浮点数的传递比整数更加困难，通常浮点数使用若干比特表示整数部分，其他比特表示小数部分。
不同类型的浮点数float和double，它们使用的比特数不相同，这使得在网络中传递它们有一定的困难。
对于浮点数的处理，可以将浮点数用字符串的形式进行传递，在接收端再将浮点数字符串转化成浮点数。
或者我们可以将浮点数的小数点前后的两个部分分别看成两个整数，分别进行传递。
图11.2 将浮点数作为字符串传递3.指针的处理在数据结构传递中，最为困难的是指针，因为指针的含义是本机上存放某个数据的地址，这个地址在远端的主机没有任何的意义。
题目：在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。
选项A：2
选项B：4
选项C：1/2
选项D：1
答案：2
题目：邻接表是图的一种（）。
选项A：链式存储结构
选项B：索引存储结构
选项C：顺序存储结构
选项D：散列存储结构
答案：链式存储结构
题目：如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。
选项A：完全图
选项B：有回路
选项C：连通图
选项D：一棵树
答案：连通图
题目：下列有关图遍历的说法不正确的是（）。
选项A：非连通图不能用深度优先搜索法
选项B：连通图的深度优先搜索是一个递归过程
选项C：图的遍历要求每一顶点仅被访问一次
选项D：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
答案：非连通图不能用深度优先搜索法
题目：无向图的邻接矩阵是一个（）。
选项A：零矩阵
选项B：上三角矩阵
选项C：对角矩阵
选项D：对称矩阵
答案：对称矩阵
题目：图的深度优先遍历算法类似于二叉树的（）遍历。
选项A：中序
选项B：后序
选项C：层次
选项D：先序
答案：先序
题目：已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
）。
）。
）条边。
选项A：n（n+1）/2
选项B：n（n-1）/2
选项C：n（n-1）
选项D：n（n+1）
答案：n（n-1）/2。
第11章 外部排序一、选择题1．下列排序算法中，其中（）是稳定的。
A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。
不稳定排序有：快速排序、堆排序、shell排序。
时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。
3．在下面的排序方法中，辅助空间为O（n）的是（）。
A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。
A．归并排序B．快速排序C．希尔排序D．堆排序【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。
5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．N B．2N-1 C．2N D．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。
最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序最好情况下的复杂度为O（n）。
6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。
插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。
将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。
数据结构导论自考题模拟11(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.逻辑关系是指数据元素的______（分数：2.00）A.存储方式B.数据项C.结构D.关联方式√解析：[考点] 逻辑关系[解析] 所谓逻辑关系是指数据元素之间的关联方式或者“邻接关系”。
2.算法能正确地实现预定功能的特性称为______（分数：2.00）A.正确性√B.易读性C.健壮性D.时空性解析：[考点] 算法的评价因素[解析] 算法的正确性是指能正确地实现预定功能，满足具体问题的需要。
3.for(i=0;i＜n;i++)for(j=0;j＜n;j++)A[i][j]=i*j;上面算法的时间复杂度为______∙ A.O(1)∙ B.O(n2)∙ C.O(log2n)∙ D.O(n)（分数：2.00）A.B. √C.D.解析：[考点] 时间复杂度的计算[解析] 第一个for语句执行n+1次，第二个for语句执行n*(n+1)次，第三行赋值语句执行n*n次，可得整个程序段的时间函数为T=(n+1)+n*(n+1)+n*n=2n 2 +2n+1，因此算法的时间复杂度为O(n 2 )。
4.带头结点的单链表head为空的判断条件为______（分数：2.00）A.head=NULLB.head!=NULLC.head-＞next=NULL √D.head-＞next=head解析：[考点] 单链表[解析] 带头结点的单链表head为空的判断条件为head-＞next=NULL。
5.设顺序表有10个元素，则在第4个元素前插入一个元素所需移动元素的个数为______（分数：2.00）A.6B.7 √C.8D.9解析：[考点] 顺序表的插入算法[解析] 插入法的基本步骤是：①将结点各向后移一位，以便空出第i个位置；②将x置入该空位；③表长加一，完成顺序表的插入。
6.已知一个单链表中，指针q指向指针p的前驱结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行______（分数：2.00）A.q-＞next=s;p-＞next=s;B.q-＞next=s;s-＞next=q;C.q-＞next=s;q-＞next=p;D.q-＞next=s;s-＞next=p; √解析：[考点] 单链表的插入算法[解析] 单链表的插入步骤是：找到插入位置的前一个结点q和后一个结点p，生成一个结点s，然后执行q-＞next=s;s-＞next=p完成单链表的插入。
