数据结构------C语言经典题目（7）

1.系统栈和数据结构中的栈有什么区别？

        1.本质：

                系统栈：由程序运行时由操作系统自动分配的一块连续内存区域，用于存储函数调用过程中的临时数据（参数、局部变量、返回地址），是程序运行的底层机制，遵循先进后出原则。

                数据结构中的栈：是一种线性数据结构，定义了一组操作（压栈、弹栈、查看栈顶），也遵循 先进后出 原则。

        2.功能与用途：

                系统栈：

                   存储函数调用时的 局部变量，保存函数的返回地址。传递函数调用的 参数。支持递归调用。

示例：当函数A调用函数B时，系统会将A的当前状态（局部变量值、返回地址）压入栈，然后为B分配栈帧；B执行完毕后，栈会弹出A的状态，恢复执行A。

                数据结构中的栈：

                     表达式求值、括号匹配、回溯算法等。

        3.操作方式：

                系统栈：

                        操作是隐式的，函数调用、返回、局部变量创建/销毁等操作会自动触发栈的压入/弹出。

                数据结构中的栈：操作是显式的。需编写实现代码。

// 定义栈的最大容量
#define MAX_STACK_SIZE 100// 用数组实现栈（底层存储结构）
// stack数组存储栈元素，下标0为栈底，下标top为栈顶
int stack[MAX_STACK_SIZE];// top变量表示栈顶元素的索引：
// - 初始值-1表示栈为空（无有效元素）
// - 当压入元素时，top先自增再赋值
// - 当弹出元素时，先返回top位置元素，再自减
int top = -1;// 压栈操作：将元素value添加到栈顶
// 参数：value - 待压入栈的整数值
// 说明：若栈已满（top == MAX_STACK_SIZE - 1），则不执行压栈操作
void push(int value) 
{// 检查栈是否未满（栈最大索引为MAX_STACK_SIZE-1）if (top < MAX_STACK_SIZE - 1) {// 先将栈顶指针上移一位，再存储新元素（栈顶索引始终指向最后一个元素）stack[++top] = value;}
}// 弹栈操作：从栈顶取出并返回元素
// 返回值：栈顶元素（int类型），若栈空则返回-1（需根据业务调整错误处理）
// 说明：执行弹栈前需确保栈非空（调用前检查top >= 0）
int pop() 
{// 检查栈是否为空（栈空时top == -1）if (top >= 0) {// 先返回栈顶元素，再将栈顶指针下移一位return stack[top--];}// 栈空时返回-1（可根据实际需求定义错误码）return -1; 
}

2.如何实现二叉树的深度优先遍历算法和广度优先遍历算法？

数据结构：

        使用结构体TreeNode定义二叉树节点，包含数据域和左右子节点指针。

深度优先遍历：

        前序遍历：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

        中序遍历：左            根                右

        后续遍历：左            右                根

广度优先遍历：

        使用数组模拟队列实现层序遍历。

        根节点入队----》循环取出队首节点并访问----》将其左右子节点依次入队

        测试构建的二叉树结构：

    1/ \2   3/ \
4   5

示例代码：

