严蔚敏数据结构各章习题及答案.docx

《严蔚敏数据结构各章习题及答案.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、严蔚敏数据结构各章习题及答案数据布局习题及解问第1章概述【例1-1】剖析下列步伐段的光阴庞大度。for(i=0;i解：该步伐段的光阴庞大度为O(m*n)。【例1-2】剖析下列步伐段的光阴庞大度。i=s=0;①while(s解：语句①为赋值语句，其实行次数为1次，以是当时间庞大度为O(1)。语句②以及语句③形成while轮回语句的轮回体，它们的实行次数由轮回把持前提中s取n的值断定。假设轮回反复实行x次后停止，则语句②以及语句③各反复实行了x次。当时间庞大度按线性乏减划定规矩为O(x)。此时s取n谦足闭系式

2、：s≥n，而s=1+2+3+…+x。以是有：1+2+3+…+x≥n，能够推出：x=nn241212811+±-=+±-x取n之间谦足x=f(n），以是轮回体的光阴庞大度为O(n)，语句①取轮回体由线性乏减划定规矩患上到该步伐段的光阴庞大度为O(n）。【例1-3】剖析下列步伐段的光阴庞大度。i=1;①while(i解：个中语句①的实行次数是1，设语句②的实行次数为f(n)，则有：nnf≤)(2。log)患上：T（n）=O(n2【例1-4】有以下递回函数fact(n)，剖析当时间庞大度。fact(intn){

3、if(nreturn(1);①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.链式存储

4、布局D.逆序存储布局3.树形布局是数据元素之间存正在一种（3.D）。A.一对于一闭系B.多对于多闭系C.多对于一闭系D.一对于多闭系4.设语句x++的光阴是单元光阴，则下列语句的光阴庞大度为（4.B）。for(i=1;ifor(j=i;jx++;A.O(1)B.O(2n)C.O(n)D.O(3n)5.算法剖析的目标是（5.C、），算法剖析的两个次要圆里是（A）。（1）A.寻出数据布局的开感性B.研讨算法中的输出以及输入闭系C.剖析算法的效力以供改善D.剖析算法的易懂性以及文档性（2）A.空间庞大度以及光阴

5、庞大度B.准确性以及扼要性C.可读性以及文档性D.数据庞大性以及步伐庞大性6.盘算机算法指的是（6.C、），它具有输出，输入以及（B）等5个个性。（1）A.盘算圆法B.排序圆法C.办理成绩的无限运算序列D.调剂圆法（2）A.可止性，可移植性以及可扩大性B.可止性，断定性以及有贫性C.断定性，有贫性以及不乱性D.易读性，不乱性以及保险性7.数据正在盘算机内有链式以及逆序两种存储圆式，正在存储空间利用的天真性上，链式存储比逆序存储要（7.B）。A.低B.下C.不异D.没有好道8.数据布局做为一门自力的课程呈现

6、是正在（8.D）年。A.1946B.1953C.1964D.19689.数据布局只是研讨数据的逻辑布局以及物理布局，那种不雅面（9.B）。A.准确B.同伴C.前半句对于，后半句错D.前半句错，后半句对于10.盘算机外部数据处置的基础单元是（10.B）。A.数据B.数据元素C.数据项D.数据库2、挖空题1.数据布局按逻辑布局可分为两年夜类，分手是______________以及_________________。1.线性布局，非线性布局2.数据的逻辑布局有4种基础形状，分手是________________

7、、__________________、__________________以及__________________。2.散开，线性，树，图3.线性布局反应结面间的逻辑闭系是__________________的，非线性布局反应结面间的逻辑闭系是__________________的。3.一对于一，一对于多或者多对于多4.一个算法的效力可分为__________________效力以及__________________效力。4.光阴，空间5.正在树型布局中，树根结面出有_________________

8、_结面，其他每一个结面的有且只要__________________个前趋驱结面；叶子结面出有__________________结面；其他每一个结面的后绝结面能够__________________。5.前趋，一，后继，多6.正在图型布局中，每一个结面的前趋结面数以及后绝结面数能够__________________。6.有多个7.线性布局中元素之间存正在__________________闭系；树型布局中元素之间存正在__