资源描述：
《算法与数据结构题库及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、单项选择题1某算法的时间复杂度是O(n2)，表明该算法（）。A问题规模是n2B问题规模与n2成正比C执行时间等于n2D执行时间与n2成正比2、关于数据结构的描述，不正确的是（）。A数据结构相同，对应的存储结构也相同。B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。C数据结构操作的实现与存储结构有关。D定义逻辑结构时可不考虑存储结构。3、按排序策略分来，起泡排序属于（）。A插入排序B选择排序C交换排序D归并排序4、利用双向链表作线性表的存储结构的优点是（）。A便于进行插入和删除的操作B提高按关系查找数据元素的速度C节省空间D便于销毁结构释
2、放空间5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。A1,2,3,4B1,3,2,4C1,4,2,3D4,3,2,16、Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。A按长度递减的顺序求出图的某顶点到其余顶点的最短路径B按长度递增的顺序求出图的某顶点到其余顶点的最短路径C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径D通过广度优先遍历求出图的某顶点到其余顶点的最短路径7、字符串可定义为n（n≥0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。A集合B数列C序列D聚合8、在二维数组A[9
3、][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。ASA+141BSA+144CSA+222DSA+2559、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。A2B3C4D510.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。A.n+1B.nC.n-1D.n-211.一个递归算法必须包括__________。A.递归部分B.结束条件和递归部分C.迭代部分D.结束条件和
4、迭代部分12.从逻辑上看可以把数据结构分为__________两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构13、若在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。AO(n)BO(1)CO(n2)DO(log2n)14.采用顺序搜素方式搜索长度为n的线性表时，在等概率情况下，搜索成功时的平均搜索长度为__________。A.nB.n/2C.(n+1)/2D.(n-1)/215、非空的循环单链表first的链尾结点（由p所指向）满足（）。Ap->link==NULL;BP==NULL;第7页
5、，共7页Cp->link==first;Dp==first;16、用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为（）。ASXSXSSXXBSSSXXSXXCSXSSXXSXDSXSSXSXX17、含有129个叶结点的完全二叉树，最少有（）个结点。A254B255C257D25818、一个有向图G的邻接表存储如图（1）所示，现按深度优先搜索方式从顶点A出发执行一次遍历，所得的顶点序列是（）。A1,2,3,4,5B1,2,3,5,4C1,2,4,5,3D1,2,5,3,419、树最合适用来表示
6、（）。A有序数据元素B元素之间具有分支层次关系的数据C无序数据元素D元素之间无联系的数据20、一棵有124个叶结点的完全二叉树最少有（）个结点。A247B248C249D25021、图（1）给出的一棵二叉搜索树，对应的二叉判定树如图（2）所示，它的搜索成功的平均长度是（）。A21/7B28/7C15/6D16/6图（1）二叉搜索树图（2）二叉判定树23、对5个不同的数据元素进行直接插入排序，最大需要进行（）次比较。A8B10C15D2524、将一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行的对角元素A
7、[i][i]在B中的存放位置是（）。A(i+3)*i/2B(i+1)*i/2C(2n-i+1)*i/2D(2n-i-1)*i/225、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的深度是（）。A2B3C4D526、顺序搜索法适合于存储结构为（）的线性表。A散列存储B顺序存储或链式存储C压缩存储D索引存储27、采用折半搜索方式搜索一个长度为n的有序顺序表时，其平均搜索长度为（）。AO(n)BO(log2n)CO(n2)DO(nlog2n)28、n个结点的线索二叉树中，线索的
8、数目是（）。An-1Bn+1C2nD2n-129、若
