数据结构练习（线性表）
一、选择题
1．线性表是一个
A. 有限序列，可以为空 B. 有限序列，不能为空
C. 无限序列，可以为空 D. 无限序列，不能为空
2．设线性表L=(a1,a2,……an)，下列关于线性表的叙述正确的是 。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少有一个元素
C. 表中元素排列顺序必须按由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都有且只有一个直接前驱和一个
直接后继
3．下面关于线性表的叙述中，错误的是
A. 线性表采用顺序存储，必须占用一片连续的存储单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链接存储，不必占用一片连续的存储单元
D. 线性表采用链接存储，便于进行插入和删除操作
4．某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素的存储地址为
A. 144 B. 145 C. 147 D. 148
5．若长度为n的顺序存储结构线性表，删除第i个数据元素，需要向前移动 <u>A</u> 个数据元素。
A. n-i B. n+i C. n-i-1 D. n-i+1
6．若长度为n的顺序存储结构线性表， 在第i个位置插入一个元素， 需要依次向后移动 <u>D</u> 个元素。
A. n-i B. n+i C. n-i-1D. n-i+1
- 在下列存储结构中，最适合实现在线性表中进行随机访问的是 <u>A</u> 。
A. 数组 B. 双向链表 C. 单向链表 D. 循环链表
- 与单链表相比，双链表的优点之一是 <u>D</u> 。
A．可以由最后一个结点找到头结点 B．可随机访问
C．插入、删除操作更加简单 D．访问前驱结点更加方便
9．如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 <u>D</u> 。
A．顺序表 B．单链表 C．双向链表 D．具有表尾指针的循环单链表
10．在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==head，则 <u>D</u> 。
A. p指向头结点 B. p指向尾结点
C.p的直接后继是头结点 D.p的直接后继是尾结点
11．带表头附加结点的单链表head为空的判断条件是 <u>B</u> 。
A. head==NULL B. head->next==NULL
C. head->next==head D. head!=NULL
- 对线性表，在下列情况下应当采用链表表示的是 <u>B</u> 。
A. 经常需要随机地存取元素
B. 经常需要进行插入和删除操作
C. 表中元素需要占据一片连续的存储空间
D. 表中的元素个数不变
13．如果最常用的操作是取第i个结点及前驱，则采用 <u>A</u> 存储方式最节省时间。
A．顺序表 B．双链表 C．单循环链表 D．单链表
14．可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是 <u>B</u> 。
A．可以加快对表的遍历 B. 使空表和非空表的处理统一
C．节省存储空间 D. 可以提高存取表元素的速度
15．一个顺序表所占存储空间的大小与 <u>D</u> 无关。
A．顺序表长度 B．结点类型
C．结点中个数据域的类型 D．结点的存放次序
16．从一个具n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 <u>D</u> 个结点。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
17．单链表中，q在前,p在后的指向相邻的两个结点，要在q,p之间插入s所指的结点应是D_。
A．s->next=p->next; p->next=s; B．p->next=s->next; s->next=p;
C．p->next=s; s->next=q; D．q->next=s; s->next=p;
18．在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是 <u>B</u> 。
A．p=p->next B．p->next=p->next->next
C．p->next=p D．p=p->next->next
19．一个循环单链表中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行 <u>D</u> 。
A．q—＞next＝p；p—＞next＝q—＞next；
B．p—＞next＝q—＞next；q＝p；
C．q—＞next＝p—＞next；p—＞next＝q；
D．p—＞next＝q—＞next；q—＞next＝p;
20．在循环双链表的指针p所指结点之前插入指针q所指结点的操作是 <u>D</u> 。
A．p->left=q; q->right=p; p->left->right=q; q->left=p->left;
B．p->left=q; p->left->right=q; q->right=p; q->left=p->left;
C．q->right=p; q->left=p->left; p->left=q; p->left->right=q;
D．q->right=p; q->left =p->left; p->left->right=q; p->left=q;
二、算法设计题
1．设有一个顺序表L，其元素为整型数据，编写一个要求时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。提示：从L的两端查找，前端找大于0的数据，后端找小于0的数据，然后将两位置的数据交换。
void Exchange_num(SqList &L){
for(int i=0,j=L.length-1;i<j;){
while(i<j&&L.data[i]<0){
i++;
while(i<j&&L.data[j]>0)
j--;
if(i<j){
int temp=L.data[i];
L.data[i]=L.data[j];
L.data[j]=temp;
}
}
}
网友评论