数据结构课程课后习题答案. 下载本文

《数据结构简明教程》练习题及参考

答案

练习题1

1. 单项选择题

(1)线性结构中数据元素之间是( )关系。 A.一对多 B.多对多 C.多对一 D.一对一 答:D

(2)数据结构中与所使用的计算机无关的是数据的( )结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答:C

(3)算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答:C

(4)算法分析的两个主要方面是( )。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答:A

(5)计算机算法指的是( )。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答:C

(6)计算机算法必须具备输入、输出和( )等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答:B 2. 填空题

(1)数据结构包括数据的 ① 、数据的 ② 和数据的 ③ 这三个方面的内容。

数据结构简明教程

答:①逻辑结构 ②存储结构 ③运算

(2)数据结构按逻辑结构可分为两大类,它们分别是 ① 和 ② 。 答:①线性结构 ②非线性结构 (3)数据结构被形式地定义为(D,R),其中D是 ① 的有限集合,R是D上的 ② 有限集合。

答:①数据元素 ②关系 (4)在线性结构中,第一个结点 ① 前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点 ② 后继结点,其余每个结点有且只有1个后继结点。

答:①没有 ②没有 (5)在树形结构中,树根结点没有 ① 结点,其余每个结点有且只有 ② 个前驱结点;叶子结点没有 ③ 结点,其余每个结点的后继结点数可以是 ④ 。

答:①前驱 ②1 ③后继 ④任意多个

(6)在图形结构中,每个结点的前驱结点数和后继结点数可以是( )。 答:任意多个

(7)数据的存储结构主要有四种,它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答:①顺序 ②链式 ③索引 ④哈希

(8)一个算法的效率可分为 ① 效率和 ② 效率。 答:①时间 ②空间

3. 简答题

(1)数据结构和数据类型两个概念之间有区别吗?

答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。

(2)简述线性结构、树形结构和图形结构的不同点。

答:线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。

(3)设有采用二元组表示的数据逻辑结构S=(D,R),其中D={a,b,…,i},R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)},问相对于关系R,哪些结点是开始结点,哪些结点是终端结点?

答:该逻辑结构为树形结构,其中a结点没有前驱结点,称为根结点,b、e、g、i结点没有后继结点,是终端结点,也称为叶子结点。

(4)以下各函数是算法中语句的执行频度,n为问题规模,给出对应的时间复杂度: T1(n)=nlog2n-1000log2n T2(n)=nlog23-1000log2n T3(n)=n2-1000log2n

T4(n)=2nlog2n-1000log2n

3答:T1(n)=O(nlog2n),T2(n)=O( n log 2 ),T3(n)=O(n2),T4(n)=O(nlog2n)。 (5)分析下面程序段中循环语句的执行次数。

int j=0,s=0,n=100;

do {

j=j+1; s=s+10*j;

练习题及参考答案 } while (j

答:j=0,第1次循环:j=1,s=10。第2次循环:j=2,s=30。第3次循环:j=3,s=60。第4次循环:j=4,s=100。while条件不再满足。所以,其中循环语句的执行次数为4。

(6)执行下面的语句时,语句s++的执行次数为多少?

int s=0;

for (i=1;i

for (j=n;j>=i;j--)

s++;

n?2in?2i?1答:语句s的执行次数??1??(n?i?1)?n?(n?1)???3?i?1j?n(n?3)(n?2)。

2(7)设n为问题规模,求以下算法的时间复杂度。

void fun1(int n) { }

int x=0,i;

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

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

x++;

答:其中x++语句属基本运算语句,T(n)????1?i?1j?i?1i?1nnn(n?i)?n(n?1)=O(n2)。 2(8)设n为问题规模,是一个正偶数,试计算以下算法结束时m的值,并给出该算法的时间复杂度。

void fun2(int n) { }

int m=0;

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

for (j=2*i;j<=n;j++)

m++;

n/2nn/2i?1答:由于内循环j的取值范围,所以i≤n/2,则m?????(n?(2i?1))?n2/4,该程

i?1j?2i序段的时间复杂度为O(n2)。

上机实验题1

有一个整型数组a,其中含有n个元素,设计尽可能好的算法求其中的最大元素和次大元素,并采用相关数据测试。

解:maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2,max1和max2设计为引用类型。对应的程序如下:

3

数据结构简明教程

#include

void maxs(int a[],int n,int &max1,int &max2) { }

void main() { }

int a[]={1,4,10,6,8,3,5,7,9,2}; int n=10; int max1,max2; maxs(a,n,max1,max2);

printf(\最大元素值=%d,次大元素值=%d\\n\int i;

max1=max2=a[0]; for (i=1;i

if (a[i]>max1) { }

else if (a[i]>max2)

max2=a[i]; max2=max1; max1=a[i];

练习题2

1. 单项选择题

(1)数据在计算机存储器内表示时,物理地址与逻辑地址相对顺序相同并且是连续的,称之为( )。

A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 答:C

(2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( )。 A.访问第i个结点(1≤i≤n)和求第i(2≤i≤n)个结点的前驱结点 B.在第i(1≤i≤n)个结点后插入一个新结点 C.删除第i个结点(1≤i≤n) D.将n个结点从小到大排序 答:A

(3) 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动( )个元素。

A.8 B.63.5 C.63 D.7 答:B

(4)链式存储结构所占存储空间( )。

A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B.只有一部分,存放结点值