题目内容
（请给出正确答案）
对给定关键字序号j(1＜j＜n)，要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间)。例如：给定无序关键字{7，5，1，6，2，8，9，3)，当j=4时，找到的关键字应是5。【中科院研究生院2003十二(15分)】【武汉理工大学2002四、3(35／3分)】
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“对给定关键字序号j（1＜j＜n)，要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个”相关的问题
给定n×m矩阵A[a．．b，c．．d]，并设A[i，j]≤A[i，j+1](0≤i≤b，c≤j≤d一1)和A[i，j]≤A[i+1，j](0≤i≤b—1，e≤j≤d)。设计一算法判定x的值是否在A中，要求时间复杂度为D(m+n)。
给定结点的关键字序列(F,B,J,G,E,A,I,D,C,H)，对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同，但中间结果是不同的。
Shell排序的第一趟扫描(步长为5)结果应为(1)。
冒泡排序(大数下沉)的第一趟冒泡的效果是(2)。
快速排序的第一次扫描结果是(3)。
二路归并排序的第一趟结果是(4)。
若以层次序列来建立对应的完全二叉树后，采用筛选法建堆，其第一趟建的堆是(5)。
A．(B, F, G, J, A, D, I, E, H, C)
B．(B, F, G, J, A, E, D, I, C, H)
C．(A, B, D, C, E, F, I, J, G, H)
D．(C, B, D, A, E, F, I, G, J, H)
给定节点的关键字序列(F,B,J,G,E,A,I,D,C,H)，对它按字母的字典顺序进行排列。采用不同方法，其最终结果相同，但中间结果是不同的。Shell排序的第一趟扫描(步长为5)结果应为(72)。冒泡排序(大数下沉)的第一趟起泡的效果是(73)。快速排序的第一趟结果是(74)。二路归并排序的第一趟结果是(75)。
A．(B, F, G, J, A, D, I, E, H, C)
B．(B, F, G, J, A, E, D, I, C, H)
C．(A, B, D, C, E, E, I, J, G, H)
D．(C, B, D, A, E, F, I, G, J, H)
【Ex-10-3】（鸡尾酒排序）修改冒泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键字最大的元素放到序列的最后，第二趟把关键字最小的元素放到序列的最前面。如此反复进行。请在空白处填入正确的语句。 typedef int ElemType; void shaker_Sort(________①_______, int n) { int low = 1, high = n - 1, i, j; int exchange; ElemType w; while(_______②________) { ________③_________; for(i = low; i ＜ high; i++) if(A[i] ＞ A[i + 1]) { w = A[i]; A[i] = A[i + 1]; ________④________; j = i; } high = j; for(i = high; i ＞ low; i--) if(A[i - 1] ＞ A[i]) { w = A[i - 1]; A[i - 1] = A[i]; A[i] = w; j = i; } ________⑤________; } }
给定以下两个算法： 算法A： for(int i = 0; i ＜ N; i++) for(int j = 0; j＜ N; j++) { S; } 算法B： for(int i = 0; i ＜ N; i++) for(int j = i; j＜ N; j++) { S; } 其中N是一个比较大的自然数，S是有若干基本语句组成的程序段。 1）在相同的计算机上，算法A比算法B运行速度慢？ 2）算法A的时间复杂度比算法B要高？ 请判断以上两个命题是否正确？并说明理由。
.每个作业Ji都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业Ji需要机器j的处理时间为tij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设Fij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和
称为该作业调度的完成时间和.批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.
算法设计:对于给定的n个作业,计算最佳作业调度方案.
数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.
结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.
阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。
[说明]
HufTman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下：
①根据给定的n各权值{W1，w2，…，wn)构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵树Ti中只有一个带权为wi的根节点，其左右子树均空。
②在F中选取两棵根节点的权值较小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左右予树根节点的权值之和。
③从F中删除这两棵树，同时将新得到的二叉树加入到F中。
重复②③，直到F中只剩一棵树为止。
函数中使用的预定义符号如下：
#define INT MAX 10000
#define ENCODING LENGTH 1000
typedef enum(none，left_child，right_child) Which；
/*标记是左孩子还足右孩子*/
typedef char Elemtype；
typedef struct TNode{//Huffman树节点
Elemtype letter；
int
weight； //权值
int parent； //父节点
Which sigh；
char *code； //节点对应编码
}HTNode，*HuffmanTree；
int n；
char coding[50]；//储存代码
[函数]
void Select(HuffmanTree HT，int end，int *sl，int *s2)
/*在0～END之间，找出最小和次小的两个节点序号，返吲S1、S2*/
{
int i；
int min 1=INT_MAX；
int min 2=INT_MAX；
for(i=0；i＜=end；i++){/*找最小的节点序号*/
if(((1) )＆＆(HT[i].weight＜minl)){
*s1=i；
min 1=HT[i].weight；
}
}
for(i=0；i＜=end；i++){/*找次小节点的序号*/
if((HT[i].parent==0)＆＆((2) )
＆＆(min 2＞HT[i].weight)){
*s2=i；
min 2=HT[i].weight；
}
}
}
void HuffmanTreeCreat(HuffmanTree＆HT)/*建立HUFFMAN树*/
{
int i；
int m=2*n-1；
int s1，s2；
for(i=n；i＜m；i++){
Select((3) )；
HT[s1].parent=i；
HT[s2].parent=i；
HT[s1].sigh=left child；
HT[s2].sigh=right child；
HT[i]．weight=(4)；
}
}
void HuffmanTreeEncoding(char sen[]，HuffmanTree HT)
{ /*将句子进行编码*/
int i=0；
int j；
while(sen[i] !='＼0'){
for(j=0；j＜n；j++){
if(HT[j].letter==sen[i])(/*字母吻合则用代码取代*/
strcat(coding， (5) )；
break；
}
}
i++；
if (Sen [1]==32) i++；
}
printf("\n%s"，coding)；
}
(1)
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
