数据结构与算法分析复习资料

《数据结构与算法分析复习资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、40/40数据结构复习资料总结2012-05T.H.C2012-06-05MODIFY目录1.第一章31.1基本概念题31.2逻辑结构题31.3物理结构题31.4算法特性题42.线性表42.1基本概念题42.2顺序表42.3链表概念题52.4链表指针题52.5链表编程题63.栈和队列83.1栈的概念题83.2进栈出栈题83.3链栈指针题93.4链栈编程题93.5队列概念题103.6链队指针题103.7链队编程题113.8循环队列题124.串124.1串的基本概念124.2串函数134.5串的编程题135

2、.数组和广义表145.1数组坐标换算题145.2矩阵题145.3广义表156.树和二叉树156.1二叉树的概念性质156.2二叉树的链式存储176.3树的遍历概念题176.4树的遍历操作题186.5树的遍历编程题206.6哈夫曼树216.7树的遍历反过来做的题227.图237.1图的基本概念237.2图的遍历2440/407.3图的最小生成树247.5图的连通性258.查找258.1顺序查找258.2折半查找258.3二叉排序树268.4二叉判定树288.5哈希函数298.6折半查找编程题298.7二叉

3、排序树编程题309.排序319.1排序基本概念319.2直接插入排序319.3折半插入排序329.4交换排序之冒泡排序329.5交换排序之快速排序339.6选择排序之直接选择排序349.7选择排序之堆排序359.8选择排序之归并排序389.9排序稳定性题3840/401.第一章1.1基本概念题1．线性结构中数据元素的位置之间存在（）的关系。【B】A．一对多B．一对一C．多对多D．每一个元素都有一个直接前驱和一个直接后继注：D选不全的，第一个元素就木有前驱，最后一个元素就木有后继。2．数据结构中，与所使用

4、的计算机无关的是数据的（）结构。【D】A．物理B．存储C．逻辑与物理D．逻辑3．结构中的数据元素存在一对一的关系称为________结构。【线性】4．数据元素是数据的基本单位，它（）。【C】A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型5．一种逻辑结构（）存储结构。【A】A．可以有不同的B．只能有唯一的C．的数据元素在计算机中的表示称为D．的数据元素之间的关系称为1.2逻辑结构题1．通常数据的逻辑结构包括_____、_____、

5、_____、_____四种类型。【集合；线性；树形；图状】2．通常可以把一本含有不同章节的书的目录结构抽象成_____结构。【树形】3．通常可以把某城市中各公交站点间的线路图抽象成_____结构。【图状】4．结构中的数据元素存在多对多的关系称为________结构。【图状（网状）】5．结构中的数据元素存在一对多的关系称为________结构。【树形】6．结构中的数据元素存在一对一的关系称为________结构。【线性】1.3物理结构题1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称称为物理（）结

6、构。【存储】2．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为________结构。（物理（存储））40/401.4算法特性题1．以下特征中，（）不是算法的特性。【C】A．有穷性B．确定性C．有0个或多个输出D．可行性2．算法的时间复杂度与（）有关。【D】A．所使用的计算机B．与计算机的操作系统C．与数据结构D．与算法本身3．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和O(n)。【n-1】2.线性表2.1基本概念题1．针

7、对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。【B】A．单链表B．顺序表C．单循环链表D．双链表2.2顺序表1．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）。【A】A．n-i+1B．n-iC．n-i-1D．i注：元素要插入到i的位置，不动的是前面i-1个元素，总元素有n个，要移动的元素个数是：n-(i-1)即：n-i+12.设顺序存储的线性表长度为n，对于插入操作，设插入位置是等概率的，则插入一个元素平

8、均移动元素的次数为（）。【A】A．n/2B．nC．n-1D．n-i+13.设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（）。【A】A．(n+1)/2B．nC．2nD．n-i4．线性表的顺序结构中，（）。【C】A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的40/40C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高2.3链表概念题1．链表所具