数据结构习题1

数 据 结 构 习 题 册

（仅供计算机和信息专业同学参考）

计 算 机 科 学 技 术 教 研 室

二ＯＯ八年十一月

基

习

一、选择题

础

题

篇

1

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

A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性

2 在数据结构中，从逻辑上可以把数据结构分为（D ）

A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 内容结构和外部结构 D 线性结构和非线性结构

3 下面程序段的时间复杂性的量级为（D ） For (i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) x=x+1;

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

4 在数据结构中，与所使用的计算机无关的是数据的（A ）结构 A 逻辑 B 存储 C 逻辑和存储 D 物理

5 数据结构在计算机中的表示是指（C ）

A 数据的逻辑结构 B 数据结构 C 数据的存储结构 D 数据元素之间的关系

6 下面（B ）的时间复杂性最好，即执行时间最短。 A O(n) B O(logn) C O(nlogn) D O(n)

7 下面程序段的时间复杂性的量级为（D ）。 Int fun(int n){ I=1,s=1; While(s

s+=++I; return I; }

A O(n/2) B O(logn) C O(n) D O(n)

8 下面程序段的时间复杂性的量级为（C）。 For(int i=0;i

For(int j=0;j

1

1/2

2

2

3

A[i][j]=i*j;

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

9 执行下面程序段时，S 语句的执行次数为（A）。 For(int i=1;i

For(int j=i+1;j<=n;j++) S;

A n(n-1)/2 B n2/2 C n(n-1)/2 D n

3

2

二、简答题

1 数据的逻辑结构有哪几种？常用的存储有哪几种？

集合 线性结构 树形结构 图状结构 顺序存储结构 链式存储结构 2 举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。

3 什么叫算法？它有哪些特性

4 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。 （1）A=(K,R),其中 K={a,b,c,d,e,f,g,h} R={r}

r={,,,,,,} (2) B=(K,R),其中

K＝{a,b,c,d,e,f,g,h}

R={r}

r={,,,,,,} (3) B=(K,R),其中 K={1,2,3,4,5,6}

R={r}

r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

三、计算题

设n为整数，求下列各程序段的时间复杂度 （1）i=1;k=2;

While(i

k=k+10*I; i=i+1; }

(2)i=1;j=0;

While(i+j<=n) If(i>j)j=j+1;

Else i=i+1;

(3)x=91;y=100 While(y>0) If(x>100){

2

x=x-10; y=y-1;

}else x=x+1;

习题1参考答案

一、选择题

1. B 2. D 3. D 4. A 5. C 6. B 7. D 8. C 9. A 二、简答题

1. 答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。存储结构主要有顺序存储结构和链式存储结构。

2. 答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。这几个关系就确定了表的逻辑结构。

3. 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。 4.答：

(1) A对应的逻辑图形如下图左，它是一种线性结构。

h g f e c e

f

(2) B对应的逻辑图形如上图右所示，它是一种树型结构。 (3) C对应的逻辑图形如下图所示，它是一种图型结构。

3

1

2

4

5

6

h d a b c d b g a

三、计算题

解： (1) O(n) ； (2) O(n) ； (3) O(n1/2)。

习

一、选择题

题2

1 线性表是（A）

A 一个有限序列，可以为空 B 一个有限序列，不能为空 C 一个无限序列，可以为空 D 一个无限序列，不能为空

3