数据结构期末复习单选

数据结构（本科）期末综合练习一（单选题）

单选题

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

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

2. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

3. 下面程序段的时间复杂度为( )。 for(int i=0; i

for(int j=0; j

22

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

4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++)

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

22

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

5. 下面算法的时间复杂度为( )。 int f(unsigned int n) {

if(n==0 || n==1) return 1; else return n*f (n-1); }

2

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

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

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

7. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。

A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型

8. 当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O操作时，则应在程序文件中包含( )头文件。

A.fstream.h B.stdlib.h C.iomanip.h D.string.h

9. 一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空

1

间的大小即记录长度为( )。

A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值

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

2

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

2

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

2

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

2

12. 某算法的时间代价为T(n)=100n+10nlog2n+n+10，其时间复杂度为（ ）。

2

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

23

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

23

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

14. 以下说法错误的是（ ）。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。

C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。

15. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0个 B. 1个 C. 2个 D. n个

16. 多维数组实际上是由嵌套的（ ）实现的。

A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量

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

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

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

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

19. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ ）个元素。

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

2

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

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

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

2

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

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

2

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

23. 在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(n)

24. 在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（ ）。 A. 80 B. 100 C. 240 D. 270

25. 设有一个n?n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2

26. 设有一个n?n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。

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

27. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接

28. 不带头结点的单链表first为空的判定条件是（ ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;

29. 带头结点的单链表first为空的判定条件是（ ）。 A. first==NULL; B. first->link==NULL; C. first->link==first; D. first!=NULL;

30. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。

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

3

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

31. 设单链表中结点的结构为（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;

32. 设单链表中结点的结构为（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;

33. 非空的尾结点（由p所指向）满足的条件是（ ）。

A. p->lin循环单链表first的k==NULL; B. p==NULL; C. p->link==first; D. p==first;

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

C.rear = rear->link->link; delete rear;

D.s = rear->link->link; rear->link->link = s->link; delete s;

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

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

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

2

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

37. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ ）。 A. O(1) B. O(n)

2

C. O(n) D. O(nlog2n)

38.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n)

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

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

4

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

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

A. first＝NULL; B. first->rLink==first C. first->lLink==NULL D. first->rLink==NULL

41. 已知L是一个不带表头的单链表, 在表首插入结点*p的操作是（ ）。 A. p = L; p->link = L; B. p->link = L; p = L; C. p->link = L; L = p; D. L = p; p->link = L;

42. 已知L是带表头的单链表, 删除首元结点的语句是（ ）。

A. L = L->link; B. L->link = L->link->link; C. L = L; D. L->link = L;

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

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

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

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

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

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

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

48. 从一个顺序存储的循环队列中删除一个元素时，首先需要( )。 A. 队头指针加一 B. 队头指针减一

C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素

49. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear

50. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL

5

本文来源：https://www.bwwdw.com/article/waih.html