单选题(答案)

单选题

1. 一个数组元素a[i] 与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 下面程序段的时间复杂度为( )。

for(int i=0; ifor(int j=0; jA. O(m2) B. O(n2) C. O(m*n) D. O(m+n)

3. 执行下面程序段时，执行S语句的次数为( )。

for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2

4. 下面算法的时间复杂度为( )。

int f(unsigned int n) {

if(n==0 || n==1) return 1;

else return n*f (n-1);

}

A. O(1) B. O(n) C. O(n2) D. O(n!)

5. 一种抽象数据类型包括数据和( )两个部分。

A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明

6. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。

A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

7. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为( )。

A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)

8. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（ ）。

A. O(n) B. O(n2) C. O(n3) D. O(1)

9. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为（ ）。

A. n B. n/2 C.(n+1)/2 D.(n-1)/2

10. 在一个长度为n的顺序表中向第i个（1≤i≤n）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

11. 在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2 B. n/2 C. n D. n+1

12. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。

A. O(n) B. O(1) C. O(n2) D. O(log2n)

13. 不带头结点的单链表first为空的判定条件是（ ）。

A. first == NULL; B. first->next == NULL;

C. first->next == first; D. first != NULL;

14. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点

的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。

A. s->link=p->link; p->link=s; B. q->link=s; s->link=p;

C. p->link=s->link; s->link=p; D. p->link=s; s->link=q;

15. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ ）。

A.s->link=p; p->link=s; B. p->link=s; s->link=p;

C.s->link=p->link; p=s; D. s->link=p->link; p->link=s;

16. 设单链表中结点的结构为（data, link）。若想摘除p->link所指向的结点，则应执行的操作是（ ）。

A. p->link=p->link->link; B. p=p->link; p->link=p->link->link;

C. p->link=p; D. p=p->link->link;

17. 非空的循环单链表first的尾结点（由p所指向）满足的条件是（ ）。

A. p->link==NULL; B. p==NULL;

C. p->link==first; D. p==first;

18. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。

A.s = rear; rear = rear->link; free( s);

B.rear = rear->link; free( rear);

C.rear = rear->link->link; free( rear);

D.s = rear->link->link; rear->link->link = s->link; free( rear);

19. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（ ）。

A. n B. n/2

C. (n-1)/2 D. (n+1)/2

20. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。

A. O(1) B. O(n) C. O(n2) D. O(nlog2n)

21. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ ）。

A. O(1) B. O(n)

C. O(n2) D. O(nlog2n)

22.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。

A. O(1) B. O(m)

C. O(n) D. O(m+n)

23. 利用双向链表作线性表的存储结构的优点是（ ）。

A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作

C. 节省空间 D. 便于销毁结构释放空间

24. 带表头的双向循环链表的空表满足（ ）。

A. first＝NULL; B. first->next==first

C. first->prior==NULL D. first->next==NULL

25. 已知L是一个不带表头的单链表, 在表首插入结点*p的操作是（ ）。

A. p = L; p->next = L; B. p->next = L; p = L;

C. p->next = L; L = p; D. L = p; p->next = L;

26. 栈的插入和删除操作在( )进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

27. 当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改top值。

A. top++; B. top--; C. top = 0; D. top;

28. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。

A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2

29. 在一个顺序存储的循环队列中，队头指针指向队头元素的( )位置。 A. 前一个 B. 后一个 C. 当前 D. 后面

30. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( A. n-2 B. n-1 C. n D. n+1

)。