数据结构试题库答案

数据结构试题及答案一、单项选择题(1)一个算法应该是（）。A)程序B)问题求解步骤的描述C)要满足五个基本属性D)A和C(2)算法指的是（）。A)计算机程序B)解决问题的计算方法C)排序算法D)解决问题的有限运算序列。(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A)存储结构B)逻辑结构C)算法D)操作(4)从逻辑上可以把数据结构分为（）两大类。A)动态结构、静态结构B)顺序结构、链式结构C)线性结构、非线性结构D)初等结构、构造型结构(5)下列叙述中正确的是()。A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率(6)数据的基本单位是（）A)数据项B)数据类型C)数据元素D)数据变量(7)下列程序的时间复杂度为（）i=0；s=0；while（sn）{i++；s=s+i；}A)O（n）B)O（n2）C)O（n）D)O（n2）(8)下列程序段的渐进时间复杂度为（）。for(inti=1;i=n;i++)for(intj=1;j=m;j++)A[i][j]=i*j;A）O(m2)B）O(n2)C）O(m*n)D）(m+n)(9)程序段如下：sum=0；for(i=1;i=n;i++)for(j=1;j=n;j++)sum++；其中n为正整数，则最后一行的语句频度在最坏情况下是（）。A）O(n）B)O(nlogn)C)O(n3)D)O(n2)(10)在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;i=n;i++)for(j=1;j=n;j++)x:=x+1;A)O(2n)B)O(n)C)O(n2)D)O(log2n)(11)程序段for(i:=n-1;i=1;i--）for(j:=1;j=i;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}其中n为正整数，则最后一行的语句频度在最坏情况下是（）。A)O(n）B)O(nlogn)C)O(n3)D)O(n2)(12)设有一个递归算法如下：intfact(intn){/*大于等于0*/if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。A)nB)n+1C)n+2D)n-1(13)下述程序段中语句①的频度是（）。s=0;for(i=1;im;i++)for(j=0;j=i;j++)s+=j;A)211)m)(m(B)21)m(mC)212)m)(m(D)21)m(m(14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）。A)单链表B)仅有头指针的单循环链表C)双链表D)仅有尾指针的单循环链表(1)求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。A)O(n)和O(1)B)O(1)和O(1)C)O(1)和O(n)D)O(n)和O(n)(15)求单链表中当前结点的后继和前驱的时间复杂度分别是（）。A)O（n）和O（1）B)O（1）和O（1）C)O（1）和O（n）D)O(n)和O（n）(16)非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）。A)rear-next==headB)rear-next-next==headC)head-next==rearD)head-next-next==rear(17)从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）。A)n-iB)n-i+1C)n-i-1D)i(18)已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（）。A)1B)2C)3D)4(19)假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（）。A)R[3][3][3]B)R[3][3][4]C)R[4][3][5]D)R[4][3][4](20)设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（）。A)13B)35C)17D)36(21)线性表采用链式存储时，节点的存储的地址（）。A)必须是不连续的B)连续与否均可C)必须是连续的D)和头节点的存储地址相连续(22)用链表表示线性表的优点是（）。A)便于随机存取B)花费的存储空间比顺序表少C)数据元素的物理顺序与逻辑顺序相同D)便于插入与删除(23)链表不具有的特点是（）。A)插入、删除不需要移动元素B)可随机访问任一元素C)不必事先估计存储空间D)所需空间与线性长度成正比(24)在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()。A)n-i+1B)iC)i+1D)n-i(25)采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。A)nB)n/2C)(n-1)/2D)(n+1)/2(26)将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A)O(1)B)O(n)C)O(m)D)O(m+n)(27)若不带头结点的单链表的头指针为head，则该链表为空的判定条件是()。A)head==NULLB)head-next==NULLC)head!=NULLD)head-next==head(28)某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A)单链表B)仅有头指针的单循环链表C)双链表D)仅有尾指针的单循环链表(29)若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。A)栈B)线性表C)队列D)二叉排序树(30)顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）。A)s.elem［top］=e；s.top=s.top+1；B)s.elem［top+1］=e；s.top=s.top+1；C)s.top=s.top+1；s.elem［top+1］=e；D)s.top=s.top+1；s.elem［top］=e；(31)循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（）。A)8B)16C)17D)18(32)链式栈与顺序栈相比，一个比较明显的优点是（）。A)插入操作更加方便B)通常不会出现栈满的情况C)不会出现栈空的情况D)删除操作更加方便(33)一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。A)较快B)较慢C)相同D)不定(34)若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1==n,则pi为（）。A)iB)n==iC)n-i+1D)不确定(35)一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()。A)edcbaB)decbaC)dceabD)abcde(36)若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是()。A)2，4，3，1，5，6B)3，2，4，1，6，5C)4，3，2，1，5，6D)2，3，5，1，6，4(37)对于栈操作数据的原则是（）。A)先进先出B)后进先出C)后进后出D)不分顺序(38)栈和队列的共同点是（）。A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点(39)一个队列的入队序列是1，2，3，4，则队列的输出序列是（）。A)4,3,2,1B)1,2,3,4C)1,4,3,2D)3,2,4,1(40)设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为（）。A)front=front+1B)front=(front+1)%(m-1)C)front=(front-1)%mD)front=(front+1)%m(41)引起循环队列队头位置发生变化的操作是()。A)出队B)入队C)取队头元素D)取队尾元素(2)设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A）(rear-front+m)%mB）rear-front+1C）(front-rear+m)%mD）(rear-front)%m(42)二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为()。A)429B)432C)435D)438(43)设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。A)32B)33C)41D)65(44)若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（ij）的位置k的关系为()。A)i*(i-1)/2+jB)j*(j-1)/2+iC)i*(i+1)/2+jD)j*(j+1)/2+i(45)对稀疏矩阵进行压缩存储目的是（）。A)便于进行矩阵运算B)便于输入和输出C)节省存储空间D)降低运算的时间复杂度(46)对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是()。A)(e,f)B)((e,f))C)(f)D)()(47)设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A)1和1B)1和3C)1和2D)2和3(48)树中所有结点的度之和等于所有结点数加（）。A)0B)1C)-1D)2(49)在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）。A)nB)n-1C)n+1D)2*n(50)某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A)空或只有一个结点B)高度等于其节点数C)任一结点无左孩子D)任一结点无右孩子(51)含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）A)3B)4C)5D)6(52)除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A)1/2倍B)1倍C)2倍D)3倍(53)对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（）A)24B)25C)98D)99(54)可以惟一地转化成一棵一般树的二叉树的特点是（）A)根结点无左孩子B)根结点无右孩子C)根结点有两个孩子D)根结点没有孩子(55)设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A)2hB)2h-1C)2h+1D)h+1(56)在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）。A)4B)5C)6D)7(57)设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵子树的结点个数是（）。A)m-nB)m-n-1C)n+1D)条件不足，无法确定(58)将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为（）。A)98B)89C)50D)没有孩子(59)下列图示的顺序