“数据结构”复习题

选择题：1、与顺序表相比，用链表表示线性表的优点是（）。A.便于随机存取B.便于元素的插入和删除操作C.存储的密度较高D.元素的物理顺序与逻辑顺序一致2、以下数据结构中，（）是线性结构。A.无向网B.队列C.二叉检索树D.有向无环3、在长度为n的顺序表中，向第k个元素（1≤k≤n+1）之前插入一个新元素时，需向后移动（）个元素。A.n-1B.n-k+1C.n-k-1D.k4、在长度为n的顺序表中，删除第k个元素（1≤k≤n+1）时，需向前移动（）个元素。A.n-1B.n-k+1C.n-kD.k5、与顺序栈相比，链栈的主要优点在于（）。A.入栈操作更加方便B.出栈操作更加方便C.通常不会出现栈满D.通常不会出现栈空6、用大小为n的一维数组S存储一个栈，令S[n-1]为栈底，变量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.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,4032、对10个记录的序列：48,37,65,93,72,16,27,50,9,53进行排序，若采用快速排序，一趟分割之后序列的次序是（）。A.37,48,65,93,16,72,27,50,9,53B.9,37,27,16,48,72,93,50,65,53C.37,48,65,16,72,27,50,9,53,93D.16,27,50,9,53,48,37,65,93,7233、以下排序算法中，时间复杂度最高的是（）。A.希尔排序B.归并排序C.快速排序D.堆排序34、以下排序算法中，需要附加的内存空间最大的是（）。A.插入排序B.选择排序C.快速排序D.归并排序判断题：1．线性表的链式存储结构优于顺序存储结构。（）2．一个n维数组可视为其数据元素为n-1维数组的线性表。（）3．空栈就是所有数据元素都是0的栈。（）4．邻接表只能用于有向图的存储。（）5．散列检索的平均检索长度为1。（）6．对n个记录的集合进行快速排序，所需的平均时间是O(nlog2n)。（）7．堆排序所需额外的记录辅助空间与待排序的记录个数无关。（）8．完全二叉树的顺序存储结构中，数据元素的存储顺序是其先序遍历的次序。（）9．栈和队列都是顺序存储的线性结构。（）10．以邻接矩阵表示图中顶点间的关系时，其所需空间与边或弧的数量有关。（）11．对n个记录进行归并排序所需额外的记录存储空间是O(log2n)。（）12．栈的特性是“后进先出”。（）13对二叉检索树进行先序遍历的序列是个递增或递减有序的序列。（）14．当待排序的数据元素个数很大时，为交换元素的位置，移动元素将耗用较多的时间，这是影响时间复杂度的主要因素。（）15．在顺序表中删除某个数据元素时，元素移动的次数与该元素的位置无关。（）16．带权图的最小生成树是唯一的。（）17．孩子-兄弟链表存储的树的先序遍历序列与其对应的二叉树的先序序列不同。（）18．不使用递归，也能实现二叉树的先序、中序和后序遍历。（）19．二叉检索树的平均检索长度是log2(n+1)-1。（）20．链式存储结构中的每个结点都包含一个指针。（）21．邻接矩阵为对称矩阵的图一定是无向图。（）22．n个叶子结点带权路径长度总和最小的唯一二叉树是最优二叉树。（）填空题：1．在一个单链表中，在指针p所指结点之后插入指针q所指结点，应执行s-next=;和p-next=;语句。2．是实现递归函数调用的数据结构；是打印数据缓冲区的数据结构。3．具有n个顶点的图的生成树中含有条边。4．对于n个顶点e条边的无向图，其邻接表中有个顶点。5．n个结点的循环队列的头指针front指示队头的下标，尾指针rear指向队尾之后的下标，则判定队列为空的条件是，判定队列满的条件是，入队后尾指针应计为，出队后头指针应计为，计算队长的表达式是。6．对线性序列（18，25，63，50，42，32，90）散列存储，若选用H(key)=key%9作为散列函数，则元素18的同义词有个，元素90的检索长度是。7．一个深度为h的完全二叉树最多有个结点，最少有个结点。8．树的三种常用存储结构是、和。9．二叉树第i层上最多有个结点，最少有个结点。10．n个结点的二叉链表中，有个空指针。11．排序算法中重复的基本操作是和。12．设有二维数组A[9][19]，其每个元素占用一个内存单元，数组以列为主序存储，第一个元素的地址为100，那么元素A[6][6]的存储地址是。13．32个结点的二叉树中有10个叶子结点，则该二叉树中有个1度结点和个2度结点。14．n个记录的顺序检索表的平均检索长度是。15．二叉树的遍历有、、和。16．遍历图的邻接矩阵第i行可以统计第i个顶点的度，遍历第i列可以统计第i个顶点的度。17．检索方法的平均检索长度与记录的个数n无关。18．栈中的最后一个数据元素称为，队列中的第一个数据元素称为。19．将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动的排序方法称为。20．一个连通图的连通分量有个。应用题：1．试分别画出下面二叉树的二叉链表和静态二叉链表。2．有向图G如图所示，顶点的次序依次为A,B,C,D,E，试写出该图的邻接矩阵和邻接表。3．已知顺序表中存储的序列{19,14,22,1,66,21,83,27,56,13}，将元素按其在表中的次序依次插入到一棵初始为空的二叉排序树中，画出插入完成后的二叉排序树，并计算在等概率的情形下，在该二叉排序树上成功检索的平均检索长度。4．已知一棵二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDAHGF，试画出该二叉树。5．无向图G的顶点依次为a、b、c、d和e，其邻接矩阵如下，试画出该图。01010101010101110101011106．有一个如右所示的无向连通图，顶点存储次序为a,b,c,d,e,f,g,h。（20分）⑴从顶点a出发，采用深度优先搜索，画出所得该图的深度优先生成树；⑵从顶点a出发，采用广度深度优先搜索，画出该图的广度优先生成树；⑶采用Prim算法，画出其求解最小生成树的每一步骤；⑷采用Kruscal算法，画出其求解最小生成树的每一步骤。7．已知某通讯电文中仅使用A、B、C、D、E等5中符号，且这些符号在电文中分别出现27、14、5、76、21次，试以这5个符号设计（画出）哈夫曼树，并写出其哈夫曼编码。编程题：1．有一个