深信服校园招聘c/c 软件开发B卷

时长:120分钟 总分:100分

799浏览 6人已完成答题

题型介绍
题型 填空题
数量 3
1.
位对齐
问题详情
编写函数align_n，将size的低n位（即：0到n-1位）清零，如果清零前size的低n位不为全零，则在第n位上加1。n满足32>n>0。
align_n的函数原型：
unsigned int align_n(unsigned int size, int n)
输入描述： size（十六进制）,n（十进制）输入样例： 0x7,3 输出描述： align_n的运算结果（十六进制）输出样例 0x8
2.
堆排序
问题详情
函数heap_sort使用堆排序方法对数组arr进行排序，排序后数据为降序。相关代码如下，请补充缺失部分。

void heap_arrange(int arr[], int cur, int cnt)  //调整为小顶堆
{
    int heaptop_val = arr[cur] //堆顶的值
    while (cur < cnt) {
        int left = 2 * cur + 1
        int right = 2 * cur + 2
        int min = -1
        int min_val = ______ 
        if (left < cnt && arr[left] < min_val) { //检查是否比左节点大
            min = left
            min_val = arr[left]
        }
        if (right < cnt && arr[right] < min_val) {//检查是否比右节点大
            min = right
        }
        if (min == ______) 
            break
        arr[cur] = ______ 
        cur = ______ 
    }
    arr[cur] = ______
}
void heap_sort(int arr[], int cnt)
{
    int i
    for (i = cnt / 2 - 1 i >= 0 --i) {
        heap_arrange(arr, i, cnt)
    }
    for (i = cnt - 1 i > 0 --i) {
        int tmp
        tmp = arr[0]
        arr[0] = arr[i]
        arr[i] = tmp
        heap_arrange(arr, 0, i)
    }
}

输入描述： 第一行为数据个数 第二行为输入数据输入样例： 10 100 32 3 6 24 86 23 90 78 3 输出描述： 排序过程的中间数据，及已经排好序的数据输出样例 origin: 100 32 3 6 24 86 23 90 78 3 make heap: 3 6 3 78 24 86 23 90 100 32 sort i=9 32 6 3 78 24 86 23 90 100 3 3 6 23 78 24 86 32 90 100 3 sort i=8 100 6 23 78 24 86 32 90 3 3 6 24 23 78 100 86 32 90 3 3 sort i=7 90 24 23 78 100 86 32 6 3 3 23 24 32 78 100 86 90 6 3 3 sort i=6 90 24 32 78 100 86 23 6 3 3 24 78 32 90 100 86 23 6 3 3 sort i=5 86 78 32 90 100 24 23 6 3 3 32 78 86 90 100 24 23 6 3 3 sort i=4 100 78 86 90 32 24 23 6 3 3 78 90 86 100 32 24 23 6 3 3 sort i=3 100 90 86 78 32 24 23 6 3 3 86 90 100 78 32 24 23 6 3 3 sort i=2 100 90 86 78 32 24 23 6 3 3 90 100 86 78 32 24 23 6 3 3 sort i=1 100 90 86 78 32 24 23 6 3 3 100 90 86 78 32 24 23 6 3 3 sorted: 100 90 86 78 32 24 23 6 3 3
3.
最优二叉树
问题详情
有一个节点数组，需要创建一棵最优二叉树，即每个节点的权值乘以节点在树中的长度，然后相加得到的值最小。以下图一为例，节点数组的[A,B,C,D,E]的权值分别为[15,7,6,6,5]，构建好的最优二叉树见图二。


相关框架代码已经给出，请补充缺失部分，保证程序正常运行，输出预期结果。

```
struct node {
    int left, right, parent
    int val
}
int build_tree(struct node arr[], int cnt)
{
    while (1) {
        int i
        int min1 = -1              //权值最小的节点编号
        int min2 = -1              //权值第二小的节点编号
        int root_node = 0          //根节点(没有父节点)的个数

        for (i = 0 i < cnt ++i) {
            if (arr[i].____________ >= 0)
                continue
            ++root_node
            if (min1 < 0) {
                min1 = i
            } else if (arr[i].val < ____________) { 
                min2 = min1
                min1 = i
            } else if (min2 < 0) {
                min2 = i
            } else if (arr[i].val < ____________) { 
                min2 = i
            }
        }
        if (root_node < ____________)
            break
        arr[cnt].left = min2
        arr[cnt].right = min1
        arr[cnt].val = arr[min1].val + ____________ 
        arr[cnt].parent = -1
        arr[min1].parent = cnt
        arr[min2].parent = cnt
        ++cnt
    }
    return cnt
}

```

输入描述： 第一行为数据个数 第二行为权值（整数）输入样例： 5 15 7 6 6 5 输出描述： 构建的二叉树（用于绘图软件生成对应的二叉树图形）输出样例 ```mermaid graph TD n0[n0:15] n0 --> n8 n1[n1:7] n1 --> n6 n2[n2:6] n2 --> n5 n3[n3:6] n3 --> n6 n4[n4:5] n4 --> n5 n5((11)) n5 --> n7 n6((13)) n6 --> n7 n7((24)) n7 --> n8 n8((39)) ```