《 数 据 结 构 》 期 中 测 试 班 级 ： 姓 名 ： 学 号 ： 一 、 填空题： 1、 在数 据 结 构 中 ，从逻辑上可以把数 据 结 构 分为集合、线性结 构 、树形结 构 和图状结 构 ，其中 树形结 构 和图状结 构 合称为非线性结 构
数 据 结 构 被形式地定义为二元组（D，S），其中 D是数 据 元素的有限集合，S是 D上关系的有限集合
2、 算法的五个重要特性是有穷性、确定性、可行性、输入和输出
3、 一 个顺序表第一 个元素的存储地址是 100，每个元素的长度为 3，则第 6个元素的地址是 115
在顺序表中 插入或删除一 个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数 与插入或删除元素的位置有关
顺序表中 逻辑上相邻的元素的物理位置相邻
单链表中 逻辑上相邻的元素的物理位置不一 定相邻
单链表中 ，除了首元结 点外，任一 结 点的存储位置由其前驱结 点的指针域指示
在单链表中 设置头结 点的作用是使第一 个结 点与其他结 点的操作统一
4、 从一 个具有 n个结 点的单链表中 查找其值等于 x的结 点时，在查找成功的情况下，需平均比较（n+1）/2个结 点
在一 个具有 n个结 点的有序单链表中 插入一 个新结 点并仍然有序的时间复杂度是 O（n）
给定有 n个元素的线性表，建立一 个有序单链表的时间复杂度是 O（n2）
5、 已知 L是无表头结 点的非空单链表，且指针 p所指结 点既不是首元结 点，也不是尾元结点，试 从下列提供的答案中 选择合适的语句序列
在 p所指结 点后插入 s所指结 点： 4、1
在 p所指结 点前插入 s所指结 点： 7、11、8、4、1
在表首插入 s所指结 点： 5、12
在 表 尾 插 入 s所 指 结 点 ： 11、9、1、6
1) p->next=s; 2) p->ne
