有n个分别排好序的整数数组[图]，其中[图]含有[图]个整...

更多“有n个分别排好序的整数数组[图]，其中[图]含有[图]个整.…”相关的问题

第1题

阅读以下说明和程序流程图，将应填入 (n) 处的字句写在对应栏内。

[说明]

假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：

m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]×10+a[2]

其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、1表示负数。注：数组下标从0开始。

流程图(图4-1)用于计算长整数的加(减)法。运算时先决定符号，再进行绝对值运算。对于绝对值相减情况，总是绝对值较大的减去绝对值较小的，以避免出现不够减情况。注，此处不考虑溢出情况，即数组足够大。这样在程序中引进两个指针pA和pB，分别指向绝对值较大者和较小者。而对绝对值相加,情况，让pA指向LA，pB指向LB，不区分绝对值大小。pA±pB可用通式pA+flag*pB来计算，flag为+1时即对应pA+pB，flag为-1时即对应pA-pB。需特别注意的是，对于相减，不够减时要进行借位，而当

最高位借位后正好为0时，结果的总位数应减1；对于加法，有最高进位时，结果的总位数应加1。

流程图中涉及的函数说明如下：

(1)cmp(int *LA，int *LB)函数，用于比较长整数LA与LB的绝对值大小，若LA绝对值大于LB绝对值则返回正值，LA绝对值小于LB绝对值返回负值，相等则返回0。

(2)max(int A，int B)函数，用于返回整数A与B中较大数。

另外，对流程图中的写法进行约定：(1)“：=”表示赋值，如“flag：=LA[0]+LB[0]”表示将“LA[0]+LB[0]”的结果赋给flag，相当于C中的赋值语句：“flag=LA[0]+LB[0]；”；(2)“：”表示比较运算，如“flag：1”表示flag与1比较。

(1)

点击查看答案

第2题

阅读以下应用程序说明和C程序，将C程序段中(1)-(7)空缺处的语句填写完整。

[说明]

以下[C程序]所完成的功能是在3X3方格中填入数字1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。系统输出满足该要求的所有填法。系统的部分输出结果如图3-18所示。

图3-18 系统的部分输出结果

3×3方格从第1行左上角方格开始的序号分别为0、1、2，第2行左边方格开始的序号分别为3、4、 5，第3行左下角方格开始的序号分别为6、7、8。以下[C程序]采用试探法，即从序号为0的方格(左上角)开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格寻找一个合理的可填整数，就要后退到前一方格，调整前一方格的整数。直至序号为8的方格(右下角)也填入合理的整数时，就找到了一个解，将该解输出，并调整序号为8的方格所填的整数，继续去找下一个解。

为了检查当前方格的填入整数的合理性，C程序引入二维数组checkMatrix，用于存放需要进行合理性检查的相邻方格的序号。

[C程序]

include ＜stdio.h＞

define N 12

int a [9]; /* 用于存储方格所填入的整数 */

int b[N+1];

int pos;

checkMatrix[][3] = {{-1},{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1} {4,6,-1}, 5,7,-1}};

void write(int a[])

{ int i, j;

for ( i = 0; i ＜ 3; i++)

for ( j = 0; j ＜ 3; j++)

printf("%3d",a[3*i+j]);

printf("\n");

}

int isPrime(int m)

{ int i;

if (m == 2)

return 1;

if (m == 1 || m % 2 == 0)

return 0;

for (i = 3; i * i ＜= m; )

{ if (m % i == O)

return 0;

i+ =2;

}

return 1;

}

int selectNum(int start)

{ int j;

for (j = start; j ＜= N; j++)

if (b[j])

return j;

return 0;

}

int check ( ) /* 检查填入pos位置的整数是否合理 */

{ int i, j;

for (i = 0; (j =(1)) ＞= 0; i++)

if (!isPrime(a[pos] + a[j]))

(2);

(3);

}