// ====================== 数据结构定义 ======================
/*** 二叉树节点结构体定义* 包含：* - data: 节点存储的整数值* - left: 指向左子节点的指针（NULL表示无左子节点）* - right: 指向右子节点的指针（NULL表示无右子节点）*/
typedef struct TreeNode {int data;               // 节点数据域struct TreeNode *left;  // 左子节点指针struct TreeNode *right; // 右子节点指针
} TreeNode;// ====================== 节点操作函数 ======================
/*** 创建二叉树节点* @param data 节点存储的整数值* @return 新创建的节点指针（动态分配内存）*/
TreeNode* createNode(int data) 
{// 分配节点内存空间TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode == NULL)  // 内存分配失败处理（实际项目中需增强错误处理）{ exit(EXIT_FAILURE);}newNode->data = data;       // 初始化数据域newNode->left = NULL;       // 初始化左子节点指针为NULLnewNode->right = NULL;      // 初始化右子节点指针为NULLreturn newNode;             // 返回新节点指针
}// ====================== 内存释放函数 ======================
/*** 递归释放二叉树所有节点内存* 遵循后序遍历顺序：先释放左子树 → 释放右子树 → 释放当前节点* @param root 待释放的二叉树树根节点（NULL时直接返回）*/
void freeTree(TreeNode* root) 
{if (root == NULL) return; // 终止条件：空节点freeTree(root->left);  // 递归释放左子树freeTree(root->right); // 递归释放右子树free(root);            // 释放当前节点内存root = NULL;           // 防止野指针（虽然此处即将离开作用域）
}// ====================== 深度优先遍历（递归实现） ======================
/*** 前序遍历（根左右）* 访问顺序：根节点 → 左子树 → 右子树* @param root 当前遍历的子树树根节点（NULL表示空树）*/
void preOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 递归终止条件：遇到空节点{return;}printf("%d ", root->data); // 先访问根节点preOrderTraversal(root->left); // 递归遍历左子树preOrderTraversal(root->right); // 递归遍历右子树
}/*** 中序遍历（左根右）* 访问顺序：左子树 → 根节点 → 右子树* @param root 当前遍历的子树树根节点（NULL表示空树）*/
void inOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 递归终止条件{    return;}inOrderTraversal(root->left); // 先递归遍历左子树printf("%d ", root->data); // 再访问根节点inOrderTraversal(root->right); // 最后递归遍历右子树
}/*** 后序遍历（左右根）* 访问顺序：左子树 → 右子树 → 根节点* @param root 当前遍历的子树树根节点（NULL表示空树）*/
void postOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 递归终止条件{return;}postOrderTraversal(root->left); // 先递归遍历左子树postOrderTraversal(root->right); // 再递归遍历右子树printf("%d ", root->data); // 最后访问根节点
}// ====================== 广度优先遍历（队列实现） ======================
/*** 层序遍历（广度优先遍历）* 访问顺序：按层次从左到右依次访问节点（第1层→第2层→...）* @param root 二叉树的根节点（NULL表示空树）*/
void levelOrderTraversal(TreeNode* root) 
{if (root == NULL)         // 空树处理{return;}// 使用数组模拟队列（固定大小，适用于小规模树，大规模建议用链表实现）TreeNode* queue[100];       // 队列存储节点指针int front = 0;              // 队头指针（指向当前出队节点位置）int rear = 0;               // 队尾指针（指向当前入队位置的下一个位置）queue[rear++] = root;       // 根节点入队（初始队列包含根节点）while (front < rear)       // 队列不为空时循环{    TreeNode* current = queue[front++]; // 取出队首节点（先取值，再front自增）printf("%d ", current->data); // 访问当前节点// 左子节点非空则入队（保证层次顺序）if (current->left != NULL) {    queue[rear++] = current->left;}// 右子节点非空则入队（保证同层节点左到右顺序）if (current->right != NULL) {queue[rear++] = current->right;}}
}// ====================== 测试用例 ======================
int main() 
{TreeNode* root = createNode(1);          // 根节点（值1）root->left = createNode(2);              // 根节点左子节点（值2）root->right = createNode(3);             // 根节点右子节点（值3）root->left->left = createNode(4);        // 左子节点的左子节点（值4）root->left->right = createNode(5);       // 左子节点的右子节点（值5）printf("前序遍历（根左右）结果：");preOrderTraversal(root);                 // 输出：1 2 4 5 3printf("\n");printf("中序遍历（左根右）结果：");inOrderTraversal(root);                  // 输出：4 2 5 1 3printf("\n");printf("后序遍历（左右根）结果：");postOrderTraversal(root);                // 输出：4 5 2 3 1printf("\n");printf("层序遍历（广度优先）结果：");levelOrderTraversal(root);               // 输出：1 2 3 4 5printf("\n");printf("正在释放二叉树内存...\n");freeTree(root); // 调用释放函数，递归释放所有节点root = NULL;    // 清空根指针，确保不再访问已释放内存return 0;
}

3.满二叉树第K层有多少个节点？总共有多少个节点？

        满二叉树的每一层节点数都达到最大值。第K层的节点数为个。

        将满二叉树的高度设为H（即共有H层），则总节点数为个。

4.冒泡排序、插入排序、选择排序、快速排序如何实现？

