2243计算机软件基础(一)复习资料10

36.在带头结点的循环链表中将头指针改设为尾指针（read）后，其第一个结点和尾结点的存储位置分别是 read ->next-> next 和read

37在一个具有n个结点的有序顺序表中插入一个新结点，并仍然有序的时间复杂度  O（n² ） 

38.带头结点的单链表head为空的判点条件是head -> next= = NULL

39.下列程序中功能是（对顺序表进行插入运算）

Void insert _Sq list (Sqlist L, datatype x , int i) ;

{ if ( L.last = = maxsize ) error (‘表满‘) ；

 if ( (i<1) || (i>L.last +1) ) error (‘非法位置‘) ；

 for ( j=L.last; j＞＝i;  j - - )  L.data [ j ] =L.data [j-1] ；

 data [i] = x ;

L.last = L.last +1 ; }

40.以下为计算带头结点单链表的表长

int  length_lklist (lklist head)

{ lklist p = head ;

 j=0 ;

While (p->next ! = NULL )

{p = p->next ;

 j + + ; }

return (j) ; }

41.以知单链表L中的结点，按值非递减有序排列的，试写一算法，将值为 x的结点插入 L中，使得L仍然有序，

Void CR_lk list (lklist *l ,datatype x )

{ lklist *q, *p,*s;

q = l ; p=q ->next ;

While ( ( p! = NULL ) && (p-> data<x ) )

{ q = p ;p = p-> next ; }

s=( lklist *) mallo (sizeof(lklist) ) ; s-> data = x ;

s -> next = q -> next ; q -> next = s ; }

42.入队列的操作

 Void  En_Queve (lqueptrTP * lp ,datatype,x )

  {lqueueTP * P ;

   P = (lqueueTP * P ) malloc ( size of (lqueueTP ) );

   P -> data = x;

   p-> next = NULL ;

  ( lp-> rear ) -> next =p ;

  lp -> rear = p ; }

43.在以下栈的运算中，不是加工运算的是，( D )

A  lnitstack (s ) B  push ( s, x ) C  pop ( s ) D  Enpth ( s )

44.循环队列的队满条件为 （ sq. rear + 1 ）% maxsize = = sq . front

45.循环队列的对空条件为 Sq . rear = sq .front .

47.改C语言数组 Date [ m+1 ] 作为循环队列 SQ 的存储空间，frone 为对头指针，rear 为对尾指针，则执行出队操作的语句为 front = ( front+1 ) % (m+1)

48.一个队列的输入列序 1,2 ,3,4 则队列的输出序列是 1,2,3,4

49.下列程序的功能是什么？ 借助栈将一个带头结点的单链表倒置

void list(LinklistTP *head)

{ LStackTP ls;

LinklistTP *p;

  DataType x;

  InitStack(&ls);

  p=head->next;

  while(p!=NULL)

{ Push (&ls, p->data); p=p->next; }

          p=head->next;

          While( ! EmptyStack(&ls))

            { Pop(&ls,&x); p->data=x; p=p->next;}

         }