《 数 据 结 构 》 期 中 测 试 班 级 ： 姓 名 ： 学 号 ： 一 、 填空题： 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->next=p->next->next; 3) p->next=s->next; 4) s->next=p->next; 5) s->next=L; 6) s->next=NULL; 7) q=p; 8) while(p->next!=q) p=p->next; 9) while(p->next!=NULL) p=p->next; 10) p=q; 11) p=L; 12) L=s; 13) L=p; 6、 已知指 针 p所 指 结 点 是某双向链表 的中间结 点 ，试从下列提供的答案中选择合适的语句序列。 在 p所 指 结 点 后插 入 s所 指 结 点 的语句序列是 7、12、6、3。 在 p所 指 结 点 前插 入 s所 指 结 点 的语句序列是 8、13、...
