软考程序员考试知识点填空检测（5）

为方便软考考生对程序员考试知识点的检测，希赛软考频道为考生带来软考程序员考试知识点填空检测的内容（完整版可在本文文首本文资料处或文末的资料下载栏目下载）。

软考程序员考试知识点填空检测（5）内容如下：

第四章 数据结构与算法基础

1.数据结构概念和分类

________时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

________时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

2.栈和队列

栈是只能在一端进行插入和删除操作的线性表，其中允许插入和删除的一端叫栈顶，另一端叫栈底。栈是一种________的数据结构，先入栈的元素要比后入栈的元素后出栈。故将一串数据全部入栈后再全部出栈，数据的次序将前后颠倒。

栈主要应用于函数调用或中断调用过程中。

队列是只能在一端插入、在另一端删除的线性表，其中允许插入元素的一端称为队列头或队头，允许删除元素的一端称为队列尾或队尾。队列是一种________的数据结构，先入队列的元素要先于后入队列的元素出队列。故一串数据无论以何种操作次序通过队列，其次序都不会发生变化。

循环队列：

队空条件：________

队满条件：________

队列长度：________循环队列的优点：入队和出队操作都不需要移动队列中的其他元素。

3.二叉树的性质

1）在二叉树的第i层上最多有________个结点（i≥1）；

2）深度为k的二叉树最多有________个结点（k≥1）；

3）叶子结点数为________，度为2的结点数为n2，则n0=n2+1。

4.二叉排序树

二叉排序树（BinarySortTree）又称为二叉搜索树，或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均________根结点的值。

（2）若右子树不空，则右子树上所有结点的值均________根结点的值。

（3）左右子树也都是二叉排序树。

5.排序算法