【数据结构习题集附答案】.pdfVIP

【数据结构习题集附答案】

数据结构习题集附答案第一章绪论一、选择题1.组成数据

的基本单位是（）A．数据项B．数据类型C．数据元素D．数据

变量2.数据结构是研究数据的（）以及它们之间的相互关系。

A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，

逻辑结构D．抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把

数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结

构和非线性结构D．内部结构和外部结构4.数据结构是一门研究非

数值计算的程序设计问题中计算机的（①）以及它们之间的（②）

和运算等的学科。

①A．数据元素B．计算方法C．逻辑存储D．数据映像②A．结

构B．关系C．运算D．算法5.算法分析的两个主要方面是（）。

A．数据复杂性和程序复杂性B．正确性和简明性C．可读性和

简明性D．空间复杂性和时间复杂性6.算法分析的目的是（）。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系

C．分析算法的效率以求改进D．分析算法的易懂性和文档性7.计算

机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。

①A．计算方法B．排序方法C．解决问题的有限运算序列D．调

度方法②A．可执行性，可移植性和可扩充性B．可行性，确定性和

有穷性C．确定性、有穷性和稳定性D．易读性、稳定性和安全性二、

判断题1.数据的机内表示称为数据的存储结构。（）2.算法就是程

序。（）3.数据元素是数据的最小单位。（）4.算法的五个特性为：

有穷性、输入、输出、完成性和确定性。（）5.算法的时间复杂度取

决于问题的规模和待处理数据的初态。（）三、填空题1.数据逻辑

结构包括________、________、________和________四种类型,其中树形结

构和图形结构合称为________。

2.在线性结构中,第一个结点________前驱结点,其余每个结点有且

只有________个前驱结点；

最后一个结点________后续结点,其余每个结点有且只有________

个后续结点。

3.在树形结构中,树根结点没有________结点,其余每个结点有且只

有________个前驱结点；

叶子结点没有________结点,其余每个结点的后续结点可以

________。

4.在图形结构中,每个结点的前驱结点数和后续结点数可以

________。

5.线性结构中元素之间存在________关系,树形结构中元素之间存

在________关系,图形结构中元素之间存在________关系。

6.算法的五个重要特性是________、________、________、________、

________。

7.数据结构的三要素是指________、________和________。

8.链式存储结构与顺序存储结构相比较,主要优点是

________________________________。

9.设有一批数据元素,为了最快的存储某元素,数据结构宜用

________结构,为了方便插入一个元素,数据结构宜用________结构。

四、算法分析题1.求下列算法段的语句频度及时间复杂度

for(i=1;ii++)for(j=1;jj++)x=x+1;分析：该算法为一个二重循环，

执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有

关，因些，时间频度T(n)=1+2+3+…+n=n*(n+1)/2有

1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2),即Ｔ(n)与n2数量级

相同。

2.分析下列算法段的时间频度及时间复杂度for（i=1;ii++）for

(j=1;jj++)for(k=1;kk++)x=i+j-k;分析算法规律可知时间频度

T(n)=1+(1+2)+(