2021数据结构全真试题2：详解与关键知识点

本资源是一份2021年的数据结构全真试题，包含选择题和非选择题两部分。选择题部分共15题，涉及数据结构的基础概念和操作。以下是部分题目解析： 1. 问题1询问了关于存储结构的定义，其中提到结点的存储地址与其关键字之间的映射关系，这指的是数据结构中的**散列存储结构**（Hashing），它利用哈希函数将关键字映射到存储地址，实现快速查找。 2. 第2题考查顺序表操作，插入操作的时间复杂度与插入位置有关，对于长度为n的顺序表，在第i个位置插入元素，元素需要移动的次数是**n-i+1**，以保持连续存储。 3. 对于频繁进行首尾插入的线性表，由于顺序表不适合频繁插入，而循环链表可以高效地在表尾插入，因此选择**用尾指针表示的单循环链表**更为合适。 4. 第4题涉及栈的应用，如果仅允许入栈和出栈操作，从a，b，c进栈能得到的不同排列数量是**6**，因为每次出栈一个元素，可以得到一种排列，但出完后剩下两个元素还有两种排列方式。 5. 为了查找特定单词在文本中的位置，需要用到**子串定位**（Substring Search），即在文本中搜索特定模式或子串。 6. 在函数调用中，`Sub(S,1,7)`表示从字符串S的第1个字符开始取长度为7的子串，`Scopy`用于复制，所以`P`最终会包含`S`的前7个字符，即`P="SCIENCE"`。 7. 三维数组按行优先存储，意味着数组的行索引变化最快，计算元素`A[3][4][5]`的地址需要先确定行（3）、列（4）和深度（5）的地址，加上每个元素占2个存储单元，从初始地址120开始计算，地址为120+2*(4*5+5*6)=362。 8. 广义表的类型判断，根据题目描述，广义表可能是**递归表**，因为它通常用来表示具有嵌套结构的数据集合，如树或图。 9. 选项分析：A错误，二叉树的度并不限定为2；B正确，二叉树中某个节点只有一个孩子时，该节点无左右之分；C错误，二叉树中不一定有度为2的节点；D正确，二叉树最多有两个子树，且有左右之分。 10. 有向完全图的边数计算，对于n个顶点，每个顶点都有一条指向其他n-1个顶点的有向边，但每条边都被计算了两次（源节点指向目标节点和目标节点指向源节点），所以最多有`n*(n-1)/2`条有向边，答案是C。 11. 最后一道题目给出了一个有向图的DFS序列可能性问题，从顶点a出发，不可能得到的DFS序列是`adbe`，因为d在a之前，不符合DFS的访问顺序。 以上知识点涵盖了数据结构中的存储结构、顺序表操作、链表、栈和队列、子串处理、二维数组存储、广义表、二叉树、图论以及深度优先搜索等基础知识。这份试题是对考生数据结构理论知识和实际操作能力的全面考察。