数据结构练习题--2011级--参考答案

1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。

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

3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。

5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。

7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。

8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（图）。

9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。

11.带头结点的单链表h为空的判断条件是（h->next== NULL）。

12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。

14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。

16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。

19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。

第七章图一、选择题1．图中有关路径的定义是（）。

A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。

A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。

A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。

A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。

一、填空题1．数据结构根据数据元素之间关系的不同特性，有四种基本结构：集合、线性结构、和。

2．数据结构的形式定义可用二元组表示，其成分分为数据元素的有限集，和。

3．一个好的算法设计应满足正确性、、健壮性和效率与低存储量需求。

4．数组是一种存取的存储结构。

5．串中组成的子序列称该串的子串。

6．稀疏矩阵存储时，常采用三元组表和的表示方法。

7．设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子结点的个数是。

8．指针pred 指向刚刚访问过的结点，p 指向当前访问的结点，结点的结构含有左指针lchild，右指针rchild，左标志ltag，右标志rtag，当结点的左指针为空时，线索化操作为：p->ltag=1；和。

9．用图的顶点表示活动，用弧表示活动间的优先关系的有向图称为网。

10．排序方法稳定的，是指排序后的序列中的元素前后次序仍不变。

11．文件在存储介质（磁盘或磁带）上的组织方式称为文件的。

12．索引文件是包括和索引表两大部分的文件。

13．在算法是正确的前提下，评价算法的两个标准是、。

14．链表是一种存取的存储结构。

15．设链栈的栈顶指针为LS，链栈的结点结构为，栈空的条件是。

16．在非空双链表（结点结构为）中，指针p指向该链表中的某个结点。

若要指针p往前移动两个结点，即使p指向当前结点的前驱的前驱（假定存在这样的结点），则需要执行一个语句。

17．设无向图G用邻接表表示，图中顶点V i的度等于。

18．中序遍历二叉排序树可得到一个关键字的。

19．后序遍历如图所示的一棵二叉树，所得到结点序列为。

20．在有n 个叶子结点的哈夫曼树中，其结点总数为 。

21．含有n 个顶点的无向图是一个环，则它有 棵生成树。

22．设单链表的结点结构为，且r 始终指向单链表的最后一个结点，要在最后一个结点之后插入由s 所指向的结点，需要执行的三条语句是 ；r=s ；s->next=NULL ；23．串中任意个连续的字符组成的子序列称为 。

二、填空题1. 线性表是一种典型的___线性______结构。

2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。

3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。

4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。

5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。

6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。

7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。

相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。

8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。

9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。

10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。

11. 在单链表中设置头结点的作用是__使空表和非空表统一______。

12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。

13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

《数据结构》练习题一、选择题1．一个数组元素a[i]与（ A ）的表示等价。

A ．*（a+i ） B ．a+i C ．*a+i D ．&a+ia 是存储的是数组首地址，*a 指向的就是数组第一个元素a[0],所以*（a+i ）的地址和a[i]的地址一样。

数组和指针在一定程度上本质是一样的。

2．当利用大小为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则退栈时，修改top 指针的语句是（ A ）。

A ．top++;B ．top=0;C ．top--;D ．top=N; 3．队列的删除操作是在（ A ）进行。

A ．队首B ．队尾C ．队前D ．队后队列删除元素是在队首进行，队列是进先先出，相对来说，队首元素是最先进入队列的，因此出队应该是在队首进行。

队列其实就和我们平时排队一样的4．二叉树上叶子结点数等于（ C ）。

A ．分支结点数加1B ．单分支结点数加1C ．双分支结点数加1D ．双分支结点数减15．哈希冲突是指（ D ）。

A ．两个元素具有相同的序号B ．两个元素的键值不同，而其他属性相同C ．数据元素太多D ．不同键值的元素对应于相同的存储地址6．由权值分别为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。

