简答题

1. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
   顺序
2. 线性表 L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
   (n-1)/2
3. 设单链表的结点结构为(data,next)，next 为指针域，已知指针 px 指向单链表中 data 为 x 的结点，指针py 指向 data 为 y 的新结点 , 若将结点 y 插入结点 x 之后，则需要执行以下语句:_______； ______;
   py->next=px->next;px->next=py;
4. 在一个长度为 n 的顺序表中第 i 个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
   n-i+1
5. 在单链表中设置头结点的作用是________。
   主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
6. 对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为________,在给定值为 x 的结点后插入一个新结点的时间复杂度为________。
   O(1)，O(n)
7. 在双向链表结构中，若要求在 p 指针所指的结点之前插入指针为 s 所指的结点，则需执行下列语句：s->next:=p； s->prior:= ________；p->prior:=s；________:=s；
   p->prior s->prior->next
8. 链接存储的特点是利用________来表示数据元素之间的逻辑关系。
   指针
9. 顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
   物理上相邻 指针
10. 循环单链表的最大优点是：________。
    从任一结点出发都可访问到链表中每一个元素
11. 已知指针 p 指向单链表 L 中的某结点，则删除其后继结点的语句是：________。
    u=p->next;p->next=u->next;free(u);
12. 带头结点的双循环链表 L 中只有一个元素结点的条件是：________。
    L->next->next==L
13. 在单链表 L 中，指针 p 所指结点有后继结点的条件是：__。
    p->next!=null
14. 带头结点的双循环链表 L 为空表的条件是：________。
    L->next==L&&L->prior==L
15. 在单链表 p 结点之后插入 s 结点的操作是：_______
    s->next=p->next;p->next=s;
16. 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？
    采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在 链式存储结构中插入和删除操作不需要移动元素。
17. 线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。
    线性表 栈 队列 串 顺序存储结构和链式存储结构
18. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系
    在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
19. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
    在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。
20. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？
    本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。
21. 设单链表中某指针 p 所指结点（即 p 结点）的数据域为 data，链指针域为 next，请写出在 p 结点之前插入 s 结点的操作。
    设单链表的头结点的头指针为head,且pre=head；
    while(pre->next!=p) pre=pre->next;
    s->next=p;pre->next=s;
    
22. 设双向循环链表中结点的数据域、前驱和后继指针域分别为 data,pre 和 next,试写出在指针 p 所指结点之前插入一 s 结点的 C 语言描述语句。
    s->pre=p->pre;s->next=p;p->pre->next=s;p->pre=s;