数据结构与算法试卷第六套

1.带权路径长度之和

带权路径长度之和只需计算叶子节点的即可；
在这里插入图片描述
**哈夫曼树：**最小的两个节点构造成一个新的节点
带权路径之和计算叶子节点即可
请添加图片描述

2.快排复习

在这里插入图片描述

3.链表判空条件

在这里插入图片描述

4.树的遍历

前序： 根左右
后序： 左右根
B:
分析如下: 先序遍历顺序是:M-L-R,后序遍历顺序是:L-R-M,可以看到,只有中间的结点(M)顺序变化了,左右结点相对位置是不变的; 那可以推断出,要满足题意的话“二叉树的先序序列与后序序列正好相反”,说明整个二叉树左子树或者右子树有一个没有…”
在这里插入图片描述

5.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是

简单选择排序，能够取出当前无序序列中最（小or大）值与第一位置的元素互换位置。

堆排序每趟总能选出一个最值位于根节点。

冒泡排序总是两两比较选出一个最值位于数组前面。

快速排序选出的枢轴在一趟排序中就位于了它最终的位置

插入排序（直接、二分）不一定会位于最终的位置，因为不确定 后面插入的元素对于前面的元素是否产生影响。

希尔排序（本质也是插入排序）只在子序列中直接插入排序。所以不能确定。

**二路归并排序（本质就是归并排序）**除非在缓存区一次放入所有的序列（这样得不偿失），否则不能确定最终位置。
在这里插入图片描述

6.完全二叉树：

深度为k的完全二叉树最少的节点个数：深度为k-1的满二叉树的节点个数+1
深度为k的完全二叉树最多的节点个数：深度为k的满二叉树
在这里插入图片描述

7.邻接表的建立

在这里插入图片描述
n表示有n个顶点，e表示有e条边。
1.若采用邻接矩阵存储，
时间复杂度为O(n^2);
2.若采用邻接链表存储，建立邻接表或逆邻接表时，
若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);
若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);

8.节点个数问题：

在这里插入图片描述

首先需要明白两个知识点：
1、哈夫曼树中不存在度为1的节点，只有度为0和2的节点
2、 n0=n2+1
其次要会求解：
设叶子结点的个数为n0，度为2的节点个数为n2，
则求全部节点数为：n=n0+n2
已知n0=n2+1，代入上式得：n=n2+1+n2=2*n2+1=199（题中给的数据）
求得n2=99，由此可得叶子结点n0=100

9.调用一次深度优先遍历可以访问到图中的所有顶点（x）

对于连通图是成立的；但是非连通图，无论是DFS还是BFS都访问不了所有节点；

10.索引分块

索引分块查找就类似于图书馆的索引，我们先找到第几楼，再找第几个书架，然后再找书。
分块查找就是先找到目标所在的数据块，然后块内查找。因此跟表中元素个数和块中元素个数都有关。
分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（对）

11.树的遍历确定二叉树的唯一形状

有两颗二叉树
（1）B是A的左孩子先序 AB 后序 BA
（2）B是A 的右孩子先序 AB 后序 BA
在这里插入图片描述
那么，什么遍历能够确定一颗唯一的二叉树呢？

已知前序遍历和中序遍历，可以确定一棵二叉树，
已知中序遍历和后序遍历，可以确定一棵二叉树
已知前序遍历和后序遍历，无法确定一棵二叉树
中序遍历二叉排序树可以得到一个有序的序列

12.树和二叉树之间的转换

1.二叉树转为树：可以先将二叉树转为森林（根据左孩子，右兄弟的思想），再转换为树；
2.树转为二叉树：左孩子右兄弟，所以根节点一定没有右子树，只有兄弟节点；

在这里插入图片描述
将树转成二叉树：

将节点的孩子 放在左子树；
将节点的兄弟 放在右子树。
应该是转换完成后的二叉树的根节点没有右子树吧

13.顺序存储结构和链式存储结构的区别：

链式存储结构相比之下更好一点，链表不需要连续的存储单元，操作方便；

14.排序算法：

快速排序是基于比较的排序算法中平均性能最好的一种排序；

15.链表的插入：

在这里插入图片描述

s->next=p->next; p->next=s;

16.拓扑序列

去除入度为0的节点，将其出度也去掉
在这里插入图片描述

请添加图片描述

17.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是:

p->lchild==0&&p->rchild==0

大题

1.设计在顺序有序表中实现二分查找的算法：

int biSearch(struct record r[],int k){
  int low=0
  int high=n-1;//n为r数组的长度
  int mid;
  //2.遍历
  while(low<=high){
    mid=(low+high)/2;
    if(r[mid].key==k) return mid; //找到元素，返回元素下标
    else if(r[mid].key>k) high=mid-1;
    else low=mid+1;
  }
  return 0;
}

2.判断树是否是二叉排序树

bool flag=true;
void inorder(BiTree* bt) {
  // 1.BASE：
  if (bt == NULL) {
    return;
  }
  // 2.判断当前节点是否满足二叉排序树的性质
  if (bt->left != NULL && bt->left->data > bt->data) {
    flag = false;
    return;
  }
  // 3.判断当前节点是否满足二叉排序树的性质
  if (bt->right != NULL && bt->right->data < bt->data) {
    flag = false;
    return;
  }
  // 4.递归当前节点左子树
  inorder(bt->left);
  // 5.递归当前节点右子树
  inorder(bt->right);
}

3.直接插入排序的算法

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 直接插入排序函数
ListNode* insertionSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head; // 链表为空或只有一个节点，无需排序，直接返回
    }
    
    ListNode* dummy = new ListNode(0); // 创建哑节点作为辅助节点
    dummy->next = head;
    ListNode* prev = head; // prev指向已排序部分的最后一个节点
    
    while (prev->next != nullptr) {
        if (prev->val <= prev->next->val) {
            prev = prev->next; // 如果已排序部分的最后一个节点小于等于下一个节点，则继续向后遍历
        } else {
            ListNode* current = prev->next; // 记录下一个待排序节点
            prev->next = prev->next->next; // 将当前节点从原位置摘除
            ListNode* p = dummy; // 从头开始寻找插入位置
            while (p->next->val <= current->val) {
                p = p->next;
            }
            current->next = p->next; // 将当前节点插入到正确位置
            p->next = current;
        }
    }
    
    return dummy->next; // 返回排序后的链表头节点
}