数据结构试题解析与复习指南

"这是一份专升本数据结构的试题，包含了选择题，涉及数据结构的基础概念，如时间复杂度分析、线性表、链式存储、栈、队列、字符串操作以及二叉树的相关知识。" 1. 时间复杂度分析是算法效率评估的重要工具。题目中提到的函数f(n), g(n), h(n)代表了不同时间复杂度的函数，选项A、B、C正确表示了它们之间的关系，而D选项中h(n)=O(nlgn)不正确，因为h(n)的时间复杂度高于nlogn。 2. 线性表是一种基本的数据结构，由有限个元素组成，可以为空。因此，正确答案是A，线性表是一个有限序列，可以为空。 3. 链式存储的线性表中，元素的存储地址不必连续，故选择D，连续与否均可。 4. 对于顺序存储的线性表，插入操作通常需要移动后续元素，如果等概率插入，大约需要移动n/2个元素，所以选择A。 5. 删除单链表中节点A后的节点，需要修改A节点的next指针指向下一个节点的下一个节点，即p->next=(p->next)->next。 6. 栈遵循后进先出（LIFO）原则，所以B是正确答案。 7. 栈和队列都属于限制存取点的线性结构，C选项正确。 8. 栈的出栈顺序是后进先出，如果输出序列的第一个元素是n，那么第i个输出元素是n-i+1，选C。 9. 字符串s1和s2的concat和sub运算后，s1的第二个字符到s2的长度位置，以及s1的s2长度到倒数第二个字符被连接起来，得到的结果是'BCPQRST'，所以选C。 10. 串的联结运算是将两个字符串连接成一个新的字符串，不满足交换律和结合律，但满足分配律，即(a+b)+c=a+(b+c)，所以选A。 11. 求q在p中首次出现的位置的运算属于模式匹配。 12. 二维数组A的终端结点a45的地址可以通过计算得出，起始于a00的地址加上(行数+1)*(列数)*元素大小，所以是1000+(5+1)*4*6=1126，选择A。 13. 在树的术语中，节点的度是指其子节点的数量。如果节点A有3个兄弟，加上A本身，B作为A的双亲，就有4个孩子，所以B的度是4。 14. 中序遍历是二叉树的一种遍历方式，对于二叉树的中序遍历，通常是左子树-根节点-右子树的顺序。 这份试题覆盖了数据结构的关键概念，包括基本操作、时间复杂度分析、线性表、链表、栈、队列、字符串处理以及二叉树的基本性质。对于准备专升本考试的学生，掌握这些知识点至关重要。