数据结构习题（含参考答案）

数据结构习题（含参考答案）一、单选题（共100题，每题1分，共100分）1.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+n×t）C、O（m×t+n）D、O（m+n+t）正确答案：A2.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。A、rear=rear->nextB、front=front->nextC、rear=front->nextD、front=rear->next正确答案：B3.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为()A、236B、239C、245D、242正确答案：B4.有个顶点e条边的无向图G，它的邻接表中的表结点总数是()。A、eB、2nC、nD、2e正确答案：D5.下列四种排序中（）的空间复杂度最大。A、快速排序B、冒泡排序C、堆D、希尔排序正确答案：A6.数据结构的定义为(D，S)，其中D是()的集合。A、算法B、数据元素C、数据操作D、逻辑结构正确答案：B7.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是()A、108B、100C、120D、110正确答案：A8.深度为k的二叉树至多有()A、2^(k-1)-1个结点B、2^k-1个结点C、2^k个结点D、2^(k-1)个结点正确答案：B9.可以唯一地转化成一棵一般树的二叉树的特点是（）A、根结点无左孩子B、根结点有两个孩子C、根结点没有孩子D、根结点无右孩子正确答案：D10.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A、O(1)B、O(n)C、O(m+n)D、O(m)正确答案：D11.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(log2n)B、O(n)C、O(2^n)D、O(n^2)正确答案：D12.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为()A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B13.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加()。A、2B、1C、0D、-1正确答案：A14.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）A、顺序表B、双链表C、单链表D、单循环链表正确答案：A15.衡量查找算法效率的主要标准是（）。A、元素的个数B、所需的存储量C、平均查找长度D、算法难易程度正确答案：C16.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A、栈B、图C、队列D、树正确答案：D17.下列排序方法中，稳定的排序方法为（）A、希尔排序B、堆排序C、快速排序D、直接插入排序正确答案：D18.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为()A、top=topB、top=n-1C、top=top+1D、top=top-1正确答案：C19.由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。A、n-1B、nC、n+1D、2´n正确答案：A20.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。A、2i+1B、2iC、i/2D、2i-1正确答案：B21.G是一个非连通无向图，共有28条边，则该图至少有()个顶点。A、7B、8C、6D、9正确答案：D22.采用线性链表表示一个向量时，要求占用的存储空间地址（）。A、部分地址必须是连续的B、一定是不连续的C、必须是连续的D、可连续可不连续正确答案：D23.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A、删除B、排序C、插入D、定位正确答案：D24.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（）A、(5，1，4，3，6，2，8，7)B、(5，1，4，3，2，6，7，8)C、(8，7，6，5，4，3，2，1)D、(5，1，4，3，2，6，8，7)正确答案：D25.设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）A、q->link=s;s->link=pB、s->link=p->link;p->link=s;C、p->link=s->link;s->link=p;D、p->link=s;s->link=q;正确答案：A26.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A、入边数B、度数C、度数减1D、出边数正确答案：D27.在一个非空二叉树的中序遍历序列中，根结点的右边（）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树的上的部分结点D、只有左子树上的所有结点正确答案：A28.若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A、上三角矩阵B、稀疏矩阵C、对角矩阵D、对称矩阵正确答案：D29.在平均情况下速度最快的排序方法为（）。A、归并排序B、快速排序C、堆排序D、简单选择排序正确答案：B30.在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为()。A、k+n/kB、n+kC、(k+n/k)/2D、(k+n/k)/2+1正确答案：D31.在一个单链表中,若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=p;D、p→link=s;s→link=q;正确答案：C32.设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A、a，b，d，cB、a，b，c，dC、c，d，a，bD、d，c，b，a正确答案：C33.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。A、20B、512C、1024D、256正确答案：B34.无向图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,e,b,c,f,dB、a,b,e,c,d,fC、a,c,f,e,b,dD、a,e,d,f,c,b正确答案：D35.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是()A、除留余数法B、折叠法C、平方取中法D、线性探测法正确答案：D36.用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A、树B、图C、栈D、队列正确答案：C37.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A、逻辑结构B、链式存储结构C、存储结构D、顺序存储结构正确答案：B38.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是()A、p->next=p->nextB、p->next=pC、p->next=p->next->nextD、p=p->next正确答案：C39.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧的时间复杂度是（）。A、O(e)B、O(n)C、O(n*e)D、O(n+e)正确答案：D40.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行()。A、p->link=s;s->link=p;B、s->link=p;p->link=s;C、s->link=p->link;p=s;D、s->link=p->link;p->link=s;正确答案：D41.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）A、2nB、nC、n-1D、n+1正确答案：C42.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）。A、top--B、top=0C、top不变D、top++正确答案：A43.抽象数据类型的三个组成部分分别为（）A、数据元素、数据结构和数据类型B、数据对象、数据关系和基本操作C、数据项、数据元素和数据类型D、数据元素、逻辑结构和存储结构正确答案：B44.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A、数据元素的值表示B、数据元素的相邻地址表示C、指向后继元素的指针表示D、数据元素在表中的序号表示正确答案：C45.3个结点可构成（）棵不同形态的二叉树。A、4B、2C、3D、5正确答案：D46.对包含n个元素的散列表进行搜索，平均搜索长度为（）A、O（n）B、O（log2n）C、上述都不对D、不直接依赖于n正确答案：D47.如下陈述中正确的是（）A、串是一种特殊的线性表B、空串就是空白串C、串中元素只能是字母D、串的长度必须大于0正确答案：A48.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A、12B、79C、24D、13正确答案：D49.循环队列是空队列的条件是（）A、Q->rear==0B、Q->rear==Q->frontC、(Q->rear+1)%maxsize==Q->frontD、Q->front==0正确答案：B50.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为()A、希尔排序B、归并排序C、选择排序D、插入排序正确答案：C51.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、高度等于其节点数C、任一结点无左孩子D、任一结点无右孩子正确答案：B52.导致栈上溢的操作是()A、栈空时执行的入栈B、栈空时执行的出栈C、栈满时执行的出栈D、栈满时执行的入栈正确答案：D53.设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。A、3B、2C、6D、4正确答案：A54.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则()A、n0=2n2+1B、n2=n0+1C、n0=n2+1D、n2=2n0+1正确答案：C55.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A、2倍B、3倍C、1/2倍D、1倍正确答案：A56.用链接方式存储的队列，在进行插入运算时()。A、仅修改尾指针B、头、尾指针可能都要修改C、头、尾指针都要修改D、仅修改头指针正确答案：B57.为了有效地利用散列查找技术，主要解决的问题是()。①找一个好的散列函数。②有效地解决冲突。③用整数表示关键值A、①和②B、①②和③C、①和③D、②和③正确答案：A58.设有n个结点的二叉树上只有度为0和度为2的结点，则此二叉树中叶子结点数()。A、不能确定B、（n+1)/2C、n/2D、(n-1)/2正确答案：B59.下面关于生成树的描述中，不正确的是()A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n，则其边数一定为n-1正确答案：A60.栈上溢现象通常出现在（）A、顺序栈的出栈操作过程中B、链栈的出栈操作过程中C、链栈的入栈操作过程中D、顺序栈的入栈操作过程中正确答案：D61.下面程序段的时间复杂度为（）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)正确答案：C62.连通图G中有n个顶点，G的生成树是()的连通子图。A、包含G的所有顶点B、不必包含G的所有顶点C、包含G的所有边D、包含G的所有顶点和所有边正确答案：A63.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A、4mB、2m-1C、2m+1D、2m正确答案：D64.图的深度、广度优先遍历算法分别类似于二叉树的()。A、层序遍历和先序遍历B、先序遍历和层序遍历C、先序遍历和中序遍历D、后序遍历和中序遍历正确答案：B65.设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正确答案：A66.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）A、(5,16,2,12)28(32,60,72)B、(2,5,12,16)28(60,32,72)C、(5,16,2,12)28(60,32,72)D、(2,16,12,5)28(60,32,72)正确答案：C67.一个栈的输入序列为1，2，3，…，n，设若输出序列的第1个元素为n，输出第i（1≤i≤n)个元素是()。A、n-i+1B、n-iC、iD、不确定正确答案：A68.算法分析的两个主要方面是：A、数据复杂性和程序复杂性B、可读性和文档性C、空间复杂性和时间复杂性D、正确性和简明性正确答案：C69.（）二叉排序树可以得到一个从小到大的有序序列。A、后序遍历B、层次遍历C、先序遍历D、中序遍历正确答案：D70.数据的四种基本逻辑结构是指()A、数组、链表、树、图形结构B、线性表、链表、栈队列、数组广义表C、线性结构、链表、树、图形结构D、集合、线性结构、树、图形结构正确答案：D71.设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A、3B、4C、1D、2正确答案：C72.若最常用的操作是读取线性表中元素的值，则采用()存储方式最节省时间。A、顺序表B、带尾指针的单循环链表C、单链表D、带尾指针的单链表正确答案：A73.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（）A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正确答案：A74.某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正确答案：D75.数据的基本单位是（）A、数据项B、数据变量C、数据元素D、数据类型正确答案：C76.设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。A、nB、2nC、2n-1D、n-1正确答案：D77.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A、1,2,3,4,5B、1,2,5,4,3C、1,2,5,3,4D、1,4,3,2,5正确答案：B78.在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1)位置插入一个新元素时需要从后向前移动()个元素A、iB、n-i+1C、n-iD、n-i-1正确答案：B79.链式栈与顺序栈相比，一个比较明显的优点是（）。A、删除操作更加方便B、不会出现栈空的情况C、通常不会出现栈满的情况D、插入操作更加方便正确答案：C80.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A、有序表B、栈C、队列D、线性表正确答案：C81.n个顶点的连通图至少中含有()边。A、0B、n-1C、nD、n+1正确答案：B82.以下数据结构中哪一个是非线性结构？()A、栈B、队列C、二叉树D、线性表正确答案：C83.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为（）。A、front=front+1B、front=(front-1)%mC、front=(front+1)%mD、front=(front+1)%(m-1)正确答案：C84.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正确答案：B85.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。A、k1B、k2C、k1+k2D、k1-k2正确答案：B86.在待排关键字序列基本有序的前提下，效率最高的排序方法是()A、归并排序B、直接选择排序C、快速排序D、直接插入排序正确答案：D87.若一个图的边集为{(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正确答案：B88.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为()A、6B、5C、7D、4正确答案：A89.一个数组元素a[i]与（）的表示等价。A、&a+iB、*（a+i）C、*a+ID、a+I正确答案：B90.下列关于线性表的叙述中，不正确的是()A、线性表的每一个结点有且仅有一个前趋和一个后继B、线性表结点间的逻辑关系是1:1的联系C、线性表可以为空表D、线性表是n个结点的有穷序列正确答案：A91.