数据结构练习题.doc

第一章l 判断题（一）1. 数据元素是数据最小单位。错2. 数据对象就是一组数据元素的集合。错3. 任何数据结构都具备三个基本运算：插入、删除和查找。错4. 数据对象是由有限个类型相同的数据元素构成的。对5. 数据的逻辑结构与各数据元素在计算机中如何存储有关。错6. 如果数据元素值发生改变，则数据的逻辑结构也随之改变。错7. 逻辑结构相同的数据，可以采用多种不同的存储方法。对8. 逻辑结构不相同的数据，必须采用不同的存储方法来储存。错9. 数据的逻辑结构是指数据元素的各数据项之间的逻辑关系。错l 判断题（二）1. 顺序存储方式只能用于存储线性结构。错2. 数据元素是数据最小的单位。错3. 数据结构是带有结构的数据元素的集合。对4. 数据的逻辑结构是指各数据元素之间的逻辑关系。对5. 数据结构、数据元素、数据项在计算机中的表示分别称为存储结构、节点和数据域。对6. 数据的物理结构是指数据在计算机内的实际的存储形式。对第二章l 判断题一1. 分配给单链表的内存单元地址必须是连续的。错2. 与顺序表相比，在链表中顺序访问所有节点，其算法的效率比较低。错3. 从长度为n的顺序表中删除任何一个元素，时间复杂度都是O（n）。错4. 向顺序表中插入一个元素，平均要移动大约一半的元素。对5. 凡是为空的单链表都是不含任何节点的。错6. 如果单链表带有头结点，则插入操作永远不会改变头节点指针的值。对7. 在循环单链表中，任何一个节点的指针域都不可能为空。对l 判断题二1. 顺序存储方式的特点是存储密度大且插入、删除运算效率高。错2. 线性表的顺序存储结构优于链式存储结构。错3. 顺序存储结构属于静态结构而链式存储结构属于动态结构。对4. 由于顺序存储结构要求连续的存储区域，所以再存储管理上不够灵活。对5. 对于单链表来说，只有从头节点开始才能扫描表中全部节点。对6. 对于循环单链表来说，从表中任一节点出发都能扫描整个链表。对7. 双链表的特点是很容易找任一节点的前驱和后继。对第三章1. 栈底元素是不能删除的元素。错2. 顺序栈中元素值的大小是有序的。错3. 在n个元素连续进栈后，他们的出栈顺序和进栈顺序一定正好相反。对4. 栈顶元素和栈底元素有可能是同一元素。对5. 若sm表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次。错6. 栈是一种对进栈、出栈操作总次数作了限制的线性表。错7. 对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。对8. 空栈没有栈顶指针。错9. 环形队列中有多少元素，可以根据队首指针和队尾指针的值来计算。对10. 无论是顺序队列，还是链式队列，插入、删除运算的时间复杂度都是O(1)。对11. 队列若用不带头节点的非循环单链表来表示链式队列，则可以用“队首指针和队尾指针的值相等”作为空队标志。错12. 栈和队列都是插入和删除操作受限的线性表。对13. 栈和队列的存储方式既可以是顺序方式，也可以是链式方式。对14. 环形队列也存在空间溢出的问题。对15. 消除递归不一定需要使用栈。对，也可用迭代第四、五、六章l 判断题1. KMP算法的最大特点是指示主串的指针不需回溯。对2. 任何递归算法都有递归出口。对3. 递归算法的执行效率比功能相同的非递归算法的执行效率高。错4. 递归算法不能转换成对应的非递归算法。错5. 稀疏矩阵的特点是矩阵中的元素较少。错l 简答题1. 两个串相等的充分必要条件是什么？长度相同且对应位置字符相等2. 二维数组A0303的元素起始地址是LOC(A 00)=1000，一个元素占用内存单元为2，则LOC（A32）为多少。（分别计算按行、列存储情况）按行存储：1000+(3-0)4+(2-0)2=1028按列存储：1000+(2-0)4+(3-0)2=1022上机操作题1. 顺序表：已知线性表（a1,a2,an）按顺序结构存储且每个元素为不相等的整数。设计把所有奇数移到所有偶数前边的算法。（要求时间少，辅助空间少）。2. 单链表：编写算法将带头节点的单链表中值重复的节点删除，使所得的链表中各节点值不同。3. 栈和队列：编程实现用两个栈模拟一个队列的算法。4. 递归：编写程序，用递归算法实现n个整数之和。5. 稀疏矩阵：稀疏矩阵压缩存储只存放行号、列号和非零值，用三元组顺序表表示。请编写程序实现两个稀疏矩阵相加的算法。