《数据结构练习附答案》由会员分享，可在线阅读，更多相关《数据结构练习附答案（21页珍藏版）》请在金锄头文库上搜索。
1、一、单项选择题1. 逻辑关系是指数据元素间的( )A 类型 B .存储方式 C 结构 D .数据项2. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A 顺序表B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表 D. 单链表3. 设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，贝9执行出队操作后其头指针front值为()Afront=front+1Bfront=(front+1)%(m-1)Cfront=(front-1)%mD front=(front+1)%m4. 在具有n个单元的顺序存储的循环队列中，假定front和re
2、ar分别为队头指针和队尾指针，贝判断队满的条件为( )。 Arearn=front B(front+l)n=rear5. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。Arearn=frontBfront+l=rearCrear=frontD(rear+l)n=front6. 已知一颗二叉树上有 92 个叶子结点，则它有个度为 2 的结点。()A. 90 B. 91 C. 92 D. 937. 在一棵非空二叉树的中序遍历序列中，根结点的右边。A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D
3、. 只有左子树上的部分结点8. 有n条边的无向图的邻接表存储法中，链表中结点的个数是()个A. nB. 2nC. n/2D. n*n9. 判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用()。A.求关键路径的方法B求最短路径的方法C.深度优先遍历算法D广度优先遍历算法10. 对线性表进行二分查找时，要求线性表必须( )。A键值有序的顺序表B键值有序的链接表C链接表但键值不一定有序D顺序表但键值不一定有序第 2 页 共 14 页A.O(1)B.O(n)C.O(log2n)D.O(n2)12. 若某线性表的常用操作是取第个元素及其前趋元素，则采用( )存储方式最节省时间？A 顺序表B
4、单链表C.双链表D单向循环13. 在一个单链表HL中，若要向q所指结点之后插入一个由指针p指 向的结点，则执行( )AHL=p;p-next=HLBp-next=HL;HL=pCp-next=q-next;q-next=p Dp-next=q-next;q=pnext14. 栈和队列是两种特殊的线性表，只能在它们的( )处添加或删 除结点。A.中间点B 端点C 随机存取点D 结点15. 一个栈的输入序列为 1，2，3，4，5，则下列序列中不可能是站的 输出序列的是_A. 2,3,4,1,5B.5,4,1,3,2C. 2,3,1,4,5D.1,5,4,3,216. 广义表(a),a)的表尾是。(
5、)A . aB .AC . (a)D. (a)17. 将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为( )A.24B.25C.23D.无法确定18. 有n个顶点的无向图的邻接矩阵是用数组存储。A. n行n列 B维C.任意行n列 D.n行任意列20. 有一个有序表1，4，6，10，18，35，42，53，67，71，78，84，92， 99，当用二分查找法查找键值为84的结点时，经比较后查找成功。A.2B.3C.4D.1221. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，贝g执行()A.
6、 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. 若采用单链表表示循环队列，则应该选用（ ）A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循环链表23. 栈和队列是两种特殊的线性表，只能在它们的处添加或删除结点。（ ）A. 中间点 B. 端点 C. 随机存取点 D. 结点24. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树这种遍历称为 （）A前序遍历B后序遍历C中序遍历D层次遍历25. 树最适合用来表示（ ）A.
7、有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D元素之间无联系的数据26. 已知一颗二叉树上有92 个叶子结点，则它有个度为2的结点。（）A. 90B. 91C. 92D. 9327. 对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是 （）A、小于B、大于C、等于D、不小于28. 对关键字序列19，11，27，18，33进行快速排序，则要进行多少次第 5 页 共 14 页A. 5 次 B. 6次 C. 7次 D. 8次1. 设有一个二维数组Amn,假设A00存放位置在644(io), A22存放位置在676，每个元素占一个空间，问A 存放在什么位(1
8、o)(1o)置？脚注(10)表示用10进制表示。(C )A.688B.678C.692D.6962. 设有6个结点的无向图，该图至少应该有(A)条边才能确保是一个连通图。A.5B. 6C. 7D. 83. 根据二叉树的定义可知二叉树共有( B )种不同的形态。A.4B.5C.6D.74. 假设在一棵二叉树中，双分支结点数为15，单分 支结点数为30 个，则叶子结点数为( B )个。A15B16C17D475. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( A )。A不发生改变B发生改变C不能确定D 以上都不对6. 在一个具有n个顶点的无向完全图中，所含的边数为(C )。7.
9、 若一个图的边集为(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,12B1,3,5,9,7,12C1,7,3,5,9,12D1,3,5,7,9,12二、填空题1. 根据值的不同特性，高级程序语言中的数据类型可分为两类： 和2. 线性表有两种存储结构：和。3. 在以HL为表
10、头指针的循环单链表中，链表为空的条件为。4. 设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6 次通过一个栈后即进入队列Q,若6个元素出对的顺序是a3,a5,a4,a6,a2,a1，则栈S至少可 以容纳个元素。5. 对于棵具有30个结点的二叉树，若个结点的编号为5，则它的左孩子结点的编号为，右孩子结点的编号为，双亲结点的编号为。6. 对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为个，其中个用于链接孩子结点，个空闲。7. 设图中有n个顶点，e条边，则含有e二条边的无向图称作完全图，含有e=条弧的有向图称作有向完全图。8. 对于线性表(7& 4，56
11、，30，65)进行哈希存储时，若选用H (K)二K %5作为哈希函数，则哈希地址为0的元素有个。9. 在单链表上难以实现的排序方法有和 。10. 根据值的不同特性，高级程序语言中的数据类型可分为两类： 和11. 在单链表中，删除指针P所指节点的后继结点的语句是。12. 栈又称为的线性表，队列又称为的线性表。13. N个结点的二叉树采用二叉链表存放，共有空链域个数为。14. 一棵深度为 k 的满二叉树的结点总数为，一棵深度为 k 的完全二叉树的结点总数的最小值为，最大值为。15. 具有 80 个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号为，编号
12、最小的分支结点序号为，编号最大的叶子结点序号为，编号最小的叶子结点序号为。16. 采用二分法进行查找的查找表，应选择的存储结构。17. 假设在有序表A 019中进行二分查找，比较二次查找成功的结点数为，比较三次查找成功的结点数为。18. 个有向图G中若有弧Vj,Vi、Vi,Vk和Vj,Vk，则在图G的拓朴序列中，顶点Vi,Vj和Vk的相对位置为 。19. 对于个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。20. 栈又称为的线性表，队列又称为的线性表。21. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为个，其中个指针是空闲的。22.
13、 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、为辅序的次序排列。23. 颗深度为K且有个结点的二叉树称为满二叉树。24. 若对棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到维数组A中，即编号为0的结点存储到A0中。其余类推，则Ai元素的左孩 子元素为，双亲元素为。25对于线性表（7& 4，56，30，65）进行哈希存储时，若选用H （K） =K %5作 为哈希函数，则哈希地址为 0 的元素有个，哈希地址为 4 的有个。26. 以折半查找方法从长度为 8 的有序表中查找个元素时，平均查找长度为27. 假 定 个 有 向 图 的 顶 点 集 为 a,b,c,d,e,f
14、 ， 边 集 a,c,a,e,c,f,d,c,e,b,e,d,则出度为 0 的顶点个数为，入度为1的顶点个数为。28设有向图 G 中有向边的集合 E=1，2，2，3，1，4，4，2，4,第 8 页 共 14 页3，则该图的一种拓扑序列为。29. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中个用于链接孩子结点，个空闲着。30. 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素Aij的值等于。31. 根据初始关键字序列（19，22，01，38，10）建立的二叉排序树的高度为。32.三应用题1. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？2. 回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队 列等方式正确输出其回文的可能性？假设正读和反读都相同的字符序 列为回文”，例如，abba和abcba是回文，abcde和ababab则不是。3. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站， 具
