问题 解答题
设A是由2×4个整数组成的2行4列的数表,如果某一行(或某一列)各数之和为负数,则改变该行(或该列)中所有数的符号,称为一次“操作”.
(1)数表A如表1所示,如果经过两次“操作”,使得到的数表每行的各数之和与每列的各数之和均为非负整数,请写出每次“操作”后所得的数表;(写出一种方法即可)
表1.
1
2
3
﹣7
﹣2
﹣1
0
1
(2)数表A如表2所示,若经过任意一次“操作”以后,便可使得到的数表每行的各数之和与每列的各数之和均为非负整数,求整数a的值
表2.
a
a2﹣1
﹣a
﹣a2
2﹣a
1﹣a2
a﹣2
a2
答案

解:(1)根据题意得:

改变第4列改变第2行

(2)a=1

分析:(1)根据某一行(或某一列)各数之和为负数,则改变改行(或该列)中所有数的符号,称为一次“操作”,先改变表1的第4列,再改变第2行即可;

(2)根据每一列所有数之和分别为2,0,﹣2,0,每一行所有数之和分别为﹣1,1,然后分别根据如果操作第三列或第一行,根据每行的各数之和与每列的各数之和均为非负整数,列出不等式组,求出不等式组的解集,即可得出答案。

解:(1)根据题意得:

改变第4列改变第2行

(2)∵每一列所有数之和分别为2,0,﹣2,0,每一行所有数之和分别为﹣1,1,

∴①如果操作第三列,为:

aa2﹣1a﹣a2
2﹣a1﹣a22﹣aa2
 则第一行之和为2a﹣1,第二行之和为5﹣2a,每一列之和为非负整数,

解得:

又∵a为整数,∴a=1或a=2。

②如果操作第一行,为:

      ﹣a1﹣a2aa2
2﹣a1﹣a2a﹣2a2
则每一列之和分别为2﹣2a,2﹣2a2,2a﹣2,2a2,每一行之和为非负整数,

解得:a=1。

此时2﹣2a2=0,2a2=2,

综上可知:a=1。

问答题

试题四

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

【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{al,a2,…,an},当且仅当满足下列关系时称其为堆。

 

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

堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构,优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。 假设现已建好大顶堆A,且已经实现了调整堆的函数heapify(A,n,index)。

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

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

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

(3) maxHeaplnsert(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)函数maxHeaplnsert int maxHeaplnsert(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; }

根据以上说明和c代码,填充c代码中的空(1)~(5)。

单项选择题