- 搜标题
- 搜题干
- 搜选项
问答题
设输入文件保存以下记录：14，22，7，24，15，16，11，100，10，9，20，12，90，17。现采用置换-选择方法生产初始归并段，并假设内存工作区可同时容纳5个记录，请画出选择的过程。
答案：设内存工作区在某一时刻可以处理5个记录，利用败者树生成初始归并段的过程如下表所示。
你可能感兴趣的试题
- 问答题
对于一个长度为m=41的散列表，采用双散列法解决冲突，对于关键字k 1 ，k 2 ，k 3 ，若h(k 1 )=30，h(k 2 )=28，h(k 3 )=19，h 2 (k 1 )=14，h 2 (k 2 )=27，h 2 (k 3 )=35，则k 1 ，k 2 ，k 3 的探测序列中前4个位置各为多少。k 1 的探测序列： 30 ，______，______，______；
答案：在双散列法中，求初始散列地址的散列函数为h(x)，求下一个空位的增量函数为h2(x)，一旦发生冲突... - 问答题
设有150个记录要存储到散列表中，要求利用双散列法解决冲突，同时要求找到新记录插入位置的平均比较次数不超过2次。试问散列表需要设计为多大请为这个散列表设计散列函数(除留余数法)和再散列函数。
设α是散列表的装载因子，则应用双散列法解决冲突时的查找成功的平均查找长度和查找不成功的平均查找长度分别为
(请根据题意选用合适的公式)答案：已知要存储的记录数为n=150，找到新记录的插入位置的平均比较次数即查找不成功的平均查找长度为ASL不成功 - 问答题
若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同查找失败。
答案：若对有n个元素的有序顺序表和无序顺序表进行顺序查找，查找失败的平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值... - 问答题
假定把关键字key散列到有n个表项(从0到n-1编址)的散列表中。对于下面的每一个函数H(key)(keyr为整数)，这些函数能够当作散列函数吗(即对于插入和查找，散列程序能正常工作吗)如果能够，它是一个好的散列函数吗请说明理由。设函数random(n)返回一个0到n-1之间的随机整数(包括0与n-1在内)。H(key)=1
答案：能够作为散列函数，但不是一个好的散列函数，因为所有关键字都映射到同一位置，造成大量的冲突机会。 - 问答题
若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同查找成功，且表中只有一个关键字等于给定值k的元素。
答案：若对有n个元素的有序顺序表和无序顺序表进行顺序查找，查找成功，且表中只有一个关键字等于给定值k的元素时的平均查找长度相同... - 问答题
设有一棵B+树，其结点最多可存放100个索引项。对于高度为1、2、3、4的B+树，最多能存储多少索引项最少能存储多少索引项
答案：能存储多少索引项，主要看叶结点。非叶结点是对下层最多关键字的复写。
对于高度为1的B+树：根据B+树定义，根结... - 问答题
若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同查找成功，且表中有若干个关键字等于给定值k的元素，要求一次查找能找出所有元素。
答案：若对有n个元素的有序顺序表和无序顺序表进行顺序查找，查找成功，且表中有若干个关键字等于给定值k的元素要求一次查找能找出所... - 问答题
设敞列表为HT[13]，散列函数为H(key)=key%13。用开地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，3l，15，36造表。采用线性探测法寻址下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。
答案：使用散列函数H(key)=key%13，有：
H(12)=12，H(23)=10，H(45)=6，H(57)=... - 问答题
设有一个散列表，要存放的数据有8个，采用除留余数法计算散列地址，并用二次散列法解决冲突，不过仅用H i =(H o +i 2 )%m计算下一个散列地址，m是表的长度，i=1，2，…，m-1。设存放的数据为{25，40，11，97，59，30，87，73}，依次计算并存放这些数据到散列表中，并计算存放后表的查找成功的平均查找长度。
答案：依次计算并存储的数据为{25，40，11，97，59，30，87，73}
Hash(25)=25%19=6；H... - 问答题
设散列表为HT[0.12]即表的大小为m=13。现采用链地址法解决冲突。若插入的关键字序列为{2，8，31，20，19，18，53，27}。画出插入这8个关键字后的散列表。
答案：散列表HT[0..12]，散列函数为Hash(key)=key%13；插入关键字序列为{2，8，31，20，19，18，... - 问答题
设散列表为HT[0.12]即表的大小为m=13。现采用链地址法解决冲突。若插入的关键字序列为{2，8，31，20，19，18，53，27}。计算查找成功的平均查找长度和查找不成功的平均查找长度。
答案：查找成功的平均查找长度为：
查找不成功的平均查找长度为：
- 问答题
如果有一个时间复杂性为O(n 2 )的算法(如冒泡排序、选择排序或插入排序等)，在有200个元素的数组上运行需要时3.1毫秒，试问在下列类似的数组上运行大约需要多长时间具有400个元素。
答案：当n=200时，T(200)=O(2002)=3.1毫秒；当n=400时，T(400)=O(400... - 问答题
如果有一个时间复杂性为O(n 2 )的算法(如冒泡排序、选择排序或插入排序等)，在有200个元素的数组上运行需要时3.1毫秒，试问在下列类似的数组上运行大约需要多长时间具有40000个元素。
答案：T(40000)=O(40000 2 )=200 2 ×O(200 2 )=40000×3.1=124000毫秒=124秒。 - 问答题
希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。
答案：以下例子中的275和275*是排序码相等的不同数据元素，为区分起见，在后一个275上加*... - 问答题
在冒泡排序过程中，什么情况下排序码会朝与排序相反的方向移动试举例说明。在快速排序过程中有这种现象吗
答案：如果在待排序序列的后面的若干排序码比前面的排序码小，则在冒泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动... - 问答题
如果只想在一个有n个元素的任意序列中得到其中最小的第k(k＜＜n)个元素之前的部分排序序列，那么最好采用什么排序方法为什么例如有这样一个序列{57，40，38，11，13，34，48，75，6，19，9，7}，要得到其第4个元素之前的部分有序序列{6，7，9，11}，用所选择的算法实现时，要执行多少次比较
答案：一般来讲，当n比较大且要选的数据k远小于n时，采用堆排序方法中的筛选算法siftDown()最好。
例如，对于... - 问答题
多路平衡归并排序是外排序的主要方法，试问多路平衡归并排序包括哪两个相对独立的阶段每个阶段完成何种工作
答案：多路平衡归并排序由两个相对独立的阶段组成：生成初始归并段和多趟归并排序。生成初始归并段阶段根据内存工作区的大小，将有n个... - 问答题
如果某个文件经内排序得到80个初始归并段，试问：若使用多路平衡归并执行3趟完成排序，那么应取的归并路数至少应为多少
答案：设归并路数为m，初始归并段个数r=80，根据归并趟数计算公式
，得：logm... - 问答题
如果某个文件经内排序得到80个初始归并段，试问：如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可用完成排序如果限定趟数，可取的最低路数是多少
答案：设多路归并的归并路数为m，需要m个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有m+1=15，因此m=14，可做... - 问答题
假设文件有4500个记录，在磁盘上每个块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：可以建立多少个初始归并段每个初始归并段有多少记录存放于多少个块中
答案：文件有4500个记录，用于排序的内存区可容纳450个记录，可建立的初始归并段有4500/450=10个。每个初始归并段中... - 问答题
假设文件有4500个记录，在磁盘上每个块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：应采用几路归并请写出归并过程及每趟需要读写磁盘的块数。
答案：内存区可容纳6块，可建立6个缓冲区，其中5个缓冲区用于输入，1个缓冲区用于输出，因此，可采用5路归并。归并过程如下图所示... - 问答题
磁盘文件采用选择法实现m路归并时，占用CPU的时间与m是否相关为什么
答案：选择法是指在做m路归并时在m个记录中通过比较旋转排序码最小的记录。因为占用CPU时间与比较次数有关，而比较次数与m有关，... - 问答题
败者树中的“败者”指的是什么若利用败者树求m个排序码中的最大者，在某次比较中得到a＞b，那么谁是败者
答案：如果最终胜者是指具有最小排序码的记录，那么“败者”指的是两个归并段当前参加归并的记录中排序码较大的记录；反之，如果最终胜... - 问答题
设有一个排序码输入序列{10，40，30，50，20，25，45，60}，试根据败者树的构造算法构造一棵败者树。
答案：输入的排序码有8个，构造出的败者树的叶结点有8个，编号0～7，第8号原始是构造败者树的辅助存储，初始时放一个-∞，该值在... - 问答题
设输入文件保存以下记录：14，22，7，24，15，16，11，100，10，9，20，12，90，17。现采用置换-选择方法生产初始归并段，并假设内存工作区可同时容纳5个记录，请画出选择的过程。
答案：设内存工作区在某一时刻可以处理5个记录，利用败者树生成初始归并段的过程如下表所示。
- 问答题
试为下列每种情况选择合适的排序方法：
(1)n=30，要求最坏情况下速度最快。
(2)n=30，要求既要快，又要排序稳定。
(3)n=1000，要求平均情况下速度最快。
(4)n=1000，要求最坏情况下速度最快且稳定。
(5)n=1000，要求既快又最省内存。答案：和(2)这两个情况适合在n比较小的排序算法中选择，包括直接插入排序、折半插入排序、冒泡排序、简单选择排序。它们在最坏情况... - 问答题
在已排好序的序列中，一个元素所处的位置取决于具有更小排序码的元素的个数。基于这个思想，可得计数排序方法。假设待排序元素放在数组a[n]中，n是待排序元素个数。该方法建立一个计数数组count[n]，用count[i]记下在已排好序的序列中a[i]前面的元素个数，最后依count[]的值，将序列在a[n]中重新排列，就可完成排序。编写一个算法，实现计数排序，并说明对于一个有a个元素的序列，为确定所有元素的count值，最多需要做n(n-1)/2次排序码比较。
答案：这是一个典型的以空间换时间的例子。为了加速计数排序的排序速度，增设一个整数计数数组，存放待排序数据的各自存放位置，然后对... - 问答题
下面给出一个排序算法，数组a[]是存放待排序数据元素的数组，n是数组大小，数据元素的数据类型是DataType。
void unknow(DataType a[],int n){
int high=n-1,i,j;DataType w;
while(high＞0){
j=0;
for(i=0;i＜high;i++)
if(a[i]＞a[i+1]){
w=a[i];a[i]=a[i+1];a[i+1]=w;
j=i;
}
high=j;
}
}若待排序数据序列为{10，20，30，40，50，60}，画出每次执行的结果序列。答案：针对正序的待排序数据序列的(每趟while)执行结果，如下表所示，一趟结束。
