|
计算机等级考试二级C++练习题(2)及解答
一、编程题。根据程序要求，写出函数的完整定义。
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;
}
答：
一，编程题答案
1. 程序为：
int CalcCapital (char *str)
{
if (str == NULL) return 0; //判断字符指针是否为空
int num_of_Capital = 0; //记录大写字母字符个数的变量，初值为0
for(int i=0; str[i] != 0x0; i++)
if (str[i] <= 'A' && str[i] >= 'Z') num_of_ Capital ++; //若是大写字母，则总数加1
return num_of_ Capital; //返回大写字母字符数
}
2．程序为：
float sum(int n)
{
if (n == 1) return 1;
else return sum(n-1) -(1.0/n)*(-1)n;
}
3．程序为：
Node * insNode(Node * head, int newValue)
{
Node * newNode = new Node; //申请新的节点空间
if (newNode == NULL) return NULL;//
newNode->data = newValue; //填充新节点的内容
newNode->next = NULL;
Node *pre, *cur;
Pre = head；
if (head == NULL) head = newNode; //插入到空链表的表头
else
if(newValue>=head->Value){
newNode->next=head;
head = newNode; //插入到链表的表头
}
else{ //在链表寻找插入点
Node *cur,*pre = head;
while(pre->next != NULL){
cur = pre->next;
if(newValue >= cur->Value) break;
else pre = cur;
}
if(pre->next!= NULL) newNode->next = cur;//若非末尾，则有下一节点
pre->next = newNode; //将新节点插入
}
}
return head;
}
4．程序可以有多种写法，下面是其中一种
char MinCode(char charAry[],int len=10)
{
char mixCode = 0x0;
for(int i=0; i <len; i++)
{
if (charAry [i] < mixCode)
mixCode = str[i];
}
return mixCode;
}
二、理解问答题：
问题1，答：
(A) bottom (NULL)
(B) top == NULL;
(C) ptop = top;
(D) pNew->nextItem = top;
(E) top = pNew;
问题2,答：不正确。因为类StackItem模板类的定义中用到了模板类Stack， Stack还没有定义，所以，必须先声明Stack是一个模板类，否则，编译程序就不知道标识符Stack代表什么样的含义，无法进行编译。
问题3,答：第11、26和47行的const修饰的都是函数的参数，表示在这个函数体中不能改它所修饰的参数的值。第27行的const修饰的是模板类Stack的成员函数is_empty()，它表示在函数is_empty()的函数体中不能改变任何数据成员的值。
问题4,答：析构函数中主要是释放存放的各个节点所占涌空间。因为Stack对象在其生存期间可能加入了很多节点，从堆中申请了一些内存空间。这些空间应随着对象的消亡而释放掉，所以，需要在析构函数中释放这些空间。
问题5,答：
|
语句号 |
1 |
2 |
3 |
4 |
5 |
|
对/错 |
错 |
对 |
错 |
错 |
对 | | 
