练习题1-6章(含答案).doc

《练习题1-6章(含答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题练习第一章1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（c）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（1c），它必须具备（2b）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4．一个算法应该是（b）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5、下面属于逻辑结构的是（c）A顺序表B哈希表C有序表D单链表6、某算法的

2、时间复杂度为O(n2)，表明该算法的（c）A问题规模是n2B执行时间等于n2C执行时间与n2成正比D问题规模与n2成正比7、下面关于算法说法错误的是（c）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8．从逻辑上可以把数据结构分为（c）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构9．以下与数据的存储结构无关的术语是（d）。A．循环队列B.链表C.哈希表D.栈10．以下数据结构中，哪一个是线性结构（d）？A．广义表B

3、.二叉树C.稀疏矩阵D.串11．以下那一个术语与数据的存储结构无关？（a）A．栈B.哈希表C.线索树D.双向链表12．在下面的程序段中，对x的赋值语句的频度为（c）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)14．以下数据结构中，（a）是非线性数据结构A．树B．字符串C．队D．栈15.下列数据中，（c）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆16．连续存储设计时，存储单元的地址（a）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续17．以下属于逻辑结构的是（c

4、）。A．顺序表B.哈希表C.有序表D.单链表二、问答：1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4.回答问题（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明

5、之。5．评价一个好的算法，您是从哪几方面来考虑的？第二章1．下述哪一条是顺序存储结构的优点？（a）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（b）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（c）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的

6、元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（d）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（d）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（c）(1

7、<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)8.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（c）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)9．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（c）A．O（i）B．O（1）C．O（n）D．O（i-1）16．非空的循环单链表head的尾结点p↑满足（a）。A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循环链表H的尾结点P的特点是（a）。A．P^.NEXT:=HB