数据结构综合练习及参考答案

1、1数据结构（数据结构（0111101111、0121101211）作业题（一）作业题（一）一、判断题一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题 1 分，共 10 分）1、 （）2、 （）3、 （）4、 （）5、 （）6、 （）7、 （）8、 （）9、 （）10、 （）（ ）1. 数据的存贮结构是数据的逻辑结构的存贮映象。（ ）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。（ ）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。（ ）4. 树的最大特点是层次结构。（ ）5. 队列的特点是先进先出。（ ）6. 图的最

2、小生成树是唯一的。（ ）7. 线性表是广义表的特殊形式。（ ）8. 后序序列和中序序列能唯一确定一棵二叉树。（ ）9. 散列表是一种链式存贮结构。（ ）10. 快速排序并非在任何情况下都比其它排序方法速度快。二、填空题二、填空题（每空 2 分，共 20 分）1 数据的存贮结构的四种形式为存贮、存贮、存贮和存贮。2所有插入和删除都在表的一端进行的线性表称为。3n 个结点的完全二叉树，其深度 h=。4对于顺序循环队列 QM，下标从 0 到 M-1，头尾指针分别为 F 和 R，入队时，队尾指针循环加 1 可表示为 R=。5散列法既是一种查找方法，又是一种方法。6n 个顶点的有向完全图具有条弧。7n

3、个元素的顺序查找的平均查找长度为。三、单选题三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）。1若进栈序列为 1，2，3，4，则不可能得到的出栈序列是（）（1）3,2,1,4（2）3,2,4,1 （3）4,2,3,1（4） 2,3,4,12对于下列二叉树，其后序序列为（）（1）ABDECFG（2）DBEAFCG（3）DEBFGCA（4）GFCEBDA3对于下列 AOV 网，不能出现的拓扑序列为（）（1）1 2 3 4 5（2）1 2 4 3 5（3）2 4 1 3 5（4）2 1 4 3 52 A B C

4、 D E F G 题 三 2 图 1 3 5 4 2 题三、3 图 4深度为 k 的完全二叉树所含叶结点的个数最多为（）（1）2k（2） 2k-1（3） k（4） 2k5衡量查找算法效率的主要标准是（）（1） 元素个数（2） 所需的存贮量（3） 平均查找长度（4） 算法难易程度四、应用题四、应用题（25 分）1将下列森林转化为二叉树。 （3 分）G F A B D E C 2对下图：（1）写出其邻接矩阵。 （2 分）（2）按 Kruskal 算法求其最小生成树；并写出相应的边集数组。 （4 分）3 V3 V6 3 V1 V4 5 V2 V5 10 12 6 11 8 3请画出后序和中序序列相同

5、的二叉树的所有形态。 （3 分）4散列函数为 H（k）=k%7，散列表的地址从 0 到 6，用线性探查法解决冲突，建立散列表 ht。给定关键字序列32，13，49，55，22，38，21要求： （1）构造散列表（只画出表，不写算法） ； （5 分）（2）求出平均查找长度。 （2 分）5用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。 （6分）68452090151050五、算法设计五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。每空3 分，共 30 分）1 1在带头结点的在带头结点的 headhead 单链表的结点单链表的结点 a a 之后插入新元素之后插入新元

6、素 x xstruct node elemtype data;node*next;4;void lkinsert (node *head, elemtype x) node*s,*p;s=new node; ;s-data=x; ;p=head-next;while (p!=NULL) &( p-data!=a )_p=p-next_; ;if (p=NULL)coutnext=p-next_; ;_p-next=s_; ;2 2快速排序快速排序voidqksort (int R , int p, int q)/ 按递增序对 RpRq 进行快速排序int i=p, j=q;R 0 =R

7、 i ;/R0作临时单元while ( _ii )&( R j _R 0 )j- -;if (ji) R i =R j ;i+;while (ij )& (R i _R 0 )i+;if (ip) qksort(R,p,j);if (iq)qksort(R,i,q);5数据结构（数据结构（0111101111、0121101211）作业题（二）作业题（二）一、判断题判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每小题 1 分，共 10 分）（）1. 数据的存贮结构独立于计算机。（）2. 线性表简称为“顺序表” 。（）3. 对数据的任何运算都不能改变数据原有的结构

