第二章基本数据结构及其运算一、单项选择题1．数据的基本单位是( B )A．数据B．数据元素C．数据项D．数据结构2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素D．数据项3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型C．逻辑结构D．物理结构4．数据的逻辑结构可分为（C）A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B )A．LOC(1)+i*m B．LOC(1)+(i-1)*mC．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D）A．所有结点的地址必须是连续的B．部分结点的地址必须是连续的C．所有结点的地址一定不连续D．所有结点的地址连续、不连续都可以7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的C．连续不连续都可以D．部分是连续的8．下列不属于线性结构的是( C )。
A．单链表B．队列C．二叉树D．数组9．链表不具有的特点是( A)A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表的长度成正比10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。
A．顺序存储线性表B．非顺序存储非线性表C．顺序存储非线性表D．非顺序存储线性表11．在单链表表示的线性表中，可以从( A )。
A．第一个结点访问到所有结点B．某个结点访问到所有结点C．某个结点访问到该结点的所有前趋结点D．最后一个结点访问到所有结点12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。
A．s->link=p->link; p->link=s;B．p->link=s->link; s->link=p;C．q->link=s; s->link=p;D．p->link=s; s->link=q;13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素个数是（A）A．(n-1)/2 B．n/2 C．n-1D．n+114．设长度大于1带头结点的循环单链表head的尾结点由rear 指向，则head和rear满足关系（B）A．rear->link= =NULLB．rear= =head->linkC．.rear->link= =headD．rear= =head15．在链式存储的线性表中，插入一个元素时（D）A．需要移动元素和修改指针B．不需要移动元素和修改指针C．需要移动元素，但不需要修改指针D．不需要移动元素，但需要修改指针16．设循环队列中有m个单元，队列满的条件是( A ) A．rear=front B．(rear+1)%m=frontC．rear%m=front D．rear+1=front17．栈和队列都是( C)。
A．顺序存储的线性结构B．链式存储的线性结构C．限定存取点的线性结构D．限定存取点的非线性结构18．栈和队列( C )A．的共同点都是先进后出B．的共同点都是先进先出C．的共同点是只允许在端点处插入和删除元素D．没有共同点19．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（B）A．n-i B．n-i+1 C．i D．n-i-1 20．设栈初始为空，输入序列为：a，b，c，d。
经过入栈、入栈、出栈、入栈、出栈、入栈操作之后，栈中的元素(从栈底到栈顶)依次为( A )A．a，d B．a,c C．b，cD．d,a21．设栈初始为空，输入序列为：a,b,c。
经过入栈、出栈、入栈、入栈、出栈操作之后，从栈中输出的序列为( b ) A．a,b B．b,a C．a,c D．b,c22．栈结构通常采用的两种存储结构是( A ) A．顺序存储结构和链表存储结构B．链表存储结构和数组C．线性存储结构和非线性存储结构D．散列方式和索引方式23．有6个元素按6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列?( C)A．5，4，3，6，1，2 B．4，5，3，1，2，6C．3，4，6，5，2，1 D．2，3，4，1，5，624．设栈S最多能容纳4个元素，现有6个元素按a,b,c,d,e,f 顺序进栈，入栈、出栈操作可随时进行，可能的出栈序列是（C）A．e,b,c,d,a,f B．b,c,e,f,a,d C．c,b,e,d,a,fD．a,d,f,e,b,c25．一个队列的入队的序列是1，2，3，4，在入队操作的同时，随时有出队的操作，则能够实现的输出序列是（A）A．1234 B．1432 C．3241 D．4321 26．设队列初始为空，入队序列为：a，b，c，d。
经过入队、入队、出队、出队、入队、入队操作之后，队列中从队首至队尾的元素依次为（A）A．c，d B．b，a C．c，b D．a，b 27．二维数组A[10][20]采用行序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][l2]的地址是( C )A．315 B．326 C．332D．33828．稀疏矩阵一般的压缩存储方法有两种，即( C)。
A．二维数组和三维数组B．三元组和散列C．三元组和十字链表D．散列和十字链表29．.若完全二叉树的某结点无左孩子结点，则( A ) A．它一定是叶子结点B．它可能有右孩子结点C．它一定是在最低层D．以上说法均不对30．设二叉树共有n个叶子结点，所有非叶子结点都有左右子树，则此二叉树共有的结点数是( D)A．2(n-1) B．2n+1 C．2n D．2n-131．.二叉树与树是两个不同的概念，二叉树的根结点有( A)。
A．0个或1个B．0个或多个C．且仅有一个D．一个或一个以上32．深度为5的二叉树至多有( B )个结点。
A．30 B．31 C．32 D．63 33．一棵深度为k(k≥1)的完全二叉树，其结点个数至多为（2的k次方-1）A．2k-1-1 B．2k-1 C．2k-1 D．2k 34．深度为5的二叉树的结点最多有（ C ）A．10个B．16个C．31个D．32个35．具有n个结点的完全二叉树的深度为( D ) A．┌log2n┐B．[log2n] C．┌log2n┐+1D．[log2n]+136．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( B)。
A．2h B．2h-1 C．2h+1 D．h+137．二叉树的第i（i≥1）层上结点个数至多有（2的i-1次方）A．2i-1-1 B．2i-1C．2i-1 D．2i38．具有65个结点的完全二叉树其深度为( C)(根的结点号为1)A．8 B．7 C． 6 D．539．已知某二叉树的后序遍历序列是d a b e c，中序遍历序列是d e b a c，则它的前序遍历序列是( C)A．a c b e d B．d e c a bC．c e d b a D．d e a b c40．在顺序表(3，6，8，10，12，15，16，21，25，30)中，用二分法查找值11，所需比较次数为( C )A．2 B．3 C． 4 D．541．树是由一个或多个结点组成的有序集合，它有( A )称为根(root)的结点。
A．0个或1个B．0个或多个C．且仅有1个D．1个或1个以上42．对长度为n的顺序表进行顺序查找，在等概率查找情况下，查找成功的平均查找长度为（B）A．(n-1)／2 B．n／2 C．(n+1)／2 D．n 43．散列函数处理冲突中的开地址法包含( B ) A．拉链法和线性探测法B．线性探测法和双重散列法C．拉链法和双重散列法D．拉链法和伪随机数法二、填空题1．从逻辑上抽象地反映__数据元素___之间的结构关系称为数据的逻辑结构。
2．把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的结构称为__数据的存储结构（也称数据的物理结构）_。
3．从逻辑上抽象地反映数据元素之间的结构关系，称之为数据的__数据的逻辑结构__。
4．顺序存储结构是把____相邻___的数据元素存储在物理上相邻的存储单元中。
5．在一个长度为n的顺序表中的第i(1≤i≤n)个元素之前插入一个元素时，需向后移动____n-i+1_______个元素。
6．在线性表的顺序存储结构中，设第一个元素的存储地址是1000，每个元素的长度为4，则第10个元素的地址是_____1000+（10-1）*4=1036________。
7．在线性表中，元素之间存在着线性逻辑关系，元素ai-1被称为元素ai的_____前件（前驱）_______。
8．设二维数组A，行下标的范围是1到6，列下标的范围是0到9，每个元素占有8个字节。
数组A所需的存储空间大小为_____480______个字节。
9．采用FIFO(先进先出)的线性表称为_____队列______。
10．不含任何数据元素的栈称为__空栈____。
11．栈的特点是___先进后出，后进先出____，队列的特点是___先进先出，后进后出____。
12．设有二维数组A[10][20]，其每个元素占两个字节，数组以列序为主序存储，第一个元素的存储地址为100，那么元素A[7][7]的存储地址为______。
13．二维数组A[8][10]采用列序为主顺序存贮，每个数组元素占2个存储单元，且第1行，第1列的数据元素a[0][0]的存储地址是500，则a[6][8]的存贮地址是___ __。
14．数组A中的每个元素占4个字节，行下标i从0到8，列下标j从1到10，存储该数组至少需要____________个字节。
15．设一棵二叉树有10个度为2的结点，则该二叉树的叶子结点的个数为______11_______。
16．具有n(n≥2)个结点的二叉树采用二叉链表进行存储，在这2n个指针域中共有______个指针域是空的。
17．在一棵二叉树中，设度为0的结点个数为n0，度为2的结点个数为n2，则n0与n2的关系为n0=___n2+1_________。
三、简答题1．试举例说明数据的顺序存储结构。
2．分别画出3个结点的二叉树的所有不同形态。
3．一棵二叉树的先序、中序遍历序列分别如下，请构造出该二叉树。
先序——ABDGHECFIJ中序——GDHBEACIJF4．有一棵二叉树如下图所示，试写出该二叉树的先序遍历和后序遍历序列。