数据结构练习附

1、一、单项选择题1.逻辑关系是指数据元素间的（）2.A 类型 B 存储方式C 结构D 数据项3. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 ( )A顺序表B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D.单链表4. 设数组 datam 作为循环队列 SQ的存储空间，front 为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）5.A front=front+1B front=(front+1)%(m-1)6.C front=(front-1)%mD front=(front+1)%m7.在具有 n 个单元的顺序存储的循环队列中，假定fro

2、nt和 rear 分别为队头指针和队尾指针，则判断队满的条件为()。Arear n=front B(front+l)n=rearCrear n-1=frontD (rear+l)n=front8.在具有 n 个单元的顺序存储的循环队列中，假定front和 rear 分别为队头指针和队尾指针，则判断队空的条件为()。Arear n=front Bfront+l=rearCrear=frontD(rear+l) n=front9.已知一颗二叉树上有 92个叶子结点，则它有 _个度为 2的结点。()10. A. 90B. 91C. 92D. 9311. 在一棵非空二叉树的中序遍历序列中，根结点的右边

3、_。12. A.只有右子树上的所有结点B.只有右子树上的部分结点13. C.只有左子树上的所有结点D.只有左子树上的部分结点14. 有 n 条边的无向图的邻接表存储法中， 链表中结点的个数是 ( ) 个。A. nB. 2nC. n/2D.n*n15. 判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法16. 对线性表进行二分查找时，要求线性表必须()。A. 键值有序的顺序表B.键值有序的链接表C. 链接表但键值不一定有序D.顺序表但键值不一定有序17. 下列时间复杂度中最好的是（）。A O(1)

4、B O(n)CO(log2n)DO(n2)18. 若某线性表的常用操作是取第 i 个元素及其前趋元素， 则采用 ( )存储方式最节省时间？19. A顺序表B单链表C双链表D单向循环20. 在一个单链表 HL中，若要向 q 所指结点之后插入一个由指针 p 指向的结点，则执行（）AHL=p;p-next=HLBp-next=HL;HL=pCp-next=q-next;q-next=p Dp-next=q-next;q=pnext21.栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。22.A中间点B 端点C随机存取点D 结点23. 一个栈的输入序列为 1，2，3，4，5，则下列序列中不

5、可能是站的输出序列的是 _A. 2,3,4,1,5B.5,4,1,3,2C. 2,3,1,4,5D.1,5,4,3,224. 广义表 (a),a)的表尾是。（）A aBC(a)D(a)25. 将含 100 个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为 1。编号为 47 的结点 X 的双亲的编号为 ( )A 24B 25C23D无法确定26. 有 n 个顶点的无向图的邻接矩阵是用 _数组存储。27.A. n 行 n 列B.一维C.任意行 n 列D.n 行任意列28.如图所示有向图的一个拓扑序列是（）A ABCDEFBFCBEADCFEDCBAD DAEBCF29.

6、 有一个有序表 1 ，4，6，10， 18，35， 42，53，67， 71，78，84，92，99 ，当用二分查找法查找键值为 84 的结点时，经 _比较后查找成功。A.2B.3C.4D.1230. 在一个带有附加表头结点的单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（）A.HL=p;p-next=HL;B.p-next=HL-next;HL-next=p;C.p-next=HL; p=HL;D. p-next=HL; HL=p;31. 若采用单链表表示循环队列，则应该选用（）A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循

7、环链表32. 栈和队列是两种特殊的线性表，只能在它们的除结点。（）A. 中间点B. 端点C. 随机存取点处添加或删 D. 结点33. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()A.前序遍历B.后序遍历C.中序遍历D.层次遍历34. 树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据35. 已知一颗二叉树上有 92 个叶子结点，则它有 _个度为 2 的结点。（）A. 90B. 91C. 92D. 9336. 对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是()A、小于B、大于

8、C、等于D、不小于37. 对关键字序列 19，11，27，18，33 进行快速排序，则要进行多少次关键字比较？（）A.5次B.6次C.7次D.8次1. 设有一个二维数组 Amn ，假设 A00 存放位置在 644(10) ，A22存放位置在 676(10) ，每个元素占一个空间，问 A33 (10) 存放在什么位置？脚注 (10) 表示用 10 进制表示。 ( C )A.688B.678C.692D.6962. 设有 6 个结点的无向图，该图至少应该有 ( A ) 条边才能确保是一个连通图。A.5B.6C.7D.83. 根据二叉树的定义可知二叉树共有 ( B ) 种不同的形态。A.4B.5C.

9、6D.74. 假设在一棵二叉树中，双分支结点数为 15 ，单分 支结点数为 30 个，则叶子结点数为 ( B )个。A15B16C17D475. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( A )。A不发生改变B发生改变C不能确定D以上都不对6. 在一个具有 n 个顶点的无向完全图中，所含的边数为 ( C ) 。AnBn(n-1)Cn(n-1)/2Dn(n+1)/27.若一个图的边集为 (A,B),(A,C),(B,D),(C,F),(D,E),(D,F)顶点 A 开始对该图进行深度优先搜索，得到的顶点序列可能为(B)。，则从AA,B,C,F,D,E CA,B,D,C,F

