数据结构模考试题及答案

数据结构模考试题及答案一、单选题（共100题，每题1分，共100分）1、下面关于生成树的描述中，不正确的是()A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n，则其边数一定为n-1正确答案：A2、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。A、图B、栈C、队列D、树正确答案：C3、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A、集合B、树形结构C、图形结构D、线性结构正确答案：A4、以下数据结构中，哪一个是线性结构（）。A、线索二叉树B、二叉树C、有向图D、串正确答案：D5、n个顶点的连通图至少中含有()边。A、n-1B、n+1C、nD、0正确答案：A6、G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、7B、8C、6D、9正确答案：D7、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。A、rear=front->nextB、front=rear->nextC、front=front->nextD、rear=rear->next正确答案：C8、一个栈的输入序列是12345，则下列序列中是栈的输出序列的是（）。A、1,4,2,5,3B、3,1,2,4,5C、2,3,4,1,5D、5,4,1,3,2正确答案：C9、假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为()A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B10、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A、存储结构B、操作C、逻辑结构D、算法正确答案：C11、深度为k的完全二叉树中最少有（）个结点。A、2k-1B、2k-1C、2k-1+1D、2k-1-1正确答案：A12、逻辑上通常可以将数据结构分为（）A、顺序结构和链式结构B、初等结构和组合结构C、线性结构和非线性结构D、动态结构和静态结构正确答案：C13、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）。A、快速排序B、冒泡排序C、插入排序D、选择排序正确答案：C14、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A、第i行非0元素的个数之和B、第i列非0元素的个数之和C、第i行0元素的个数之和D、第i列0元素的个数之和正确答案：B15、由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。A、n+1B、nC、2´nD、n-1正确答案：D16、循环队列是空队列的条件是（）A、(Q->rear+1)%maxsize==Q->frontB、Q->rear==0C、Q->front==0D、Q->rear==Q->front正确答案：D17、数据的四种基本逻辑结构是指()A、线性结构、链表、树、图形结构B、线性表、链表、栈队列、数组广义表C、数组、链表、树、图形结构D、集合、线性结构、树、图形结构正确答案：D18、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是()。A、m2B、m2+m3C、m1+m2D、m3正确答案：B19、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A、顺序存储结构B、存储结构C、逻辑结构D、链式存储结构正确答案：D20、为了有效地利用散列查找技术，主要解决的问题是()。①找一个好的散列函数。②有效地解决冲突。③用整数表示关键值A、①和②B、②和③C、①和③D、①②和③正确答案：A21、树的先根序列等同于与该树对应的二叉树的（）A、中序序列B、层序序列C、后序序列D、先序序列正确答案：D22、图的邻接矩阵表示法适用于表示（）A、有向图B、稀疏图C、无向图D、稠密图正确答案：D23、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。A、线性结构B、树型结构C、图型结构D、集合正确答案：C24、队列是一种（）的线性表。A、先进先出B、只能插入C、先进后出D、只能删除正确答案：A25、若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。A、二叉排序树B、队列C、栈D、线性表正确答案：C26、若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A、6B、7C、5D、3正确答案：C27、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A、不发生改变B、发生改变C、不能确定D、以上都不对正确答案：A28、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。A、(n-1)/2B、n/2C、(n+1)/2D、n正确答案：C29、在一个具有n个结点的有序单链表插入一个新结点并仍然有序的时间复杂度是()。A、O(1)B、O(n2)C、O(n)D、O(nlog2n)正确答案：C30、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。A、eB、2nC、nD、2e正确答案：C31、高度为h的完全二叉树中，结点数最多为（）A、2^(h-1)B、2^hC、2^h+1D、2^h-1正确答案：D32、设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。A、n+1-IB、不能确定C、n-1-ID、n-I正确答案：A33、一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()。A、edcbaB、abcdeC、decbaD、dceab正确答案：D34、在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。A、eB、2eC、nD、ne正确答案：A35、下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（）A、二分查找B、顺序查找C、分块查找D、散列查找正确答案：D36、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为()。A、neB、nC、2eD、e正确答案：C37、采用顺序存储结构存储的线性表，其首地址为100，每个元素的长度为2，则第5个元素的地址为()。A、120B、110C、100D、108正确答案：D38、循环队列A[0…m-1]存放其元素值，分别用front和rear表示队头和队尾，则当前队列的元素个数是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正确答案：A39、元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为()A、top=topB、top=top-1C、top=n-1D、top=top+1正确答案：D40、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。A、BADCB、BCDAC、CDABD、CBDA正确答案：A41、对于一个无向图，下面()种说法是正确的。A、每个顶点的入度等于出度B、每个顶点的度等于其入度与出度之和C、每个顶点的入度为0D、每个顶点的出度为0正确答案：A42、对包含n个元素的散列表进行搜索，平均搜索长度为（）A、不直接依赖于nB、上述都不对C、O（n）D、O（log2n）正确答案：A43、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A、O(n1/2)B、O(1og2n)C、O(n)D、O(n2)正确答案：C44、栈的数组表示中，top为栈顶指针，指向栈顶元素的下一个位置，栈空的条件是()。A、top=-1B、top=maxSizeC、top=maxSizeD、top=0正确答案：D45、下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n3)B、O(n2)C、O(n)D、O(n4)正确答案：B46、若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A、对角矩阵B、对称矩阵C、上三角矩阵D、稀疏矩阵正确答案：B47、关于栈和队列的说法中正确的是（）A、栈和队列都是线性结构B、栈和队列都不是线性结构C、栈不是线性结构，队列是线性结构D、栈是线性结构，队列不是线性结构正确答案：A48、下列四种排序中（）的空间复杂度最大。A、希尔排序B、快速排序C、冒泡排序D、堆正确答案：B49、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A、希尔排序B、选择排序C、冒泡排序D、插入排序正确答案：D50、数组的逻辑结构不同于下列（）的逻辑结构。A、线性表B、树C、栈D、队列正确答案：B51、在一棵二叉树上第4层的结点数最多为（）。A、2B、6C、4D、8正确答案：D52、在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A、2nB、n+1C、nD、n-1正确答案：D53、设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵子树的结点个数是（）。A、m-nB、m-n-1C、n+1D、条件不足，无法确定正确答案：A54、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A、对顺序表中元素进行排序B、访问第i个元素的前驱（1<i<=n)C、在第i个元素之后插入一个新元素(1<=i<=n)D、删除第i个元素(1<=i<=n)正确答案：B55、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。A、20B、45C、30D、40正确答案：B56、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、高度等于其节点数C、任一结点无左孩子D、任一结点无右孩子正确答案：B57、连通图G中有n个顶点，G的生成树是()的连通子图。A、包含G的所有顶点B、不必包含G的所有顶点C、包含G的所有边D、包含G的所有顶点和所有边正确答案：A58、计算机识别、存储和加工处理的对象被统称为()A、数据元素B、数据C、数据结构D、数据类型正确答案：B59、for（i=0；i<m；i++）for（j=0；j<t；j++）c［i][j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i][j］=c［i][j］+a［i][k］*b［k][j］；上列程序的时间复杂度为（）A、O（m+n×t）B、O（m×t+n）C、O（m+n+t）D、O（m×n×t）正确答案：D60、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A、48B、53C、71D、24正确答案：C61、设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（）操作。A、x=top->data;B、top=top->link;x=top->data;C、x=top->data;top=top->link;D、x=top;top=top->link;正确答案：C62、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()A、3.4B、1C、5.5D、2.9正确答案：D63、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A、图B、队列C、树D、栈正确答案：C64、在()运算中，使用顺序表比链表好。A、删除B、根据元素值查找C、插入D、根据序号查找正确答案：D65、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。A、80B、100C、240D、270正确答案：C66、下列排序方法中，属于不稳定的排序方法是()A、希尔排序B、冒泡排序法C、归并排序法D、直接插入排序法正确答案：A67、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。A、p→link=s;s→link=q;B、p→link=s→link;s→link=p;C、s→link=p→link;p→link=s;D、q→link=s;s→link=p;正确答案：D68、已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A、4B、3C、2D、1正确答案：C69、假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为()A、n+2B、nC、n-1D、n+l正确答案：B70、若<vi,vj>是有向图的一条边，则称（）A、vi与vj¬不相邻接B、vi和vj相互邻接C、vj邻接于viD、vi邻接于vj正确答案：C71、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()。A、A,B,C,F,D,EB、A,C,F,D,E,BC、A,B,D,C,F,ED、A,B,D,F,E,C正确答案：B72、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。A、n，eB、e，nC、n，2eD、2n，e正确答案：C73、设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A、6B、5C、7D、8正确答案：B74、由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A、n(m-1)B、mnC、mn-1D、m(n-1)正确答案：A75、一个队列的入队序列是1，2，3，4，则队列的输出序列是（）。A、4,3,2,1B、1,2,3,4C、3,2,4,1D、1,4,3,2正确答案：B76、在计算机内实现递归算法时所需的辅助数据结构是()A、图B、队列C、栈D、树正确答案：C77、如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A、堆排序B、冒泡排序C、归并排序D、插入排序正确答案：D78、下面选项中，（）不是图的存储方法。A、邻接矩阵B、邻接链表C、孩子兄弟链表D、逆邻接链表正确答案：C79、栈和队列都是（）。A、链式存储的线性结构B、限制存取位置的线性结构C、顺序存储的线性结构D、限制存取位置的非线性结构正确答案：B80、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）。A、top++B、top=0C、top不变D、top--正确答案：D81、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A、3，2，5，4，1，6B、5，4，3，2，1，6C、1，4，6，5，2，3D、2，3，5，6，1，4正确答案：A82、在一个单链表中，若P所指结点不是最后结点，在P之后插入s所指结点，则执行()。A、s->next=p->next;p->next=sB、s->next=p;p->next=sC、p->next=s;s->next=pD、s->next=p->next;p=s正确答案：A83、在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()A、快速排序B、希尔排序C、冒泡排序D、插入排序正确答案：D84、设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。A、线性结构B、树型结构C、物理结构D、图型结构正确答案：B85、根据数据元素的关键字直接计算出该元素存储地址的存储方法是（）A、链式存储方法B、索引存储方法C、散列存储方法D、顺序存储方法正确答案：C86、一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为（）。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,84,56,79D、40,38,46,56,79,84正确答案：D87、设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发不能得到一种深度优先遍历的顶点序列为（）。A、acfebdB、aebdfcC、abedfcD、aedfcb正确答案：A88、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。A、top=top->next;B、top->next=top;C、top=top-1;D、top=top+1;正确答案：A89、下面程序段的时间复杂度为（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n)C、O(n^2)D、O(n!)正确答案：B90、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）。A、(rear+l)％n==frontB、rear％n==frontC、（front+l）％n==rearD、rear％n-1==front正确答案：A91、在对查找表的查找过程中，若被查找的数据元素不存