一、編程題。根據程序要求，寫出函數的完整定義。
1．寫一個函數，找出給定字符串中大寫字母字符（即’A’-‘Z’這26個字母）的個數（如字符串”China Computer Wrold”中大寫字母字符的個數為3個）。
函數的原型： int CalcCapital (char *str);
函數參數： str為所要處理的字符串；
函數返回值：所給字符串中數字字符的個數
2．寫一個函數，用遞歸函數完成以下運算:
sum(n) = 1 – 1/2 + 1/3 – 1/4 + … -(1/n)*(-1)n （其中n>0）
函數原型： float sum(int n);
函數參數：n為正整數。
函數返回值：相應于給定的n，右邊表達式運算結果。
提示：你可以使用遞歸表達式： sum(n) = sum(n-1) -(1/n)*(-1)n
3. 給定新數值，在一個按節點所存放數值從大到小排序的鏈表中，找適當位置插一個新節點，仍保持有序的鏈表，寫一個函數，完成此操作。
函數的原型： Node * InsNode(Node * head, int newValue);
其中，鏈表節點的定義如下：
struct Nodee{
int Value; //存放數值
Node * next; //指向鏈表中的下一個節點
};
函數參數：函數的第一個參數head指向鏈表頭一節點的指針，如果鏈表為空，則head的值為NULL。第二個參數newValue為所給定的插入新節點的新數值。
函數返回值：當成功地插入新的節點時，函數返回指向新鏈表頭一節點的指針，否則，若不能申請到內存空間，則返回NULL。
4．寫一個函數，找出給定數組中具有最小值的元素。
函數的原型：
char MinCode(char charAry[]);
函數參數：charAry所要處理的字符數組名；
函數返回值：返回具有最小ASCII碼的字符。
二、理解問答題：
下面的文件stack.h是一個堆棧類模板Stack的完整實現。在這個文件中，首先定義了一個堆棧元素類模板StackItem，然后，在這個類的基礎上定義了堆棧類模板Stack。在Stack中使用鏈表存放堆棧的各個元素，top指針指向鏈表的第一個節點元素，bottom指針指向鏈表的最后一個節點元素，成員函數push()將一個新節點元素加入（壓進）到堆棧頂部，pop()從堆棧頂部刪除（彈出）一個節點元素。為方便起見，程序中加上了行號。閱讀程序，根據程序后面的問題作出相應解答。
1. /*---------------------------------------------------------- -------------------*/
2. /********************* 文件stack.h ************************/
3. /*---------------------------------------------------------- -------------------*/
4. template <class Type>
5. class Stack;
6. /***************** 定義模板類StackItem ******************/
7. template<class Type>
8. class StackItem
9. {
10. public:
11. StackItem(const Type & elem):item(elem) {}
12. ~StackItem() {}
13. private:
14. Type item;
15. StackItem * nextItem;
16. friend class Stack<Type>;
17. };
18. /***************** 定義模板類Stack *********************/
19. template <class Type>
20. class Stack
21. {
22. public:
23. Stack():top( NULL), ____(A)_____ {}
24. ~Stack();
25. Type pop();
26. void push(const Type &);
27. bool is_empty() const { return ____(B) ______ ; }
28. private:
29. StackItem<Type> * top;
30. StackItem<Type> * bottom;
31. };
32. //模板類Stack的函數成員pop()的實現。
33. //從堆棧頂彈出一個節點，并返回該節點的值
34. template<class Type>
35. Type Stack<Type>::pop()
36. {
37. StackItem<Type> *ptop; //指向頂部節點的臨時指針
38. Type retVal; //返回值
39. ______(C) ________;
40. retVal = top->item;
41. top = top->nextItem;
42. delete ptop;
43. return retVal;
44. }
45. //模板類Stack的函數成員push()的實現
46. template<class Type>
47. void Stack<Type>::push(const Type & newItem)
48. {
49. StackItem<Type> *pNew = new StackItem<Type>( newItem);
50. ______(D)___________;
51. if (bottom == NULL) bottom = top = pNew;
52. else _____(E)_________;
53. }
54. //模板類Stack的析構函數~Stack()的實現
55. template<class Type>
56. Stack<Type>::~Stack()
57. {
58. StackItem<Type> *p = top, *q;
59. while(p != NULL) {
60. q = p->nextItem;
61. delete p;
62. p = q;
63. }
64. }
問題1： 程序中有幾處填空，將它們完成。
（A）_________________________________________________
（B）_________________________________________________
（C）_________________________________________________
（D）_________________________________________________
（E）_________________________________________________
問題2：程序第4，5行有什么作用？如果沒有這兩行語句，程序還正確嗎？
問題3：程序中多處出現const，請分別說明它們各自表示什么含義。
問題4：程序中模板類Stack的析構函數主要做了什么事情？為什么要這么做？
問題5：下面的程序使用了stack.h文件中定義的類模板，請說明下列程序中定義堆棧對象的語句(1-5)是否正確。
#include “stack.h”
void main()
{
Stack q1; // 1
Stack<float> q2; // 2
Stack<float> q3(10); // 3
Stack<float> q4[10]; // 4
Stack<float> *q5 = new Stack<int>; // 5
//....
delete q5;
}
答：
