数据结构复习题23624

1、选择题：1、与顺序表相比，用链表表示线性表的优点是（ ）。A. 便于随机存取 B. 便于元素的插入和删除操作C. 存储的密度较高 D. 元素的物理顺序与逻辑顺序一致2、以下数据结构中，（ ）是线性结构。A. 无向网 B. 队列 C. 二叉检索树 D. 有向无环3、在长度为n的顺序表中，向第k个元素（1kn+1）之前插入一个新元素时，需向后移动（ ）个元素。A. n-1 B. n-k+1 C. n-k-1 D. k4、在长度为n的顺序表中，删除第k个元素（1kn+1）时，需向前移动（ ）个元素。A. n-1 B. n-k+1 C. n-k D. k5、与顺序栈相比，链栈的主要优点在于（ ）。A.

2、 入栈操作更加方便 B. 出栈操作更加方便C. 通常不会出现栈满 D. 通常不会出现栈空6、用大小为n的一维数组S存储一个栈，令Sn-1为栈底，变量top表示当前栈顶的位置（下标），即Stop为栈顶元素。则，元素出栈后top应做如下（ ）的修改。A. top-; B. top+;C. top = n-1; D. top = -1;7、以链表作为栈的存储结构，令Sp为栈顶指针，栈空的判定条件是（ ）。A. Sp = NULL B. Sp >= -1C. Sp != NULL D. SP != -18、在一个单链表中，若要删除指针p所指向结点的后继结点，则需执行（ ）中的语句。A. p-&g

3、t;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. 3 B. 4 C. 5 D. 610、若进栈序列为a1、a2、a3、a4，进栈过程允许出栈，则下列出栈序列中，（ ）是不可能的。A. a1、a3、a4、a2

4、B. a2、a4、a3、a1C. a3、a4、a2、a1 D. a1、a4、a2、a311、设有一个大小为m的数组表示循环队列，若f表示当前队头元素在数组中的前一位置，r表示队尾元素的所在位置，则计算队列中元素个数的表达式为（ ）。A. r-f B. (m-f-r) % mC. (m+f-r) % m D. (m+r-f) % m12、在大小为n的循环队列中，假定front指示队头的位置，rear指示队尾的后一位置，则判定队空的条件是（ ）。A. rear=n-1 B. (front+1) % n=rearC. front=rear D. front=(rear+1) % n13、深度为7的二

5、叉树至多有（ ）个结点。A. 127 B. 255 C. 128 D. 25614、n个结点的二叉树，其最小深度是（ ）。A. log2n+1 B. log2n C. n/2 D. n15、设二叉树中任一结点的值大于其左子树中每个结点的值，而小于其右子树中每个结点的值，即它是一个二叉排序树。则中序遍历该二叉树时，访问结点的序列是一个值（ ）的序列。A. 递减 B. 递增C. 先递减后递增 D. 先递增后递减16、以顺序存储方式将完全二叉树中的所有结点逐层存放于数组A中，结点Ai若有左孩子，则结点（ ）是其左孩子。A. A2*i B. A2*i+1 C. A2*i+2 D. Ai/217、由3个

6、结点可以构成（ ）棵形态不同的树，或构成（ ）棵形态不同的二叉树。A. 2 B. 3 C. 4 D. 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,

7、 4, 6, 7, 3, 5C. 2, 6, 4, 7, 1, 5, 3D. 6, 7, 4, 2, 5, 3, 121、有n个顶点的无向完全图中，具有（ ）条边。A. n(n-1)/2 B. n(n-1) C. n(n+1)/2 D. n222、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵中元素的个数为（ ）。A. n B. (n-1)2C. (n+1)2 D. n223、对图所示的无向图G，从顶点开始，广度优先遍历，可能的顶点访问顺序为（ ）。A. , , , , , , , B. , , , , , , , C. , , , , , , , D. , , , , , , , 24

8、、对上一题的图G，从顶点开始，深度优先遍历，则可能的顶点访问顺序为（ ）。A. , , , , , , , B. , , , , , , , C. , , , , , , , D. , , , , , , , 25、有向图G有n个顶点，其邻接矩阵为A（二维数组），G中第k个顶点的度为（ ）。A. B. C. D. +26、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均检索长度）为（ ）。A. n B. n/2 C. (n+1)/2 D. (n-1)/227、设检索表（a1, a2, a3, ., a32）中有32条记录，且已按关键字递增有序排列，采用二分法检索一个与

