练习附答案(更新)

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

2、ront=(front-1)%m       Dfront=(front+1)%m4. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( D )。Arearn=front B(front+l)n=rearCrearn-1=front D(rear+l)n=front5. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( C )。A rearn=front Bfront+l=rearCrear=front D

3、(rear+l)n=front6. 已知一颗二叉树上有92个叶子结点，则它有_个度为2的结点。( B )A. 90 B. 91 C. 92 D. 93    7. 在一棵非空二叉树的中序遍历序列中，根结点的右边( C )。A.只有右子树上的所有结点 B. 只有右子树上的部分结点 C.只有左子树上的所有结点 D. 只有左子树上的部分结点8. 有n条边的无向图的邻接表存储法中，链表中结点的个数是( B )个。 A.n B. 2n C. n/2 D.n*n9. 判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（ C ）。A. 求关键路径的方法 B.求最短路径

4、的方法C. 深度优先遍历算法 D.广度优先遍历算法10. 对线性表进行二分查找时，要求线性表必须( A )。 A.键值有序的顺序表 B.键值有序的链接表 C.链接表但键值不一定有序 D.顺序表但键值不一定有序11. 下列时间复杂度中最好的是（ A ）。 AO(1) BO(n) CO(log2n) DO(n2)12. 若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间？A顺序表B单链表C双链表D单向循环13. 在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行（ C ）AHL=p;p->next=HL Bp->next=HL;H

5、L=pCp->next=q->next;q->next=p Dp->next=q->next;q=p>next14. 栈和队列是两种特殊的线性表，只能在它们的（ B ）处添加或删除结点。A中间点 B端点 C随机存取点 D结点15. 一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是站的输出序列的是( B) A. 2,3,4,1,5 B.5,4,1,3,2 C. 2,3,1,4,5 D.1,5,4,3,216. 广义表(a),a)的表尾是。（ C ）Aa B C(a) D (a)17. 将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点

6、编号，根结点的编号为1。编号为47的结点X的双亲的编号为( C )A24 B25 C23 D无法确定18. 有n个顶点的无向图的邻接矩阵是用_A_数组存储。A. n行n列 B.一维 C.任意行n列 D.n行任意列19. 如图所示有向图的一个拓扑序列是（B）AABCDEF BFCBEAD CFEDCBA DDAEBCF20. 有一个有序表1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找键值为84的结点时，经_C_比较后查找成功。 A.2 B.3C.4 D.1221. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行

7、（ B ）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; 22. 若采用单链表表示循环队列，则应该选用（ B ）A. 带尾指针的非循环链表 B. 带尾指针的循环链表C. 带头指针的非循环链表 D. 带头指针的循环链表23. 栈和队列是两种特殊的线性表，只能在它们的 处添加或删除结点。（ B ）A. 中间点 B. 端点 C. 随机存取点 D. 结点24. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍

8、历称为 (C )A.前序遍历 B.后序遍历 C.中序遍历D.层次遍历25. 树最适合用来表示（ C ）A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据26. 已知一颗二叉树上有92个叶子结点，则它有_个度为2的结点。（ B ）A. 90 B. 91 C. 92 D. 9327. 对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是 ( A)A、小于 B、大于 C、等于D、不小于1. 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？

9、脚注(10)表示用10进制表示。( C )A.688 B.678 C.692 D.696 2. 设有6个结点的无向图，该图至少应该有( A )条边才能确保是一个连通图。A.5 B. 6 C. 7 D. 83. 根据二叉树的定义可知二叉树共有( B )种不同的形态。A.4 B.5 C.6 D.74. 假设在一棵二叉树中，双分支结点数为15，单分 支结点数为30个，则叶子结点数为( B )个。A15 B16 C17 D475. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( A )。A不发生改变 B发生改变 C不能确定 D以上都不对6. 在一个具有n个顶点的无向完全图中

