02142《数据结构导论》复习题

1数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题(本大题共15小题，每小题2分，共30分)2、填空题(本大题共13小题，每小题2分，共26分)3、应用题(本大题共5小题，每小题6分，共30分)4、算法设计题(本大题共2小题，每小题7分，共14分)二、单项选择题和填空题样题参考（一）单项选择题1.在二维数组中，每个数组元素同时处于（）个向量中。A.0B.1C.2D.n2.已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（）。A.O(1)B.O(m)C.O(n)D.O(m+n)3.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为()。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL4.若让元素1,2,3依次进栈，则出栈次序不可能出现()种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,25.图的广度优先搜索类似于树的（）遍历。A.先根B.中根C.后根D.层次6.下面程序段的时间复杂度为()。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)7.设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。A.求子串B.模式匹配C.串替换D.串连接8利用双向链表作线性表的存储结构的优点是（）。A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间9.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行()操作。A.top-link=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;10.一棵具有35个结点的完全二叉树的高度为()。假定空树的高度为-1。A.5B.6C.7D.811.一个有n个顶点和n条边的无向图一定是()的。A．连通B．不连通C．无回路D．有回路12.在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（）。A.O(n)B.O(n/2)C.O(1)D.O(n2)13.已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（）。A．Tail(Head(A))B．Head(Tail(A))2C．Head(Tail(Head(Tail(A))))D．Head(Head(Tail(Tail(A))))14.在一棵树的静态双亲表示中，每个存储结点包含()个域。A1B2C3D415.有向图中的一个顶点的度数等于该顶点的()。A．入度B．出度C．入度与出度之和D．(入度+出度)/２15.与邻接矩阵相比，邻接表更适合于存储()。A．无向图B．连通图C．稀疏图D．稠密图17.较快的数据搜索方法是（）搜索方法。A.顺序B.折半C.单链D.散列18.在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的。A.同义词之间发生冲突B.非同义词之间发生冲突C.同义词之间或非同义词之间发生冲突D.散列表“溢出”19.根据n个元素建立一个有序单链表的时间复杂度为（）。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)20.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为()。A.front+1==rearB.rear+1==frontC.front==0D.front==rear21.假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有()个结点。A.3iB.6iC.9iD.2i22.对于具有e条边的无向图，它的邻接表中共有()个边结点。A．e-1B．e+1C．2eD．3e23.图的深度优先搜索遍历类似于树的（）次序遍历。A.先根B.中根C.后根D.层次24．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列?()A.E、D、C、B、A、FB.B、C、E、F、A、DC.C、B、E、D、A、FD.A、D、F、E、B、C25．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：()A.98B.99C.50D.4826.对下列关键字序列用快速排序法进行排序时，速度最快的情形是：()A.{21、25、5、17、9、23、30}B.{25、23、30、17、21、5、9}B.{21、9、17、30、25、23、5}D.{5、9、17、21、23、25、30}27．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表28．假设以第一个元素为分界元素，对字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）进行快速排序，则第一次划分的结果是：()A.(A,C,D,F,H,M,P,Q,R,S,X,Y)B.(A,F,H,C,D,P,M,Q,R,S,Y,X)C.(F,H,C,D,P,A,M,Q,R,S,Y,X)D.(P,A,M,F,H,C,D,Q,S,Y,R,X)29．下面是三个关于有向图运算的叙述：()3（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A.只有（1）B.（1）和（2）C.都正确D.都不正确30．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为:()A.4B.5C.6D.731.以下关于广义表的叙述中,正确的是：()A.广义表是由0个或多个单元素或子表构成的有限序列B.广义表至少有一个元素是子表C.广义表不能递归定义D)广义表不能为空表32.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？()A.堆排序B.直接插入排序C.快速排序D.冒泡排序33．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：()A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为034．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：()A.head-priro==NULLB.head-next==NULLC.head-next==headD.head-next-priro==NULL35.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：()A.2B.3C.4D.536.以下哪一个不是队列的基本运算？()A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值37．对包含n个元素的哈希表进行查找，平均查找长度为：()A.O(log2n)B.O(n)C.O(nlog2n)D不直接依赖于n38．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：()A.48B.49C.50D.5139．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：()A.3B.2C.4D.540．下面是顺序存储结构的优点。A.存储密度大B.插入运算方便C.查找方便D.适合各种逻辑结构的存储表示41．下面关于串的叙述中，是不正确的。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储42．的邻接矩阵是对称矩阵。A.有向图B.无向图C.AOV网D.AOE网43．用链式方式存储的队列，在进行删除运算时，。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改444．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是。先序序列：EFHIGJK中序序列：HFIEJKGA.EB.FC.GD.H45．下面方法可以判断出一个有向图中是否有环。A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径46．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。A.插入B.选择C.冒泡D.都不是47．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是。A.edcbaB.decbaC.dceabD.abcde48．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是。A.inB.2*i=nC.2*i+1nD.2*in49．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A.64.5B.64C.63D.6550．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。A.q-next=p-next;p-next=q;B.p-next=q-next;q=p;C.p-next=p-next;q-next=q;D.p-next=q-next;q-nxet=p;51．对一个满二叉树，m个树叶，n个结点，深度为h，则有。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-152．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。A.选择排序B.冒泡排序C.插入排序D.希尔排序53．用链式方式存储的队列，在进行插入运算时，。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改54．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移个元素。A.n-iB.n-i-1C.n-i+1D.i55．一个栈的入栈序列是12345，则栈的不可能的输出序列是。A.23415B.54132C.23145D.1543256．5个顶点的有向图最多有条弧。A.5B.20C.4D.2557．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL58．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（）存储方式最省时间。A.单链表B.双链表C.单向循环链表D.顺序表59．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（）。A.34B.35C.33D.无法确定60.单循环链表的主要优点是（）。5A.不再需要头指针了B.已知某结点的位置后，很容易找到其前驱C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表61.一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、562.串是一种特殊的线性表，其特殊性表现在（）。A.可以顺序存储B.数据元素是一个字符C可以链式存储D.数据元素是多个字符63.n个顶点的无向图中最多有（）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)D.n(n+1)/264.6个顶点的无向图中，至少有（）条边才能保证是一个连通图。A.5B.6C.7D.865．若某线性表中最常用的操作是删除第1个元素，则不宜采用（）存储方式。A.单链表B.双链表C.单向循环链表D.顺序表66．在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其