欢迎来到天天文库
浏览记录
ID:56707894
大小:1.27 MB
页数:72页
时间:2020-07-05
《数据结构各章习题及答案.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。for(i=0;i2、O(x)。此时s与n满足关系式:s≥n,而s=1+2+3+…+x。所以有:1+2+3+…+x≥n,可以推出:x=x与n之间满足x=f(),所以循环体的时间复杂度为O(),语句①与循环体由线性累加规则得到该程序段的时间复杂度为O()。【例1-3】分析以下程序段的时间复杂度。i=1;①while(i<=n)i=2*i;②解:其中语句①的执行次数是1,设语句②的执行次数为f(n),则有:。得:T(n)=O()【例1-4】有如下递归函数fact(n),分析其时间复杂度。fact(intn){if(n<=1) return(1); 3、①elsereturn(n*fact(n-1)); ②}解:设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1),语句②的运行时间是T(n-1)+O(1),其中O(1)为常量运行时间。由此可得fact(n)的时间复杂度为O(n)。习题1一、单项选择题1.数据结构是指(1.A)。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为(2.C)。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种(3.4、D)。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间,则以下语句的时间复杂度为(4.B)。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是(5.C、),算法分析的两个主要方面是(A)。(1)A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性(2)A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指5、的是(6.C、),它具备输入,输出和(B)等五个特性。(1)A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法(2)A.可行性,可移植性和可扩充性B.可行性,确定性和有穷性C.确定性,有穷性和稳定性D.易读性,稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要(7.B)。A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在(8.D)年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构,这种观点(9.B)。A.正确6、B.错误C.前半句对,后半句错D.前半句错,后半句对10.计算机内部数据处理的基本单位是(10.B)。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类,分别是______________和_________________。1.线性结构,非线性结构2.数据的逻辑结构有四种基本形态,分别是________________、__________________、__________________和__________________。2.集合,线性,树,图3.线性结构反映结点间的逻辑关系是______7、____________的,非线性结构反映结点间的逻辑关系是__________________的。3.一对一,一对多或多对多4.一个算法的效率可分为__________________效率和__________________效率。4.时间,空间5.在树型结构中,树根结点没有__________________结点,其余每个结点的有且只有__________________个前趋驱结点;叶子结点没有__________________结点;其余每个结点的后续结点可以__________________。5.前趋,一,后继,多6.在图型8、结构中,每个结点的前趋结点数和后续结点数可以__________________。6.有多个7.线性结构中元素之间存在__________________关系;树型结构中元素之间存在____________
2、O(x)。此时s与n满足关系式:s≥n,而s=1+2+3+…+x。所以有:1+2+3+…+x≥n,可以推出:x=x与n之间满足x=f(),所以循环体的时间复杂度为O(),语句①与循环体由线性累加规则得到该程序段的时间复杂度为O()。【例1-3】分析以下程序段的时间复杂度。i=1;①while(i<=n)i=2*i;②解:其中语句①的执行次数是1,设语句②的执行次数为f(n),则有:。得:T(n)=O()【例1-4】有如下递归函数fact(n),分析其时间复杂度。fact(intn){if(n<=1) return(1);
3、①elsereturn(n*fact(n-1)); ②}解:设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1),语句②的运行时间是T(n-1)+O(1),其中O(1)为常量运行时间。由此可得fact(n)的时间复杂度为O(n)。习题1一、单项选择题1.数据结构是指(1.A)。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为(2.C)。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种(3.
4、D)。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间,则以下语句的时间复杂度为(4.B)。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是(5.C、),算法分析的两个主要方面是(A)。(1)A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性(2)A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指
5、的是(6.C、),它具备输入,输出和(B)等五个特性。(1)A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法(2)A.可行性,可移植性和可扩充性B.可行性,确定性和有穷性C.确定性,有穷性和稳定性D.易读性,稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要(7.B)。A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在(8.D)年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构,这种观点(9.B)。A.正确
6、B.错误C.前半句对,后半句错D.前半句错,后半句对10.计算机内部数据处理的基本单位是(10.B)。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类,分别是______________和_________________。1.线性结构,非线性结构2.数据的逻辑结构有四种基本形态,分别是________________、__________________、__________________和__________________。2.集合,线性,树,图3.线性结构反映结点间的逻辑关系是______
7、____________的,非线性结构反映结点间的逻辑关系是__________________的。3.一对一,一对多或多对多4.一个算法的效率可分为__________________效率和__________________效率。4.时间,空间5.在树型结构中,树根结点没有__________________结点,其余每个结点的有且只有__________________个前趋驱结点;叶子结点没有__________________结点;其余每个结点的后续结点可以__________________。5.前趋,一,后继,多6.在图型
8、结构中,每个结点的前趋结点数和后续结点数可以__________________。6.有多个7.线性结构中元素之间存在__________________关系;树型结构中元素之间存在____________
此文档下载收益归作者所有