数据结构 每日一练：选择 + 编程

目录

选择

编程

---

选择

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指向的结点的值不为x
        Del_x(L->next,3);
}