下载文档原格式
数据结构试卷带答案数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（ 1.C ）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。
(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（D）的逻辑结构。
(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（C）个。
(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B 需要的操作为（.A ）。
(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。
(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。
(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（B）种不同的形态。
(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（B ）的空间复杂度最大。
(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。
数据结构试卷（一）参考答案一、选择题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D 10.A 二、填空题（每空1分，共26分）1. 正确性 易读性 强壮性 高效率2. O(n)3. 9 3 34. -1 3 4 X * + 2 Y * 3 / -5. 2n n-1 n+16. e 2e7. 有向无回路8. n(n-1)/2 n(n-1)9. （12，40） （ ） （74） （23,55，63） 10.增加111.O(log 2n) O(nlog 2n) 12.归并三、计算题（每题6分，共24分）1. 线性表为：（78，50，40，60，34，90）2. 邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111010101110111010101110邻接表如图11所示：图113. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 见图12图124 4 4 4 4 2 2 25 552 2 8 84 352 83 4四、读算法（每题7分，共14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,a n,a1）2.递归地后序遍历链式存储的二叉树。
五、法填空（每空2分，共8 分）true BST->left BST->right六、编写算法（8分）int CountX(LNode* HL,ElemType x){ int i=0; LNode* p=HL;//i为计数器while(p!=NULL){ if (P->data==x) i++;p=p->next;}//while, 出循环时i中的值即为x结点个数return i;}//CountX数据结构试卷（二）参考答案一、选择题1.D2.B3.C4.A5.A6.C7.B8.C二、填空题1.构造一个好的HASH函数，确定解决冲突的方法2.stack.top++，stack.s[stack.top]=x3.有序4.O(n2)，O(nlog2n)5.N0-1，2N0+N16.d/27.(31，38，54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)三、应用题1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储结构略，二叉树略5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.略四、算法设计题1.设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
1内蒙古农业大学职业技术学院2010―2011学年第二学期《数据结构》重修考试卷一、填空题。
（每空1分，共20分） 1、算法的5个特性为_________、 、 、 、 。
2、结构中的数据元素存在多对多的关系称为________结构。
3、结构中的数据元素存在一对多的关系称为________结构。
4、结构中的数据元素存在一对一的关系称为________结构。
5、在一个单链表中p 所指结点之后插入一个s 所指结点时，应执行___ _____和p->next=s;的操作。
6、在一个单向链表中，要删除p 所指结点，又已知q 指向p 所指结点的前驱结点。
则可以用操作________。
7、对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。
8、设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_________个结点。
（根所在结点为第1层）9、一棵有14个结点的完全二叉树，则它的最高层上有_______个结点。
10、二叉树排序中任一棵子树都是二叉排序树，这种说法是_______的。
(回答正确或不正确)11、________遍历二叉排序树可得到一个有序序列。
12、两个串相等的充分必要条件是_______ ___。
13、在双向链表中，每个结点有两个指针域，一个指向________，另一个指向_________。
二、选择题。
（每题2分，共30分）1、带头结点的链表为空的判断条件是（ ）（设头指针为head ）。
A ．head = =NULL B ．head →next= =NULL C ．head →next= =head D ．head!=NULL2、链表所具备的特点是（ ）。
A ．可以随机访问任一结点B ．占用连续的存储空间C ．插入删除不需要移动元素结点D ．可以通过下标对链表进行直接访问 3、非空的单向循环链表的尾结点满足（ ）（设头指针为head ，指针p 指向尾结点）。
数据结构试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是元素之间存在一对一的线性关系。
以下哪个数据结构不属于线性结构？A. 栈B. 队列C. 树D. 链表答案：C2. 栈（Stack）是一种后进先出（LIFO）的数据结构，以下哪个操作不是栈的基本操作？A. PushB. PopC. TopD. Sort答案：D3. 在二叉树的遍历中，前序遍历的顺序是：A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表的冲突可以通过多种方法解决，以下哪个不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再散列法D. 排序法答案：D5. 以下哪个排序算法是稳定的？A. 快速排序B. 堆排序C. 归并排序D. 选择排序答案：C6. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B7. 以下哪个是图的存储方式？A. 顺序存储B. 链式存储C. 散列表D. 矩阵存储答案：D8. 动态数组（如C++中的vector）在插入元素时可能需要进行的操作是：A. 原地扩展B. 复制元素C. 重新分配内存D. 释放内存答案：C9. 以下哪个不是算法的时间复杂度？A. O(1)B. O(log n)C. O(n^2)D. O(n!)答案：D10. 在查找算法中，二分查找法要求被查找的数据必须是：A. 无序的B. 有序的C. 随机分布的D. 唯一元素答案：B二、简答题（每题5分，共30分）1. 简述链表和数组的区别。
答案：链表和数组都是存储数据的线性数据结构，但它们在内存分配、访问方式、插入和删除操作等方面存在差异。
数组在内存中是连续存储的，可以通过索引快速访问任意元素，但插入和删除元素时可能需要移动大量元素。
链表在内存中是非连续存储的，每个元素包含数据和指向下一个元素的指针，不支持通过索引快速访问，但插入和删除操作只需要改变指针，不需要移动其他元素。
一．是非题（正确的打“√”，错误的打“×”。
）1. 数据结构可用三元式表示（D，S，P）。
其中：D是数据对象，S是D上的关系，P是对D的基本操作集。
×2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。
×3. 字符串是数据对象特定的线性表。
4. 二叉树是一棵结点的度最大为二的树。
×5．邻接多重表可以用以表示无向图，也可用以表示有向图。
×6．可从任意有向图中得到关于所有顶点的拓扑次序。
×7．一棵无向连通图的生成树是其极大的连通子图。
×8．二叉排序树的查找长度至多为log2ｎ。
×9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。
除根之外的所有非终端结点至少有┌m/2┐个关键字。
×10．对于目前所知的排序方法，快速排序具有最好的平均性能。
11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
×12. 二维数组是其数据元素为线性表的线性表。
13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。
×14. 折半查找不适用于有序链表的查找。
15. 完全二叉树必定是平衡二叉树。
16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。
17. 队列是与线性表完全不同的一种数据结构。
×18. 平均查找长度与记录的查找概率有关。
19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。
×20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。
×二．选择题1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。
a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,12. 递归程序可借助于( b )转化为非递归程序。
数据结构试卷及答案一、选择题（共30题，每题2分，共60分）1. 数据结构是解决什么问题的基础？A. 数据的存储和组织问题B. 数据的计算和分析问题C. 数据的传输和交换问题D. 数据的加密和解密问题2. 下列哪种数据结构可以实现后进先出（LIFO）的特性？A. 栈B. 队列C. 链表D. 树3. 哪种数据结构可以快速地查找和插入元素？A. 数组B. 链表C. 栈D. 队列4. 在二叉树中，每个节点最多有几个子节点？A. 0B. 1C. 2D. 35. 下列哪种排序算法的时间复杂度是O(nlogn)？A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序...二、填空题（共10题，每题4分，共40分）1. 数据结构中，关系密切的元素组成的集合称为________。
2. 对一个链表进行插入或删除操作，时间复杂度是________。
3. 在树结构中，没有子节点的节点称为________。
4. 广度优先搜索（BFS）使用的数据结构是________。
5. 在堆排序中，堆的建立时间复杂度是________。
...三、简答题（共5题，每题10分，共50分）1. 请简要解释什么是数组，并说明其在数据结构中的优势和限制。
2. 请解释栈和队列这两种数据结构的特点和应用场景，并给出一个实际的例子。
3. 请解释什么是二叉树，给出一个二叉树的例子，并说明其遍历的方法。
4. 请简要解释图的概念，并说明图的遍历方法。
5. 请解释并比较快速排序和归并排序两种常用的排序算法，包括它们的时间复杂度和空间复杂度。
...答案解析：一、选择题答案：1. A2. A3. B4. C5. C二、填空题答案：1. 集合2. O(1)3. 叶节点4. 队列5. O(n)三、简答题答案：1. 数组是一种连续存储数据的结构，其优势是在已知索引的情况下能快速访问元素，但限制在插入和删除操作上效率较低。
2. 栈是一种后进先出（LIFO）的数据结构，适用于需要倒序处理的场景，如函数调用栈。
数据结构试卷试1一、解释下列术语（每小题4分，共20分）1. 头指针2. 二叉排序树的定义3. 头结点4. 数据的逻辑结构5. 排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素A.n-iB. n-i+1C. n-i-1D.i2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列A.1,2,3,4B.2,3,4,1C. 4,3,2,1D.3,4, 1,23. 对二叉排序进行( )遍历可以得到结点的排序序列A.前序B.中序C. 后序D.按层次4．有64个结点的完全二叉树的深度为（）。
A 8B 7C 6D 55．折半查找法的时间复杂度是( )A.(n2)B.O(n)C. O(n㏒n)D. O(㏒n)6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。
A 1140B 1145C 1120D 11257. 有n个叶子结点的哈夫曼树的结点总数为（）。
A 不确定B 2nC 2n+1D 2n-18. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（）。
A acbedB decabC deabcD cedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。
A (r-f+m)mod mB r-f+1C r-f-1D r-f10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。
A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子 D任一结点无右孩子三，判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。
数据结构试题及答案(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编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。
每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
成都理工大学《数据结构》重修考试试卷大题一二三四五总分得分一、选择题（20分）单项选择题，共19个小题，20个选项，每个选项1分。
1. 树型结构是指数据元素之间存在哪种关系。
（ ）A ）一对多关系B ）多对多关系C ）多对一关系D ）一对一关系2. 数据结构中算法分析的目的是（ ）。
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性3．数据结构的二元组表示S=（D,R ），D 表示数据元素，R 表示数据关系。
下面表示为树型结构的是（ ）。
A) D={d1,d2,d3,d4} R={<d1,d2>,<d2,d3>,<d3,d4> ,< d4,d1>}B) D={d1,d2,d3,d4} R={<d1,d2>,<d1,d3>,<d3,d4> }C) D={d1,d2,d3,d4} R={<d1,d2>,<d1,d3>,>d3,d2> }D) D={d1,d2,d3,d4}R={(d1,d2),(d1,d3),(d3,d4),(d4,d2) }4．已知C++语言中的字符型数组A[4][5],第一个元素A[0][0]的存储单元位置为100，元素A[3][3]的存储位置为（ ）A ）117B ）118C ）119D ）1205. 在n 个结点的单链表存储中，算法的时间复杂度是O （1）的操作是（ ）。
A ）访问第i 个结点（1≤i ≤n ）B ）在第i 个结点后插入一个新结点（1≤i ≤n）︵C）删除第1个结点D）在链表最后插入一个结点6. 判定一个队列QU（最多元素为m0）为空队列的条件是( )。
A) QU->rear－QU->front == m0 B) QU->rear －QU->front －1== m0 C) QU->front == QU->rear D) QU->front == QU->rear+17．队列中元素的进出原则是（）。
A) 先进先出B) 后进先出C) 空则进入D) 任意位置8．一个字符栈的入栈序列依此为ABDCE，则通过栈调度后不可能存在的输出序列有（）。
A) ABCDE B) EDCBAC) DBACE D) ACEDB9．串是一种特殊的线性表，其特殊性体现在（）。
A）可以顺序存储B）数据元素是一个字符C）可以链式存储D）数据元素可以是多个字符10. 有8个结点的无向连通图最少有（）条边。
A）5 B） 6 C）7 D）811．广度优先遍历类似于二叉树的（）。
A) 先序遍历B) 中序遍历C) 后序遍历D) 层次遍历12．对22个记录的有序表作折半查找，当查找成功时，至多需要比较次关键字。
（）A) 3 B) 4 C) 5 D) 613．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。
A) 希尔排序B) 归并排序C) 插入排序D) 选择排序14．堆的形状是一棵（）。
A) 二叉排序树B) 满二叉树C) 完全二叉树D) 平衡二叉树15．对有n个记录的表作简单交换排序，在最坏情况下，算法的时间复杂度是A) O(n) B) O(n2) C) O(nlog2n) D) O(n3)16．中序遍历二叉树，是指（）。
A) 先访问根结点，再依次访问左子树和右子树B) 先访问左子树，再访问根结点，然后访问右子树C) 先访问左子树，再访问右子树，然后访问根结点D) 先访问根结点，再依次访问右子树和左子树17．线性表指的是（）。
A) 一个有限数据元素序列，允许是空B) 一个有限数据元素序列，不能为空C) 一个无限数据元素序列，允许是空D) 一个无限数据元素序列，不能为空18. 设矩阵A是一个下三角矩阵，按行序存放在一维数组B[ 0, n(n-1)/2-1 ]中，对下三角部分中任一元素ai,j(i≥j), 在一维数组B中下标k的值是（）。
A) i(i-1)/2+j-1 B) i(i-1)/2+jC) i(i+1)/2+j-1 D) i(i+1)/2+j19. 树是结点的有限集合，它( ①)根结点，记为T。
其余的结点分成为m（m≥0）个( ②)的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
供选择的答案①：A)有0个或1个B) 有0个或多个C) 有且只有1个D) 有1个或1个以上②:A) 互不相交B) 允许相交C) 允许叶结点相交D) 允许树枝结点相交二、填空题（20分）共12个小题，20个空，每空1分。
1．数据结构按物理存储结构划分为、、和索引存储。
2．在树型结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以3．向一个长度为n的线性表中删除第i个元素(1≤i≤n)时，需向前移动个元素。
4．是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
5．子串的定位运算称为串的模式匹配；称为目标串，称为模式。
6．三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。
7．一棵深度为6的满二叉树有个分支结点和个叶子。
8．设一棵完全二叉树有70个结点，则共有个叶子结点。
9．N个结点的完全二叉树的深度为。
10．无向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。
11．n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。
12．在具有n 个单元的循环队列中，队满时共有 个元素。
三、判断题 （10分）共10个小题，每题1分，在括号里打√或×。
（ ）1. 链表的每个结点中都只包含一个指针。
（ ）2. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
（ ）3. 顺序存储方式的特点是存储密度大，且插入、删除运算效率底。
（ ）4. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ）5. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（ ）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（ ）7.二叉树中每个结点的两棵子树的高度差等于1。
（ ）8.二叉树中每个结点有两棵非空子树或有两棵空子树。
（ ）9. 具有24个结点的完全二叉树有12个度为2的结点。
（ ）10. 归并排序是简单选择排序的改进算法。
四、简答分析题（25分）共5个小题，每题5分。
1．画出下列树对应的二叉数。
(5分)2．如图所示二叉树，请写出其先序、中序和后序的遍历序列，然后再图上画出其中序遍历的线索二叉数示意图。
(5分)3．已知一个AOE 网，其中v0为源点，v8为汇点。
请求出汇点的最早发生时间，并画出关键路径。
（5分）4．已知如图所示的无向连通图，请画出该图邻接矩阵存储结果示意图。
（5分）12435．假设用于通信的电文仅由6个字母(A、B、C、D、E、F)组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03。
设计哈夫曼树。
五、算法设计题（25分）共4个小题，1、2、3小题各5分，4小题10分1．算法填空(共5个空，每空1分)二分查找排序，实现过程如下：bool Search(SStable S,KeyType key){ int L,H,M;L=1;H= ;while (L<=H){M=if ( S.elem[M]== )return ;else if ( S.elem[M]> )L=M+1;ElseH=M-1;}return false;}说明：线性表的结构定义如下：typedef struct {ElemTpye elem[MaxSize]; //存储元素int length; //线性表的长度}SStable;2．写出求二叉树深度的算法（5分）已知二叉树结点的结构声明如下：typedef struct node{ datatype data; //结点值struct node *lchild, *rchild; // 指针}BiTree;3．已知顺序存储n个元素，编写实现排序的算法，要求采用交换排序方式来实现。
（5分）typedef int keyType; //定义关键字类型为整数类型typedef struct {KeyType key; //关键字项infoType otherinfo; //其它项} RedType; //记录类型Typedef struct {RedType r[100];int length; //顺序表长度} SqlList; //顺序表类型其中数组的0号单元不存在数据。
4．编写一个算法实现算术表达式求值。
（10分）说明：涉及的堆栈的函数和判断C是否包含在OP运算符号中函数IN(c,oP)，判断运算符的优先级函数Precede(theta1,theta2)和计算结果函数Opertate(a,theta,b)直接使用。
