C program design topic 18-19 final exam exercise solutions (Part 2)

Section 3

Pay attention to the purpose of the procedure , You need to recursively draw the graph shown in the figure .

（1）MidPoint The function finds the midpoint and returns , The midpoint coordinates are based on the structure type VERTEX Storage .

answer ：mAB
（2） The purpose of this step is to draw the triangle corresponding to the current three vertices .

answer ：DrawTriangle(A,B,C);

（3）（4）（5） Now draw a triangle , But also for 3 Recursion of sub triangles .

answer ：FraTriangle(A,mAB,mCA);

FraTriangle(mAB,B,mBC);

FraTriangle(mCA,mBC,C);

notes ： Keep the vertex order consistent , Prevent mistakes .

2. The purpose of this question is ： Implement the operations of the circular queue .（ Array implementation , The head and tail pointers are numbered （ Subscript ） Express ）

① For loop queues , In particular, pay attention to distinguish when the queue is full 、 The condition that the queue is empty . According to the question ："wraps around" to the beginning if the last entry of the buffer is occupied when adding a new entry, The condition that the queue is full is rear and end One bit short .

② It also depends on whether the circular queue can be filled . Please have a look at CreateQueue Initialization operation in function , At the beginning, an empty queue is established , here rear and front equal . This shows that the circular queue given in the question needs a tail node that does not store data .

（6） Pay attention to the operation of remainder , This step is very important , Otherwise, it may cross the border .

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

notes ： The so-called queue is full , In fact, the tail node still does not store data , If the tail node also stores data , The queue is full or empty .

（7） according to CreateQueue Initialization condition in function , When the stack is empty, the first and last pointers should be the same .

answer ：Q->front==Q->rear;

（8） According to the above analysis , We know rear The corresponding node itself does not store data .

Enqueue Function implementation process ：

If the queue is full , Then return to .

If the queue is not full , First, store the data at the old tail node , Then move the tail node back .

answer ：Q->pBase[Q->rear]=val;

（9） You still need to pay attention to the remainder operation when the node moves .

answer ：(Q->rear+1)%(Q->maxsize);

（10） Element out of queue , The value of the out of queue element is obtained across functions in the form of a pointer .

answer ：*val

3. This question examines the basic operation of the graphic library .

（11） answer ：InitGraphics( );

（12） Check the related concepts and usage of callback function .

answer ：KeyboardEventProcess

（13） answer ：TimerEventProcess

（14） The accumulation of cancelTimer Function usage .

answer ：cancelTimer(TIMER_BLINK100);

（15） Switch the circle drawing mode .

answer ：isDisplayCircle=!isDisplayCircle

Section 4

1.

Thought analysis ： The purpose of this problem is to find the first same physical node . According to the diagram ： The first few nodes are different , After the first common node , The two linked lists are the same . First, determine which linked list has more initial nodes , Get the difference of nodes n, Let the linked list with many nodes go first n Nodes , Then the two linked lists go at the same time , This completes the traversal .

answer ：

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. The question involves binary choice sorting , It is an improved version of the general selective sorting method . Normal selection sort , Select only one element per round ; And binary selection sorting selects the largest element in each round , And choose the smallest element , Therefore, the number of iterations is reduced by half compared with the ordinary selection sorting . The selection process is the process of selecting the sorting range to narrow from both sides to the middle .

answer ：

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;
}