数据结构常见题型整合

数据结构常见题型整合数据结构常见题型整合数据结构常见题型整合数据结构常见题型整合编制仅供参考审核批准生效日期地址：电话：传真:邮编:数据结构常见题型整合1、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，3、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。A.N/2,NB.N,N/2C.0,ND.N,0设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分6、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if==… B．if==+MAXQSIZE))C．if==+1)%MAXQSIZE)D．if==+1)%MAXQSIZE)假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少()A.1和5B.2和4C.4和2D.5和19、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,2最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点栈是___操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循___后进先出____的原则。，其特点是__先进先出__。用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为___S×SS×S××__。表达式求值是___栈____应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是线性表。在作进栈运算时，应先判别栈是否.满，在作退栈运算时应先判别栈是否空。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n。12、在二叉树的第I层(I≥1)上最多含有结点数为（）A.2IB.2I-1-1C.2I-1D.2I-113、深度为6的二叉树最多有()个结点A．6414、一棵树高为K的完全二叉树至少有()个结点–1–1k15、有关二叉树下列说法正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为216、n个结点的线索二叉树上含有的线索数为（）A.2nB.n－lC.n＋lD.n17、线性表和树的结构区别在于（）A．前驱数量不同，后继数量相同 B．前驱数量相同，后继数量不同C．前驱和后继的数量都相同 D．前驱和后继的数量都不同18、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE19、设有一表示算术表达式的二叉树（见下图），EEFDGAB/++*-C*它所表示的算术表达式是（）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G20、一棵具有n个结点的完全二叉树的树高度（深度）(符号表示取不大于x的最大整数)是（）A.B.C.D.21、利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空22、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定23、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。A.3 B.4 C.5 D.624、线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性二、填空题7、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___N2+1_________。8、具有256个结点的完全二叉树的深度为___9___。9、一个深度为4的二叉树，其结点至少有4个，至多有15个：10、深度为H的完全二叉树至少有_2H-1__个结点；至多有2H-1_个结点；H和结点总数N之间的关系是H=log2N+1。11、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有__2N__个指针域，其中有_N-1__个指针域是存放了地址，有__N+1_____个指针是空指针。12、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是__63____13、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为2i；若右孩子结点存在，则其编号为2i+1；而双亲结点的编号为。14、赫夫曼树是带权路径长度最小的二叉树，又称最优二叉树，路径上权值较大的结点离根较近。15、structnode*rchildT=NULL16、二叉树由_根结点__，__左子树_，_右子树__三个基本单元组成。17、树的链表存储结构常用的有三种，其中，双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关27、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历28、图的广度优先遍历算法类似于树的（）。A.中根遍历 B.先根遍历 C.后根遍历 D.按层次遍历29、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．030、设有n个结点的无向图，该图至少应有()条边才能确保是一个连通图。A．n-1B．nC．n+1D．nlogn；31、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于032、要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n33、下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程34、无向图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,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b35、若一个连通图有n个顶点,则它的生成树有（）条边。A.n B.n-1 C.n+1 D.n(n-1)/2二、填空题22、邻接多重表适于表示稀疏无向图，邻接表、逆邻接表和十字链表适于表示稀疏有向图。23、设有向图的顶点个数为n，则该图最多有n(n-1)条弧。24、右图中顶点D的出度是3。25、8层完全二叉树至少有_128(第七层满，加第八层１个)_个结点，拥有100个结点的完全二叉树的最大层数为__7__。26、求图的最小生成树有两种算法：_普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。其中，_克鲁斯卡尔____算法适合于求_边稀疏___的稀疏图的最小生成树。普里姆算法适用于求边稠密的网的最小生成树。27、对于含n个顶点e条边的无向连通图，利用普里姆算法生成最小代价生成树其时间复杂度为__O(n2）_，利用克鲁斯卡尔算法生成最小代价生成树其时间复杂度为_O(eloge)__。28、在无向图的深度优先遍历算法中，DFS（从某个顶点出发深度优先遍历图的算法）被调用了几次就说明该图有几个联通分量。29、一个有n个结点的图，最少有1个连通分量，最多有n个连通分量。30、判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图。31、有向图G的强连通分量是指__有向图的极大强连通子图____。32、右图中的强连通分量的个数为3个。33、一个连通图的__生成树____是一个极小连通子图。34、若用n表示图中顶点数目，则有___n(n-1)/2___条边的无向图成为完全图。35、已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先_遍历方法。36、为实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列__存放被访问的结点以实现遍历。37、设无向图G有n个顶点，m条边。阅读下面用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号），并在画线处完成填空。voidCreatGraph(AdjListg)ertex);g[i].firstarc=null;}for(k=1;k<=m;k++)irstarc;g[i].firstarc=p;irstarc; g[j].frstarc=p;}}三、简答题4、已知一个无向网的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示(1)画出该无向网图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。答案：(1)该无向网图形如下：dd1aebc54362深度优先序列为：abcde；广度优先序列为：abdce36、适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序37、对有18个元素的有序表A作折半查找，则查找A[3]的比较序列的下标为（），2，3，5，2，3，5，3，4，2，338、对有14个数据元素的有序表R进行折半搜索，搜索到R[3]的关键字等于给定值，查找过程中元素比较的顺序依次为（）。A.R[6],R[2],R[4],R[3] B.R[6],R[4],R[2],R[3]C.R[0],R[1],R[2],R[3] D.R[0],R[13],R[2],R[3]39、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A．（N+1）/2B.N/2C.ND.[（1+N）*N]/240、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。A．35/1212121241、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减42、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。B.3C.443、在查找过程中，只完成查找操作，这种查找称为（）A.静态查找 B.动态查找 C.内部查找 D.外部查找44、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)二、填空题对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是不同的，对于查找成功,他们的平均查找长度是相同的。执行顺序查找时，储存方式可以是__顺序存储或链式存储__，二分法查找时，要求线性表__顺序存储且有序__。40、在数据结构中一般采用平均查找长度衡量查找算法时间性能，而对于排序算法一班通过统计记录的比较次数和移动次数衡量排序算法的时间性能。二叉查找树的查找效率与二叉树的树型有关,在呈单枝树时其查找效率最低。若表中元素个数为n，则顺序查找该表中的元素，若查找成功，则比较关键字的次数最多为__n__次，平均比较次数为(n+1)/2；若进行折半查找，则最大比较次数是__㏒2n」+1。44、给定一个主关键字，在长为n的有序表中进行折半查找，则最多经过log2n+1次比较即可确定该关键字是否在表中，至少经过1次比较即可确定该关键字在表中。在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为__4__。在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_6,9,11,12。己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需____2______次查找成功，47时_____4_____成功，查100时，需______3____次才能确定不成功。假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为___37/12____。49、在查找中，能够唯一标识一个记录的关键字称之为主关键字，能够标识若干记录的关键字称之为次关键词。动态查找表和静态查找表的重要区别在于前者包含有__插入__和_删除_运算，而后者不包含这两种运算。已知二叉排序树的左右子树均不为空，则____左子树______上所有结点的值均小于它的根结点值，_____右子树_____上所有结点的值均大于它的根结点的值。三、简答题5、设有序表为(a,b,c,d,e,f,g,h,i,j,k,p,q)，请分别画出对给定值a,g和n进行折半查找的过程。【答案】（1）查找a的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。（2）g的查找过程如下，一次比较成功。

