C program design topic 15-16 final exam exercise solutions (Part 1)

Section 1

1. The second element out of the stack is n, Indicates that the first element out of the stack is 1 To n-1 Any one of , When other elements are released from the stack, the principle of "first in, last out" should be strictly followed , You can't arrange or combine . So the number of types of the stack sequence is n-1.

answer ：C

2. This question is to examine the calculation method of the inverse Polish expression ： When it comes to numbers , Direct stack ; Binary operator encountered , Take two elements directly from the top of the stack , About this operator , Put the result back on the stack . There is only one number left in the stack , Traversal of the expression is complete , This number is the final result of the operation , The whole process ends after the stack is released .

answer ：D

3. This question examines how members of the structure can access , The pointer -> Structural members , Structure variable name . Structural members .

answer ：B

4. Pay attention to understanding expressions int (*func(int))(double); The meaning of ：

func Is a function name ,(int) Indicates that the parameter received by the corresponding function is a int Type parameter , The rest is the return value type of the function . The function returns a function pointer , receive double Type parameter , return int Type value .

answer ：C

5. Pay attention to the wrong setting of macro replacement , To put “ Macro replace ” Write the following sentences completely with a pen , Then calculate the value of the formula , Otherwise, it's easy to make mistakes . The expression after the replacement of this question is 2*3*2*3-2+3*2+3, The calculation result is 43.

answer ：A

6. This question examines the step size of different types of pointers . In limine ,p Is a structure pointer , so p+1 Point to a[1] Structural variable ; Then cast the type ,p From structure pointer to integer pointer ,p+1 Points to an integer 5; then p+2, Pointing to 7. Finally, the result of dereference is 7.

answer ：B

7.A term ,finding someone in your telephone book, If the names of the people in the phone book meet lexicographic order, You can use binary search , The time complexity is O(logn), Instead of O(n).BCD All three terms are linear time complexity .

answer ：A

8.ACD It is obviously a constant time complexity （ The number of operations does not vary with n To increase by ）, and B Term is linear （O(n)） Time complexity .

answer ：B

9. Two point search is balanced Of , Based on half search , So the worst case scenario is until the search interval is only 1 Elements , Time complexity is also O(logn). The average time complexity is O（logn）. The best case is that the element to be searched is just the middle element of the whole search range , The time complexity is O（1）.

answer ：A

10. This question is about ASCII The correspondence between code value and numeric character , And numeric characters in %d,%c Different output results under . Note that the steps of recursion are ： Recursion first , Post output standard . So first dsp(s+1) Until the string termination element is encountered \0, No more recursion , Output '\0' The corresponding value 0, return , Output '1' Corresponding ASCII Code value 50, return , Output '0' Corresponding ASCII Code value 49, End function call .

answer ：D

Section 2

【 Methods to summarize 】 This question type pays attention to the role of understanding and evaluation procedures , Once you have a deep understanding of the role of the program , You can easily see the result .

1. We observe while The internal calculation steps of the loop , Found that this is the use of Qin Jiushao algorithm to calculate the value of the polynomial program . One side , Can follow the program using Qin Jiushao algorithm to calculate polynomials ; On the other hand , You can also directly look at the graph to calculate the polynomial value . Use two methods to calculate , Mutual verification , Improve accuracy .

answer ：42

2. Specify operator priority ：-> First priority ,++ Second priority . Besides , The three operations are independent of each other , That is, the previous operation does not affect the subsequent operation .

（1） That's right p->s Conduct ++ operation , In dereference .p->s Is a pointer , Start pointing at 'a',++ Point back 'b', Dereference leads to 'b'.

（2） That's right p->x Conduct ++ operation ,p->x The original for 1,++ The latter value is 2. Be careful ++ On the front , The new value is returned .（ It can be said that first ++ After the return ）

（3）p Is a structure pointer ,p+1 Give Way p Point to the structure variable a[1], use ->x Or get 3.

answer ：（1）'b'

（2）2

（3）3

3. The value entered is 2, Call functions and CMDS[2] Corresponding function c, Output c.

4. First step ：

Be careful NMAX The value of is 8, therefore getIntArray At most, only the front 8 A numerical . Because... Does not exist in the input sequence 0, That there is no temp==sentinel The situation of , So read in the front one by one 8 After number ,return 8, end getIntArray Function call .

Pay attention later bs(x+num/4,num/2), therefore bs The function operation is for the... In the input sequence 3 To the first 6 Elements .

The second step ： Don't go through it step by step bs function , Still evaluation bs Function function . Its essence is bubble sort（ Ascending sort ）, The first i The trip guarantees the i Small numbers are in place .

answer ：3#4#5#6#7#8#9#10#

5. This question examines recursive calls , Pay attention to step-by-step calculation when making a draft .（ The following equal signs are all equal signs of mathematical calculation ）

ack(2,1)=ack(1,ack(2,0)). Here we first calculate ack(2,0), Count again ack(1,ack(2,0)).

ack(2,0)=ack(1,1)=ack(0,ack(1,0))

because ack(1,0)=ack(0,1)=2

so ack(2,0)=ack(0,2)=3

So the problem turns into ack(1,3) The calculation of . According to the recursive function ,ack(1,3)=ack(0,ack(1,2)).

To calculate ack(1,2),ack(1,2)=ack(0,ack(1,1)), We have already calculated ack(1,1)=ack(2,0)=3, therefore ack(1,2)=ack(0,3)=4,

So the final result =ack(1,3)=ack(0,4)=5.

answer ：5