广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:＿＿。 广度优先搜索序列：＿＿。

16.已知一个无向图的邻接表如图1.17所示，试写出从顶点V0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 深度优先搜索序列:＿＿。 广度优先搜索序列：＿＿。

17.已知一个带权有向图如1.18所示，用迪杰斯特拉提出的算法求其任一对结点之间的最短路径。

18.构造如图1.19所示加权图的最小生成树（给出利用克鲁斯卡尔算法构造的过程）。 19.对长度为11有序集，进行折半查找，试画出它的一棵判定树，并求在等概率情况下的平均查找长度。

20.已知一个顺序存储的有序表为（15，26，34，39，45，56，58，63，74，6），试画出对应的二分查找判定树，求出其平均查找长度。

21.假定一个线性表为（38，52，25，74，68，16，30，54，90，72）画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。

22.假定一个待散列存储的线性表为（32，75，29，63，48，94，25，36，18，70，49，80），散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试画出最后得到的链式哈希函数列表，并求出平均查找长度。

23.已知一组记录为（46，74，53，14，26，38，86，65，27，34）。 （1）给出采用直接插入排序法进行排序时每一趟的排序结果。 （2）给出采用冒泡排序法进行排序时每一趟的排序结果。 （3）给出采用快速排序法进行排序时每一趟的排序结果。

（4）给出采用直接选择排序法进行排序时每一趟的排序结果。 （5）给出采用堆排序法进行排序时每一趟的排序结果。

24.编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最小值并同第一个元素交换，再从待排序区间中选择一个最大值并同最后一个元素进行交换，反复进行直到最后待排序区间中元素个数不超过1为止。 参考答案 一 选择题

1.D 2.C 3.A 4.B 5.A 6.C 7.C 8.D 9.B 10.B 11.A 12.C 13.B 14.A 15.C 16.D 17.B 18.B 19.C 20.B 21.D 22.C 23.B 24.A 25.A 26.A 27.B 28.A 29.C 30.B 31.C 32.D 33.C 34.D 35.A 36.B 37.B 38.D 39.B 40.A 41.C 42.D 43.A 44.D 45.B 46.B 47.D 48.B 49.C 50.C 51.C 52.B 53.A 54.C 55.C 56.D 57.C 58.A 59.A 60.C 61.D 62.B 63.C 64.A 65.B 66.D 67.A 68.A 69.D 70.D 71.C 72.B 73.B 74.A 75.C 76.D 77.C 78.D 79.B 80.C 81.A 82.A 83.B 84.D 85.A 86.C 87.B 88.D 89.B 90.C 91.B 92.C 93.D 94.A 95.D 96.B 97.C 98.B 99.D 100.B 101.C 102.A 103.C 104.D 105.B 106.C 107.C 108.B 109.D 110.A 111.C 112.B 113.D 114.B 115.A 116.D 117.A 118.A 119.B 120.D

二 填空题

1.线形；非线形 2.顺序；链式；索引；散列存储结构 3. n；n（n+1）/2；O（n） 5.顺序；链式 7链式;顺序 9.O（1）；O（n） 13.p->next->next

4.线性

6.顺序表；链式表 8.O（n）；O（1） 10.p->next

14.p->next 16.O(1);O(n) 18.前趋；后续

11.HL->next==NULL; HL->next==HL 12. 循环 15.p->next=head;head=p 17.相同

19.q 21. 先进后出；先进先出 23.栈顶指针；插入（写入） 25.-1；M-1 27.top->next 29.Pop(s);Pop(s);Push(s,d) 31.front=rear;(r+1)%M==front 33.0;N-1

20. p->prior

22.0;1

24. 栈顶元素; 栈顶指针 26．p->next=top;top=p 28.Push(s,3);Pop(s);Push(s,5) 30.队尾；队首

32.(front+1)%M;(r+1)%M 34.队尾指针；插入（写入）

35.p->next=NULL;r=f=p 36.p->next=r->next;r=r->next=p

37.（front=rear）&&(front!=NULL)或者（front=rear）&&(rear!=NULL)38.空栈；空；只含有一个结点 39.1432

