数据结构复习题(4A)

数据结构复习题 第1章 绪论

一、单选题（共有题目8题）

1.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n2) D. O(n!) 标准答案：B

2.输出一个二维数组b[m][n]中所有元素值的时间复杂度为（ ）。 A. O(m+n) B. O(m×n) C. O(m2) D. O(n2) 标准答案：B

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

A. O(m2) B. O(n2) C. O(m×n) D. O(m+n) 标准答案：C

4.分析下面程序段的时间复杂度是（ ）。 int i=1; while (i<=n) i=i*2;

A. O(n) B. O(log2n) C. O(n2) D. O(1) 标准答案：B

5.下面程序段的时间复杂度是（ ）。 int i,j;

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

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

标准答案：B S语句执行的次数为n(n+1)/2。 6.下面算法的时间复杂度为（ ）。 int f( int n) {

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

A. O(n) B. O(1) C. O(n 2) D. O(n!) 标准答案：A

7.下面程序段的时间复杂度是（ ）。 int i,j;

for( i=0; i

A. O(n 2) B. O(m 2) C. O(m×n) D. O(m+n) 标准答案：C

二、多选题（共有题目1题） 1.int Prime(int n) { int h=n/2;

int i;

for(i=2;i<=h;i++) {

1

if (m%i==0) break; }

if(i>h) return 1; else return 0; }

请问该算法的功能是什么？它的时间复杂度数量级是哪个？ 标准答案：判断整数n是不是素数；O(n) 三、填空题（共有题目14题）

1.在线性结构中，前驱结点和后继结点之间存在着1对1(1：1 或 一对一)的联系。

2.对算法评价一般从正确性、健壮性、可读性、简单性、时间复杂度、空间复杂度六个方面进行的。 3.在图形结构中，前驱和后继结点之间存在着多对多;m：n的联系。

4.数据结构研究的内容主要包括数据的逻辑结构、数据的存储结构（数据的物理结构）和数据的操作三部分。

5.数据的物理结构又名存储结构_，它主要有顺序存储、链接存储、索引和散列4种方式。 6.在树形结构中，前驱和后继结点之间存在着1对多（1：N）联系。

7.数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构4种。

8.算法是指对特定问题求解步骤的一种描述，是一组指令的有限序列；也可以说是解决特定问题的方法步骤。

9.在一个算法的程序描述中，不同的语句重复执行的次数不同，某语句重复执行的次数称为该语句的频度（频次）。

10.记录（数据记录）是数据处理领域组织数据的基本单位。

11.依据视点的不同，数据结构分为数据的逻辑结构和物理结构。数据的逻辑结构是面向问题的，数据的物理结构（数据的存储结构）是面向计算机的。

12.算法应具备有穷性、确定性、可行性、输入和输出五个特性。

13.在下面程序段中，s=s+p语句的执行次数是n，p*=j语句的执行次数是n(n+1)/2，该程序段的时间复杂度为O(n 2)。

int i=0,s=0; while(++i<=n) { int p=1;

for( int j=1;j<=i;j++) p*=j; s=s+p; }

14.数据元素;元素是一个数据整体中相对独立的单位。 四、判断题（共有题目6题）

1.数据结构是数据对象与对象中数据元素之间关系的集合。对

2.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。错 3.数据元素是数据的最小单位。错

4.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。对 5.只有用面向对象的计算机语言才能描述数据结构算法。 错 6.算法和程序原则上没有区别，在讨论数据结构时两者是通用的。 错 五、程序填空题（共有题目1题）

1.数据结构的研究内容包括数据的逻辑结构、数据的存储结构和数据的操作三部分内容。

第2章 线性表

一、单选题（共有题目55题）

2

1. 数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5][5]的地址是( )。

A. 1140 B. 1145 C. 1120 D. 1125 标准答案：A

2.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省运算时间。

A. 单链表 B. 双链表 C. 单循环链表 D. 带头结点的双循环链表 标准答案：A（D）

3. 已知L是带附加表头的单链表，删除表头结点的语句是（ ）。

A. L = L->next; B. L-> next = L-> next -> next; C. L = L; D. L-> next = L; 标准答案：B

4. 给定有n个元素的数组，建立一个有序单链表的时间复杂度是（ ） A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 标准答案：B

5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。 A. p=q->next;p->next=q->next; B. p=q->next;q->next=p;

C. p=q->next;q->next=p->next; D. q->next=q->next->next;q->next=q; 标准答案：C

6.在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 标准答案：C

7.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用( )存储方式节省时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 标准答案：D

8.不带头结点的单链表first为空的判定条件是（ ）。 A. first == NULL; B. first-> next == NULL; C. first-> next == first; D. first != NULL; 标准答案：A

9.执行下面程序段时，执行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 标准答案：D

10. 设单链表中结点的结构为（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; 标准答案：A

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

A. *(a+i) B. a+i C. *a+i D. &a+i 标准答案：A

12. 非空的循环单链表head的尾指针p满足( )。

A. p->next=NULL B. p==NULL C. P->next==head D. p==head 标准答案：C

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

3

A. 80 B. 100 C. 240 D. 270 标准答案：C

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

A. n B. n/2 C. (n+1)/2 D. (n-1)/2 标准答案：C

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

A. first==NULL; B. first-> next ==NULL; C. first-> next ==first; D. first!=NULL; 标准答案：B

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

A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 标准答案：A

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

A. O(n) B. O(n2) C. O(n3) D. O(1) 标准答案：C

19.有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为( )。

A.head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 标准答案：B

20. 设有一个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 标准答案：C

21.在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。

A. s→next = p→next; p→next = s; B. p→next = s; s→next = q; C. p→next = s→next; s→next = p; D. q→next = s; s→next = p; 标准答案：D

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

A. n-i B. n-i+1 C. n-i-1 D. i 标准答案：A

23.设单链表中结点的结构为（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; 标准答案：B

24.在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为（ ）。

A. O(1) B. O(1) C. O(log2n) D. O(n) 标准答案：C

25.在一个单链表HL中，若要在指针q所指向结点的后面插入一个由指针p所指向的结点，则执行（ ）。

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

C. q->next=p->next; q->next=p; D. p->next=q->next; q->next=p; 标准答案：D

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

4