else p->score=60; p=p->next; q=q->next; } }
}
34、假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100 typedef struct {
int data[ListSize]; int length;
} SeqList, *Table;
编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 （2010年1月）
3、将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ ）
A、O(1) B、O(m) C、O(n) D、O(m+n) 4、在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ ）
A、2个 B、3个 C、4个 D、6个 17、长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。
30、已知下列程序，Ls指向带头结点的单链表。 Typedefstruct node { DataType data; struct node * next; } * LinkList;
void f30( LinkList Ls ) { LinkList p, q;
q = Ls->next;
if ( q && q->next ) { Ls->next = q->next; p=q
while ( p->next ) p = p->next; p->next = q;
}
q->next = NULL;
}
请回答下列问题：
(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。
(2)请简述算法的功能。 （2010年10月）
2、若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( ) A、无头结点的单向链表 B、带头结点的单向链表 C、带头结点的双循环链表 D、带头结点的单循环链表 3、若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )
A、head=NULL B、head->next=NULL C、head!=NULL D、head->next!=head 17、已知链表结点定义如下：
typedef struct node{
char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。
30、已知线性表(a1,a2,a3，…，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a[],int n) { int k,m,temp； m= (1) ；
while (a[m]<0 &&m m= (2) ； k=m; while (k { while(a[k]>=0&&k k= (3) ； if(k { temp=a[k]； a[k]=a[m]； a[m]= (4) ； m= (5) ； } } } (1) (2) (3) (4) (5) 33、设有单链表类型定义如下： typedef struct node { int data; struct node *next; } *LinkList; 阅读下列算法，并回答问题： void f33(LinkList head, int A, int B) { LinkList p=NULL; While (head !=NULL) { if (head->data>A&&head->data p=head; head=head->next; } if (p !=NULL) printf(\ } (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果； (2)简述算法f33的功能。 （2011年1月） 2、将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ） A、n-1 B、n C、2n-1 D、2n 17、在单链表中某结点后插入一个新结点，需要修改_______________个结点指针域的值。 32、阅读下列程序。 void f32(int A[],int n) { int i,j,m=l,t； for (i=0; i for (j=0； j for (j=1; j if (A[j-1]>A[j]) { t=A[j-l]; A[j-1]=A[j]； A[j]=t； m=1； } } } 回答问题： 已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。 34、假设用带头结点的单循环链表表示线性表，单链表的类型定义如下： typedef struct node { int data; struct node*next; }LinkNode，*LinkList; 编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为： float f34(LinkList head); （2011年10月） 2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ） A.O（1） B.Ｏ（log n） C.O（n） D.O（n2） 3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ） A.p1－＞next=p2－＞next;p2－＞next=p1－＞next; B. p2－＞next=p1－＞next;p1－＞next=p2－＞next; C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p; 17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由_____________
