数据结构复习6
一、选择题
4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子
数为（）
A．5 B．6 C．7 D．8
5. 在下述结论中，正确的是（）
①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意
交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F
中第一棵树的结点个数是（）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)
的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T
的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个
不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定
义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T
中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│
λKi-λKj│≤1一定成立时，则称T为一棵（(5)）。供选择的答案：
（1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1
个以上
（2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交
（3） A. 权 B.维数 C.次数 D.序
（5） A. 丰满树 B.查找树 C.平衡树 D.完全树
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定
9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个
A．4 B．5 C．6 D．7
10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林
F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3 D．M2+M3
11．具有10个叶结点的二叉树中有（）个度为2的结点，
A．8 B．9 C．10 D．ll
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A． 250 B． 500 C．254 D．505 E．以上答案都不对
13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A．不确定 B．2n C．2n+1 D．2n-1
14. 有n个叶子的哈夫曼树的结点总数为（）。
A．不确定 B．2n C．2n+1 D．2n-1
15．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。
A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)?D．?n/(m-1)?-1 E．?(n+1)/(m+1)?-1
16. 有关二叉树下列说法正确的是（）
A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
17．二叉树的第I层上最多含有结点数为（）
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
18. 一个具有1025个结点的二叉树的高h为（）
A．11 B．10 C．11至1025之间 D．10至1024之间
19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1
20．对于有n 个结点的二叉树, 其高度为（）
A．nlog2n B．log2n C．?log2n?|+1 D．不确定
21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（）
A．?logn?+1 B．logn+1 C．?logn? D．logn-1
22．深度为h的满m叉树的第k层有（）个结点。(1= A．m k-1 B．m k-1 C．m h-1 D．m h-1 23．在一棵高度为k的满二叉树中，结点总数为（） A．2k-1 B．2k C．2k-1 D．?log2k?+1 24．高度为 K的二叉树最大的结点数为（）。 A．2k B．2k-1 C．2k -1 D．2k-1-1 25. 一棵树高为K的完全二叉树至少有（）个结点 A．2k–1 B. 2k-1–1 C. 2k-1 D. 2k 26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A．4 B．5 C．6 D．7 27. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号， 同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实 现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 29．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 30．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( ) 遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 31．在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 32．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（） A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果 为（）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是 （）。 A．acbed B．decab C．deabc D．cedba ： A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对 36. 上题的二叉树对应的森林包括多少棵树（） A．l B．2 C．3 D．概念上是错误的 37．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 38．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的A．前序遍历 B．中序遍历 C．后序遍历（） 39. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的 结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 40．下面的说法中正确的是（）. （1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)(2) B．(1) C．(2) D．(1)、(2)都错 41．对于前序遍历与中序遍历结果相同的二叉树为（1）; 对于前序遍历和后序遍历结果相同的二叉树为（2）。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树 42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树 43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 44．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 45．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 46．在下列情况中，可称为二叉树的是（） A．每个结点至多有两棵子树的树 B. 哈夫曼树 C．每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E．以上答案都不对 47. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( ) A．不确定 B. 0 C. 1 D. 2 48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定 49. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最 右叶结点 50. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 51. 线索二叉树是一种（）结构。 A．逻辑 B．逻辑和存储 C．物理 D．线性 52．n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n 55. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针 域为空的结点有（）个。 A． n-1 B．n C． n+1 D． n+2 56．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。 A．先序 B．中序 C．后序 D．层次序 57. 由3 个结点可以构造出多少种不同的有向树？（） A．2 B．3 C．4 D．5 58．由3 个结点可以构造出多少种不同的二叉树？（） A．2 B．3 C．4 D．5 59.下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关 键字有序（）。 A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆 60．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（）。 A．正确 B．错误 61．最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度最小的树，其中对最优二 叉树，n表示（1），对最优查找树，n表示（2），构造这两种树均（3）。 A．结点数 B．叶结点数 C．非叶结点数 D．度为2的结点数 E．需要一张n个关 键字的有序表 F．需要对n个关键字进行动态插入 G．需要n个关键字的查找概率表 H．不需要 任何前提 62．下述编码中哪一个不是前缀码（）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01， 000，001） 63．下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 64. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（） A．A[2i](2i= 法确定 65. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的 位置是（） A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 66．从下列有关树的叙述中,选出5条正确的叙述(共5分) （） A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B．当K≥1时高度为K的二叉树至多有2k-1个结点。 C．用树的前序周游和中序周游可以导出树的后序周游。 D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。 F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G．在二叉树中插入结点,该二叉树便不再是二叉树。 H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。 I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J．用一维数组存储二叉树时,总是以前序周游存储结点。 二、判断题 1. 二叉树是度为2的有序树。 2. 完全二叉树一定存在度为1的结点。 3. 对于有N个结点的二叉树，其高度为log2n。 4．深度为K的二叉树中结点总数≤2k-1。 5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。 6. 二叉树的遍历结果不是唯一的. 7. 二叉树的遍历只是为了在应用中找到一种线性次序。 8. 树可用投影法进行中序遍历。 9. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。 10. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一 个，则可以确定这棵二叉树。 11. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序 遍历是一致的。 12．对一棵二叉树进行层次遍历时，应借助于一个栈。 13．用树的前序遍历和中序遍历可以导出树的后序遍历。 14．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。 15. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。 16．中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使 用堆栈。 17．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 21．由一棵二叉树的前序序列和后序序列可以唯一确定它。 22．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 23. 二叉树只能用二叉链表表示。 24. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i 的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1 25. 给定一棵树，可以找到唯一的一棵二叉树与之对应。【青岛大学 2001 一、5 （1分）】 26. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。 27. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空 指针。 28. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊 情形. 29．树形结构中元素之间存在一个对多个的关系。【燕山大学 1998 二、1 （2分）】 30．在二叉树的第i层上至少有2i-1个结点(i>=1)。 31．必须把一般树转换成二叉树后才能进行存储。 32．完全二叉树的存储结构通常采用顺序存储结构。 33．将一棵树转成二叉树，根结点没有左子树； 34．在二叉树中插入结点，则此二叉树便不再是二叉树了。 35．二叉树是一般树的特殊情形。 36．树与二叉树是两种不同的树型结构。 37. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 38．在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。 39．度为二的树就是二叉树。 40．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为?2k-2?+1。 41.下面二叉树的定义只有一个是正确的，请在正确的地方画“√”。 （1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。 （2）（a）在一株二叉树的级i上，最大结点数是2i-1（i≥1） （b）在一棵深度为k的二叉树中，最大结点数是2k-1+1（k≥1）。 （3）二叉树是结点的集合，满足如下条件： （a）它或者是空集； （b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。45．霍夫曼树的结点个数不能是偶数。 46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。 47. 哈夫曼树无左右子树之分。 48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。 49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1 个空指针。( ) 三、填空题 1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。 3．在二叉树中，指针p所指结点为叶子结点的条件是______。 5．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的____。 6．具有256个结点的完全二叉树的深度为______。 7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 8．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。 9．深度为H 的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；H和结点总数N之间的关系是 (3)__。 10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。11．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。 12．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支（非终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。 14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______ 15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。 16．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为______。 17．高度为K的完全二叉树至少有______个叶子结点。 18．高度为8的完全二叉树至少有______个叶子结点。 19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 20．一个有2001个结点的完全二叉树的高度为______。 21．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。22．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。 23．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 24．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。 25．高度为h的2-3树中叶子结点的数目至多为______ 26．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。 27．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。28．对于一个具有n个结点的二元树，当它为一棵_(1)_二元树时具有最小高度，当它为一棵_(2)_时，具有最大高度。 29．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 30．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。31．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。 33． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。【 34．每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是_(1)__。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)__。 35．先根次序周游树林正好等同于按_(1)__周游对应的二叉树，后根次序周游树林正好等同于按__(2)_周游对应的二叉树。 36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)__,则该二叉树对应的树林包括_(2)__棵树。 37．二叉树的先序序列和中序序列相同的条件是______。 38．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__，右子树中有_(3)__。 39．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为_(1)__;后序遍历二叉树时，访问的结点序列为_(2)__。 40．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。【青岛大学2000 六、3(2分）】 41．现有按中序遍历二叉树的结果为abc，问有_(1)__种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)__。 42．一个无序序列可以通过构造一棵______树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 43．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。 44．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。 45．先根次序周游树林正好等同于按______周游对应的二叉树；后根次序周游树林正好等同于______周游对应的二叉树。 46. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。 47．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。 48．具有n个结点的满二叉树，其叶结点的个数是______。 49．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过______中间结点（不含后继及x 本身） 52．哈夫曼树是______。 53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。54．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。 55．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。 56．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。 四、应用题 1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 2．树和二叉树之间有什么样的区别与联系？ 3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。 6. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 7. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 8．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？ 4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。 9．证明任一结点个数为n 的二叉树的高度至少为O(logn). 10．有n个结点并且其高度为n的二叉树的数目是多少? 11．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 12．高度为10的二叉树，其结点最多可能为多少？ 13．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。 14. 已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？ 15．给定K(K>=1),对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度。 16．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 17．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 18．如在内存中存放一个完全二叉树，在树上只进行下面两个操作： （1）寻找某个结点双亲（2）寻找某个结点的儿子； 请问应该用何种结构来存储该二叉树？ 19．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。 20．设二叉树T中有n个顶点，其编号为1，2，3，…,n,若编号满足如下性质： （1）T中任一顶点v的编号等于左子树中最小编号减1； （2）对T中任一顶点v,其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。 21．若一棵树中有度数为1至m的各种结点数为n1,n2,…,n m(n m表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。 22．若一棵完全二叉树中叶子结点的个数为n,且最底层结点数≧2，则此二叉树的深度H=？ 23．已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？ 24．在一棵表示有序集S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合Sl；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈Sl,b∈S2，c∈S3是否总有a≤b≤c?为什么? 25．试证明,在具有n(n>=1)个结点的m次树中,有n(m-1)+1个指针是空的。 26．对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式n0=f(n2).要求给出推导过程。 27．对于任意一棵非空的二叉树T，我们用n0表示T中叶子结点的个数，用n2表示T 中有两棵非空子树的结点的个数。（1）给出n0和n2所满足的关系式。（2）证明你在（1）中给出的关系式成立。 28．试求有n个叶结点的非满的完全二叉树的高度 30．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？ 31．一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标的u的结点的第i 个孩子的下标以及结点下标为v的结点的父母结点的下标。 32．二叉树有n个顶点，编号为1，2，3，…，n，设： * T中任一顶点V的编号等于左子树中最小编号减1； * T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加1； 试描绘该二叉树。 33．设T 是具有n 个内结点的扩充二叉树，I 是它的内路径长度，E 是它的外路径长度。 （1）试利用归纳法证明E=I+2n, n>=0.（5分) （2）利用（1）的结果试说明：成功查找的平均比较次数s 与不成功查找的平均比较次 数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1。 34．一棵非空的有向树中恰有一个顶点入度为0, 其它顶点入度为1,但一个恰有一个 顶点入度为0,其它顶点入度为1的有向图却不一定是一棵有向树,请举例说明。 36．证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个 数+1 37. 对于一个堆栈，若其入栈序列为1，2，3，…，n ，不同的出入栈操作将产生不同的 出栈序列。其出栈序列的个数正好等于结点个数为n 的二叉树的个数，且与不同形态的二叉 树一一对应。请简要叙述一种从堆栈输入（固定为1，2，3……n ）/输出序列对应一种二叉 树形态的方法，并以入栈序列1，2，3（即n=3）为例加以说明。 38. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能， 请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否 构造出此二叉树?若能，请证明之。若不能，请给出反例。 39．试证明:同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中 都按相同的相对位置出现（即先后顺序相同），例如前序abc,后序bca 对称序bac 。 40. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是 否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC 和后序序列DEBGFCA 构造二叉树。 41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树 的前序序列为ABDGECFH ，中序序列为：DGBEAFHC 。试画出该二叉树。 42．试证明：仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这 棵二叉树。 43. ① 试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 ② 已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG 和DEBHIFGCA ，画出 这棵二叉树。 44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） 45. 阅读下列说明和流程图，回答问题（1说明：流程图是用来实现中序遍历，二叉树存放在数组tree 中，每个数组元素存放树中 一个结点，每个结点的形式为（值，左指针，右指针），分别用tree[i].v ，tree[i].l ， tree[i].r 来表示第i 个结点的值，左指针，右指针，其中左，右指针的值为所指结点在数 组中的下标，若指针的值为0，表示它指向空树，图中指针root 用以指向二叉树的根结点。 问题： （1）填充流程图中的①、②、③，使其按中序遍历二叉树。 （2）把流程图中的（A ）框移至哪个位置（图中Ⅰ～Ⅸ）使流程图的算法从中序遍历变成 后序遍历。 46．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 47．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1)给出这棵二叉树： (2)转换为对应的森林： (3)画出该森林的带右链的先根次序表示法： (4) 画出该森林带度数的后根次序表示法： (5) (在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）48．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI： （1）试画出该二叉树； （2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。 （3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。 （4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。 （5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。 49. 假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC吗? 50．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 51．已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。 53. 已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 54．画出同时满足下列两条件的两棵不同的二叉树。 (1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。 55．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 56．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列：_ _ C D E _ G H I _ K 中序序列：C B _ _ F A _ J K I G 后序序列：_ E F D B _ J I H _ A 57．M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？ 58．证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。 59. 下表中M﹑N分别是一棵二叉树中的两个结点，表中行号i=1，2，3，4分别表示四种M ﹑N的相对关系，列号j=1，2，3分别表示在前序、中序、后序遍历中M,N之间的先后次 序关系。要求在i，j所表示的关系能够发生的方格内打上对号。例如：如果你认为n是m 写出后序遍历该二叉树时访问结点的顺序。 61．设树形T在后根次序下的结点排列和各结点相应的次数如下： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次数：００００３０００２０２４ 请画出Ｔ的树形结构图。 62．已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指 针，是否可不用递归且不用栈来完成？请简述原因。 63．对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和后序中哪两 个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确 性。 64．设二叉树的存储结构如下(每题5分,共15分) LINK 0 0 2 3 7 5 8 0 10 1 INFO J H F D B A C E G I RLINK 0 0 0 9 4 0 0 0 0 0 其中,T为树根结点的指针,LLINK、RLINK分别指向结点的左右子女,INFO为其数据域,请完成下列各题: （1）画出二叉树T的逻辑结构. （2）写出按前序、中序和后序周游二叉树T得到的结点序列. （3）画出二叉树T的后序线索树。 65．在二叉树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留 的参数有什么作用？如何清除最后这个递归语句？ 66．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？ 【山东大学 1999 六、１(２分）】 67．按下面要求解下图中二叉树的有关问题： (1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林； (3)用后根序遍历该森林，；写出遍历后的结点序列。 68．对下图所示二叉树分别按前序﹑中序﹑后序遍历，Array给出相应的结点序列，同时给二叉树加上中序线索。 第67题图 69. 假设一个二叉树的两种遍历如下： 前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA （1）画出这棵二叉树以及它的中序线索树； （2）写出在中序线索树的情况下，找到结点N 70．已知一棵二叉树的中序（或中根）遍历结点排列为 点排列为GDBEIHFCA， （1）试画出该二叉树； （2）试画出该二叉树的中序穿线（或线索）树； （3）试画出该二叉树（自然）对应的森林； 71．设二叉树BT的存储结构如下: 1 2 3 4 5 6 7 8 9 10 其中,data 为结点的数据域。试完成下列各题: （l）画出二叉树BT的逻辑结构; （2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。 72．请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。 73．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 74．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。 75．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？ 77. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。78．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 79．给定集合{15,3,14,2,6,9,16,17} (1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树： (2) (2分)计算它的带权路径长度： (3)（3分)写出它的huffman编码： (4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。 （5）设用于通信的电文由8个字母组成, 字母在电文中出现的频率分别为:7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码.使用0-7的二进制表示形式是另一种编码方案,试比较这两种方案的优缺点。【南京航空航天大学 1999 四、 (10分)】（6）假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。【燕山大学 1999 五、 (5分)】 （7）假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04}, 1) 为这7个字母设计哈夫曼编码； 2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码 使电文总长压缩多少？【北京邮电大学 2001 四、2 （5分)】 （8）试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。【北方交通大学 1993年五（12分)】 （9）带权结点为{5,6,7,8,9}，构造Huffman树，计算带权路径长度。] （10）以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，并计算其带权路径长度。 （11）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3，21,10。试为这8个字母设计哈夫曼编码。使用0∽7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 （12）设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。 (13) 给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。 (14) 以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。 80．给定权W1,W2,…，Wm 。说明怎样来构造一个具有最小的加权路径长度的k叉树。试对于权1,4,9,16,25, 36,49,64,81,100来构造最优的三叉树，并给出其最小加权路径长度。 五、算法设计题 数据结构试卷（一） 三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试 写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到 的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的 变化。 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的 返回值所表示的线性表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< 全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template 数据模型所描述的内容包括三个部分：数据结构、数据操作、数据约束。 1）数据结构:数据模型中的数据结构主要描述数据的类型、内容、性质以及数据间的联系等。数据结构是数据模型的基础，数据操作和约束都建立在数据结构上。不同的数据结构具有不同的操作和约束。 2）数据操作:数据模型中数据操作主要描述在相应的数据结构上的操作类型和操作方式。 3）数据约束：数据模型中的数据约束主要描述数据结构内数据间的语法、词义联系、他们之间的制约和依存关系，以及数据动态变化的规则，以保证数据的正确、有效和相容。 数据模型按不同的应用层次分成三种类型：分别是概念数据模型、逻辑数据模型、物理数据模型。 1、概念数据模型（Conceptual Data Model）：简称概念模型，主要用来描述世界的概念化结构，它使数据库的设计人员在设计的初始阶段，摆脱计算机系统及DBMS的具体技术问题，集中精力分析数据以及数据之间的联系等，与具体的数据管理系统（Database Management System，简称DBMS）无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。 概念数据模型是最终用户对数据存储的看法，反映了最终用户综合性的信息需求，它以数据类的方式描述企业级的数据需求，数据类代表了在业务环境中自然聚集成的几个主要类别数据。 概念数据模型的内容包括重要的实体及实体之间的关系。在概念数据模型中不包括实体的属性，也不用定义实体的主键。这是概念数据模型和逻辑数据模型的主要区别。 概念数据模型的目标是统一业务概念，作为业务人员和技术人员之间沟通的桥梁，确定不同实体之间的最高层次的关系。 在有些数据模型的设计过程中，概念数据模型是和逻辑数据模型合在一起进行设计的。 2、逻辑数据模型（Logical Data Model）:简称数据模型，这是用户从数据库所看到的模型，是具体的DBMS所支持的数据模型，如网状数据模型(Network Data Model)、层次 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A ) 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈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. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 11. 队列是一种（ B ）的线性表。 A．先进后出B．先进先出 C．只能插入D．只能删除 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系 时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表 达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 1. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 （1） （2） 数据结构试卷（一） 三、计算题（每题 6 分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?? ???????01 1 1 1010111011101010111 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集 V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,东南大学十套数据结构试题及答案
全国自学考试数据结构导论试题及答案(4套)
数据结构实验报告
数据结构(C语言版)期末复习
自考数据结构导论复习资料
数据结构实验十一：图实验
数据结构期末复习总结超详细1
数据模型所描述的内容包括三个部分
数据结构实验---图的储存与遍历
自考数据结构导论
数据结构实验报告图实验
数据结构复习资料
清华大学数据结构试题及答案
2010年1月自考数据结构导论真题
数据结构实验
武汉大学数据结构考试题(附答案)
自考02142《数据结构导论》串讲笔记
数据结构期末考试复习总结