资源描述：
《线性表 08-12年1月试题及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章线性表08-12年1月试题及参考答案（2008年1月）2、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）A、访问第i个元素的前驱（1<）B、在第i个元素之后插入一个新元素()C、删除第i个元素()D、对顺序表中元素进行排序3、假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）A、head==NULLB、head–>next==NULLC、head!=NULLD、head–>next==head17、输入线性表的n个元素建立带头结点的单链表，其时间复杂度为_________
2、__。30、假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:(1)设线性表为(a1,a2,a3,a4,a5,a6,a7),写出执行算法f30后的线性表；(2)简述算法f30的功能。voidf30(LinkListL){//L为带头结点单链表的头指针LinkListp,q;p=L;while(p&&p–>next){q=p–>next;p–>next=q–>next;p=q–>next;free(q);}}(1)(2)34、假设以单链表表示线性表,单链表的类型定义如下:typedefstructnode{Dat
3、aTypedata;structnode*next;}LinkNode,*LinkList;编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。（2008年10月）3、在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（）A、p->next==headB、p->next->next==headC、p->next==NULLD、p==head17、将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的
4、最好的时间复杂度是。30、已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。voidf30(SeqList*L){inti,j;for(i=j=0;ilength;i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i];j++；}L->length=j;}(1)(2)（2009年1月）2、假设某个带头结点的单链表的头指针为hea
5、d，则判定该表为空表的条件是()A、head==NULL；B、head->next==NULL；C、head!=NULL；D、head->next==head；17、在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。30、假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;阅读下列算法，并回答问题：(1)已知初始链表如图所示，画出
6、执行f30(head)之后的链表；题30图(2)简述算法f30的功能。voidf30(LinkListhead){LinkListp,r,s;if(head->next){r=head->next;p=r->next;r->next=NULL;while(p){s=p;p=p->next;if(s->data%2==0){s->next=head->next;head->next=s;}else{s->next=r->next;r->next=s;r=s;}}}}(1)(2)34、假设以带头结点的单链表表示线性表，单链表的类型
7、定义如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：voidf34(LinkListhead);（2009年10月）3、指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（ ）A、p->next=r；q->next=r->next；r->next=q；B、p->next=r；r->next
8、=q；q->next=r->next；C、r->next=q；q->next=r->next；p->next=r；D、r->next=q；p->next=r；q->next=r->next；17、如果需要对线性表频繁进行________或________操作，则不宜采用顺序存
