《数据结构域算法设计-第二部分 线性表 答案教案》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第二部分 线性表 答案教案（12页珍藏版）》请在金锄头文库上搜索。
1、第二部分第二部分 线性表线性表一、选择题1关于顺序存储的叙述中,哪一条是不正确的 ( B )A. 存储密度大B. 逻辑上相邻的结点物理上不必邻接C. 可以通过计算直接确定第 i 个结点的位置D. 插入、删除操作不方便2长度为 n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 ( C )A O(n) B O(1) C O(m) D O(m+n)3在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是：( A )A 访问第 i 个结点（1link=p;p-link=s;（B）s-link=p-link;p-link=s;（C）s-link=p-link;p=s;（D）p-lin
2、k=s;s-link=p;16. 在循环链表中 first 为指向链表表头的指针，current 为链表当前指针，在循环链表中检测 current 是否达到链表表尾的语句是( D )。（A）current-link=NULL (B)first-link=current（C）first=current (D)current-link=first17. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较( D )个结点。A. nB. n/2C.（n-1）/2D. (n+1)/218. 在一个具有 n 个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为(
3、 B )。A. O(1)B. O(n)C. O(n2)D. O(nlog2n)19. 用链表表示线性表的优点是 ( C )。A. 便于随机存取 B. 花费的存储空间比顺序表少C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同20. 当需要随机查找线性表的元素时,宜采用( C )作存储结构。A. 双向链表 B. 循环链表 C. 顺序表 D. 单链表21. 线性表的链接实现有利于（ A ）运算。A、插入 b、读表元 c、查找 d、定位22. 线性表采用链式存储时，其地址（ D ） 。A 必须是连续的 B 部分地址是连续的C 一定是不连续的 D 连续与否均可以23. 设单链表中指针 p 指
4、着结点 a，若要删除 a 之后的结点（若存在） ，则需要修改指针的操作为（ A ） 。A、p-next=p-next-next b、p=p-nextC、 p= p-next-next d、p-next=p24. 向一个有 127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ B ）个元素。A、8 B、63.5 C、63 D、725. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动（ C ）个元素（A） 8 （B） 63.5 （C） 63 （D） 7 26. 用链表表示线性表的优点是（ A ）A 便于插入和删除操作B 数据元素的物理顺序与逻辑顺序相同C 花费的存储空
5、间较顺序存储少D 便于随即存取27. 以下数据结构中不属于线性数据结构的是（ C ）A 队列B 线性表C 二叉树D 栈28对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ B ） 。AN+1BNC(N+1)/2DN/229下列叙述中正确的是( A )。A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构30在单链表中，增加头结点的目的是( A )。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现31线性表的顺序存储结构和线性表的链式存储结构分别是（ B ） 。A.
6、 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存取的存储结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构33线性表中正确的说法是( D )。A. 每个元素都有一个直接前驱和一个直接后继B. 线性表至少要求一个元素C. 表中的元素必须按由小到大或由大到小排序D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继34线性表是具有 n 个（ C ）的有限序列。A. 表元素B. 字符C. 数据元素D. 数据项35若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（
7、C ） 。 （1in+1）A. O(0)B. O(1)C. O(n)D. O(n2)36在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（B） 。A. O(1)B. O(n)C. O(nlogn)D. O(n2)37某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（ A ）存储方式最节省运算时间。A. 仅有尾指针的单向循环链表B. 仅有头指针的单向循环链表C. 单向链表D. 双向链表二、填空题1在单项链表中删除一个指定结点的后继的时间复杂度为 O(1) 2线性表中 _数据元素的个数_ 称为表的长度。3. 在
8、n 个结点的单链表中，在 P 指向的结点之后插入一个结点的时间复杂度为 _O（n） 。4设长度为 n 的线性表顺序存贮,若在它的第 i-1 和第 i 个元素之间插入一个元素, 共需移动 _n-i+1_ 个元素(1link;p-link=_ p-link -link _ _Delete q9将适当的语句添入单链表搜索函数 find 中。templateListNode*List:find(Type value)current=first-link；while(current!=NULL)if(current-data=value) breakelse current=current-link;r
9、eturn _ current _ _10顺序存储方法是把逻辑上相邻的结点存储在物理位置 _也相邻_ 的存储单元中。11顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表便于_随机_访问，是一种_随机访问存储结构_。12在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程_不相同_。13已知 L 是无头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点，添加合适的语句。1) P 结点之后插入结点 S：S-next=P-next; P-next=S;2) P 结点之前插入结点 S：pre=L;while(pre-next!=P) pre=p
10、re-next;S-next=P; pre-next=S;3) 在表首插入结点 S：S-next=L; L=S;4) 在表尾插入结点 S：while(P-next) P=P-next;P-next=S; S-next=NULL;14已知 P 结点是某双向链表的中间结点，添加合适的语句。1) P 结点之后插入结点 S：S-next=P-next; S-prior=P;P-next-Prior=S; P-next=S;2) P 结点之前插入结点 S：S-next=P; S-prior=P-prior;P-prior-next=S; P-prior=S;3) 删除 P 结点的直接后继结点：Q=P-n
11、ext; P-next=Q-next; Q-next-prior=P; free(Q);4) 删除 P 结点的直接前驱结点：Q=P-prior; P-prior=Q-prior; Q-prior-next=P; free(Q);5) 删除 P 结点：P-prior-next=P-next; P-next-prior=P-prior; free(P);15在链表的结点中，数据元素所占存储量和整个结点所占的存储量之比称作 存储密度 。三、判断题1线性链表中各个链结点之间的地址不一定要连续。( R )2若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。( W )3若线性表采用顺序存
12、储结构，每个数据元素占用 4 个存储单元，第 12 个数据元素的存储地址为 144，则第 1 个数据元素的存储地址是 101。( W )4若长度为 n 的线性表采用顺序存储结构，删除表的第 i 个元素之前需要移动表中n-i+1 个元素。( W )5在顺序表中取出第 i 个元素所花费的时间与 i 成正比。 （ W ）四、算法题1设 n 个元素的线性表顺序存储在一维数组 st1.maxlen的前 n 个位置上,试将新元素e 插入表中第 i-1 个和第 i 个元素之间,写出算法。typedef struct ElemType st1.maxlen; /存放线性表的数组int n; /n 是线性表的长
13、度 SeqList;SeqList SeqLiseInit() /构造一个线性链表 LSeqList L; /定义为顺序表L.lengh=0; /顺序表的长度为 0return Lvoid SeqListInsert(Seqlist L,int i,ElemTypex) /在顺序表中的第 i 个位置插入元素 xif(L.length= maxlen) printf(“the list is full“); exit(0); /表满,退出if(iL.length)printf(“position error“);exit(0); /插入位置错,退出 for(j=L.length-1;j=i-1;
14、j-)L.dataj+1=L.dataj; /第 i 个位置后的数组元素逐一后移L.datai-1=x; /新元素插入到第 i 个位置L.length+; /顺序表长度增 13. 执行下面的 C 程序,指出输出结果。#include#includestruct node char data；struct node *next；void link_list(struct node *p) while(p!=NULL) printf(“%c“,p-data)； p=p-next；printf(“n“)； main( ) char ch； struct node *q,*p,*f,*head=NUL
15、L；for (ch=A；chdata=ch； p-next=head； head=p； link_list(p)； p=head； head=NULL； while(p!=NULL) q=p； p=p-next； q-next=head； head=q； f=head；while(f-next!=NULL)link_list(head)； f=f-next-next； ABACBADCBAEDCBAFEDCBAFFEFEDFEDFEDCFEDCFEDCBFEDCBFEDCBFEDCBAFEDCBAFEDCBA4下列算法完成的功能？1）ListNode *Demo1(LinkList L, ListNode *p)/*L 是带有头结点的单链表*/ListNode *q = L
