[简答题]【说明】 设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次L.Locate(x)操作时，令元素值x的结点的访问频度 freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 【函数】 void Locate( int &x) { ＜结点类型说明＞ * p =first -＞ next; while(p!=frist&& (1) )P=P-＞next; if(p! =first) /*链表中存在x*/ { (2) ; ＜结点类型说明＞ * current = P; /*从链表中摘下这个结点*/ Current -＞ prior -＞ next = current -＞ next; Current -＞ next -＞ prior = current -＞ prior; P = current -＞ prior; /*寻找重新插入的位置*/ While(p! =first && (3) )p=p-＞prior; Current-＞ next = (4) ; /*插入在P之后* Current -＞ prior = P; P -＞ next -＞ prior = current; P-＞next= (5) ; } else printf("Sorry. Not find! /n"); /*没找到*/ }

[简答题]【说明】
设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次L.Locate(x)操作时，令元素值x的结点的访问频度 freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【函数】
void Locate( int &x)
＜结点类型说明＞
* p =first -＞ next;
while(p!=frist&& (1) )P=P-＞next;
if(p! =first) /*链表中存在x*/
(2) ;
＜结点类型说明＞
* current = P; /*从链表中摘下这个结点*/
Current -＞ prior -＞ next = current -＞ next;
Current -＞ next -＞ prior = current -＞ prior;
P = current -＞ prior; /*寻找重新插入的位置*/
While(p! =first && (3) )p=p-＞prior;
Current-＞ next = (4) ; /*插入在P之后*
Current -＞ prior = P;
P -＞ next -＞ prior = current;
P-＞next= (5) ;

else printf("Sorry. Not find! /n"); /*没找到*/

[简答题]设带表头结点的双向链表的定义为
typedef int ElemType；
typedef struct dnode∥双向链表结点定义
ElemType data；∥数据
struct dnode*lLink，*rLink；∥结点前驱与后继指针
)DblNode；
typedef DblNode*DblList；∥双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

[简答题]【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空： #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)

[简答题]【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：
#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)
//私有函数：递

[填空题]已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
(1)在P结点之前插入S结点的语句序列是______；
(2)在表首插入S结点的语句序列是______。
a P—＞nex=S b P—＞next=P—＞next—＞next
c P—＞next=S—＞next d S—＞next=P—＞next
e S—＞next=L f Q=P
g while(P—＞next!=Q＞P=P—＞next
h while(P—＞next!=NULL)P=P—＞next
i P=L j L=S

[简答题]设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

[单项选择]对于n个结点的单向链表(无表头结点)，需要指针单元的个数至少为（）。
A. n-1
B. n
C. n+1
D. 2n

[填空题]带头结点的双向循环链表L为空的条件是______。

[简答题]设有带头结点的循环双链表表示的线性表L=(a₁，a₂，……，a_n-1，a_n)。设计在时
间和空间上都尽可能高效的算法，将L改造成L=(a₁，a₃，……，a_n,……a₄，a₂)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。

[简答题]设有带头结点的循环双链表表示的线性表L=(a₁，a₂，…，a_n-1，a_n)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a₁，a₃，…，a_n，…，a₄，a₂)。要求：
给出算法的基本设计思想。

[填空题]双向循环链表找前驱结点和后继结点的时间复杂度为______。

[简答题]分别写出删除单向和双向循环链表中指针P所指的结点的直接后继结点(非尾结点)对应的语句。
(1)单向循环链表。
(2)双向循环链表。

[填空题]【说明2.1】
L为一个带头结点的循环链表。函数deletenode(LinkList L, int c)的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。
【函数2.1】
LinkList deletenode(LinkList L, int c)
　　　　
LinkList Lc,p,pre;
pre=L;
p= (1) ;
Lc=(LinkList)malloc(sizeof(ListNode) );
Lc-＞next=Lc
while(p!=L)
if(p-＞data＞c)

(2) ;
(3) ;
Lc-＞next=p;
p=pre-＞next;
　　　　
else

pre=p;
p=pre-＞next;

return Lc;

【说明2.2】
递归函数dec_to_k_2(int n, int k)的功能是将十进制正整数n转换成k＜2≤k≤9)进制数，并打印。
【函数2.2】
dec_to_k_2(int n, int k)
/*将十进制正整数n转换成k(2≤k≤9)进制数*/
if(n!=0)

dec_to_k_2( (4) ,k);
printf("%d", (5) );

[填空题]【说明2.1】 L为一个带头结点的循环链表。函数deletenode(LinkList L, int c)的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。 【函数2.1】 LinkList deletenode(LinkList L, int c) 　　{　　 LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinkList)malloc(sizeof(ListNode) ); Lc-＞next=Lc while(p!=L) if(p-＞data＞c) { (2) ; (3) ; Lc-＞next=p; p=pre-＞next; 　　　　} else { pre=p; p=pre-＞next; } return Lc; } 【说明2.2】 递归函数dec_to_k_2(int n, int k)的功能是将十进制正整数n转换成k＜2≤k≤9)进制数，并打印。 【函数2.2】 dec_to_k_2(int n, int k) { /*将十进制正整数n转换成k(2≤k≤9)进制数*/ if(n!=0) { dec_to_k_2( (4) ,k); printf("%d", (5) ); } }

[填空题]删除双向循环链表中*p的前驱结点(存在)应执行的语句是______。