数据结构测试题

第1章 绪论

一、填空题（每空1分，共35分）

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 间的

和

等的学科。

的有限集合，R是D上的 以及它们之

2. 数据结构被形式地定义为（D, R），其中D是 有限集合。

3. 数据结构按逻辑结构可分为两大类，它们分别是 类，分别是

、

、

和

。

。若细分为4

和

4. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系。

关系，图形结构中元素之间存在 5. 在线性结构中，第一个结点 前驱结点；最后一个结点 结点。

6. 在树形结构中，树根结点没有

前驱结点，其余每个结点有且只有 个后继结点，其余每个结点有且只有 个后继

结点，其余每个结点有且只有 个前驱

结点；叶子结点没有后继结点，其余每个结点的后继结点数可以任意。 7. 在图形结构中，每个结点的前驱结点数和后继结点数可以 。

8. 数据结构包括数据的 、数据的 和数据的

这三个方面的内容。

9. 数据的存储结构可用四种基本的存储方法表示，它们分别是 、 和 。

、 、 、 、 10. 数据的运算最常用的有5种，它们分别是 、 。 11. 一个算法的效率可分为 二、B（每小题1分，共5分）

效率和 效率。

1. 数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A、存储 和存储

2. 算法分析的目的是（ ）。

A、找出数据结构的合理性 C、分析算法的效率以求改进 3. 算法分析的两个主要方面是：（ ）。

A、空间复杂性和时间复杂性 C、可读性和文档性 4. 计算机算法指的是（ ）。

A、计算方法

B、排序方法

B、正确性和简明性

D、数据复杂性和程序复杂性

B、研究算法中的输入和输出的关系 D、分析算法的易懂性和文档性

B、物理

C、逻辑

D、物理

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

5. 计算机算法必须具备输入、输出和（ ）等5个特性。

A、可行性、可移植性和可扩充性 C、确定性、有穷性和稳定性

B、可行性、确定性和有穷性 D、易读性、稳定性和安全性

三、判断下列叙述的对错。如果正确，在题前的括号内填入“?”，否则填入“?”。（每题1分，共8分）

1. （ ）数据元素是数据的最小单位。

2. （ ）数据结构是数据对象与对象中数据元素之间关系的集合。 3. （ ）数据结构是具有结构的数据对象。

4. （ ）算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 5. （ ）所谓数据的逻辑结构是指数据元素之间的逻辑关系。 6. （ ）数据的逻辑结构与数据元素本身的内容和形式无关。

7. （ ）数据结构是指相互之间存在一种或多种关系的数据元素的全体。 8. （ ）从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 四、设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。（每题4分，共24分）

(1) for (int i = 1；i <= n；i++）

for (int j = 1; j <= n; j++） {

c[i][j]=0.0；

for（int k = 1; k <= n; k++）

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

(2) x = 0；y = 0；

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

for( int k = 1; k <= j; k++)

x = x + y；

（3）k=0;

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

for(j=I; j<=n; j++)

k++;

}

五、分析下面各程序段的时间复杂度（每小题4分，共16分）

2. s=0;

1. for (i=0; i

for i=0; i

for (j=0; j

for(j=0; j

A[i][j]=0;

s+=B[i][j];

sum=s;

4. i=1; 3. x=0;

for(i=1; i

for (j=1; j<=n-i; j++) i=i*3;

x++;

(5) x=n; y=0;

while(x>=(y+1)*(y+1))

y++ ; (4) i=1; j=0;

while(i+j<=n) { }

if(i>j) j++; else i++;

(6) x=91; y=100;

while(y>0) { }

if(x>100) {x-=10; y--; } else x++;

六、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？（每小题4分，共12分） 1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }

2. D={d1,d2,?,d9}

R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }

3. D={d1,d2,?,d9}

R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}

第二章 线性表

一、填空（每空1分，共18分）

1、 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。

2、 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 个元素。

3、 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 个元素。

4、 在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表支持 访问。

相邻。单链表中逻辑上相邻的

相邻。

5、 顺序表中逻辑上相邻的元素的物理位置 元素的物理位置

6、 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示。 7、 在n个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 。

8、 循环单链表La中，指针P所指结点为表尾结点的条件是 。

9、 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

a) a. 在P结点后插入S结点的语句序列是： 。

。 。

。

b. 在P结点前插入S结点的语句序列是： c. 在表首插入S结点的语句序列是： d. 在表尾插入S结点的语句序列是： 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分） （ ）1、链表的每个结点中都恰好包含一个指针。

（ ）2、顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 （ ）3、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各

个单元向前移动。

（ ）4、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（ ）5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）7、线性表在物理存储空间中也一定是连续的。

（ ）8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ ）9、顺序存储方式只能用于存储线性结构。

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