有一个线性表(a ,a ,…,a ),其中 n≥2,采用带头结点的单链表存储,头指针[br][/br]1[br][/br]2[br][/br]N[br][/br]为 L,每个结点存放线性表中一个元素,结点类型为(data,next),现查找某个元素值等[br][/br]于 x 的结点指针,若不存在这样的结点返回 NULL。分别写出下面 3 种情况的查找语句。[br][/br]要求时间尽量少。[br][/br](1线性表中元素无序。[br][/br](2线性表中元素按递增有序。[br][/br](3线性表中元素按递减有序。
举一反三
- 判断正误[br][/br]( )1、链表的每个结点中都恰好包含一个指针。 [br][/br]( F )2、链表的物理存储结构具有同链表表达的逻辑结构有一样的顺序。 [br][/br]( F )3、线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。[br][/br]( F )4、顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 [br][/br]( F )5、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。[br][/br]( F )6、线性表在物理存储空间中也一定是连续的。[br][/br]( F )7、线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序也相邻。[br][/br]( F )8、线性表的逻辑顺序与存储顺序总是一致的。
- 有线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。（1）线性表中元素无序。（2）线性表中元素按递增有序。（3）线性表中元素按递减有序。【北京邮电大学1994 七（7分）】
- 对于顺序存储的线性表,访问第i个结点和在第i个结点前插入结点的时间复杂度分别为()。 A: O(1)<br/>O(n) B: O(n)<br/>O(1) C: O(n)<br/>O(n) D: O(1)<br/>O(1)
- 每个存储结点只含一个数据元素,所有存储结点连续存放。此外增设一个索引表,[br][/br]索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的[br][/br]存储结构称为__1__。
- 顺序表的删除算法： 假设顺序表的长度为 n， （１）若在位序 1 处删除元素，则需要移动 （） 个元素；[br][/br] （２）若在位序 n 处删除元素，则需要移动 （） 个元素；[br][/br] （３）若在位序 i (1≤i≤n) 处删除元素，则需要移动 （） 个元素；[br][/br] （４）假设各位序删除元素的概率相同，则平均需要移动 （） 个元素。[br][/br] [br][/br] 注：请填写正确的C表达式。