程序存储问题 问题描述：假设有n个程序（1,2,3....,n）要...

程序存储问题 问题描述：假设有n个程序（1,2,3....,n）要存放在长度为L的磁带上。程序i存放在磁带上的长度是,. 程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得尽量快地能够在磁带上存储尽可能多的程序。 数据输入：第一行读入2个正整数，分别表示文件个数n和磁带程度L;第二行读入n个正整数，分别表示n个文件存储在磁带上的长度。 输出：输出1个整数数为满足要求的最多存储的文件数 输入示例： 6 50 2 3 13 8 80 20 输出： 5 下面的选项正确的是（ ）

A、将程序按照在磁带上的存储长度非递减排序，假设排序后，第i个程序的长度为,其中且。则采用贪心算法，将程序长度最小的程序依次存放到磁带上，直到第k个磁带不能存储到磁带，则结束。磁带能够存放的程序个数为k-1(k<n),满足： data="280872">且

B、穷举法，枚举所有的存放程序到磁带且不会空间不够的情况，其中最大的程序数量就是答案。

C、递归法，将第n个程序放到磁带和不放到磁带，各是2种不可能同时出现的方法，比较这2种方法看哪一种放到磁带的程序数量更多，就选择哪一种放法。

D、先如果,则将所有程序都可以放入磁带，因此能够存放的最多程序数量为n。 否则，将程序按照在磁带上的存储长度非递减排序，假设排序后，第i个程序的长度为,其中且。则采用贪心算法，将程序长度最小的程序依次存放到磁带上，直到第k个磁带不能存储到磁带，则结束。磁带能够存放的程序个数为k-1(k<n),满足： data="280872">且

某程序中有如下循环代码段P： for (i=0; i<n; 1 2 3 4 5 6 i++) sum+="A[i];" 假设编译时变量sum和i分别分配在寄存器r1和r2中。常量n在寄存器r6中，数组a的首地址在寄存器r3中，程序段p的起始地址为08048100h，对应汇编代码和机器代码如下表所示： 编号 地址 机器码 汇编码 操作注释 08048100h 00022080h loop: sll r4,r2,2 08048104h 00083020h add r4,r4,r3 (r4)+(r3)→r4 08048108h 8c850000h load r5,0(r4) ((r4)+0)→r5 0804810ch 00250820h r1,r1,r5 (r1)+(r5)→r1 08048110h 20420001h addi r2,r2,1 (r2)+1→r2 08048114h 1446fffah bne r2,r6,loop if (r2) ≠ (r6) goto loop 如果执行上述代码的计算机采用32位定长指令字，其中的分支指令bne格式如下： 31:26 25:21 20:16 15:0 op rs rd offset 其中的op为操作码，rs和rd为寄存器编号，offset为偏移量（用补码表示），请回答下列问题： 计算机的存储器编址单位是( ) a. 8位 b. 16位 c. 32位 d. 64位>

某程序中有如下一段循环代码段 P： for (i = 0; i < N; i++) sum += A[ i ]; 假设编译时变量 sum 和 i 分别分配在寄存器 R1 和 R2 中，常量 N 在寄存器 R6 中，数组 A 的首地址在寄存器 R3 中，程序段 P 的起始地址为 08048100H，对应的汇编码和机器代码如下所示： 指令序号 指令地址 机器代码 汇编码 操作注释 1 08048100H 00022080H loop: sll R4, R2, 2 (R2)<<2→r4 1 2 3 4 5 6 32 08048104h 00083020h add r4, r3 (r4)+(r3)→r4 08048108h 8c850000h load r5, 0(r4) ((r4)+0)→r5 0804810ch 00250820h r1, r5 (r1)+(r5)→r1 08048110h 20420001h addi r2, (r2)+1→r2 08048114h 1446fffah bne r6, loop if (r2)≠(r6) goto 执行上述代码的计算机中，存储器 m 采用 位定长指令字，其中分支指令 采用如下格式： 31:26 25:21 20:16 15:0 op rs rd offset 指令格式中的 代表操作码字段， 和 都代表寄存器编号， 为偏移量常数（用补码表示）， 请回答下列问题，并说明理由： （1）存储器 的编址单位是什么？ （2）已知 sll 指令实现左移功能，数组 a 中每个元素占多少位？ （3）上表中 指令的 字段的值是多少？已知 指令采用相对寻址方式， pc 的当前内容为指令bne 的地址，通过分析表中指令地址和 指令内容，推断>

阅读下列说明和C代码，回答问题1至问题 3，将解答写在答题纸的对应栏内。

【说明】

堆数据结构定义如下：

在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1 是一个大顶堆的例子。

堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。

假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A, n, index)。

下面将C代码中需要完善的三个函数说明如下：

（1）heapMaximum(A)：返回大顶堆A中的最大元素。

（2）heapExtractMax(A)：去掉并返回大顶堆 A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。

（3）maxHeapInsert(A, key)：把元素key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。

优先队列采用顺序存储方式，其存储结构定义如下：

define PARENT(i) i/2

typedef struct array{

int *int_array; //优先队列的存储空间首地址

int array_size; //优先队列的长度

int capacity; //优先队列存储空间的容量

} ARRAY;

【C代码】