10、，所含的边数为( C )。An Bn(n-1) Cn(n-1)/2 Dn(n+1)/27. 若一个图的边集为(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( B )。AA,B,C,F,D,E BA,C,F,D,E,BCA,B,D,C,F,E DA,B,D,F,E,C8. 假定对元素序列(7,3,5,9,1,12)进行堆排序，采用小顶堆，则初始数据构成的初始堆为( B )。A1,3,5,7,9,12 B1,3,5,9,7,12C1,7,3,5,9,12 D1,3,5,7,9,12 二、填空题1. 根据值的不同特性

11、，高级程序语言中的数据类型可分为两类：_原子类型_和 结构类型。2. 线性表有两种存储结构： 顺序结构 和 链式结构 。3. 在以HL为表头指针的循环单链表中，链表为空的条件为 HL->next=HL 。4. 设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6一次通过一个栈后即进入队列Q，若6个元素出对的顺序是a3,a5,a4,a6,a2,a1，则栈S至少可以容纳 4 个元素。5. 对于一棵具有30个结点的二叉树，若一个结点的编号为5，则它的左孩子结点的编号为 10 ，右孩子结点的编号为 11 ，双亲结点的编号为 2 。6. 对于一个具有n个结点的二叉树，当它存储在二

12、叉链表中时，其指针字段的总数为 2n 个，其中 n-1 个用于链接孩子结点， n+1 个空闲。7. 设图中有n 个顶点，e条边，则含有e= n(n-1)/2 条边的无向图称作完全图，含有e= n(n-1) 条弧的有向图称作有向完全图。8. 对于线性表（78，4，56，30，65）进行哈希存储时，若选用H（K）=K %5作为哈希函数，则哈希地址为0的元素有 2 个。9. 在单链表上难以实现的排序方法有 堆排序 和 希尔排序  。10. 根据值的不同特性，高级程序语言中的数据类型可分为两类：原子类型 和 结构类型 。11. 在单链表中，删除指针P所指节点的后继结点的语句是 p->n

13、ext=p->next->next 。12. 栈又称为 后进先出 的线性表，队列又称为 先进先出 的线性表。13. N个结点的二叉树采用二叉链表存放，共有空链域个数为 N+1 。14. 一棵深度为k的满二叉树的结点总数为2k-1 ，一棵深度为k的完全二叉树的结点总数的最小值为 2k-1 ，最大值为 2k-1 。15. 具有80个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号为 40 ，编号最小的分支结点序号为 1 _，编号最大的叶子结点序号为 80 ，编号最小的叶子结点序号为 41 。16. 采用二分法进行查找的查找表，应选择_键值有

14、序的顺序_的存储结构。17. 假设在有序表A 019中进行二分查找，比较二次查找成功的结点数为 2 ，比较三次查找成功的结点数为 4 。18. 一个有向图G中若有弧<Vj,Vi>、<Vi,Vk>和<Vj,Vk>，则在图G的拓朴序列中，顶点Vi,Vj和Vk的相对位置为_VjViVk_。19. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_O(n) ，在表尾插入元素的时间复杂度为 O(1) 。20. 栈又称为 后进先出 的线性表，队列又称为 先进先出 的线性表。21. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 2n 个，其

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

16、素时，平均查找长度为 2.625 。27. 假定一个有向图的顶点集为a,b,c,d,e,f，边集<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>，则出度为0的顶点个数为 1 ，入度为1的顶点个数为 4 。28. 设有向图G中有向边的集合E=<1，2>，<2，3>，<1，4>，<4，2>，<4，3>，则该图的一种拓扑序列为 1423 。29. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中 n-1 个用

17、于链接孩子结点， n+1 个空闲着。30. 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素Aij的值等于_ 0 _。31. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为 3 。32.三应用题1. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？2. 回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？假设正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是。3. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的

18、所有可能的顺序。至少有14种。 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,34. 对给定的权值2,3,4,7,8,9，构造出相应的赫夫曼树，并求出带权路径的长度WPL。WPL=2*4+3*4+4*3+9*2+7*2+8*2=805. 对于下图的无向图，绘出从a出发，用普利姆算法构造的最小生成树的过程

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