数据结构自测题1-5.doc

数据结构 自测题 （前五章） 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。 2. 数据结构被形式地定义为（D, S），其中D是 的有限集合，S是D上 的有限集合。 3. 数据结构按逻辑结构可分为两大类，它们分别是 和 。 4. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 5．在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。 6. 一个算法的效率可分为 效率和 效率。 7. 线性表中结点的个数是 的，结点间的关系是 的。 8. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 个元素。 9. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 个元素。 10. 在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。 11. 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。 12. 在单链表中，除了首元结点外，任一结点的存储位置由 指示。 13． 在n个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 。 14. 线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。 15. 在具有n个单元的循环队列中，队满时共有 个元素。 16. 称为空串； 称为空白串。 17. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为 。 18. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 。 二、判断正误 （ ）1. 链表的每个结点中都恰好包含一个指针。 （ ）2. 链表的物理存储结构具有同链表一样的顺序。 （ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 （ ）4. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）6. 线性表在物理存储空间中也一定是连续的。 （ ）7. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ ）8. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 三、单项选择题 （ ）1. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ ）2. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （ ）3. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ ）4. 计算机算法指的是： A) 计算方法