数据结构模拟练习题+答案

数据结构模拟练习题+答案一、单选题（共100题，每题1分，共100分）1.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。A、O(n2)B、O(n)C、O(1)D、O(log2n)正确答案：B2.下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A、集合B、图形结构C、线性结构D、树形结构正确答案：A3.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为()A、归并排序B、希尔排序C、选择排序D、插入排序正确答案：C4.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A、算法B、存储结构C、逻辑结构D、操作正确答案：C5.衡量查找算法效率的主要标准是（）。A、元素的个数B、所需的存储量C、平均查找长度D、算法难易程度正确答案：C6.以下数据结构中，哪一个是线性结构（）。A、二叉树B、有向图C、线索二叉树D、串正确答案：D7.下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n4)B、O(n)C、O(n2)D、O(n3)正确答案：C8.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A、10B、7C、8D、9正确答案：C9.循环队列是空队列的条件是（）A、Q->front==0B、Q->rear==Q->frontC、Q->rear==0D、(Q->rear+1)%maxsize==Q->front正确答案：B10.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）A、nB、n·eC、2eD、e正确答案：D11.对于一个线性表，若既要求能够进行较快地插入和删除，又要求存储结构能够得出数据元素之间的关系，则应该以()。A、链式存储B、索引方式存储C、顺序方式存储D、散列方式存储正确答案：A12.对于顺序表来说，访问任一节点的时间复杂度是（）A、O(1)B、O(log2n)C、O(n)D、O(n2)正确答案：A13.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为()A、n-1B、n+2C、nD、n+l正确答案：C14.导致栈上溢的操作是()A、栈满时执行的出栈B、栈满时执行的入栈C、栈空时执行的入栈D、栈空时执行的出栈正确答案：B15.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A、48B、71C、53D、24正确答案：B16.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在()A、BT[i/2]B、BT[2*i-1]C、BT[2*i]D、BT[2*i+1]正确答案：D17.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是()。A、m3B、m2C、m1+m2D、m2+m3正确答案：D18.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为()。A、O(n)B、O(n／2)C、O(1)D、O(n2)正确答案：A19.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。A、front=rear->nextB、rear=front->nextC、front=front->nextD、rear=rear->next正确答案：C20.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）。A、（front+l）％n==rearB、(rear+l)％n==frontC、rear％n-1==frontD、rear％n==front正确答案：B21.有8个结点的无向连通图最少有（）条边。A、5B、8C、7D、6正确答案：C22.若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。A、O(n2)B、O(n)C、O(log2n)D、O(1)正确答案：B23.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为()A、q->next=s->next；s->next=p；B、p->next=s->next；s->next=q;C、s->next=q；p->next=s->next；D、s->next=p；q->next=s->next；正确答案：A24.栈的数组表示中，top为栈顶指针，指向栈顶元素的下一个位置，栈空的条件是()。A、top=maxSizeB、top=-1C、top=maxSizeD、top=0正确答案：D25.栈和队列()A、共同之处在于二者都是先进后出的特殊的线性表B、没有共同之处C、共同之处在于二者都只允许在顶端执行删除操作D、共同之处在于二者都是先进先出的特殊的线性表正确答案：C26.栈可以在()中应用。A、递归调用B、子程序调用C、表达式求值D、A,B,C正确答案：D27.设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。A、2n-1B、nC、n-1D、2n正确答案：C28.设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、在p所指结点的元素之后插入元素B、在p所指结点的元素之前插入元素C、结点*p与结点*s的数据域互换D、在结点*p之前插入结点*s正确答案：D29.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是()A、2，3，5，1，6，4B、4，3，2，1，5，6C、3，2，4，1，6，5D、2，4，3，1，5，6正确答案：A30.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()。A、abcdeB、edcbaC、decbaD、dceab正确答案：D31.对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（）A、元素基本有序B、从小到大排列好的C、从大到小排列好的D、元素无序正确答案：C32.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）。A、n-i-1B、n-i+1C、n-iD、i正确答案：C33.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A、1,2,5,4,3B、1,4,3,2,5C、1,2,5,3,4D、1,2,3,4,5正确答案：A34.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A、冒泡排序B、插入排序C、希尔排序D、选择排序正确答案：B35.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A、线性结构B、树形结构C、线性结构和树型结构D、线性结构和图状结构正确答案：C36.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正确答案：A37.若最常用的操作是读取线性表中元素的值，则采用()存储方式最节省时间。A、带尾指针的单链表B、顺序表C、单链表D、带尾指针的单循环链表正确答案：B38.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）A、4B、5C、3D、6正确答案：C39.对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）。A、m+1=2nB、m=k-1C、n=2k+1D、n=m+1正确答案：C40.链式栈与顺序栈相比，一个比较明显的优点是（）。A、删除操作更加方便B、通常不会出现栈满的情况C、不会出现栈空的情况D、插入操作更加方便正确答案：B41.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()。A、归并排序B、快速排序C、基数排序D、堆排序正确答案：D42.高度为h的完全二叉树中，结点数最多为（）A、2^(h-1)B、2^h-1C、2^hD、2^h+1正确答案：B43.引起循环队列队头位置发生变化的操作是()。A、出队B、入队C、取队尾元素D、取队头元素正确答案：A44.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A、1，2，3B、9，5，2，3C、9，5，3D、9，4，2，3正确答案：D45.数据的四种基本存储结构是指（）A、顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构B、顺序存储结构、链式存储结构、树型存储结构、图型存储结构C、顺序存储结构、索引存储结构、链式存储结构、散列存储结构D、顺序存储结构、索引存储结构、直接存储结构、倒排存储结构正确答案：C46.邻接矩阵为对称矩阵的图是()A、带权有向图B、无向图C、有向图D、有向图或无向图正确答案：D47.下面关于线性表的叙述错误的是（）。A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储便于插入和删除操作的实现C、线性表采用链式存储不必占用一片连续的存储空间D、线性表采用顺序存储便于插入和删除操作的实现正确答案：D48.深度为6（根的层次为1）的二叉树至多有（）结点。A、64B、32C、63D、31正确答案：C49.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A、7B、1C、10D、25正确答案：C50.利用二叉链表存储树，则根结点的右指针是()。A、非空B、指向最左孩子C、空D、指向最右孩子正确答案：C51.在平均情况下速度最快的排序方法为（）。A、堆排序B、归并排序C、快速排序D、简单选择排序正确答案：C52.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）。A、二叉排序树B、队列C、栈D、线性表正确答案：C53.队列是一种（）的线性表。A、只能插入B、先进先出C、只能删除D、先进后出正确答案：B54.在有n个叶子结点的哈夫曼树中，其结点总数为（）。A、2nB、2n+1C、2n-1D、不确定正确答案：C55.在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。A、结点大小B、向量大小C、基地址和结点大小D、基地址正确答案：C56.下面选项中，（）不是图的存储方法。A、孩子兄弟链表B、逆邻接链表C、邻接矩阵D、邻接链表正确答案：A57.采用顺序存储结构存储的线性表，其首地址为100，每个元素的长度为2，则第5个元素的地址为()。A、120B、108C、110D、100正确答案：B58.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、高度等于其节点数C、任一结点无左孩子D、任一结点无右孩子正确答案：B59.数组的逻辑结构不同于下列（）的逻辑结构。A、线性表B、栈C、树D、队列正确答案：C60.下面程序段的时间复杂度为（）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(n2)B、O(m*n)C、O(m2)D、O(m+n)正确答案：B61.下列排序算法中，（）在某些特殊情况可能只需一趟排序即可完成。A、快速排序B、堆排序C、冒泡排序D、插入排序正确答案：C62.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A、有序表B、栈C、线性表D、队列正确答案：D63.深度为k的完全二叉树中最少有（）个结点。A、2k-1-1B、2k-1+1C、2k-1D、2k-1正确答案：C64.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为()。A、12B、4C、13D、8正确答案：A65.对于长度为n的顺序表执行删除操作，则其结点的移动次数（）A、最少为0，最多为nB、最少为0，最多为n-1C、最少为1，最多为nD、最少为1，最多为n-1正确答案：B66.为了有效地利用散列查找技术，主要解决的问题是()。①找一个好的散列函数。②有效地解决冲突。③用整数表示关键值A、①和③B、②和③C、①②和③D、①和②正确答案：D67.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（）A、(8，7，6，5，4，3，2，1)B、(5，1，4，3，6，2，8，7)C、(5，1，4，3，2，6，8，7)D、(5，1，4，3，2，6，7，8)正确答案：C68.下列程序段的渐进时间复杂度为（）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)正确答案：C69.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I个结点的地址为（）。A、da1+(I-1)*mB、da1+(I+1)*mC、da1-I*mD、da1+I*m正确答案：A70.栈的插入和删除操作在（）进行。A、任意位置B、栈顶C、指定位置D、栈底正确答案：B71.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为()A、top=top-1B、top=n-1C、top=top+1D、top=top正确答案：C72.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A、不好说B、相同C、低D、高正确答案：D73.对于二叉树来说，第I层上至多有（）个节点。A、2^iB、2^(i-1)-1C、2^(i-1)D、2^i-1正确答案：C74.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A、1倍B、1/2倍C、3倍D、2倍正确答案：D75.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。A、归并排序B、插入排序C、希尔排序D、选择排序正确答案：D76.for（i=0；i<m；i++）for（j=0；j<n；j++）A［i][j］=i*j；上面算法的时间复杂度为()A、O(m2)B、O(n2)C、O(m×n)D、O(m+n）正确答案：C77.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（）A、n+2B、n-1C、nD、n+1正确答案：D78.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（）A、求一个顶点的邻接点B、广度优先遍历C、求一个顶点的度D、深度优先遍历正确答案：A79.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。A、512B、1024C、256D、20正确答案：A80.设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）A、s->link=p->link;p->link=s;B、p->link=s->link;s->link=p;C、q->link=s;s->link=pD、p->link=s;s->link=q;正确答案：C81.在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（）。A、O(nlog2n)B、O(1)C、O(n2)D、O(log2n)正确答案：B82.判定一个栈ST（最多元素为m0）为空的条件是A、ST->top<>m0B、ST->top=0C、ST->top=m0D、ST->top<>0正确答案：B83.在一个单链表中，若P所指结点不是最后结点，在P之后插入s所指结点，则执行()。A、s->next=p->next;p=sB、s->next=p;p->next=sC、s->next=p->next;p->next=sD、p->next=s;s->next=p正确答案：C84.树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间无联系的数据D、元素之间具有分支层次关系的数据正确答案：D85.3个结点可构成（）棵不同形态的二叉树。A、4B、5C、3D、2正确答案：B86.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A、13B、79C、24D、12正确答案：A87.设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A、a，b，d，cB、d，c，b，aC、c，d，a，bD、a，b，c，d正确答案：C88.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(n)B、O(n^2)C、O(log2n)D、O(2^n)正确答案：B89.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A、6B、4C、5D、7正确答案：A90.若要把n个顶点连接为一个连通图，则至少需要()条边。A、n+1B、nC、2nD、n-1正确