单项选择题

1.下面程序段的时间复杂度为 ( ) s=0; for(i=1;i＜n;i++) for(j=1;j＜i;j++) s+=i*j;

（A）O(1)

（B）O(log2n)

（C）O(n)

（D）O(n3)

【正确答案】D

2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 ( )

（A）q—＞next=s—＞next;s—＞next=p;

（B）s—＞next=P;q—＞next=s—＞next;

（C）p—＞next=s—＞next;s—＞next=q;

（D）s—＞next=q;p—＞next=s—＞next;

【正确答案】A

3.在计算机内实现递归算法时所需的辅助数据结构是 ( )

（A）栈

（B）队列

（C）树

（D）图

【正确答案】A

4.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 ( )

（A）(rear-length+m+1)%m

（B）(rear-length+m)%m

……此处隐藏7326个字…… ld=NULL; } } }

【正确答案】1.

算法设计题

34.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ int data; struct node*next; }LinkNode,*LinkList; 编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一 个)。算法的函数原型给定为 LinkList f 34(int n);

【正确答案】LinkList f 34(int n) { LinkList L,P,q,s; int e,i; L=(LinkList)malloe(sizeof(LinkNode)); L—＞next=NULL; for(i=1;i＜=n;i++){ seanf("%d",&e); p=L; q=p—＞next; while(q&&q—＞data＜e){ p=q; q=q—＞next; } if(!q||q—＞data＞e){ s=(LinkList)malloc(sizeof(LinkNode)); s—＞data=e; s—＞next=q; p—＞next=s; } } return L; }