2022年数据结构补充试卷1

Q1:数据结构包括数据的 逻辑结构 、 数据的 存储结构 和数据的 运算 这三个方面的内容

Q2:算法分析的目的是分析算法的效率以求改进

Q3:在顺序表中访问任意一结点的时间复杂度均为 O(1)

Q4:带表头结点的空循环双向链表的长度等于 0

Q5:满二叉树有度为 1 的结点

Q6:线性表中结点的集合是 有限 的， 结点间的关系是 一对一 的

Q7:在具有 n 个单元的循环队列中， 队满时共有 n-1 个元素

Q8:不含任何结点的空树是一棵树也是一棵二叉树;

Q9:数据的运算最常用的有 5 种， 它们分别是 插入 、 删除、 修改、 查找 、 排序 。

Q10:数据结构按逻辑结构可分为两大类， 它们分别是 线性结构 和 非线性结构 。

Q11:向栈中压入元素的操作是先 移动栈顶指针 ， 后 存入元素

Q12:把一棵树转换为二叉树后， 这棵二叉树的形态不是唯一的

Q13:二叉树是非线性数据结构， 所以顺序存储结构和链式存储结构都能存储

Q14:大多数排序算法都没有两个基本的操作： 比较 和 移动

Q15:散列法存储的基本思想是由 关键字的值 决定数据的存储地址

Q16:向量、 栈和队列都是 线性 结构，不 可以在向量的 任何 位置插入和删除元素

Q17:从循环队列中删除一个元素时， 其操作是 先 移动队首指针 ， 后 取出元素

Q18:在 n 个结点的单链表中要删除已知结点*p， 需找到它的前驱结点的地址， 其时间复杂度为 O（n）。

Q19:二叉树中最多只有两棵子树， 并且有左右之分

Q20:完全二叉树一定是满二叉树

Q21:在有序的顺序表和有序的链表上， 均可以使用折半查找法来提高查找速度

Q22:线性表采用顺序存储， 必须占用一片连续的存储单元。

Q23:在双链表中要删除已知结点*p， 其时间复杂度为（O(n)）。

Q24:在（链队列为空） 的情况下， 链队列的出队操作需要修改尾指针。

Q25:栈是后进先出表。

Q26:队列是后进先出的线性表。

Q27:为解决队列“假满” 问题， 可以采用循环队列实现队列存储

Q28:顺序队列和循环队列的队满和队空的条件是一样的

Q29:对顺序栈而言， 在栈满状态， 如果此时再作进栈运算， 则会发生“下溢”

Q30:循环队列只有下溢， 没有上溢

Q31:循环队列中无上溢现象

Q32:在具有 n 个结点的双链表中做插入、 删除运算， 平均时间复杂度为（O(1)）。

Q33:在具有 n 个结点的完全二叉树中， 结点 i（i1） 的父结点是

Q34:以二叉链表作为二叉树的存储结构， 在具有ｎ 个结点的二叉链表中(n0)， 空链域的个数为

Q35:在一棵具有五层的满二叉树中， 结点总数为

Q36:由二叉树的（ ） 遍历， 可以惟一确定一棵二叉树

Q37:在完全二叉树中， 如果一个结点是叶子结点， 则它没有。

Q38:在具有 n 个结点的完全二叉树中， 若结点 i 有左孩子， 则结点 i 的左孩子编号为。

Q39:在具有 n 个结点的完全二叉树中， 若结点 i 有左孩子， 则结点 i 的右孩子编号为。

Q40:若由树转化得到的二叉树是非空的二叉树， 则二叉树形状是。

Q41:哈夫曼树是访问叶结点的带权路径长度 的二叉树。

Q42:某二叉树的前序和后序序列正好相反， 则该二叉树一定是 的二叉树。

Q43:12 个结点的完全二叉树的叶结点有6

Q44:在任何一棵二叉树中， 度为０ 的结点 n 0 和度为２ 的结点 n 2 之间的关系是n0=n2-1。

Q45:一个二叉树中， 度为 2 的结点有 3 个， 则叶结点有（4） 个。

Q46:二叉树通常有（顺序） 存储结构和（链式） 存储结构两种。

Q47:完全二叉树中， 若一个结点没有左孩子， 则它必须是叶子。

Q48:一般在哈夫曼树中， 权值越大的叶子离根结点越近。

Q49:二叉树中任何一个结点的度都是 2。

Q50:中序遍历二叉排序树的结点不能得到排好序的结点序列。

Q51:由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。