数据结构与算法（仲恺农业工程学院）期末答案2023秋

1.存储图的邻接矩阵大小不但与图的顶点个数有关，而且与图的边数也有关。（   ）
A:正确 B:错误
答案:错误
2.栈的栈底是固定的，栈顶是动态的。（ ）
A:错 B:对
答案:错
3.线性表中的所有元素都有一个前驱元素和后继元素。（   ）
A:对 B:错
答案:错
4.线性表的顺序存储结构优于链表存储结构。（ ）
A:错误 B:正确
答案:错误
5.数据结构是指相互之间存在一种或多种关系的数据元素的全体。（   ）
A:错 B:对
答案:错
6.对二叉排序树进行中序遍历得到的序列一定是递增序列。（   ）
A:错 B:对
答案:对
7.在线性表的链式存储结构中，某结点的指针字段必定指向该结点的后继结点。（   ）
A:错 B:对
答案:错
8.顺序栈没有求栈长度的操作，有判断栈满和栈空的操作。（   ）
A:对 B:错
答案:对
9.算法的空间复杂度与问题规模有关。（   ）
A:错 B:对
答案:对
10.顺序表中作删除操作时不需移动大量数据元素。（   ）
A:对 B:错
答案:错
11.每种数据结构都应具备三种基本运算：插入、删除、搜索。（   ）
A:对 B:错

