数据结构复习题(答案)

选择题：1、与顺序表相比，用链表表示线性表的优点是（）。A.便于随机存取B.便于元素的插入和删除操作C.存储的密度较高D.元素的物理顺序与逻辑顺序一致2、以下数据结构中，（）是线性结构。A.无向网B.队列C.二叉检索树D.有向无环3、在长度为n的顺序表中，向第k个元素（1≤k≤n+1）之前插入一个新元素时，需向后移动（）个元素。A.n-kB.n-k+1C.n-k-1D.k4、在长度为n的顺序表中，删除第k个元素（1≤k≤n+1）时，需向前移动（）个元素。A.n-kB.n-k+1C.n-k-1D.k5、与顺序栈相比，链栈的主要优点在于（）。A.入栈操作更加方便B.出栈操作更加方便C.通常不会出现栈满D.通常不会出现栈空6、用大小为n的一维数组S存储一个栈，令S[0]为栈底，变量top表示当前栈顶的位置（下标），即S[top]为栈顶元素。则，元素出栈后top应做如下（）的修改。A.top--;B.top++;C.top=n-1;D.top=-1;7、以链表作为栈的存储结构，令Sp为栈顶指针，栈空的判定条件是（）。A.Sp==NULLB.Sp=-1C.Sp!=NULLD.Sp!=-18、在一个单链表中，若要删除指针p所指向结点的后继结点，则需执行（）中的语句。A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p=p-next-next;D.p-next=p;9、设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是a2,a4,a3,a6,a5,a1，则栈S至少可以容纳（）个元素。A.3B.4C.5D.610、若进栈序列为a1、a2、a3、a4，进栈过程允许出栈，则下列出栈序列中，（）是不可能的。A.a1、a3、a4、a2B.a2、a4、a3、a1C.a3、a4、a2、a1D.a1、a4、a2、a311、设有一个大小为m的数组表示循环队列，若f表示当前队头元素在数组中的前一位置，r表示队尾元素的所在位置，则计算队列中元素个数的表达式为（）。A.r-fB.(m-f-r)%mC.(m+f-r)%mD.(m+r-f)%m12、在大小为n的循环队列中，假定front指示队头的位置，rear指示队尾的后一位置，则判定队空的条件是（）。A.rear==n-1B.(front+1)%n==rearC.front==rearD.front==(rear+1)%n13、深度为7的二叉树至多有（）个结点。A.127B.255C.128D.25614、n个结点的二叉树，其最小深度是（）。A.log2n+1B.log2nC.n/2D.n15、设二叉树中任一结点的值大于其左子树中每个结点的值，而小于其右子树中每个结点的值，即它是一个二叉排序树。则中序遍历该二叉树时，访问结点的序列是一个值（）的序列。A.递减B.递增C.先递减后递增D.先递增后递减16、以顺序存储方式将完全二叉树中的所有结点逐层存放于数组A中，结点A[i]若有左孩子，则结点（）是其左孩子。A.A[2*i]B.A[2*i+1]C.A[2*i+2]D.A[i/2]17、由3个结点可以构成（）棵形态不同的树，或构成（）棵形态不同的二叉树。A.2B.3C.4D.518、在下列存储形式中，（）不适合于树。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法19、某二叉树如图所示，对该二叉树进行中序遍历，结点的访问序列为（）。A.1,2,3,4,5,6,7B.1,2,4,6,3,5,7C.2,6,4,1,5,7,3D.6,4,2,1,3,5,720、某二叉树如图所示，对该二叉树进行先序遍历的结点序列为（）。A.1,2,3,4,5,6,7B.1,2,4,6,7,3,5C.2,6,4,7,1,5,3D.6,7,4,2,5,3,121、有n个顶点的无向完全图中，具有（）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n222、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵中元素的个数为（）。A.nB.(n-1)2C.(n+1)2D.n223、对图所示的无向图G，从顶点①开始，广度优先遍历，可能的顶点访问顺序为（）。A.①,②,③,④,⑤,⑥,⑦,⑧B.①,②,⑥,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧24、对上一题的图G，从顶点①开始，深度优先遍历，则可能的顶点访问顺序为（）。A.①,②,③,④,⑤,⑥,⑦,⑧B.①,②,⑥,③,④,⑦,⑧,⑤C.①,②,⑥,③,④,⑤,⑦,⑧D.①,②,③,⑤,④,⑥,⑦,⑧25、有向图G有n个顶点，其邻接矩阵为A（二维数组），G中第k个顶点的度为（）。A.1k0i]i][i[AB.1n0i]i][1k[AC.1n0i1n0i]1k][i[A]i][1k[AD.1k0i]1k][i[A+1k0i]i][1k[A26、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均检索长度）为（）。A.nB.n/2C.(n+1)/2D.(n-1)/227、设检索表（a1,a2,a3,...,a32）中有32条记录，且已按关键字递增有序排列，采用二分法检索一个与给定的键值K相等的记录，若a1.keyKa2.key，则检索过程中K与记录关键字的比较次数为（）。A.3B.4C.5D.628、哈希检索的基本思想是依据关键字值的简单换算来决定（）。A.记录的存储地址B.记录的序号C.平均检索长度D.哈希表空间29、设有一个用线性探测法解决冲突得到的哈希表（哈希函数：H(key)=key%11）：0123456789101325801617614若要检索关键字值为14的记录，探测（比较）的次数是（）。A.1B.6C.7D.830、设计一个用线性探测法解决冲突的哈希表（哈希函数：H(key)=key%17），其地址区间为0..16，现将关键字值分别为26、25、72、38、8、18、59的记录依次存储到哈希表中。关键字值为59的记录在哈希表中的地址（下标）是（）。A.8B.9C.10D.1131、用直接插入排序法对下面4个序列进行递增（由小到大）排序，元素比较次数和移动次数最少的是（）。A.10,3,4,9,8,6,2,7B.2,3,6,4,8,7,9,10C.3,4,2,6,7,10,9,8D.9,7,8,6,2,3,10,432、对10个记录的序列：4,3,6,9,7,1,2,5,0,8进行排序，若采用快速排序，一趟分割之后序列的次序是（）。A.3,4,6,9,1,7,2,5,0,8B.0,3,2,1,4,7,9,5,6,8C.3,4,6,1,7,2,5,0,8,9D.1,2,5,0,8,4,3,6,9,733、对10个记录的序列：4,3,6,9,7,1,2,5,0,8用归并排序方法进行一趟归并后的结果为（）。A.3,4,6,9,1,7,2,5,0,8B.0,3,2,1,4,7,9,5,6,8C.3,4,6,1,7,2,5,0,8,9D.1,2,5,0,8,4,3,6,9,734、以下排序算法中，时间复杂度最高的是（）。A.希尔排序B.归并排序C.冒泡排序D.堆排序35、以下排序算法中，需要附加的内存空间最小的是（）。A.归并排序B.快速排序C.堆排序D.树形选择排序36、以下排序算法中，时间复杂度最小的是（）。A.二分插入排序B.直接选择排序C.冒泡排序D.归并排序37、对n个元素进行快速排序，所需要的辅助存储空间为（）。A.O(1)B.O(n)C.O(log2n)D.O(n2)是非题：1、在顺序表中定位第i个元素所花费的时间与i成正比。（×）2、在单链表中访问第i个元素所花费的时间与i成正比。（√）3、链式存储结构的优点是存储密度大，且插入和删除运算的效率高。（×）4、栈和队列都是顺序存储的线性结构。（×）5、“后进先出”不符合栈的特性。（×）6、一个2维数组可以视为其数据元素是1维数组的线性表。（√）7、空表就是所有元素都为0的表。（×）8、顺序存储结构不仅适宜表示完全二叉树，也完全适宜表示一般的二叉树。（×）9、二叉树先序遍历序列的最后一个结点，必是其中序遍历序列中的最后一个结点。（×）10、不使用递归也能实现二叉树的遍历。（√）11、一个无向图的邻接表中表结点的个数与边的个数一致。（×）12、一个有向图的邻接表和逆邻接表中表结点的个数不一定相等。（×）13、邻接表只能用于有向图的存储。（×）14、邻接矩阵只能用于表示无向图的顶点关系。（×）15、n（n3）个带权叶子结点可以构成多棵哈夫曼树（最优二叉树）。（√）16、无向连通网存在最小生成树问题，而有向图不存在最短路径问题。（×）17、运用二分检索时，检索表中的元素必需以关键字递增（由小到大）有序排列。（×）18、哈希表中若不存在地址冲突或同义词，则其成功检索的平均检索长度等于1。（√）19、二路归并排序的核心操作是将两个有序序列合并为一个有序序列。（√）20、顺序检索表中的记录关键字递减（由大到小）有序时，不宜运用折半检索。（×）21、通常，选择排序比插入排序的元素交换次数要少。（√）22、对n个元素的集合进行归并排序时，需要的辅助存储空间为O(log2n)。（×）填空题：1、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行如下操作：s-next=p-next;p-next=s;2、在一个单链表中，要删除指针p所指向结点的后继结点，应执行如下操作：p-next=p-next-next;3、在一个链栈中，Top为指向栈顶的指针，p所指向的结点入栈时，应顺序执行如下操作语句：p-next=Top;Top=p;4、栈中的最后一个元素称为栈顶。队列的第一个元素称为队首。5、栈作为函数局部数据空间的数据结构。队列作为文件缓冲区的数据结构。6、size个结点的循环队列中，front指示当前队头的位置（下标），rear指示当前队尾的后一位置。那么，在元素出队前，要执行front=(front+1)%size;语句；在元素入队前，要执行rear=(rear+1)%size;语句。7、64个结点的完全二叉树中，有32个分枝结点，有32个叶子结点。8、有15个结点的二叉树的二叉链表中，共有30个指针，其中有14个指针用于指向左、右孩子，剩余的16个指针为空。9、一棵深度为6的满二叉树中，叶子结点的个数为32，分支结点的个数为31。10、在有9个顶点的有向完全图中，共有72条弧。11、在有9个顶点的无向完全图中，共有36条边；而其生成树中，有8条边。12、各种选择排序算法中，最优的时间复杂度为O(nlog2n)；最糟的时间复杂度为O(n2)。13、各种排序算法中，最优的空间复杂度为O(1)；最坏的空间复杂度为O(n)。14、含有n个顶点的有向图的邻接矩阵为A（Ai,j是其第i行、第j列元素），计算第i个顶点的出度公式为n1jijA；计算其入度的公式为n1jAji。15、哈希（散列）检索的平均检索长度可以趋近于1。16、平衡二叉检索树是指其任一结点的左子树与右子树深度的差不大于1的二叉检索树。17、在连通的无向图中，求解指定源点到指定终点的最短路径，可以采用广度优先搜索算法。18、求解连通网最小生成树的Prim算法的时间复杂度为O(n2)，而Kruscal算法适用于边稀疏（e=nlog2n）的连通网。应用题：1、已知一棵二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDAHGF，试画出该二叉树。2、试分别画出下面二叉树的二叉链表，并分别写出先序遍历和中序遍历该二叉树的结点访问序列。3、如下无向图的顶点依次存储为a、b、c、d和e，试画出该图的邻接表。4、如下有向图的顶点依次存储为A,B,C,D,E和F，试画出该图的邻接矩阵。5、有向图的邻接矩阵如下所示，顶点的次序依次为A,