数据结构练习题库与答案

数据结构练习题库与答案一、单选题（共100题，每题1分，共100分）1.树形结构是数据元素之间存在一种（）。A、多对多关系B、多对一关系C、一对多关系D、一对一关系正确答案：C2.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。A、23B、62C、21D、41正确答案：A3.对于一个无向图，下面()种说法是正确的。A、每个顶点的入度等于出度B、每个顶点的度等于其入度与出度之和C、每个顶点的入度为0D、每个顶点的出度为0正确答案：A4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是()A、120B、100C、108D、110正确答案：C5.哈夫曼树中度为1的结点个数为()。A、1B、2C、0D、不确定正确答案：C6.在有n个叶子结点的哈夫曼树中，其结点总数为（）。A、2nB、不确定C、2n+1D、2n-1正确答案：D7.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。A、101B、102C、99D、100正确答案：D8.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。A、n-1-IB、n-IC、n+1-ID、不能确定正确答案：C9.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的二叉树根结点的右子树上的结点个数是()。A、m2B、m2+m3C、m3D、m1+m2正确答案：B10.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（）。A、s->next=hs；hs=s；B、s->next=hs；hs=hs->next；C、hs->next=s；D、s->next=hs->next；hs->next=s；正确答案：A11.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A、数据元素的相邻地址表示B、数据元素在表中的序号表示C、数据元素的值表示D、指向后继元素的指针表示正确答案：D12.假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为().A、f==0B、f+1==rC、f==rD、r+1==f正确答案：C13.对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（）A、O(n+e)B、O(e)C、O（n）D、O(n2)正确答案：D14.排序算法中，不稳定的排序是（）。A、冒泡排序B、直接插入排序C、选择排序D、堆排序正确答案：D15.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()。A、基数排序B、归并排序C、快速排序D、堆排序正确答案：D16.对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（）。A、n=2k+1B、m+1=2nC、n=m+1D、m=k-1正确答案：A17.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为（）。A、front=front+1B、front=(front+1)%mC、front=(front-1)%mD、front=(front+1)%(m-1)正确答案：B18.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正确答案：A19.以下数据结构中，哪一个是线性结构（）。A、二叉树B、串C、线索二叉树D、有向图正确答案：B20.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A、O(n1/2)B、O(1og2n)C、O(n2)D、O(n)正确答案：D21.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）。A、s.elem［top++］=e；s.top=s.top+1；B、s.top=s.top+1；s.elem［top+1］=e；C、s.elem［top］=e；s.top=s.top+1；D、s.top=s.top+1；s.elem［top］=e；正确答案：D22.一棵含18个结点的二叉树的高度至少为()A、3B、5C、4D、6正确答案：B23.高度为h的完全二叉树中，结点数最多为（）A、2^h-1B、2^h+1C、2^hD、2^(h-1)正确答案：A24.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A、顺序存储结构B、存储结构C、链式存储结构D、逻辑结构正确答案：C25.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。A、45B、20C、40D、30正确答案：A26.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）A、n-1B、2nC、n+1D、n正确答案：A27.在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A、O(n)B、O(1)C、O(log2n)D、O(n2)正确答案：A28.栈和队列共同具有的特点是（）A、都是先进后出B、只允许在端点进行操作运算C、既能先进先出，也能先进后出D、都是先进先出正确答案：B29.二叉树的第k层的结点数最多为().A、2^(k-1)B、2k+1C、2k-1D、2^k-1正确答案：A30.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。A、k1+k2B、k1-k2C、k1D、k2正确答案：D31.一个栈的输入序列是12345，则下列序列中是栈的输出序列的是（）。A、5,4,1,3,2B、2,3,4,1,5C、3,1,2,4,5D、1,4,2,5,3正确答案：B32.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。A、p→link=s→link;s→link=p;B、q→link=s;s→link=p;C、s→link=p→link;p→link=s;D、p→link=s;s→link=q;正确答案：B33.利用二叉链表存储树，则根结点的右指针是()。A、空B、非空C、指向最左孩子D、指向最右孩子正确答案：A34.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。A、选择排序B、归并排序C、希尔排序D、插入排序正确答案：A35.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为()A、n+lB、nC、2nD、n-1正确答案：A36.由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A、m(n-1)B、n(m-1)C、mnD、mn-1正确答案：B37.若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A、7B、6C、3D、5正确答案：D38.对于二叉树来说，第I层上至多有（）个节点。A、2^(i-1)B、2^(i-1)-1C、2^iD、2^i-1正确答案：A39.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。A、nB、eC、2nD、2e正确答案：A40.下列排序算法中，在最好情况下，时间复杂度为O(n)的算法是()。A、归并排序B、快速排序C、冒泡排序D、选择排序正确答案：C41.若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1==n,则pi为（）。A、n-i+1B、iC、不确定D、n==i正确答案：A42.下列排序方法中，属于不稳定的排序方法是()A、希尔排序B、归并排序法C、冒泡排序法D、直接插入排序法正确答案：A43.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A、树B、栈C、图D、队列正确答案：A44.在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1)位置插入一个新元素时需要从后向前移动()个元素A、n-i-1B、n-i+1C、n-iD、i正确答案：B45.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A、队列B、栈C、有序表D、线性表正确答案：A46.邻接矩阵为对称矩阵的图是()A、有向图B、有向图或无向图C、带权有向图D、无向图正确答案：B47.下面程序段的时间复杂度为（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(n^2)B、O(1)C、O(n)D、O(n!)正确答案：C48.在一个非空二叉树的中序遍历序列中，根结点的右边（）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树的上的部分结点D、只有左子树上的所有结点正确答案：A49.关于二叉树性质的描述，正确的是（）A、二叉树至少含有一个根结点B、二叉树若存在两个结点，则必有一个为根，另一个为左孩子C、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子D、二叉树结点的个数可以为0正确答案：D50.求单链表中当前结点的后继和前驱的时间复杂度分别是（）A、O（1）和O（1）B、O（1）和O（n）C、O（n）和O（1）D、O(n)和O（n）正确答案：B51.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A、开始结点B、直接后继C、直接前趋D、终端结点正确答案：B52.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A、O(m)B、O(1)C、O(n)D、O(m+n)正确答案：A53.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正确答案：B54.将5个不同的数据进行排序，至多需要比较（）次。A、8B、9C、10D、25正确答案：C55.有个顶点e条边的无向图G，它的邻接表中的表结点总数是()。A、2nB、2eC、eD、n正确答案：B56.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。A、O(nlog2n)B、O(n2)C、O(n)D、O(1)正确答案：D57.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）A、3B、5C、6D、4正确答案：A58.设指针变量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)；正确答案：A59.栈和队列都是（）。A、顺序存储的线性结构B、链式存储的线性结构C、限制存取位置的线性结构D、限制存取位置的非线性结构正确答案：C60.若<vi,vj>是有向图的一条边，则称（）A、vi与vj¬不相邻接B、vj邻接于viC、vi邻接于vjD、vi和vj相互邻接正确答案：B61.线性表的顺序存储结构是一种（）的存储结构。A、索引存取B、随机存取C、散列存取D、顺序存取正确答案：B62.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个.A、4B、2C、1D、3正确答案：A63.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列（）。A、A,B,C,D,EB、B,C,D,E,AC、E,A,B,C,DD、E,D,C,B,A正确答案：C64.栈和队列的共同特点是()。A、只允许在端点处插入和删除B、都是先进后出C、没有共同点D、都是先进先出正确答案：A65.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()A、冒泡排序B、快速排序C、希尔排序D、插入排序正确答案：D66.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A、A,B,C,D,E,FB、A,B,C,F,D,EC、A,B,D,C,E,FD、A,C,B,F,D,E正确答案：D67.对包含n个元素的散列表进行搜索，平均搜索长度为（）A、O（log2n）B、上述都不对C、不直接依赖于nD、O（n）正确答案：C68.衡量查找算法效率的主要标准是（）。A、元素的个数B、所需的存储量C、平均查找长度D、算法难易程度正确答案：C69.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A、前序遍历算法B、中序遍历算法C、后序遍历算法D、层次遍历算法正确答案：B70.在数据结构中，与所使用的计算机无关的是（）。A、存储结构B、物理结构C、逻辑结构D、逻辑结构和物理结构正确答案：C71.循环队列A[0…m-1]存放其元素值，分别用front和rear表示队头和队尾，则当前队列的元素个数是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正确答案：A72.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）A、p=q->nextB、p->next=q->next->nextC、p->next=qD、p->next=q->next正确答案：D73.一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为（）。A、38,40,46,56,79,84B、40,38,46,84,56,79C、40,38,46,56,79,84D、40,38,46,79,56,84正确答案：C74.在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。A、80B、100C、240D、270正确答案：C75.散列查找中散列函数的值()散列地址的范围。A、在B、小于C、无关D、大于正确答案：A76.采用线性链表表示一个向量时，要求占用的存储空间地址（）。A、必须是连续的B、部分地址必须是连续的C、可连续可不连续D、一定是不连续的正确答案：C77.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为()A、n-1B、n+2C、nD、n+l正确答案：C78.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发不能得到一种深度优先遍历的顶点序列为（）。A、acfebdB、aebdfcC、aedfcbD、abedfc正确答案：A79.下列排序算法中，（）在某些特殊情况可能只需一趟排序即可完成。A、冒泡排序B、插入排序C、快速排序D、堆排序正确答案：A80.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。A、log2(n+1)B、log2nC、log2n+1D、log2n-1正确答案：C81.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A、线性结构和树型结构B、线性结构和图状结构C、树形结构D、线性结构正确答案：A82.设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A、4B、1C、2D、3正确答案：B83.为了有效地利用散列查找技术，主要解决的问题是()。①找一个好的散列函数。②有效地解决冲突。③用整数表示关键值A、①和②B、②和③C、①和③D、①②和③正确答案：A84.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为()A、4，3，3B、3，3，4C、3，4，4D、4，4，3正确答案：A85.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A、24B、12C、79D、13正确答案：D86.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A、不发生改变B、发生改变C、不能确定D、以上都不对正确答案：A87.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（）。A、直接选择排序B、冒泡排序C、快速排序D、直接插入排序正确答案：C88.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A、2m-1B、2m+1C、4mD、2m正确答案：D89.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(n^2)B、O(log2n)C、O(n)D、O(2^n)正确答案：A90.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（）A、