2021数据结构 全真模拟试题2.docx

数据结构试题摘要 本资源提供了 2021 数据结构全真模拟试题 2.docx 的知识点摘要，涵盖数据结构的多个方面，包括图论、树、堆排序、快速排序、索引顺序表、链表、栈操作、矩阵存储等。 一、单项选择题 1. 一个具有 n 个顶点的无向完全图的边数为 n(n-1)/2。这是图论中一个基本概念，无向完全图是每个顶点与其他所有顶点相连的图。 2. 在索引顺序表中查找一个元素，用的且最快的方法是用二分查找法确定元素所在块，再用顺序查找法在相应块中查找。这是因为索引顺序表是一种结合了索引和顺序表的数据结构，索引可以快速定位元素所在的块，然后在块内使用顺序查找法。 3. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用单链表存储方式最节省运算时间。这是因为单链表在插入和删除操作时只需要更改指针，而不需要移动大量元素。 4. 串是有限个字符构成的序列。串是字符序列的统称，可以是字符串、 cadena 等。 5. 堆排序在最坏情况下，其时间复杂性为 O(nlog2n)。堆排序是一种常用的排序算法，时间复杂度为 O(nlog2n)。 6. 快速排序的记录移动次数大于比较次数，其总执行时间为 O(nlog2n)。快速排序是一种常用的排序算法，时间复杂度为 O(nlog2n)。 7. 一棵二叉树有 n 个结点，要按某顺序对该二叉树中的结点编号，应按层次遍历顺序编号。这是因为层次遍历可以保证结点的编号是从小到大。 8. 3 个结点可构成 5 个不同形态的二叉树。二叉树是一种基本的数据结构，3 个结点可以构成多种不同的二叉树形态。 9. 对有 n 个记录的有序表采用二分查找，其平均查找长度的量级为 O(log2n)。二分查找是一种常用的查找算法，时间复杂度为 O(log2n)。 10. 对有 n 个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查找长度的量级为 O(log2n)。二叉树是一种基本的数据结构，可以用来实现查找操作。 11. 栈操作的原则是后进先出。这是因为栈是一种 Last-In-First-Out 的数据结构，最后进栈的元素最先出栈。 12. 矩阵 A 是一对称矩阵，若每个矩阵元素占 3 个单元，将其上三角部分（包括对角线）按行序为主序存放在数组 B 中，那么矩阵元素 a67 的地址为 1093。这是因为对称矩阵的存储可以使用压缩存储，减少存储空间。 二、判断题 1. 如果两个串含有相同的字符，不一定相等。这是因为串是字符序列的统称，可以有不同的串具有相同的字符。 2. 数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。这是因为数组是一种基本的数据结构，可以进行插入、删除等操作。 3. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。这是因为索引顺序表是一种结合了索引和顺序表的数据结构，查找长度取决于索引和块中的元素个数。 4. 在顺序表中取出第 i 个元素所花费的时间与 i 无关。这是因为顺序表是一种基本的数据结构，取出第 i 个元素的时间是常数时间。 5. 在栈满情况下不能作进栈运算，否则产生“上溢”。这是因为栈是一种 Last-In-First-Out 的数据结构，不能在栈满情况下进行进栈运算。 6. 二路归并排序的核心操作是将两上有序序列归并为一个有序序列。这是因为二路归并排序是一种常用的排序算法，核心操作是将两个有序序列合并为一个有序序列。 7. 对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。这是因为图是一种基本的数据结构，可以使用深度优先或广度优先搜索来访问图的每个顶点。 8. 二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。这是因为二叉排序树是一种基本的数据结构，具有特定的性质。 9. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。这是因为排序算法的稳定性是指在排序过程中，相同的元素的相对顺序不变。 10. 一个有向图的邻接表和逆邻接表中表结点的个数一定相等。这是因为有向图是一种基本的数据结构，邻接表和逆邻接表的结点个数相同。 三、填空题 1. 在带有头结点的单链表 L 中，若要删除第一个结点，则需执行下列三条语句：L->next=L->next->next;free(L->next);L->next->prev=NULL;。 2. 有一个长度为 20 的有序表采用二分查找方法进行查找，共有 4 个元素的查找长度为 3。 3. 采用冒泡排序对有 n 个记录的表 A 按键值递增排序，若 L 的初始状态是按键值递增，则排序过程中记录的比较次数为 n(n-1)/2。若 A 的初始状态为递减排列，则记录的交换次数为 n(n-1)/4。 4. 在无头结点的双链表中，指针 P 所指结点是第一个结点的条件是 P->prev=NULL。 5. G 为无向图，如果从 G 的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。