北理工 数据结构与算法设计试题

### 关于数据结构与算法设计的考试题目

#### 堆的性质
对于一组初始记录关键字序列 (k1, k2, …, kn)，如果该序列为堆，则对 i=1, 2, ..., n/2 而言应满足如下条件：ki ≤ k2i 并且 ki ≤ k2i+1 或者 ki ≥ k2i 并且 ki ≥ k2i+1，这取决于最小堆还是最大堆[^2]。

#### 数据结构定义
在北京理工大学的数据结构课程中，二叉树节点被定义为：

typedef struct node {
    int data;
    struct node *lchild, *rchild;
} bitree;

此定义用于表示具有整数数据成员以及指向左子节点和右子节点指针的二叉树节点[^1]。

为了帮助理解并掌握这些概念，以下是几个典型的数据结构与算法设计练习题：

---

#### 练习题一：构建完全二叉树
给定一个数组 `arr` 表示一棵完全二叉树的层次遍历顺序，请编写函数创建对应的二叉树，并返回根节点。

def create_complete_binary_tree(arr):
    if not arr:
        return None
    
    nodes = [None if val is None else TreeNode(val) for val in arr]
    
    kids = nodes[::-1]
    root = kids.pop()
    for node in nodes:
        if node:
            if kids: node.left  = kids.pop()
            if kids: node.right = kids.pop()
            
    return root

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

#### 练习题二：验证最小堆属性
给出一个列表形式存储的关键字序列，判断其是否构成一个小顶堆。

def is_min_heap(heap_array):
    length = len(heap_array)

    for i in range(length // 2):
        # Check children of node at index i.
        left_child_index = 2*i + 1
        right_child_index = 2*i + 2
        
        if heap_array[i] > heap_array[left_child_index]:
            return False
            
        if right_child_index < length and heap_array[i] > heap_array[right_child_index]:
            return False
                
    return True