有一个不带表头节点的单链表，其节点类型为LinkList。设计一个递归算法，删除以h为首指针的单链表中值为x的所有节点。

已知一个带有表头结点的单链表，结点结构为(data，link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)，若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求： (1)描述算法的基本设计思想； (2)描述算法的详细实现步骤； (3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或Java语言实现)，关键之处请给出简要注释。【2009年全国试题42(15分)】

设有指针p指向带表头结点的单链表，现将指针p指向节点的后继节点删除(不考虑节点值及空间回收)，其操作是______。其中p^.next表示p所指节点的链域，q是一个临时指针变量，初始值为null。

A．p：=p^.next

B．q：=p^.next；p^.next：=q^.next

C．p^.next：=q；q^.next：=p

D．p：=q^.next；q^.next=p

已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求： (1)描述算法的基本设计思想； (2)描述算法的详细实现步骤； (3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或JAVA语言实现)，关键之处请给出简要注释。

给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(dam，next)，dam为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间。)【华中理工大学2000八、2(13分)】

编写逆向输出不带头结点的单向链表中数据域的递归算法。设表中有4个结点，从表头至表尾其数据域分别为10，30，20，40，作图表示出该算法的执行过程。设该链表的结点的数据类型的名称为list，结点的数据域和指针域的名称分别为data和next，不必写出list的定义。【中南大学2005四、3(10分)】

若L是一个无表头结点的单链表，P结点既不是首结点，也不是尾结点。删除P结点的后继结点的语句是(57)。

A．P→ next = P→next→next; Q=P→next; free(Q);

B．Q = P → next; P → next = P → next→next; free(Q);

C．P → next → next = P → next; Q = P → next; free(Q);

D．Q = P → next; P → next → next = P→next; free(Q);

若L是一个无表头结点的单链表，P结点既不是首结点，也不是尾结点。则在P结点后插入S结点的语句是(32)。

A．S→next=P→next；P→next=S；

B．P→next=S；S→next=P→next；

C．S=P→next；P→next=S→next；

D．P→next=S→next；S=P→next；

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：

include＜iostream．h＞

include＜assert．h＞

template＜class T＞class List；

template＜class T＞class ListNOde{

friend (1)；

private：

T data；

ListNode＜T＞ *link；

public：

ListNode()：link(NULL)()

ListNOde(const T& item，ListNOde＜T＞*next＝NULL)

：data(item)，link(next){}

}；

template＜class T＞class List{

private：

ListNode＜T＞*first；

void createList(T A[]，int n，int i，ListNOde＜T＞*&p)；

void printList(ListNOde＜T＞*p)；

public：

List()；

～List()；

friend ostream& operator＜＜(ostream& ost，List＜T＞&L)；

friend istream& operator＞＞(istream& ist，List＜T＞&L)；

}；

template＜class T＞

istream& operator＞＞(istream& ist，List＜T＞&1){

int i，n； ist＞＞n；

T A[n]；

for(i＝0；i＜n；i++) (2)；

createList(A，n，0，first)；

}

template＜class T＞

void List＜T＞：：createList(TA[]，int n，int i，ListNOde＜T＞*& p){

//私有函数：递归调用建立单链表

if(i＝＝n)p＝NULL；

else{

p＝new ListNode＜T＞(A[i])；

assert(p !＝NULL)；

createList((3))；

}

}

template＜class T＞

ostream& operator＜＜(ostream& ost,List＜T＞& L){

(4)；

}

template＜class T＞

void List＜T＞：：printList(ostream& ost，ListNode＜T＞*p){

if(p!＝NULL){

ost＜＜p-＞data；

(5)；

}

}

已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

(1)删除P结点的语句序列是______；

(2)删除尾元结点的语句是______。

a P—＞next=P—＞next—＞next b P=P—＞next—＞next

c while(P—＞next!=Q)P=P—＞next

d while(P—＞next!—＞next!=Q)P=P—＞next

e while(P—＞next!—＞next!=NULL)P=P—＞next

f Q=P g Q=P—＞next

h P=L i L=L—＞next

j free(Q)