作业6-改进的链表及链表应用

解析：因为要在最后一个元素之后插入元素和删除第一个元素，所以应该用带有尾指针的单循环链表。

解析：先将s的前驱指针指向p，再将s的后继指针指向p的下一个元素，再将p下一个元素的前驱指针指向s，最后将p的后继指针指向s，故此题选择D项。

解析：因为要经常在最后一个结点之后插入结点和删除最后一个结点，所以采用带头结点的双循环链表更方便。

解析：因为要经常在最后一个结点之后插入结点和删除最后一个结点，所以采用带头结点的双循环链表更方便。

解析：这是一个非空的循环单链表，因此p->next==h。

解析：因为要形成循环链表并且要返回循环链表的头指针，所以应该让p->next指向ha，并且返回头指针ha。

解析：要求时间复杂度为O(1)，并且占用辅助空间尽量小，因此应选择带尾指针的单循环链表。

typedef struct Node{
ElemType  data; 
   struct Node *left;  
   struct Node *right; 
intfreq;          
} DNode;
DNode *locate_DList(DNode *&L, ElemType x)
{ //在表L中查找元素x，查找成功则调整结点频度域值及结点位置，并返回结点地址；
//查找不成功则返回NULL
DNode *p=L, *q;
   if (L==NULL)  return NULL;
   while (p->data!=x && p->right!=L)  p=p->right;
   if (p->data!=x)  return NULL;
   p->freq++; 
   q=p->left;
   while (q!=L && q->freq<=p->freq)  q=q->left;  //查找插入位置
   if (q==L && q->freq<=p->freq) {  //需将p结点插在头结点L前
//将p结点先从链表中摘下来
p->left->right=p->right; 
      p->right->left=p->left;   
               //将p结点插在L结点前
      p->right=L;
      p->left=L->left;
      L->left->right=p;
      L->left=p;
      L=p;
   }
   else if (q!=p->left ) {  //若q不是p的前驱，则需调整结点位置，将p结点插在q结点后
//将p结点先从链表中摘下来
      p->left->right=p->right; 
      p->right->left=p->left;
      ______________ //将p结点插在q结点后         
   }
   return p;
}

解析：先将p的左指针指向q，再将p的右指针指向q的下一个元素，再将q的下一个元素的左指针指向p，最后将q的右指针指向p即可，
故此题选择C项。

解析：先将s的前驱指针指向p，再将s的后继指针指向p的下一个元素，再将p下一个元素的前驱指针指向s，最后将p的后继指针指向s，故此题选择D项。

解析：双向链表的优点是顺序访问相邻结点更加灵活。

解析：L的左指针指向L或者L的右指针指向L，则说明该双向循环链表为空。

解析：多项式相乘需要用其中一个多项式的每一项去乘以另一个多项式的所有项，因此时间复杂度为O(N1*N2)。

解析：循环链表的主要优点是从表中任意结点出发都能扫描到整个链表。

解析：先将s->next指针指向p，再将s->prior指针指向p->prior，然后再将p->prior->next指针指向s，最后将p->prior指向s即可。

解析：先将p的前一个元素的next指针指向p的下一个元素，再将p的下一个元素的prior指针指向p的前一个元素即可。

解析：因为要在线性表的最后一个结点之后插入结点和删除第一个结点，故应该采用带有尾指针的单循环链表。

解析：要删除最后一个元素需要找到其前驱，因此需要遍历该链表，故该操作与链表的长度有关。

解析：非空的循环单链表的尾指针p的下一个元素是头结点，因此p->next==head。

解析：因为要经常删除表中最后一个结点和在最后一个结点之后插入新结点，所以宜采用带尾指针的循环单链表。

解析：根据题目中描述的四种运算可知，用仅带头指针的循环双链表更方便。

解析：因为链表要经常删除第一个元素和在最后一个元素后面插入新结点，所以用仅带尾指针的循环单链表更方便。