西南交通大学840数据结构编程大题-2014年

四、程序与算法设计题(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 
#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 

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