data=item; newptr->next =NULL; if (HQ.rear==NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear->next=newptr; }17 稀疏矩阵的定义：其非零元素的个数远远小于零元素的个数。
稀疏矩阵的严格定义： 稀疏因子=非零元素/所有元素个数 通常认为 0.3 的矩阵为稀疏矩阵
三元组表示形式： ( i, j, value ) i为第i行， j为第j列，value为非0元素的值 18 广义表的特点
规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a是广义表的表头head。其余元素组成表尾tail；
广义表中的数据元素有相对次序;广义表的长度定义为所含元素的个数; 广义表的深度;注意:“空表〞的深度为 1 ; 广义表可以共享;
广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。 例：D=(E, F) E=(a, (b, c), D) , F=(d, (e)) D的长度为2，深度为无穷 19 求广义表的长度 深度
广义表的深度=Max {子表的深度} +1；空表的深度 = 1；仅由单元素组成的表的深度 = 1 例LS=((),(e),(a,(b,c,d)))长度为3深度为3； LD=(((a),((),b),(c)))长度1深度4 20 树的性质1
树中结点个数等于所有结点的度数加1 21 二叉树的性质4 P185
性质4：
假设对具有n个结点的完全二叉树按照层次从上到下,每层从 i 的结点具有以下性质:
(1) i的结点有左孩子,2i;
(2) 除树根结点外,i,那么它的双亲结点的也就是说,当i为偶数时,i/2,它是双亲结点的左孩子,当i为奇数时,为(i-1)/2,它是双亲结点的右孩子. (3) 假设i≦|_n/2_|,即2i ≦ 22 给定权值 构造哈夫曼树 求带权路径长度〔参考作业题〕
例题1：如右图：
WPL=7*1+5*2+2*3+4*3=35
23 哈夫曼树的特点
又称最优树，是一种带权路径长度WPL最 小的二叉树。
由0和1组成，用哈夫曼编码传送的电文长度；传输速率最快。
叶子结点的度为零；除叶子结点外的所有结点的度都为2
24 二叉排序树求平均查找长度:
K为层数，n表示最大层数，m〔k〕表示第k层有m结点个数， M表示所有结点个数。
/〔M〕
25 有向图边数和顶点入度 出度关系
在有向图的邻接表中，从一顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍；在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的1倍；无向图的邻接表中结点个数的边数的2倍。 向图边数=所有度之和/2
26 无向图 顶点数和最小生成树的边数关系
无向图 顶点数n：最小生成树的边数n-1 27 图的邻接表P258
邻接表:是图的一种链式存储结构。在邻接表中，对图中每个顶点建一个单链表，第i个单链表中的结点表示依附于顶
点vi的边〔对于有向图是以顶点vi为尾的弧〕。 图的邻接表是存放什么的：
无权无向图：列存放所有节点，横向为结点对应邻接结点和指针指向结点对应的下一邻接点
带权有向图：列存放所有节点，横向为结点的出度的所有邻接点，其中第一项为结点名称，第二项为与该结点名称对应的权值，第三项为指针指向结点对应的下一出度邻接点。
28 求最短路径长度P281
两个顶点间可能存在多条路径，其中有一条是长度最短的路径，即最短路径
假设带权值要i到j中所经过边权值之和最小的路径称为最短路径，其权值称为最短路径长度。
29 图的边数与顶点数的关系
〔以下是网上找的小题〕
a).在一个图中,所有顶点的度数之和等于所有边数的1倍。 b).在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的1倍。 c).一个有n个顶点的无向图最多有n(n-1)/2条边。 d).具有4个顶点的无向完全图有6条边。 e).具有6个顶点的无向图至少应有5条边才能确保是一个连通图。 h).在一个具有n个顶点的无向图中,要连通全部顶点至少需要n-1条边。 i).对于一个具有n个顶点的无向图,假设采用邻接矩阵表示,那么该矩阵的大小n2 g).对于一个具有n个顶点和e条边的无向图,假设采用邻接表表示,那么表头向量的大小为 n ，所有邻接表中的结点总数是2e 。 k).一个图中的一条路径长度为k，那么该路径所含的顶点数为k-1 30 求最小生成树:带权连通图中,总的权值之和最小的带权生成树 1） 布里姆算法
依次在G中选择一条一个顶点仅在V中,另一个顶点在U中,并且权值最小的边参加集合TE,同时将该边仅在V 中的那个顶点参加集合U. 重复上述过程n-1次,使得U=V,此时T为G的最小生成树.
2） 克鲁斯卡尔算法
将图Ｇ中的边按权值从小到大的顺序依次选取，假设选取的边使生成树Ｔ形成回路，那么将其舍弃，如此进行下去，直到TE中包含有n-1条边为止,此时T为G的最小生成树.
31 顺序查找的平均查找长度:〔1+2+3……n〕/N 32 构造二叉排序树 求平均查找长度
平均查找长度为：〔1*1+2*2+3*4+4*1〕/8=21/8
33二分查找 给定有序表和待查元素 求依次与哪些元素进行比拟
将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一维数组A[0..9]中，然后采用二分 4，7，5 _。 34冒泡排序 每趟需要进行的比拟次数，最多进行多少趟 n-1趟 35 快速排序 第一次划分结果
36 各排序算法空间复杂度
时间复杂度
平均情况 最坏情况 最好情况
直接插入 O(n2)
空间复杂稳定性 复杂性 度 O(1)
稳定 简单 不稳定 较复杂 稳定 简单
O(n2) O(n)
希尔排序 O(n*n1/2) O(n2) 冒泡排序 O(n2)
O(nlog2n) O(1) O(n)
O(1)
O(n2)
快速排序 O(nlog2n) O(n2) 直接选择 O(n2)
O(nlog2n) O(log2n) 不稳定 较复杂 O(n2)
O(1)
不稳定 简单 不稳定 较复杂 稳定 较复杂 稳定 较复杂 O(n2)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd)
37 二叉排序树的特点
二叉排序树的中序是有序的；左孩子比根小，右孩子大于等于根
38 顺序查找适合的存储结构
39排序算法时间复杂度 (见36知识点图) 40 双循环链表 〔老师忘记出什么样的了〕 41 图连通需要的边数
在n个顶点的无向图中，假设边数>=n-1，那么该图必是连通图。 42 排序的稳定性(见36知识点图)
稳定的有：直接插入 、归并排序、基数排序、冒泡排序 不稳定的有：快速排序、希尔排序、直接选择、堆排序
43 树的性质3
课件：性质3 深度为h的k叉树中至多有(k-1)/(k-1) 结点。
h
满k叉树：结点个数等于(k-1)/(k-1) 的k叉树。
递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。
h
44 二叉树的定义：二叉树为度为2的有序树。
45 二分查找 最多需要比拟次数：N个元素最多比拟n/2次 46树的深度的定义：树中所有结点层次的最大值，也称高度。
每次调整至少能排除一半的个数(从x到其x-1层,x层得个数应该是所有个数的一半+1),所以复杂度是log级别
比方有32个元素(为了方便取一个2的幂), 第一次排除 ,16,第二次,8,第三次4,... 2,1. 以这种规律排除几次才能完呢?
比方要排除a次,那么 第一次 2^(a-1) ,第二次2^(a-2)... 第三次2^(a-3) ....第a次2^0=1 是不是 总的个数-1= 1+2+4+...2^(a-1) =2^a-1 那么总的个数=2^a 所以: a=log2 (总的个数)
对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_________ 2n ____个，其中_____ n-1__________个用于指向孩子，____________ n+1_____个指针是空闲的。
2i+1____,右孩子元素为____ 2i+2 ___________，双亲元素为____(i-1)/2________。
6. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。答： ASL=(1*1+2*2+3*4)/7=17/7
2.从一个长度为n的顺序表中删除第i个元素(0≤i≤n-1)时，需向前移动n-i+1个元素。 [ n-i-1 ]
〔×〕
1．在一个长度为n的顺序表中删除第i个元素时，需向前移动 n－i－1 个元素。插入i位置，移动 n－i个元素。
8．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，那么有n0＝n2＋1 。 9．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点。
3、顺序查找查找成功时的最坏比拟次数为〔n-1〕和查找失败时的比拟次数为〔n〕。
只有非空的广义表的表尾永远是广义表 表头可以是原子也可以是子表
3．设某堆中有n个结点，那么在该堆中插入一个新结点的时间复杂度为O(log2n)。〔对 〕 一个n个顶点的无向连通图最多有n(n-1) /2 条边，最少有 n-1 条边。
8、用邻接表表示图进行广度优先遍历时，通常是采用〔B队列〕 来实现算法的。 9、用邻接表表示图进行深度优先遍历时，通常是采用 (A、栈) 来实现算法的。
6.在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率的情况下，查找成功时的平均查找长度为____________。
A n B n/2 C (n+1)/2 D (n-1)/2
D 。
A、iC、2*i+1>nD、2*i>n
5.下面程序段的时间复杂度为____________。
int i=1; while (i<=n) i=i*2; A O(n)
14. 对于长度为N的线性表,在最坏情况下,以下各种排序所对应的比拟次数中正确的选项是______________。 A 冒泡顺序为N/2
B 冒泡顺序为N
B O(n1/2) C O(log2n) D O(n2)
C 快速排列为N D 快速排序为N(N+1)/2
.快速排序的时间复杂度为O(log2n) ×
.结点最少的树为只有一个结点的树 ×
.顺序存储的线形表可以随机存取 √
