数据结构复习题集：算法、查找与链表特性

在《数据结构》课程的复习题中，我们遇到了一系列关于数据结构与算法的基础概念。首先，针对顺序查找算法，当在一个无序表中有N个数据且查找概率均匀时，平均查找长度ASL（Average Search Length）并不直接等于N或N-1，而是介于两者之间，具体计算公式是(N+1)/2，因此正确答案是C。 在图论部分，连通图的生成树是指将图中的所有结点连接成一棵树，这样得到的树将包含N-1条边，因为生成树恰好缺少一条边以形成环路。所以选择项是B，即N-1个结点，N-1条边。 算法设计的目标通常包括可读性（使代码易于理解）、可执行性（确保程序能够运行）、健壮性（处理异常和错误的能力），而高空间效率通常不是主要目标，因为它可能会牺牲执行效率。所以不属于算法设计目标的是D，高空间效率。 数据结构的研究内容主要包括数据之间的逻辑关系（如何组织和表示数据）、数据的存储方式（如何在内存中安排数据），以及数据的运算（对数据的操作）。数据的大小虽然会影响数据结构的选择，但并不是其研究的核心内容，因此答案是B。 单链表作为一种线性数据结构，其优点在于插入和删除操作只需要改变相邻节点的指针，无需移动大量元素，这使得它在动态数据结构中表现优越。选项C正确。然而，单链表不支持随机存取，元素的存储地址也不是连续的。 在链表操作中，如果要删除p指针后的节点，需要更新p指针指向下一个节点，即p.next=p.next.next。选项B正确。循环队列的队满条件是在满的情况下， rear 指针指向下一个可以存放元素的位置，即 (rear+1) % maxsize == front。 对于二叉树的问题，一个重要的性质是对于非空二叉树，如果有15个叶结点且没有度为1的结点，说明这棵树是一个满二叉树，除了最底层外，每一层都是满的。由于最底层有15个结点，而除根结点外，每层比上一层多一个结点，所以总结点数可以通过倒推得出，即27个结点。答案是C。 中序遍历和后序遍历可以帮助我们重构二叉树，给定的中序遍历为 bdaec，后序遍历为 dbeca，我们可以反推出前序遍历是 adbec，因为前序遍历的顺序是根-左-右。答案是B。 最后，二分查找适用于有序数据结构，如有序表，因为它依赖于中间元素来缩小搜索范围。因此，答案是C，有序表。 填空题涉及了线性数据结构中的堆栈，其特点是插入和删除都在表的一端进行。在给定字符串"Iamastudent"中，找到第5个's'的索引为5。一维数组的地址计算方法是首地址加上元素下标乘以元素大小，所以a[6]的地址为1000+6*4=1024。深度为5的二叉树最多有2^5-1=31个节点。有向完全图中，K个结点的边数是K*(K-1)，即K^2-K。三个节点的树形态可以有多种，具体形状取决于连接方式。按逻辑结构分类，数据可分为线性和非线性，常见的非线性结构如树和图。 这部分复习题涵盖了数据结构基础、查找算法、图论、链表操作、队列、二叉树和排序等核心概念。