《江西理工大学《数据结构》复习题(附答案).docx》由会员分享，可在线阅读，更多相关《江西理工大学《数据结构》复习题(附答案).docx（14页珍藏版）》请在课桌文档上搜索。
1、2022级数据结构习题第1章绪论，一、单项选择题：(从给定的选项中选择出一个最恰当的答案)1 .算法分析的目的是_。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 .线性表的顺序存储结构是一种A的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取3 .顺序存储设计时，存储单元的地址A_oA.一定连续B.一定不连续C.不一定连续D.部份连续，部份不连续4 .下列数据中C一是非线性数据结构。A栈B.队列C.彻鸟二叉树D.串5 .一个算法应该是B。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.6 .以下属于逻
2、辑结构的是一CoA.顺序表B.哈希表C.线性表D.单链表7 .计算机执行下面的语句时，语句S的执行频度为_DoFOR(i=l;i=i;j-)A.0(n)B.O(nlogn)C.0(n3)D.0(n2)8 .算法分析的两个主要方面是_A_oA.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D-数据复杂性和程序复杂性9 .下面说法错误的是_A.A.算法原地工作的含义是指不需要增加额外的辅助空间B.在相同的规模n下，复杂度0(n)的算法在时间上总是优丁复杂度0(2n)的算法C.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界D.同一合算法L实现语言的级别越高，执行效率就越低10
3、.一个顺序表的第一个元素的存储地址是100,每一个元素的长度为2,则第5个元素的地-OA.110B.108C.100D.12011 .从存储结构上可以把数据结构分为两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构12 .下列叙述中正确的是。A.一种逻辑数据结构只能有一种存储结构。B.数据的逻辑结构属壬线性结构，存储结构属于非线性结构。C. 一种逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率。D. 一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。13 .算法的计算量的大小称为计算的OA.效率B.复杂性C
4、.现实性D.难度14 .下述昂顺下存储结构的优点?A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示15 .以下叙述中错误的是二A.算法IE确的程序最终一定会结束B.算法正确的程序可以有零个输出C算法正确的程序可以有零个输入D.算法正确的程序对于相同的输入一定有相同的结果16 .数据结构的定义为（D,S）,其中D是的*九A.算法B.数据元素C.数据操作D.逻辑结构17 .执行完下列语句段后，i值为。intf（intx）return（x0）?x*f（x-l）;inti;i=f（f（D）;A.2B.4C.8D.无限递归18 .三个递归算法必须包括oA.递归部份B.
5、终止条件和递归部份C.迭代部份D.终止条件和迭代部份二、判断对错题：（正确的选A,错误的选B）1 .数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）2 .顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）3 .记录是数据处理的最小单位。（）4 .程序二定是算法。（）5 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）6 .数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。（）7 .递归的算法简单、易懂、容易编写，而且执行效率也高。（）8 .每种数据结构都应具备三种基本运算：插入、删除和搜索。（）三、应用题1 .给出圆环类的声明（内径为R,外径为R
6、J（包括求圆环面积、圆环内周长和外周长）。2 .给出等腰三角形类的声明（腰长为a,底长为b）（包括求面积与周长）。第2章线性表一、单项选择题：(从给定的选项中选择出一个最恰当的答案)1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表I2 .以下数据结构中，是线性结构。A.哈希表B.二叉树C.有向图D.串3 .设单链表中结点的结构为StrUCtnOdeElcmTypedat;astructnode*Li；nk；己知指针P所指结点不是尾结点，若在*p之后插入结点*s,则应执行下列操作。A
7、.s-link=；pp-link=；SB.s-link=p-l;inkp-Iink=；SC.link=p-l;inkp=s;D.p-link=；ss-link=；P4 .在作进栈运算时,应先判别栈是否。A.空B.满C.上溢D.下溢5 .若栈顶指针指向栈顶元素,当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为OA.n-1B.nC.n+1D.n/26若栈采用顺序存储方式存储，现两栈共享空间VLm,topi代表第i个栈(i=l,栈2)顶，栈1的底在vl,栈2的底在Vm,若栈顶指针指向栈顶元素,则栈满的条件是oA.top2-toplI=B.topl+1=topl2JC.topltop2=
8、mD.topl=top27 .递归过程或者函数调用时,处理参数及返回地址，要用一种称为的数据结构。A.队列B.多维数组C.栈D.线性表8 .若用一个大小为6的数组来实现循环队列，且当前mar和fiwl的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，mar和fint的值分别为.IA.1和5B.2和4C.4和2D.5和19 .若进队列的序列为1,2,3,4则是一个出队列序列。A.3,2,1,4B.3,2,4,1C.4,3,2,1D.1,2,3,410 .在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时oA.r=f-next;B.r=r-next;C.f=f-next
9、;D.f=r-next;11 .线性表(al,a2,an)以链接方式存储时，访问第i位置元素的时间复杂性为。A.0(i)B.0(1)C.O(n)D.O(i-1)12 .删除一单向链表中P指针所指向结点的后继结点，正确的操作是。A.p-ncxt=p-next-next;B.p=p-next;C.p-next=p;D.p-next-next=p-next：13 .为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的设在内存空间的两端。A.长度B.深度C.栈顶D.栈底14 .栈在中应用。A.递归调用B.子程序调用C.表达式求值D.A,B,C31.栈和队列都是OA.
10、顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构15 .在作退栈运算时应先判别栈是否。A.空B.满C.上溢D.下溢16 .若一个栈的输入序列为1,2,3,，n输出序列的第一个元素是i,则第j个输出元素是A.i-j-1B.i-jC.j-i+1D.不确定的17 .在一个链队中，假设f和份别为队首和队尾指针，则插入S所指结点的运算时一oA.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;18 .判定一个循环队列0列最多元素为m)为空的条件是。A.QU.front=(QU.rear+l)%mB
11、.QU.front!=(QU.rear+1)%mC.QU.front=QU.rearD.QU.front!=QU.rear19 .在单项循环链表head的末尾(rear指针指向)插入S指针指向的结点，正确操作是A.rear-next=s;s-next=head;B.s-next=rear;rear-next=head;C.rear=s;s-next=head;D.rear-next=s;s=head;20 .已知函数SUb(S,i,的j)功能是返回串S中从第i个字符起长度为j的子串，函数Spy(s,t)的功能为复制串t到s。若字符串S=SClENCESTUDY，则调用函数SeOPy(P,Sub
12、(S,1,7)后得到丁A.P=SCIENCEB.P=STUDYC.S=SCIENCED.S=STUDY21 .设计一个判别表达式中左，右括号是否配对浮现的算法，采用数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈22 .用链接方式存储的队列，在进行删除运算时oA.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针都不修改23 .以下算法的功能是(栈和队列的元素类型均为int。)voidalgo(StackS,inte)StackT；intd；InitS(ack(T)；while(!StackEmpty(三)pop(S,d);if(d!=e)push(T
13、,d);)while(!StackEmpty(T)pop(T,d);push(S,d);IJA.删除栈S中的数据eB.判断栈S中是否存在数据eC.将栈S中的数据逆置D.将栈S中的数据放入栈T中24 .以下算法的功能(栈中的数据元素类型为int)是。voidstatusalgo(StackS)inti,n,a255;n=0;while(!StackEmpty(三)n+;Pop(S,an);)fr(i=l;inext=r;q-next=r-next;r-next=q;B.p-next=r;r-next=q;q-next=r-next;C.r-next=q;q-next=r-next;p-next=
14、r;D.r-next=q;p-next=r;q-next=r-next;28 .串的操作函数Str定义为：inlstr(char*s)dwr；*p=hsile(*!k计；+returnp-;s)W1Jstr(abcde)的返回值是iA.3B.4C.5D.629 .飞线性表相比，串的插入和删除操作的特点是oA.通常以用整体作为操作对象B.需要更多的辅助空间_斗法的时间复杂度较高涉及挪移的元素更多口30 .对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有个。A.1B,2C3D.431 .设主串长为n,模式串长为m(
15、mwn),则在匹配失败情况下，朴素匹配算法进行的无效位移次数为。A.mB.n-mC.n-m+1D.n32 .已知顺序表的存储结构为：typedefstructElemtypev;intlength;L;以下算法的功能是voidSortA(sqlist&L)inti=0,zerosum=0;if(LJength=O)rcturn(0);elsefr(i=1;i=L.length;i+)if(L.vi0)L.vi-zerosum=L.vi;elsezerosum+;A.计算线性表L中非零元素数目B.将线性表L中零元素集中到表尾C.删除线性表L中的零元素D.计算线性表L中零元素数目33 .在下列对顺
16、序表进行的操作中，算法时间复杂度为O(I)的是JA.访问第i个元素的前驱()B.在第i个元素之后插入一个新元素()C.删除第i个元素OD.对顺序表中元素进行排彳34 .带头结点的单链表屣为t空的判定条件是oA.first=NULLB.first-1ink=NULLC.first-link=firsDt.first=!NULL栈的输入序列为1234,5则下列序列中不可能是栈的输出序列的是。A.23415B.54132C.23145D.1543236.设循环队列的结构是：structintdataMaxsize;intfront,rear;Q;试问判断队列满的条件应是下列语句OA.Q.front=
17、Q.rear;B.Q.front-Q.rear=Maxsize;C.Q.front+Q.rear=Maxsize;D.Q.front=（Q.rear+1）%Maxsize;M判断对错题：（正确的选A,错误的选B）1 .取线性表的第i个元素的时间同i的大小有关。（）2 .两个栈共用静态存储空间，对头使用也存在空间溢出问题。（）3 .二叉树是普通树的特殊情形。（）4 .两个串相等的充分必要条件是分配的存储空间一样。（）5 .已知指针P指向键表L的某结点，执行语句P=P-next不会删除该链表中的结点。（）6 .在链队列中，即使不设置尾指针也能进行入队操作。（）7 .循环链表不是线性表.r）8 .顺
18、序存储结构通过数据元素存储的位置表示元素之间的关系。（）9 .队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）10 .循环队列的引入，目的是为了克服假溢出。（）11 .链表中的头结点仅起到标识的作用。（）12 .对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点挪移量为标准分析。（）13 .为了很方便的插入和删除数据，可以使用双向链表存放数据。（）14 .栈是实现过程和函数等子程序所必需的结构。（一了一15 .在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符浮现的位置均为模式串的最末字符。（）16 .在单链表中，指针P指向元素为X的结点，实现删
19、除X的后继的语句是P-next=p-next-nexto（）17 .通常将链串的结点大小设置为大于1是为了提高存储密度。（）18 .线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（）19 .单链表从任何一个结点出发，都能访问到所有结点。（）20 .在数据结构中，空串和空格串的概念是一样的。（）21 .如果一个串中的所有字符均在另一串中浮现，则说前者是后者的子串。（）22 .循环队列通常用指针来实现队列的头尾相接。（）23 .链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续单元向前挪移。（）三、应用题1 .借助堆栈将（A+B）*（C-D）*E+F）转换成后
20、缀表达式，写出转换过程。2 .借助堆栈计算后缀表达式ABC*DE*+AC*,写出计算过程。第3章树一、单项选择题：(从给定的选项中选择出一个最恰当的答案)1 .在按层次遍历二叉树的算法中，需要借助的辅助数据结构是A.队列B.栈C.线性表D.有序表2 .在任意二棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系.A.不一定相同B.都相同C.都不相同D.互为逆序3 .在下述结论中，正确的是.惟独一个结点的二叉树的度为0;二义树的度为2；二叉树的摆布子树可任意交换；深度为K的彻底二叉树的结点个数小于或者等于深度相同的满二叉树。A.B.C.D.4 .树是结点的有限*,它根结点，记为T。其余结点分
21、成为m(m=0)个互不相交的*T1,T2,，Tm,每一个*又都是树。A.有O个或者1个B.有O个或者多个C.有且惟独一个D.有1个或者1个以上5 .若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为O的结点个数是.A.9B.11C.15D.不确定6 .对于有n个结点的二叉树,其高度为.A.nlog2nB.Iog2nC.Iog2n+1D.不确定7 .利用二叉链表存储树，则根结点的右指针是。A.指向最左孩子B.指向最右孩子C.空D.非空8 .已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为OA.CBEFDAB.FEDCBAC.CBEDFAD.不定
22、9 .下面关于串的的叙述中，是不正确的？A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储10 .有关二叉树下列说法正确的是OA.二叉树的度为2B.棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2IL在一棵高度为k的满二叉树中，结点总数为。A.2k-1B.2kC.2k-lD.Iog2k+112 .树的后根遍历序列等同于该树对应的二叉树的oA.先序序列B.中序序列C.后序序列D.层次序列13 .对于前序遍历和中序遍历结果相同的二叉树为oA.根结点无左孩子的三叉树B.根结点无右孩子的三叉
23、树C.所有结点惟独左子树的二叉树D.所有结点惟独右子树的二叉树14 .下面的说法中正确的是o(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；(2)按二又树定义，具有三个结点的二叉树共有6种。A.(1X2)B.(1)C.(2)D.(1)、都错15 .在彻底二叉树中，若一个结点是叶结点，则它没。A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点16 .假设用于通信的电文由8个字母组成，其频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.2k0.10,为这8个字母设计哈夫曼编码X渡中编码长度最大的字母的编码是位。A.4B.5C.6D.71
24、7 .采用邻接表存储的图的深度优先遍历算法类似于树的aA.中根遍历B.先根遍历C.后根遍历D.按层次遍历18 .在n(n0)个元素的顺序栈中删除1个元素的时间复杂度为。A.()(n)B.O(nlog2n)C.O(I)D.0()19 .若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。A.前序B中序C.后序D,按层次20 .由3个结点可以构造出种不同的二叉树？A.2B.3C.4D.521 .设有两个串P和q,其中q是P的子串，求q在P中首次浮现的位置的算法称为。A求子串B,联接C匹配D.求丽便一22 .若串P=飞tructure其”子用的数目是.A.46B.
25、45C.41D.4023 .设森林F奸应的二叉树为B,它有m个结点，B的根为P,P的右子树结点个数为n,森林F中第一棵树的结点个数是A.m-nB.m-n-1C.n+1D.条件不足，无法确定24 .三:叉树的第I层上最多含有结点数为oA.21B.21-1-1C.21-1D.21-125 .在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为个A.4B.5C.6D.726 .以下算法的功能是ointBTreeDepth(Btree*BT)/*BT为二叉树某结点的指针intIeftdcp,rightdcp;if(BT=NULL)return(O);lef
26、tdep=BTreeDepth(BT-left);rightdep=BTreeDepth(BT-right);if(leftdeprightdep)retum(leftdep+l);elsercturn(rightdcp+1);)A.求二叉树的深度B.求二叉树结点数目】C.先序遍历二叉树的结点D.求二叉树叶子结点的数目二I判断对错题：(正确的选A,错误的选B)叉树是普通树的特殊情形()2 .树最适合用来表示元素之间具有分支层次关系的数据。()3 .哈夫曼树度为1的结点数等于度为2和0的结点数之差。()4 .彻底二叉树一定存在度为1的结点。()5 .对一棵二叉树进行层次遍历时，应借助于一个枝。(
27、)6 .=三叉树只能用】叉链表表示。()7 .树中的结点和图中的顶点就是指数据结构中的数据元素。()8 .度为二的树就是叉树。()9 .二叉树的遍历结果不是惟一的JXj_110 .将一棵树转换为二叉树后，根结点没有左子树。()11 .对于三棵二叉树，如果度为2的结点数为n个，则叶子结点数为n+1个。()12 .对一棵有n个结点，高度为h的二叉树，进行任二种次序遍历的时间复杂度为0(h)。()13 .在树中，如果从结点K出发，存在两条分别到达KK”的长度相等的路径，则结点K，和k”互为兄弟。()三、应用题1.证明存在这样的二叉树：其叶子节点在先根次序、中根次序、后根次序下的都按相同的相对位置浮现
28、(即每一个叶子节点在先根次序、中根次序、后根次序排序结果中的位置相同)。3.某二叉树的结点数据采用顺序存储表示如下：0123456789011213CABDEFG(1)试画出此二叉树的图形表示。(2分)(2)写出结点D的双亲结点及左、右子女。(2分)(3)将此二叉树看做森林的二叉树表示，试将它还原为森林。(2分)3 .根据下面给定的几个数(6,11,6,12,8,18,12,7,4)构造一颗赫夫曼树，并求出其带权路径长度。(给出具体过程)4 .假如一颗二叉树有5个节点，请画出满足下列条件的所有二叉树：(1)先根序列和中根序列相同；(2)中根序列和后根序列相同；5 .分别画出有A、B、C、D三个
29、节点所组成的所有树和所有二叉树。6若一棵度为4的树中有n(l)个度为1的节点个数，n(2)个度为2的节点个数，n(3)个度为3的节点个数，n(4)个度为4的节点个数，问该树有多少个叶节点？一、单项选择题：(从给定的选项中选择出一个最恰当的答案)1 .具有4个顶点的无向彻底图有一条边。A.20B.16C.12D.62 .在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的一倍。A.4B.2C.1D.1/23 .图中有关路径的定义是oA.由顶点和相邻顶点序偶构成的边所形成的序列B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是4 .设无向图的顶点个数为n,则该图最多有条边。
30、A.n-1B.n(n-l)2C.n(n+l)2D.n25 .要连通具有n个顶点的有向图，至少需要条边。A.n-1B.nC.n+1D.2n6 .从邻接阵矩可以看出，该图共有个顶点。A.9B.3C.6D.17 .设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有丁7ebdfcacfdebaedfcbaefdcbaefdbcA.5个B.4个C.3个D.2个8 .在图采用邻接表存储时(n是图的顶点数，e是图的边数)，求最小生成树的Prim算法的时间复杂度为OA.O(n)B.O(n+e)C.O(n2)D.O(n3)9 .n个结点的彻底有向图含有边的数目oA.n*nB.n(nl)C.n/2D.n*
31、(n-l)10 .无向图G=(V,E),其中：V=a,b,c,d,e,f),问做),(喇,(/),(班),9,。,(。小寸),该心图,(1进)行深度优先遍历，得到的顶点序列正确的是A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b11 .若以4,5,6,3,作8为叶子结点的权值构造哈夫曼树，则带权路径长度是。A.28B.55C.59D.6812 .设m,n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙13下列说法不正确的是oA.图的遍历是从给定的源点出发每一个顶点仅被访问一
32、次B.图的深度遍历不合用于有向图C.遍历的基本算法有两种：深度遍历和广度遍历D.图的深度遍历是一个递归过程14 .当各边上的权值时，BFS算法可用来解决单源最短路径问题。A.均相等B.均互不相等C.不一定相等D.均相等或者均不等15 .用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点*U=1,2,5,边的*WE=(1,2),(2,5),要选取下一条权值最小的边，应当从组中选取。A.(1,4),(3,4),(3,5),(2,5)JB.(5,4),(5,3),(5,6)C.(1,2),(2,3),(3,5)D.(3,4),(3,5),(4,5),(1,4)16 .下
33、面算法的功能是ointcount(adjmatrix,GAint,iintn)intd=0;for(intj=0;jiintn)printf(t*%d;,J)visitcd=itnc;for(in=tj;jn；j+)next;L是一带头结点单链表，结点有数据域data和指针域next)if(pre!=null)while(pre-next!=null)p=pre-next;if(p-data=pre-data)pre=EpLSEretum(false)Jreturn(true);A.判断L中相邻的两个结点是否升序罗列B.判断L中相邻的两个结点是否降序罗列C.判断L中的结点是否升序罗列D.判断L
34、中的结点是否降序罗列5 .若查找每一个记录的概率均等，则在具有n个记录的连续顺叙文件中采用顺序查找法查找一个记录，其辛翅善麻度ASL为rA.(114)QBn/2C毋1延D.n6 .下列排序方法中，不是稳定的排序方法？A.直接选择排序B.三分法插入排序C.上路归并排序D.快速排序丁厩希翼较快的查找又便于线性表动态变化的查找方法是。A.顺序查找B.折半查找C.索引顺序查找D.哈希法查找8 .以下算法的功能(栈中的数据元素类型为int)是ovoidalgo(Queue&Q)StackS；intd：InitStack(S)；while(!QueueEmpty(Q)DeQueue(Q,d);Push(S
35、,d);?!while(!StackEmpty(三)pop(S,d);EnQueue(Q,d);7A.将栈S中的元素逆置B.将队列Q中的元素逆置C.输出栈S中的元素D.输出队列Q中的元素9 .当采用分快查找时，数据的组织方式为oA.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或者最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或者最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同10.若用数组SO.m-l作为两个栈Sl和S2的共同存储结构，对任何一个栈，惟独当S全满时才不能作入栈操作。为这两
36、个栈分配空间的最佳方案是OA .B .C.D.Sl的栈底位置为O, SI的栈底位置为0, Sl的栈底位置为1, SI的栈底位置为1,S2的栈底位置为n-IS2的栈底位置为n/2-lS2的栈底位置为nS2的栈底位置为n/211对线性表进行二分查找时，要求线性表必须.A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序12 .一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为OA.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,4
37、6,56,79,84)D.(40,38,46,84,56,79)13 .既希翼较快的查找又便于线性表动态变化的查找方法是oA.顺序查找B.折半查找C.索引顺序查找D.哈希法查找14,排序趟数与序列的原始状态有关的排序方法是排序法。A.插入B.选择C冒泡D.快速15 .数据序列(2,1,4,9,8,10,6,20)只能是下列排序算法中的的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D,插入排序16 .对一组数据(84,47,25,15,21)排序，数据的罗列次序在排序的过程中的变化为(1)8447251521(2)1547258421(3)1521258447(4)1521254784
38、则采用的排序是。A.选择B.冒泡C.快速D.插入17 .具有12个关键字的有序表，折半查找的平均查找长度cA.3.1B.4C.2.5D.518 .折半筐找的时间复杂性为。A.O(n2)B.O(n)C.O(nlogn)D.O(Iogn)19 .关于杂凑查找说法不正确的有几个。(1)采用链地址法解决冲突时，查找一个元素的时间是相同的(2)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起会萃现象(4)再哈希法不易产生会萃A.1B.2C.3D.420 .假定有k个大键？17I为RJ义词，若用线性探测法把这k个关键字存入散列表中,至少要进行次探测
39、？A.k-1次B.k次C.k+1次D.k(k+1)2次21 .散列表的地址区间为0-17,散列函数为H(K)=KmOd17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59挨次存储到散列表中。元素59存放在散列表中的地址是OA.8B.9C.10D.H22 .对序列（22,86,19,49,12,30,65,35,18）进行一趟排序后得到的结果如下：（18,12,19,22,49,30,65,35,86）,则可以认为使用的排序方法是。A.选择排序B.冒泡排序C.快速排序D.插入排序三、判断对错题：（正确的选A,错误的选B）1 .就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（）2 .HaSh表的平均查找长度与处理冲突的方法无关。（）3 .直接选择排序算法在最好情况下的时间复杂度为O（N）,N是数据元素的个数。（）4 .排序算法中的比较次数与初始元素序列的罗列无关。（）5 .合用于折半查找的表的存储方式及元素罗列要求是：链接方式存储，元素无序。（）6 .当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。（）7 .散列函数越复杂越好，因为这样随机性好，冲突概率小。（）8 .冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。（）9 .在排序过程中，主要进
