数据结构线性表练习及答案
- 格式:doc
- 大小:18.50 KB
- 文档页数:2
一、选择题
1、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是()
A、当前结点所在的地址域
B、指针域
C、空指针域
D、空闲域
2、不带头结点的单链表head为空的判断条件是()
A、head==NULL
B、head->next==NULL
C、head->data==NULL
D、head!=NULL
3、在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在p和q之间插入s结点,则执行()
A、s->next=p; q->next=s;
B、p->next=s->next; s->next=p;
C、q->next=s->next; s->next=p;
D、p->next=s; s->next=q;
4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
5、一个单链表中,若删除p所指结点的后续结点,则执行()
A、p->next=p->next->next;
B、p=p->next; p->next=p->next->next;
C、p->next=p;
D、p=p->next->next;
6、已知一个顺序存储的基本线性表,设每个结点需占m个存储单元,若第一个结点的地址为d1,则第i个结点的地址为()
A、d1+(i-1)*m
B、d1+i*m
C、d1-i*m
D、d1+(i+1)*m
7、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()
A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)
B、在第i个结点后插入一个新结点(1<=i<=n)
C、删除第i个结点(1<=i<=n)
D、将n个结点从小到大排序
8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中,能正确完成要求的算法段是()
A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;
B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;
D、以上都不对
9、在循环双链表的p所指结点之后插入s所指结点的操作是()
A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D、s->prior=p; p->next->prior=s; s->next=p->next; p->next=s;
10、从具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较()个结点。
A、n
B、n/2
C、(n-1)/2
D、(n+1)/2
11、单链表的存储空间利用率()
A、大于1
B、等于1
C、小于1
D、不能确定
12、在顺序表中,有7个元素,设第1个元素的查找概率是1/4,第2个元素的查找概率是1/3,其余元素的查找概率相等,则整个顺序表的平均查找次数是()次。
A、44/12
B、451/60
C、36/12
D、56/24
13、顺序表的长度是()。
A、表中的存储空间数
B、表中的数据元素个数
C、存储空间数减去数据元素个数
D、存储空间数加数据元素个数
14、在单链表中插入结点的时间复杂度是()
A、O(1)
B、O(n)
C、O(n2)
D、O(log2n)
二、填空题
1、基本线性表有(顺序)和(链式)两种存储形式。
2、在双链表中,每个结点有两个指针域,一个指向(前驱结点),另一个指向(后继结点)。
3、按顺序存储方法存储的基本线性表称为(顺序表),按链表存储的基本线性表称为(链表)。
4、顺序表相对于链表的优点有(随机存取)和(存储空间利用率高)。
5、链表相对于顺序表的优点有(存储空间动态分配)和(插入删除操作效率高)。
6、在n个结点的顺序表中插入一个结点需平均移动(N/2)个结点,具体的移动次数取决于(插入的位置)。
7、在n个结点的顺序表中删除一个结点需平均移动((N-1)/2)个结点,具体的移动次数取决于(删除的位置)。
8、在顺序表中访问任意一个结点的时间复杂度均为(1),因此,顺序表也称(随机存取或直接存取)的数据结构。
9、在单链表中设置头结点的作用是(保护头指针)。
10、顺序表中逻辑上相邻的元素,物理位置(一定)相邻。
11、当对一个基本线性表进行插入和删除操作较频繁时,线性表应采用(链式)存储结构;当对线性表的操作不会引起它的变化时,线性应采用(顺序)存储结构。
12、基本线性表的链式存储中,根据链表指针的链接方向可分为(单向链表)、(双向链表)和(循环链表)。
13、在个结点的单链表中要删除已知结点*p,则需找到(P的前驱结点),其时间复杂度为(O(N))。
14、在双向链表中要删除已知结点*p,其时间复杂度为(O(1))。
15、在循环链表中,可根据任一结点的地址遍历整个链表,而单链表中需知道(头指针)才能遍历整个链表。