（1）函数heapMaximum

int heapMaximum(ARRAY *A){ return （1） ; }

（2）函数heapExtractMax

int heapExtractMax(ARRAY *A){

int max;

max = A->int_array[0];

（2） ;

A->array_size --;

heapify(A,A->array_size,0); //将剩余元素调整成大顶堆

return max;

}

（3）函数maxHeapInsert

int maxHeapInsert(ARRAY *A,int key){

int i,*p;

if (A->array_size == A->capacity) { //存储空间的容量不够时扩充空间

p = (int*)realloc(A->int_array, A->capacity *2 * sizeof(int));

if (!p) return -1;

A->int_array = p;

A->capacity = 2 * A->capacity;

}

A->array_size ++;

i = （3） ;

while (i > 0 && （4） ){

A->int_array[i] = A->int_array[PARENT(i)];

i = PARENT(i);

}

（5） ;

return 0;

}

【问题 1】（10分）

根据以上说明和C代码，填充C代码中的空（1）～（5）。

【问题 2】（3分）

根据以上C代码，函数heapMaximum、heapExtractMax和 maxHeapInsert的时间复杂度的紧致上界分别为 （6） 、 （7） 和 （8） （用O 符号表示）。

【问题 3】（2分）

若将元素10插入到堆A =〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉中，调用 maxHeapInsert函数进行操作，则新插入的元素在堆A中第 （9） 个位置（从 1 开始）。

说明：堆数据结构定义如下。对于n个元素的关键字序列（a1，a2，...，an），当且仅当满足下列关系时称其为堆：在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图8.11是一个大顶堆的例子。堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小项堆。以下考虑最大优先队列。假设现已建好大顶堆A，且已经实现了调整堆的函数heapify（A，n，index）。下面将C代码中需要完善的3个函数说明如下。

（1）heapMaximum（A）：返回大顶堆A中的最大元素。

（2）heapExtractMax（A）：去掉并返回大顶堆A的最大元素，将最后一个元素"提前"到堆顶位置，并将剩余元素调整成大顶堆。（

3）maxHeapInsert（A，key）：把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。优先队列采用顺序存储方式，其存储结构定义如下：C代码：

阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的

对应栏内。

【说明】

两个包含有限个元素的非空集合A、B的相似度定义为IAUBI/IA U Bl，即它们的交

集大小(元素个数)与并集大小之比。

以下的流程图计算两个非空整数集合（以数组表示）的交集和并集，并计算其相似

度。己知整数组A[1：m】和B【1：n】分别存储了集合A和B的元素（每个集合中包含的元素

各不相同），其交集存放于数组C[1：s】，并集存放于数组D【1：t】，集合A和B的相似度存

放于SIM。

例如，假设A={1，2，3，4}，B={1，4，5，6}，则C={1，4}，D={1，2，3，4，5，

6}，A与B的相似度SIM=1/3。

A、254

B、244

C、258

D、262

【说明】

c语言常用整型(int)或长整型(1ong)来说明需要处理的整数，在一般情况下可以满足表示及运算要求，而在某些情况下，需要表示及运算的整数比较大，即使采用更长的整型(例如，long long类型，某些c系统会提供)也无法正确表示，此时可用一维数组来表示一个整数。假设下面要处理的大整数均为正数，将其从低位到高位每4位一组进行分组(最后一组可能不足4位)，每组作为1个整数存人数组。例如，大整数2543698845679015847在数组A中的表示如下(特别引入-1表示分组结束)：

在上述表示机制下，函数add_large_number(A，B，c)将保存在一维整型数组A和B中的两个大整数进行相加，结果(和数)保存在一维整型数组c中。

【c函数】

Void add_large_number(int A[]， int B[]， int c[])

{

int i，cf； ／*cf存放进位*／

int t，*p； ／*t为临时变量，p为临时指针*／

cf= ( 1) ；

for(i=0 ； A[i]>-l＆＆B[i]>-1；i++){

／*将数组A、B对应分组中的两个整数进行相加*／

t=(2) ；

C[i]=t％i0000；

cf= (3) ；

}

if( (4))P=B；

else P=A；

for(；P[i]>-1；i++){／*将分组多的其余各组整数带进位复制入数组C*／

C[i]=(p[i]+cf)％i0000； cf=(p[i]+cf)／10000；

}

if(cf>0) C[i++]=cf；(5)=-1； ／*标志”和数”的分组结束*／

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

【函数】

void print(BinTreeNode*t；DateType ＆x){

stack ST；int i，top；top=0；∥置空栈

while(t!=NULL ＆＆t->data!=x‖top!=0)

{while(t!=NULL ＆＆ t->data!=x)

{

∥寻找值为x的结点

(1) ；

ST［top］．ptr=t；

ST［top］．tag=0；

(2) ；

}

if(t!=Null ＆＆ t->data==x){∥找到值为x的结点

for(i=1； (3) ；i＋＋)

printf("％d"，ST［top］．ptr->data)；}

else{

while( (4) )

top--；

if(top>0)

{

ST［top］．tag=1；

(5) ；

}

}

}

A、F1可能是F2和F3的合力

B、F2可能是F1和F3的合力

C、F3可能是F1和F2的合力

D、所有答案均不对