[a

b

c

d

e

f

(g)

h

i

j

k

p

q

]（3）n的查找过程如下，

经过四次比较，查找失败。6、构造有12个元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少（2）查找长度为1、2、3、4的元素各有多少具体是哪些元素（3）查找第5个元素依次要比较哪些元素（4）试求解在等概率情况下，查找成功情况下二分查找的平均查找长度。【答案】12个元素的二叉判断树如下图所示：

（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。（4）根据,平均查找长度ASL=（1+2*2+4*3+5*4）/12=37/127、设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。答案：8、已知序列40，30，50，24，28，46，60，10。试画出由该输入序列构成的二叉排序树，并分别给出依次执行下列操作后的二叉排序树（共画四棵树）（1）插入数据42和80；（2）删除数据30；（3）删除数据50。答案：45、n个记录进行直接插入排序时，记录最小的比较次数是()A.(n-1) C.(n+3)(n-2)/2 246、对n个记录进行希尔排序，所需要的辅助存储空间为（）。（1og2n）（n）（1）（n2）就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速直接插入排序在最好情况下的时间复杂度为（）A．O(logn)B．O(n)C．O(n*logn)D．O(n2)49、以下算法思路分别出自什么排序算法：取当前最小的数，插入到已经排好序的数据末尾：（）；取当前要排序的数，插入到已经排好序的数据中适当位置：（）；相邻两个数比较，如果大小顺序颠倒就把两者交换过来：（）。A.插入排序、选择排序、起泡排序 B.选择排序、插入排序、起泡排序C.插入排序、选择排序、快速排序 D.选择排序、插入排序、快速排序51、下列四种排序算法中，哪一个需要采用递归调用的方式实现A、直接插入排序 B、快速排序 C、冒泡排序 D、折半插入排序从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。A.插入B.选择C.希尔D.快速快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。A.选择B.冒泡C.快速D.插入55、在希尔排序算法中，需要借助（）实现A、直接插入排序 B、快速排序 C、冒泡排序 D、折半插入排序若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A.3B.10C.15D.25在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（）。A.直接插入排序B.起泡排序C.快速排序D.选择排序对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是()。A．直接插入B.起泡排序C.快速排序D.二分法插入若采用希尔排序法对序列{12,36,21,7,2,19,6,31,49,13,27,38,5}进行排序，增量分别为5、3、1。那么当增量为3时，排序结束后的序列是哪一个A.{5,2,19,6,27,21,7,31,38,12,36,49,13}B.{12,6,5,7,2,19,36,21,49,13,27,38,31}C.{7,2,5,12,6,19,13,21,38,31,27,49,