数据结构复习题集(上).ppt

《数据结构复习题集(上).ppt》由会员分享，可在线阅读，更多相关《数据结构复习题集(上).ppt（43页珍藏版）》请在课桌文档上搜索。

1、数据结构习题集,第一二章,重要概念：数据结构相关定义：数据结构=数据+结构 记作 Data_Structure=(D,S)其中,Data_Structure是数据结构的名称。D是数据元素的有限集合(一般为一个数据对象)S是D上关系的有限集.几个相关名词：存储结构 逻辑结构 现实中任何一个问题都可以定义为一个数据类型-称为抽象数据类型抽象数据类型Abstract Data Type ADT一个数学模型及定义在这个模型上的一组操作(或运算)的总称.抽象数据类型定义 抽象数据类型=数学模型+操作=数据结构+操作描述如下：ADT 抽象数据类型的名称 数据对象 数据关系 基本操作ADT抽象数据类型名时间

2、复杂度(空间复杂度雷同)通常选择对特定问题的最基本操作作为原操作，以原操作执行次数即语句频度作为算法的时间度量T(n)。算法分析一般步骤：1.计算出算法的各个语句的频度2.统计出算法的语句频度和T(n)3.给出T(n)的大O表示称为算法的时间复杂度T(n)=O(f(n)常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。,第一二章习题,1数据结构在计算机中的表示称为数据的（存储结构）。2数据结构是相互之间存在一种或多种特定关系的数据元素的集合.3

3、数据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（顺序存储结构）。4.定义一个整数序列的ADT 需要记住此整数序列需要支持元素的位置概念。Integers数据对象：D=ci|ci DO DO=INT i=1，2,n n=0 数据关系：R NN=|ci-1,ci D0 i=2，3,，n 基本操作：void clear();void insert(int);void remove(int);void sizeof();bool isEmpty();bool isInSet(int);,5.写出下列代码段的平均时间复杂度。假定其中的所有变量都是整型。(a)a=b+c;d=

4、a+e;(b)sum=0;for(i=0;i3;i+)for(j=0;jn;j+)sum+;(c)sum=0;for(i=0;in*n;i+)sum+;(d)for(i=0;i n-1;i+)for(j=i+1;j n;j+)tmp=Aij;Aij=Aji;Aji=tmp;(e)sum=0;for(i=1;i=n;i+)for(j=1;j=n;j*=2)sum+;(f)sum=0;for(i=1;i=n;i*=2)for(j=1;j=n;j+)sum+;,T(n)=O(f(2)=O(1);常数阶时间复杂度,T(n)=O(f(n-1)*(n)/2)=O(n2);,T(n)=O(f(3n)=O(n

5、);1阶时间复杂度,T(n)=O(f(n*log2n)=O(n*logn);,T(n)=O(f(log2n*n)=O(logn*n);,T(n)=O(f(n2)=O(n2);2阶时间复杂度,(g)Assume that array A contains values,Random takes constant time,and sort takes steps.for(i=0;i 1)if(ODD(n)n=3*n+1;else n=n/2;,T(n)=O(f(n*(n-1)/2)=O(n2);,T(n)=O(f(n*n*log2n)=O(n2logn);,T(n)=O(f(n+1)/2)=O(

6、n);,下限是(log n)，没有上限。(只有当n=2x时，此段代码执行次数最少，执行的次数为log2n),7.(代码题)输入三个数x,y,z 按照从小到大顺序输出将输入的三个数作为数组元素进行冒泡排序void main()int num=3;printf(Input three number:n);int anum,temp,i,j;for(i=0;iaj)temp=ai;ai=aj;aj=temp;for(i=0;inum;i+)scanf(%d,ai);,第三章,重要概念：线性表：具有相同数据类型的n(n=0)个数据元素的有限序列。一般表示为L=(a1,a2,ai,an)注意：线性表是一

7、种逻辑结构，表示元素之间一对一的相邻关系，下面说的两种实现方式是指他们的存储结构。线性表的两种实现方式：顺序表：顺序存储的线性表又称为顺序表，是使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理地址上也相邻。链表：通过一组任意的存储单元来存储线性表中的数据元素，每一个链表结点，除了存放元素自身信息还需要存放指向其后继的指针。,第三章习题,1在下列序列中，不是线性表的是(a,true,c)。2线性链表中各链结点之间的地址（连续与否无所谓）。3如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，（带头结点的双循环链表）存储方式最节省运行时

8、间。4线性表的顺序存储结构特点是（可直接随机访问任一元素）。,1.设A是一个线性表（al，a2，,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？分析：假设 pi 是在第i个元素之前插入元素的概率，则在长度为n的线性表中插入一个元素所需移动元素次数的平均次数为：2线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，

9、应采用哪种存储表示？为什么？Answer:(1)顺序表需要提前估计线性表的大小并且插入删除效率低需要移动大量结点，优点在于表中节点没有浪费存储空间，并且可以按位置随机访问；链表优点在于插入删除效率高，无需提前估计表的大小，表中元素个数没有限制，缺点在于访问结点需要从表头遍历查找并且每个节点除了储存元素还需要附加空间存储指针。(2)链表 表的大小不固定(3)顺序表，表大小固定，插入删除操作少，按位置随机存取速度快,3针对带表头结点的单链表，试编写下列函数。(1)定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。(2)求最大值函数ma

10、x：通过一趟遍历在单链表中确定值最大的结点。(1)Node*LinkLocate(int i)if(i next;int j=0;while(p,(2)template E LinkMax()Node*p;p=head-next;E j=p-data;while(p-next,(3)统计函数number：统计单链表中具有给定值x的所有元素。(4)建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂性为O(n)。(3)template int LinkCount(E a)Node*p;p=head-next;int count

11、=0;while(p)if(p-data=a)count+;p=p-next;return count;,(4)template void LinkCreate(E a,int n)Node*p;p=head-next;/尾指针 尾插法 for(int i=0;inext=temp;temp-data=ai;p=temp-next;,5)整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。template void LinkSort()Node*p=head-next,*temp;while(p!=null,第四章,1栈应用的典型事例是（）。A）排队 B）查找 C）归并 D）用“

12、算符优先法”进行表达式求值2若用单链表来表示队列，则应该选用（）。A）带尾指针的非循环链表B）带尾指针的循环链表C）带头指针的非循环链表D）带头指针的循环链表 3在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A）堆栈B）队列C）数组D）线性表 4设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。A）ABCDB）DCBAC）ACDBD）DABC5一般情况下，将递归算法转换成等价的非递归算法应该设置（）。A）栈B）队列C）堆栈或队列D）数组6设栈

13、的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（）。A）n-i+1B）i C）n-iD）前面都不正确,D,B,D,B,A,A,1有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？分析：栈特点：先进后出；元素C元素D为前两个出栈元素，说明AB已入栈，并且CD入栈后又出栈。可能的情况有 三种。E元素未入栈时，BA依次出栈 即为CDBAE；B元素出栈后E元素入栈然后EA再入栈 即为CDBEA；E元素入栈后，EBA依次出栈 即为CDEBA2已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和P

14、op操作输出；如果能，请写出操作序列；如果不能，说明原因。(1)dbca(2)cbda 分析：栈特点：先进后出；(1)dbca 不可能 若d第一个出栈，则只有dcba这种可能(2可能 操作序列为：Push(a)Push(b)Push(c)Pop(c)Pop(b)Push(d)Pop(d)Pop(a)3.给一个链表增加一个成员函数，此函数用来将链表中的元素逆置。算法时间复杂度尽可能的小。,Node*Reverse(Node*head)Node*p,*q;if(head=NULL)return NULL;p=NULL;/*逆序后头指针的next为NULL*/while(head-next)q=he

15、ad-next;/*保存指针的下一个*/head-next=p;/*next指针反转*/p=head;/*指针后移*/head=q;/*指针后移*/head-next=p;/*处理逆序后的尾指针*/return head;4.存在一个非空的队列，以及一个空栈。写出一个算法去逆置队列中的元素，并且只能使用栈和队列的基本操作，在空间上只使能用一个变量空间。void reverse(Queue,5.花括号的匹配问题，题目要求，给出一个只有(和)的字符串，使用栈去判断字符串中的左右括号的使用是否正确，其中正确的含义包括：个数上是否正使用确以及配对上是否正确。a)如果字符串不正确则返回false，若字符

16、串正确则返回true。提示：在任意时刻不可能存在右括号比左括号多的情况。(b)如果字符串不正确则返回出错元素在字符串中的下标，若字符串正确则返回true答案：a)利用栈进行匹配，从左往右遍历字符串，左括号入栈，右括号匹配栈顶元素，若匹配不到则字符串出错，若成功则左括号出栈；最后判断栈是否为空，不为空则出错。bool balance(String str)Stack S;int pos=0;while(str.charAt(pos)!=NULL)/遍历strif(str.charAt(pos+)=()/左括号入栈 S.push();else if(str.charAt(pos+)=)/右括号 i

17、f(S.isEmpty()return FALSE;/没有相匹配的左括号，出错 else S.pop();/匹配成功 继续循环 if(S.isEmpty()return TRUE;/栈不为空说明左括号过多，出错 else return FALSE;,b)从左往右遍历字符串，将左括号对应下标入栈，右括号匹配最新的左括号即为栈顶元素，若匹配不到则字符串出错，直接返回当前右括号的下标；若成功则栈顶出栈；最后判断栈是否为空，不为空则出错。int balance(String str)Stack S;int pos=0;while(str.charAt(pos)!=NULL)/将下标直接存入栈中 出错可

18、以直接返回 if(str.charAt(pos+)=()S.push(pos);else if(str.charAt(pos+)=)if(S.isEmpty()return pos;else S.pop();if(S.isEmpty()return-1;else return S.pop();,第五章 二叉树,1.设某二叉树前序为abdcef，中序为dbaecf，画出此二叉树（南方名校经典试题）2有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。,3若一颗二叉树的前序遍历序列与后序遍历序列分别为1.2.3,4和4,3,2,1，则该二叉树的中序遍历不会是（C）。

19、A)1 2 3 4 B)2 3 4 1 C)3 2 4 1 D)4 3 2 14.在下列序列中，不能唯一地确定一颗二叉树的是（D）A)层次序列和中序序列B)先序序列和中序序列C)后序序列和中序序列D)先序序列和后序序列分析1：前序序列为LRN后序序列为NLR，由于前序序列与后序序列正好相反，因此不可能存在一个结点同时存在左右孩子，即二叉树的高度为4，且1为根节点，因此在中序序列中1或者在序列首部或者在尾部，现考虑除去根节点的以2为根节点的子树。分析2：先序序列为NLR，后序序列为LRN虽然可以唯一确定一颗树中的根节点，但是无法划分左右子树，例如先序序列为AB，后序序列为BA5.已知二叉树的先序

20、遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果是什么，并且画出这颗二叉树。答：后序遍历结果为：CBEFDA,6.已知二叉树的层次序列为ABCDEF，中序序列为BADCFE，则先序序列是什么，并且画出这颗二叉树。答：先序遍历结果为：ABCDEF7.表达式x*(y-z)+u的逆波兰式（后缀表达式）表示是（B）。A）xyzuu-+B）xyz-*u+C）xyz*-u+D）+-*xyzu,8.设有表达式：a*(b-c)/d+f/(g+h*i)，试给出此表达式的下面结果：二叉树表示；逆波兰式表示；中缀表示；,逆波兰式表示(后缀即为左右根)：abc-*d/fghi*+/+中缀表示(即为

21、左根右)：a*b-c/d+f/g+h*i,9.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8、11，试求对应哈夫曼树。,步骤如下：(1)将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。,10.Build the Huffman coding tree and determine the codes f

22、or the following set of letters and weights:Letter A B C D E F G H I J K L Frequency 2 3 5 7 11 13 17 19 23 31 37 41 What is the expected length in bits of a message containing characters for this frequency distribution?,209/83 126/l 42 55 71/H I 24 J 34 K/E F 17 G/D 10/5 C/A B,l 00 h 010 i 011 e 10

23、00 f 1001 j 101 d 11000 a 1100100 b 1100101 c 110011 g 1101 k 111,其中F代表总频度或权值,n代表总个数,li代表编码长度,fi代表频度,本题中长度为3.23445,11.将下列序列调整为大顶堆:10 5 12 3 2 1 8 7 9 4,10/5 12/3 2 1 8/7 9 4,答案：（10，5，12，3，2，1，8，7，9，4）从最后一非终端节点开始筛选,10/5 12/3 4 1 8/7 9 2,10/5 12/9 4 1 8/7 3 2,10/5 12/9 4 1 8/7 3 2,10/9 12/7 4 1 8/5 3

24、2,12/9 10/7 4 1 8/5 3 2,大顶堆为12,9,10,7,4,1,8,5,3,2,12.使用数学归纳法证明：在一棵非空满K叉树中，n代表树中的分支节点，即非叶子节点，证明树中叶子节点的个数为(K-1)n+1；证明：当n=1时,即其中的叶子节点数为K,满足(K-1)*1+1=K,即成立；假设当n=x时，叶子节点数为(K-1)x+1成立；那么当n=x+1时，某一个叶子节点变成非叶子节点则会增加K-1个叶子节点。即最终叶子节点数目为：(K-1)x+1+K-1=(K-1)(x+1)+1 成立。,13.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如图所

25、示的树状显示二叉树。,分析：1）打印顺序ceabd，对树来说是右根左的访问顺 序；2）每个元素前的空白字符数等于它在树中的层数减一；void Inorder(BiTree bt,level)/level=1 int i;if(bt!=NULL)/按右根左遍历二叉树 Inorder(bt-rchild,level+1);/右 for(i=0;idata);printf(n);Inorder(bt-lchild,level+1);/左,14.写一个递归函数，名字叫做search，此函数带有两个参数，树的根节点，以及待查找的value值。如果value在树中存在则返回ture，反之返回false。答

26、案：以根左右的方式遍历查找template bool search(BinNode*subroot,Key K)if(subroot=NULL)return false;if(subroot-value()=K)return true;if(search(bt-lchild,K)return true;if(search(bt-rchild,K)return true;15写一个递归算法，返回一颗二叉树的高度。答案：template int height(BinNode*subroot)if(subroot=NULL)return 0;/空 return 1+max(height(subroo

27、t-lchild),height(subroot-rchild);,16.写名为printRange的递归函数。带有三个参数，分别是：一颗BST(二叉排序树)的根，以及一个low value和一个high value。此函数的功能是将二叉排序树中值在low value与high value之间的数据打印出来。要求尽可能少的访问二叉排序树中的结点。template void printRange(BinNode*root,int low,int high)if(root=NULL)return;if(root-val()high)printRange(root-left(),low,high);

28、else if(root-val()right(),low,high);else printRange(root-left(),low,high);PRINT(root-value();printRange(root-right(),low,high);,排序,1堆排序的时间复杂度是（D）。A）O(1)B）O(n)C）O(n2)D）O(nlogn)2.若一个具有N个顶点，K条边的无向图是一个森林（NK），则该森林中必有（C）棵树。A）KB）NC）N-KD）13每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（B）。A）冒泡排序B）简单选择排序 C）希尔排序 D）直接插入排序4快速

29、排序执行一遍之后，已经到位的元素个数是（A）。A）1B）3C）n/4D）n/25数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（C）排序算法最节省时间。A）快速排序B）希尔排序C）堆排序D）直接选择排序,6如果一棵树有n1个度为1的结点,有n2个度为2的结点,nm个度为m的结点,试问有多少个度为0的结点?试推导.,7请画出右图所示的树所对应的二叉树。（8）,8.判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则将它调整为大根堆。答案：因为堆为完全二叉树，因此只需要判断是不是所有节点，都大于或小于子节点，即节点n需要大于或小于2n节

30、点和2n+1节点；序列不是堆如调整为大根堆为：(92，86，56，70，33，33，48，65，12，24)若调整为小根堆为：(12，24，33，65，33，56，48，92，86，70),9给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。（1）希尔排序（第一趟排序的增量为6）（2）快速排序（选第一个记录为枢轴）答案：(1)（4，2，16，6，8，28，12，10，20，30，18）(2)（6，2，10，4，8，12，28，30，20，16，18）10.编写一个处理整数关键码的插入排序。条件如下：输入的是一个栈（不

31、是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是(n2)。void StackSort(Stack,第十题实例如下：算法过程初始序列为：(18,12,56,9,55,8)插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个插入到这个有序子序列中。,1812,E=18,E=12,E=56,IN,8 912185556,E=19,E=55,E=8,最终结果,排序,1在下述排序算法中，所需辅助存储量最多的是（D）。A）快速排序B）归并排序C）堆排序D）链式基数排序快速排序：O(logn)归并排序：O(n)

32、堆排序：O(1)链式基数排序：O(n+r)r是基数2在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）。A）直接插入排序 B）起泡排序 C）简单选择排序 D）基数排序,3用一张表概括各种排序算法的时间代价、空间代价，特点。并总结各种情况下应选择的排序算法、并说明理由。,4.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中，另一个数组存储指向这个大字符串数组的索引（索引指向特定字符串的指针），请改写快速排序算法，对这个字符串序列进行排序。函数要修改索引数组，使得第一个指针指向最小字符串的起始位置。,答案：在此题中，考虑到待排序的元素为字符

33、串，并且另有一个数组index存储指向每一个字符串的指针。#define NUM 10char*testNUM=back,alert,cat,door,effective,grant,father,ideal,hand,zero;/存放所有字符的数据char*indexNUM;/假定只有NUM个待排字符串 此处存放的为指针,for(i=0;iNUM;i+)indexi=/初始化 index数组内的元素为指针 指向每一个字符串在这个快速排序算法中，主要修改的地方有两个：一：每次比较的元素是两个字符串，因此应该用strcmp()比较函数；二：对于元素的交换，应该直接交换index指针即可，不需要交

34、换test元素；,void swap(char*a,char*b)/交换指针char*temp;temp=a;a=b;b=temp;int Partition(int low,int high)char*pivotkey;/定义一个指针 int pivotindex=low;pivotkey=testlow;while(low=0)high-;swap(indexlow,indexhigh);while(lowhigh,5.下面各个操作中，哪一个是最适合先进行排序处理？对于这些操作，简短的描述一个实现算法，并给出算法的渐进复杂度。（1）找最小值（2）找最大值（3）计算算术平均值（4）找中值（即

35、中间的值）（5）找出模式数（mode，即出现次数最多的值）答案：（1）找最小值遍历一次即可，无需排序（2）找最大值遍历一次即可，无需排序（3）计算算术平均值遍历一次即可，无需排序（4）中值是在一组数据中居于中间的数(特别注意：这组数据已经经过升序排列)，即在这组数据中，有一半的数据比它大，有一半的数据比它小。因此找中值需要对数据先排序，然后再找中间的数。一般采用快速排序法，其渐进复杂度O(nlogn)（5）找出模式数（即出现次数最多的值）需要先排序，然后再遍历，其渐进复杂度为O(n),虚拟缓冲区相关置换算法,6.Assume that a virtual memory is managed u

36、sing a buffer pool.The buffer pool contains five buffers and each buffer stores one block of data.Memory accesses are by block ID.Assume the following series of memory accesses takes place:5 2 5 12 3 6 5 9 3 2 4 1 5 9 8 15 3 7 2 5 9 10 4 6 8 5 For each of the following buffer pool replacement strate

37、gies,show the contents of the buffer pool at the end of the series,and indicate how many times a block was found in the buffer pool(instead of being read into memory).Assume that the buffer pool is initially empty.(a)First-in,first out.先进先出(b)Least frequently used(with counts kept only for blocks cu

38、rrently in memory,counts for a page are lost when that page is removed,and the oldest item with the smallest count is removed when there is a tie).最不经常使用(c)Least frequently used(with counts kept for all blocks,and the oldest item with the smallest count is removed when there is a tie).最不经常使用(d)Least

39、 recently used.最近最少使用(e)Most recently used(replace the block that was most recently accessed).最近访问,(a)10 4 6 8 5(b)5(6 times)3(3 times)4(1 time)6(1 time)8(1 time)(c)5(6 times)3(3 times)9(3 times)2(3 times)8(2 times)(d)5 8 6 4 10(e)12 15 2 4 5,7.假定一块磁盘配置如下：存储总量将近1033MB，分成15个盘面。每个盘面有2100个磁道，每个磁道有64个扇区

40、，每个扇区有512字节，每个簇包括8个扇区。磁盘以7200rpm旋转。磁道-磁道寻道时间是3ms，平均寻道时间是20ms。现在假定磁盘中有一个512KB的文件，在一般情况下，读取文件中的所有数据要花多少时间？假定文件中的第一个磁道随机位于磁盘中的某一个位置，整个文件放在一组相邻磁道内，文件完全填充它所占据的磁道。试给出你的计算。,分析：2100磁道64扇区512字节每簇8个扇区 磁盘以7200rpm旋转，转一圈时间为60*1000/7200=0.0083磁道到磁道寻道时间为3ms 平均寻道时间20ms,512KB的文件存放需要多少个扇区?多少个簇？1024个sectors 128个cluste

41、r一般情况 128*20ms+（1/2+1/8）*0.0083s连续存放512KB文件放多少个track？1024/64=16第一个磁道：20ms+（1/2+1/1）*0.0083s后续三个磁道：3ms+1.5*0.0083s,知识点：磁盘一次读取时间由寻道时间延迟时间和传输时间决定其中r为磁盘每秒钟的转速，b为每次读取的字节数，N为一个磁道上的字节数寻道时间：将磁头移动到指定磁道所需要的时间延迟时间：磁头定位到某一磁道相关扇区所需要的时间，T=1/2*r传输时间：从磁盘读出或向磁盘写入数据所经历的时间，T=b/rN,8.总存储量675MB，分布在15个盘面上，每个盘面有612磁道，每个磁道1

42、44个扇区，每个扇区512字节。每簇有8个扇区，磁盘转速为3600rpm，磁道到磁道的寻道时间为20ms，平均寻道时间为80ms，现在假设磁盘上有一个大小为360KB的文件。一般情况下，读取文件中的所有数据要花多少时间？假定文件中的第一个磁道随机位于磁盘中的某一个位置，整个文件放在一组相邻磁道内，文件完全填充它所占据的磁道。试给出你的计算。,360KB的文件存放需要多少个扇区?多少个簇？720个sectors 90个cluster一般情况：90*80ms+90*（1/2+8/144）*0.0166s=7288.18ms连续存放：360KB文件放多少个track？720/144=5第一个磁道：8

43、0ms+（1/2+1/1）*0.0166s=104.9ms后面4个磁道：20ms+1.5*0.0166s=44.9ms总时间：104.9+44.9*4=284.5ms,分析：612磁道144扇区512字节每簇8个扇区；转一圈时间为60*1000/3600=0.0166磁道到磁道寻道时间为20ms 平均寻道时间80ms,9.写一个函数去合并两个链表，两个链表中的元素在初始状态是有序的，并且是从小到大的顺序排列，合并完成后的链表要求有序并且从高到低排列，算法的时间复杂度应为O(n).,答案：1.对L1，L2元素依次比较，找到较小的一个，使用头插法放置L中，相应找下一个元素；2.直到L1与L2有一个

44、为空时，比较结束，把非空链表中的元素依次使用头插法加至L中即可。代码如下：,Link merge(Link L1,Link L2)/最后数据存放在新链表L，要求逆序采用头插法Link p,q,L,m,temp;p=L1-next;q=L2-next;L-next=null;m=null;while(p,10.两个单链表L1和L2中的元素类型相同，要求从L1中删除那些同时在L2中出现的元素。若L1中有重复元素，要求只保留一个。分析所设计的算法的时间复杂度。,Link merge(Link L1,Link L2)Link p,q,temp,pre;p=L1-next;temp=p-next;pre

45、=L1;/从L1的第二个元素开始比较while(p)/对L1依次遍历，删除L1中重复的元素 只保留一个while(temp)if(p-data!=temp-data)temp=temp-next;else pre-next=pre-next-next;break;pre=p;p=p-next;/记录当前节点的前驱节点便于删除pre=L1;p=L1-next;temp=L2-next;/从L2的第一个元素开始比较while(p)/对L1中的元素，与L2中逐个比较，删除相同的元素while(temp)if(p-data!=temp-data)temp=temp-next;else p-next=p-next-next;break;pre=p;p=p-next;/记录当前节点的前驱节点便于删除return L1；;,时间复杂度为O(n2)(假设链表L1与L2的规模均为n),Thanks,