10、,EBDA,C,F,D,E,BA,B,D,F,E,C8. 假定对元素序列 (7,3,5,9,1,12) 进行堆排序，采用小顶堆，则初始数据构成的初始堆为 ( B ) 。A1,3,5,7,9,12 B 1,3,5,9,7,12 C1,7,3,5,9,12 D 1,3,5,7,9,12二、填空题1.根据值的不同特性，高级程序语言中的数据类型可分为两类：_ 和_ 。2.线性表有两种存储结构： _和 _。3.在以 HL 为表头指针的循环单链表中，链表为空的条件为_。4.设栈 S 和队列 Q 的初始状态皆为空，元素a1,a2,a3,a4,a5和 a6 一次通过一个栈后即进入队列 Q，若 6 个元素出对的

11、顺序是a3,a5,a4,a6,a2,a1，则栈 S 至少可以容纳 _个元素。5. 对于一棵具有 30 个结点的二叉树， 若一个结点的编号为 5，则它的左孩子结点的编号为 _，右孩子结点的编号为 _，双亲结点的编号为 _。6. 对于一个具有 n 个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为 _个，其中 _个用于链接孩子结点，_个空闲。7.设图中有 n 个顶点， e 条边， 则含有 e=_ _条边的无向图称作完全图，含有 e=_条弧的有向图称作有向完全图。8. 对于线性表（ 78， 4， 56， 30， 65）进行哈希存储时，若选用H （ K） =K %5作为哈希函数，则哈希地址为0

12、 的元素有 _个。9.在单链表上难以实现的排序方法有_ 和 _ 。10.根据值的不同特性，高级程序语言中的数据类型可分为两类：_ 和_ 。11. 在单链表中，删除指针 P 所指节点的后继结点的语句是 _。12. 栈又称为 _ 的线性表，队列又称为 _的线性表。13.N 个结点的二叉树采用二叉链表存放，共有空链域个数为_ 。14.一棵深度为 k 的满二叉树的结点总数为_，一棵深度为k 的完全二叉树的结点总数的最小值为_，最大值为 _。15.具有 80 个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为 1 号 )，则编号最大的分支结点序号为_，编号最小的分支结点序号为 _，编号最大

13、的叶子结点序号为_，编号最小的叶子结点序号为 _。16. 采用二分法进行查找的查找表，应选择_的存储结构。17. 假设在有序表A 0 19 中进行二分查找，比较二次查找成功的结点数为_，比较三次查找成功的结点数为_。18. 一个有向图 G 中若有弧 、 和 ，则在图 G 的拓朴序列中，顶点 Vi,Vj 和 Vk 的相对位置为_。19. 对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。20. 栈又称为 _ 的线性表，队列又称为 _的线性表。21. 对于一棵具有 n 个结点的二叉树， 用二叉链表存储时， 其指针总数为 _个，其中 _个指针是空闲

14、的。22. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_ 为主序、_为辅序的次序排列。23. 一颗深度为 K 且有 _个结点的二叉树称为满二叉树。24. 若对一棵完全二叉树从 0 开始进行结点的编号，并按此编号把它顺序存储到一维数组 A 中，即编号为 0 的结点存储到 A0 中。其余类推， 则 Ai 元素的左孩子元素为 _，双亲元素为 _。25. 对于线性表（ 78， 4， 56， 30， 65）进行哈希存储时，若选用H （ K） =K %5作为哈希函数，则哈希地址为0 的元素有 _个，哈希地址为4 的有_个。26. 以折半查找方法从长度为8 的有序表中查找一个元素时，平均查找长度为_

15、。27. 假 定 一 个 有 向 图 的 顶 点 集 为 a,b,c,d,e,f ， 边 集, ，则出度为 0 的顶点个数为 _，入度为 1 的顶点个数为 _。28. 设有 向图 G 中有向边的集合 E=， ， ， ，则该图的一种拓扑序列为 _ 。29. 对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n 个，其中 _个用于链接孩子结点， _个空闲着。30. 设有向图中不存在有向边， 则其对应的邻接矩阵 A 中的数组元素 Aij 的值等于 _。31. 根据初始关键字序列 (19，22，01， 38，10)建立的二叉排序树的高度为 _ 。32.三应用题1. 顺

16、序队的“假溢出” 是怎样产生的？如何知道循环队列是空还是满？2. 回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？假设正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是。3. 设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。至少有14 种。 全进之后再出情况，只有1 种： 4， 3，2， 1 进 3个之后再出的情况，有3 种， 3,4,2,13,2,4,13,2,1,4 进 2个之后再出的情况，有5 种， 2,4,3,12,3,4,12

17、,1, 3,4 2,1,4,32,1,3,4 进 1个之后再出的情况，有5 种， 1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,34. 对给定的权值 2,3,4,7,8,9 ，构造出相应的赫夫曼树，并求出带权路径的长度 WPL。33181599785 423WPL=2*4+3*4+4*3+9*2+7*2+8*2=805. 对于下图的无向图，绘出从 a 出发，用普利姆算法构造的最小生成树的过程。（过程略）begadcfh6. 请画出右图的邻接矩阵和邻接表。7. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？在什么情况下用链表比顺序表好？ 顺序存储

18、时， 相邻数据元素的存放地址也相邻（逻辑与物理统一） ；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（ 1？），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时， 相邻数据元素可随意存放， 但所占存储空间分两部分， 一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作； 链表宜于做插入、 删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。8. 按照下列给定二叉树的先序遍历序列、中序遍历序列和后序遍历序列，分别构造出二叉树。 先序遍历序列： EBADCFHGIKJ 中序遍历序列： ABCDEFGHIJK 中序遍历序列： ACBGEDF后序遍历序列： ABCDEFG(1)(2)EBFADHCGIKJGCFABED9. 如下列所示的连通图，请画出：（1）以顶点 a 为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点。顶点a 和顶点c 是关节点10. 给定表 19，14，22， 01，66