题目内容
（请给出正确答案）
设
是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积.对于任意给定的d个整数
,用分治法设计一个有效算法,计算出满足
且最高次项系数为1的d次多项式P(x),并分析算法的效率.
如果结果不匹配，请 联系老师 获取答案
更多“设是一个d次多项式.假设已有一算法能在O（i)时间内计算一个…”相关的问题
A.O(lgn)
B.O (nlgn)
C.O(n)
D.O(n2)
A.H、U
B.H、Z
C.K、O
D.O、U
●试题一
阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
循环：i以1为步长，从2到n，反复执行
①准备
X＜-R［i］； (1) ；high＜-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key＜R［mid］．key
则high＜-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］＜-R［j］
④插入
R［low］＜-X
3．算法结束
某虚拟存储系统采用最近最少使用(LRU)页面淘汰算法，假定系统为每个作业分配3个页面的主存空间，其中一个页面用来存放程序。现有某作业的部分语句如下：
Var A：Array[1．．150，1．．100]OF integer；
i，j：integer；
FOR i：=1 to 150 DO
FOR j：=1 to 100 DO
A[i，j]：=0；
设每个页面可存放150个整数变量，变量i、j放在程序页中。初始时，程序及变量i、j已在内存，其余两页为空，矩阵A按行序存放。在上述程序片段执行过程中，共产生(16)次缺页中断。最后留在内存中的是矩阵A的最后(17)。
A．50
B．100
C．150
D．300
某虚拟存储系统采用最近最少使用(LRU)页面淘汰算法。假定系统为每个作业分配3个页面的主存空间，其中一个页面用来存放程序。现有某作业的部分语句如下：
Var A：Array [1．．128，1．．128] OF integer；
i，j：integer；
FOR i:＝1 to 128 DO
FOR j:＝1 to 128 DO
A[i，j]:＝0；
设每个页面可存放128个整数变量，变量i，j放在程序页中，矩阵A按行序存放。初始时，程序及变量i、j已在内存，其余两页为空。在上述程序片段执行过程中，共产生(27)次缺页中断。最后留在内存中的是矩阵A的最后(28)。
A．64
B．128
C．256
D．512
A.0
B. 0.5
C. 1
D. 2
Var A: Array[1..100,1..100] OF integer;
i,j: integer;
FOR i:=1 to 100 DO
FOR j:=1 to 100 DO
A[i,j]:=0;
设每个页面可存放200个整数变量，变量i、j存放在程序页中。初始时，程序及i、j均已在内存，其余3页为空。若矩阵A按行序存放，那么当程序执行完后共产生 （3） 次缺页中断；
A.50
B.100
C.5000
D.10000
A.7
B.8
C.9
D.10
