计算机学科专业基础2014 真题档案

答案：C

答案：B

答案：A

答案：D

答案：C

答案：D

答案：D

答案：D

答案：D

答案：B

答案：C

【答案】

（1）算法基本设计思想
方法一：基于先序递归遍历。定义递归函数，将当前结点的深度作为参数传递。若结点为叶子结点，则累加 深度 * 权值 到结果；否则，递归遍历其左右子树，并将深度参数加1。
方法二：基于层次遍历（BFS）。使用队列实现层次遍历，并记录当前层数 deep。利用指针 lastNode 标记当前层最后一个结点。当遍历到叶子结点时，累加 deep * 权值。每当处理完 lastNode 结点，就更新 lastNode 为下一层的最后一个结点，并将 deep 加1。

（2）二叉树结点的数据类型定义（C语言）

typedef struct BiTNode {
    int weight;                     // 存储权值
    struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;

（3）算法描述（C语言）
方法一：先序递归

int wpl_PreOrder(BiTree root, int deep);
int wpl_LevelOrder(BiTree root);

int WPL(BiTree root) {
    return wpl_PreOrder(root, 0); // 基于先序遍历
    // 如需使用层次遍历，可改为：return wpl_LevelOrder(root);
}

int wpl_PreOrder(BiTree root, int deep) {
    if (root == NULL) return 0; // 空树返回0
    if (root->lchild == NULL && root->rchild == NULL)
        return deep * root->weight;
    return wpl_PreOrder(root->lchild, deep + 1)
         + wpl_PreOrder(root->rchild, deep + 1);
}

方法二：层次遍历

int wpl_LevelOrder(BiTree root) {
    BiTree q[MaxSize]; // 声明队列，end1为头指针，end2为尾指针
    int end1, end2 = 0;
    end1 = end2 = 0;
    int wpl = 0, deep = 0;
    BiTree lastNode;
    BiTree newlastNode;
    lastNode = root;
    newlastNode = NULL;
    q[end2++] = root;
    while (end1 != end2) {
        BiTree t = q[end1++];
        if (t->lchild == NULL && t->rchild == NULL) {
            wpl += deep * t->weight;
        }
        if (t->lchild != NULL) {
            q[end2++] = t->lchild;
            newlastNode = t->lchild;
        }
        if (t->rchild != NULL) {
            q[end2++] = t->rchild;
            newlastNode = t->rchild;
        }
        if (t == lastNode) {
            lastNode = newlastNode;
            deep += 1;
        }
    }
    return wpl; // 返回wpl
}

（1）本题中的网络可抽象为数据结构中的图（具体为无向图）。

（2）采用带表头结点的链式存储。每个表头结点保存路由器 ID，并指向该路由器的链路/网络信息链；弧结点用 Flag 区分 Link 和 Net 两种记录。数据类型可定义为：

typedef struct {
    unsigned int ID, IP;
} LinkNode;                 // Link的结构

typedef struct {
    unsigned int Prefix, Mask;
} NetNode;                  // Net的结构

typedef struct Node {
    int Flag;               // Flag=1为Link，Flag=2为Net
    union {
        LinkNode Lnode;
        NetNode Nnode;
    } LinkORNet;
    unsigned int Metric;
    struct Node *next;
} ArcNode;                  // 弧结点

typedef struct HNode {
    unsigned int RouterID;
    ArcNode *LN_link;
    struct HNode *next;
} HNODE;                    // 表头结点

例如，R1 的表头结点保存 Router ID 10.1.1.1，其信息链依次记录到 R2 的 Link、到 R3 的 Link 以及直连网络 192.1.1.0/24 的 Net；其他路由器按同样方式组织。这样既能表示题表中的全部 LSI，也与题图中的无向图相对应。

（3）从R1到各目的网络的最短路径及代价如下表所示：