下载文档原格式
第1篇一、选择题1. 问题：在PHP中，以下哪个数据结构允许你以任意顺序存储元素？- A. 数组- B. 队列- C. 栈- D. 链表答案：A. 数组解析：在PHP中，数组是一种非常灵活的数据结构，它允许你以任意顺序存储元素。
每个元素可以通过一个键来访问，这个键可以是数字或者字符串。
2. 问题：以下哪个函数可以用来检查一个PHP数组是否为关联数组？- A. is_array()- B. array_keys()- C. is_associative()- D. array_is_associative()答案：D. array_is_associative()解析：PHP 7.1.0引入了`array_is_associative()`函数，该函数可以用来检查一个数组是否为关联数组。
如果是关联数组，返回`true`；如果是索引数组，返回`false`。
3. 问题：以下哪个PHP函数可以用来检查一个值是否在数组中？- A. in_array()- B. array_key_exists()- C. isset()- D. array_search()答案：A. in_array()解析：`in_array()`函数用来检查一个值是否存在于数组中。
它接受两个参数：要查找的值和要检查的数组。
二、填空题1. 问题：在PHP中，使用`[]`可以创建一个______数组。
- 答案：索引数组2. 问题：在PHP中，使用`array()`函数可以创建一个______数组。
- 答案：关联数组3. 问题：在PHP中，要遍历一个关联数组，可以使用______循环。
- 答案：foreach三、简答题1. 问题：解释PHP中的`isset()`和`empty()`函数的区别。
答案：- `isset()`函数用于检查一个变量是否已经设置并且不为`null`。
如果变量已设置且不为`null`，则`isset()`返回`true`。
数据结构与算法同步训练模拟试题及答案解析(1/43)选择题第1题下列叙述中正确的是()。
A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序的存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构下一题(2/43)选择题第2题算法的有穷性是指()。
A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用上一题下一题(3/43)选择题第3题算法的空间复杂度是指()。
A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数上一题下一题(4/43)选择题第4题定义无符号整数类为UInt，下面可以作为类UInt实例化值的是()。
A.-369B.369C.0.369D.整数集合{1,2,3,4,5}上一题下一题(5/43)选择题第5题下列叙述正确的是()。
A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对上一题下一题(6/43)选择题第6题下列叙述中正确的是()。
A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构上一题下一题(7/43)选择题第7题下列关于线性链表的叙述中，正确的是()。
A.各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续C.进行插入数据与删除数据时，不需要异动表中的元素D.以上说法均不对上一题下一题(8/43)选择题第8题下列叙述中正确的是()。
A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间上一题下一题(9/43)选择题第9题下列叙述中正确的是()。
课程：数据结构专业：计算机科学与技术、网络工程、软件工程参考答案及评分标准一、单项选择题(10小题，每小题1分，共10分)1．算法指的是____D_____。
A．数据处理B．计算机程序C．解决问题的计算方法D．对特定问题求解步骤的一种描述，是指令的有限序列2．已知已个AOV网如图所示，下列____C_____不是该图的拓扑序列。
A．v0 v1 v5 v2 v3 v6 v4 B．v0 v1 v5 v2 v6 v3 v4C．v0 v1 v5 v3 v2 v6 v4 D．v0 v1 v5 v6 v2 v3 v43．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是___B______。
A．2 B．3 C．4 D．64．如果结点A有3个兄弟，B是A的双亲，则结点B的度是______D______。
A．1 B．2 C．3 D．45．二叉树的前序序列和后序序列正好相反，则该二叉树一定是___B______的二叉树。
A．完全二叉树B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子6．在一个无向图中，所有顶点的度数之和等于所有边数的____B______倍。
A．1 B．2 C．3 D．47．判定有向图是否存在回路除了可以利用拓扑排序方法外，还可以用_____A______。
A．深度优先遍历算法B．广度优先遍历算法C．求关键路径方法D．求最短路径方法8．下述排序方法中，比较次数与待排序记录的初始状态无关的是____C_______。
A．插入排序和快速排序B．归并排序和快速排序C．选择排序和归并排序D．插入排序和归并排序9．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值____A_____。
A．不一定都是同义词B．一定都是同义词C．一定都不是同义词D．都相同10．下列序列中，_______ 是执行第一趟快速排序的结果。
2020年考研计算机数据结构模拟试题及答案(三)一、选择题(30分)1. 1. 字符串的长度是指( )。
(A) 串中不同字符的个数 (B) 串中不同字母的个数(C) 串中所含字符的个数 (D) 串中不同数字的个数2. 2. 建立一个长度为n的有序单链表的时间复杂度为( )(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)3. 3. 两个字符串相等的充要条件是( )。
(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等(C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对4. 4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下选择( )。
(A) 99 (B) 97 (C) 91 (D) 935. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为( )。
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)6. 6. 设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。
(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4](C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]7. 7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。
(A) 8 (B) 7 (C) 6 (D) 58. 8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有( )个度数为0的结点。
(A) 5 (B) 6 (C) 7 (D) 89. 9. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发实行深度优先遍历能够得到的一种顶点序列为( )。
试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。
A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n 个数据元素的有限非空集合。
B. 栈和队列都是操作受限的线性表。
C. 串（或字符串）是由零个或多个字符组成的有限序列。
D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。
4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。
A. Q.front=Q.rearB. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZED. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。
A. 3 B. 4 C. 5 D. 66. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。
A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j0,01,01,11,01,11,1...............n n n n a a a A a a a ----⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。
北京语言大学网络教育学院《数据结构》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。
请监考老师负责监督。
2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。
3.本试卷满分100分，答题时间为90分钟。
4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。
一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。
1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用（）存储方式最节省时间。
[A] 顺序表[B] 双链表[C]带头结点的双循环链表[D] 单循环链表2、队列操作的原则是（）。
[A] 只能进行删除[B] 后进先出[C]只能进行插入[D] 先进先出3、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
[A] 空或只有一个结点[B] 高度等于其结点数[C]任一结点无左孩子[D] 任一结点无右孩子4、在下列排序方法中，（）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。
[A] 插入排序[B] 希尔排序[C] 快速排序[D] 堆排序5、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左、右孩子中，其左孩子编号小于右孩子编号。
则可采用（）次序的遍历实现编号。
[A] 先序[B] 中序[C]后序[D] 从根开始的层次遍历6、若用数组S[n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[n]全满时才不能作入栈操作。
为这两个栈分配空间的最佳方案是（）。
[A] S1的栈底位置为0，S2的栈底位置为n[B] S1的栈底位置为－1，S2的栈底位置为n/2[C] S1的栈底位置为0，S2的栈底位置为n－1[D] S1的栈底位置为0，S2的栈底位置为n/27、对一棵二叉排序树进行（）遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。
第3章栈和队列一、填空题（每空1分，共15分）1。
向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
2。
栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。
不允许插入和删除运算的一端称为栈底。
3。
队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4。
在一个循环队列中，队首指针指向队首元素的前一个位置。
5。
在具有n个单元的循环队列中，队满时共有n-1 个元素.6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。
7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。
8。
〖00年统考题〗带表头结点的空循环双向链表的长度等于0。
解：二、判断正误(）（每小题1分，共10分）（×）1。
是一个复杂类型。
错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。
（×）2。
在表结构中最常用的是线性表,栈和队列不太常用。
错，不一定吧？调用子程序或函数常用，CPU中也用队列。
（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）4. 对于不同的使用者，一个表结构既可以是栈,也可以是队列，也可以是线性表.正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
( ×）5. 栈和链表是两种不同的数据结构。
错,栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念,二者不是同类项。
（×)6. 栈和队列是一种非线性数据结构。
错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。
（√）7。
栈和队列的存储方式既可是顺序方式，也可是链接方式。
（√)8。
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
第一章概论一、选择题1、研究数据结构就是研究（ D ）。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。
A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。
A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。
A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。
for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。
A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。
i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。
A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。
i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。
数据结构试卷（一）王彬一、单选题（每题2 分，共20分）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进制表示。
cA．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-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.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
数据结构试题及答案一、选择题（每题5分，共25分）1. 以下哪个数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 以下哪个操作的时间复杂度是O(1)？A. 在链表中插入一个元素B. 在数组中查找一个元素C. 在二叉搜索树中插入一个元素D. 在图中查找一个顶点的邻居答案：B3. 以下哪个数据结构是非线性结构？A. 栈B. 队列C. 数组D. 树答案：D4. 以下哪个操作不能在O(1)时间内完成？A. 删除链表的尾节点B. 删除数组的最后一个元素C. 删除二叉搜索树的最小值节点D. 删除图中任意两个顶点之间的边答案：D5. 以下哪个数据结构不具有后进先出（LIFO）的特点？A. 栈B. 队列C. 数组D. 链表答案：B二、填空题（每题5分，共25分）1. 在_________中，任何节点的两个子节点之间恰好有_________条边。
答案：树，02. 动态数组是_________数据结构，它可以在_________时间内改变其大小。
答案：线性，O(1)3. 栈和队列都是_________结构，它们都具有_________特点。
答案：线性，后进先出（LIFO）4. 哈希表是通过_________函数将键映射到_________上的数据结构。
答案：哈希，数组索引5. 在_________中，每个节点最多有_________个子节点。
答案：二叉树，2三、判断题（每题5分，共25分）1. 链表比数组更适合进行频繁的插入和删除操作。
（）2. 深度优先搜索（DFS）和广度优先搜索（BFS）都可以用来遍历图。
（）3. 堆是一种完全二叉树，且满足堆积的性质。
（）4. 哈希表的查找时间复杂度为O(1)。
（）5. 并查集是一种用于解决集合合并和查找问题的数据结构。
（）四、简答题（每题10分，共30分）1. 简述二分搜索树（BST）的特点及其性质。
答案：二分搜索树是一种有序的二叉树，它的特点是：对于任意节点，其左子树上的所有节点的值都小于该节点的值，其右子树上的所有节点的值都大于该节点的值。
《数据结构》模拟试题3一、单项选择题1．带头结点的单向链表为空的判断条件是（）（设头指针为head）。
A．head = =NULL B．head!=NULLC．head->next= =head D．head->next= =NULL2．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。
A．p->next = =NULL B．p= =NULL C．p= =head D．p->next= =head 3．算法的时间复杂度与（）有关。
A．所使用的计算机 B．计算机的操作系统C．算法本身 D．数据结构4．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。
A．n-i+1 B．n-i C．n-i-1 D．i5．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。
A．p=s→next B．p→next=s→next;C．s→next=p→next; p→next=s; D．p→next= s; s→next= p→next6．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。
A．r=f→next; B．r=r→next; C．f=f→next; D．f=r→next;7．元素1，3，5，7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．7，5，3，1 B．7，5，1，3C．3，1，7，5 D．1，3，5，78．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。
A．4 B．3 C．6 D．129．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。
A．2i B．2i-1 C．2i+1 D．2i+210．一棵具有35个结点的完全二叉树，最后一层有（）个结点。
A．4 B．6 C．16 D．811．在一个无向图中，所有顶点的度数之和等于边数的（）倍。
A．3 B．2 C．2.5 D．1.512．已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。
A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8图313．对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。
A．按层次 B．后序 C．中序 D．前序14．设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（）。
A．折半排序 B．冒泡排序 C．归并排序 D．简单选择排序15．一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。
A．39，47，46，80，41，57 B．39，41，46，80，47，57C．41，39，46，47，57，80 D．39，80，46，47，41，57二．填空题1．算法的5个特征为_________。
2．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。
则比较的次数和算法的时间复杂度分别为________和________ 。
3．在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s->next=p->next;和的操作。
4．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。
则可以用操作________。
5．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h; 和操作。
(结点的指针域为next)6．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r->next=s;和(结点的指针域为next)。
7.两个串相等的充分必要条件是_______ ___。
8．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_______、、。
9．一棵二叉树中有2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有_______个非叶结点。
10．如图1所示的二叉树，其中序遍历序列为________ _。
11．如图1所示的二叉树，其后序遍历序列为_________。
12．哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。
13．n 个元素进行冒泡法排序，通常需要进行________趟冒泡，第j 趟冒泡要进行______次元素间的比较。
三、综合题1．已知序列{11，19，5，4，7，13，2，10}（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。
（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。
2．设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素40需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ 3．（1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。
（2）设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据，构造一棵二叉排序树. 4．(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。
该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？(2)设有查找表{7，16，4，8，20，9，6，18，5}，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果. 5．（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。
（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。
四、程序填空题1．以下是用尾插法建立带头结点且有n 个结点的单向链表的程序，结点中的数据域从前向图1 图2后依次为1,2,3,……,n，完成程序中空格部分。
NODE *create(n){NODE *head , *p, *q;int i;p=(NODE*)malloc(sizeof(NODE));head= ①; ②;p→next=NULL; /*建立头结点*/for(i=1; i<=n; i++){ p= ③;p->data=i;p->next=NULL;q->next= ④;⑤;}return(head);}2．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。
#define NULL 0void main( ){NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾结点*/head= ①;a.next=&b;b.next=&c;c.next=&d;②; /*以上结束建表过程*/p=head; /*p为工作指针，准备输出链表*/do{printf(“%d\n”, ③);④;}while( ⑤);}3．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT){ if(BT!=NULL){①;②;③;}}4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT){if(BT!=NULL){（1）;（2）;Inorder(BT->right);}}利用上述程序对右图进行遍历，结果是 ;综合练习题答案一、单项选择题1．D 2．D 3．C 4．B 5．C 6．C 7．B 8．A 9．A 10．A 11．B 12．A 13．C 14．D 15．B二、填空题1．有穷性、确定性、可行性、零个或多个输入、一个或多个输入2．n-1,O(n)3．s->next=p->next;4．q->next=p->next;5．s->next=h;6．r->next=s;7．串长度相等且对应位置的字符相等8．值域、左指针、右指针9．n-110．dgbaechif11．gdbeihfca12．存储地址13．n-1,n-j三、综合题1．(1) 初始11，19，5，4，7，13，2，10第一趟[ 11，19][4，5][7，13][2，10]第二趟[4，5，11，19][2，7，10，，13]第三趟[2，4，5，7，11，10，11，13](2)2． (1)(2)4次(3)ASL=(1+2*2+3*4+4*4)/11=33．(1)不正确，例 (2)4．(1)不正确，二叉排序树要求其子树也是二叉排序树。
(2)后续遍历 5，6，4，9，8，18，20，16，75．（1）wpl1=45（2）wpl2=45四、程序填空题 1． ①p②q=p③(NODE*)malloc(sizeof(NODE)) ④p ⑤q=p2． ①&a②d →next= =NULL ③p →data ④p =p →next ⑤p!=NULL3． ① Inorder(BT->left);② printf(“%c ”,BT->data);③ Inorder(BT->right);4．① Inorder(BT->left);② printf(“%c”,BT->data);③dbeafc。
