数据结构自测题1、算法的计算量的大小称为计算的（）。

A. 效率B. 复杂性C. 现实性D. 难度2、一个算法应该是（）。

A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.3、下面说法错误的是（）（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B. (1), (2) C. (1), (4) D. (3)4、在数据结构中，从逻辑上可以将之分为（）。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 内部结构和外部结构D. 线性结构和非线性结构5、计算算法的时间复杂度是属于一种（）。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6、可以用（）定义一个完整的数据结构:A. 数据元素B. 数据对象C. 数据关系D. 抽象数据类型7、算法分析的目的是_______。

A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性8、设计一个“好”的算法应考虑达到的目标有______。

A. 是可行的B. 是健壮的C. 无二义性D. 可读性好线性表1、线性表是具有n个（）的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项2、若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A. 单链表B. 仅有头指针的单循环链表C. 双链表D. 仅有尾指针的单循环链表4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。

A. 带头结点的双循环链表B. 单循环链表C. 带尾指针的单循环链表D. 单链表5、静态链表中指针表示的是（）A.下一元素的地址B. 内存储器的地址C.下一元素在数组中的位置D. 左链或右链指向的元素的地址6、下述哪一条是顺序存储结构的优点？（）A．插入运算方便B．可方便地用于各种逻辑结构的存储表示C．存储密度大D．删除运算方便7、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链接存储，不必占用一片连续的存储单元D．线性表采用链接存储，便于插入和删除操作。

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.顺序存储结构的主要优点是节省存储空间，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)叫链式存储结构.又叫链接存储结构。

它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.链式存储结构特点：1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。

4、查找结点时链式存储要比顺序存储慢。

5、每个结点是由数据域和指针域组成。

8、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表9、链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）A.(1), (2)B.(1)C.(1),(2), (3)D.(2)11、单链表中，增加一个头结点的目的是为了( ）。

A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储12、对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（）。

A． p->right=s ; s->left=p;p->right->left=s ; s->right=p->right;B． p->right=s ; p->right->left=s ;s->left=p; s->right=p->right;C． s->left=p; s->right=p->right;p->right=s ; p->right->left=s ; ;D． s->left=p; s->right=p->right;p->right->left=s ; p->right=s ;13、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL堆栈和队列1、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）A. 栈B. 队列C. 树D. 图2、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e, f,g依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（）A. 1B. 2C. 3D. 4习题1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答以下问题：（1）若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop( )，则出栈的数字序列为什么？（2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。

（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。

2、链栈中为何可以不设头指针？3、循环队列的优点是什么？如何判断它的空和满？4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。

8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。

树1、n(n>0)个结点的树的高度:最低是多少？__________________最高是多少？__________________2、n(n>0)个结点的二叉树的高度:最低是多少？__________________最高是多少？__________________3、有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为24、已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）A. 39B. 52C. 111D. 1195、一棵124个叶结点的完全二叉树，最多有( )个结点。

A.247B.248C.249;D.250;E.2516、已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

A. 311B. 312C. 313D. 3147、一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间8、一棵树高为K的完全二叉树至少有（）个结点A. 2k –1B. 2k-1 –1C. 2k-1D. 2k9、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_________个叶子结点。

10、•已知二叉树的•先序序列ABDFCEHG•中序序列DBFAHECG•请构造该二叉树。

11、•已知二叉树的•先序序列ABDFCEHG•中序序列DBFAHECG•请构造该二叉树。

12、•一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。

•先序序列为：_ _ C D E _ G H I _ K•中序序列为：C B _ _ F A _ J K I G•后序序列为： _ E F D B _ J I H _ A13、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。

A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEGB14、一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。

A. 其中任意一个结点均无左孩子B. 其中任意一个结点均无右孩子C. 其中只有一个叶子结点D. 其中度为2的结点最多为一个15、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树A．空或只有一个结点B. 高度等于其结点数C．任一结点无左孩子D. 任一结点无右孩子16、17、18、按关键字序列15,21,27,43,36,8,11构造平衡二叉树19、LL型调整的两个例子20、二叉查找树的查找效率与二叉树的( （1） )有关, 在 (（2） )时其查找效率最低(1) A. 高度B. 结点的多少C. 树型D. 结点的位置(2) A. 结点太多B. 完全二叉树C. 呈单枝树D. 结点太复杂。

21、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。