A ．51B ．23C ．53D ．742310 135 56 72 3(2+3)*3+5*2+(6+7)*2=517．某程序的时间复杂度为)log log 1003(22n n n n +⨯+，其数量级表示为（ B ）。

A ．O(n)B ．)log (2n n OC ．O(100)D ．)(log 2n O8．从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。

A ．O(n)B ．O(1)C ．)(log 2n OD ．)(2n O9．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则装填因子α等于（ A ）。

数据结构基本概念练习题1、选择练习题1）执行下面程序段时，执行S语句的次数为-------for(int I=1;I<=n;I++)for(int j=1;j<=I;j++)S;(A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2答案：D2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。

下列______不属于算法的五个特性之一。

(A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性答案：D3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

(A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表答案：A4）下面的叙述正确的是（）(A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比;(B) 线性表在链式存储时，查找第i个元素的时间同i的值无关;(C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比;(D) 以上说法都不对.答案：A5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

(A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表答案：B6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。

(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;答案：C7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

数据结构练习题1一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）2. 以下说法错误的是（）。

A. 抽象数据类型具有封装性。

B. 抽象数据类型具有信息隐蔽性。

C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。

D. 抽象数据类型的一个特点是使用与实现分离。

3. 设有一个n n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。

A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/24. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。

A. O(1)B. O(m)C. O(n)D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front == rearB. front != NULLC. rear != NULLD. front == NULL7. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。

A. 2h-1B. 2h+1C. 2h-1D. 2h8. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。

A 1B 2C 3D 49. 向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为( )。

A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)10. 具有n个顶点的有向无环图最多可包含( )条有向边。

A．n-1 B．n C．n(n-1)/2 D．n(n-1)11. 图的广度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次12. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

1、栈的“先进后出”特性是指（）。

A.最后进栈的元素总是最先出栈B.同时进行进栈和出栈操作时，总是进栈优先C.每当有出栈操作时，总要先进行一次进栈操作D.每次出栈的元素总是最先进栈的元素正确答案：A2、给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D, 则以C、D开头的出栈序列的个数为（）。

A.1B.2C.3D.4正确答案：A解析：若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有CDBA 一个。

3、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（）OA. dcebfaB.cbdaefC.bcaefdD. afedcb正确答案：D 解析：选项A操作：a进，b进，c进，d进，d出，c出，e进，e 出，b出，f进，f出，a出。

选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e 进，e出，f进，f出。

选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e 出，f进，f出，d出。

选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e 出，d出，c出，b出。

从中看到，选项D中最后连续出栈5次，不符合要求。

4、一个栈的进栈序列是a、b、c、d> e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde正确答案：C解析：对于选项A, a、b、c^ d、e进栈，e、d^ c、b、a出栈；对于选项B, a, b, c, d进栈，d出栈，e进栈，e出栈，c、b、a 依次出栈；对于选项C, a、b、c^ d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b,不可能a先出栈，所以C是不可能的输出序列；对于选项D, a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d 进栈，d出栈，e进栈，e出栈。

数据结构与算法练习题库（含答案）一、单选题（共80题，每题1分，共80分）1、对一棵二叉树的结点从 1 开始顺序编号。

要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。

可采用▁▁▁▁▁ 实现编号。

A、中序遍历B、先序遍历C、层次遍历D、后序遍历正确答案：A2、设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？A、5B、4C、2D、0正确答案：C3、两个有相同键值的元素具有不同的散列地址A、一定不会B、一定会C、可能会D、有万分之一的可能会正确答案：C4、将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。

散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。

问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.73B、0.27C、0.64D、0.45正确答案：D5、对N个记录进行归并排序，归并趟数的数量级是：A、O(NlogN)B、O(logN)C、O(N)D、O(N2)正确答案：B6、下列说法不正确的是：A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、图的深度遍历不适用于有向图C、遍历的基本算法有两种：深度遍历和广度遍历D、图的深度遍历是一个递归过程正确答案：B7、二叉树的中序遍历也可以循环地完成。

给定循环中堆栈的操作序列如下（其中push为入栈，pop为出栈）： push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()A、6是根结点B、2是4的父结点C、2和6是兄弟结点D、以上全不对正确答案：C8、设最小堆（小根堆）的层序遍历结果为{1, 3, 2, 5, 4, 7, 6}。

数据结构与算法考试题+答案一、单选题（共100题，每题1分，共100分）1.Excel工作表D列保存了18位身份证号码信息，为了保护个人隐私，需将身份证信息的第9到12位用“*”表示，以D2单元格为例，最优的操作方法是：A、=MID(D2,1,8)+"****"+MID(D2,13,6)B、=CONCATENATE(MID(D2,1,8),"****",MID(D.13,6))C、=REPLACE(D2,9,4,"****")D、=MID(D2,9,4,"****")正确答案：C2.小李正在Word中编辑一篇包含12个章节的书稿，他希望每一章都能自动从新的一页开始，最优的操作方法是：A、在每一章最后连续按回车键Enter，直到下一页面开始处B、将每一章标题指定为标题样式，并将样式的段落格式修改为“段前分页”C、在每一章最后插入分页符D、将每一章标题的段落格式设为“段前分页”正确答案：B3.在Excel2010中，要在某个单元格区域的所有空单元格中填入相同的内容，最佳的操作方法是：A、逐一选中这些空单元格，并输入相同的内容B、按住Ctrl键，同时选中这些空单元格，然后在活动单元格中输入所需内容，并使用Ctrl+Enter组合键在其他空单元格中填入相同内容C、选中包含空单元格的区域，并定位到空值，然后在活动单元格中输入所需内容，并使用正确答案：C4.建立表示学生选修课程活动的实体联系模型，其中的两个实体分别是A、课程和成绩B、学生和学号C、课程和课程号D、学生和课程正确答案：D5.PowerPoint2010演示文稿的首张幻灯片为标题版式幻灯片，要从第二张幻灯片开始插入编号，并使编号值从1开始，正确的方法是：A、直接插入幻灯片编号，并勾选“标题幻灯片中不显示”复选框B、从第二张幻灯片开始，依次插入文本框，并在其中输入正确的幻灯片编号值C、首先在“页面设置”对话框中，将幻灯片编号的起始值设置为0，然后插入幻灯片编号，并勾选“标题幻灯片中不显示”复选框D、首先在“页面设置”对话框中，将幻灯片正确答案：C6.JAVA属于：A、操作系统B、办公软件C、数据库系统D、计算机语言正确答案：D7.某公司需要在Excel中统计各类商品的全年销量冠军，最优的操作方法是：A、在销量表中直接找到每类商品的销量冠军，并用特殊的颜色标记。

数据结构第二单元练习题答案一、选择1.树最适合用来表示( )A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.在下述结论中，正确的是( )①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③B.②③④C.②④D.①④3.以下说法正确的是( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树的度肯定等于2D.任何一棵二叉树的度可以小于24.在下列情况中，可称为二叉树的是( )A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E.以上答案都不对5.深度为h的满m叉树的第k层有( )个结点(1=<k=<h)A.m k-1B.m k-1C.m h-1D.m h-16.在一棵高度为k的满二叉树中，结点总数为( )A.2k-1B.2kC.2k-1D.⎣log2k⎦+17.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个A.4B.5C.6D.78.具有10个叶结点的二叉树中有( )个度为2的结点。

A.8B.9C.10D.ll9.二叉树有n个结点，则其深度为（）A.n-1B.nC.(log2n)+`1D.无法确定该题是二叉树不是完全二叉树由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

10.一个具有1025个结点的二叉树的高h为( )A.11 B．10 C.11至1025之间 D.10至1024之间11.一棵具有 n个结点的完全二叉树的深度是( )A.⎣log2n⎦+1B.log2n+1C.⎣log2n⎦D.log2n-112.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度( )A.4B.5C.6D.713.将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）A.98B.99C.50D.48利用二叉树的性质514.在完全二叉树中，若一个结点是叶结点，则它没( )A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点15.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为( )A.A[2i](2i=<n)B.A[2i+1](2i+1=<n)C.A[i/2]D.无法确定16.在下列存储形式中，( )不是树的存储形式？A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法17.以下说法错误的是( )A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.三叉链表，二叉树求双亲运算很容易实现C．在二叉链表上，求左.右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好18.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。

数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。