跳到主要内容

筑波大学 理工情報生命学術院 システム情報工学研究群 情報理工学位プログラム 2018年8月実施 基礎科目 問題IV

标签：

Author​

祭音Myyura

Description​

二分木を用いて int 型の値の集合を格納するデータ構造を C 言語で実装する． 図 1 に，二分木の各ノードの構造体 node の定義を示す． 構造体node は，表 1 に示した関数で操作される． その関数の実装を図 2 に示す．ただし，関数 malloc は常に成功するものとする． このとき以下の問いに答えなさい．

struct node {
    int value;
    struct node *left;
    struct node *right;
};

図 1: 構造体 node の定義
​

表 1: 構造体 node を操作する関数
​

関数説明
struct node *new_node(int value, struct node *left, struct node *right)新たなノードを作成し，値 value，左の子ノードへのポインタ left，右の子ノードへのポインタ right を設定し，作成したノードのポインタを返す．
void traverse(struct node *n)ポインタ n が示すノードを根とする二分木に含まれるノード群の値を中順にて標準出力に出力する（出力の順序は，左の部分木に格納された値の集合，根の値，右の部分木に格納された値の集合とする）．
#include <stdlib.h>
#include <stdio.h>

struct node *new_node(int value, struct node *left, struct node *right)
{
    struct node *n = malloc(sizeof(struct node));
    n->value = value;
    n->left = left;
    n->right = right;
    return (n);
}

void traverse(struct node *n)
{
    if (n == NULL) return;
    traverse(n->left);
    printf("%d\n", n->value);
    traverse(n->right);
}

図 2: 表 1 に示した関数の実装
​

(1) 以下に示す関数 main() が実行されたとき，この関数が標準出力に出力する内容を答えなさい．

int main()
{
    struct node *top;
    top = new_node(5, new_node(9, NULL, NULL), new_node(7, NULL, NULL));
    traverse(top);
    return (0);
}

(2) 二分木を深さ優先で走査する方法としては，関数 traverse() で実装した中順以外に，前順と後順がある． 前順で走査する関数と後順で走査する関数を以下の表に示す．これらの関数を定義しなさい．

関数説明
void pre_order_traverse(struct node *n)ポインタ n が示すノードを根とする二分木に含まれるノード群の値を前順にて標準出力に出力する（出力の順序は，根の値，左の部分木に格納された値の集合，右の部分木に格納された値の集合とする）．
void post_order_traverse(struct node *n)ポインタ n が示すノードを根とする二分木に含まれるノード群の値を後順にて標準出力に出力する（出力の順序は，左の部分木に格納された値の集合，右の部分木に格納された値の集合，根の値とする）．

(3) 関数 traverse() を用いて値が昇順で出力されるような二分木となるように値を挿入する関数insert() を以下の表に示す． ただし，既に二分木に格納されている値と同じ値がこの関数に与えられることはないものとする． 関数 insert() が正しく動作するように，以下の空欄 [ (a) ] ~ [ (e) ] を埋めなさい．

関数説明
struct node *insert(struct node *top, int value)ポインタ top が NULL のときは新しくノードを作成し，そのノードに値を格納し，そのノードへのポインタを返す．それ以外の場合，ポインタ top が示すノードに格納されている値よりも値 value が小さい場合には左の部分木に値 value を格納するために再帰的にこの関数を呼んでポインタ top を返し，大きい場合には右の部分木に値 value を格納するために再帰的にこの関数を呼んでポインタ top を返す．
struct node *insert(struct node *top, int value)
{
    if (top == NULL)
        return (new_node(value, NULL, NULL));
    if (value < [空欄 (a)])
        [空欄 (b)] = insert([空欄 (c)]);
    else
        [空欄 (d)] = insert([空欄 (e)]);
    return (top);
}

(4) 設問 (3) で作成した関数 insert() を用いて空の二分木に3つの値 5，7，9 を挿入する関数 main() を以下に示す． この関数を実行したときに，関数 insert() が呼び出される回数（関数 insert() が再帰呼び出しにより呼び出される回数も含める）を答えなさい．

int main()
{
    struct node *top = NULL;
    top = insert(top, 5);
    top = insert(top, 7);
    top = insert(top, 9);
    traverse(top);
    return (0);
}

(5) 設問 (4) で示した関数main() では，空の二分木に3つの値 5，7，9 をこの順序で挿入している． この順序を変えることで関数 insert() が呼び出される回数が変化する． 3つの値 5，7，9 を空の二分木に挿入する際に，関数 insert() が呼び出される回数が最小となる順序を1つ答えなさい．

