数据结构考试重点整理

"这是一份关于数据结构的考试题，包含了填空题，涵盖了数据结构的基本概念、操作和算法分析。" 在数据结构领域，填空题中的知识点包括： 1. 栈的性质：栈是一种后进先出（LIFO）的数据结构，如果输入序列为1,2,3，…n，输出序列为p1,p2,p3,...pn，且p1=n，则pi表示的是第i个进入栈的元素，最后出栈。 2. 单循环链表：在单循环链表中，如果指针p所指结点为最后一个结点，意味着p->next等于头结点。 3. 完全二叉树：具有32个结点的完全二叉树的深度为5，因为2^4 < 32 < 2^5。 4. 链表操作：L是带有头结点的单链表的头指针，第一个元素结点的指针可以通过L->next获取。 5. 数据结构分类：数据结构主要分为线性结构和非线性结构两大类。 6. 二分查找：在有序表中，元素为1到9，采用二分查找方法查找元素，查找长度为2的情况可能发生在查找5、6、7这三个元素时。 7. 图的遍历：在无向图中，从某个顶点出发进行一次广度优先搜索能访问所有顶点，表明图是连通图。 8. 归并排序：归并排序的时间复杂性为O(nlogn)，是一种稳定的排序算法。 9. 顺序表操作：在长度为n的顺序表中删除第m个元素，需要将m到n的所有元素都向前移动一位。 10. 多维数组：多维数组通常由一维数组实现，通过索引映射到多维空间。 11. 链式存储：链式存储利用指针表示数据元素之间的逻辑关系，是数据结构的一种物理实现。 12. 后缀表达式计算：后缀表达式“4 5* 3 2 + -”的值为5，这是基于逆波兰表示法的计算。 13. 算法复杂性：算法复杂性分为时间复杂性和空间复杂性，分别衡量运行时间和内存使用。 14. 无向图的邻接矩阵：邻接矩阵是对称的，A[i,j] = 1则A[j,i] = 1，表示两个顶点间有边连接。 15. 栈的定义：栈是一种限定在表的一端（顶部）进行插入和删除的线性表，又称后进先出（LIFO）表。 16. 广度优先搜索：在图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>,<2,3>}中，从顶点1出发进行广度优先搜索，可能的序列有4种，包括所有可能的访问顺序。 17. 树的性质：在一棵树中，叶子结点没有后继结点，即没有子节点。 18. 存储结构与逻辑结构：存储结构是逻辑结构的物理实现，反映了数据在计算机内存中的实际存储方式。 19. 链表操作：在单链表中，指针p所指结点为最后一个结点的条件是p->next为NULL。 20. 栈的操作原则：栈的插入和删除操作遵循后进先出（LIFO）原则。 21. 双向链表插入：在双向链表中，要在结点A后插入结点X，需要修改三个指针，即s->next=p->next; p->next=s; s->right=p->right; p->right->left=s。 22. 无向图的邻接矩阵：无向图的邻接矩阵是对称的，A[i,j]=1则A[j,i]=1。 23. 栈的性质：栈是限定在表尾（即末尾）进行插入或删除操作的线性表，遵循先进后出（FILO）原则。 24. 度为3的树：在树的度数问题中，已知度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，根据树的性质，可以计算得出叶子结点的数量，通常是度为1和2的结点数量之和减去1。在这个例子中，叶子结点的数量为(2+3)-1=4。 25. 链表插入：在单链表中，如果指针变量p指向结点A，s指向要插入的结点X，插入操作的语句为s->next=p->next; p->next=s。 26. 有序表查找：在有序表(13，35，...）中，采用二分查找的方法，根据题目内容，此处省略了部分数据，需要找到具体查找长度为2的情况。 这些填空题覆盖了数据结构的基础知识，包括栈、链表、树、图、排序算法、查找算法以及存储结构等多个核心概念。