40.3080

41.3642.i(i-1)/2+j-1 44.树型或层次 46.根；前趋（父）；后续（子） 48.2；6 50.10；4；3 52.B;I和J 54.2i；2i+1；i/2 55.16 56.5；8 57.A；F；空 58.2；2；3

59.a[10];a[11];a[2]

60.a[2i+1];a[2i+2];a[(i-1)/2] 61.2n,n-1,n+1 62.2h-1;2h-1 63.16;31

64.ABCDEF;CBAEDF;CBEFDA 65.2;4;3 66.4;5 67.3 68.4;87 69.图状 70.2

43.52 45.n-1 47.7；1；4；1 49.3；4

51.2；1；1；6 53.6

71.n(n-1)/2;n(n-1) 72.4 73.2;4 74.n-1

75.邻接矩阵；邻接表 76.1 77.3 78.4 79.7 80.n;n 81.e;2e

82.出边；入边

83.acdeb;acedb(答案不唯一) 84.acfebd;acefbd(答案不唯一) 85.深度；广度 86.唯一 87.（n+1）/2 88.

89.20.5;41 90.1b(n+1) 91.6

92.1;3 93.6;19 94.11 95.

96.小于；大于

97.查找成功；左子树；右子树 98. 左子树；右子树 99.1 100.5 101.2 102.n/m 103.3;2

104.插入；选择 105.4

106.直接插入 107.n-1;1

108.(46,56,38,40,79,84) 109.4 110.冒泡 111.3

112.4

113.[40 38]46[56 79 80] 114.快速

115.O(n2); O(n)

116.2 117.快速

118.（40，46，56，79，84，38） 119.堆排序 120.简单排序

三 名词解释

数据是指反映客观事物的信息的集合，它是数据结构所要描述的东西。 2.数据元素是数据的一个个体，它是数据的基本单位。

数据对象是指在数据这个集体中人们感兴趣的一个子集，通常，数据对象中的元素具有某些相同的特性。

数据结构是指相互之间有关联的数据元素的集合。 逻辑结构是指数据之间的逻辑关系。

算发在计算机执行时在时间资源方面消耗的多少。 算发在计算机执行时在空间资源方面消耗的多少。

栈是被限定为仅能在表尾进行插入和删除运算的线性表。

列对是一种只允许在表的一端进行插入，而在另一端进行删除的受限的线性表。 压缩存储是指给多个值相同的元素只分配一个空间，对零元素不分配空间。

树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。

一个结点的子树的个数称为该结点的度。 树的所有结点中最大的度称为树的度。

树的深度是指树的所有结点中最大的层次，又称树的高度。

有序树是指如果一棵树所有结点的子结点的左右顺序不可颠倒的树。

遍历是指循某条线路，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。 哈夫曼树是指以文本中出现的字符为叶子结点的最优二叉树，其中叶子结点的全值为该字符在文本中出现的几率。

邻接关系是指在无向图中若存在边（Vi，Vj），则称结点Vi邻接于Vj或结点Vj邻接于Vi；在有向图中若存在边（Vi，Vj），则称结点Vj邻接于结点Vi。 路径是连接两个结点的边的集合。

如果无向图中的任意两个结点都是通的，则称无向图是连通图。

在有向图中，任意一对结点Vi和Vj之间都存在路径，则称有向图为强连通图。 若一个有向图中每一对结点之间都存在一条边，则称无向图为完全无向图。 若一个有向图中每一对结点之间都存在两条不同的边，则称有向图为完全有向图。 主关键字是指能用来唯一标识该记录的数据项。

四 简答题

线性结构是指数据元素之间存在一对一的关系。 树型结构是指元素之间存在一对多的关系。

图或网状结构是指数据元素之间存在多对多的关系。

算法的复杂度分析可分为时间复杂度和空间复杂度。时间复杂度以基本操作重复执行的次数为算法的时间量度。空间复杂度指算发所存储空间的量度。

3.要使100n2快于2n时, 必须满足100n2(2n, 可以算出n的值为15时, 2n恰好大于100n2, 所