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

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

2、. 后序序列和中序序列能唯一确定一棵二叉树。（ ）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）GFCEBDA 3对于下列AOV网，不能出现的拓扑序列为（ ）（1） 1 2 3 4 5 （2）1 2 4 3 5 （3）2 4 1 3 5 （4）2 1 4 3 5 4深度为k的完全二叉树所含叶结点的个数最多为（ ）（1）2k （2） 2k-1 （3） k （4） 2

4、k 5衡量查找算法效率的主要标准是（ ）（1） 元素个数 （2） 所需的存贮量 （3） 平均查找长度 （4） 算法难易程度 四、应用题（25分）1将下列森林转化为二叉树。（3分） 2对下图：（1）写出其邻接矩阵。（2分）（2）按Kruskal算法求其最小生成树；并写出相应的边集数组。（4分） 3请画出后序和中序序列相同的二叉树的所有形态。（3分）4散列函数为H（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。给定关键字序列 32，13，49，55，22，38，21要求：（1）构造散列表（只画出表，不写算法）；（5分）（2）求出平均查找长度。（2分）5用直接选择排序方法

5、对下列关键字进行排序，请写出每一趟排序的结果。（6分）68 45 20 90 15 10 50五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。每空3分，共30分）1在带头结点的head单链表的结点a之后插入新元素x struct node elemtype data; node *next; ; 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)cou

6、tnext=p-next _;_p-next=s _;2 快速排序void qksort (int R , int p, int q) / 按递增序对Rp Rq 进行快速排序 int i=p, j=q;R 0 =R 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) ; 数据结构（01111、01211）作业题（二）1、 判断题（下列各题，你认为正确的，请在前面的括号

7、内打，错误的打。每小题1分，共10分）（ ）1. 数据的存贮结构独立于计算机。（ ）2. 线性表简称为“顺序表”。（）3. 对数据的任何运算都不能改变数据原有的结构特性。（）4. 从循环单链表的任一结点出发，可以找到表中所有结点。（ ）5. 栈是一种先进先出的线性表。（ ）6. 链表的主要缺点是不能随机访问。（ ）7. 二叉树是树的特殊形式。（ ）8. 图可以没有边，但不能没有顶点。（ ）9. 冒泡排序算法是稳定的排序。（ ）10. 散列法是一种对关键字进行比较的查找方法。2、 填空题（每空2分，共20分）1、 引 用 、 加工 2、 队列 、 队尾 3、 n0=n2+1 4、 F=R 5、

8、n*(n-1) / 2 6、 AOV 网 7、 8、 插入 1对数据所施加的运算可分为两类，即 型和 型。2将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为 ； 允许插入的一端称为 。3二叉树的叶结点数n0与二度结点数n2的关系是 。4对于顺序循环队列QM，下标从0到M1，头尾指针分别用F和R表示，则队空条件是 。5n个顶点的无向完全图具有 条边。6拓扑排序的操作对象是 。7快速排序的最坏情况是初始序列为正序和反序，其时间复杂度为 。 8希尔排序是属于 排序的改进方法。三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题

9、3分，共15分） 1、（2） 2、（3） 3、（4） 4、（3） 5、（1） 1栈和队列都是（ ）（1）顺序存贮的线性结构 （2）限制存取点的线性结构（3）链接存贮的线性结构 （4）限制存取点的非线性结构2与线性表的链接存贮不相符合的特性是 （ ）（1）便于插、删运算（2）存贮空间动态分配（3）需要连续的存贮空间 （4）只能顺序查找3设二叉树的根为第一层，则第i层上的结点数最多有 （ ）（1）i （2） i +1 （3）i - （4）i -1 4直接选择排序的时间复杂度为 （ ）（1）O（n） （2）O(n2n) （3）O(n2 ) （4）O(2 n)5给定下列有向图，从顶点V1出发，其深度优

10、先搜索序列为（ ）（1）12534 （2）12435 （3） 14325 （4）12345四、应用题（25分） 1画出下列二叉树所对应的森林。（3分） 2对于下边有向图 （1）画出其邻接表（4分） （2）写出三种不同的拓扑序列（3分） 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对下列关键字序列进行

11、快速排序，请写出第一趟排序结果，并标识出在第一趟排序过程中数据交换的情况。（5分）35 92 15 19 10 80 100第一趟排序结果：五、算法设计（在下列算法的横线内填上适当的语句或表达式。 每空3分，共30分）1 直接插入排序 、 、 、 、 void insertsort(int R )/ 按递增序对R1 R n 进行直接插入排序 int i, j; for ( i=2; i = n ; i+ ) R 0 =R i ; / 设定R0为监视哨 j= i 1 ； while (R 0 R j ) Rj+1=Rj ; j- - ; R j+1 = R0 ; / 插入第i个记录 2先序遍历二

12、叉树 设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为node；栈s的元素类型为指向node的指针类型, 栈容量M足够大。先序遍历的非递归算法如下： struct node char data; 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 ); 数据结构（01111、01211）作业题（三

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

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

