算法与数据结构复习提纲及答案

《算法与数据结构复习提纲及答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、概论部分2.算法的时间复杂度取决于（C）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（1C），它必须具备（2A）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4．一个算法应该是（B）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5.下面关于算法说法错误的是（D）A．算法最终必须由计算机程序实现B.为解决某问题的算法同

2、为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（C）(1）算法原地工作的含义是指不需要任何额外的辅助空间n（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)7．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．

3、线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D）。A．循环队列B.链表C.哈希表D.栈9．以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串10．以下那一个术语与数据的存储结构无关？（A）A．栈B.哈希表C.线索树D.双向链表以下哪个数据结构不是多型数据类型（D）A．栈B．广义表C．有向图D．字符串11．以下数据结构中，（A）是非线性数据结构A．树B．字符串C．队D．栈12.下列数据中，（C）是非线性数据结构。A．栈B.队列C.完全二叉树D

4、.堆13．连续存储设计时，存储单元的地址（A）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续14．以下属于逻辑结构的是（C）。A．顺序表B.哈希表C.有序表D.单链表15.对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形结构，__图形结构_四种16.数据的逻辑结构是指数据的组织形式。17．一个数据结构在计算机中表示称为存储结构18.数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度19.数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这

5、1种结构定义相应的_操作_，设计出相应的算法_。20.一个算法具有5个特性:确定性、有穷性、可行性，有零个或多个输入、有一个或多个输出。n21.有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的时间复2杂度为T2=O(n)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。二、线性表部分1．下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺

6、序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（C）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除

7、第一个元素，则采用（D）存储方式最节省运算时间。【南开大学2000一、3】A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（D）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表8.静态链表中指针表示的是（C）.A．内存地

8、址B．数组下标C．下一元素地址D．左、右孩子地址9.链表不具有的特点是（B）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10.下面的叙述不正确的是（BC）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同