算法练习题

一、判断题1-1算法分析的两个主要方面是时间复杂度和空间复杂度的分析。(2分)TF1-2将NNN个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)O(logN)O(logN)。(3分)TF1-3通过对堆栈S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。输出的序列为：123。(3分)TF1-4所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(2分)TF1-5某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。(3分)TF1-6在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。(3分)TF1-7将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。(3分)TF1-8一棵有124个结点的完全二叉树，其叶结点个数是确定的。(3分)TF1-9用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。(3分)TF1-10如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。(3分)TF二、选择题2-1下列函数中，哪个函数具有最快的增长速度？(4分)A、N^2logNNB、N(logN)^4C、N^3D、NlogN^22-2给定N×NN\timesNN×N的二维数组A，则在不改变数组的前提下，查找最大元素的时间复杂度是：(4分)A、O(N^2)B、O(NlogNC、O(ND、O(N^2logN2-3给定程序时间复杂度的递推公式：T(1)=1T(1)=1T(1)=1，T(N)=2T(N/2)+NT(N)=2T(N/2)+NT(N)=2T(N/2)+N。则程序时间复杂度是：(4分)A、O(logN)B、O(N)C、O(NlogN)D、O(N^2)2-4设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：(4分)A、h=t;t-next=h-next;B、t-next=h-next;h=t;C、h=t;t-next=h;D、t-next=h;h=t;2-5若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？(4分)A、+(*+B、+(+C、++(+D、abcde2-6若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？(4分)A、2和0B、2和2C、2和4D、2和62-7三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？(4分)A、8B、10C、12D、132-8已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：(4分)A、ABCB、BACC、CBAD、CAB2-9在一个用数组表示的完全二叉树中，如果根结点下标为1，那么下标为17和19这两个结点的最近公共祖先结点在哪里（数组下标）？（注：两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点）(4分)A、8B、4C、2D、12-10将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：(4分)A、3B、5C、6D、92-11设一段文本中包含字符{a,b,c,d,e}，其出现频率相应为{3,2,5,1,1}。则经过哈夫曼编码后，文本所占字节数为：(4分)A、40B、36C、25D、122-12在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{1,-4,1,1,-3,4,4,8,-2}（注：−n-n−n表示树根且对应集合大小为nnn），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？(4分)A、1和-6B、4和-5C、8和-5D、8和-63-1下列代码的功能是从一个大顶堆H的某个指定位置p开始执行下滤。voidPercolateDown(intp,PriorityQueueH){intchild;ElementTypeTmp=H-Elements[p];for(;p*2=H-Size;p=child){child=p*2;if(child!=H-Size&&__________(6分))child++;if(H-Elements[child]Tmp)___________________(6分);elsebreak;}H-Elements[p]=Tmp;}3-2下列代码的功能是返回带头结点的单链表L的逆转链表。ListReverse(ListL){PositionOld_head,New_head,Temp;New_head=NULL;Old_head=L-Next;while(Old_head){Temp=Old_head-Next;______________(6分);New_head=Old_head;Old_head=Temp;}__________________(6分);returnL;}三、程序题给定KKK个整数组成的序列{N1N_1N1,N2N_2N2,...,NKN_KNK}，“连续子列”被定义为{NiN_iNi,Ni+1N_{i+1}Ni+1,...,NjN_jNj}，其中1≤i≤j≤K1\lei\lej\leK1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{-2,11,-4,13,-5,-2}，其连续子列{11,-4,13}有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：数据1：与样例等价，测试基本正确性；数据2：102个随机整数；数据3：103个随机整数；数据4：104个随机整数；数据5：105个随机整数；输入格式:输入第1行给出正整数KKK(≤100000\le100000≤100000)；第2行给出KKK个整数，其间以空格分隔。输出格式:在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。输入样例:6-211-413-5-2输出样例:20GivenasequenceofKintegers{N1,N2,...,NK}.Acontinuoussubsequenceisdefinedtobe{Ni,Ni+1,...,Nj}where1≤i≤j≤K.TheMaximumSubsequenceisthecontinuoussubsequencewhichhasthelargestsumofitselements.Forexample,givensequence{-2,11,-4,13,-5,-2},itsmaximumsubsequenceis{11,-4,13}withthelargestsumbeing20.Nowyouaresupposedtofindthelargestsum,togetherwiththefirstandthelastnumbersofthemaximumsubsequence.InputSpecification:Eachinputfilecontainsonetestcase.Eachcaseoccupiestwolines.ThefirstlinecontainsapositiveintegerK(≤10000\le10000≤10000).ThesecondlinecontainsKKKnumbers,separatedbyaspace.OutputSpecification:Foreachtestcase,outputinonelinethelargestsum,togetherwiththefirstandthelastnumbersofthemaximumsubsequence.Thenumbersmustbeseparatedbyonespace,buttheremustbenoextraspaceattheendofaline.Incasethatthemaximumsubsequenceisnotunique,outputtheonewiththesmallestindicesiandj(asshownbythesamplecase).IfalltheKnumbersarenegative,thenitsmaximumsumisdefinedtobe0,andyouaresupposedtooutputthefirstandthelastnumbersofthewholesequence.SampleInput:10-101234-5-2337-21SampleOutput:1014