冒泡排序：  

/*** 冒泡排序函数* @param arr 待排序的整数数组* @param n 数组元素个数* 算法思想：重复走访数组，比较相邻元素，将较大的元素逐步后移* 时间复杂度：O(n²)，稳定排序算法*/void bubble_sort(int arr[], int n) 
{int i = 0；    //外层循环计数器（控制排序轮数），int j = 0;     //内层循环计数器（控制每轮比较次数）//int temp = 0;  //临时变量用于交换元素// 外层循环：执行n-1轮排序（每轮确定一个最大元素到末尾）for (i = 0; i < n-1; i++) {// 内层循环：每轮比较相邻元素，将最大元素逐步后移// 每轮结束后，第n-i-1个位置是当前未排序部分的最大元素for (j = 0; j < n-i-1; j++) {// 如果当前元素大于下一个元素，则交换位置if (arr[j] > arr[j+1]) {temp = arr[j];        // 保存当前元素值arr[j] = arr[j+1];    // 下一个元素移到当前位置arr[j+1] = temp;      // 当前元素移到下一个位置}}}
}

插入排序：

/*** 插入排序函数* @param arr 待排序的整数数组* @param n 数组元素个数* 算法思想：将未排序元素插入到已排序部分的合适位置，使已排序部分始终有序* 时间复杂度：O(n²)，稳定排序算法*/
void insertion_sort(int arr[], int n) 
{int i = 0;                    //未排序部分起始索引   int key = 0;                  //待插入的当前元素int j = 0;                    //已排序部分反向遍历索引// 外层循环：从第二个元素开始（假设第一个元素已排序）for (i = 1; i < n; i++) {key = arr[i]; // 保存当前待插入的元素j = i - 1;    // 已排序部分的最后一个元素索引// 内层循环：将已排序部分中大于key的元素后移，为key腾出位置// 当j>=0且当前元素大于key时，继续后移while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j]; // 元素后移一位j--;               // 向前移动一位继续比较}arr[j+1] = key; // 将key插入到正确位置（j+1是因为循环结束时arr[j] <= key）}
}

选择排序：

/*** 选择排序函数* @param arr 待排序的整数数组* @param n 数组元素个数* 算法思想：每轮找到未排序部分的最小元素，与当前位置元素交换* 时间复杂度：O(n²)，不稳定排序算法*/
void selection_sort(int arr[], int n) 
{int i = 0;                      //已排序部分末尾索引  int j = 0;                      //未排序部分遍历索引int min_idx = 0;                //最小元素索引int temp = 0;                   //临时变量用于交换// 外层循环：控制已排序部分的末尾位置（从0到n-2）for (i = 0; i < n-1; i++) {min_idx = i; // 初始化最小元素索引为当前位置// 内层循环：在未排序部分（i+1到n-1）寻找最小元素索引for (j = i+1; j < n; j++) {if (arr[j] < arr[min_idx])  // 如果找到更小的元素，更新最小索引{   min_idx = j;}}// 交换最小元素与当前位置元素（将最小元素放到已排序部分末尾）temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}
}

快速排序：

/*** 快速排序辅助函数：分区操作* @param arr 待分区的整数数组* @param low 分区起始索引* @param high 分区结束索引* @return 分区点索引（基准元素的最终位置）* 算法思想：选择基准元素，将数组分为两部分，左边<=基准，右边>=基准*/
int partition(int arr[], int low, int high) 
{int pivot = arr[high];  // 选择最后一个元素作为基准值int i = (low - 1);     // 初始化最小元素索引为low-1（表示已处理部分的末尾）// 遍历low到high-1的元素，将小于等于基准的元素移到左边for (int j = low; j <= high - 1; j++) {// 如果当前元素小于等于基准值if (arr[j] <= pivot) {    i++;  // 最小元素索引递增（指向当前处理的左边区域的下一个位置）// 交换arr[i]和arr[j]，将较小元素移到左边int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确的位置（左边区域的末尾+1），完成分区int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;return (i + 1); // 返回基准元素的最终位置
}/*** 快速排序主函数* @param arr 待排序的整数数组* @param low 排序起始索引* @param high 排序结束索引* 算法思想：分治策略，通过分区将数组分为两部分，递归排序子数组* 平均时间复杂度：O(n log n)，最坏O(n²)，不稳定排序算法*/
void quick_sort(int arr[], int low, int high) 
{if (low < high)  // 终止条件：当子数组长度>=2时继续处理{// 获取分区点，将数组分为左右两部分int pi = partition(arr, low, high);// 递归排序左子数组（low到pi-1）和右子数组（pi到high）quick_sort(arr, low, pi - 1);quick_sort(arr, pi, high);}
}

