算法与数据结构题库及答案

一、单项选择题1某算法的时间复杂度是O(n2)，表明该算法()。A问题规模是n2 B问题规模与n2成正比C执行时间等于n2 D执行时间与n2成正比2、关于数据结构的描述，不正确的是()。A数据结构相同，对应的存储结构也相同。B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。C数据结构操作的实现与存储结构有关。D定义逻辑结构时可不考虑存储结构。3、按排序策略分来，起泡排序属于()。A插入排序B选择排序C交换排序D归并排序4、利用双向链表作线性表的存储结构的优点是()。A便于进行插入和删除的操作B提高按关系查找数据元素的速度C节省空间D便于销毁结构释放空间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(n20)个字符的有限()。其中，n是字符串的长度，表明字符串中字符的个数。A集合B数列C序列D聚合8、 在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为()。ASA+141 BSA+144CSA+222DSA+2559、 已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),则它的长度是()。TOC\o"1-5"\h\zA2 B3 C4 D510、 对于具有n(n>1)个顶点的强连通图，其有向边条数至少有 。A.n+1B.n C.n-1D.n-211、 一个递归算法必须包括 。A.递归部分B.结束条件和递归部分C.迭代部分D.结束条件和迭代部分12、 从逻辑上看可以把数据结构分为 两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构13、 若在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为()。AO(n) BO(1) CO(n2) DO(logn)采用顺序搜素方式搜索长度为n的线性表时，在等概率情况下，搜索成功时的平均搜索长度为 。A.n B.n/2 C.(n+1)/2 D.(n-1)/215、 非空的循环单链表first的链尾结点(由p所指向)满足()。Ap->link==NULL; BP==NULL;

Cp->link==first;Dp==first;16、 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为()。ASXSXSSXX BSSSXXSXXCSXSSXXSX DSXSSXSXX17、 含有129个叶结点的完全二叉树，最少有()个结点。A254 B255 C257 D25818、一个有向图G的邻接表存储如图(1)所示，现按深度优先搜索方式从顶点A出发执行一次遍历，所得的顶点序列是()。A1,2,3,4,5 B1,2,3,5,4 C1,2,4,5,3 D1,2,5,3,419、 树最合适用来表示()。A有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D元素之间无联系的数据20、 一棵有124个叶结点的完全二叉树最少有()个结点。A247 B248 C249 D25021、 图(1)给出的一棵二叉搜索树，对应的二叉判定树如图(2)所示，它的搜索成功的平均长度是()。A21/7B28/7CA21/7B28/7C15/6D16/6图(1图(1)二叉搜索树图(2)二叉判定树23、对5个不同的数据元素进行直接插入排序，最大需要进行()次比较。A8 B10 C15 D2524、将一个nXn的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行的对角元素A[i][i]在B中的存放位置是()。A(i+3)*i/2B(i+1)*i/2 C(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)),则它的深度是()。A2 B3 C426、 顺序搜索法适合于存储结构为()的线性表。A散列存储B顺序存储或链式存储C压缩存储D索引存储27、 采用折半搜索方式搜索一个长度为n的有序顺序表时，其平均搜索长度为()。AO(n)BO(logn)CO(n2) DO(nlogn)28、n个结点的线索二叉树中，线索的数目是()。 2An-1 Bn+1 C2n D2n-129、 若数据元素序列｛11,12,13,7,8,9,23,4,5｝是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是()。A插入排序B选择排序C交换排序D归并排序