(6) 設問 (3) で示した関数 insert() を用いて，空の二分木に関数 insert() が呼び出される回数が最小となる順序で NN 個の異なる値を挿入したとする． この二分木に，さらにもう 1 個の値を挿入したときに関数 insert() が呼び出される回数を NN を用いて答えなさい．

题目描述​

使用二叉树在 C 语言中实现一个存储 int 型数值集合的数据结构。图 1 给出了二叉树节点所用的结构体 node；该结构体由表 1 中的函数操作，函数实现见图 2。假设 malloc 始终成功，请回答以下问题。

struct node {
    int value;
    struct node *left;
    struct node *right;
};

图 1：结构体 node 的定义
​

表 1：操作结构体 node 的函数
​

函数说明
struct node *new_node(int value, struct node *left, struct node *right)新建一个节点，分别把数值 value、指向左子节点的指针 left 和指向右子节点的指针 right 设入该节点，并返回新节点的指针。
void traverse(struct node *n)对以指针 n 所指节点为根的二叉树作中序遍历，并把其中各节点的值输出到标准输出。输出顺序为：左子树中的值、根节点的值、右子树中的值。
#include <stdlib.h>
#include <stdio.h>

struct node *new_node(int value, struct node *left, struct node *right)
{
    struct node *n = malloc(sizeof(struct node));
    n->value = value;
    n->left = left;
    n->right = right;
    return (n);
}

void traverse(struct node *n)
{
    if (n == NULL) return;
    traverse(n->left);
    printf("%d\n", n->value);
    traverse(n->right);
}

图 2：表 1 所列函数的实现
​

  1. 执行下面的 main() 函数时，写出该函数在标准输出中输出的内容。
int main()
{
    struct node *top;
    top = new_node(5, new_node(9, NULL, NULL), new_node(7, NULL, NULL));
    traverse(top);
    return (0);
}
  1. 二叉树的深度优先遍历除了 traverse() 所实现的中序遍历以外，还有前序遍历与后序遍历。按照下表的规格，分别定义前序遍历函数和后序遍历函数。
函数说明
void pre_order_traverse(struct node *n)对以指针 n 所指节点为根的二叉树作前序遍历，并把节点值输出到标准输出。输出顺序为：根节点的值、左子树中的值、右子树中的值。
void post_order_traverse(struct node *n)对以指针 n 所指节点为根的二叉树作后序遍历，并把节点值输出到标准输出。输出顺序为：左子树中的值、右子树中的值、根节点的值。

  1. 下面给出了函数 insert()，它向二叉树中插入数值，使调用 traverse() 时各值按升序输出。假设传入的值不会与树中已有的值相同。填写空格 [(a)]～[(e)]，使函数正确工作。

    insert() 的规格如下：若指针 top 为 NULL，则新建节点、存入 value 并返回该节点的指针；否则，若 value 小于 top 所指节点中的值，就递归地把 value 插入左子树，若较大则递归地插入右子树，最后返回 top。

struct node *insert(struct node *top, int value)
{
    if (top == NULL)
        return (new_node(value, NULL, NULL));
    if (value < [空欄 (a)])
        [空欄 (b)] = insert([空欄 (c)]);
    else
        [空欄 (d)] = insert([空欄 (e)]);
    return (top);
}
  1. 下面的 main() 使用第 3 问完成的 insert()，依次向空二叉树插入 5、7、9。执行该函数时，insert() 总共被调用多少次？计数中也包括递归调用。
int main()
{
    struct node *top = NULL;
    top = insert(top, 5);
    top = insert(top, 7);
    top = insert(top, 9);
    traverse(top);
    return (0);
}

  1. 第 4 问按 5、7、9 的顺序插入三个值；改变插入顺序会改变 insert() 的调用次数。给出一种能使调用次数最少的插入顺序。

  2. 使用第 3 问的 insert()，按能使 insert() 调用次数最少的顺序向空二叉树插入 NN 个互不相同的值。随后再向所得二叉树插入一个值，用 NN 表示这次插入过程中 insert() 的调用次数。

Kai​

(1)​

9
5
7

(2)​

void pre_order_traverse(struct node *n) {
    if (n == NULL) return;
    printf("%d\n", n->value);
    pre_order_traverse(n->left);
    pre_order_traverse(n->right);
}

void post_order_traverse(struct node *n) {
    if (n == NULL) return;
    post_order_traverse(n->left);
    post_order_traverse(n->right);
    printf("%d\n", n->value);
}

(3)​

  • [空欄 (a)]: top->value
  • [空欄 (b)]: top->left
  • [空欄 (cc)]: top->left, value
  • [空欄 (d)]: top->right
  • [空欄 (e)]: top->right, value

(4)​

関数 insert() が呼び出される回数: 6 回．

(5)​

7，5，9

(6)​

O(log⁡N)O(\log N)

本页目录