数据结构作业8

1、数据结构第八次作业选择题1在下述排序算法中，所需辅助存储量最多的是（D）。A）快速排序B）归并排序C）堆排序D）链式基数排序快速排序：O(logn) 归并排序：O(n) 堆排序：O(1) 链式基数排序：O(n+r)r是基数2在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）。A）直接插入排序 B）起泡排序 C）简单选择排序 D）基数排序起泡排序效率低，比较次数多；简单选择排序对文件有序无序没有要求；基数排序对文件数据有要求，适用于位数小的数列；1用一张表概括各种排序算法的时间代价、空间代价，特点。并总结各种情况下应选择的排序算法、并说明理由。7.5 图7.5中给出了选择排序的

2、最少交换次数为(n)，因为算法并不检查第i个元素是否已经在第i个位置，这就是说，那可能带来不必要的交换。（1）改进算法使之不存在不必要的交换（2）你认为这种改进能加快速度吗？（3）编写两个程序验证一下原始插入排序算法和改进算法的运行时间。哪个算法实际上更快？答案：（1）改进算法使之不存在不必要的交换 void SimpleSeclectionSortAfter(int A,int n)/修改后for(int i=0;in;i+)int lowindex=i;for(int j=i+1;jn;j+) if(AjAlowindex)lowindex=j;if(i!=lowindex)swap(Ai

3、,Alowindex);/for i/function（2）是不可能有很大作用，更可能的算法的速度带慢。因为每次交换之前需要额外花费检查的时间。 （3）验证得之，在交换之前判断交换位置不一定会给程序带来效率上的改进，反而有时会拖慢程序的运行时间。因此7.5书中的算法更快。 当N=10000时，对一个随机数组进行测试得出一下结果：7.10 某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中，另一个数组存储指向这个大字符串数组的索引（索引指向特定字符串的指针），请改写快速排序算法，对这个字符串序列进行排序。函数要修改索引数组，使得第一个指针指向最小字符串的起始

4、位置。答案：在此题中，考虑到待排序的元素为字符串，并且另有一个数组index存储指向每一个字符串的指针。#define NUM 10char *testNUM=back,alert,cat,door,effective,grant,father,ideal,hand,zero;/存放所有字符的数据char *indexNUM;/假定只有NUM个待排字符串 此处存放的为指针for(i=0;iNUM;i+) indexi=&testi;/初始化 index数组内的元素为指针 指向每一个字符串在这个快速排序算法中，主要修改的地方有两个：一：每次比较的元素是两个字符串，因此应该用strcmp(

5、)比较函数；二：对于元素的交换，应该直接交换index指针即可，不需要交换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(lowhigh) while(low=0)high-; swap(indexlow,indexhigh); while(lowhigh&strcmp(testlow,pivotkey)

6、=0)low+; swap(indexlow,indexhigh); return low;7.16 下面各个操作中，哪一个是最适合先进行排序处理？对于这些操作，简短的描述一个实现算法，并给出算法的渐进复杂度。（1）找最小值（2）找最大值（3）计算算术平均值（4）找中值（即中间的值）（5）找出模式数（mode，即出现次数最多的值）答案：（1）找最小值遍历一次即可，无需排序（2）找最大值遍历一次即可，无需排序（3）计算算术平均值遍历一次即可，无需排序（4）中值是在一组数据中居于中间的数(特别注意：这组数据已经经过升序排列)，即在这组数据中，有一半的数据比它大，有一半的数据比它小。因此找中值需要对

7、数据先排序，然后再找中间的数。一般采用快速排序法，其渐进复杂度O(nlogn)（5）找出模式数（即出现次数最多的值）需要先排序，然后再遍历，其渐进复杂度为O(n)第九次作业分析1：前序序列为LRN后序序列为NLR，由于前序序列与后序序列正好相反，因此不可能存在一个结点同时存在左右孩子，即二叉树的高度为4，且1为根节点，因此在中序序列中1或者在序列首部或者在尾部，现考虑除去根节点的以2为根节点的子树。分析2：先序序列为NLR，后序序列为LRN虽然可以唯一确定一颗树中的根节点，但是无法划分左右子树，例如先序序列为AB，后序序列为BA1若一颗二叉树的前序遍历序列与后序遍历序列分别为1.2.3,4和4

8、,3,2,1，则该二叉树的中序遍历不会是（C）。 A)1 2 3 4 B)2 3 4 1 C) 3 2 4 1 D)4 3 2 1 2.在下列序列中，不能唯一地确定一颗二叉树的是（D）A)层次序列和中序序列B)先序序列和中序序列C)后序序列和中序序列D)先序序列和后序序列3.已知二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果是什么，并且画出这颗二叉树。答：后序遍历结果为：CBEFDA4. 已知二叉树的层次序列为ABCDEF，中序序列为BADCFE，则先序序列是什么，并且画出这颗二叉树。答：先序遍历结果为：ABCDEF8.16 Assume that a vir

9、tual memory is managed using 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 bu

10、ffer pool replacement strategies, 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 use

11、d (with counts kept only for blocks currently 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

12、 removed when there is a tie). 最不经常使用(d) Least 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

13、10 (e) 12 15 2 4 58.5 Assume that a disk drive is configured as follows. The total storage is approximately 1033MB divided among 15 surfaces. Each surface has 2100 tracks, there are 64 sectors/track, 512 bytes/sector, and 8 sectors/cluster. The disk turns at 7200 rpm. The track-to-track seek time is

14、 3 ms, and the average seek time is 20 ms. Now assume that there is a 512KB file on the disk. On average, how long does it take to read all of the data on the file? Assume that the first track of the file is randomly placed on the disk, that the entire file lies on contiguous tracks, and that the fi

15、le completely fills each track on which it is found. Show your calculations. 翻译：假定一块磁盘配置如下：存储总量将近1033MB，分成15个盘面。每个盘面有2100个磁道，每个磁道有64个扇区，每个扇区有512字节，每个簇包括8个扇区。磁盘以7200rpm旋转。磁道-磁道寻道时间是3ms，平均寻道时间是20ms。现在假定磁盘中有一个512KB的文件，在一般情况下，读取文件中的所有数据要花多少时间？假定文件中的第一个磁道随机位于磁盘中的某一个位置，整个文件放在一组相邻磁道内，文件完全填充它所占据的磁道。试给出你的计算。2100磁道64扇区512字节每簇8个扇区 磁盘以7200rpm旋转，转一圈时间为60*1000/7200=0.0083磁道到磁道寻道时间为3ms平均寻道时间20ms 512KB的文件存放需要多少个扇区?多少个簇？ 1024个sectors 128个cluster 一般情况 128*20ms+（1