目录
选择
编程
选择
1.
在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入结点s,则执行()
A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;
C. q->next=s; s->next=p; D.p->next=s; s->next=q;
答案:C
解析:s插入后,q成为s的前驱,p成为s的后继。是不是有小伙伴认为C中的语句会造成短链,应该交换位置呢,其实C的语句顺序并不会造成短链。这是因为本题插入位置的前后节点都有指针指示。
2.
给定有n个元素的一维数组,建立一个有序单链表的最低时间复杂度是()
A. O(1) B. O(n) C. O(n^2) D. O(nlogn)
答案:D
解析:若先建立链表,然后依次插入建立有序表,则每插入一个元素就需要遍历链表寻找插入位置,即直接插入排序,时间复杂度为O(n^2)。若先将数组排好序,然后建立链表,建立链表的时间复杂度为O(n),数组排序的最好时间复杂度为O(nlogn),总时间复杂度为O(nlogn)
3.
在双链表中向p所指的结点之前插入一个结点q的操作为()
A. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
B. q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
C. q->next=p; p->next=q; q->prior->next=q; q->next=p;
D. p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
答案:D
解析:在p之前插入结点q,可以将p的前一个结点的next域指向q,将q的next域指向p,将q的prior域指向p的前一个结点,将p的prior域指向q。
4.
带头节点的双循环链表L为空的条件是()
A. L->prior==L&&L->next==NULL;
B. L->prior==NULL&&L->next==NULL;
C. L->prior==NULL&&L->next==L;
D. L->prior==L&&L->next==L;
答案:D
解析:循环双链表L判空的条件是头结点(头指针)的prior和next域都指向它自身。
5.
一个链表最常用的操作是在末尾插入结点和删除结点,则选用()最节省时间
A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表
答案:A
解析:在链表的末尾插入和删除一个结点时,需要修改其相邻结点的指针域。在寻找尾结点及尾结点的前驱结点时,只有带头结点的双循环链表所需要的时间最少。
编程
题目:将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表
思路:按顺序不断将取下两个顺序表表头较小的结点存入新的顺序表中,然后,把有剩余的表的元素加到新的顺序表的后面。
代码:
bool Merge(SeqList A, SeqList B, SeqList &C)//A,B合并成C
{
if (A.length + B.length > C.maxsize)//超过C的长度,退出
return false;
int i = 0, j = 0, k = 0;
while (i < A.length && j < B.length)//选取小的元素存入C
{
if (A.data[i] <= B.data[j])
C.data[k++] = A.data[i++];
else
C.data[k++] = B.data[j++];
}
while(i < A.length) //剩余元素存入C
C.data[k++] = A.data[i++];
while (i < B.length)
C.data[k++] = B.data[j++];
C.length = k;
return true;
}