15、半查找要求待查表为 表。7n个记录按其关键字大小递增或递减的次序排列起来的过程称为 8存储数据的时侯，不仅要存储数据元素的 ，还要存储元素之间的相互 。三、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题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)等于（

16、 ）（1）（a,b） （2）(a,b) （3）a,b （4）a4n个结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为 （ ）（1）n （2）2n （3）n-1 （4）n+1 56个顶点的连通图的深度优先生成树，其边数为（ ）（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出发的深度优先搜索序列

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

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

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

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

21、把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题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个结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为 （ ）（1）n （2）2

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

23、）（2）求出其成功的平均查找长度ASL。（4分）五、算法设计（在下列算法的横线内填上适当的语句或表达式或运算符。 每空3分，共30分）1二分插入排序 void insertsort( int R )/ 按递增序对R1R n 进行二分插入排序 int i, j, left, right, mid; for ( i=2; i = ; i+) R 0 =R i ; / 设定R0为监视哨 left=1;right= ； while (left right) ;if(R0=left;j-)R j+1 = ; / 元素后移 Rleft=temp; 2层次遍历二叉树 设二叉树用二叉链表表示，以t为根指针，二

24、叉链表结点的类型为node；队列s的元素类型为指向node的指针类型, 队列容量m足够大。层次遍历二叉树的算法如下：struct node char data; node *lc,*rc; ;void preorder (node *t) node *sm ，*p= ; int f=r= 1；/设置队列头、尾指针s1= ; while (flc!=NULL) r+； ； if(p-rc!=NULL) ； sr=p-rc; 数据结构（01111、01211）作业题（五）一、判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打 每题1 分，共10分）（ ）1. 算法可以用任意的符号来描述。

25、 （ ）2. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 （ ）3. 线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中。（ ）4. 栈是一种先进后出的线性表。 （ ）5. 将插入和删除限定在表的同一端进行的线性表称为队列。（ ）6. 单链表的结点有且仅有一个指针域。（ ）7. 二叉树是树的特殊形式。（ ）8. 在有向图G中，和是两条不同的边。 （ ）9. 折半查找方法要求待查表必须是有序表。（ ）10. 快速排序在最坏情况下的时间复杂度为O（n2）。二、填空题（每空2分，共20分）1数据的存贮结构的四种形式为 存贮， 存贮， 存贮和 存贮。2 所有插入和删除都在表的

26、一端进行的线性表称为 。3 n个结点的满二叉树,其深度k= 。4 对于顺序循环队列QM，下标从0到M-1，头尾指针分别为F和R，出队时， 队首指针循环加1可表示F= 。5设二叉树的叶结点数为n0 ,二度结点数为n2 ,则两者之间的关系可表示为 。6n个顶点的连通图的生成树具有 条边。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下列

27、排序算法中，最坏情况下，时间复杂度为O（n2）的排序算法是（ ）(1) 堆排序 (2) 希尔排序(3) 归并排序(4) 快速排序3在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（ ）（1） p=NULL （2） pnext=NULL （3） p=h （4） pnext=h4与线性表的链接存储不相符的特性是 （ ）（1）插入和删除操作灵活（2）需要连续的存储空间（3）存储空间动态分配（4）需另外开辟空间来保存元素间的关系5对于下边的二叉树，其中序序列为 （ ）（1）DBEHAFCG （2）DBHEAFCG （3）ABDEHCFG （4）ABCDEFGH 四、应用题（25分） 1请

28、分别画出具有三个结点的树和二叉树的所有形态。（7分）2画出下列二叉树所对应的中序线索二叉树。（5分）3写出上述二叉树的后序遍历序列。（4分）4假定有以下关键字序列，试给出快速排序的第一趟排序结果。（4分） 80 15 85 25 65 90 05 95 第一趟排序结果为： 5已知有一带头结点的双向循环链表（结点个数=3），其头指针为head，写出删除最后一个结点的语句序列（引进一个临时指针P, 须先找到尾结点）。（5分） 设双向循环链表的结点类型为： struct bnode datatype data; bnode *prior,*next; ;五、算法设计（在下列算法的横线上填上适当的表达

29、式或语句。每空3分，共30分）。1 将两个有序的顺序表合并成一个有序表 void merge(int R , int A ,int s,int m,int t)/对两个升序顺序表RsRm和Rm+1Rt合并，结果存入升序顺序表A中 int i,j,k; i=s;j=m+1;k=s; while(i=m)&(j= ) if(Ri=Rj) Ak=Ri;i+; ; else Ak=Rj; ;k+; while(i= ) /复制第一个区间中剩下元素 Ak=Ri;i+;k+; while(j=t) /复制第二个区间中剩下元素 ;j+;k+; 2对有序表R0至Rn-1进行二分查找，成功时返回记录在表中的位置

