下载文档原格式
. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。
2、程序越短，运行的时间就越少。
3、处理同一问题的算法是唯一的。
B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。
三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
2、______________结构的数据元素之间存在一对多的关系。
3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。
4、数据结构在计算机中的______________称为存储结构。
5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。
6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。
7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。
四、解答题1、设n 为正整数。
第一章1．在数据结构中，从逻辑上可以把数据结构分为(C )A．动态结构和静态结构B。
紧凑结构和非紧凑结构C．线性结构和非线性结构D。
内部结构和外部结构● 2.在数据结构中，与所使用的计算机无关的是( A )A。
逻辑结构 B. 存储结构C。
逻辑和存储结构 D. 物理结构3。
下面程序的时间复杂度为____O(mn）_______。
for (int i=1；i〈=m; i++）for （int j=1；j〈=n；j++ ）S+=i第二章线性表●链表不具备的特点是（A)A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2。
不带头结点的单链表head为空的判定条件为（A )，带头结点的单链表head为空的判定条件为（B ）A head==nullB head—〉next==nullC head-〉next==headD head！=null●3.在线性表的下列存储结构中,读取元素花费时间最少的是（D)A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为（C）A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表●5。
在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为（ D ）A O(1）B O(log2n)C O(n2)D O(n）● 6.在一个长度为n （n〉1）的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7。
与单链表相比，双向链表的优点之一是（D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8。
若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域（头结点的地址）中存放的是（ B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则（ B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10。
一、单项选择题1.下面程序段的时间复杂度为( C ) 。
for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A． O(m2) B． O(n2) C． O(m*n) D． O(m+n) 2.设有一个递归算法如下int fact(int n){串的长度 B.原串的子串 C.串的模式匹配 D.串的连接3.设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B 中( C )处。
A．(i+3)*i／2 B．(i+1)*i／2 C．(2n-i+1)*i／2 D．(2n-i-1)*i／24.在( C )运算中，使用顺序表比链表好。
5.A．插入B．删除C．根据序号查找 D．根据元素值查找6.带头结点的单链表head为空的判断条件是( C )。
7.A．head= =NULL B．head->next= =NULLC．head->next=head D．head!=NULL8.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ C ）最节省时间。
A）单链表 B）循环链单表 C）带尾指针的循环链单表 D）带头结点的双循环链表9.栈的插入与删除操作在（A ）进行。
A．栈顶 B．栈底 C．任意位置 D．指定位置10.设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（ D ）。
11.A．ABCD B．DCBA C．ACDB D．DABC12.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是( C )。
13.A．R=F->next; B．R=R->next; C．F=F->next; D．F=R->next;14.串是一种特殊的线性表，其特殊性体现在( B )。
15.A．可以顺序存储B．数据元素是一个字符16.C．可以链接存储D．数据元素可以是多个字符17.以下说法正确的是（C ）。
数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。
A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。
A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。
3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。
例如构成一个数据元素的字段、域、属性等都可称之为_数据项。
4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。
5、数据的逻辑结构是指数据之间的逻辑关系。
逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。
因此逻辑结构可以看作是从具体问题抽象出来的数学模型。
6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。
存储结构是逻辑结构在计算机里的实现，也称之为映像。
7、数据的运算是指对数据施加的操作。
它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。
常用的有：查找、排序、插人、删除、更新等操作。
8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。
9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。
A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。
A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。
logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。
int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。
该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。
6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。
7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。
数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。
A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。
A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。
脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。
A．2k-1 +1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。
A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。
A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
第一章概论一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R ），其中D 是 数据元素 的有限集合，R 是D 上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间 效率和 空间 效率。
二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种：A ）一对多关系B ）多对多关系C ）多对一关系D ）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
1.数据结构是研究数据的( C )以及它们之间的相互关系。
A)存储结构，物理结构 B)理想结构，抽象结构 C)物理结构，逻辑结构 D)抽象结构，逻辑结构2.在数据结构中，与所使用的计算机无关的是数据的( C )结构。
A)存储 B)物理 C)逻辑 D)物理与存储3.数据结构课程主要研究以下三方面的内容，它们是(D)。
A)数据、数据元素、数据类型B)数据元素、数据类型、算法实现 C)数据元素、数据的逻辑结构、数据的存储结构D)数据的逻辑结构、数据的存储结构、数据的运算4.在以下的复杂度量级中，量级最低的是(B)。
A) O(n) B) O(log2n) C) O(nlog2n) D) O(n2)5.在下列叙述中，正确的是(C)。
A)数据的逻辑结构要考虑数据元素本身的内容 B)不同类型的数据元素可以归类到同一的逻辑结构中 C)数据元素之间的关联关系在数据的逻辑结构中体现D)数据元素是数据不可分割的最小标识单位6.计算机算法必须具备输入、输出和(B)等五个特性。
A)可行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、稳定性和有穷性 D)易读性、稳定性和安全性7.算法分析的目的是(D)。
A)找出数据结构的合理性 B)研究算法中的输入/输出关系C)分析算法的易读性 D)分析算法的效率以求改进8.设 n>=10，下面程序段的时间复杂度是(D)。
for(i=10; i<n; i++){ j=k=0;while(j+k<=i)if (j>k) k++;else j++;}A) O (log2n) B) O(n) C) O(nlog2n) D) O(n2)9.计算机算法是指( D )A)计算方法 B)排序方法 C)调度方法 D)解决问题的有限运算序列10.数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构(A)。
A)正确 B) 不正确11.下面说法错误的是(AD )A)算法原地工作的含义是指不需要任何额外的辅助空间B)在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法C)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界D)同一个算法，实现语言的级别越高，执行效率就越低1. 数据元素是数据的最小单位。
数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
习题一一、填空题1. 算法具有有穷性、确定性、可行性、输入和输出五大特征。
2. 数据结构的内容包括以下三个方面：数据元素、数据关系和运算集合。
3. 数据结构的存储结构分为顺序、链式、索引、散列。
4. 评价算法性能的标准主要从算法执行时间和空间两方面考虑。
5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着1对1 、1对多和多对多关系。
二、分析题2.设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。
（1）for(n =1;n<=10;n++)*s=s+n;(2) for(i =1;i<=n;i++)*s=s+n;(3) for(i =1;i<=n;i++)for(j=1;j<=n;j++)*s=s+n(4) for(i =1;i<=n;i++)for(j=1;j<=i ;j++)*s=s+n;（5）for(i =1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)*c[i][j]=c[i][j]+a[i][k]*b[k][j];}习题二3.填空题1.在顺序表中，逻辑上相邻的元素，其物理位置上一定相邻。
2.在单链表中，逻辑上相邻的元素，其物理位置上不一定相邻。
3.设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为P=s->next;s->next=s->next->next;free(p); 。
4.在一个长度为n的顺序表中，如果要删除第i个元素，需移动n-i+1 个元素。
二、选择题1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（C ）存储方式的时间性能最好。
A.双向链表B.双向顺环链表C.顺序表D.单向顺环链表2.在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。
A.s->next=p->next;p->next=sB.p->next=s->next;s->next=pC.q->next=s;s->next=pD.p->next=s;s->next=q3.带头结点的单链表为空的判定条件是（B ）。
A.L=NULLB.L->next=NULLC.L->next=headD.L!=NULL4.某线性表中最常用的操作是存取第i元素及其前驱结点的值，则采用（C ）存储方式能节省时间。
A双向链表 B.双向循环环链表 C.顺序表 D.单向循环环链表5.已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为( D )。
A.R->nextB.*(r->next->next)C.&(r->next->next)D.R->next->next三、编程题6.试将入口为head的有序单链表，按所给关键字k分成两个循环链表。
其中，比k小的所有结点组成入口为h1的循环链表，比k大的所有结点组成入口为h2的循环链表。
9.对于单链表，写出下列操作的算法。
（1）根据一维数组建立一个单链表，使单链表中元素的顺序与数组的次序相同。
（2）统计单链表中值在x~y之间的所有结点个数。
（3）删除单链表中第k个结点开始连续的j个结点。
（4）将该单链表分解为两个单链表，使其中一个单链表中仅含有奇数，另一个单链表中仅含有偶数。
（5）将另一个已经存在的单链表插入到该链表的第k个结点之后。
（6）将单链表中的所有元素排成一个有序序列。
习题三4.分析题1.写出下列程序段的输出结果void main(){stack s;char x,y;stackinit(s); \\构造一个空栈sx=‘c’;y=‘k’;push(s,x); \\将新元素x插入到栈s中push(s,‘a’);push(s,y);pop(s,x); \\从栈s中删除顶元xpush(s,‘t’);push(s,x);pop(s,‘s’);push(s,x);\\判断栈s是否为空，若为空，返回1，否则返回0While(!stackempty(s)){pop(s,y);printf(y);}printf(x);}2.写出以下程序段的输出结果。
void main(){queue q;char x=‘e’;char y=‘c’;queinit(q); //构造一个空队列qenque(q,‘h’); //将元素h到队q的尾部enque(q,‘r’);enque(q,y);deque(q,x); //删除队q的队首元素xenque(q,x);deque(q,x);enque(q,‘a’);while(! queempty(q))//当队q非空{deque(q,y);rintf(y);}printf(x);}习题四一、填空题1. 串是一种特殊的线性表，其特殊性表现在。
2. 串的最基本的两种存储方式为：和。
3. 两个字符串相等的充分必要条件是。
二、串的基本运算题1. 设串a=”very”,b=”good”,c=”I am a student”(1) 调用函数Concat(a,b)和Concat(b,a)的结果各是什么(2) 调用函数Concat(a,Concat(b,c))和Concat(Concat(a,b),c)的结果各是什么(3) 调用函数SubString(c,3,1)和SubString(c,1,3)的结果各是什么(4) 调用函数StrInsert(c,5,b)和StrInsert(b,5,c)的结果各是什么(5) 调用函数I ndex(c,’am’)和I ndex(c,’AM’)的结果各是什么？(6) 调用函数R eplace(c,’a’,a)的结果各是什么？2.试问执行以下函数产生怎样的输出结果? V oid demonstrate(){ StrAssign(S,’THIS IS A BOOK’);Replace(S,substring(s,3,7),’ESE ARE’);StrAssign(t,concat(s,’S’));StrAssign(u,XYXYXYXYXYXY’);StrAssign(v,substring(u,6,3));StrAssign(w,’W’);printf(“t=”,t,”v=”,v,”u=”,replace(u,v,w)) }习题五一、填空题2. 已知有三对角矩阵A8 8压缩存储，其首元素地址Loc(a00)=1000，每个数据元素占用6字节的存储空间，则元素a34的存储地址为。
3. 已知广义表T=(((a),(b)),c,(d),(e,f))，则该广义表表头为，表长为，深度为。
4. 设广义表表头为(a，b)，表尾为(c，(d，e))，则广义表为。
习题6二、填空题1．在树中，一个结点所拥有的子树数称为该结点的（）。
2.度为零的结点称为（）结点。
3.树中结点的最大层次称为树的（）。
4.对于二叉树来说，第i层上至多有（）个结点。
5.深度为h的二叉树至多有（）结点。
6.由一棵二叉树的前序序列和（）序列可唯一确定这课二叉树。
7.有20个结点的完全二叉树，编号为10的结点的父结点的编号是（）。
8.哈夫曼树是带权路径长度（）的二叉树。
9.由二叉树的后序和（）遍历序列，可以唯一确定这棵二叉树。
10.某二叉树的中序遍历序列为：DEBAC，后序遍历序列为EBCAD。
则前序遍历序列为（）。
11.设一棵二叉树结点的先序遍历序列为：ABDECFGH，中序遍历序列为：DEBAFCHG，则二叉树中叶节点是（）。
12.已知完全二叉树的第8层有8个结点，则其叶节点数是（）。
13.由树转换成二叉树时，其根节点无（）。
14.采用二叉链表存储的n个结点的二叉树，一共有（）指针域。
15.采用二叉链表存储的n个结点的二叉树，共有空指针（）个。
16.前序为ABC且后续为CBA的二叉树共有（）种。
17.三个结点可以组成（）种不同形态的树。
18.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为（）。
19.给定如图6-39所示的二叉树，其前序遍历序列为（）。
20. 给定如图6-40所示的二叉树，其层次遍历序列为（）。
三、选择题1.树最适合用来表示（）。
A有序数据元素B无序数据元素C元素之间无联系的数据D元素之间有分支的层次关系2.前序为ABC的二叉树共有（）种。
A2 B3 C4 D53.根据二叉树的定义，具有3个结点的二叉树有（）种树型。
A3 B4 C5 D64.在一棵具有5层的满二叉树中，结点的总数为（）。
A16 B31 C32 D335.具有64个结点的完全二叉树的深度为（）。
A5 B6 C7 D86.任何一颗二叉树的叶节点在前序、中序、后序遍历序列中的相对次序（）。
A不发生任何改变B发生改变C不能确定D以上都不对7.A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（）。
A.A在B右方B.A是B祖先C.A在B左方D.A是B子孙8.下列4棵树中，（）不是完全二叉树。
9.如图6-41所示的二叉树，后续遍历的序列是（）。
A. ABCDEFGHIB. ABDHIECFGC. HDIBEAFCGD. HIDEBFGCA10.如图6-42所示的二叉树，后序遍历的序列是（）。
A. DBEHAFCGB. DBHEAFCGC. ABDEHCFGD. ABCDEFGH11.某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序遍历序列为（）。
A. ABCDEB. DECABC. DEABCD. CEDBA12.具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是（）。
A 2iB 2i+1C 2i-1D 不存在13.把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A 唯一的B有多种C 有多种，但根节点都没有左孩子结点D有多种，但根节点都没有右孩子结点14.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根节点的编号为1，则编号为45的结点的左孩子结点编号为（）。
A 46B 47C 90D 9115. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子结点编号为（）。
A.98B.99C.50D.10016.二叉树按某种顺序线索化后，任一结点均有指向其前驱结点和后继结点的线索，这种说法（）。
A.正确B.错误C.不确定D.都有可能17.下列陈述正确的是（）。
A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子结点时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左、右子树之分18.用5个权值（3,2,4,5,1）构造的哈夫曼树的带权路径长度是（）。
