13994数据结构习题及参考答案

习题1

一、单项选择题

1. 数据结构是指（ A ）。

A.数据元素的组织形式 B.数据类型

C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ C ）。

A.存储结构

C.链式存储结构

B.逻辑结构 D.顺序存储结构

3. 树形结构是数据元素之间存在一种（D ）。

A.一对一关系 B.多对多关系

C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ B ）。

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

x++;

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

2 C.O(n) D.O(n)

35. 算法分析的目的是（1.C），算法分析的两个主要方面是（2.A）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性

（2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性

6. 计算机算法指的是（1.C），它具备输入，输出和（2.B）等五个特性。 （1） A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性

C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性

7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ）。

A.低 B.高

C.相同

D.不好说

8. 数据结构作为一门独立的课程出现是在（ D）年。

A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ B ）。

A.正确

C.前半句对，后半句错

B.错误

D.前半句错，后半句对

10. 计算机内部数据处理的基本单位是（ B ）。

A.数据 B.数据元素 C.数据项 二、填空题

D.数据库

1. 数据结构按逻辑结构可分为两大类，分别是___线性结构___________和______非线性结构___________。

2. 数据的逻辑结构有四种基本形态，分别是___集合_____________、____线性

______________、____树______________和___图_______________。

3. 线性结构反映结点间的逻辑关系是_____一对一_____________的，非线性结构反映结点间的逻辑关系是______一对多或多对多____________的。

4. 一个算法的效率可分为______时间____________效率和_______空间___________效率。

5. 在树型结构中，树根结点没有______前趋____________结点，其余每个结点的有且只有______一____________个前趋驱结点；叶子结点没有______后趋____________结点；其余每个结点的后续结点可以_______多___________。

6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_____有多个_____________。

7. 线性结构中元素之间存在_______一对一___________关系；树型结构中元素之间存在_____一对多_____________关系；图型结构中元素之间存在______多对多____________关系。

8. 下面程序段的时间复杂度是_____Ｏ（ｎ２）_____________。

for(i=0;i

A[i][j]=0;

9. 下面程序段的时间复杂度是______Ｏ（ｎ１／２）____________。

i=s=0; while(s

10. 下面程序段的时间复杂度是______Ｏ（ｎ２）____________。

s=0;

for(i=0;i

for(j=0;j

s+=B[i][j];

sum=s;

11. 下面程序段的时间复杂度是______Ｏ（ｌｏｇ３ｎ）____________。

i=1; while(i<=n)

-2-

i=i*3;

12. 衡量算法正确性的标准通常是__________程序对于精心设计的典型合法数据输入能得出符合要求的结果__________________________。

13. 算法时间复杂度的分析通常有两种方法，即___事后统计________和_____事前估计______的方法，通常我们对算法求时间复杂度时，采用后一种方法。 三、求下列程序段的时间复杂度。

1. x=0;

for(i=1;i

x++; Ｏ（ｎ２）

2. x=0;

for(i=1;i

x++; Ｏ（ｎ２）

3. int i,j,k;

for(i=0;i

for(j=0;j<=n;j++) { c[i][j]=0;

for(k=0;k

c[i][j]=a[i][k]*b[k][j]

} Ｏ（ｎ３）

4. i=n-1;

while((i>=0)&&A[i]!=k))

j--;

return (i); Ｏ（ｎ）

5. fact(n)

{ if(n<=1)

return (1);

else

return (n*fact(n-1));

} Ｏ（ｎ）

习题2 一、单项选择题

1. 线性表是___Ａ_____。

A．一个有限序列，可以为空 C．一个无限序列，可以为空

B．一个有限序列，不可以为空 D．一个无限序列，不可以为空

2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 Ａ 个元素。

-3-

A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址___Ｄ_____。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以

4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，

需平均比较___Ｃ_____个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/2

5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是__Ｄ__。

A． p->next=s; s->prior=p;

p->next->prior=s; s->next=p->next;

B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为___Ａ_____。

A．p->next=p->next->next; C．p=p->next->next;

B．p=p->next;

D．p->next=p;

7. 在一个长度为n的顺序表中向第i个元素(0< i

A．n-i B．n-i+l C．n-i-1 D．i

8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行Ｂ

A．s->next=p->next; p->next=s B．q->next=s; s->next=p

C．p->next=s->next; s->next=p D．p->next=s; s->next=q

9. 以下关于线性表的说法不正确的是___C___。

A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。

C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种___A____的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取

11. 在顺序表中，只要知道__D_____，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小

-4-