for（intj=0;j<=i;j++）
s;Westorea4×4symmetricmatrixAintoanarrayBwithrowmajororder,Storethelowertriangleonly.theindexofelementa[2][3]inBis6.
3．Wecanuse3vectortypetostorevalueandofnon-zeroelementsinasparsematrix.
4.A______stack______isalistwhereremovalandadditionoccuratthesameend.FrequentlyknownaLIFO（Last-In-First-Out）structure.
5.T（n）=2T（n/2）+cn,T（n）=O（logn）
T（n）=T（n-1）+cn,T（n）=O（_____n_____）
6.Thereisabinarytreewhoseelementsarecharacters.Preorderlistofthebinarytreeis“ABECDFGHIJ”andinorderlistofthebinarytreeis“EBCDAFHIGJ”.PostordertraversalsequenceofthebinarytreeisEDCBIHJGFA.
7．Thereare（n+1）/2leafnodesinafullbinarytreewithnnodes.
8．Whentheinputhasbeensorted,therunningtimeofinsertionsort（Big-Oh）isO（n）.
9．Wesortthesequence（43，02，80，48，26，57，15，73，21，24，66）withshellsortforincrement3,theresultis______（1502212426574366804873）_.
10、Inacircularqueue,“front”and“rear”arethefrontpointerandrearpointerrespectively.Queuesizeis“maxsize”.Wheninsertanelementinthequeue,rear=__（rear+1）%maxsize__
11.A_________________B树_____________________isanexampleofasearchtreewhichismultiway（allowsmorethantwochildren）.
12.Atreeinwhicheverynodeisnosmallerthanitschildrenistermed_____大顶堆______.
IIIApplicationofAlgorithms（35points）
GshowninFig2isadirectedgraph,pleasedescribeGwithadjacencymatrixandwritetheordersofbreadthfirsttraversalanddepthfirsttraversal.
ABCDE
A01010
B00110
C00001
D00001
E00000
Dft:
ABCED
Bft:
ABDCE
2．Thesequenceofinputkeysisshownbelow:
19，1，23，14，55，20，84，27，68，11，10，17
Afixedtablesizeof19andahashfunctionH（key）=key%13，withlinearprobing（线性探测）,fillthetablebelowandcomputetheaveragelengthofsuccessfulsearch.
3.Showtheresultsofinserting53,17,78,09,45,65,87each,oneatatime,inainitiallyemptymaxheap（大根堆）
4.writethesequenceofpreorder,postordertraversalsandaddinorderthreadsinthetree.
Fig.3
5.BuildaHuffmantreeanddetermineHuffmancodewhentheprobabilitydistribution（概率分布）overthe8alphabets（c1,c2,c3,c4,c5,c6,c7,c8）is,,,,,,,
6.GraphGshowninFig4isadirectedgraph,pleasedescribeGwithadjacencylistandwritetopologicalordering.
Fig.4
IVFillinblankofalgorithms.（15）
1．HereissinglesourceshortestpathalgorithmDijkstra.Fillinblankofthealgorithm.
classGraph{#include
Usingnamespacestd;
intmatching（string&exp）{
Writeefficientfunctions（andgivetheirBig-Ohrunningtimes）thattakeapointertoabinarytreerootTandcompute:
–ThenumberofleavesofT
typedefstructBiTNode
{TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
amethodcalledmaximumDegreeofanundirectedhgraphthatreturnsthemaximumdegreeofanyvertexinthegraph.Thegraphisstoredwithadjacencymatrix.Writethedefinitionofthegraph.implementthefunction.Analyzespacecomplexityandtimecomplexityofyourfunction.
3.Writeafunctionwithlinkedlistthatinsertsanumberintoasortedlinkedlist.Firstly,youshouldwriteafunctioncreatesalistthatlikethis:
L={3,5,8,12,32,48}
andtheninsert25intothislist.
答案解析0-0，仅供参考，若有不同意见请联系☆_☆
选择题：
1-5:
ACBDB6-11:
CBBDDE
1、知识点：
复杂度分析，必考
思路：
复杂度主要计算算法的步数，可以看出，当前循环执行的步数与i的值是相等的，所以可列1+2+..+i=（5*n*n+2），复杂度的计算忽略常数,（1+i）*i/2=（5*n*n+2）,i~O（n）
2、知识点：
non-linear与linear的区别
3、知识点：
复杂度分析+线性序列
思路：
很显然，当元素在sequencelist的末尾的时候，removing元素复杂度最高O（n）
4、知识点：
循环队列（circularqueue），重点
思路：
主要区分循环队列判断空与满的条件。
主要有三个方法
count计数，判断当前队列的元素与maxsize的大小
vis标志，比如可以一开始设vis=0,满时设置vis=1
就是题目中说的gap（....重点）
front代表头指针,rear代表尾指针
循环队列空时：
front==rear;满时：
front==（rear+1）%maxsize
5、知识点：
递归的定义,terminationmissing，终止条件缺失则可能无限调用。
6、知识点：
完全二叉树（completebinarytree）与满二叉树（fullbinarytree）的区别
思路：
学院PPT上有如下定义
depthofanode:
numberofancestors
heightofatree:
maximumdepthofanynode
并且有结点计算公式：
2h+1-1（其中h为树的高度，与某XXXX定义树的高度不一样，且照学院教材来做==）
所以ans:
24+1-1=31
7、知识点：
查找
思路：
有疑问的题...
单纯来说二分查找（binarysearch）的速度O（logN）是比较快的，可是题目仅仅要求Searchinginanunsortedlist,只进行一次查找，那我们用二分还要先进行排序O（NlogN）+O（logN）的复杂度是不如选项b的。
sentinel（哨兵...）的概念可见ppt讲插入排序的地方，貌似能加快查找速度吧...
8、知识点：
图的邻接矩阵存储
思路：
注意题目所问，无向图（undirectedgraph）,每条边都是要存储两遍的
9、知识点：
哈夫曼树（Huffmantree）
思路：
离散上学过的。
。
。
weightedpathlength=
所以ans=9*1+7*2+5*3+2*3=44（自己构造哈夫曼树》。
《）
10、知识点：
Dijkstra/最短路,重点
11、知识点：
快排,重点
10、11两题是重点，限文字难于描述清楚，请自主学习%>_<%
注意10题在priority_queue里进行更新时一开始肯定加入s、y结点，而后x结点会因为松弛操作从而距离变为1+3=4<5（t结点），所以x结点会比t结点先压入队列。
2、填空题
1、O（n2）
2、6数组元素存储地址的计算。
注意题目中规定存储下三角矩阵lowertriangleonly
3、location在稀疏矩阵中sparsematrix，如果对每个元素都进行存储的话空间复杂度为O（N2），因为好多位置没有值所以这会造成空间的极大浪费。
可以用题目所说的，只存储有值元素的值与位置（即i,j下标）。
4、stack栈（stack）与队列（queue）的区别，重点
5、题目有问题。
正确问法应该是这样：
T（n）=2T（n/2）+cn,T（n）=O（____logn_____）
T（n）=T（n-1）+cn,T（n）=O（_____n______）
时间复杂度计算。
对题目有点疑问，故此题答案不确定。
（不清楚这是按递归还递推进行计算得出，还有cn中的n是下标还cn相乘。
）
对于T（n）=2T（n/2）+cn，可以这样想，每次计算T（n）都会转化为2*T（n/2）+cn,对于T（n/2）又会转化为T（n/4）的计算，如此计算下去，其实就是按2的指数次幂的程度在递减。
可以自己举个例子，比如计算T（16），那计算过程为T（16）->T（8）->T（4）->T
（2）->T
（1）,所以计算次数为log16=4,类似T（n）=T（n-1）+cn的复杂度可以计算。
6、树的前、中、后序遍历，重点
首先要明白前、中、后序遍历是根据根的位置决定的，比如前序遍历就是（根左右），中序遍历为（左根右）....
首先你得能很熟练的写出一棵树的前、中、后序遍历（preorder、inorder、postorder），然后可以进行一下分析，对于前序遍历ABECDFGHIJ，中序遍历EBCDAFHIGJ，由前序遍历可知根结点肯定为A，那么从中序遍历里面可以以A为中点进行分割，左边的部分必定属于左子树，右边的部分肯定属于右子树，然后进行一步步分割，自己多尝试一下就ok了
构造树如下：
所以后序遍历为:
EDCBIHJGFA
ps:
已知前序遍历和后序遍历，不能确定唯一的中序遍历
7、n/2+1
满二叉树,设叶子层leafnode为第p层，则非叶子结点20+21+22+...+2p-1=2p-1
叶子结点：
2p
若总结点为n,那叶子结点为n/2+1
ps:
有好多种答案，比如（n+1）/2,n/2取下界等。
8、O（N）
关于插入排序，最好的情况就是序列已经有序，那就少去了比较的步数，直接进行n个元素的插入，故复杂度为O（N）
9、1502212426574366804873
希尔排序。
每个数与增量处进行大小比较若大于则交换。
10、（rear+1）%maxsize
前面讲过
11、B树
B树相对来说复杂一点，只会这样考了。
。
==
12、大顶堆
大顶堆的定义，如题目所说
3、算法应用题
1、
邻接矩阵为：
ABCDE
A01010
B00110
C00001
D00001
E00000
dfs序列:
ABCED
bfs序列:
ABDCE
考点、重点：
图的存储及dfs、bfs序列。
区分dfs与bfs，dfs为走子结点走到不能走为止，bfs为要先走遍所有的邻居结点。
2、考点：
hash
hash序列如下
averagelengthsearch=（1+1+1+2+3+1+3+4+3+1+3+6）/12=29/12次
（ps:
hash这一章我们班还没有学,答案仅是靠自己感觉写的,当某链只有一个元素时查询长度为1==）
3、考点：
大根堆的构造
4、考点：
前、中、后序遍历+线索树
5、考点：
哈夫曼树
构造树如下：
6、考点：
拓扑排序
邻接表如下：
邻接表形式如上，构造拓扑序列的算法请自行看书，
主要是对入度为0的结点进行压队列（或栈）
一个可能的答案为：
123456789
V、编程题
以下所有代码均为大致思路代码，细节请忽略（~~~）
1、计算叶子结点数
2、求无向图最大度数结点
3、裸链表随便写写。
。
升级会员 