8、特性。（）4. 从循环单链表的任一结点出发，可以找到表中所有结点。（）5. 栈是一种先进先出的线性表。（ ）6. 链表的主要缺点是不能随机访问。（）7. 二叉树是树的特殊形式。（ ）8. 图可以没有边，但不能没有顶点。（ ）9. 冒泡排序算法是稳定的排序。（）10. 散列法是一种对关键字进行比较的查找方法。二、填空题填空题（每空 2 分，共 20 分）1、 引 用、加工2、 队列、队尾3、 n0=n2+14、 F=R5、 n*(n-1) / 26、 AOV 网7、8、 插入1对数据所施加的运算可分为两类，即型和型。2将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为； 允许插入的一端

9、称为。3二叉树的叶结点数 n0与二度结点数 n2 的关系是。4对于顺序循环队列 QM，下标从 0 到 M1，头尾指针分别用 F 和 R 表示，则队空条件是。5n 个顶点的无向完全图具有条边。6拓扑排序的操作对象是。7 快速 排 序的最坏情况是初始序列为正序和反序，其时间复杂度为。8希尔排序是属于排序的改进方法。三、单选题三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1、 （2）2、 （3）3、 （4）4、 （3）5、 （1）1栈和队列都是（ ）（1）顺序存贮的线性结构（2）限制存取点的线性结构（3）链接

10、存贮的线性结构（4）限制存取点的非线性结构62与线性表的链接存贮不相符合的特性是（ ）（1）便于插、删运算（2）存贮空间动态分配（3）需要连续的存贮空间（4）只能顺序查找3设二叉树的根为第一层，则第 i 层上的结点数最多有（）（1）i（2） i+1（3）i-（4）i-14直接选择排序的时间复杂度为（）（1）O（n）（2）O(n 2n)（3）O(n2)（4）O(2n)5给定下列有向图，从顶点 V1 出发，其深度优先搜索序列为（）（1）12534（2）12435（3） 14325（4）12345 1 5 4 3 2 四、应用题四、应用题（25 分）1画出下列二叉树所对应的森林。 （3 分）B D

11、E G H C F I A 2对于下边有向图（1）画出其邻接表（4 分）（2）写出三种不同的拓扑序列（3 分）7 1 5 3 4 2 3请画出先序与中序序列相同的二叉树的所有形态。 （3 分）4给定关键字序列19，14，27，68，84，23，1，20，55，12，10，79，散列函数为 HK=K% 11 散列表的地址从 0 到 10，用外链法处理冲突，散列地址为 d 的同义词均挂在以 htd为头指针的单链表中。（1）请画出其散列表（不写算法） ； （5 分）（2）求出成功的平均查找长度。 （2 分）5对下列关键字序列进行快速排序，请写出第一趟排序结果，并标识出在第一趟排序过程中数据交换的情况

12、。 （5 分）359215191080100第一趟排序结果：五、算法设计五、算法设计（在下列算法的横线内填上适当的语句或表达式。每空3分，共30分）1 1 直接插入排序直接插入排序、void insertsort(intR )/ 按递增序对 R1 R n 进行直接插入排序 inti, j;for ( i=2;i =n;i+ ) R 0 =R i ;/ 设定 R0为监视哨j=i 1；while (R 0 R j )8Rj+1=Rj;j- - ;R j+1 =R0;/ 插入第 i 个记录2先序遍历二叉树设二叉树用二叉链表表示，以 t 为根指针，二叉链表结点的类型为 node；栈 s的元素类型为指向

13、 node 的指针类型, 栈容量 M 足够大。 先序遍历的非递归算法如下：struct nodechardata;node*lc,44*rc;void preorder (node*t) node*s M ，*p=_ ;int top=- 1；/置栈空;do while (p!=NULL);s+top =;if (top!= -)p=stop- -； while ( top! = - 1 ) | ( p ! =NULL );9数据结构（数据结构（0111101111、0121101211）作业题（三）作业题（三）一、判断题判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题 1

14、分，共 10 分）1、 （）2、 （）3、 （）4、 （）5、 （）6、 （）7、 （）8、 （）9、 （）10、 （）（ ）1. 数据是计算机加工处理的对象。（ ）2. 数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。（ ）3. 线性表是由 n0 个相同类型元素组成的有限序列。（ ）4. 栈是一种后进先出的线性表。（ ）5. 从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。（ ）6. 单链表设置头结点的目的是为了简化运算。10（ ）7. 深度为 h 的二叉树最多有 2h-1 个结点。（ ）8. 图 G 由两个集合 V（G）和 E（G）所组

