02笔-数据结构部分选读.docx

数据结构1.采用折半有哪些信誉好的足球投注网站算法长度为n的有序表时，元素的平均有哪些信誉好的足球投注网站长度为（）A)O(n2) B)O(nlog2n) C)O(log2n) D)O(n)2.下面程序的时间复杂度为（）for(int i=0;im;i++){for(int j=0;jn;j++){a[i][j] = i * j;}} A)O(m2); B)O(n2); C)O(m*n); D)O(m+n);3.下列叙述中，正确的是（）A)线性表中的个元素在存储空间中的位置必须是连续的B)线性表中的表头元素一定存储在其他元素的前面C)线性表中的个元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D)线性表中的个元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的4.已知二叉树后序遍历序列是edcfba，中序遍历序列deacbf，它的前序遍历序列是（）;5.如果进栈序列为 e1,e2,e3,e4 ，则可能的出栈序列是（）;6.对长度为n的字符串进行字符定位运算的时间复杂度为（）;A)O(1) B)O(根号n) C)O(nlog2n) D)O(n)7.n个顶点的连通图中边得条数至少为（）8.合并两个已经排好序的长度为n的Arrayint,最坏情况下需要比较多少次（）A)2n B)2n-1 C)2n+1 D)n29.深度为5的满二叉树中，叶子结点的个数为（）A)32 B)31 C)16 D)1510.冒泡排序算法和快速排序算法的时间复杂度分别是什么？11.请简述数组和链表数据结构的特点及应用的场合？12.下列哪些数据结构最适合医疗仪器设备中的大型数据量的插入，查找（）A)数组B)哈希表C)红黑树/二叉平衡树D)链表13.下列哪些排序算法的平均时间复杂度是O(nlog2n)（），哪些是稳定的排序（）A)冒泡排序B)希尔排序C)快速排序D)插入排序E)堆排序14.下列哪些说法是正确的：（）A)二分查找法在一个长度为1000的有序整数数组查找一个整数，比较的次数不超过100次B)在二叉树中查找元素的时间复杂度为O(log2n)；C)对单向链表，可以使用冒泡排序；D)对双向链表，可以使用快速排序；15.已知某二叉树的后序遍历是DFBEGCA，中序遍历的顺序是DBFACEG，其前序遍历顺序是_________________16.下列代码将两个有序链表结合为一个，链表中的元素的排列顺序为从小到大。请补充其中的空缺。struct node{struct node *pnext;int val;};struct node* splice(struct node* plhs,struct node* prsh){if(______________)return prhs?prhs:plhs;struct node* phead,*plast;if(______________){phead = plast = prhs;plhs = plhs-pnext;}else{phead = plast = plhs;prhs = prhs-pnext;}while(__________){if(plhs-val prhs-val){plast-pnext = plhs;plast = plhs;plhs = plhs-pnext;}else{plast-pnext = prhs;plast = prhs;prhs = prhs-pnext;}}plast-pnest = ___________________;return ________________________;}17. 比较哈希表和平衡二叉树的特点，他们分别用在哪些场合.18.一个栈的入栈序列是 A,B,C,D,E 则栈的不可能的输出序列是（）A) EDCBA B)DECBA C)DCEAB D)ABCDE19.在排序的方法中，关键码比较次数与记录地初始排列无关的是（）A) Shell B)归并排序C)直接排序D)选择排序20.以下反向遍历array数组的方法有什么错误？vector array;array.push_back(1);array.push_back(2);array.push_back(3);for(vector::size_type i=array.size()-1;i=0;--i){cout array[i] endl;}21.某火车站要通过一条栈道（先进后出）来调换进入车站的列车顺序，若进站的列车顺序为A，B，C，则下列哪个出栈顺序不可能？A)ABC