数据结构练习.docx

一、单项选择题(每小题2分，共20分)(1)以下数据结构中哪一个是线性结构？()A)有向图B)队列C)线索二叉树D)B树(2)在一个单链表HL中，若要在当前由指针P指向的结点后面插入一个由q指向的结点，则执行如下()语句序列。A)p=q;p->next=q;B)p->next=q;q->next=p;C)p->next=q->next;p=q;D)q->next=p->ncxt;p->next=q;(3)()不是队列的基本运算。A)在队列第i个元素之后插入一个元素B)从队头删除一个元素C)判断一个队列是否为空D)读取队头元素的值(4)字符A、B、C挨次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成()个不同的字符串。A)14B)5C)6D)8(5)由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。A)11B)35C)19D)53以下6-8题基于下图：(6)该二叉树结点的前序遍历的序列为()oA) E、G、F、A、C、D、BB)E、A、G、C、F、B、DC) E、A、C、B、D、G、FD)E、G、A、C、D、F、B(7)该二叉树结点的中序遍历的序列为()。D) A、B、C、D、E、G、FB)E、A、G、C、F、B、DC)E、A、C、B、D、G、FD)B、D、C、A、F、G、E(8)该二叉树的按层遍历的序列为()oA)E、G、F、A、C、D、BB)E、A、C、B、D、G、FC)E、A、G、C、F、B、DD)E、G、A、C、D、F、B(9)下面关于图的存储的叙述中正确的是()。A)用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B)用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C)用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D)用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关(10)设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果？()A)a,g,h,m,n,p,q,x,zB)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)h,g,m,p,a,n,q,x,Z一、单项选择题(1) B(2)D(3)A(4)B(5)B(6) C(7)A(8)C(9)B(10)B一、单项选择题(每小题2分，共20分)(1)设Huffman树的叶子结点数为m,则结点总数为()。A)2mB)2m-1C)2m+lD)m+1(2)若顺序存储的循环队列的QUCUeMaXSiZe=n,则该队列最多可存储()个元素。A)nB)n-lC)n+1D)不确定(3)下述哪一条是顺序存储方式的优点？()A)存储密度大B)插入和删除运算方便C)获取符合某种条件的元素方便D)查找运算速度快(4)设有一个二维数组Amn,假设A00存放位置在600(10),A33存放位置在678(10),每一个元素占一个空间，问A23(10)存放在什么位置？(脚注(IO)表示用10进制表示，m>3)(A)658B)648C)633D)653(5)下列关于二叉树遍历的叙述中，正确的是()oA)若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B)若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C)若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D)若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点(6) k层二叉树的结点总数最多为()。A)2k-1B)2k+lC)2K-1D)2k-1(7)对线性表进行二分法查找，其前提条件是()。A)线性表以链接方式存储，并且按关键码值排好序B)线性表以顺序方式存储，并且按关键码值的检索频率排好序C)线性表以顺序方式存储，并且按关键码值排好序D)线性表以链接方式存储，并且按关键码值的检索频率排好序(8)对n个记录进行堆排序，所需要的辅助存储空间为()。)0(log2n)B)0(n)C)0(1)D)0(n2)(9)对于线性表(7,34,77,25,64,49,20,14)进行散列存储时，若选用H(K)=K%7作为散列函数，则散列地址为0的元素有()个。A)1B)2C)3D)4(10)下列关于数据结构的叙述中，正确的是()。A)数组是不同类型值的集合B)递归算法的程序结构比迭代算法的程序结构更为精炼C)树是一种线性结构D)用一维数组存储一棵彻底二叉树是有效的存储方法一、单项选择题(每小题2分，共20分)(1) B(2)B(3)A(4)D(5)A(6) A(7)C(8)C(9)D(10)D)方面的内容。C)正确性 D)时空复杂度一、单项选择题(每小题2分，共20分)(1)对一个算法的评价，不包括如下(A)茁壮性和可读性B)并行性(2)在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行)OA)p->next=HL->next;HL->next=pB)p->next=HL;HL=pC)p->next=HL;p=HLD)HL=p;p->next=HL(3)对线性表，在下列哪种情况下应当采用链表表示？()A)时常需要随机地存取元素B)时常需要进行插入和删除操作C)表中元素需要占领一片连续的存储空间D)表中元素的个数不变(4) 一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是()。A)231B)321C)312D)123(5)每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是()。A)冒泡排序B)简单选择排序C)希尔排序D)直接插入排序(6)采用开放定址法处理散列表的冲突时，其平均查找长度()。A)低于链接法处理冲突B)高于链接法处理冲突C)与链接法处理冲突相同0)高于二分查找(7)若需要利用形参直接访问实参时，应将形参变量说明为()参数。A)<B)函数C)指针D)引用(8)在稀疏矩阵的带行指针向量的链接存储中，每一个单链表中的结点都具有相同的)OA)行号B)列号C)元素值D)非零元素个数(9)快速排序在最坏情况下的时间复杂度为()。A)0(log2n)B)0(nlog2n)C)0(n)D)0(n2)(10)从二叉搜索树中查找一个元素时，其时间复杂度大致为()。A)0(n)B)0(1)C)0(log2n)D)0(n2)一、单项选择题(每小题2分，共20分)(1)B(2)A(3)B(4)C(6)B(7)D(8)(9)D(10)C一、单项选择题(每小题2分，共20分)(1)以下数据结构中哪一个是线性结构？()A)有向图B)栈C)二叉树D)B树(2)若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用()存储方式最节省时间。A)单链表B)双链表C)带头结点的双循环链表D)单循环链表(3)()不是队列的基本运算。A)在队列第i个元素之后插入一个元素B)从队头删除一个元素C)判断一个队列是否为空D)读取队头元素的值(4)字符A、B、C、D挨次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成()个不同的字符串？A)15B)14C)16D)21(5)由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。A)11B)37C)19D)53以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G,后序遍历的序列为B、D、C、A、F、G、Eo(6)则该二叉树结点的前序遍历的序列为()。A)E、G、F、A、C、D、BB)E、A、G、C、F、B、DC)E、A、C、B、1)、G、FD)E、G、A、C、D、F、B(7)该二叉树有()个叶子。A)3B)2C)5D)4(8)该二叉树的按层遍历的序列为()。A)E、G、F、A、C、D、BB)E、A、C、B、D、G、FC) E、 A、 G、 C、 F、 B、 DD) E、 G、 A、 C、 D、 F、 B(9)下面的二叉树中，()不是彻底二叉树。(10)设有关键码序列(q,g,mtz,a),()序列是从上述序列出发建的小根堆的结果。A)a,g,m,q,zB)a,g,m,z,qC)g,m,q,a,zD)g,m,a,q,z一、单项选择题(每小题2分，共20分)(1) B(2)C(3)A(4)B(5)B(6) C(7)A(8)C(9)C(10)B一、单项选择题(每小题2分，共20分)(1)队列的特点是()oA)先进后出B)先进先出C)任意位置进出D)前面都不正确(2)有n个记录的文件，如关键字位数为d,基数为r,则基数排序共要进行()遍分配与采集。A)nB)dC)rD)n-d(3)在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序()OA)都不相同B)彻底相同C)先序和中序相同，而与后序不同D)中序和后序相同，而与先序不同(4)限定在一端加入和删除元素的线性表称为()。A)双向链表B)单向链表C)栈D)队列(5)快速排序执行一遍之后，已经到位的元素个数是()。A)1B)3C)D)(6)设森林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树上的结点个数为n,森林F中第一棵树的结点个数是()。A)m-n-1B)n+1C)m-n+1D)m-n(7)设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为()oA)12B)13C)14D)15(8)下面关于广义表的叙述中，不正确的是()。A)广义表可以是一个多层次的结构B)广义表至少有一个元素C)广义表可以被其他广义表所共享D)广义表可以是一个递归表(9)设二叉树根结点的层次为0,一棵深度(高度)为k的满二叉树和同样深度彻底二叉树各有f个结点和C个结点，下列关系式不正确的是()oA)f>=cB)c>fC)f=2k+l-aD)c>sk-l(10)从L=(apple,pear),(orange,banana),取出banana元素的表达式为()。A)head(tail(L)B)head(head(tai1(L)C)tail(head(tai1(L)D)head(tail(head(tail(L)一、单项选择题(每小题2分，共20分)(1) B(2)B(3)B(4)C(5)A(6) D(7)C(8)B(9)B(10)D(1)下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是()。A)顺序结构B)链接结构C)索引结构D)HaSh结构(2)在数据结构中，数据元素可由()。A)实体B)域C)数据项D)字段(3)对于有n个顶点的有向图，由弗洛伊德(FIoyd)算法求每一对顶之间的最短路径的时间复杂度是()。A)0(1)B)0(n)C)0(n)D)0(n3)(4)对n个记录的文件进行快速排序，所需要的辅助存储空间为()。A)0(1)B)0(Iog2n)C)0(n)D)0(n2)(5)哈夫曼树中一定不存在()。A)度为0的结点B)度为1的结点C)度为2的结点D)带权的结点(6)设D=A,B,C,D,R=<E,A>,<A,B>,<B,D>,<D,E>,<D,A>,则数据结构(D,R)是()。A)树B)图B)线性表D)前面都正确(7)()关键码序列不符合堆的定义。A) A、C、D、G、H、M、P、Q、R、XB) A、C、M、D、H、P、X、G、Q、RC) A、D、P、R、C、Q、X、M、H、GD) A、D、C、M、P、G、H、X、R、Q(8)假定关键字K=442205883,允许存储地址为四位十进制数，并且Hash地址为6111,则所采用的构造Hash函数的方法是()。A)直接定址法B)平方取中法C)除留余数法，模为97D)折叠法(9)在算法的时间复杂度中，n表示问题规模，f(n)表示基本操作重复执行的次数，则随问题的规模n的增大，算法执行时间的增长率同()相同。A)f(n)B)nC)0(n)D)前面都不正确(10)对线性表进行二分法查找，其前提条件是()。A)线性表以顺序方式存储，并且按关键码值排好序B)线性表以顺序方式存储，并且按关键码值的检索频率排好序C)线性表以链接方式存储，并且按关键码值排好序D)线性表以链接方式存储，并且按关键码值的检索频率排好序一、单项选择题(每小题2分，共20分)(1) A(2)C(3)D(4)B(5)B(6) B(7)C(8)D(9)A(10)一、单项选择题(每小题2分，共20分)(1)若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是()。A)1234B)4132C)4231D)4213(2)将一个Al.100,L.100的三对角矩阵，按行优先存入一维数组B298中，A中元素a66,65(即该元素下标)在B数组中的位置k为()(假设B0的位置是1)。A)198B)195C)197D)198【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64=194个非零元素，a66,65本身是第195个非零元。(3)若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为()。A)n-1B)C)D)(4)若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那末它的邻接矩阵必然为()。A)对称矩阵B)稀疏矩阵C)三角矩阵D)普通矩阵(5)设森林F对应的二叉树为有m个结点，此二叉树根的左子树的结点个数为k,则另一棵子树的结点个数为()。A)m-k+1B)k+1C)m-k-lD)m-k(6)假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行()次探测。A)K-I次B)K次C)K+1次D)K(K+1)2次(7)一棵深度为k的平衡二叉树，其每一个非终端结点的平衡因子均为0,则该树共有()个结点。A)2k-l-lB)2k-1C)2k-l+lD)2k-1(8)如表r有100000个元素，前99999个元素递增有序，则采用()方法比较次数较少。A)直接插入排序B)快速排序C)归并排序D)选择排序(9)如果只考虑有序树的情形，那末具有7个结点的不同形态的树共有()棵。)132B)154C)429D)前面均不正确(10)对ISAM文件的删除记录时，普通()A)只需做删除标B)需挪移记录C)需改变指针D)一旦删除就要做整理一、单项选择题(每小题2分，共20分)(I)参考答案：C)(2)【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64=194个非零元素，a66,65本身是第195个非零元。参考答案：B)(3)【分析】在哈夫曼树的非叶结点中最多惟独1个结点的度不为m,设非叶结点的个数为k,则其中有k-1个结点的度为m,设另1个结点的度为u,则2u,设结点总数为n总，则有如下关系：n总T=In(kT)+un总=k+n将代入可得：k+n-l=m(k-l)+u,解得：，由于2um,所以可得OWnruVm-I,所以可得：k<+l,可知。参考答案：C)(4)【分析】设顶点按拓扑排序序列为：v,vl,vn-1,则对于邻接矩阵A,惟独当i<j时，才可能有弧<vi,vj>,也就是当ij时，一定没有弧<vi,vj>,所以这时Aij=0,可知邻接矩阵为三角矩阵。参考答案：C)(5)【分析】设另一棵子树的结点个数为n,所以有m=n+k+l,可知n=m-k-l参考答案：C)(6)【分析】因为K个关键字互为同义词，惟独在存入第一个关键字的情况下不发生冲突，所以至少需进行l+2+-+K=K(K+l)2次探测。参考答案：D)(7)【分析】由于每一个非终端结点的平衡因子均为0,所以每一个非终端结点必有摆布两个孩子，且左子树的高度和右子树的高度相同，这样AVL树是满二叉树。高度为k的满二叉树的结点数为2k-lo参考答案：【)(8)【分析】本题中惟独直接插入排序利用前面有序的子序列这个性质，如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可，显然比较次数较少。参考答案：A)(9)【分析】具有n个结点有不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同(将树转化为二叉树时，根结点右子树为空，所以除根结点而外惟独左子树，其不相似的二叉树的等价于不相似的左子树)。具有n个结点互不相似的二又树的数目为，本题中应为。参考答案：A)(9)参考答案：A)