DS一、二、三章测试
一、选择题（每题2分，共20分）
1、 若某线性表中最常用的操作是取第i个数据元素，则应采用( )存储方式最节
约时间。
A 单链表 B 双链表 C 单循环链表 D 顺序表
2、 在一个长度为n的顺序表的表尾插入一个元素，其渐进时间复杂度为( )。
A O(n) B O(1) C O(n2 ) D O(log2n)
3、 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n C.(front-rear+1)％n
B.(rear-front)％n D.(rear-front+n)％n
4、 已知一个栈的入栈序列是1,2,3,…, n，其输出序列是p1,p2,…,pn。若p1=n，则pi(1≤i≤n)为（ ）。
A. i B. n-i C. n-i+1 D. 不确定
5、下列程序段的时间复杂度为( ) s=0；
for(i=1；i for(j=1；j s+=i*j； B.O(n) C.O(2n) D.O(n2) A.O(1) 6、假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( ) A.head==NULL； B.head->next==NULL； C.head!=NULL； D.head->next==head； 7、线性表是具有n个（ ）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 8. 判定一个大小为m的栈S为满的条件是（ ）。 A. S.top- S.Base=0 B. S.top==0 C. S.top=m D. S.top-S.Base>=m 9、判定一个循环队列Q （最多元素为MAXSIZE）为满的条件是 。 A. Q.front= = Q.rear B. Q.front!=Q.rear C. Q.front= =(Q.rear+1)%MAXSIZE D. Q.front!=(Q.rear+1)%MAXSIZE 10、带头结点的单链表（头指针为h）为空的判定条件是（ ）。 A. A. h=NULL B. h->next=NULL C. h->next=h D. H!=NULL 二、填空题（每题4分，共40分） 1、表长为n的顺序存储的线性表，假设搜索表中任何一个数据元素的概率相等，则搜索任何一个元素所需进行的平均比较次数为 。 2、 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是： 。 3、 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为 。 4、若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现 个不同的出栈序列。 5、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是： 。 6、表长为n的顺序存储的线性表，假设搜索表中任何一个数据元素的概率相等，则搜索任何一个元素所需进行的平均比较次数为 。 7、 在一个单链表中删除p所指结点时，可以将p的后继结点的数据域放入p所指结点的数据域，然后将p的后继结点删除，那么，应执行以下操作： q=p->next； p->data= ； p->next= ； 8、将图1中s所指结点加到p所指结点之后，其语句应是 。 s e p Ai-1 图1 Ai 9、若有程序段 i=0；s=0; while(s 三、程序设计（每题20分，共40分） 1、写一个算法，将一个不带头结点的单链表（由L指向）逆置。 提示：为方便起见，采用逆序创建新链表的方法放置逆置的结点，且新链表带头结点（由S指向）。 说明：该单链表的存储类型定义为 typedef int ElemType; typedef struct { ElemType data; LNode *next; } LNode, *LinkList; 函数模块的框架为： void invertLinkList(LinkList L) { 请在此写入自己的算法 解答： 2、假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 编写算法，删除线性表中最大元素(假设最大值唯一存在)。 DS 1、2、3章测试答案 一、 DBDCD BCDCB 二、 1、(n+1)/2 2、s->next=p->next; p->next=s 3、10 4、5 5、s->next=p->next; p->next=s; 6、(n+1)/2 7、p->next->data 或 q->data； q->next 或 p->next->next 8、s->next=p-next； p->next=s 9、O(n) 10、O(log2n) 三、 1、 S=(LNode *)malloc(sizeof(LNode)); S->next=NULL; p=L; while(p) { Q=s->next; s->next=p; p=p->next; s->next->next=q; } } 2、 void del_max_link (LinkList & head) { pre=head; //pre是 p 的前驱 p=head->netx; max_value=p->data; q=p; while (q->next ) { if (q->next->data >max_value ) { pre=q; p=q->next; max_value=p->data; } q=q->next; }// end of while; pre->next=p->next; delete p; }