15、成，其中顶点集 V（G）可以为空集，而边集 E(G)不能为空。（ ）9. 散列法是一种对关键字进行运算的查找方法和存储方法。（ ）10. 快速排序在任何情况下，都是速度最快的一种排序方法。二、填空题填空题（每空 2 分，共 20 分）1、结构2、线性、非线性3、顺序表4、队列5、h6、有序表7、排序8、值关系1数据元素之间存在的相互关系称为。2数据结构从逻辑上分为结构和结构。3线性表的顺序存储结构称为。4所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为。5深度为 h 的二叉树，最少有个结点。6折半查找要求待查表为表。7n 个记录按其关键字大小递增或递减的次序排列起来的过程称为8存

16、储数据的时侯，不仅要存储数据元素的，还要存储元素之间的相互。三、选择题三、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1与线性表的链接存储相符的特性是（）（1）插入和删除操作灵活（2）需要连续存储空间（3）便于随机访问（4）存储密度大2若进队序列为 1，2，3，4，则出队序列是（）（1）4，3，2，1（2）1，2，3，4（3）1，3，2，4（4） 3，2，4，13已知广义表 A=（ （a,b）,(c,d)）,则 head(A)等于（）（1） （a,b）（2）(a,b)（3）a,b（4）a4n 个结点的二叉

17、树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为（）（1）n（2）2n（3）n-1（4）n+156 个顶点的连通图的深度优先生成树，其边数为（）（1）6（2）5（3） 7（4）411四、应用题四、应用题（共 25 分）1已知二叉树的中序序列为 DBHEIAFJCKG，先序序列为 ABDEHICFJGK，请画出该二叉树。 （4 分）2对于给定的 5 个实数 W=8，5，13，2，6，试构造 Huffman 树；并求出该树的最小带权路径长度。 （7 分）3对于下边的图 G（1）画出其邻接表（4 分） 。（2）写出从 V1出发的深度优先搜索序列（3 分） 。 V1 V3 V2 V5 V4 4

