四、程序与算法设计题(30分,共3小题,每小题10分)(答在试卷上的内容无效)重要说明:此题允许使用C++语言作答。
1、用如下公式计算πI的近似值。要求计算到最后一项绝对值小于 1 0 − 6 10^{-6} 10−6时停止计算;输出结果保留4位小数。(10 分)
π 4 = 1 − 1 3 + 1 5 − 1 7 + 1 9 − … \frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\dots 4π=1−31+51−71+91−…
#include <stdio.h> #define exp 1e-6 int main() { double flag = 1, sum = 0; int fm = 1; while (1.0 / fm > exp) { sum += flag / fm; flag = -flag; fm += 2; } printf("pi = %.4lf", 4 * sum); }
2、编程打印如下字符图形到屏幕上和字符文件7a1.txt中。打印图形前,要求打印行数n (1<=n<=9)由键盘输入(10分)
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 (n=5时图形)
#include <stdio.h> int main() { int n; scanf("%d", &n); FILE *fp = fopen("a1.txt", "w"); for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) printf("%d ", j), fprintf(fp, "%d ", j); putchar('\n'), putc('\n', fp); } return 0; }
3、若二叉树采用二叉链表存储结构,其结点及结点指针数据类型定义如第二大题第17小题所示。已知二叉树根结点地址bt以及某字符key,写一个算法,在二叉树中查找字符key所在结点。已知二叉树各结点data域值无重复。若查找成功,返回key所在结点地址;否则,返回NULL。(10 分)
typedef struct node { char data; struct node *lchild, *rchild; } BiTNode, *BiTree; 其中,lchild 和rchild分别表示结点的左子树和右子树根结点地址
提示:利用先序递归遍历算法;函数原型建议采用如下两种形式之一一。
(1) 函数原型
BiTree locate(BiTree bt,char key);
函数调用格式为: BiTree p = locate(bt,key);
(2)函数原型二
void locate (BiTree bt,char key, BiTree *p);/C语言/
void locate (BiTree bt,char key, BiTree &p); /C++语言/
函数调用格式为:
BiTree p = NULL;
Locate(bt,key,&p);/C语言/
Locate(bt,key,p); /C 语言/
#include <stdio.h> typedef struct node { char data; struct node *lchild, *rchild; } BiTNode, *BiTree; void locate(BiTree bt, char key, BiTree *p) { if (bt == NULL) return; if (bt->data == key) { p = bt; return; } locate(bt->lchild, key, p); if (p == NULL) locate(bt->rchild, key, p); }