《算法与数据结构题库与答案》由会员分享，可在线阅读，更多相关《算法与数据结构题库与答案（12页珍藏版）》请在金锄头文库上搜索。
1、)。n2成正比n2成正比一、单项选择题1某算法的时间复杂度是A问题规模是n2C执行时间等于n2O(n2 )，表明该算法(B问题规模与D执行时间与2、关于数据结构的描述不正确的是()。数据结构相同，对应的存储结构也相同。数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。数据结构操作的实现与存储结构有关。D3、4、定义逻辑结构时可不考虑存储结构。按排序策略分来，起泡排序属于( )。A插入排序B 选择排序C交换排序利用双向链表作线性表的存储结构的优点是(D归并排序)。A便于进行插入和删除的操作C节省空间D一个队列的进队顺序为1,2,3,4A 1,2,3,4B 1,3,2,4B提高按关系
2、查找数据元素的速度便于销毁结构释放空间则该队列可能的输出序列是()。C 1,4,2,3D 4,3,2,1Dijkstra 算法是按()方法求出图中从某顶点到其余顶点最短路径的。按长度递减的顺序求出图的某顶点到其余顶点的最短路径按长度递增的顺序求出图的某顶点到其余顶点的最短路径通过深度优先遍历求出图中从某顶点到其余顶点的所有路径通过广度优先遍历求出图的某顶点到其余顶点的最短路径n ( nN 0 )个字符的有限()。其中，n是字符串的长度，表明字符串D字符串可定义为 中字符的个数。A集合B数列C序列D聚合8、 在二维数组 A910中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放。在这
3、种情况下，元素A85的起始地址为()。A SA+141B SA+144C SA+222D SA+2559、 已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(),(),(e,(f,g),h) 的长度是(A2对于具有7、10.，则它)。n(n1)A. n+1B3个顶点的强连通图B. n C. n-1C4D5其有向边条数至少有D. n-211.12.一个递归算法必须包括A.递归部分B .结束条件和递归部分从逻辑上看可以把数据结构分为C.迭代部分D.结束条件和迭代部分 _两大类。A.动态结构、静态结构B.顺序结构、链式结构C .线性结构、非线性结构D.初等结构、构造型结构
4、若在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为(A O(n)B O(1)C O(n 2) D O(log 2n)14. 采用顺序搜素方式搜索长度为n的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 。A. n B. n/215、 非空的循环单链表first13、A p-link=NULL;C . (n+1)/2 D. (n-1)/2的链尾结点(由p所指向)满足(B P=NULL;C p-link=first;D p=first;16、 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234,为了得到1342的出栈顺序，相应的S和X的操作序列为()。A SXSXSSX
5、XB SSSXXSXXC SXSSXXSXD SXSSXSXX17、 含有129个叶结点的完全二叉树，最少有()个结点。A 254B 255C 257D 258现按深度优先搜索方式从顶点A出发执行18、一个有向图G的邻接表存储如图(1)所示， 一次遍历，所得的顶点序列是()。19、20、21、A 1,2,3,4,5树最合适用来表示(A有序数据元素C无序数据元素一棵有A 247图(1)B 1,2,3,5,4)。B元素之间具有分支层次关系的数据D元素之间无联系的数据C 1,2,4,5,3D 1,2,5,3,4124个叶结点的完全二叉树最少有( )个结点。C 249D 250对应的二叉判定树如图(2
6、)所示，它的搜索成功的平B 248给出的一棵二叉搜索树均长度是(A 21/7)。B 28/7C 15/6D 16/6r；i-2)二叉判定树图(1)二叉搜索树图(23、对5个不同的数据元素进行直接插入排序A8B10C15最大需要进行(D25)次比较。24、将一个n Xn的对称矩阵 A的下三角部分按行存放在一个一维数组B中，A00存放在B0中，那么第i行的对角元素 Aii在B中的存放位置是(A (i+3)*i/2B (i+1)*i/2C (2n-i+1)*i/225、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(),(),(e,(f,g),h)它的深度是()。A2)
7、。D (2n-i-1)*i/2，则B3D526、 顺序搜索法适合于存储结构为()的线性表。A散列存储B顺序存储或链式存储C压缩存储D索引存储27、 采用折半搜索方式搜索一个长度为n的有序顺序表时，其平均搜索长度为()A O(n)B O(log2n)C O(n 2)D O(nlog 2n)28、 n个结点的线索二叉树中，线索的数目是()。A n-1B n+1C 2nD 2n-129、 若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序 后的结果，则该排序方法只能是( )。A插入排序B 选择排序 C交换排序 D归并排序30、 为了增加内存空间的利用率和减
8、少溢出的可能，在两个栈共享一片连续的存储空间时，应将两个栈的栈顶分别设在这片存储空间的两端，当()时才产生上溢。A两个栈的栈顶同时到达栈空间的中心点B其中一个栈的栈顶到达栈空间的中心点C两个栈的栈顶在栈空间的某一位置相遇D两个栈的栈顶相加超过了栈空间的最大容量31、 设一棵二叉树的中序序列为badce，后序遍历为bdeca，则该二叉树前序遍历的顺序是()。A adbec32、图的简单路径是指(A权值 B顶点33、用n个权值构造出来的A 2n-1B decabC debacB 2n)不重复的路径。C边Huffman树共有(C 2n+1D abcdeD边与顶点均不重复)个结点。D n+134、在如
9、图(2)所示的AVL树中插入关键码48，得到了一棵新的AVL树，在这棵新的 AVL树中，关键码37所在结点的左右子女结点中保存的关键码分别是()。A 13,48B 24,48C 24,53D 24,90二、填空题算法效率的度量分为_ 事后测量算法是一个有穷的指令集，输出、确定性、1、事前估2、 入、3、4、一个抽象数据类型ADT包括队列的插入操作是在 队尾栈又称为先进后出对称矩阵的行数和列数两种。它为解决某一特定任务规定了一个运算序列。它应当具有输有穷性可行性等特性。和 对象两个部分。数据操作进行，删除操作是在队头 进行。的线性表，队列又称为先进先出线性表。相等且以主对角线为对称轴， 因此只要
10、存储它的上三角部分或者下三角部分即可。7、利用三元组表存放稀疏矩阵中的非零元素，零元的行号、列号和非零元素的8、广义表 A(a,b,c),(d,e,f)9、广义表 A(a,b,c),(d,e,f)10、在一棵有n个结点的二叉树中，则在三元组表中每个三元组中应记录相应非值。的表头是(a,b,c)的表尾是(d,e,f)若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最小高度为 _ log2 n 1，其叶节点数为 n2+1。11、 在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为 二，其叶节点数为 1。12、
11、已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，当用折半搜索法搜索值18的元素时，搜索成功的数据比较次数为 4(n+1)/213、采用顺序搜索方式搜索长度为 n的线性表时，平均搜索长度为14、对于一个具有n个顶点和e条边的无向图进行遍历，若采用邻接矩阵表示，则时间复杂度为 O(n 2)，若采用邻接表表示，则时间复杂度为O(n+e) 。15、 对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是 n 2，矩阵中的非零元个数为2e 。花3次从无序表中挑选一个最小或者最大元素，把它交换到有序表的一端，此种排序方法叫做 交换 排序。17、对n
12、个元素的序列进行排序时，如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需要进行n(n-1)/2 次元素值的比较， n(n-1)/2次元素值的交换。18、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 插入 插入 排序。19、对n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需要进行n-1次元素值的比较，0 次元素值的交换。三、判断题1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按照使用需要建立的。错2、数据结构是指相互之间存在一种或多种关系的数据元素的全体。对3、根据队列的先进先出的特性，最后进队列的元素最后出队列
13、。对4、在顺序栈中元素是按照其值的大小有序存放的。错5、栈底元素是不能删除的。错6、在队列中，n个元素的进队列顺序和出队列顺序总是一致的。对7、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。错8、广义表是线性表的推广，但它不是一种线性结构。对9、二维数组可以视为数组元素为一维数组的一维数组。因此，二维数组是线性结构。错10、 有n个整数存放在一维数组An中，在进行顺序搜索时，无论这n个整数的排列是否有序，其平均搜索长度都相同。错11、 邻接矩阵适用于稠密图(边数接近于顶点数的平方)，邻接表适用于稀疏图(边数远小 于顶点数的平方)。对12、 对n个顶点的连通图G来说，如
14、果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。错13、希尔排序、简单选择排序都是不稳定的排序方法。错14、如果一个二叉树的结点，或者两棵子树都空，或者两棵子树都非空，则此二叉树称为完全二叉树。错15、在二叉搜索树中，任一结点所具有的关键码值都大于它的左子女(如果存在)的关键 码值，同时小于其右子女(如果存在)的关键码值。对16、 具有n个顶点的无向图最多有n(n-1)条边，最少有 n-1条边。错17、最小生成树是指边数最少的生成树。错四、简答与计算题1、什么是数据结构？有关数据结构的讨论涉及哪三个方面？2、 什么是算法，算法的5个特性是什么？3、 已知如图(3)所示的有向图，请利用Kruskal算法求出最小生成树。图（3）4、如图（3 ）所示的有向图，请给出该图的邻接矩阵和邻接表。图（3）5、已知一棵二叉树的前序
