目录
选择
编程
选择
1、
设对n（n>1）个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素之前插入新元素，在最后一个元素之后插入新元素，则最好使用（）
A. 只有尾结点指针没有头结点指针的循环单链表
B. 只有尾结点指针没有头结点指针的非循环双链表
C. 只有头结点指针没有尾结点指针的循环双链表
D. 既有头结点指针又有尾结点指针的循环单链表
答案：C
解析：
A.删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)
B.删除首结点*p时，需要找到*p结点。这里没有直接给出头结点指针，而通过尾结点的prior指针找到*p结点的时间复杂度为O(n)
C.执行这4种算法的时间复杂度均为O(1)
D.删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)
2、
某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度可能是（）
A. 0 B. 1 C. 2 D. 可能为0或1
答案：D
解析：
对一个空循环单链表，有 head->next==head，推理head->next->next==head->next==head。
对含有1个元素的循环单链表，头结点的next域指向该唯一元素结点，该元素的next域指向头结点，因此也有head->next->next==head。
3、
已知头指针h指向一个带头结点的非空单循环链表，结点结构为" data | next "，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句顺序是（）
A. h->next = h->next->next ; q = h->next ; free(q);
B. q = h->next ; h->next = h->next->next ; free(q);
C. q = h->next ; h->next = q->next ; if ( p ! = q ) p=h ; free(q);
D. q = h->next ; h->next = q->next ; if ( p= = q ) p=h ; free(q);
答案：D
解析：请看图1，要删除带头结点的非空单循环链表的第一个元素，就要先用临时指针q指向待删结点， q = h->next ；然后将q从链表中断开， h->next = q->next（这一步也可以写成h->next = h->next->next）；还有一种特殊情况是，若待删结点是链表的尾结点，即循环单链表中只有一个元素（p和q指向同一个结点），请看图2，则在删除后要将尾指针指向头结点，即 if ( p= = q ) p=h；最后释放q结点即可。
4、
关于线性表的顺序存储结构和链式存储结构的描述中，正确的有几个（）
线性表的顺序存储结构优于其链式存储结构；
链式存储结构比顺序存储结构能更方便地表示各种逻辑结构；
若频繁的使用插入和删除结点操作，则顺序存储结构更优于链式存储结构；
顺序存储结构和链式存储结构都可以进行顺序存取
A. 1 B. 2 C. 3 D. 4
答案：B
解析：两种存储结构有不同的使用场合，不能简单地说哪个更好，第一个错误；
链式存储用指针表示逻辑结构，而指针的设置是任意的，故可以很方便地表示各种逻辑结构，顺序存储只能用物理上的邻接关系来表示逻辑结构，第二个正确；
在顺序存储中，插入和删除结点需要移动大量元素，效率较低，第三个错误；
顺序存储结构既能随机存取又能顺序存取，而链式结构只能进行顺序存取，第四个正确。
5、
设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高
A. 删除所有值为x的元素
B. 在最后一个元素的后面插入一个新的元素
C. 顺序输出前k个元素
D. 交换第i个元素和第2n-i-1个元素的值（i=0，...，n-1）
答案：A
解析：对于A，在单链表上实现和在顺序表上实现的时间复杂度都为O(n)，但是顺序表要移动很多的元素，所以在单链表上效率更高。对于B,D。顺序表更高；对于C，两者效率一样。
编程
题目：设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
思路：设计一个函数func(L，x)的功能是删除以L为首结点指针的单链表所有值等于x的结点， 那么func(L->next，x)就是删除以L->next为首结点指针的单链表所有值等于x的结点，那么就可以递归调用这个func()函数。
void Del_x(LinkList &L, ElemType x)
{LNode *p; //p指向待删除结点if(L==NULL)return ;if(L->data==x) //如果L指向的结点的值为x{p=L: //删除*L，并让L指向下一个结点L=L->next;free(p);Del_x(L,3); //函数递归调用}else //L指向的结点的值不为xDel_x(L->next,3);
}