30、，失败时返回0Struct sqlist keytype key; int binsrch(sqlist R ,keytype k) /在表R中查找关键字k int low ,high,mid; low=0; high=n-1; while( ) ; if( ) return mid; else if( kRmid.key ) high=mid-1; else low=mid+1; return ; 数据结构作业一三、单选题（本题的第一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）。1、若进栈序列为1，2，3，4，则不可能得到的出栈

31、序列是（ ） （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）12345 （2）12435 （3）24135 （4）214354深度为k的完全二叉树所含叶结点的个数最多为（ ）（1）2K （2）2K-1 （3）k （4）2k5衡量查找算法效率的主要标准是（ ） (1)元素个数 (2)所需的存贮量 (3)平均查找长度 (4)算法难易程度3请画出后序和中序序列相同的二叉树的所有形态。

32、（3分）4散列函数为H（k）=k%7，散列表的地址从0到6，用线性控查法解决冲突，建立散列表ht。给定关键字序列32，13，49，55，22，38，21要求：（1）构造散列表（只画出表，不写算法）；（5分） （2）求出平均查找长度。（2分）5用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。（6分）68 45 20 90 15 10 50五、算法设计（在下列算法的横线上填上适当的表达形式或语句或运算符。每空3分，共30分）1 在带头结点的head单链表的结点a之后插入新元素x struct nodeelemtype data;数据结构作业二一、判断题（下列各题，你认为正确的，请在

33、前面的括号内打，错误的打每小题1分，共10分）二、填空题（每空2分，共20分）1 对数据所施加的运算可分为两类，即_型和_型。2 将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为_；允许插入的一端称为_。3 二叉树的叶结点数据n0与二度结点数据n2的关系是_。4 对于顺序循环队列QM，下标从0到M-1，头尾指针分别用F和R表示，则队空条件是_。5 N个顶点的无向完全图具有_条边。6 拓扑排序的操作对象是_。7 快速排序的最坏情况是初始序别为正序和反序，其时间复杂度为_。8 希尔排序是属于_排序的改进方法。三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号

34、填入题干的括号内，多选不给分，每小题3分，共15分）1栈和队列都是 （ ） （1）顺序存贮的线性结构 （2）限制存取点的线性结构 （3）链接存贮的线性结构 （4）限制存取点的非线性结构四、应用题（25分）1 画出下列二叉树所对应的森林。（3分）2 对于下边有向图（1） 画出其邻接表（4分）（2） 写出三种不同的拓扑序列（3分）第一趟排序过程中数据交换的情况。（5分）35 92 15 19 10 80 100第一趟排序结果：五、算法设计（在下列算法的横线内填上适当的语句或表达式。每空3分，共30分）1 直接插入排序void insertsort(int R )/按递增序对R1Rn进行直接插入排序

35、 int i, j; for (i=2; i=_; i+) R 0=Ri; /设定R0为监视哨 j=_; while (R 0 _R j ) _; j- -； R j+1=_; /插入第i个记录 2 先序遍历二叉树设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为mode；栈s的元素类型为指向node的指针类型，栈容量M足够大。先序遍历的非递归算法如下：struct node char data; node *lc，*rc; ;void preorder (node *t)node *sM, *p=_; int top= - 1; /置栈空； dowhile (p!=NULL) _ ;

36、 s+top=_; _; if (top!= - 1) p=stop- -; _ ; while ( top! = - 1) | | (p ! =NULL); 数据结构作业三一、 判断题（下列各题，你认为正确的，请在前面的括号内打，错误的打。每题1分，共10分） （ ）1、数据是计算机加工处理的对象。 （ ）2、数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 （ ）3、线性表是由n0个相同类型元素组成的有限序列。 （ ）4、栈是一种后进先出的线性表。 （ ）5、从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。 （ ）6、单链表设置头结点的

37、目的是为了简化运算。 （ ）7、深度为h的二叉树最多有2h-1个结点。 （ ）8、图G由两个集合V（G）和E（G）所组成，其中顶点集V（G）可以为空集，而边集E（G）不能为空。 （ ）9、散列法是一种对关键字进行运算的查找方法和存储方法。 （ ）10、快速排序在任何情况下，都是速度最快的一种排序方法。二、 填空题（每空2分，共20分）1、 数据无素之间存在的相互关系称为_。2、 数据结构从逻辑上分为_结构和_结构。3、 线性表的顺序存储结构称为_。4、 所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为_。5、 深度为h的二叉树，最少有_个结点。6、 折半查找要待查表为_表。7、

38、n个记录按其关键字大小递增或递减的次序排列起来的过程称为_。8、 存储数据的时候，不仅要存储数据元素的_，还要存储元素之间的相互_。三、 选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题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

39、，b） （2）（a，b） （3）a，b （4）a4结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为（ ）（1）n （2）2n （3）n-1 （4）n+15个顶点的连通图的深度优先生成树，其边数为（ ） （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。现要求：