数据结构与算法-5单元练习题及答案.pdf
***
单元练习1
一．判断题〔以下各题，正确的请在前面的括号内打√；错误的打╳〕
〔√〕〔1〕数据的逻辑构造与数据元素本身的内容和形式无关。
〔√〕〔2〕一个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体。
〔ㄨ〕〔3〕数据元素是数据的最小单位。
〔ㄨ〕〔4〕数据的逻辑构造和数据的存储构造是一样的。
〔ㄨ〕〔5〕程序和算法原那么上没有区别，所以在讨论数据构造时可以通用。
〔√〕〔6〕从逻辑关系上讲，数据构造主要分为线性构造和非线性构造两类。
〔√〕〔7〕数据的存储构造是数据的逻辑构造的存储映像。
〔√〕〔8〕数据的物理构造是指数据在计算机内实际的存储形式。
〔ㄨ〕〔9〕数据的逻辑构造是依赖于计算机的。
〔√〕〔10〕算法是对解题方法和步骤的描绘。
二．填空题
（1）数据有逻辑构造和存储构造两种构造。
（2）数据逻辑构造除了集合以外，还包括：线性构造、树形构造和图形构造。
（3）数据构造按逻辑构造可分为两大类，它们是线性构造和非线性构造。
（4）树形构造和图形构造合称为非线性构造。
（5）在树形构造中，除了树根结点以外，其余每个结点只有1个前趋结点。
（6）在图形构造中，每个结点的前趋结点数和后续结点数可以任意多个。
（7）数据的存储构造又叫物理构造。
（8）数据的存储构造形式包括：顺序存储、链式存储、索引存储和散列存储。
（9）线性构造中的元素之间存在一对一的关系。
（10）树形构造构造中的元素之间存在一对多的关系，
（11）图形构造的元素之间存在多对多的关系。
（12）数据构造主要研究数据的逻辑构造、存储构造和算法〔或运算〕三个方面的内容。
（13）数据构造被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。
（14）算法是一个有穷指令的集合。
（15）算法效率的度量可以分为事先估算法和事后统计法。
（16）一个算法的时间复杂性是算法输入规模的函数。
（17）算法的空间复杂度是指该算法所消耗的存储空间，它是该算法求解问题规模n的函数。
（18）假设一个算法中的语句频度之和为T〔n〕=6n+3nlogn，那么算法的时间复杂度为O〔nlogn〕。
22
22
（19）假设一个算法中的语句频度之和为T〔n〕=3n+nlogn+n，那么算法的时间复杂度为O〔n〕。
2
〔20〕数据构造是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算
的学科。
三．选择题
〔1〕数据构造通常是研究数据的〔A〕及它们之间的互相联络。
A.存储构造和逻辑构造B.存储和抽象C.联络和抽象D.联络与逻辑
〔2〕在逻辑上可以把数据构造分成：〔C〕。
A.动态构造和静态构造B.紧凑构造和非紧凑构造
C.线性构造和非线性构造D.内部构造和外部构造
〔3〕数据在计算机存储器内表示时，物理地址和逻辑地址一样并且是连续的，称之为〔C〕。
1
***
A.存储构造B.逻辑构造C.顺序存储构造D.链式存储构造
〔4〕非线性构造中的每个结点〔D〕。
A.无直接前趋结点
B.无直接后继结点
C.只有一个直接前趋结点和一个直接后继结点
D.可能有多个直接前趋结点和多个直接后继结点