02笔试题-数据结构部分

《02笔试题-数据结构部分》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构1•采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为OA)0(n2)B)O(nlog2n)C)O(log2n)D)O(n)2.下面程序的时间复杂度为()for(inti=0;i

2、空间中的位置不一定是连续的，fl.各元索的存储顺序也是任意的4.已知二义树后序遍历序列是edcfba,中序遍历序列deacbf,它的前序遍历序列是()；5.如果进栈序列为el,e2,e3,e4,则可能的出栈序列是();&对长度为n的字符串进行字符定位运算的时间复杂度为();A)O(l)B)0(根号n)C)O(nlog2n)A)O(n)7m个顶点的连通图中边得条数至少为()8•合并两个己经排好序的长度为n的Array,®坏情况下需要比较多少次()A)2nB)2n-1C)2n+1D)n29.深度为5的满二叉树屮，叶子结点的个数为()A)32B)31C)16D)1510•

3、冒泡排序算法和快速排序算法的吋间复杂度分別是什么？11•请简述数纟R和链表数据结构的特点及应用的场合?12•下列哪些数据结构最适合医疗仪器设备中的大型数据量的插入，查找()A)数组B)哈希表C)红黑树/二叉平衡树D)链表13.下列哪些排序算法的平均吋间复杂度是O(nlog2n)(),哪些是稳定的排序()A)冒泡排序B)希尔排序C)快速排序D)插入排序E)堆排序14•卞列哪些说法是正确的：()A）二分查找法在一个长度为1000的冇序整数数组查找一个整数，比较的次数不超过100次B）在二叉树屮查找元素的时间复杂度为O（log2n）；C）対单向链表，可以使用冒泡排序；D）对双向链表

4、,可以使用快速排序;15•已知某二叉树的后序遍历是DFBEGCA,屮序遍历的顺序是DBFACEG,其前序遍历顺序是16.下列代码将两个冇序链表结合为一个，链表中的元索的排列顺序为从小到大。请补充其中的空缺。structnodestructnode*pnext;intval;structnode*splice(structnode*plhs,structnode*prsh)returnprhs?prhs:plhs;structnode*phead,*plast;if()phead=plast=prhs;plhs=plhs->pnext;}elsephead=plast=plhs

5、;prhs=prhs->pnext;}while()if(plhs->valval)plast->pnext=plhs;plast=plhs;plhs=plhs->pnext;}elseplast->pnext=prhs;plast=prhs;}}plast->pnest=;return;}17.比较哈希表和平衡二叉树的特点，他们分别用在哪些场合.16.—个栈的入栈序列是A,B,C,D,E则栈的不可能的输出序列是()A)EDCBABJDECBAC)DCEABD)ABCDE17.在排序的方法屮，关键码比较次数与记录地初始排列无关的是()A)ShellB)归并排序C

6、)直接排序D)选择排序18.以卜仮向遍丿力array数组的方法有什么错误?vectorarray;array.push_back(l);array.push_back(2);array.push_back(3);for(vector::size_typei=array.size()-l;i>=O;-i){cout«array[i]«endl;}19.某火车站要通过一•条栈道(先进后出)來调换进入车站的列车顺序，若进站的列车顺序为A,B,C,则下列哪个出栈顺序不可能?A)ABCB)ACBC)CABD)CBA20.栈是一种是白能在某一端插入和删除的特殊线性表。他按照麻进先出的原则

7、存储数据,先进入的数据被压入栈底，最后进入的数据在栈顶，若6元素进入栈S的顺序为A.B.C.D.E.F出栈顺序为B.D.C.F.E.A,则S栈最小容量为？A）3B）4C）5D）624.若完全二叉树的结点个数为2的N次方则叶子结点个数为：A）N-1B）2*NC）2（N-1）次方D）2N次方24.排序算法是稳定是指：关键码相同的记录排序前后对应位直不发朱改变，卜面哪种排序算法是不稳定的？A）插入排序B）冒泡排序C）快速排序D）归并排序25.下列说法中错误的是：A）插入排序某些情况下复朵度为0（N）。B）排序