2022年数据结构线性表习题 .pdf
第二章作业题1求单链表中当前结点的后继和前驱的时间复杂度分别是（）AO（n）和 O（1）BO（1）和 O（1）CO（1）和 O（n）DO(n)和 O（n）2非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）Arear-next= =head Brear-next-next= =head Chead-next= =rear Dhead-next-next= =rear 3在带头结点的循环链表L 中，结点的数据元素为整型，且按值递增有序存放。给定两个整数 a 和 b，且 anext=s-next ；s-next=p；B.s-next=p；q-next=s-next ；C.p-next=s-next ；s-next=q ；D.s-next=q ；p-next=s-next ；6若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）A无头结点的双向链表B带尾指针的循环链表C无头结点的单链表D带头指针的循环链表7.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A.访问第 i 个元素的前驱（1next!=head) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - p=head-next; A-length=0; while(p-next!=head) p=p-next; A-dataA-length +=p-data; if(p-next!=head)p=p-next; (1) (2) 13已知链串的存储结构描述如下：#define NodeSize 4 typedef struct Node char data NodeSize; struct Node * next; * LinkStr; 阅读下列算法，并回答问题：（1）t1 和 t2 的串值分别为Chinese和 China时，写出f31(t1,t2) 的返回值；（2）t1 和 t2 的串值分别为Japan和 Japanese 时，写出f31(t1,t2) 的返回值；（3）t1 和 t2 的串值都为string时，写出f31(t1,t2) 的返回值；（4）简述函数f31 的功能。inf f31(LinkStr t1,LinkStr t2) / 串值以 0为结束符int i; while (1) for (i=0;idatai= =0&t2-datai= =0return 0; if(t1-datai= = 0)return 1; if(t2-datai= = 0)return 1; if(t1-datait2-dataireturn 1; if(t1-dataidataireturn 1; t1=t1-next; t2=t2-next; (1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - (2) (3) (4) 14已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题：（1）写出执行f30（a,b）的返回值，其中a 和 b 分别为指向存储集合2 ，4，5，7，9，12和2 ，4，5，7，9的链表的头指针；（2）简述算法f30 的功能；（3）写出算法f30 的时间复杂度。int f30(LinkList ha,LinkList hb) /LinkList是带有头结点的单链表/ha 和 hb 分别为指向存储两个有序整数集合的链表的头指针LinkList pa,pb; pa=ha-next; pb=hb-next; while(pa & pb & pa-data=pb-data) pa=pa-next; pb=pb-next; if(pa=NULL & pb=NULL) return 1; else return 0; (1) (2) (3) 15假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct node DataType data; struct node *next LinkNode, *LinkList; 编写算法，从有序表A 中删除所有和有序表B 中元素相同的结点。16.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULL B.headnext= =NULL C.head!=NULL D.headnext= =head 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -
