数据结构填空题

二、填空题(15分,共15题,每小题1分) （填空题是1，3 ，4， 7 ，查找）

1、一个算法的效率可分为（ 时间（时间复杂度） ）效率和（ 空间（空间复杂度） ）效率

2、在一个长度为n的顺序表中的第i个元素之前插入一个元素，需要后移（ n-i+1 ）个元素

3、在双向链表中，每个节点含有两个指针域，一个指向（ 前驱 ）节点，另一个指向（ 后继 ）节点。

4、在单向链表中，在单链表中设置头节点的作用是（ 简化插入、删除操作 ），除首节点外，任何一个节点的存储位置由（ 前驱节点的后继指针 ）表示。

5、允许在线性表的一端进行插入和删除的线性表称为（ 栈 ）

6、当栈满时再进行栈运算将产生（ 上溢出 ），当栈空时再做出栈运算将产生（ 下溢出 ）。

7、后进先出的线性表称为（ 栈 ），后进后出的线性表称为（ 队列 ）。

8、对于一个有n个节点的二叉树，当它为一棵（ 完全 ）二叉树时具有最小高度，即为（ log2（n+1） ），当它为一棵单支树具有（ 最大 ）高度，即为（ n ）。

9、在一棵二叉树中，度为0的节点个数为n0，度为2的节点个数为n2，则n0=

（ n2+1 ）。

10、空树是指（ 节点数为0 ），最小的树是指（ 只有根节点 ）。

11、以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为（ (n+1)/2 ），时间复杂度为（ O(n) ）。

12、假定对长度为n=50的有序表进行折半查找，则对应的判定树的高度为（ 6 ），最后一层的节点数为（ 19 ）。

13、对一棵二叉排序树进行中序遍历时，得到的节点序列是一个（从小到大的有序序列 ）。

14、在简单选择排序中，记录比较次数的时间复杂度为（ o（n的平方） ），记录移动次数的时间复杂度为（ o(n) ）。

15、假定一组记录为（46，79，56，25，76，38，40，80），对其进行快速排序的第一次划分后，右区间元素的个数为（ 4 ( 76、56、79、80) ）。

o(n)

1、数据的存储结构可用四种基本的存储方法，它们是___顺序 ____存储方法、__链接____存储方法、索引存储方法、散列存储方法。

2、一个算法的效率可分为__时间___效率和空间效率。

3、按顺序存储方式存储的线性表称为_顺序表_____,按链式存储方式存储的线性表称为__链表_____。

4、在栈中存取数据遵从的原则是_先进后出______,而在队列中存取数据应遵从的原则是先进先出。

5、在队列中，允许插入的一端称为__队尾_____,允许删除的一端称为__队头______。

6、对于数组，一般采用顺序存储方式来表示，通常有两种顺序存储方式：__按行优先_______存储方式和按列优先存储方式。

7、深度为4的完全二叉树至少有__8___个结点。

8、所有插入和删除都在表的一端进行的线性表称为 栈 。

9、n个元素的顺序检查（检索）的平均查找长度为 （n+1） / 2 。

10、线性表的链接存储结构简称为 线性存储结 。

1．二叉树的第i层（根结点为第1层），最多有 2的(i-1)次 个结点。

2． 数据逻辑结构包括 线性结构 树型（层次）结构 和图形结构等三种类型。

3．树型结构和图形结构合称 非线性 结构。

4．算法的五个重要特性是：有穷性、 确定性 、 可行性 、输入和输出。

5．线性结构中元素之间存在 一对一 关系，树型结构元素之间存在 一对多 关系，图形结构中元素之间存在多对多关系。

6．评价算法的性能从利用计算机资源角度看主要从 时间 复杂度和 空间 复杂度两方面来分析。

7．在线性结构中，第一个结点 前驱结点 ，其余每个结点有且只有 一 个前驱结点。

8．在线性结构中，最后一个结点 没有 后驱结点，其余每个结点有且只有 一 个后驱结点。

9．在双向链表中，每个结点有两个指针域，一个指向 前驱节点 ，另一个指向 后驱节点 。

10．单链表是 线性表 的链接存储表示

1．线性表是一种典型的 线性 结构。

2．顺序表中逻辑上相邻的元素的物理位置 也相邻 。

3．要从顺序表中删除一个元素时，被删除的元素之后的所有元素均需 向前移动 一个位置。

4．对于队列只能在 队尾 位置删除元素。

5．只有一个指针的链表，包括 单链表 和 循环链表 。

6．有两个指针的链表，包括 双向链表 和 双向循环链表 。

7．没有任何结点的树是 空树 。

8．只有一个结点的树是 最小树 。

9．有三个结点构成的二叉树，共有 五种 种不同的状态。

10．在二叉树存储方式中，三叉链表比二叉链表多一个指向 双亲 的指针域。