1、baidu文库20091 .为处置核算机与打印机之间速度不匹配的疑问，一般设置一个打印数据缓冲区，主机即将输出的数据顺次写入该缓冲区，而打印机则顺次从该缓冲区中取出数据。该缓冲区的逻辑规划大约是a.栈b.行列c.树d.图2 .设栈s和行列q的初始状况均为空，元素abcdefg顺次进入栈s。若每个元素出栈后当即进入行列q,且7个元素出队的次序是bdcfeag,则栈s的容量至少是a.1/3 .给定二叉树图所示。设n代表二叉树的根，l代表根结点的左子树，r代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方法是/a.lrn4.下列二叉排序树中，满足平衡二叉树界说的是5
2、.已知一棵完全二叉树的第6层（设卞g为第1层）有8个叶结点，则完全二叉树的结点个数最多是a.396 .将森林变换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在正本的森林中，u和v可以具有的联络是i.父子联络ii.兄弟联络的父结点与v的父结点是兄弟联络a.只需ii和ii和iii、ii和iii7 .下列关于无向连通图特性的叙说中，正确的是i一切极点的度之和为偶数ii.边数大于极点个数减1iii.至稀有一个极点的度为1a.只需ib.只需ii和ii和iii/8 .下列叙说中，不契合m阶b树界说需求的是/a.根节点最多有m棵子树b.一切叶结点都在同一层上c.各结点内要害词均升序或降序
3、摆放d.叶结点之间经过指针联接9 .已知要害序列5,8,12,19,28,20,15,22是小根堆（最小堆）,刺进要害词3,调整后得到的小根堆是/a.3,5,12,8,28,20,15,22,19/,5,12,19,20,15,22,8,28/c.3,8,12,5,20,15,22,28,19,12,5,8,28,20,15,22,19/10 .若数据元素序列11,12,13,7,8,9,23,4,5是选用下列排序办法之一得到的第二趟排序后的成果，则该排序算法只能是a.起泡排序b.刺进排序c.选择排序d.二路归并排序41. （10分）带权图（权值非负，标明边联接的南北极点间的间隔）的最短途径疑问
4、是找出从初始极点到方针极点之间的一条最短途径。假定从初始极点到方针极点之间存在途径，现有一种处置该疑问的办法:设最短途径初始时仅包括初始极点，令其时极点u为初始极点；选择离u迩来且没有在最短途径中的一个极点v,参加到最短途径中，修合理时极点u=v;重复进程，直到u是方针极点时中止。请问上述办法能否求得最短途径？若该办法可行，请证明之；否则，请举例阐明。42. （15分）已知一个带有表头结点的单链表，结点规划为datalink假定该链表只2&出了头指针list。在不改动链表的条件下，请方案一个尽可以高效的算法，查找链表中倒数第k个方位上的结点（k为正整数）。;若查找成功，算法输出该结点的
5、data值，并回来1;否则，只回来0。需求:（1）描绘算法的根柢方案思维（2）描绘算法的具体完成进程（3）根据方案思维和完成进程，选用程序方案言语描绘算法（运用c或c+或java言语完成），要害之处请给出扼要注释。20101、若元素a,b,c,d,e,f顺次进栈，答应进栈、退栈操作替换进行。但不答应接连三次进行退栈作业，则不可以能得到的出栈序列是（）a:dcebfab:cbdaefc:dbcaefd:afedcb2、某行列答应在其两端进行入队操作，但仅答应在一端进行出队操作，则不可以能得到的次序是（）a:bacdeb:dbacec:dbcaed:ecbad3、下列条理二叉树中（用虚线标明条理），符
6、合后序条理树界说的是（）4、鄙人列所示的平衡二叉树中刺进要害词，48后得到一棵新平衡二叉树，在新平衡二叉树中，要害词37地址结点的左、，右子结点中保存的要害词别离是（）a:13,48b:24,48c:24,53d:24,905、在一棵度为4的树t中，若有20个度为4的结点，10个度为3的结点,1个度为2的结点，/10个度为1的结点，则树t的叶节点个数是（）a:41b:82c:113d:1226、对n（n大于等于2）个权值均纷歧样的字符构成哈夫曼树，关于该树的叙说中，差错的是（）a:该树必定是一棵完全二叉树b:树中必定没有吨蔼1的结点c:树中两个权值最小的结点必定是兄弟结点d:树中任一非叶结点的
7、权值必定不小于下一任一结点的权值7、若无向图g-（）中含7个极点，则保证图g在任何情况下都是连通的，则需要的边数最少是（）a:6b:15c:16d:218、对下图进行拓补排序，可以得到不一样的拓补序列的个数是（）eda-cxf_*vjfbba:4b:3c:2d:19、已知一个长度为16的次序表l,其元素按要害词有序摆放，若选用减半查找法查找一个不存在的元素，则比照次数最多是（）a:4b:5c:6d:710、选用递归方法对次序表进行快速排序，下列关于递归次数的叙说中，正确的是（、）a:递归次数与初始数据的摆放次序无关b:每次区别后，先处置较长的分区可以削减递归次数c:每次区别后，先处置较短的分区可
8、以削减递归次数d:递归次数与每次区别后得到的分区处置次序无关11、对一组数据（2,12,16,88,5,10）进行排序，若前三趟排序成果如下（）/第一趟:2,12,16-5,10,88/第二趟:2,12,5,10,<16,88/第三趟:2,5,10,12,16,88则选用的排序办法可所以:a:起泡排序b:希尔排序c:归并排序d:基数排序41.(10分)将要害词序列(7、8、11、18、9、14)散列存储到散列列表中，散列表的存储空间是一个下标从0初步的一个一维数组散列函数维:h(key)=(keyx3)modt,处置冲突选用线性勘探再散列法，需求装填(载)因子为疑问:(1)请画出所规划的
9、散列表；、(2)别离核算等概率情况下，查找成功和查找不成功的均匀查找长度。42.(13分)设将n(n,1)个整数存放到一维数组r中，试方案一个在时刻和空间两方面尽可以有用的算法，将r中保有的序列循环左移p(0<p<n)个方位，即将r中的数据由(x0x1xr-1)改换为(xpxp+1xn-1x0x1xp-1)需求:(1)给出算法的根柢方案思维。(2)根据方案思维，选用c或c+或java言语表述算法要害之处给出注释。(3)阐明你所计合算法的时刻凌乱度和空间凌乱度20111.设n是描绘疑问规划的非负整数，下面程序片段的时刻凌乱度是二x=2;while(x<n/2)x=2*x;(lo
10、g2n)(n)(nlog2n)(n2)2 .元素a,b,c,d,e顺次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到一切元素都出栈，则在一切可以的出栈序列中，以元素d最初的序列个数是3 .已知循环行列存储在一维数组a0.n-1中，且行列非空时front和rear别离指向队头元素和队尾元素。若初始时行列为空，且需求第1个进入行列的元素存储在a0处，则初始时front和rear的值别离是,0,n-1,0,n-14 .若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是5.若一棵二叉树的前序遍历序列和后序遍历序列别离为1,2,3,4和4,3,2,1,则该二叉树的中序遍历序列不会是,2,3
11、,4,3,4,1,2,4,1,3,2,16 .已知一棵有2011个结点的树，其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是7 .关于下列要害词序列，不可以能构成某二叉排序树中一条查找途径的序列是,22,91,24,94,71,20,91,34,88,35,89,77,29,36,38,25,71,68,33,348 .下列关于图的叙说中，正确的是i .回路是简略途径/ii .存储稀少图，用邻接矩阵比邻接表更省空间/iii .若有向图中存在拓扑序列，则该图不存在回路a.仅iib.仅i、iic.仅iiid.仅i、iiiiv 为前进散列(hash)表的查找功率，可以采纳的正确办法是1 .
12、增大装填(载)因子、/11 .方案冲突(磕碰)少的散列函数111 .处置冲突(磕碰)时避免发生集合(堆积)表象a.仅ib.仅iic.仅i、iid.仅ii、iii112 为完成快速排序算法，待排序序列宜选用的存储方法是a.次序存储b.散列存储c.链式存储d.索引存储113 已知序列25,13,10,12,9是大根堆，在序列尾部刺进新元素18,将其再调整为大根堆，调整进程中元素之间进行的比照次数是41 .(8分)已知有6个极点(极点编号为05)的有向带权图g,其邻接矩阵a为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。480000g50088aqoco3j需求:(1)写出图g的邻接矩阵a
13、o(2)画出有向带权图g(3)求图g的要害途径，并核算该要害途径的长度。42 .(15分)一个长度为l(l>1)的升序序列s,处在第el/2cl个方位的数称为s的中位数。例如，若序列s1=(11,13,15,17,19),则s1的中位数是15。两个序列的中位数是含它们一切元素的升序序列的中位数。例如，若s2=(2,4,6,8,20),则s1和s2的中位数是11。现有两个等长升序序列a和b,试方案一个在时刻和空间两方面都尽可以高效的算法，找出两个序列a和b的中位数。需求:(1)给出算法的根柢方案思维。(2)根据方案思维，选用c或c+域java言语描绘算法，要害之处给出注释。(3)阐明你所设
14、核算法的时刻凌乱度和空间凌乱度。20121、求整数n(n>0)阶乘的算法如下，其时刻凌乱度是()intfact(intn)if(n<=1)return1;returnn*fact(n-1);(log2n)(n)c.(nlog2n)(n2)2、已知操作符包括+、、(和)。将中缀表达式a+b-a*(c+d)/e-f)+g变换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能断定运算次序的操作符，若栈初始时为空，则变换进程中一起保存栈中的操作符的最大个数是()3、若一颗二叉树的前序遍历序列为a,e,b,d&
15、#163;后续遍历序列为b,c,d,e,q则根节点的孩子节点()a.只需eb.有e、bc.有e、cd.无法断定4、若平衡二叉树的高度为6,且一切非叶节点的平衡因子均为1,则该平衡二叉树的节点总数为()5、对有n个节点、e条边且运用邻接表存储的有向图进行广度优先遍历，其算法时刻凌乱度()（n）（e）（n+e）（n*e）6、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的规划是（）a.存在，且仅有b.存在，且不只有c.存在，可以不只有d.无法断定是不是存在7、如下有向带权图，若选用迪杰斯特拉（dijkstra）算法求源点a到其他各极点的最短途径，得到的第一条最短途径的方针
16、极点是b,第二条最短途径的方针极点是c,后续得到的其他各最短品&径的方针极点顺次是（）,e,f,d,f,d,e,e,d8、下列关于最小生成树的说法中，正确的是（）i、最小生成树的价值仅有n一切权值最小的边必定会呈如今一切的最小生成树中田、运用普里姆（prim）算法从不一样极点初步得到的最小生成树必定相同iv、运用普里姆算法和克鲁斯卡尔（kruskal）算法得到的最小生成树总纷歧样a.仅ib.仅hc.仅i、md.仅h、iv9、已知一棵3阶b-树，如下图所示。删去要害词78得到一棵新b-树，其最右叶结点中的要害词是（）1c21374762,62,6510、在内部排序进程中，对没有断定究竟方位
17、的一切元素进行一遍处置称为一趟排序。下列排序办法中，每一趟排序结束都至少可以断定一个元素究竟方位的办法是（）i.简略选择排序l希尔排序田.快速排序/iv.堆排序v.二路归并排序/a.仅i、m、ivb.仅i、m、v/c.仅h、m、ivd.仅出、iv、v/11.对一待排序序列别离进行减半刺进排序和直接刺进排序，两者之间可以的不一样之处是（）a.排序的总趟数b.元素的移动次数c.运用辅佐空间的数量d.元素之间的比照次数二、问答题。41、(10分)设有6个有序表a、b、c、d、e、f,别离富含10、35、40、50、60和200个数据元素，各表中元素按升序摆放。需求经过5次两两兼并，将6个表究竟兼并成1
18、个升序表，并在最坏情况下比照的总次数抵达最小。请答复下列疑问。(1)给出无缺的兼并进程，并求出最坏情况下比照的总次数。(2)根据你的兼并进程，描绘n(n>2)个不等长升序表的兼并战略，并阐明理由。42、(13分)假定选用带头结点的单链表保存单词，当两个单词有相同的后时缀，则可同享相同的后缀存储空间，例如，"loaging"、和“being"，如下图所示。strl、对r2:i|-一tp|-ag*wehu设str1和str2别离指向两个单词地址单链表的头结点，链表结点规划为(data,next,请方案一个时刻上尽可以高效的算法，找出由stu和str2所指向两个链
19、表一起后缀的开始方位(如图中字符i地址结点的方位p)o需求:(1)给出算法的根柢方案思维。(2)根据方案思维，选用c或c+或java言语描绘算法要害之处给出注释。(3)阐明你所计合算法的时凌乱度。20131 .已知两个长度别离为m和n的升序链表，若将它们兼并为一个长度为m+n的降序链表，则最坏情况下的时刻凌乱度是a.o(n)b.o(m*n)c.o(min(m,n)d.o(max(m,n)2>一个栈的入栈序列为1,2,3,n,其出栈序列是p1,p2,p3,pn=若p2=3,则p3可以取值的个数是:/a.n-3b.n-2c.n-1d.无法断定/3.若将要害词1,2,3,4,5,6,7顺次刺进
20、到初始为空的平衡二叉树t中，则t中平衡因子为0的分支结点的个数是/a.0b.1c.2d.34 .已知三叉树t中6个叶结点的权别离是2,3,4,5,6,7,t的带权(外部)途径长度最小是a.27b.46c.54d.565 .若x是后序条理二叉树中的叶结点，且x存在左兄弟结点y,则x的右条理指向的是a.x的父结点b.以y为根的子树的最左下结点c.x的左兄弟结点yd.以y为根的子树的最右下结点6.在任意一棵非空二叉排序树t1中，删去某结点v之后构成二叉排序树t2,再将v刺进t2构成二叉排序树t3。下列关于t1与t3的叙说中，正确的是i .若v是t1的叶结点，则t1与t3不一样ii .若v是t
21、1的叶结点，则t1与t3相同iii .若v不是t1的叶结点，则t1与t3不一样iv .若v不是t1的叶结点，则t1与t3相同a.仅卜iiib.仅卜ivc.仅ii、iii、d.仅ii、iv7.设图的邻接矩阵，a如下所示。各极点的度顺次是-01or0011a=01001000a.1,2,1,2b.2,2,1,1c.3,4,2,3d.4,4,2,28.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是a.h,c,a,b,d,e,g,fb.e,a,f,g,b,h,c,dc.d,b,c,a,h,e,f,gd.a,b,c,d,h,e,f,g9、下列的aoe网标明一项包括8个活动的工程。经过一起加
22、快若干活动的发展可以缩短整个工程的工期。下列选项中，加速其发展就可以缩短整个工程的工期的是:ac和ebd和ecf和ddf和h10、在一棵高为2的5阶b树中，所含要害词的个数最少是a5b7c8d144l(13分)已知不整数序列=(%吗jlln.j,其间。置。海:若存在4i-口/14此啮r则和3一为a的主沅素、例如=a=(0,5,5,3,5,7,5,5),侧5为主元素；又如a=(0,5,5,3,5,1,5,7),则a中没有主元素。假定a中的n个元素保存在一个一维数组中，请计一个尽可以高效的算法，找出a的主元素。若存在主元素，则输出该元素；
23、否则输出-1。需求:(1)给出算法的根柢方案思维。(2)根据方案思维，选用c或c+或java言语描绘算法，要害之处给出释。(3)阐明你所计合算法的时刻凌乱度和空间凌乱度。42.(10分)4个元素的s="do","for","repeat""while",各元素查找概率顺次为:p1=,p2=,p3=0.15,p4=。将s保存在一个长度为4的次序表中，选用减半查找法，查找成功时的均匀查找长度为。请答复:(1)若选用次序存储规划保存s,且需求均匀查找长度更短，则元素应如何摆放？应运用何种查找办法？查找成功时的均匀查找长度
24、是多少？(2)若选用链式存储规划保存s,且需求均匀查找长度更短，则元素应如何摆放？应运用何种查找办法？查找成功时的均匀查找长度是多少？20141 .下列程常段的时刻凌乱度是count=0;*for(k=1;k<=n;k=2)for(j=1;j<=n;j+1)count+;(log2n)(n)(nlog2n)(n2)2.假定栈初始为空，将中缀表达式a/bcdef/g变换为等价后缀表达式的进程中，当扫描到f时，栈中的元素顺次是a.b.c./d./3 .循环两列放在一维数组a0m-1中，end1指向队头元素，end2指向队尾元素的后一个方位。假定行列两端均可进行入队和出队操作，行列中最多
25、能包容m-1个元素。初始时为空，下列判别队空和队满的条件中，正确的是/a.队空:end1=end2;队满:end1=(end2+1)modmb.队空:end1=end2;队满:end2=(end1+1)mod(m-1)c.队空:end2=(end1+1)modm;队满:end1=(end2+1)modmd.队空:end1=(end2+1)modm;队满:end2=(end1+1)mod(m-1)4 .若对如下的二叉树进行中序条理化，则结点/x的左、右条理指向的结点别离是,c,a,c,a115.将森林f变换为对应的二叉树 中叶结点的个数t, f中叶结点的个数等于中吨蔼1的结点个数中左孩子指针为空
26、的结点个数中右孩子指针为空的结点个数6.5个字符有如下4种编码方案，不是前缀编码的是,0000,0001,001,1,000,001,010,1,1,2,4,5,6,001,010,011,100,001,010,011,1007.对如下所示的有向图进行拓扑排序，得到的拓扑序列可所以8j,用哈希（散列）办法处置冲突（磕碰）时可以呈现堆积（集合）表象,卜列选项中，会受堆积表象直接影响的是a.存储功率b.数列函数c.装填（装载）因子d.均匀查找长度9 .在一棵具有15个要害词的4阶b树中，含要害词的结点数最多是10 .用希尔排序办法对一个数据序列进行排序时，若第1趟排序成果为9,1,4,13,7,
27、8,20,23,15则该趟排序选用的增量（间隔）可所以11 .下列选项中，不可以能是快速排序第2趟排序成果的是,3,5,4,6,7,9,7,5,6,4,3,9,2,5,4,7,6,9,2,3,5,7,6,941.（13分）二叉树的带权途径长度（wpl）是二叉树中一切叶结点的带权途径长度之和，给定一棵二叉树t,选用二叉链表存储，节点规划为:leftweightright其间叶节点的weight域保存该结点的非负权值。设root为指向t的根节点的指针，方案求t的wpl的算法。需求:(1)给出算法的根柢方案思维；(2)运用c或c+言语，给出二叉树结点的数据类型界说；(3)根据方案思维，选用c或c+言语
28、描绘算法，要害之处给出注释。20151 .已知程序如下:ints(intn)return(n<=0)?0:s(n-1)+n;voidmain()cout<<s(1);程序运转时运用栈来保存调用进程的信息,自栈底到栈顶保存的信息一次对应的是1 .main()->s(1)->s(0)b.s(0)->s(1)->main()c.main()->s(0)->s(1)d.s(1)->s(0)->main()2 .先序序列为a,b,c,d的不一样二叉树的个数是a.13b.14c15d.163 .下列选项给出的是从根别离抵达两个叶节点途径上的权
29、值序列能归于同一棵哈夫曼树的是a.24,10,5和24,10,7b.24,10,5和2412,7c.24,1q10和24,14,11d24,10,5和24,14,64 .如今有一颗无重复要害词的平衡二叉树avl树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙说中，正确的是a.根节点的度必定为2b.树中最小元素必定是叶节点c.最终刺进的元素必定是叶节点d,树中最大元素必定是无左子树5 .设有向图g=(v,e),顶除v=v0,v1,v2,v3，边集e=<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>,若从极点v0初步对
30、图进行深度优先遍历，则可以得到的不一样遍历序列个数是a.2b.3c.4d.56.求下面带权图的最小(价值)生成树时，可所以克鲁斯卡(kruskad算法第次选中但不是普里姆(prim)算法(从v4初步)第2次选中的边是a.(v1,v3)b.(v1,v4)c.(v2,v3)d.(v3,v4)7 .下列选项中，不能构成减半查找中要害词比照序列的是a.500,200,450,180b500,450,200,180c.180,500,200,450d.180,200,500,4508 .已知字符串s为"abaabaabacacaabaabc忒比t为"abaab冰川kmp算进行匹配，第
31、一次呈现失配"(si=ti)时，i=j=5,则下次初步匹配时,i和j的值分另a.i=1,j=0b.i=5,j=0c.i=5,j=2d.i=6,j=29 .下列排序算法中元素的移动次数和要害词的初始摆放次序无关的是a.直接刺进排序b.起泡排序c,基数排序d.快速排序10.已知/讨艮堆为8, 15, 10, 21, 进程中，要害词之间的比照数是34, 16, 12,删去要害词8之后需重建堆,18a.1b.2c.3d.411.希尔排序的组内排序选用的是()a.直接刺进排序b,减半刺进排序c.快速排序d.归并排序41 .用单链表保存m个整数，节点的规划为(data,link),且|data|
32、<n(m正整数)。州需求方案一个时刻凌乱度尽可以高效地算法，关于链表中必定值相等的节点，仅保存一次呈现的节点而删去其他必定值相等的节点。例如若给定的单链或head如下head删去节点后的head为head需求:(1)给出算法的根柢思维运用c或c+=2)个极点的邻接矩
33、阵为b则，bm(2<=m<=n)非零元素的意义是啥？20091-5:bcdbc6-10:badba41该办法求得的途径不必定是最 短途径。例如，关于下图所示的带权 图，假定依照题中的原则，从 a至u c 的最短途径为a 一b一c,实际上其最 短途径为a> d c。从4到口的最10途径为a-jc+事宴上其最混路行为ka*u-+c(a210d)y/.342. (1)算法的根柢方案思维:界说两个指针变量p和q,初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针初步与p指针同步移动；当p指针移动到链表最终一个结点时，q指针所指元素为倒数第k个结点。
34、以上进程对链表仅进行一遍扫描。(2)算法的具体完成进程:count=0,p和q指向链表表头结点的下一个结点；若p为空，转；若count等于k,则q指向下一个结点；否则,count=count+1;/*计数器赋初值*/p=q=list
35、->link;/*p和q指向链表表头结点的下一个结点*/while(p!=null)/if(count<k)count+;/*计数器+1*/elseq=q->link;/*q移到下一个结点*/p=p->link;/*p移到下一个结点*/if(count<k)return(0);/*假定链表的长度小于k,查找失利*/elseprintf("%d”,q->data);/*查找成功*/return(1);1)规划的散列表如下下标01i23456789要害词7-1481130189(2)查找成功的均匀查找长度:asl成功=12/7。查找不成功的均匀查找长度
36、:asl不成功=18/7。42.(1)给出算法的根柢方案思维:先将n个数据x0x1-xp-xn-1原地逆置,得到xn-1xpxp-1)。,然后再将前n-p个和后p个元素别离原地逆置，得到最结束果:xpxp+1xn-1x0x1xp-1。(2)算法完成:
voidreverse(intr口,intleft,intright)intk=left,j=right,temp;分笔记图最终一题42.(1)算法的根柢方案思维:(5分)1)比照笨的办法:将两升序序列归并排序，然后求其间位数，时刻凌乱度是o(n),空间凌乱度o(n)。2)高效的办法:别离求两个升序序列a和b的中位数，设为a和b。假定a=b,则a或
37、者b即为所求的中位数。缘由:假定将两序列归并排序，则究竟序列中，排在子序列ab前边的元素为早年两序列中排在a和b前边的元素；排在子序列ab后边的元素为早年两序列a和b后边的元素。所以子序列ab必定位于究竟序列的中心，有因为a=b,显着a就是中位数。%假定awb贸设a<p>缘由:相同可以用归并排序后的序列来验证，归并后排序后必定有形如a.b的序列呈现，中位数必定呈如今(a,b)规模内。因而可以做如下处置:扔掉a地址序列a之中比照小的一半，一起扔掉b地址序列b之中比照大的一半。一在保存的两个升序序列中求出新的中位数a和b,重复上述进程，直到两个序列只含一个元素中止，则较小者即为所求中位
38、数。(2)算法完成(高效办法):(8分)/intsearch(inta,intb口，intn)ints1,e1,mid1,s2,e2,mid2;s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(amid1=bmid2)returnamid1;if(amid1<p)1)算法思维:次序遍历两个链表到尾结点时，并不能保证两个链表一起抵达尾结点。这是因为两个链表的长度不一样。假定一个链表比另一个链表长k个结点，咱们先在长链表上遍历k个结点，之后同步遍历两个链表。这样咱们就可以保证它们一起抵达最终
39、一个结点了。因为两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们必定一起抵达第一个公共结点。所以得到算法思路:遍历两个链表求的它们的长度l1,l2;比照l1,l2,找出较长的链表，并求l=|l1-l2|;先遍历长链表的l各结点；同步遍历两个链表，直至找到相同结点或链表结束。(2)算法的c言语代码描绘linklistsearch_first_common(linklistl1,linklistl2)1)给出算法的根柢方案思维:依分)算法的战略是早年向后扫描数组元素，符号出一个可以变成主元素的元素num=然后从头计数，招认num是不是是主元素。算法可分为以下两步:选择候选的主元素:顺次扫描
40、所给数组中的每个整数，将第一个遇到的整数num保存ijc中记载num的呈现次数为1;若遇到的j个整数仍等于num则计数加一，否则计数减一；当计数减到0时，将遇到的下一个整数保存至匕中，计数从头记为1,初步新一轮计数，即从其时方位初步重复上述进程，直到扫描完悉数数组元素。判别c中元素是不是是真实的主元素:再次扫描该数组，统诂中元素呈现的次数，若大于n/2,则为主元素；否则，序列中不存在主元素。(2)算法完成:(7分)intmajority(inta,intn)inti,c,count=1;/cw来保存候选主元素，count用来计数c=a0;/设置a0为候选主元素for(i=1;i<n;i+)
41、/查找候选主元素if(ai=c)count+;/1a中的候选主元素计数elseif(count>0)count-;/处置不是候选主元素的情况else/替换候选主元素，从头计数c=ai；count=1;1)选用次序存储规划，数据元素按其查找概率降序摆放。2分)选用次序查找办法。(1分)查找成功时的均匀查找长度=x1+x2+x3+x4=0(2分)7(2)【答案一】选用链式存储规划,数据元素按其查找概率降序摆放构成单链表。(2分)选用次序查找办法。(1分)查找成功时的均匀查找长庚x1+x2+x3+x4=o（2分）【答案二】剌二叉链表存储详尽柔软规划二叉排序树，元素存储方法见下图。（2分）20141
42、-5:cbadc6-11:ddddbc41.答复:查询二叉树的带权途径长度，二叉树的带权途径长度为每个叶子结点的深度与权值之积的总和,可以运用先序遍历或层次遍历处置疑问。1）算法的根柢方案思维:根据先序递归遍历的算法思维是用一个static变量记载wpl,把每个结点的深度作为递归函数的一个参数传递，算法进程如下:若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一；最终回来核算出的wpl即可。根据层次遍历的算法思维是运用行列进行层次遍历，并记载其时的层数
43、，当遍历到叶子结点时，累计wpl;当遍历到非叶子结点时对该结点的把该结点的子树参加行列；当某结点为该层的最终一个结点时，层数自增1;行列空时遍历结束，回来wpl2）二叉树结点的数据类型界说如下:typedefstructbitnodeintweight;structbitnode*lchild,*rchild;bitnode,*bitree;3）算法代码如下:根据先序遍历的算法:intwpl（bitreeroot）returnwpl_preorder（root,0）;1）算法思维:界说一个巨细为n的数组，初始化为0.在遍历链表的一起将数组中索引值为节点的值的必定值的元素肾.假定此元素现已为1,阐明此节点之前现已有与此节点的值的必定值相等的节点，需将此节点删去。（2）节点的数据规划界说如下:typedefstructnodeintdata;structnode*next;node;（3） intan;1）邻接矩阵为:(2) 0行3列的元素的意义是极点0到极点3的最短间隔为2.则表小i极点(3) bm中非零元素的意义是:假定此极点位于i行j列，假定i=j,到自个的间隔为0;假定i手j则标明极点i抵达不了极点j。