数据结构
1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为（）
A)O(n2) B)O(nlog2n) C)O(log2n) D)O(n)
2.下面程序的时间复杂度为（） for(int i=0;i 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的Array A)2n B)2n-1 C)2n+1 D)n2 9.深度为5的满二叉树中，叶子结点的个数为（） A)32 B)31 C)16 D)15 10.冒泡排序算法和快速排序算法的时间复杂度分别是什么？ 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)ABCDE 19.在排序的方法中，关键码比较次数与记录地初始排列无关的是（） 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 B)ACB C)CAB D)CBA 22.栈是一种是自能在某一端插入和删除的特殊线性表。他按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶， 若6元素进入栈S的顺序为 A.B.C.D.E.F 出栈顺序为B.D.C.F.E.A,则S栈最小容量为？ A) 3 B) 4 C) 5 D) 6 24.若完全二叉树的结点个数为2的N次方-1，则叶子结点个数为： A) N-1 B)2*N C)2（N-1）次方 D) 2N次方 25.排序算法是稳定是指：关键码相同的记录排序前后对应位置不发生改变，下面哪种排序算法是不稳定的？ A)插入排序 B)冒泡排序 C)快速排序 D)归并排序 26.下列说法中错误的是： A)插入排序某些情况下复杂度为O(N)。 B)排序二叉树元素查找的复杂度可能为O(N). C)对于有序列表的排序最快的是快速排序。 D)在有序列表中通过二分查找的复杂度一定是O(nlog2n)。 27.栈和队列的共同特点是（ ） 28.栈通常采用的两种存储结构是（ ） 29.下列关于栈的叙述正确的是（ ） A)栈是非线性结构 B)栈是一种树状结构 C)栈具有先进先出的特征 D)栈有后进先出的特征 30.链表不具有的特点是（ ） A)不必事先估计存储空间 B)可随机访问任一元素