搜索
数据结构试题及答案一、单项选择题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.在下面的程序段中，对x的赋值语句的频度为（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)7.程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]A[j+1]THENA[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）。A.O(n）B.O(nlogn)C.O(n3)D.O(n2)8.设有一个递归算法如下：intfact(intn){/*大于等于0*/if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。A.nB.n+1C.n+2D.n-19.用链表表示线性表的优点是（）。A.便于随机存取B．花费的存储空间比顺序表少C．便于插入与删除D．数据元素的物理顺序与逻辑顺序相同10.链表不具有的特点是（）。A.插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比11.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()。A.n-i+1B.iC.i+1D.n-i12.采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。A.nB.n/2C.(n-1)/2D.(n+1)/213.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A.O(1)B.O(n)C.O(m)D.O(m+n)14.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是()。A.head==NULLB.head-next==NULLC.head!=NULLD.head-next==head15.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表16.链式栈与顺序栈相比，一个比较明显的优点是（）。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便17.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。A.较快B.较慢C.相同D.不定18.若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1==n,则pi为（）。A.iB.n==iC.n-i+1D.不确定19.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()。A.edcbaB.decbaC.dceabD.abcde20.若进栈序列为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，421.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序22.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点23.一个队列的入队序列是1，2，3，4，则队列的输出序列是（）。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,124.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front指为（）。A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m25.引起循环队列队头位置发生变化的操作是()。A.出队B.入队C.取队头元素D.取队尾元素26.设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m27.二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为()。A.429B.432C.435D.43828.设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。A.32B.33C.41D.6529.若对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+i30.对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度31.树中所有结点的度之和等于所有结点数加（）。A.0B.1C.－1D.232.在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）。A.nB.n-1C.n+1D.2*n33.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个结点B.高度等于其节点数C.任一结点无左孩子D.任一结点无右孩子34.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A.2hB.2h-1C.2h+1D.h+135.在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个数为（）。A.4B.5C.6D.736.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵子树的结点个数是（）。A．m-nB．m-n-1C．n+1D．条件不足，无法确定37.将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为（）。A.98B.89C.50D.没有孩子38.下列图示的顺序存储结构表示的二叉树是(A)39.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据40.在一个非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树的上的部分结点D.只有左子树上的所有结点41.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对42.在有n个叶子结点的哈夫曼树中，其结点总数为（）。A.不确定B.2nC.2n+1D.2n-143.权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（）。A.18B.28C.19D.2944.对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）。A.n=m+1B.m+1=2nC.m=k-1D.n=2k+145.在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。A.eB.2eC.n2-eD.n2-2e46.若采用邻接矩阵翻存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵47.在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.448.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.449.n个顶点的连通图至少中含有()。A.n-1B.nC.n+1D.050.n个顶点的完全有向图中含有()。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边51.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（）。A.O(n)B.O(e)C.O(n+e)D.O(n*e)52.在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（）。A.顶点序列B.边序列C.权值总和D.边的条数53.由同一组关键字集合构造的各棵二叉排序树()。A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同54.无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b55.下面哪一方法可以判断出一个有向图是否有环（回路）。A．求节点的度B.拓扑排序C.求最短路径D.求关键路径56.图的广度优先搜索类似于树的（）次序遍历。A.先根B.中根C.后跟D.层次57.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)58.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V759.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路60.对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为()。A.(19,23,56,34,78,67,88,92)B.23,56,78,66,88,92,19,34)C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88)61.用某种排序方法对关键字序列{25,84,21,47,15,27,68,25,20}进行排序时，序列的变化情况如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84则采用的方法是（）。A.直接选择排序B.希尔排序C.归并排序D.快速排序62.一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为（）。A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,7963.下列排序算法中不稳定的是（）。A.直接选择排序B.二分插入排序C.冒泡排序D.快速排序64.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（）。A.直接选择排序B.直