堆数据结构定义如下：
对于n个元素的关键字序列{a1，a2，...,an}，当且仅当满足下列关系时称其为堆。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若顶堆元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。
图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开始）。
【问题1】
（1）A->int_array[0]
（2）A->int_array[0]=A->int_array[A->array_size-1]
（3）A->array_size-1
（4）A->int_array[PARENT(i)]＜key
（5）A->int_array[i]=key
【问题2】
（6）O(1)（7）O(lgn)（8）O(lgn)
【问题3】
（9）3
【问题1】
本题考查堆数据结构的相关内容。题目告诉我们函数heapMaximum（A）的功能返回大顶堆A中的最大元素；函数heapExtractMax（A）的功能是去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆；而函数maxHeaplnsert（A，key）的功能是把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
第（1）空在函数heapMaximum（A）中，而且从程序中可以看出，是返回的结果，那么应该是大顶堆中最大元素，就应该是A->int_array[0]。
第（2）空在函数heapExtractMax（A）中，根据该函数的功能描述，并结合程序可以看出，第（2）空是在将最大元素移出后，那么接下了来应该处理将最后一个元素“提前”到堆顶位置，那么就应该是A->int_array[0]=A->int_array[A->array_size-1]。
第（3）（4）（5）空都在函数maxHeaplnsert（A，key）中。从程序和函数的功能我们可以知道，从程序第（3）空最后，其作用是找到元素key的插入位置并插入该元素。第（3）空是给变量i赋值，从后面的程序中我们可以看出i是做为数组下标的；而查找元素插入的位置应该从后往前的顺序，因此i的初值应该为A->array_size–1，从循环中也可以看出i的值在逐渐变小。
第（4）空是循环的一个条件，而循环的作用是找到合适的插入位置，由于大顶堆的特点是根节点的值大于左右子树节点上的值，那么找到比待插入元素大的父节点时，应该就找到了它插入的合适位置，而每次操作后i的值被赋值为PARENT（i），很显然这是找到其父节点的存储位置，因此循环结束的一个条件就是找到一个比key值大的父节点，那么循环继续的条件就是父节点的值小于key的值，所以本空的答案为A->int_array[PARENT(i)]＜key。＜key。
第（5）空就是插入元素，所以应该填A->int_array[i]=key。
【问题2】
根据题目描述，heapMaximum用来返回大顶堆A中的最大元素，而且大顶堆已经建成，只需要通过一步操作就能取到。因此时间复杂度是O（1），
而对于heapExtractMax是用来去掉大顶堆A的根，然后重新建堆，当输出堆顶结点并将堆中最后一个结点设置为根结点之后，根结点将有可能不再满足堆的性质，所幸的是整个序列也只有根结点一处的堆结构可能被破坏，其余结点仍然满足堆性质，故可利用性质进行堆调整，算法的基本思想为：将新堆顶沿着其关键字较大的孩子结点向下移动，直到叶子结点或者满足堆性质为止。因此相对于有N个元素的堆，只需要log2n次比较即可完成，因此时间复杂度是O（log2n），这与书本说堆排序的算法时间复杂度是：O(nlog2n)不冲突，因为书本上是对堆中所有元素进行操作，而这里其实相当于只将一个元素入堆，因此少了一个n。同样的道理可以得到maxHeaplnsert的时间复杂度O（log2n）。
【问题3】
这个我们可以结合题目给出的那个大顶堆的图来看，首先将key插入在最后，应该是8这个节点的右子树，由于10比8大，所以应该互换，再与节点9比较，由于10仍然大于9，所以也应该互换，这个时候再与其父节点15比较，由于小于15，所以不需要再调整，那么调整后的结果就是10这个元素应该作为根节点15的右子树。那么很显然10应该是在堆A中第3个位置。
一台主机的IP地址为202.123.25.36，掩码为255.255.254.0。如果该主机需要在该网络进行直接广播，那么它应该使用的目的地址为（ ）
在计算机系统的日常维护工作中，应当注意硬盘工作时不能__(2)__。另外，需要防范病毒，而__(3)__是不会被病毒感觉的。
有 4 个 IP 地址：201.117.15.254、201.117.17.01、201.117.24.5 和 201.117.29.3，如果子网掩码为 255.255.248.0，则这 4 个地址分别属于3个子网；其中属于同一个子网的是（）
在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位，每秒钟传送200个字符，采用4相位调制，则码元速率为（）。
在 Windows 中，运行（ ）命令得到下图所示结果。以下关于该结果的叙述中，错误的是（ ）。
Pinging 59.74.111.8 with 32 bytes of data:
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Ping statistics for 59.74.111.8:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 3ms, Maximum = 5ms, Average = 4ms
在ISO OSF/RM参考模型中，七层协议中的__(1)__利用通信子网提供的服务实现两个用户进程之间端到端的通信。在这个模型中，如果A用户需要通过网络向B用户传送数据，则首先将数据送入应用层，在该层给它附加控制信息后送入表示层；在表示层对数据进行必要的变换并加头标后送入会话层；在会话层加头标送入传输层；在传输层将数据分解为__(本题)__后送至网络层；在网络层将数据封装成__(3)__后送至数据链路层；在数据链路层将数据加上头标和尾标封装成__(4)__后发送到物理层；在物理层数据以__(5)__形式发送到物理线路。B用户所在的系统接收到数据后，层层剥去控制信息，把原数据传送给B用户。
在OSI/RM中，解释应用数据语义的协议层是（）。
在TCP/IP协议栈中，ARP协议的作用是（）,RARP协议的作用是（请作答此空）。
在地址 http://www.dailynews.com.cn/channel/welcome.htm 中，www.dailynews.com.cn 表示（ ），welcome.htm 表示（请作答此空）。
在电子表格软件Excel中，假设A1单元格的值为15，若在A2单元格输入“=AND(15＜A1，A1＜100)”，则A2单元格显示的值为 （）
