数据结构期末复习题

1数据结构期末复习题一、单选题1．设有两个串T和P，求P在T中首次出现的位置的串运算称作()。A.联接B.求子串C.字符定位D.子串定位2．8×8的整型数组A，其每个数组元素占2个字节，已知A[0][0]在内存中的地址是100，按列主序，A[5][6]的地址是()。A.192B.206C.92D.1063．一个具有767个结点的完全二叉树，其叶子结点个数为（）。A.383B.384C.385D.3864．具有65个结点的完全二叉树的高度为（）。（根的层次号为0）A.8B.7C.6D.55．一个数组元素a[i]与（）的表示等价。A.*(a+i)B.a+iC.*a+iD.&a+i6．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于()。A.2^(h-1)B.2^(h+1)C.2^(h-1)D.2^h7.已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS种元素e的运算是（）A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))8．串S=’software’,其子串的数目是（）。A.8B.37C.36D.99.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。A.n-2B.n-1C.nD.n+110.设有一个n*n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/211．在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()。A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;12．下列算法的时间复杂度为（）。for(i=1；im；i++)for(j=i+1；jn；j++)a[i][j]=i*j;A.O(m*n)B.O(n2)C.O(m2)D.O(m+n)13．研究数据结构就是研究（）。A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和数据的存储结构D.数据的逻辑结构、存储结构及其数据的抽象运算。14.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()。A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致。2C.每个数据元素都一样。D.数据元素所包含的数据项的个数要相等。15．假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是（）。A.front+1==rearB.front==rear+1C.front==0D.front==rear16.假定一个顺序循环队列存储于数组A[n]中，队首和队尾指针分别用front和rear表示，则判断队满的条件是()。A.（rear-1）%n==frontB.（rear+1）%n==frontC.rear==（front-1）%nD.rear==（front+1）%n17．若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）。A．上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵18.如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。（）就是不稳定的排序方法。A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序19．在一棵具有5层的满二叉树中结点数为（）。A．31B.32C.33D.1620.5阶B树中，每个结点最多有（）个关键码。A．2B．3C．4D．521、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A．O(n)B．O(1)C．O(n2)D．O(log2n)22、设单链表中结点的结构为（data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（）A．s-link=p-link;p-link=s；B．q-link=s;s-link=p；C．p-link=s-link;s-link=p；D．p-link=s;s-link=q；23、若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，224、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）A．较快B．较慢C．相同25、树中所有结点的度等于所有结点数加（）A．0B．1C．-1D．226、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．nB．n-1C．n+1D．2*n27、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）A．n/2B．(n+1)/2C．(n–1)/2D．n/428、在无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个（）A．顶点序列B．边序列C．权值总和D．边的条数29、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A．起泡排序B．快速排序C．堆排序D．直接选择排序30、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表3项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。（设搜索成功的平均搜索长度为Snl={1+1/(1-α)}/2其中α为装填因子）A．400B．526C．624D．676二、填空题1．在程序运行过程中不能扩充的数组是分配的数组。这种数组在声明它时必须指定它的大小。2．将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素A[I][J]，如果它能够在数组B中找到，则它应在位置。3．链表适用于查找。4．队列的插入操作在进行，删除操作在进行。5．设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为。6．通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。7．广义表A（（a，b，c），（d，e，f））的表尾为。8．在一棵树中，结点没有前驱结点。9．一棵树的广义表表示为a（b（c，d（e，f），g（h）），i（j，k（x，y））），结点k的所有祖先的结点数为个。10．根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为的结点时需要进行旋转调整。11.快速排序算法的最坏情况的时间复杂度是。12.文件可以有多种不同的组织方式：顺序文件、散列文件、和倒排文件。13.B－树的一个变体用于文件的动态索引结构，被称为。14.冒泡排序算法的最坏情况的时间复杂度是。15.一棵树中结点的后根序列与对应二叉树中结点的___序列相同。16．在具有n个结点的中根线索二叉树中，非空指针的个数是。17.给出所有不同形态的二叉树，它们的先根序列和后根序列完全相同：______。18.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。19.对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为N，所有边链表中边结点的总数为。20．判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用。21.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为________。假定树根结点的层数为0。22.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。23.含有n个结点的树有多少条边________。24.一个连通图的生成树是该图的连通子图。若这个连通图有N个顶点,则它的生成树有条边。25.能够成功完全拓扑排序的图一定是一个____________。26.数组是一种态的数据结构，其上未定义运算。7.一棵树中结点的4后根序列与对应二叉树中结点的_____序列相同。27．在具有n个结点的中根线索二叉树中，非空指针的个数是。三、判断题（）1.连通分量是无向图中的极小连通子图；（）2.强连通分量是有向图中的极大强连通子图；（）3.霍夫曼树一定是完全二叉树。（）4.有n个结点的不同的二叉树有n！棵。（）5.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。（）6.二维数组可以视为数组元素为一维数组的一维数组。（）7.链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。（）8．在用单链表表示的链式队列中，队头在链表的链尾位置。（）9．凡是递归定义的数据结构都可以用递归算法来实现它的操作。（）10．当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。（）12．进行折半搜索的表必须是顺序存储的有序表。（）13．一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。（）14．在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。（）15．一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。（）16.若让元素1，2，3依次进栈，则出栈次序不可能出现2，1，3的情况。（）17.假定一个链式队列的对头和对尾指针分别为front和rear，则判断对空的条件为front==rear（）18.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。（）19.对于AOE网络，加速任一关键活动都能使整个工程提前完成。（）20.由树转化成二叉树，其根的右子女指针总是空的。四、问答题1．高度为h的满二叉树,如果按层次自上而下，同层从左到右的次序从1开始编号，试问:（1）该树上有多少个结点？（2）编号为i的结点的父结点（若存在）的编号是多少？2．右图所示的二叉搜索树上（1）依次插入28和33，画出结果二叉搜索树（2）依次删除30和56，画出结果二叉搜索树。53．设有n个顶点的无向连通加权图G。（1）以顶点1为起始顶点，用普里姆算法求图G的一棵最小代价生成树，并画出之。（2）计算该生成树的代价。4．设有有向图如下所示。用迪杰斯特拉算法求以顶点1为源点的单源最短路径。要求写出一维数组d在执行该算法的过程中各步的状态。数组d中保存最短路径的长度。5．设有关键字序列20，40，30，60，50，70，90，对其进行直接插入排序和快速排序。快6速排序的分割元素为序列左起第一个元素。（1）分别指出每个算法的稳定性。（2）分别写出两种算法的排序过程。6．设有向图G如下图所示，给出其邻接矩阵和邻接表两种存储结构；给出对上题的有向图进行拓扑排序的各种可能的拓扑序列。7．对于一个n×n的矩阵A的任一矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元d相同）78．设有一个求解汉诺塔（Hanoi）的递归算法voidHANOI(intn,intpeg1,intpeg2,intpeg3){if(n==1)cout“move”peg1“to”peg3end1;else{HANOI(n-1,peg1,peg3,peg2);cout“move”peg1“to”peg3end1;HANOI(n-1,peg2,peg1,peg3);}}假定采用HANOI（3，1，2，3）去调用上述算法，则写出整