02笔试题-数据结构部分

数据结构1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为（）A)O(n2)B)O(nlog2n)C)O(log2n)D)O(n)2.下面程序的时间复杂度为（）for(inti=0;im;i++){for(intj=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)2nB)2n-1C)2n+1D)n29.深度为5的满二叉树中，叶子结点的个数为（）A)32B)31C)16D)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.下列代码将两个有序链表结合为一个，链表中的元素的排列顺序为从小到大。请补充其中的空缺。structnode{structnode*pnext;intval;};structnode*splice(structnode*plhs,structnode*prsh){if(______________)returnprhs?prhs:plhs;structnode*phead,*plast;if(______________){phead=plast=prhs;plhs=plhs-pnext;}else{phead=plast=plhs;prhs=prhs-pnext;}while(__________){if(plhs-valprhs-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)EDCBAB)DECBAC)DCEABD)ABCDE19.在排序的方法中，关键码比较次数与记录地初始排列无关的是（）A)ShellB)归并排序C)直接排序D)选择排序20.以下反向遍历array数组的方法有什么错误？vectorarray;array.push_back(1);array.push_back(2);array.push_back(3);for(vector::size_typei=array.size()-1;i=0;--i){coutarray[i]endl;}21.某火车站要通过一条栈道（先进后出）来调换进入车站的列车顺序，若进站的列车顺序为A，B，C，则下列哪个出栈顺序不可能？A)ABCB)ACBC)CABD)CBA22.栈是一种是自能在某一端插入和删除的特殊线性表。他按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，若6元素进入栈S的顺序为A.B.C.D.E.F出栈顺序为B.D.C.F.E.A,则S栈最小容量为？A)3B)4C)5D)624.若完全二叉树的结点个数为2的N次方-1，则叶子结点个数为：A)N-1B)2*NC)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)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比31.用链表表示线性表的优点是（）32.循环链表的主要优点是（）33.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（）A)每个元素都有一个直接前件和直接后件B)线性表中至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小D)除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件34.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续不连续都可以35.树是结点的集合，它的根结点数目是（）36.在深度为5的满二叉树中，结点的个数为（）37.具有3个结点的二叉树有（）种形态38.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（）39.算法一般都可以用哪几种控制结构组合而成（）40.下列叙述正确的是（）A)算法的执行效率与数据的存储结构无关B)算法的空间复杂度是指算法程序中指令（或语句）的条数C)算法的有穷性是指算法必须能在执行有限个步骤之后终止D)算法的时间复杂度是指执行算法程序所需要的时间41.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（）42.下列叙述中，错误的是（）A)数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占的空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构46.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为（）43.下列数据结构中，按先进后出原则组织数据的是（）A)线性链表B)栈C)循环链表D)顺序表44.下列关于栈的叙述中正确的是（）A)在栈中只能插入数据B)在栈中只能删除数据C)栈是先进先出的线性表D)栈是先进后出的线性表45.应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定（）中，当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。46.下列关于队列的叙述中正确的是（）A)在队列中只能插入数据B)在队列中只能删除数据C)队列是先进先出的线性表D)队列是先进后出的线性表47.有一个C语言用来删除单链表的头元素的函数，请找出其中的问题并加以纠正。voidRemoveHead(node*head){free(head)head=head-next}48.设单链表中节点的结构为：typedefstructnode{Elemtypedata;//数据structnode*Link;//节点后继指针}Listnode;（1）已知指针p所指节点不是尾节点，若在*p之后插入节点*s，则应执行下列哪一个操作？A)s-link=p;p-link=s;B)s-link=p-link;p-link=s;C)s-link=p-link;p=s;D)p-link=s;s-link=p;(2)非空的循环单链表first的尾节点（由p所指向）满足：A)p-link==NULL;B)p==NULL;C)p-link==first;D)p==first;49.如何证明一个表是循环链表？52.如果一棵二叉树节点的前序序列是A、B、C，后序序列是C、B、A，则该二叉树节点的中序序列是什么？A)必为ABCB)必为ACBC)必为BCAD)不能确定53.什么是平衡二叉树？54.下面的程序是一快速排序问题，请填空。#includeiostream#includestdio.hvoidimproveqsort(int*list,intm,intn){intk,t,i,j;/*for(i=0;i10;i++)printf(%3d,list[i]);*/if(mn){i=m;j=n+1;k=list[m];while(ij){for(i=i+1,in.i++)if(list[i]=k)break;for(j=j-1,jm,j--)if(list[j]=k)break;if(ij){t=list[i];list[i]=list[j];list[j]=t;}}t=list[m];list[m]=list[j];list[j]=t;improveqsort();improveqsort();}}main(){intlist[10];intn=9,m=0,i;printf(input10number:);for(i=0;i10;i++)scanf(%d,&list[i]);printf(\n);improveqsort(list,m,n);for(i=0;i10;i++)printf(%5d,list[i]);printf(\n);}55.以下哪种排序属于稳定排序？A)归并排序B)快速排序C)希尔排序D)堆排序56.用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？A)5B)2C)4D)157.下面那种排序法对1234567最快？A)quicksortB)bubblesortC)mergesort58.解释一下什么是哈夫曼编码问题？59.假设执行语句Q的时间是O（1），则执行下列程序段的时间为（）for(inti=1;i=n;i++)for(intj=i;j=n;j++)Q;A.O(n)B.O(n2)C.O(n*i)D.O(n+1)61.一棵有124个叶结点的完全二叉树，最多有（）个结点A．247B.248C.249D.25063.下列排序算法中，在待排序数据有序的情况下，花费时间最多的是（）A．快速排序B.希尔排序C.冒泡排序D.堆排序64.有1000个无序的整数，希望使用最快的方式找出前50个最大的，最佳的选择是（）A.冒泡排序B.基数排序C.堆排序D.快速排序65.下列哪个不是用来解决哈希表冲突的开放地址法（）A.线性探测法B.线性补偿探测法C.拉链探测法D.随机探测法66.假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数___。A．h(k)=k/N;B．h(k)=1;C．h(k)=kmodN;D．h(k)=(k+Random(N))modN,random(N)返回一个0到N-1的整数68.下面算法的时间复杂度是____.intf(unsignedintn){i