数据结构考试模拟题与参考答案

数据结构考试模拟题与参考答案一、单选题（共100题，每题1分，共100分）1.具有35个结点的完全二叉树的深度为()A、6B、8C、7D、5正确答案：A2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()A、n-iB、IC、i+1D、n-i+1正确答案：A3.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A、入边数B、度数减1C、出边数D、度数正确答案：C4.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则()A、n0=2n2+1B、n2=2n0+1C、n0=n2+1D、n2=n0+1正确答案：C5.关于二叉树性质的描述，正确的是（）A、二叉树若存在两个结点，则必有一个为根，另一个为左孩子B、二叉树至少含有一个根结点C、二叉树结点的个数可以为0D、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子正确答案：C6.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。A、3B、4C、5D、1正确答案：B7.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正确答案：A8.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数()。A、3B、1C、4D、2正确答案：D9.对n个元素进行直接插入排序时间复杂度为（）。A、O(log2n)B、O(n)C、O(n2)D、O(1)正确答案：C10.计算机识别、存储和加工处理的对象被统称为()A、数据结构B、数据元素C、数据类型D、数据正确答案：D11.下面程序段的时间复杂度为（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n!)C、O(n)D、O(n^2)正确答案：C12.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A、低B、不好说C、高D、相同正确答案：C13.设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）A、s->link=p->link;p->link=s;B、p->link=s;s->link=q;C、p->link=s->link;s->link=p;D、q->link=s;s->link=p正确答案：D14.一个栈的输入序列是12345，则下列序列中是栈的输出序列的是（）。A、5,4,1,3,2B、2,3,4,1,5C、1,4,2,5,3D、3,1,2,4,5正确答案：B15.下面关于线性表的叙述错误的是（）。A、线性表采用顺序存储便于插入和删除操作的实现B、线性表采用顺序存储必须占用一片连续的存储空间C、线性表采用链式存储不必占用一片连续的存储空间D、线性表采用链式存储便于插入和删除操作的实现正确答案：A16.对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）。A、m+1=2nB、n=2k+1C、m=k-1D、n=m+1正确答案：B17.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（）A、62B、37C、41D、5正确答案：B18.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。A、层次序B、前序C、后序D、中序正确答案：B19.在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。A、2eB、n2-2eC、eD、n2-e正确答案：B20.设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A、1B、2C、3D、4正确答案：A21.为了有效地利用散列查找技术，主要解决的问题是()。①找一个好的散列函数。②有效地解决冲突。③用整数表示关键值A、①和③B、②和③C、①②和③D、①和②正确答案：D22.将5个不同的数据进行排序，至多需要比较（）次。A、25B、9C、8D、10正确答案：D23.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为()A、2nB、nC、n+lD、n-1正确答案：C24.在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换。A、nB、n-1C、n+1D、n/2正确答案：B25.长度为12的按关键字有序的查找表，采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是()。A、Dec-37B、37/13C、Dec-49D、49/13正确答案：D26.某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正确答案：D27.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（）个元素。A、n-i-1B、iC、n-iD、n-i+l正确答案：C28.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）A、eB、nC、2eD、n·e正确答案：A29.对于一组记录的关键字值(25,38,63,74)，采用折半查找25时，()次查找成功。A、1B、2C、3D、4正确答案：B30.邻接矩阵为对称矩阵的图是()A、有向图或无向图B、无向图C、有向图D、带权有向图正确答案：A31.在索引顺序表中查找一个元素，可用的且最快的方法是（）。A、用顺序查找方法确定元素所在块，再用顺序查找在相应块中查找B、用二分查找方法确定元素所在块，再用二分查找在相应块中查找C、用二分查找方法确定元素所在块，再用顺序查找在相应块中查找D、用顺序查找方法确定元素所在块，再用二分查找在相应块中查找正确答案：C32.下列排序算法中，（）在某些特殊情况可能只需一趟排序即可完成。A、堆排序B、插入排序C、快速排序D、冒泡排序正确答案：D33.广度优先遍历类似于二叉树的（）。A、层次遍历B、后序遍历C、先序遍历D、中序遍历正确答案：A34.用链接方式存储的队列，在进行插入运算时()。A、仅修改头指针B、仅修改尾指针C、头、尾指针可能都要修改D、头、尾指针都要修改正确答案：C35.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(2^n)B、O(log2n)C、O(n^2)D、O(n)正确答案：C36.对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（）A、O（n）B、O(e)C、O(n2)D、O(n+e)正确答案：C37.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。A、O(nlog2n)B、O(n)C、O(1)D、O(n2)正确答案：C38.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。A、1024B、256C、512D、20正确答案：C39.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是()A、2，3，5，1，6，4B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，4，3，1，5，6正确答案：A40.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A、O(m+n)B、O(n)C、O(1)D、O(m)正确答案：D41.判定一个栈ST（最多元素为m0）为空的条件是A、ST->top=0B、ST->top=m0C、ST->top<>m0D、ST->top<>0正确答案：A42.有个顶点e条边的无向图G，它的邻接表中的表结点总数是()。A、2eB、nC、eD、2n正确答案：A43.下列四种排序中（）的空间复杂度最大。A、快速排序B、冒泡排序C、堆D、希尔排序正确答案：A44.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）A、层次遍历B、先根遍历C、后根遍历D、中根遍历正确答案：B45.对于二叉树来说，第I层上至多有（）个节点。A、2^i-1B、2^(i-1)C、2^iD、2^(i-1)-1正确答案：B46.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）。A、n-i+1B、n-i-1C、iD、n-i正确答案：D47.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为()A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n正确答案：D48.一棵完全二叉树上有1001个结点，其中叶子结点的个数是()。A、505B、501C、500D、254正确答案：B49.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。A、nB、(n+1)/2C、(n-1)/2D、n/2正确答案：B50.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A、算法B、操作C、逻辑结构D、存储结构正确答案：C51.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A、24B、13C、79D、12正确答案：B52.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）A、单链表B、顺序表C、双链表D、单循环链表正确答案：B53.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）。A、top--B、top不变C、top++D、top=0正确答案：A54.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（）A、顺序查找B、散列查找C、二分查找D、分块查找正确答案：B55.设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正确答案：A56.假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为().A、f+1==rB、f==0C、r+1==fD、f==r正确答案：D57.求单链表中当前结点的后继和前驱的时间复杂度分别是（）A、O(n)和O（n）B、O（1）和O（n）C、O（n）和O（1）D、O（1）和O（1）正确答案：B58.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。A、栈B、线性表C、二叉排序树D、队列正确答案：A59.链表不具有的特点是（）。A、可随机访问任一元素B、所需空间与线性长度成正比C、不必事先估计存储空间D、插入、删除不需要移动元素正确答案：A60.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×t+n）B、O（m+n×t）C、O（m+n+t）D、O（m×n×t）正确答案：D61.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I个结点的地址为（）。A、da1+(I-1)*mB、da1-I*mC、da1+(I+1)*mD、da1+I*m正确答案：A62.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为()。A、1,2,4,3,5B、1,4,2,5,3C、1,2,4,5,3D、1,2,3,4,5正确答案：C63.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是()。A、m1+m2B、m2C、m3D、m2+m3正确答案：D64.下面选项中，（）不是图的存储方法。A、邻接矩阵B、逆邻接链表C、孩子兄弟链表D、邻接链表正确答案：C65.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正确答案：B66.有关栈的描述，正确的是（）A、栈是一种先进先出的特殊的线性表B、只能从栈顶执行插入、删除操作C、只能从栈顶执行插入、栈底执行删除D、栈顶和栈底均可执行插入、删除操作正确答案：B67.栈上溢现象通常出现在（）A、顺序栈的入栈操作过程中B、链栈的入栈操作过程中C、链栈的出栈操作过程中D、顺序栈的出栈操作过程中正确答案：A68.在一棵二叉树上第4层的结点数最多为（）。A、4B、2C、8D、6正确答案：C69.（）二叉排序树可以得到一个从小到大的有序序列。A、中序遍历B、后序遍历C、先序遍历D、层次遍历正确答案：A70.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。A、n/2B、（n+1）/2C、（n-1）/2D、n正确答案：B71.下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n2)B、O(n4)C、O(n)D、O(n3)正确答案：A72.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。A、q=p->next；p->data=q->data；p->next=q->next；free(q)；B、q=p->next；q->data=p->data；p->next=q->next；free(q)；C、q=p->next；p->next=q->next；free(q)；D、q=p->next；p->data=q->data；free(q)；正确答案：A73.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A、在第i个元素之后插入一个新元素(1<=i<=n)B、删除第i个元素(1<=i<=n)C、对顺序表中元素进行排序D、访问第i个元素的前驱（1<i<=n)正确答案：D74.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）A、希尔排序B、归并排序C、选择排序D、插入排序正确答案：C75.数据的基本单位是（）A、数据变量B、数据项C、数据元素D、数据类型正确答案：C76.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为()A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B77.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。A、top=top-1;B、top=top+1;C、top->next=top;D、top=top->next;正确答案：D78.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。A、62B、21C、41D、23正确答案：D79.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（）A、(8，7，6，5，4，3，2，1)B、(5，1，4，3，2，6，8，7)C、(5，1，4，3，2，6，7，8)D、(5，1，4，3，6，2，8，7)正确答案：B80.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A、3B、1C、4D、2正确答案：D81.采用顺序存储结构存储的线性表，其首地址为100，每个元素的长度为2，则第5个元素的地址为()。A、108B、120C、110D、100正确答案：A82.对于顺序表来说，访问任一节点的时间复杂度是（）A、O(n)B、O(log2n)C、O(n2)D、O(1)正确答案：D83.判定一个队列QU（最多元素为m0）为满队列的条件是()A、QU->front==QU->rearQU->front==(QU->rear+1)%m0B、QU->front==QU->rear+1C、QU->rear－QU->front－1==m0D、QU->rear－QU->front==m0正确答案：D84.下列关于线性表的叙述中，不正确的是()A、线性表结点间的逻辑关系是1:1的联系B、线性表的每一个结点有且仅有一个前趋和一个后继C、线性表可以为空表D、线性表是n个结点的有穷序列正确答案：B85.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。A、2eB、nC、eD、ne正确答案：C86.对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（）A、从大到小排列好的B、元素基本有序C、从小到大排列好的D、元素无序正确答案：A87.线性表的顺序存储结构是一种（）的存储结构。A、随机存取B、顺序存取C、散列存取D、索引存取正确答案：A88.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A、2，3，5，6，1，4B、5，4，3，2，1，6C、3，2，5，4，1，6D、1，4，6，5，2，3正确答案：C89.具有n个顶点的无向图，若要连通全部顶点，至少需要（）A、n(n-1)/2条边B、（n-1）条边C、n(n-1)条边D、n条边正确答案：B90.衡量查找算