30、为了增加内存空间的利用率和减少溢出的可能，在两个栈共享一片连续的存储空间时，应将两个栈的栈顶分别设在这片存储空间的两端，当()时才产生上溢。A两个栈的栈顶同时到达栈空间的中心点B其中一个栈的栈顶到达栈空间的中心点C两个栈的栈顶在栈空间的某一位置相遇D两个栈的栈顶相加超过了栈空间的最大容量31、设一棵二叉树的中序序列为badce,后序遍历为bdeca,则该二叉树前序遍历的顺序是()。Aadbec Bdecab Cdebac Dabcde32、 图的简单路径是指()不重复的路径。A权值B顶点C边D边与顶点均不重复33、 用n个权值构造出来的Huffman树共有()个结点。A2n-1 B2n C2n+1 Dn+134、在如图(2)所示的AVL树中插入关键码48,得到了一棵新的AVL树，在这棵新的AVL树中,关键码3734、在如图(2)所示的AVL树中插入关键码48,得到了一棵新的AVL树，在这棵新的AVL树中,关键码37所在结点的左右子女结点中保存的关键码分别是(A13,48 B24,48）。D24,90C24,53图(1)14小题的邻接表15小题的AVL树图2)ABCDE251\3141\二、填空题1、算法效率的度量分为事后测量和事前估两种。2、 算法是一个有穷的指令集,它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、确定性、 有穷性 可行性等特性。3、一个抽象数据类型ADT包括. 数据操作 和对象 两个部分。4、队列的插入操作是在队尾进行，删除操作是在 队头进行。5、栈又称为 先进后岀 的线性表，队列又称为 先进先岀线性表。6、对称矩阵的行数和列数 相等 且以主对角线为对称轴，因此只要存储它的上三角部分或者下三角部分即可。7、 利用三元组表存放稀疏矩阵中的非零元素,则在三元组表中每个三元组中应记录相应非TOC\o"1-5"\h\z零元的行号、列号和非零元素的—值 。8、广义表A((a,b,c),(d,e,f))的表头是 (a,b,c) 。9、广义表A((a,b,c),(d,e,f))的表尾是 ((d,e,f))10、 在一棵有n个结点的二叉树中，若度为2的结点数为n2,度为1的结点数为n1,度为0的结点数为n0,则树的最小高度为—^先“」+1 ，其叶节点数为—n2+1 。11、 在一棵有n个结点的二叉树中，若度为2的结点数为n2,度为1的结点数为n1,度为0的结点数为n0,则树的最大高度为 n ，其叶节点数为 1 。12、 已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，当用折半搜索法搜索值18TOC\o"1-5"\h\z的元素时，搜索成功的数据比较次数为4 。13、采用顺序搜索方式搜索长度为n的线性表时，平均搜索长度为 （n+l）/2 。14、 对于一个具有n个顶点和e条边的无向图进行遍历，若采用邻接矩阵表示，则时间复杂度为 0（e），若采用邻接表表示，则时间复杂度为O（n+e）。15、 对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是—n2 ,矩阵中的非零元个数为 2e。16、 每次从无序表中挑选一个最小或者最大兀素，把它交换到有序表的一端，此种排序方法叫彳 排序。17、 对n个元素的序列进行排序时，如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需要进行n（n-1）/2 次元素值的比较， n（n-1）/2次元素值的交换。18、 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做插入插入排序。19、 对n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需要进行n-1 次元素值的比较， 0次元素值的交换。三、判断题1、 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按照使用需要建立的。错2、 数据结构是指相互之间存在一种或多种关系的数据元素的全体。对3、 根据队列的先进先出的特性，最后进队列的元素最后出队列。对4、 在顺序栈中元素是按照其值的大小有序存放的。错5、 栈底元素是不能删除的。错6、 在队列中，n个元素的进队列顺序和出队列顺序总是一致的。对7、 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。错8、 广义表是线性表的推广，但它不是一种线性结构。对9、 二维数组可以视为数组元素为一维数组的一维数组。因此，二维数组是线性结构。错10、 有n个整数存放在一维数组A[n]中，在进行顺序搜索时，无论这n个整数的排列是否有序，其平均搜索长度都相同。错11、 邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。对12、 对n个顶点的连通图G来说，如果其中的某个子图有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、已知一棵二叉树的前序遍历结果是ABECDFGHIJ,中序遍历结果是EBCDAFHIGJ,试画出这6、给定权值集合｛15,03,14,02,06,09,16,17｝，构造相应的huffman树，并计算它的带权外部路径长度。7、设串s为“abcabaa”，试计算其next数组的值。j0123456rabcabaanext[j]-10001218、利用广义表的head和tail操作写出函数表达式，把以下各题中单元素banana从广义表中分离出来。L1(apple,pear,banana,orange)L2((apple,pear),(banana,orange))L3(((apple),(pear),(banana),(orange)))L4((((apple),pear),banana),orange)L5(apple,(pear,(banana),orange))Head(Tail(Tail(Ll)))(l分)Head(Head(Tail(L2)))(1分)Head(Head(Tail(Tail(Head(L3)))))(1分)Head(Tail(Head(L4)))(1分)Head(Head(Tail(Head(Tail(L6)))))(1分)9、 设有序顺序表中的元素依次为17,154,170,275,503,509,512,553,612,677,765,897,908。试画出对其进行折半搜索时的判定树，并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。搜索成功的平均搜索长度为45/14（1分）搜索不成功的平均搜索长度为59/14（1分）10、已知一个待排序的关键字序列为｛56，36，22，86，72，10，28，48｝，请写出快速排序每一趟排序的结果（写出过程）。（5分）第1趟排序结果：48,36,22,28,10,56,72,86第2趟排序结果：10,36,22,28,48,56,72,86第3趟排序结果：10,36,22,28,48,56,72,86第4趟排序结果：10,22,28,36,48,56,72,86第5趟排序结果：10,22,28,36,48,56,72,8611、已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94,50时的比较次数。元素值345658639450比较次数21344412、已知一