extend () /* 为下一方格找一个尚未使用过的整数 * /

{ a[(4)] = selectNum(1);

b[a[pos]] = 0;

}

void change() /* 为当前方格找下一个尚未使用过的整数(找不到回溯) */

{ int j;

while (pos ＞= 0 && (j = selectNum((5) ) == 0

(6);

if (pos ＜ 0)

return;

b[a[pos]] = 1;

a[pos] = j;

b[j] = 0;

}

find ( )

{ int k = 1;

pos = 0; a[pos] = 1; b[a[pos]] = 0;

de {

if (ok)

if ( (7) ) {

write (a);

change( );

}

else

extend( );

else

change( );

ok = check(pos);

} while (pos ＞=0);

}

main( )

点击查看答案

第3题

设n是k的倍数，有k个排好序的数表[图]，每个数表都有n/k...

设n是k的倍数，有k个排好序的数表，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是。使用顺序归并算法，即先归并和，接着把得到的数表-与归并，再把得到的数表-与归并，…，直到得到-。例如，那么归并过程是：---。以比较做基本运算，那么顺序归并算法最坏情况下的时间复杂度是（）。

A、

B、

C、

D、

E、

点击查看答案

第4题

设n是k的倍数，有k个排好序的数表[图]，每个数表都有n/k...

设n是k的倍数，有k个排好序的数表，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是。使用顺序归并算法，即先归并和，接着把得到的数表-与归并，再把得到的数表-与归并，…，直到得到-。例如，那么归并过程是：---。当顺序归并成数表-的过程中在最坏情况下的比较次数记作，那么满足递推方程和初值是:从下述答案中选择适当的答案填入上面的括号内。

A、

B、

C、

D、

E、

点击查看答案

第5题

给定含有 [图] 个不同的数的数组 [图] 。如果 [图] 中...

给定含有个不同的数的数组。如果中存在，则称是单峰的，并称是的“峰顶”。假设是单峰的，请把 a - d 四行代码补全到算法中使得算法正确找到的峰顶。。

A、d, c, a, b

B、d, c, b, a

C、c, d, b, a

D、d, b, c, a

E、d, a, b, c

点击查看答案

第6题

确定n个不同数的数组S和正整数i，[图]，求S中最大的i个...

确定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从小到大的次序输出。有下述算法：算法A：调用i次找最大算法Findmax每次从S中删除一个最大的数。算法B：对S排序，并输出S中最大的i个数。（1）分析A，B两个算法在最坏情况下的时间复杂度。（2）试设计一个最坏情况下时间复杂度的阶更低的算法，要求给出伪码。

点击查看答案

第7题

假设L含有n个不同的元素，其中[图]，k为非负整数。如果已...

假设L含有n个不同的元素，其中，k为非负整数。如果已知x在表L中，且在L的每个位置的概率相等，那么用顺序搜索算法查找元素x，该算法平均情况下的比较次数是多少？从下面备选的答案中选出正确答案的标号填入括号内。()

A、

B、

C、

D、

E、

F、

点击查看答案

第8题

若对[图]个只有三位数字的整数进行排序，可以用O(N)复...

若对个只有三位数字的整数进行排序，可以用O(N)复杂度将其排序的算法是（）

A、快速排序

B、插入排序

C、希尔排序

D、基数排序

点击查看答案

第9题

设有n项任务，加工时间分别表示为正整数[图]。现有2台同...

设有n项任务，加工时间分别表示为正整数。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。假设问题的解是，其中0或1. 如果，那么第i项任务放到第一台机器上加工；如果，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，那么它的目标函数是：

A、

B、

C、

D、

点击查看答案

第10题

设有n项任务，加工时间分别表示为正整数[图]。现有2台同...

设有n项任务，加工时间分别表示为正整数。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。假设问题的解是，其中或1. 如果，那么第i项任务放到第一台机器上加工；如果，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，那么它的目标函数是：

A、

B、

C、

D、

点击查看答案