C程序设计专题 18-19年期末考试习题解答（下）

Section 3

注意明确程序目的，需要递归画出图中所示的图形。

（1）MidPoint函数的目的是求出中点并返回，中点坐标以结构类型VERTEX存储。

答案：mAB
（2）这一步的目的是画出当前三个顶点对应的三角形。

答案：DrawTriangle(A,B,C);

（3）（4）（5）当前画出三角形后，还要针对3个子三角形进行递归。

答案：FraTriangle(A,mAB,mCA);

FraTriangle(mAB,B,mBC);

FraTriangle(mCA,mBC,C);

注：保持顶点顺序一致，防止出错。

2.本题目的是：实现循环队列的各项操作。（数组实现，头指针和尾指针用数字（下标）表示）

①对于循环队列，尤其要注意区分队列已满、队列为空的条件。根据题干："wraps around" to the beginning if the last entry of the buffer is occupied when adding a new entry,可知队列已满的条件是rear和end差一位。

②还要看循环队列能否被塞满。请看CreateQueue函数中的初始化操作，一开始建立的是一个空队列，此时rear和front相等。这说明题中所给循环队列需要一个不存放数据的尾结点。

（6）注意取余数的运算，这一步非常重要，否则可能越界。

答案：Q->front==(Q->rear+1)%(Q->maxsize);

注：所谓队列已满，实际上尾结点仍然不存放数据，如果尾结点也存放数据，则队列满和空两种状态就无法辨别了。

（7）根据CreateQueue函数中的初始化条件，栈空时应该是首尾指针相同。

答案：Q->front==Q->rear;

（8）根据上述分析，我们知道rear对应的结点本身是不存放数据的。

Enqueue函数的实现过程：

若队列已满，则返回。

若队列未满，则首先在旧的尾结点处存放数据，再让尾结点后移。

答案：Q->pBase[Q->rear]=val;

（9）仍需注意节点移动时的取余运算。

答案：(Q->rear+1)%(Q->maxsize)；

（10）元素出队列，出队列元素的值是通过指针形式跨函数获取的。

答案：*val

3.本题考查图形库的基本操作。

（11）答案：InitGraphics( );

（12）考查回调函数的相关概念及用法。

答案：KeyboardEventProcess

（13）答案：TimerEventProcess

（14）积累cancelTimer函数的用法。

答案：cancelTimer(TIMER_BLINK100);

（15）切换画圆模式。

答案：isDisplayCircle=!isDisplayCircle

Section 4

1.

思路分析：本题目的是寻找第一个相同的物理结点。根据图示可知：一开始几个结点不同，到第一个共同结点之后，两个链表就相同了。首先确定哪个链表的起始部分结点比较多，得出结点之差n，让结点多的链表先走n个结点，之后两个链表同时走，如此完成遍历即可。

答案：

static ListNode* FindFirstCommonNode(ListNode* l1,ListNode* l2)
{
 int len1,len2,numLeftNodes;
ListNode *lPtr,*sPtr;
if(l1==NULL||l2==NULL)
return NULL;
len1=ListLength(l1);
len2=ListLength(l2);
if(len1>len2)
{
lPtr=l1;sPtr=l2;
numLeftNodes=len1-len2;
}
else
{
lPtr=l2;sPtr=l1;
numLeftNodes=len2-len1;
}
for(int i=0;i<numLeftNodes;i++)
 lPtr=lPtr->next;
while(lPtr&&sPtr&&lPtr!=sPtr)
{
lPtr=lPtr->next;
sPtr=sPtr->next;
}
return lPtr;

}

2.题中涉及二元选择排序，是针对普通选择排序法的一种改进版本。普通选择排序，每一轮只选择一个元素；而二元选择排序每一轮既选出最大元素，又选出最小元素，故遍历次数比普通选择排序减少一半。选择的过程就是选择排序区间从两边向中间一致缩小的过程。

答案：

void binSelection(int array[],int n)
{
   int k,tmp,lh,rh,minPos,maxPos;
   for(lh=0,rh=n-1;lh<rh;lh++;rh--)
   {
minPos=lh;maxPos=rh;
for(k=lh;k<=rh;k++)
{
   if(array[minPos]>array[k])
   minPos=k;
   else if(array[maxPos]<array[k])
maxPos=k;
}
tmp=array[lh];array[lh]=array[minPos];array[minPos]=tmp;
tmp=array[rh];array[rh]=array[maxPos];array[maxPos]=tmp;
   }
return;
}