《1顺序存储的线性表..doc》由会员分享，可在线阅读，更多相关《1顺序存储的线性表..doc（4页珍藏版）》请在三一文库上搜索。
1、第二章 线性表一、填空题1顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作的时间代价基本上都是等效的 .则插入一个元素大约要移动表中的 个元素 ,删除一个元素时大约要移动表中的个元素 .2. 数组的长度是 ,线性表的长度是 .3. 当向一个顺序表插入一个元素时, 从插入位置开始向后的所有元素均需 一个位置移动过程是由 向 依次移动每一个元素 .4. 要从一个顺序表删除一个元素时, 被删除元素之后的所有元素均需 一个位置 ,移动过程是由 向依次移动每一个元素 .5. 向顺序表中第 i 个元素之前插入一个新元素时 , 首先从 开始向后的所有元素均需一个位置 ,接着把新元素写入 上,最后使
2、线性表的长度 ,从顺序表 中删除第i个元素时,首先把第i个元素赋给 ,接着从开始向后，所有元素均一个位置 ,最后使线性表的长度 .6. 在线性表的顺序存储中,元素之间的逻辑关系是通过 决定的 ; 在线性表的链接存储中 ,元素之间的逻辑关系是通过 决定的 .7. 对于一个具有n 个结点的单链表 ,在已知的结点 *p 后插入一个新结点的时间复杂度为,在给定值为 x 的结点后插入一个新结点的时间复杂度为 .8. 在双链表中 , 每个结点含有两个指针域 ,一个指向 结点,另一个指向 结点 .9. 在一个单链表中删除 *p 结点时 ,应执行下列操作 :q=p->next;p->data=p-
3、>next->data;p->next=;free(q);10. 若要在一个不带表头结点的单链表的首结点 *p 结点之前插入一个 *s 结点时 , 可执行下列 操作 :s->next=p->next=s;t=p->data;p->data=;s->data=;11. 根据线性表的链式存储结构中每个结点所含指针的个数,链表可分为 和;而根据指针的联接方式 ,链表又可分为 和. ,若分配太少又容易在算法中造成 ,因而只适用于数据量变化不大的情况;对 于线性表的链接存储 ,不需要 存储空间 ,存储器的整个空间都可供使用, 分配和回收结点都非常方便 ,能
4、够有效地利用存储空间 ,在算法中不必考虑 的发生 , 因此适用于数据量变化较大的情况 .13. 当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时 , 则采用 存储结构为宜 ,相反 ,当经常进行的是插入和删除操作时 ,则采用 存储结构为宜 .14. 在单链表中设置头结点的作用是 .15. 顺序表中逻辑上相邻的元素物理位置 紧邻 ,单链表中逻辑上相邻的元素物理位置紧邻.二、选择题个元素 .1在一个长度为n的顺序表中删除第i个元素(0 < i帥)需向前移动(A)n-i(B)n-i+1(C)n-i-1(D)i2从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，
5、需平均比较个元素结点 (A)n/23.对一个具有(B) n(C)(n+1)/2n个元素的线性表，建立其单链表的时间复杂度为2(C)O(n 2 )(D) (n-1)/2(A)O(n)4在双向循环链表中,在p所指的结点之后插入 s指针所指的结点,其操作是(B)O(1)(D)O(log 2 n)(A) p->next=s;s->prior=p;(p->next)->prior=s;s->next=p->next;(B) s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;(
6、C)p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;(D)s->prior=p;s->next=p->next;p->next->prior=s;5设单链表中指针p指向结点p->next=s;:m,若要删除m之后的结点(若存在),则需修改指针的操作为(A) p->next=p->next->next;(B) p=p->next;(C) p= p->next->next;6线性表采用链式存储结构时(A) 必须是连续的(C) 部分地
7、址必须是连续的(D)p->next= p;，其地址 (B) 一定是不连续的(D) 连续与否均可以7在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为 .2 (A)O(log 2n)(B)O(1) (C)O(n2 ) (D)O(n)8. 在一个单链表中,已知*q结点是*p结点的前趋结点,若在* q和* p之间插入* s结点，则须执行 .(A) s->next = p- >next; p->next = s(B) q->next=s; s->next=p(C) p->next =s ->next; s-> next
8、 = p(D) p-> next = s ; s->next = q9. 线性表是 .(A) 一个有限序列 ,可以为空(B) 一个有限序列 ,不可以为空(C) 一个无限序列，可以为空(D) 个无限序列，不可以为空10. 在一个长度为n的顺序表中向第i个元素 (0< i w n+之前插入一个新元素时，需向后移动 个元素 .(A)n-i(B)n-i+1(C)n-i-1(D) i三、简答题1. 在单链表和双向链表中， 能否从当前结点出发访问任一结点2. 线性表的两种存储结构各有些优缺点 ?四、算法设计1. 设顺序表va中的数据元素递增有序.试写一算法，将x插入到顺序表的适当位置上，以保 持该表的有序性 .LENGTH（L，X）2. 写出在带头结点的动态单链表结构上实现线性表的查找操作LOCATE(L，X)3. 写出在带头结点的动态单链表结构上求线性表的长度的算法