主函数：

/*** 打印数组函数* @param arr 待打印的整数数组* @param size 数组元素个数*/
void print_array(int arr[], int size) 
{int i = 0;for (i = 0; i < size; i++) {printf("%d ", arr[i]); // 逐个打印数组元素}printf("\n"); // 换行
}int main() 
{int arr[] = {64, 34, 25, 12, 22, 11, 90}; // 测试用数组int n = sizeof(arr) / sizeof(arr[0]);    // 计算数组元素个数printf("原始数组: ");print_array(arr, n); // 打印排序前的数组// 选择要测试的排序算法（取消注释对应函数调用）// bubble_sort(arr, n);        // 冒泡排序// selection_sort(arr, n);     // 选择排序// insertion_sort(arr, n);     // 插入排序quick_sort(arr, 0, n-1);       // 快速排序（注意快速排序需要传入low=0和high=n-1）printf("排序后的数组: ");print_array(arr, n); // 打印排序后的数组return 0;
}

5.什么是时间复杂度，常见的时间复杂度有哪些？

        时间复杂度是衡量算法执行时间随输入数据规模增长而变化的趋势的指标。它关注的是算法执行时间的“增长率”，而不是具体的执行时间，用于评估算法的效率和优化。

常用的时间复杂度：

        O（1）常数时间：

                算法的执行时间与输入规模无关，始终是一个固定值。

                比如数组元素的直接访问、简单的算术运算。

        O（log n）对数时间：

                算法每执行一次操作，输入规模以固定倍数（通常是2）减少，常见于二分法相关操作。

        O（n）线性时间：

                算法的执行时间与输入规模成正比，需要遍历数据一次。

                数组求和、查找最大值/最小值。

        O（n  log  n）线性对数时间：

                常见于分治算法，归并排序、快速排序。

        O（）平方时间：

                算法需要两层嵌套循环，执行时间与输入规模的平方成正比。

                冒泡排序、选择排序、双重循环遍历。

6.冒泡排序、选择排序、插入排序、快速排序的时间复杂度分别是什么？是否稳定？

冒泡排序：

        最好情况：当数组已有序时，只需遍历一次，时间复杂度为O（n）。

        最坏情况：当数组逆序时，需要进行 n  -  1轮比较，每轮比较n  -  i次，时间复杂度为O（）

        稳定的。

选择排序：

        无论数组是否有序，均需进行n - 1轮选择和交换。时间复杂度为O（）

        不稳定。例如，数组 [5,5,3]排序时，第一个5可能与后面的3交换，导致两个5的相对顺序发生改变。

插入排序：

        最好情况：数组已有序时，每轮插入只需比较一次，时间复杂度为O（n）。

        最坏情况：数组逆序时，每次插入需移动 i 个元素，时间复杂度为O（）。

        稳定。      

快速排序：

        通过分治策略，每次分区平衡，时间复杂度为O（n log n）。

        不稳定。

7.二分查找的前提条件是什么？时间复杂度？

前提条件：

        1.数据有序：

                待查找的数组必须是有序的（升序或降序）。二分查找通过不断比较中间元素与目标值，将搜索范围减半，因此无序数据无法使用该算法。

        2.顺序存储：

                数据需存储在顺序存储结构（如数组）中。支持随机访问（通过下标直接访问中间元素）。链表等链式存储结构由于无法快速定位中间元素，不适合直接使用二分查找。

时间复杂度为O（log  n）：

        每次查找将搜索范围缩小一半，最多需要 次比较操作（n为数组元素个数）。

二分查找法的核心优势是高效，但严格依赖数据的有序性和顺序存储特性。使用前需确保数组已排序，否则需先排序（通过快速排序等算法）再进行查找。