9、给定的键值K相等的记录，若a1.key<K<a2.key，则检索过程中K与记录关键字的比较次数为（ ）。A. 3 B. 4 C. 5 D. 628、哈希检索的基本思想是依据关键字值的简单换算来决定（ ）。A. 记录的存储地址 B. 记录的序号C. 平均检索长度 D. 哈希表空间29、设有一个用线性探测法解决冲突得到的哈希表（哈希函数：H(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要检索关键字值为14的记录，探测（比较）的次数是（ ）。A. 1 B. 6 C. 7 D. 834、以下排序算法中，需要附加的内存空间最大的

10、是（ ）。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序判断题：1线性表的链式存储结构优于顺序存储结构。（ ）2一个n维数组可视为其数据元素为n-1维数组的线性表。（ ）3空栈就是所有数据元素都是0的栈。（ ）4邻接表只能用于有向图的存储。（ ）5散列检索的平均检索长度为1。（ ）6对n个记录的集合进行快速排序，所需的平均时间是O(nlog2n)。（ ）7堆排序所需额外的记录辅助空间与待排序的记录个数无关。（ ）8完全二叉树的顺序存储结构中，数据元素的存储顺序是其先序遍历的次序。（ ）9栈和队列都是顺序存储的线性结构。（ ）10以邻接矩阵表示图中顶点间的关系时，其所需空间与边或

11、弧的数量有关。（ ）11对n个记录进行归并排序所需额外的记录存储空间是O(log2n)。（ ）12栈的特性是“后进先出”。（ ）13对二叉检索树进行先序遍历的序列是个递增或递减有序的序列。（ ）14当待排序的数据元素个数很大时，为交换元素的位置，移动元素将耗用较多的时间，这是影响时间复杂度的主要因素。（ ）15在顺序表中删除某个数据元素时，元素移动的次数与该元素的位置无关。（ ）16带权图的最小生成树是唯一的。（ ）17孩子-兄弟链表存储的树的先序遍历序列与其对应的二叉树的先序序列不同。（ ）18不使用递归，也能实现二叉树的先序、中序和后序遍历。（ ）填空题：1在一个单链表中，在指针p所指结点

12、之后插入指针q所指结点，应执行s->next= ; 和p->next= ;语句。2 是实现递归函数调用的数据结构； 是打印数据缓冲区的数据结构。3具有n个顶点的图的生成树中含有 条边。4对于n个顶点e条边的无向图，其邻接表中有 个顶点。5n个结点的循环队列的头指针front指示队头的下标，尾指针rear指向队尾之后的下标，则判定队列为空的条件是 ，判定队列满的条件是 ，入队后尾指针应计为 ，出队后头指针应计为 ，计算队长的表达式是 。6对线性序列（18，25，63，50，42，32，90）散列存储，若选用H(key)=key %9作为散列函数，则元素18的同义词有 个，元素90的检

13、索长度是 。7一个深度为h的完全二叉树最多有 个结点，最少有 个结点。8树的三种常用存储结构是 、 和 。9二叉树第i层上最多有 个结点，最少有 个结点。10n个结点的二叉链表中，有 个空指针。11排序算法中重复的基本操作是 和 。12设有二维数组A919，其每个元素占用一个内存单元，数组以列为主序存储，第一个元素的地址为100，那么元素A66的存储地址是 。1332个结点的二叉树中有10个叶子结点，则该二叉树中有 个1度结点和 个2度结点。14n个记录的顺序检索表的平均检索长度是 。15二叉树的遍历有 、 、 和 。16遍历图的邻接矩阵第i行可以统计第i个顶点的 度，遍历第i列可以统计第i个

14、顶点的 度。17 检索方法的平均检索长度与记录的个数n无关。18栈中的最后一个数据元素称为 ，队列中的第一个数据元素称为 。19将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动的排序方法称为 。20一个连通图的连通分量有 个。应用题：1试分别画出下面二叉树的二叉链表和静态二叉链表。2有向图G如图所示，顶点的次序依次为A, B, C, D, E，试写出该图的邻接矩阵和邻接表。3已知顺序表中存储的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，将元素按其在表中的次序依次插入到一棵初始为空的二叉排序树中，画出插入完成后的二叉排序树，并计算在等概率的情形

15、下，在该二叉排序树上成功检索的平均检索长度。4已知一棵二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDAHGF，试画出该二叉树。5无向图G的顶点依次为a、b、c、d和e，其邻接矩阵如下，试画出该图。6有一个如右所示的无向连通图，顶点存储次序为a, b, c, d, e, f, g, h。（20分） 从顶点a出发，采用深度优先搜索，画出所得该图的深度优先生成树； 从顶点a出发，采用广度深度优先搜索，画出该图的广度优先生成树； 采用Prim算法，画出其求解最小生成树的每一步骤； 采用Kruscal算法，画出其求解最小生成树的每一步骤。7已知某通讯电文中仅使用A、B、C、D、E等5中符

16、号，且这些符号在电文中分别出现27、14、5、76、21次，试以这5个符号设计（画出）哈夫曼树，并写出其哈夫曼编码。编程题：1有一个带头结点的单链表，已知指向头结点的指针hp，试写出在元素值为a的结点（假设该结点存在）之后插入元素值为b的结点（该结点未建立）的算法过程。结点类型node已经定义，含有存放元素的data域（elemtp类型）和指向后继结点的指针域next。2以二叉链表为存储结构，写出求二叉树中叶子结点数的算法的递归函数。3以链地址法处理冲突建立开散列表，设散列函数为：H(key)=key%13。试编写在此开散列表上实现动态检索（即，给定记录键值K，若检索成功则返回结点地址；否则以拉链法插入新结点，并返回新结点的地址）算法的函数。设同义词单链表结点的数据类型定义如下：type