下载文档原格式
数据结构考试题目和答案一、单项选择题1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一的对应关系D. 结构中元素之间是否有层次关系答案：D2. 一个栈的入栈序列为1, 2, 3, 4, 5，则可能的出栈序列为（）。
A. 4, 3, 2, 5, 1B. 5, 4, 3, 2, 1C. 5, 4, 3, 1, 2D. 1, 2, 3, 4, 5答案：B3. 在二叉树中，度为2的节点数为n，度为1的节点数为m，度为0的节点数为p，则m的值为（）。
A. nB. n-1C. p-1D. p+1答案：B4. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别在于（）。
A. 是否使用链表B. 是否使用数组C. 是否使用额外的存储空间D. 是否使用线性探测答案：C5. 对于一个无向图，其邻接矩阵表示法中，矩阵的行数和列数分别为（）。
A. 顶点数和边数B. 顶点数和顶点数C. 边数和边数D. 边数和顶点数答案：B二、填空题1. 在顺序表中，插入一个元素平均需要移动元素的个数为表长减1，即 _______ 。
答案：n-12. 快速排序算法的时间复杂度为 _______ 。
答案：O(n^2)3. 折半查找法的平均查找长度为 _______ 。
答案：O(log n)4. 在图的遍历中，深度优先搜索（DFS）使用的栈是_______ 。
答案：非必需的5. 一个完全二叉树有15个度为2的节点，则该树的叶子节点数为 _______ 。
答案：16三、简答题1. 什么是二叉搜索树？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。
其特点包括：- 每个节点的左子树只包含小于节点值的节点。
- 每个节点的右子树只包含大于节点值的节点。
- 左子树和右子树也必须是二叉搜索树。
数据结构题型
以下是一些常见的数据结构题型：
1. 数组操作：包括数组的插入、删除、查找、排序等操作。
2. 链表操作：包括链表的插入、删除、查找等操作。
常见的链表问题包括反转链表、合并两个有序链表等。
3. 栈和队列操作：栈和队列属于线性结构，栈是后进先出（LIFO）的数据结构，队列是先进先出（FIFO）的数据结构。
常见的栈和队列问题包括括号匹配、计算器等。
4. 树操作：包括二叉树、二叉搜索树、平衡树（如AVL树、
红黑树）等。
常见的树问题包括遍历、查找、插入、删除等。
5. 图操作：包括图的遍历、最短路径、最小生成树等。
常见的图问题有深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra算法、Prim算法等。
6. 哈希表：哈希表是一种根据键（Key）直接访问内存存储位
置的数据结构。
常见的哈希表问题包括求最长不重复子串、两数之和等。
7. 堆操作：堆是一种特殊的树结构，常见的堆有二叉堆、最大堆、最小堆等。
常见的堆问题包括找到前k个最大/最小元素、合并k个有序数组等。
8. 字符串操作：包括字符串的操作、匹配、查找等。
常见的字符串问题有字符串转换整数、最长回文子串等。
以上只是介绍了一些常见的数据结构题型，实际情况还有更多其他类型的题目。
在解决数据结构问题时，需要根据题目的具体要求选择合适的数据结构，并结合相应的算法进行解答。
数据结构常见题型整合1、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。
2、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )(A) f->next=c；f=s (B) r->next=s；r=s(C) s->next=r；r=s (D) s->next=f；f=s3、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。
A. N/2 , NB. N , N/2C. 0 , ND. N , 04、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。
6、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if (Q.rear == Q.front) …B．if (Q.rear == (Q.front + MAXQSIZE))C．if (Q.rear == (Q.front + 1) % MAXQSIZE)的元素个数为（）。
A．(rear-front+m)%m B．rear-front+1C．(front-rear+m)%m D．(rear-front)%m8、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和5B. 2和4C. 4和2D. 5和19、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（）。
A. 1 , 3 , 4 , 8B. 8 , 4 , 3 , 1C. 2 , 5 , 0 , 4D. 4 , 0 , 5 , 210、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A. (rear+1) MOD n=frontB. rear=frontC．rear+1=front D. (rear-l) MOD n=front11、栈和队列的共同点是（）。
数据结构试题及答案一、选择题题目1：以下哪一个不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个前件和一个后件C. 数据元素之间存在一对一的线性关系D. 数据元素可以任意插入和删除答案：D解析：线性结构的基本特征包括有且只有一个根节点，每个节点最多有一个前件和一个后件，数据元素之间存在一对一的线性关系。
数据元素任意插入和删除是线性表的特点，但不是线性结构的基本特征。
题目2：下列哪种排序算法的平均时间复杂度是 O(n log n)？A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序答案：C解析：快速排序在平均情况下的时间复杂度为 O(n log n)，而冒泡排序、选择排序和插入排序的平均时间复杂度均为O(n^2)。
二、填空题题目3：在树形结构中，节点拥有的子节点的个数称为______。
答案：度解析：在树形结构中，节点拥有的子节点的个数称为“度”。
例如，一个节点有两个子节点，则其度为2。
题目4：对于具有 n 个节点的二叉树，其完全二叉树的最小深度为______。
答案：log2(n+1)解析：完全二叉树的最小深度是最后一个节点所在的层级。
对于具有 n 个节点的二叉树，其最小深度为 log2(n+1)。
三、判断题题目5：堆排序是一种不稳定的排序算法。
（对/错）答案：对解析：堆排序是一种不稳定的排序算法。
在堆排序过程中，相等的数据元素可能会改变它们在原数组中的相对位置。
题目6：在顺序存储结构中，数据的插入和删除操作的时间复杂度是 O(1)。
（对/错）答案：错解析：在顺序存储结构中，数据的插入和删除操作的时间复杂度不是 O(1)。
当插入或删除的位置不是在数组的末尾时，需要移动大量元素，其时间复杂度为 O(n)。
四、应用题题目7：给定一个长度为 n 的整数数组 arr，请编写一个算法，找出数组中的旋转点。
假设数组中不包含重复元素，并且原数组是一个升序排序的数组。
例如，数组 `[4, 5, 6, 7, 0, 1, 2]` 的旋转点是 4。
数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。
每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。
下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。
2. 在二叉搜索树中，中序遍历的结果是________。
编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。
2. 二叉树每个节点最多有______个子节点。
编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。
每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。
天津市考研计算机复习资料数据结构常见题型解析数据结构是计算机科学中的重要基础课程之一，它研究的是数据的组织、存储和管理方式。
在天津市考研计算机专业的复习中，数据结构常常是考试中的重点内容。
本文将对数据结构的常见题型进行解析，帮助考生更好地复习和应对考试。
一、线性表线性表是数据结构中最基本的一种数据结构，常见的线性表包括数组、链表、栈和队列。
在考试中，出现线性表的题型多为应用题和基本操作题。
1. 应用题应用题常常会给出一个具体的场景或问题，要求考生利用线性表的知识进行解答。
比如，给出一段文字，要求统计文字中每个字母出现的次数。
在这种题型中，考生需要选择合适的线性表来存储数据，并设计相应的算法进行处理。
2. 基本操作题基本操作题主要考查考生对线性表的基本操作的掌握程度。
常见的操作包括插入、删除、查找等。
考生需要熟悉不同线性表的实现方式，并能够根据题目要求选择合适的数据结构和算法进行操作。
二、树树是一种用来描述具有层次关系的数据结构，常见的树包括二叉树、二叉搜索树和平衡二叉树等。
在考试中，树的题型多为遍历操作和树的建立与转换。
1. 遍历操作树的遍历是指按照一定次序访问树的每个节点，常见的遍历方式包括前序遍历、中序遍历和后序遍历。
考生需要熟悉不同遍历方式的实现方法，掌握递归和非递归的两种解法。
2. 树的建立与转换树的建立与转换题型常常给出一些具体的条件，要求考生根据条件构建相应的树或进行树的转换。
考生需要熟悉树的表示方法，并能够根据题目要求进行操作。
三、图图是一种用来描述事物之间关系的数据结构，常见的图包括无向图、有向图和带权图等。
在考试中，图的题型多为图的遍历和最短路径求解。
1. 图的遍历图的遍历是指按照一定次序访问图的每个节点，常见的遍历方式包括深度优先搜索（DFS）和广度优先搜索（BFS）。
考生需要熟悉不同遍历方式的实现方法，并能够根据题目要求进行操作。
2. 最短路径求解最短路径求解是指寻找图中两个节点之间的最短路径，常见的算法包括迪杰斯特拉算法和弗洛伊德算法。
1、以下哪种数据结构常用于实现栈？A、链表B、数组C、二叉树D、哈希表（答案：B）2、在二叉搜索树中，若一个节点的左子树不为空，则左子树上所有节点的值都____该节点的值。
A、大于B、小于C、等于D、不确定（答案：B）3、队列这种数据结构遵循的访问原则是？A、先进先出B、后进先出C、随机访问D、按优先级访问（答案：A）4、图数据结构中，用来表示图中顶点之间关系的元素称为？A、顶点B、边C、路径D、环（答案：B）5、以下哪种数据结构最适合用于快速查找操作？A、链表B、栈C、哈希表D、队列（答案：C）6、在顺序存储的线性表中，第i个元素的存储地址是？A、随机的B、与i无关C、通过计算首地址和i的关系得到D、由用户自定义（答案：C）7、下列关于二叉树遍历的说法中，错误的是？A、前序遍历首先访问根节点B、中序遍历对于任何节点，其左子树节点先于该节点被访问C、后序遍历的最后一个被访问的节点是根节点D、层次遍历是从根节点开始，自上而下逐层遍历（答案：D）8、以下哪种情况不会导致二叉搜索树退化成链表？A、插入的元素按递增顺序B、插入的元素按递减顺序C、随机插入元素D、插入的元素先递增后递减（答案：C）9、在哈希表中，解决冲突的方法不包括？A、开放寻址法B、链地址法C、再哈希法D、二分查找法（答案：D）10、关于树的深度优先搜索（DFS），以下描述错误的是？A、DFS需要使用栈来辅助实现B、DFS可以遍历图或树的所有节点C、DFS对于每个节点只访问一次D、DFS总是先访问深度最深的节点（答案：D）。
数据结构习题集一、选择题1．数据结构中所定义的数据元素，是用于表示数据的。
（C）A.最小单位B.最大单位C.基本单位D.不可分割的单位2．从逻辑上可以把数据结构分为（C）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构3．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A )A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法4．关于串的的叙述，不正确的是( B)A.串是字符的有限序列B.空串是由空格构成的串C.替换是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5．带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（A ）A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B）A.n/2B.nC.(n+1)/2D.n+17．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A）A.nB.2n-1C.2nD.n28．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B )A.236B.239C.242D.2459．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A )A.dceabB.decbaC.edcbaD.abcde10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为(D )A.top=topB.top=n-1C.top=top-1D.top=top+111．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（B）A.13B.35C.17D.3612．栈和队列( C )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处13．含有n个结点的二叉树用二叉链表表示时，空指针域个数为(C )A.n-1B.nC.n+1D.n+214．对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（B）A.99B.98C.97D.5015．在一个图中，所有顶点的度数之和与图的边数的比是( C)A.1∶2B.1∶1C.2∶1D.4∶116．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为(A )A.n-1B.nC.n+1D.n/217．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ B ）A.nB.n-1C.n+1D.2(n-1)18．若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（D）A.先序遍历B.中序遍历C.后序遍历D.层次遍历19．对线性表进行二分查找时，要求线性表必须( C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列20．二分查找算法的时间复杂度是（D）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)21．采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（C）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡22. 闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( B)A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的23．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。
数据结构期末总结题型一、引言数据结构是计算机领域中的重要基础课程之一，是计算机科学与技术、软件工程等专业的核心基础知识。
数据结构主要包括线性结构、树形结构、图形结构等。
本文将对数据结构期末考试常见的题型进行总结和归纳，以帮助同学们复习和备考。
二、常见题型1. 链表题链表题是数据结构中常见的题型，通常会考察链表的创建、插入、删除、查找、反转等操作。
创建链表的方法有多种，常见的有头插法和尾插法。
插入节点、删除节点操作也是经常出现的。
查找链表中的某个节点，可以通过遍历每个节点，直到找到目标节点。
反转链表是一个比较典型的题型，通常会要求使用迭代或递归的方式来实现。
2. 栈和队列题栈是一种后进先出（LIFO）的数据结构，队列是一种先进先出（FIFO）的数据结构。
栈和队列都是线性结构。
常见的栈和队列题有：判断括号是否匹配、计算逆波兰表达式、实现队列等。
判断括号是否匹配可以使用栈来实现，遇到左括号入栈，遇到右括号出栈并判断是否匹配。
计算逆波兰表达式也可以使用栈来实现，遇到数字入栈，遇到操作符出栈两个数字进行计算并将结果入栈。
3. 树和二叉树题树是一种数据结构，由若干个节点组成，每个节点可以有若干个子节点。
二叉树是一种特殊的树，每个节点最多只有两个子节点。
常见的树和二叉树题有：判断两棵树是否相同、判断是否为二叉搜索树、求二叉树的最大深度、层次遍历二叉树等。
判断两棵树是否相同可以使用递归的方式来实现，遍历每个节点并比较。
判断是否为二叉搜索树可以使用中序遍历的方式，判断遍历结果是否为升序。
求二叉树的最大深度可以使用递归的方式，分别求左子树和右子树的最大深度，然后取两者中的较大值加上当前节点的深度。
层次遍历二叉树可以使用队列来实现，先将根节点入队列，然后每次从队列中取出一个节点，并将其左右子节点入队列。
4. 图题图是一种非线性结构，由若干个节点和边组成。
图常用来表示网络、地图等实际问题。
常见的图题有：图的邻接矩阵和邻接表的表示、图的深度优先搜索和广度优先搜索等。
数据结构题库及答案Excel1. 单链表的插入操作- 问题：请描述在单链表中插入一个新节点的步骤。
- 答案：首先确定插入位置，然后创建一个新节点。
将新节点的next指针指向原链表中该位置的节点。
接着，更新前一个节点的next指针指向新节点。
最后，如果插入位置是链表头部，则更新头指针。
2. 二叉树的遍历方法- 问题：请列举二叉树的三种基本遍历方法。
- 答案：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）。
3. 哈希表的冲突解决方法- 问题：在哈希表中，如何解决冲突？- 答案：常见的冲突解决方法有开放地址法（线性探测、二次探测、双重哈希）和链地址法。
4. 堆排序的基本原理- 问题：堆排序的基本原理是什么？- 答案：堆排序基于二叉堆数据结构，通过构建最大堆或最小堆，然后逐步将堆顶元素与堆尾元素交换，缩小堆的范围，最后得到有序序列。
5. 图的深度优先搜索（DFS）- 问题：请简述图的深度优先搜索（DFS）的基本思想。
- 答案：DFS从图的某个顶点开始，沿着邻接表的边尽可能深地搜索，直到无法继续为止，然后回溯到上一个顶点，继续搜索其他邻接顶点。
6. 快速排序算法的时间复杂度- 问题：快速排序算法的平均时间复杂度是多少？- 答案：快速排序算法的平均时间复杂度为O(n log n)。
7. 栈的后进先出（LIFO）特性- 问题：栈的后进先出特性是如何体现的？- 答案：栈的LIFO特性体现在元素的添加和删除操作都发生在栈顶，即最后添加的元素最先被删除。
8. 队列的先进先出（FIFO）特性- 问题：队列的先进先出特性是如何体现的？- 答案：队列的FIFO特性体现在元素的添加操作在队尾进行，而删除操作在队首进行，即最先添加的元素最先被删除。
9. 最小生成树的构造方法- 问题：请列举两种最小生成树的构造方法。
- 答案：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
10. 动态规划的适用场景- 问题：动态规划适用于解决哪些类型的问题？- 答案：动态规划适用于具有重叠子问题和最优子结构特性的问题，如斐波那契数列、背包问题、最长公共子序列等。
数据结构常见题型整合1、设栈的输入序列是1，2，3，4, 则（）不可能是其出栈序列。
A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，2、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )(A) f->next=c；f=s (B) r->next=s；r=s(C) s->next=r；r=s (D) s->next=f；f=s3、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。
A. N/2 , NB. N , N/2C. 0 , ND. N , 04、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX5、一个递归算法必须包括（）。
A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分6、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if (Q.rear == Q.front) …B．if (Q.rear == (Q.front + MAXQSIZE))C．if (Q.rear == (Q.front + 1) % MAXQSIZE)D．if (Q.front == (Q.rear + 1) % MAXQSIZE)7、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
A．(rear-front+m)%m B．rear-front+1C．(front-rear+m)%m D．(rear-front)%m8、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和 5B. 2和4C. 4和2D. 5和110、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A. (rear+1) MOD n=frontB. rear=frontC．rear+1=front D. (rear-l) MOD n=front11、栈和队列的共同点是（）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点1、栈是___操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循___后进先出____的原则。
2、队列的插入操作在_ 队尾__进行，删除操作在队头___进行，其特点是__先进先出__。
3、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为___S×SS×S×× __。
4、表达式求值是___栈____应用的一个典型例子。
5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是线性表。
6、在作进栈运算时，应先判别栈是否 . 满，在作退栈运算时应先判别栈是否空。
当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 n 。
12、在二叉树的第I层(I≥1)上最多含有结点数为（）A. 2IB. 2I-1-1C. 2I-1D. 2I -113、深度为6的二叉树最多有( )个结点A．64 B.63 C.32 D.3114、一棵树高为K的完全二叉树至少有( )个结点A.2k–1B.2k-1 –1C.2k-1D.2 k15、有关二叉树下列说法正确的是（）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为2E F D G A B /++* - C * 16、n 个结点的线索二叉树上含有的线索数为（ ） A. 2n B. n －l C. n ＋l D. n17、线性表和树的结构区别在于（ ） A ．前驱数量不同，后继数量相同 B ．前驱数量相同，后继数量不同 C ．前驱和后继的数量都相同D ．前驱和后继的数量都不同18、已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，则其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE19、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D. A*B+C/D*E+F-G20、一棵具有 n个结点的完全二叉树的树高度（深度）(符号⎣⎦x表示取不大于x的最大整数)是（）21、利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空22、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定23、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。
24、线索二叉树是一种（）结构。
A．逻辑 B．逻辑和存储 C．物理 D．线性二、填空题7、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___ N2 + 1_________。
8、具有256个结点的完全二叉树的深度为___9___。
9、一个深度为4的二叉树，其结点至少有 4 个，至多有 15 个：10、深度为H 的完全二叉树至少有_ 2H-1__个结点；至多有2H-1_个结点；H和结点总数N 之间的关系是H=ëlog2Nû+1。
11、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，N个结点的二叉树共有__2N__个指针域，其中有_N-1__个指针域是存放了地址，有__N+1_____个指针是空指针。
12、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是__63____13、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为⎣⎦2/i。
14、赫夫曼树是带权路径长度最小的二叉树，又称最优二叉树，路径上权值较大的结点离根较近。
15、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。
typedef struct node{ int data;struct node *lchild;_struct node *rchild __;} BiTNode, *BiTree;void createBitree(BiTree &T){ scanf(“%c”, &ch);if(ch=='#') T=NULL ;else{ T=( BiTNode *)malloc(sizeof(BiTNode));T->data=ch;createBitree(T->lchild)；___createBitree(T->rchild);}}16、二叉树由_根结点__，__左子树_，_右子树__三个基本单元组成。
17、树的链表存储结构常用的有三种，其中，双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。
孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。
孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。
//P135-13618、利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。
19、在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==NULL &&p->rchlid==NULL _____。
20、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
21、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。
二叉树的度至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制。
三、简答题1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树，并写出后序遍历结果。
答案：当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：这棵二叉树的后序遍历结果是：K D C B I H J G F A2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是16，5，7，3，8，1。
试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。
为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。
答案：哈夫曼树如下：对应的哈夫曼编码如下：A: 0B: 101C: 110D: 1001E: 111F: 1000带权路径长度为: WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序﹑中序﹑后序遍历，给出相应的结点序列，同时给二叉树加上中序线索。
答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA（4）中序线索见图中虚线箭头所示。
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关27、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历28、图的广度优先遍历算法类似于树的（）。
A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历29、设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．030、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A．n-1 B．n C．n+1 D．nlogn；31、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于032、要连通具有n个顶点的有向图，至少需要（）条边。