18、给定有序表 D=15，17，18，22，35，51，60，88，93，用折半查找法在 D中查找 18。现要求：（1）试用图示法表示查找过程； （4 分）（2）求出其成功的平均查找长度 ASL。 （3 分）12五、算法设计五、算法设计（在下列算法的横线内填上适当的语句或表达式。 每空 3 分，共 30 分）1 1直接选择排序直接选择排序五、算法设计1. n-2、i+1、k!=i、Rkvoidselectsort (int R )/ 按递增序对 R 0 Rn-1 进行直接选择排序 int i, j, k, temp ;for (i=0;i=; i+) k=i ;for (j=;jlc、 coutd

19、ata、 p=p-rc 、 top!=-1struct nodechardata;node*lc,*rc;void preorder (node*t) node*sm ，*p=t ;int top =- 1；/置栈空do13 while (p!=NULL)s+top =;if (top!= -)p=stop- -； while () | ( p ! =NULL );数据结构（数据结构（0111101111、0121101211）作业题（四）作业题（四）一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题 1 分，共 10 分）1、 （）2、 （）3、 （）4、 （）5、 （）

20、6、 （）7、 （）8、 （）9、 （）10、 （）（ ）1. 数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。（）2. 算法是对解题方法和步骤的描述。（）3. 线性表简称为“顺序表” 。（）4. 队列是一种先进后出的线性表。（）5. 从循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前趋结点。（ ）6. 单链表设置头结点的目的是为了把空表与非空表、第一个结点处与非第一个结点处的运算统一起来。（）7. 深度为 h 的二叉树最多有 2h-1 个结点。（ ）8. 图 G 由两个集合 V（G）和 E（G）所组成，其中顶点集 V（G）和边集E(G

21、)都可以为空集。（）9. 散列法既是一种查找方法，又是一种存储方法。（）10. 对快速排序来说，初始序列为正序和反序，都是最坏情况。14二、填空题二、填空题（每空 2 分，共 20 分）1数据元素之间存在的相互关系称为。2数据结构从逻辑上分为结构和结构。3线性表的链接存储结构简称为。4所有插入和删除都限定在表的同一端进行的线性表称为。5二叉树的第 i 层上，最多有个结点。6树所对应的二叉树，其根结点的子树一定为空。7顶点表示活动、有向边表示活动间优先关系的网称为。8折半查找的前提条件是要求待查表为表。9将 n 个记录按其关键字大小递增或递减的次序排列起来的过程称为。三、单选题三、单选题（本题的

22、每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1、 （1）2、 （2）3、 （1）4、 （3）5、 （3）1线性表的顺序存储不相符的特性是（）（1）插入和删除操作灵活（2）需要连续存储空间（3）便于随机访问（4）存储密度大2若进队序列为 1，2，3，则出队序列是（）（1）3，2，1（2）1，2，3（3）1，3，2（4） 3，2，13已知广义表 A=（ （a,b）,(c,d)）,则 head(A)等于（）（1） （a,b）（2）(a,b)（3）a,b（4）a4n 个结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩

23、子链域为（）（1）n（2）2n（3）n-1（4）n+15具有 8 个顶点的连通图的深度优先生成树，其边数为（）（1）8（2）9（3） 7（4）6四、应用题四、应用题（共 25 分）1已知二叉树的中序序列为 CDBAEGF，后序序列为 DCBGFEA，请画出该二叉树。 （5 分）2对于给定的 5 个实数 W=8，5，13，2，6，试构造 Huffman 树；并求出每个叶子结点的哈夫曼编码。 （6 分）153对下图：（1）写出其邻接矩阵。 （3 分）（2）求出从顶点 V5出发的广度优先搜索遍历序列（4 分） V3 V6 V1 V4 V2 V5 4给定无序表 D=18，88，15，93，35，51，

24、60，17，22，用二叉排序树查找法在 D 中查找 51。现要求：（1）试画出二叉排序树，并画出查找过程； （3 分）（2）求出其成功的平均查找长度 ASL。 （4 分）16五、算法设计五、算法设计（在下列算法的横线内填上适当的语句或表达式或运算符。每空 3 分，共 30 分）1 1二分插入排序二分插入排序void insertsort( int R )/ 按递增序对 R1R n 进行二分插入排序 inti, j, left, right, mid;for ( i=2;i =;i+) R 0 =R i ;/ 设定 R0为监视哨left=1;right=；while (leftright);if

25、(R0=left;j-)R j+1 =;/ 元素后移Rleft=temp;2层次遍历二叉树设二叉树用二叉链表表示，以 t 为根指针，二叉链表结点的类型为 node；队列 s 的元素类型为指向 node 的指针类型, 队列容量 m 足够大。 层次遍历二叉树的算法如下：struct nodechardata;node*lc,*rc;void preorder (node*t) node*sm ，*p=;int f=r= 1；/设置队列头、尾指针17s1=;while (flc!=NULL)r+；if(p-rc!=NULL)；sr=p-rc;18数据结构（数据结构（0111101111、012110

26、1211）作业题（五）作业题（五）一、判断题一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打每题 1 分，共 10 分）（）1. 算法可以用任意的符号来描述。（）2. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。（）3. 线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中。（）4. 栈是一种先进后出的线性表。（）5. 将插入和删除限定在表的同一端进行的线性表称为队列。（）6. 单链表的结点有且仅有一个指针域。（）7. 二叉树是树的特殊形式。（）8. 在有向图 G 中，和是两条不同的边。（）9. 折半查找方法要求待查表必须是有序表。（）10. 快速排序在最

27、坏情况下的时间复杂度为 O（n2） 。二、填空题二、填空题（每空 2 分，共 20 分）1数据的存贮结构的四种形式为存贮，存贮，存贮和存贮。2 所有插入和删除都在表的一端进行的线性表称为。3 n 个结点的满二叉树,其深度 k=。4 对于顺序循环队列 QM，下标从 0 到 M-1，头尾指针分别为 F 和 R，出队时， 队首指针循环加 1 可表示 F=。5设二叉树的叶结点数为 n0,二度结点数为 n2,则两者之间的关系可表示为。6n 个顶点的连通图的生成树具有条边。7顺序查找的平均查找长度为。三、单选题三、单选题（在本题的每一个备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号

28、里，多选不给分，每题 3 分，共 15 分）1设输入序列为 1，2，3，4 借助一个栈不可能得到的输出序列是（ ）(1)1，2，3，4 (2)4，3，2，1 (3)3，4，1，2 (4)1，3，4，22下列排序算法中，最坏情况下，时间复杂度为 O（n2）的排序算法是（ ）(1) 堆排序(2) 希尔排序(3) 归并排序(4) 快速排序193在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是（ ）（1） p=NULL（2） pnext=NULL（3） p=h（4） pnext=h4与线性表的链接存储不相符的特性是（ ）（1）插入和删除操作灵活 （2）需要连续的存储空间（3）存储空

29、间动态分配（4）需另外开辟空间来保存元素间的关系5对于下边的二叉树，其中序序列为（ ）（1）DBEHAFCG（2）DBHEAFCG（3）ABDEHCFG（4）ABCDEFGHB D E H C F G A 四、应用题四、应用题（25 分）1请分别画出具有三个结点的树和二叉树的所有形态。 （7 分）2画出下列二叉树所对应的中序线索二叉树。 （5 分）B D E H I C F G K J A 3写出上述二叉树的后序遍历序列。 （4 分）204假定有以下关键字序列，试给出快速排序的第一趟排序结果。 （4 分） 8015852565900595 第一趟排序结果为：5已知有一带头结点的双向循环链表（结

30、点个数=3） ，其头指针为head，写出删除最后一个结点的语句序列（引进一个临时指针P, 须先找到尾结点） 。 （5分）设双向循环链表的结点类型为：struct bnode datatypedata;bnode*prior,*next;五、算法设计（在下列算法的横线上填上适当的表达式或语句。每空 3 分，共 30 分）。1 1 将两个有序的顺序表合并成一个有序表将两个有序的顺序表合并成一个有序表void merge(intR , intA ,int s,int m,int t)/对两个升序顺序表 RsRm和 Rm+1Rt合并，结果存入升序顺序表 A 中 int i,j,k;i=s;j=m+1;

31、k=s;while(i=m)&(j=)if(Ri=Rj) Ak=Ri;i+;elseAk=Rj;k+;while(i=)/复制第一个区间中剩下元素 Ak=Ri;i+;k+;while(j=t)/复制第二个区间中剩下元素;j+;k+;212 2对有序表对有序表 R0R0至至 R Rn-1n-1进行二分查找进行二分查找，成功时返回记录在表中的位置成功时返回记录在表中的位置，失失败时返回败时返回 0 0Struct sqlist keytype key;int binsrch(sqlist R ,keytype k)/在表 R 中查找关键字 k int low ,high,mid;low=0

32、;high=n-1;while();if()returnmid;else if( kRmid.key )high=mid-1;else low=mid+1;return;22数据结构作业一三、单选题（本题的第一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）。1、若进栈序列为 1，2，3，4，则不可能得到的出栈序列是（）（1）3，2，1，4（2）3，2，4，1（3）4，2，3，1（4）2，3，4，12、对于下列二叉树，其后序序列为（）（1）ABDECFG（2）DBEAFCG（3）DEBFGCA（4）GFCEBDA3、对于下列

33、AOV 网，不能出现的拓扑序列为（）23（1）12345（2）12435（3）24135（4）214354深度为 k 的完全二叉树所含叶结点的个数最多为（）（1）2K（2）2K-1（3）k（4）2k5衡量查找算法效率的主要标准是（）(1)元素个数(2)所需的存贮量(3)平均查找长度(4)算法难易程度3请画出后序和中序序列相同的二叉树的所有形态。（3 分）4散列函数为 H（k）=k%7，散列表的地址从 0 到 6，用线性控查法解决冲突，建立散列表 ht。给定关键字序列32，13，49，55，22，38，21要求：（1）构造散列表（只画出表，不写算法）；（5 分）24（2）求出平均查找长度。（2

34、分）5用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。（6 分）68452090151050五、算法设计（在下列算法的横线上填上适当的表达形式或语句或运算符。每空 3 分，共30 分）1 在带头结点的 head 单链表的结点 a 之后插入新元素 xstructnodeelemtypedata;数据结构作业二一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打每小题 1 分，共 10 分）二、填空题（每空 2 分，共 20 分）1 对数据所施加的运算可分为两类，即_型和_型。2 将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为_；允许插入的一端称为_。3

35、二叉树的叶结点数据 n0与二度结点数据 n2的关系是_。4 对于顺序循环队列 QM，下标从 0 到 M-1，头尾指针分别用 F 和 R 表示，则队空条件是_。5 N 个顶点的无向完全图具有_条边。6 拓扑排序的操作对象是_。7 快速排序的最坏情况是初始序别为正序和反序， 其时间复杂度为_。8 希尔排序是属于_排序的改进方法。三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1栈和队列都是（）25（1）顺序存贮的线性结构（2）限制存取点的线性结构（3）链接存贮的线性结构（4）限制存取点的非线性结构四、应用题（

36、25 分）1 画出下列二叉树所对应的森林。 （3 分）2 对于下边有向图26（1）画出其邻接表（4 分）（2）写出三种不同的拓扑序列（3 分）第一趟排序过程中数据交换的情况。 （5 分）359215191080100第一趟排序结果：五、算法设计（在下列算法的横线内填上适当的语句或表达式。每空 3 分，共 30 分）1 直接插入排序void insertsort(intR)/按递增序对 R1Rn进行直接插入排序 inti,j;for(i=2;i=_; i+)R 0=Ri;/设定 R0为监视哨j=_;while (R 0 _R j )_;j- -；R j+1=_;/插入第 i 个记录2 先序遍历二

37、叉树设二叉树用二叉链表表示，以 t 为根指针，二叉链表结点的类型为 mode；栈 s 的元素27类型为指向 node 的指针类型，栈容量 M 足够大。先序遍历的非递归算法如下：struct nodechardata;node *lc，*rc;void preorder(node*t)node*sM, *p=_;inttop= - 1;/置栈空；dowhile(p!=NULL) _ ;s+top=_;_;if (top!= - 1)p=stop- -;_ ; while ( top! = - 1) | | (p ! =NULL);数据结构作业三一、判断题（下列各题，你认为正确的，请在前面的括号内

38、打，错误的打。每题 1 分，共 10 分）（ ）1、数据是计算机加工处理的对象。（ ）2、数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。（ ）3、线性表是由 n0 个相同类型元素组成的有限序列。（ ）4、栈是一种后进先出的线性表。（ ）5、从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。（ ）6、单链表设置头结点的目的是为了简化运算。（ ）7、深度为 h 的二叉树最多有 2h-1 个结点。（ ）8、图 G 由两个集合 V（G）和 E（G）所组成，其中顶点集 V（G）可以为空集，而边集 E（G）不能为空。（ ）9、散列法是一种对关键字进行运

39、算的查找方法和存储方法。（ ）10、快速排序在任何情况下，都是速度最快的一种排序方法。二、填空题（每空 2 分，共 20 分）1、 数据无素之间存在的相互关系称为_。282、 数据结构从逻辑上分为_结构和_结构。3、 线性表的顺序存储结构称为_。4、 所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为_。5、 深度为 h 的二叉树，最少有_个结点。6、 折半查找要待查表为_表。7、 n 个记录按其关键字大小递增或递减的次序排列起来的过程称为_。8、 存储数据的时候，不仅要存储数据元素的_，还要存储元素之间的相互_。三、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的

40、答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1与线性表的链接存储相符的特性是（）（1）插入和删除操作灵活（2）需要连续存储空间（3）便于随机访问（4）存储密度大2若进队序列为 1，2，3，4，则出队序列是（）（1）4，3，2，1（2）1，2，3，4（3）1，3，2，4（4）3，2，4，13已知广义表 A=（ （a，b） ，*c，d） ） ，则 head（A）等于（）（1） （a，b）（2） （ （a，b） ）（3）a，b（4）a4结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为（）（1）n（2）2n（3）n-1（4）n+15个顶点的连通图的深度优先生

41、成树，其边数为（）（1）6（2）5（3）7（4）4四、应用题（共 25 分）1已知二叉树的中序序列为 DBHEIAFJCKG，先序序列为 ABDEHICFJGK，请画出该二叉树。 （4 分）2于给定的 5 个实数 W=8，5，13，2，6，试构造 Huffman 树；并求出该树的最小带权路径长度。 （7 分）3对于下边的图 G（1）画出其邻接表（4 分） 。（2）写出从 V1出发的深度优先搜索序列（3 分） 。4给定有序表 D=15，17，18，22，35，51，60，88，93，用折半查找法在 D 中查找18。现要求：（1）试用图示法表示查找过程； （4 分）（2）求出其成功的平均查找长度

42、ASL。 （3 分）29五、算法设计（在下列算法的横线内填上适当的语句或表达式。每空 3 分，共 30 分）1直接选择排序voidselectsort(intR )/按递增序对 R0Rn-1进行直接选择排序inti，j，k，temp;for(i=0;i=_ ; i+k=i;for(j=_; j=n-1;j+)if (R j _ R k )k=j;if(_ ) temp=R i ;R i = _; R k =temp;2中序遍历二叉树设二叉树用二叉链表表示，以 t 为根指针，二叉链表结点的类型为 node；栈 s 的元素类型为指向 node 的指针类型，栈容量 m 足够大。中序遍历的非递归算法如

43、下：structnodechardata;node*lc, *rc;voidpreorder (node*t)node *sm , *p=t;inttop = - 1;/置栈空dowhile(p!=NULL)s+top =_;_;if(top!= - 1)p=stop - -;_;_;while(_)| | (P! =NULL);数据结构作业四30一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题 1 分，共 10 分）（ ）1.数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。（ ）2.算法是对解题方法和步骤的描述。（ ）3.线

44、性表简称为“顺序表“。（ ）4.队列是一种先进后出的线性表。（ ）5.从循环链表的某一结点出发，既能找到它的后继结点。又能找到它的前趋结点。（ ）6.单链表设置头结点的目的是为了把空表与非空表、第一个结点处于非第一个结点处的运算统一起来。（ ）7.深度为 h 的二叉树最多有 2h-1 个结点。（ ）8.图 G 由两个集合 V（G）和 E（G）所组成，其中顶点集 V（G）和边集 E（G）都可以为空集。（ ）9.散列法既是一种查找方法，又是一种存储方法。（ ）10.对于快速排序来说，初始序列为正序和反序，都是最坏情况。二、填空题（每空 2 分，共 20 分）1、 数据无素之间存在的相互关系称为_。

45、2、 数据结构从逻辑上分为_结构和_结构。3、 线性表的顺序存储结构称为_。4、 所有插入和删除都限定在表的同一端进行的线性表称为_。5、 二叉树的第 i 层上，最多有_个结点。6、 树所对应的二叉树，其根结点的_子树一定为空。7、 顶点表示活动、有向边表示活动间优先关系的网称为_。8、 折半查找的前提条件是要求待查表为_表。9、 将 n 个记录按其关键字大小递增或递减的次序排列起来的过程称为_。三、择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1线性表的链接存储不相符的特性是（）（1）插入和删除操作灵活（2

46、）需要连续存储空间（3）便于随机访问（4）存储密度大2若进队序列为 1，2，3，则出队序列是（）（1）3，2，1（2）1，2，3（3）1，3，2（4）3，2， 13已知广义表 A=（ （a，b） ，c，d） ） ，则 head（A）等于（）（1） （a，b）（2） （ （a，b） ）（3）a，b（4）a4n 个结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为（）（1）n（2）2n（3）n-1（4）n+15具有 8 个顶点的连通图的深度优先生成树，其边数为（）（1）8（2）9（3）7（4）6四、应用题（共 25 分）311已知二叉树的中序序列为 CDBAEGF, 先序序列为 D

47、CBGFEA,请画出该二叉树。 （5分）2对于给定的 5 个实数 W=8，5，13，2，6，试构造 Huffman 树；并求出每个叶子结点的哈夫曼编码。 （6 分）3对于图：（1）写出其邻接矩阵。 （4 分） 。（2）求出从顶点 Vs出发的广度优先搜索遍历序列（4 分） 。4给定元序表 D=18，88，15，93，35，51，60，17，22，用二叉排序树查找法在 D中查找 51。现要求：（1）试画出二叉排序，并画出查找过程； （3 分）（2）求出其成功的平均查找长度 ASL。 （4 分）五、算法设计（在下列算法的横线内填上适当的语句或表达式。每空 3 分，共 30 分）1二分插入排序void

48、insertsort( int R )/按递增序对 R1Rn进行二分插入排序inti，j，left，right，mid;for(i=2; i=_;i+)R 0 =R i ;/设定 R0为监视哨left=1; right=_;while(left_right) _ ;if(R0=left; j-)Rj+1=_;/元素后移Rleft=temp;2遍历二叉树设二叉树用二叉链表表示，以 t 为根指针，二叉链表结点的类型为 node；队列 s 的元素类型为指向 node 的指针类型，队列容量 m 足够大。层次遍历二叉树的算法如下：structnode32chardata;node*lc, *rc;voi

49、dpreorder (node*t)node *sm , *p=_;intf=r=1;/设置队列头尾指针s1=_;while (flc!=NULL)r+;_ ;if (p-rc!=NULL)_;sr=p-rc;数据结构作业五一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题 1 分，共 10 分）（ ）1算法可以用任意的符号来描述。（ ）2数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。（ ）3线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中。（ ）4栈是一种先进后出的线性表。（ ）5将插入和删除限定在表的同一端进行的线性表称为队列。（ ）6单链表的结

50、点有仅有一个指针域。（ ）7二叉树是树的特殊形式。（ ）8在有向图 G 中，是两条不同的边。（ ）9折半查找方法要求待查表必须是有序表。（ ）10快速排序在最球情况下的时间复杂度为 0（n2） 。二、填空题（每空 2 分，共 20 分）1数据的存贮结构的四种形式为_存贮,_存贮,_存贮和_存贮。2所有插入和删除都在表的一端进行的线性表称为_。3n 个结点的满二叉树，其深度 k=_。4对于顺序循环队列 QM，下标从 0 到 M-1，头尾指针分别为 F 和 R，出队时，队道指针循不加 1 可表示 F=_。335设二叉树的叶结点数为 n0，二度结点数为 n2，则两者之间的关系可表示为_。6n 个顶点

51、的连通图的生成树具有_条边。7顺序查找的平均查找长度为_。三、择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题 3 分，共 15 分）1设输入序列为 1，2，3，4，借助一个栈不可能得到的输出序序列是（）（1）1，2，3，4（2）4，3，2，1（3）3，4，1，2（4）1，3，4，22下列排序算法中，最坏情况下，时间复杂度为 0（n2）的排序算法是（）（1）堆排序（2）希尔排序（3）归并排序（4）快速排序3在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是（）（1）p=NULL（2）pnext=NULL（3）p=h（

52、4）pnext=h4与线性表的链接存储不相符的特性是（）（1）插入和删除操作灵活（2）需要连续的存储空间（3）存储空间动态分配（4）需另外开辟空间来保存元素间的关系5对于下边的二叉树,其中序序列为（）（1）DBEHAFCG（2）DBHEAFCG（3）ABDEHCFG（4）ABCDEFGH四、应用题（25 分）1请分别画出具有三个结点的树和二叉树的所有形态。 （7 分）2画出下列二叉树所对应的中序线索二叉树。 （5 分）3435数据结构作业题一参考答案数据结构作业题一参考答案一、判断题1、 （）2、 （）3、 （）4、 （）5、 （）6、 （）7、 （）8、 （）9、 （）10、 （）二、填空题

53、1、顺序链接索引散列2、栈363、log2n +14、(R+1) % M5、存储6、n*(n-1)7、(n+1) / 2三、单选题1、 （3）2、 （3）3、 （1）4、 （2）5、 （3）四、应用题1、解：森林转换成的二叉树如下： A B F E C G D 2、解：(1)邻接矩阵如下：01131106106053081080125120 (2)用 Kruskal 算法求得的最小生成树如下：37 6 V4 V1 5 V5 10 V2 V3 V6 3 8 边集数组如下： fromvex weight endvex 2 4 3 4 6 3 5 8 6 1 2 5 3 5 10 1 4 3 2 5

54、 3、解：中序和后序相同的所有二叉树形态如下： 4、解：线性探查的散列表如下： 49 55 22 38 32 21 13 0 1 2 6 5 4 3 平均查找长度 ASL=(1+1+1+3+2+1+6)/7=15/7=2.145、解：直接选择排序的每一趟排序结果如下：初始状态： 68452090151050 第一趟排序结果：10 452090156850 第二趟排序结果：1015 2090456850 第三趟排序结果：101520 90456850 38第五趟排序结果：1015204550 6890 第六趟排序结果：101520455068 90 五、算法设计1、 new node 、x、p=

55、p-next 、 s-next=p-next 、 p-next=s2、i、R0、 qksort(R,i,q)数据结构作业题二参考答案一、判断题1、 （） 2、 （） 3、 （） 4、 （） 5、 （）6、 （） 7、 （） 8、 （） 9、 （） 10、 （）二、填空题1、 引 用、加工2、 队列、队尾3、 n0=n2+14、 F=R5、 n*(n-1) / 26、 AOV 网7、 O（n2）8、 插入三、单选题1、 （2）2、 （3）3、 （4）4、 （3）5、 （1）四、应用题1、解：二叉树所对应的森林如下： C F I A E G B D H 2、解：(1) 邻接表为39 1 2 4 3

56、 5 4 4 3 2 5 4 （2）三种不同的拓扑序列如下： V1V2V3V5V4 V1V3V5V2V4 V1V3V2V5V43、解：先序和中序相同的二叉树的所有形态如下： 4、解：(1)外链法的散列表为 0 1 3 2 4 5 6 8 7 9 10 55 23 12 1 68 79 14 27 84 19 9 10 （2） 平均查找长度 ASL=（1*9+2*2+3*1）/ 12 = 16/12 = 1.333。5、解：快速排序的第一趟排序结果： 10 19 15 35 92 80 100 40五、算法设计1、n、i 1、Rj+1=Rj、 R02、t、 coutpdata、p、p=plc、p=prc数据结构作业题三参考答案一、判断题1、 （）2、 （）3、 （）4、 （）5、 （）6、 （）7、 （）8、 （）