12.在栈操作中输入序列为(A, B, C)，不可能得到的输出是(C, A, B)。（   ）
A:对 B:错 13.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（   ）
A:错误 B:正确 14.栈是一种只允许在表的一端插入和删除的线性表，这一端称为栈顶，另外一端称为栈底。（ ）
A:对 B:错 15.循环队列不会有溢出现象。（   ）
A:对 B:错 16.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图。（   ）
A:错误 B:正确 17.二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。（   ） 
A:错 B:对 18.栈是一种只允许在表的一端插入和删除的线性表，这一端称为栈底，另外一端称为栈顶。（ ）
A:对 B:错 19.不带表头单向循环链表某指针指向表中任一个结点即可访问整个链表。（   ）
A:对 B:错 20.树最适合用来表示（    ）。
A:元素之间无联系的数据 B:元素之间具有分支层次关系的数据 C:无序数据元素 D:有序数据元素 21.设某二叉树中度数为0的结点数为N0，度数为1的结点数为N1，度数为2的结点数为N2，则下列等式成立的是（   ）。
A:N0=N2+1 B:N0=2N1+1 C:N0=N1+N2 D:N0=N1+1 22.采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（     ）。
A:先序遍历 B:层次遍历 C:后序遍历 D:中序遍历 23.某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（    ）。
A:3 B:4 C:5 D:2 24.设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（    ）。
A:9 B:3 C:5 D:8 25.下列关于图遍历的说法不正确的是（    ）。
A:图的广度优先搜索中邻接点的寻找具有“先进先出”的特征      B:图的遍历要求每一顶点仅被访问一次 C:有回路非连通图不能用深度优先搜索法 D:连通图的深度优先搜索是一个递归过程      26.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（     ）。
A:250 B:501 C:254 D:505 27.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串。
A:8 B:6 C:14 D:5 28.二叉树中第5层上结点最多为（     ）个。
A:16 B:32 C:7 D:19 29.深度为4的二叉树至多有（   ）个结点。
A:16 B:8 C:15 D:4 30.将一棵有80个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（   ）。
A:99 B:不存在 C:98 D:50 31.在以下的叙述中，正确的是（     ）。
A:二维数组是其数据元素为线性表的线性表 B:任何条件下，线性表的顺序存储结构优于链式存储结构 C:线性表中至少要有一个元素，元素有序 D:线性表中每个元素都有一个直接前驱和直接后继 32.若A、B、C、D、E、F车顺序进栈，且任意一辆车可以在栈顶时出栈，则出栈次序可以为（ ）。
A:AEDFCB B:AEDFBC C:DCEFAB D:DFEBAC 33.对于一个具有n个顶点和e个边的有向图，若采用邻接矩阵表示，则该矩阵中零元素个数是（     ）。
A:(n-1)*(n-1) B:n*n C:n*n-2e D:n*n-e 34.在数据结构中，从逻辑上可以把数据结构分成（   ）。
A:线性结构和非线性结构 B:紧凑结构和非紧凑结构 C:内部结构和外部结构 D:动态结构和静态结构 35.如果以链表作为栈的存储结构，则入栈操作时（     ）。
A:对栈不作任何判别 B:必须判别栈是否为空 C:必须获取栈顶元素值 D:必须判别栈是否为满 36.在邻接表中，图的每个顶点关联的边集合是一种（    ）。
A:顺序存储结构 B:链式存储结构 C:散列存储结构 D:索引存储结构 37.线性表中（     ）只有一个直接前驱和一个直接后继。
A:所有的元素 B:尾元素 C:中间的元素 D:首元素 38.将递归算法转换成对应的非递归算法时，通常需要使用（   ）。
A:树 B:链表 C:图 D:栈 39.数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的（   ）的科学。
A:关系 B:运算 C:算法 D:结构 40.无向图的邻接矩阵是一个（    ）。
A:对角矩阵 B:零矩阵 C:对称矩阵 D:上三角矩阵 41.下面关于哈希查找的说法，不正确的是（    ）。
A:采用链地址法处理冲突时，查找一个元素的时间是相同的 B:用链地址法处理冲突，适合表长不确定的情况 C:用链地址法处理冲突，不会引起二次聚集现象 D:采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 42.一组记录的键值为（10，31，29，25，66，48，61，88），按2路归并排序方法对该序列进行一趟归并后的结果为（   ）。
A:10，31，25，29，48，66，61，88 B:10，25，29，31，48，61，66，88 C:10，31，29，25，66，48，61，88 D:10，29，31，25，61，48，66，88 43.以下数据结构中，（     ）是非线性数据结构。
A:树 B:队 C:栈 D:字符串 44.下列存储形式中，（   ）不是树的存储形式。
A:孩子链表示法          B:孩子兄弟链表示法 C:顺序存储表示法 D:双亲表示法 45.在做出栈操作时，首先要判断栈是否（   ）。
A:上溢出 B:满 C:空 D:初始化 46.设有序表中有1000个元素，利用二分查找算法查找元素X最多需要比较（     ）次。
A:7 B:1 C:10 D:25 47.一个栈的入栈序列依次是a,b,c,d,e，不可能得到的输出序列是（ ）。
A:dceab B:abcde C:decba  D:edcba 48.设给定权值总数为n 个，其哈夫曼树的非叶子结点总数为(     )。
A:n B:n-1 C:2n-1 D:2n+1  49.下列（   ）不是单链表的特性。
A:不必事先估计所需存储空间大小 B:所需空间与线性表长度成正比 C:插入与删除时不必移动元素 D:随机访问 50.以下序列，不是堆（大根或小根）的是（     ）。
A:｛100，85，98，77，80，60，82，40，20，10，66 ｝ B:｛100，98，85，82，80，77，66，60，40，20，10 ｝ C:｛100，85，40，77，80，30，66，98，82，10，20 ｝ D:｛10，20，40，60，66，77，80，82，85，98，100 ｝ 51.对于堆栈和队列，以下说法正确的是（ ）。
A:都是可以在中部插入和删除的线性结构 B:都是限制存取点的线性结构 C:都是可以访问中间结点的非线性结构 D:都限制存取点的非线性结构 52.在对表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这方式主要适合于（   ）。
A:动态查找表   B:两种表都不适合 C:静态查找表与动态查找表 D:静态查找表 53.假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（    ）个。
A:17 B:15 C:16 D:47 54.在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是（     ）。
A:顺序表 B:循环链表 C:双向链表 D:单链表 55.若二叉树的中序遍历序列为abcdef，且c为根结点，则（     ）。
A:二叉树有两个度为0的结点  B:结点C有两个孩子 C:二叉树的高度为5 D:以上都不对 56.下列算法的时间复杂度是（   ）。
    for(i=1; i<=n; i++ )
        sum +=i*i;
A: B: C: D: