《数据结构考试试卷(含六卷).docx》由会员分享，可在线阅读，更多相关《数据结构考试试卷(含六卷).docx（115页珍藏版）》请在课桌文档上搜索。
1、数据结构考试试卷（一）总分：100分考试时间：90分钟注意事项：考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致作答有误需重新作答时，尽量避免使用橡皮擦除，以防卡面破损，个别错误可用正确的删除?口修改符号进行修改；不准修改答题卡上的题号，否则答案无效。考试结束信号发出后，要立即停笔并起立。一.单项选择题（每小题2分，共100分）1.最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是A、rear=frontBx（rear+l）%n=frontC、rear+l=frontD、（rear-l）%n=front【答案】A2、带头结点的单链表1.为空的条件是（
2、）A、1.!=NU1.1.B、1.=NU1.1.C、1.-next=NU1.1.D、1.-next=1.【答案】C3、二叉树的深度为k,则二叉树最多有（）个结点。（3.0分）A、2kB、2k-lC、2k-1D、2k-l【答案】C4、设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为（）。A、nzeB、eznC、2nzeD、nz2e【答案】D5、设高度为h的二叉树上只有度为O和度为2的结点，则此类二叉树中所包含的结点数至少为A、2h8、 2h-lC、2h+lD、h+1【答案】B6、插入和删除分别在两端端进行的线性表是A、循环队列B、栈C、队列D、循环栈【答案】C7、栈
3、和队列的共同特点是A、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点【答案】A8、对于一个具有N个顶点的无向图,若采用邻接矩阵表示很U该矩阵大小是()A、NB、(N-l)2C、(N-1)*ND、N*N【答案】D9、(4分)在一个单链表中,已知q指向P所指向结点的前趋结点,若在q.p所指结点之间插入一个s所指向的新结点很I执行的操作是（八）。A、q-next=s;s-next=pBxp-net=s;s-next=qC、s-next=p-next;p-next=sDxp-next=s-nxt;s-next=p【答案】A10、在表长为n的链表中进行顺序查找,它的平均查找长
4、度为()。(5.0分)A、n/2B. (n+l)2Cxn+lDxlg(nl)-l【答案】B11、顺序队列的初始化时,需要将front和rear分别设置为()A、都是0B、0和-1C、都是-1Dx-1和0【答案】A12、分析以下程序段,其时间复杂度为T(n)=()i=l;While(i=n)i=3*i;A、0(n)B、O(n2)C、O(n3)D、O(I)【答案】D13、打印杨辉三角形时,可以使用的数据结构是()。A、线性表的JII姊存储结构B、队列C、线性表的链式存储结构D、栈【答案】B14、如果以链表作为栈的存储结构很U退栈操作时A、必须判别栈是否满B、对栈不作任何判别C、必须判别栈是否为空D
5、、判别栈元素的类型【答案】C15、递归函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A、队列B、多维数组C、栈D、线性表【答案】C16、若广义表A满足heaD（八）=tail（八）,则A为（A、（）B、（）C、（）,（）D、（）,（）,（）【答案】B17、数据结构这门学科的研究内容下面选项最准确的是A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作【答案】D18、（4分）若栈采用链式存储结构很（J下列说法中正确的是（B）。A、需要判断栈满且需要判断栈空B、不需要判断栈满但需要判断栈空C、需要判断栈满但不需要判断栈空D
6、、不需要判断栈满也不需要判断栈空【答案】B19、一棵具有n个结点的完全二叉树的树高度（深度）是（八）A、og2nJ+1BxIog2n+1C. og2nJDxIog2n-1【答案】A20、在一棵深度为k的完全二叉树中，所含结点个数至少（）A、2kB、2k+lD、2k-l【答案】D21、(3分)用邻接表表示n个顶点e条边的无向图,其边表结点的总数是(C)。A、nxeB、eC、2eDxn+e【答案】C22、当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用()方法的时间复杂度都是0(n2)A、快速排序B、冒泡排序C、归并排序D、直接选择排序【答案】D23、可进行拓扑排序的图只能是(C)oA
7、、有向图B、无向图C、有向无环图D、无向连通图【答案】C24、设某无向图有20个顶点,则该无向图的邻接表中有()个表头结点。A、40B、20C、5D、380【答案】B25、对于顺序循环队列，以下说法正确的是（）A、无法判断队列是否为空B、无法判断队列是否为满C、队列不可能满D、以上说法都不对【答案】D26、对长度为4的顺序表进行查找,若查找第一个记录的概率为1/24,查找第二个记录的概率为1/6,查找第三个记录的概率为2/3,查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为（）。（5.0分）A、 23/8B、 20/8C、 17/8D、 13/8【答案】A27、在平衡二叉树中插
8、入一个结点后造成了不平衡,设最低不平衡结点为A,并已知结点A的左孩子的平衡因子为0,右孩子的平衡因子为1.则应做（）型调整其A、1.1.B、1.RC、R1.D、RR【答案】C28、数据结构指的是数据之间的相互关系,即数据的组织形式。数据结构一般包括()三方面内容。(5.0分)A、数据的逻辑结构.数据的存储结构.数据的描述B、数据的逻辑结构.数据的存储结构.数据的运算C、数据的存储结构.数据的运算.数据的描述D、数据的逻辑结构.数据的运算.数据的描述【答案】B29、设二叉树如下则后序序列为()a、Abdegcfhb、Dbgeafhcc、Dgebhfcad、Abcdefgh【答案】c30、下面程序
9、段的时间复杂度是(Ifor(i=0；i(1分)A、0(m2)B、O(n2)CxO(m*n)D、O(m+n)【答案】C31、某哈希查找表有n条记录,对应的哈希函数具有m个值很1()A、nmCxn=m【答案】D32、线性表(al,a2,an)以链接方式存储时，访问第i位置元素的时间复杂性为(A、0(i)B、0(1)C、0(n)D、0(i-l)【答案】C33、下列4种基本逻辑结构中，数据元素之间关系最弱的是(工A、集合B、线性结构C、树形结构D、图形结构【答案】A34、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度(I(1分)A、O(Iog2n)B、0(1)C、0(
10、n)D、O(n2)【答案】C35、n个顶点的强连通图，若该连通图含有最少的边，其形状是(A、无回路B、有多个回路C、环状D、无法确定【答案】C36、队列的删除操作是在()。(4.0分)A、队首B、队尾C、队前D、队后【答案】A37、以下各阶时间复杂度中,性能最优的是()。A、O(log2n)B、0(n)C、0(n3)D、0(2n)【答案】A38、下列程序段的时间复杂度为()oFor(i=0;im;i+)for(j=0;jt;j+)cij=0;For(i=0;im;i+)for(j=0;jt;j+)for(k=0;kn;k+)cij=cij+aik*bkj;A、0(m*n*t)B、0(mn+t)
11、C、0(m+n*t)Dx0(m*t+n)【答案】A39、线性表采用链式存储时,其地址OA、必须是连续的B、一定是不连续的C、部分地址必须是连续的D、连续与否均可以【答案】D40、关于线性表的说法不正确的是？A、存在唯一的一个被称为“第一个的数据元素(开始结点)B、存在唯一的一个被称为最后一个的数据元素(终端结点)C、除第一个之外，集合中的每个数据元素均只有一个前驱D、除第一个之外，集合中的每个数据元素均只有一个后继【答案】D41、已知某二叉树的后序遍历序列是DabeC,中序遍历序列是DebaCz它的前序遍历序列是（）A、aCbeDBxDeCaBC、DeabCD、CeDba【答案】D42、二维数
12、组A行下标i的范围从1到12,列下标j的范围从3到10,采用行序为主序存储，每个数据元素占用4个存储单元，该数组的首地址（即Al3的地址）为1200,则A65的地址为（工A、 1400B、 1404C、 1372D、 1368【答案】D43、某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是A、某班级的学生成绩表是数据元素,90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素,90分是数据元素【答案】C44、设F是由T1.T2和T3
13、三棵树组成的森林,与F对应的二叉树为B,T1.T2和T3的结点数分别为Nl、N2和N3,则二叉树B的根结点的左子树的结点数为（1A、Nl-IB、N2-1C、N2+N3D、N1+N3【答案】A45、设有向无环图G中的有向边集合E=,则下列属于该有向图G的一种拓扑排序序列的是（A、1,2,3,4B、2,3,4,1C、1,4,2,3D、1,2,4,3【答案】A46、判断带头结点的单链表为空表的条件是（）,假设头指针为heado（3.0分）A、this.head.next=null;B、this.head=null;C、this.head.next=this.head;D、this.head!=nul
14、l;【答案】A47、(4分)长度为n的顺序表,删除位置i上的元素(OSiSn-I),需要移动的元素个数为(B)。A、n-iB、n-i-1C、iDxi+1【答案】B48、广义表1.=(a,b,c),(e,f),则1.的长度和深度分别为()oA、3,2B、2,3C、2,2D、2,5【答案】C49、在长度为n的字符串S的第i个位置插入另外一个字符串,i的合法值应该是()A、i0B、inCxlinD、lin+l【答案】C50、如果以链表作为栈的存储结构很U退栈操作时()。A、必须判别栈是否满B、判别栈元素的类型C、必须判别栈是否空D、不做任何判别【答案】C数据结构考试试卷（二）总分：100分考试时间：
15、90分钟注意事项：考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致作答有误需重新作答时，尽量避免使用橡皮擦除，以防卡面破损，个别错误可用正确的删除?口修改符号进行修改；不准修改答题卡上的题号，否则答案无效。考试结束信号发出后，要立即停笔并起立。一.单项选择题（每小题2分，共100分）1.从没有排序序列中挑选元素,并将其一次插入已排序序列末端的方法,称（）A、归用非序B、冒泡排序C、插入排序D、选择排序【答案】D2、以下说法正确的是（）。A、线性结构的基本特征是:每个结点有且仅有一个直接前驱和一个直接后继B、线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要
16、低C、在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素位置有关D、顺序存储的线性表的插入和删除操作不需要付出很大的代价,因此平均操作只有近一半的元素需要移动【答案】C3、在下面的几种排序方法中,需要内存空间最大的方法是（八）。A、归并排序B、直接选择排序C、快速排序D、插入排序【答案】A4、向一个队首指针为front.队尾指针为rear的链队列中插入一个S所指结点时，其操作步骤为()A、s-net=front;B、front=front-next;front-next=s;C、s-next=rear;Dxrear=s;rear=s;s-next=rear;【答案】C5、设栈的
17、顺序存储空间为SQ:m),初始状态为top=mlo现经过一系列正常的入栈与退栈操作后,top=2(则栈中的元素个数为()。A、30B、20C、m-19D、M-20【答案】C6、以下排序方法中,()不需要进行关键字的比较。A、快速排序B、归并排序C、基数排序D、堆排序【答案】C7、设有100O个无序的元素，希望用最快的速度挑出其中前10个最大的元素，最好（）排序法。A、起泡排序B、选择排序C、堆排序D、希尔排序【答案】B8、对一个满二叉树，它有m个树叶，n个结点，深度为h,则（）A、n=h+mB、h+m=2nC、m=h-lDxxn=2h-l【答案】D9、具有6个顶点的无向图至少有（）条边才能确保
18、是一个连通图A、5B、6C、7D、8【答案】A10、分析以下程序段,其时间复杂度为T(n)=()x=0;For(i=l;in;i+);for(j=ljn;j+);For(k=l;kright=s;s-left=p;p-right-Ieft=S;s-right=p-right;B、s-left=p;s-right=p-right;p-right=s;p-right-left=s;C、p-right=s;p-right-left=s;s-left=p;s-right=p-right;Dss-left=p;s-right=p-right;p-right-left=s;p-right=s;【答案】D1
19、4、数据结构只是研究数据的逻辑结构和物理结构,这种观点()A、正确B、错误C、前半句正确,后半句错误D、前半句错误,后半句正确【答案】B15、若INDEX(S,T)表示求T在S中的位置厕对于S=wBeiJingSiNanjingwzT=wjing,zJNDEX(SzT)=OoA、2B、3C、4D、5【答案】C16、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(A、8B、7C、6D、5【答案】B17、有n个数据的二叉排序树最大可能深度是()A、nB、nlC、Iog2(n)DxIog2(n+1)【答案】A18、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾
20、指针，指针变量S指向将要入队列的结点X,则入队列的操作序列为(A、front-next=s;front=s;B、s-next=rear;rear=s;C、rear-next=s;rear=s;Dxs-next=front;front=s;【答案】C19、顺序栈是空栈的条件是(A、top=0B、top=lCxtop=-lDxtop=m【答案】A20、算法分析的目的是（）。（5.0分）A、分析算法的效率以求改进B、找出数据结构的合理性C、分析算法的可读性D、研究算法中的输入输出关系【答案】A21、数据的基本单位（）A、数据结构B、数据元素C、数据项D、文件【答案】B22、为解决计算机主机与打印机间
21、速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（A、队列B、栈C、线性表D、有序表【答案】A【解析】解释：解决缓冲区问题应利用一种先进先出的线性表,而队列正是一种先进先出的线性表。23、已知线性表1.=(alra2,ai,an),下列说法正确的是()。A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外,其余每个元素都有一个数,且仅有一个直接前驱和直接后继【答案】D24、用邻接表表示图进行广度优先遍历时，通常
22、借助()来实现算法。A、栈B、队列C、树D、图【答案】B【解析】解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。25、对一些特殊矩阵采用压缩存储的目的主要是为了()A、表达变得简单B、对矩阵元素的存取变得简单C、去掉矩阵中的多余元素D、减少不必要的存储空间的开销【答案】D26、设一组初始记录关键字序列为（13,18,24,35,47,50,62,83,90,115,134）,则利用二分法查找关键字90需要比较的关键字个数为（A、1B、2C、3D、4【答案】B27、一颗二叉树高度为h（根的高度为1）,所有结点的度为0,或者为2,则这颗二叉树最少（）结点。（3.0分）A
23、、2hB、 2h-lC、2h+lD、h+1【答案】B28、有n个十进制整数进行基数排序,其中最大的整数为5位,则基数排序过程中临时建立的队数个数是（）OA、10B、nC、5D、2【答案】A29、给定排序码值序列为F,B,J,C,E,A,I,D,C,H,对其按字母的字典序列的次序进行排列，二路归并排序的第一趟排序结果是A、B,F,C,J,A,E,D,I,C,HB、C,B,D,A,E,F,I,C,J,HC、B,F,C,E,A,I,D,C,H,JD、A,B,D,C,E,F,I,J,C,H【答案】A30、深度为4的完全:二叉树的结点数至少为。A、4B、8C、13D、15【答案】B31、k=m*n;Fo
24、r(i=0;ik;i+)i+;A、O(m)B、O(n)C、O(m*n)D、O(i)【答案】C32、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度AS1.为()A、(n-1)/2C、 (n+l)2D、n【答案】C33、下面程序段的时间复杂性的量级为(For(inti=0;im;i+)For(intj=O;j考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致作答有误需重新作答时，尽量避免使用橡皮擦除，以防卡面破损，个别错误可用正确的删除?口修改符号进行修改；不准修改答题卡上的题号，否则答案无效。考试结束信号发出后，要立即停笔并起立。
25、一.单项选择题（每小题2分，共100分）1、在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为A、4B、5C、6D、7【答案】D2、下面关于求关键路径的说法不正确的是（C）。A、求关键路径是以拓扑排序为基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一定位于关键路径上【答案】C3、(3分)下列关于无向图广度优先搜索序列的叙述中,正确的是(C)。A、广度优先搜索序列只有一种B、广度优先搜索序列可能不存在C、广度优先搜索序列可能有多
26、种D、广度优先搜索序列一定有多种【答案】C4、(3分)若某二叉树的后序遍历序列为dabec,中序遍历序列是debac,则它的前序遍历序列是(B)。A、acbedBxcedbaC、deabcD、decab.【答案】B5、下列叙述中正确的是()。A、在循环队列中,队头指针和队尾指针的动态变化决定队列的长度B、在循环队列中,队尾指针的动态变化决定队列的长度C、在带链的队列中,队头指针与队尾指针的动态变化决定队列的长度D、在带链的栈中,栈顶指针的动态变化决定栈中元素的个数【答案】A6、在哈夫曼编码中,根结点的权值是()。A、根的左右两个子结点的权值之和B、根的左右两个子结点的权值的平均值C、所有结点的
27、权值的平均值D、所有结点的权值之和【答案】A7、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4,列下标j的范围从O到5,M按行存储时元素M35的起始地址与M按列存储时元素（）的起始地址相同。A、M24B、M34C、M35D、M44【答案】B8、任可一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序（）A、不发生变化B、发生变化C、某些树中发生变化，某些树中不发生变化D、没有规律，无法确定【答案】A9、用链式存储的栈，在进行出栈和入栈运算时（）A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改【答案】D10、如果按关
28、键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均查找长度AS1.为A、50B、48C、45D、47【答案】A11、下面()的时间复杂性最好，即执行时间最短。A、O(n)BxO(Iogn)C、O(nlogn)D、0(n2)【答案】B12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是()A、正确性算法应能正确地实现预定的功能B、易读性算法应易于阅读和理解,以便调试、修改和扩充C、健壮性当环境发生变化时,算法能适当地做出反应或进行处理,不会产生不需要的运行结果D、高效性即达到所需要的功能花费的时间和空
29、间【答案】D13、一个无向图有20个顶点,共有50条边。则一个顶点的度最多是()。A、50B、49C、20D、19【答案】D14、若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为()A、O(n)B、0(n2)C、0(n3)Dx0(Iog2n)【答案】B15、(3分)设有一组关键字(19.14,23.1.6.20.4275.1109),用散列函数H(key)=key%13构造散列表,用拉链法解决冲突,散列地址为1的链中记录个数为(C).A、1B、2C、3D、4【答案】C16、已知指针p指向单链表1.中的某结点，则删除其后继结点的语句是A、P=p-nextB、p=nullC、
30、p-next=nullDxp-next=p-next-next【答案】D17、用链式存储的栈，在进栈操作之前，需要（）A、判断栈是否满了B、判断栈是否空了C、不需判断D、以上答案都不对【答案】C18、采用邻接表存储的图的宽度优先遍万算法类似于二叉树的。A、按层遍历B、前序遍历C、后序遍历D、中序遍历【答案】A19、以下说法正确的是（A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构【答案】D【解析】解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。20、一个队列
31、的进队序列为ab,c,d,则出队序列是：()。A、a,b,c,dB、d,c,a,bC、azd,bzcD、c,a,d,b【答案】A21、设有序顺序表中有n个数据元素,则利用二分查找法查找数据元素X的最多比较次数不超过()。AsIog2(n)+1BxIog2(n)-1C、Iog2(n)DxIog2(n+1)【答案】A22、若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在()种情况。A、5,4,3,2,1B、2,1,5,4,3C、4,3,1,2,5D、2,3,5,4,1【答案】C【解析】解释：栈是后进先出的线性表,不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现
32、C选项所示的情况。23、(2分)苦一棵二叉树的前序遍历序列与后序遍历序列相同很!J该二二叉树可能的形状是(B)。A、树中没有度为2的结点B、树中只有一个根结点C、树中非叶结点均只有左子树D、树中非叶结点均只有右子树【答案】B24、序列3,2,4,1,5,6,8,7是第一趟递增排序后的结果,则采用的排序方法可能是OoA、快速排序B、冒泡排序C、堆排序D、简单选择排序【答案】A25、循环队列的队空条件为()。A、(sq.rear+l)%maxsize=(sq.front+l)%maxsizeB、(sq.rear+l)%maxsize=sq.front+1C、sq.(rearl)%maxsize=s
33、q.frontD、sq.rear=sq.front【答案】D26、设森林F对应的二叉树有m个结点，二叉树的根节点的右子树上结点个数为n,则森林F中第一个树的结点个数为（）A、m-nB、m-n-1C、m-n+1D、无法确定【答案】A27、对于顺序表的优缺点,以下说法不正确的是（）。（3.0分）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算比较方便D、容易造成一部分空间长期闲置而得不到充分利用【答案】C28、下面属于整数类I的实例的是0A、229B、0.229C、 229E-2D、 “229”【答案】A29、树的后序遍历等价于该树对应二叉树
34、的。A、层次遍历B、前序遍历C、中序遍历D、后序遍历【答案】C30、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为()。A、2i+lB、2iC、i/2D、2i-l【答案】B31、无向图G=(ME),其中:V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历彳导到的顶点序列正确的是(D)。A、a,b,e,c,d,fB、a,c,fe,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b【答案】D32、队列的插入操作是在()。Ax队尾B、队头C、队列任意位置
35、D、队头元素后【答案】A33、(4分)顺序表便于(D)。A、插入结点B、删除结点C、：按值查找结点D、按序号查找结点【答案】D34、difference/,BQ表示求集合A和B的差集C。若A=b,c,d,B=c,e,则difference(A,B,C)运算后C=(A、b,c,d,eB、cC、b,dD、b,c,c,d,e【答案】C35、图中有关路径的定义是（八）。A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不是【答案】A36、对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为X的结点后插入一个新结
36、点的时间复杂度分别为A、O(l)zO(n)B、O(n)zO(n)C、O(I)zO(I)D、0(n),0(l)【答案】A37、算法的有穷性是指()。A、算法程序的运行时间是有限的B、算法程序所处理的数据量是有限的C、算法程序的长度是有限的D、算法只能被有限的用户使用【答案】A38、(3分)某索引顺序表共有元素395个,.平均分成5块。若先对引表采用顺序查找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找长度是（八）。A、43B、79C、198D、200【答案】A39、算法的时间复杂度取决于（A、问题的规模B、待处理数据的初态C、计算机的配置D、A和B【答案】D【解析】解释：算
37、法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。40、链表适用于（）。（5.0分）A、顺序直找B、二分查找C、插值查找D、随机【答案】A41、下列四种排序中（）的空间复杂度最大。（2.0分）A、快速排序B、冒泡排序C、希尔排序D、堆排序【答案】A42、一棵二叉排序树采用二叉链存储,对于关键字最小的结点,它的（）。A、左指针一定为空B、右指针一定为空C、左、右指针均为空D、左、右指针均不为空【答案】A43、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(C)的两趟排序后的结果。A、选择排序B、冒泡排序
