数据结构题库课后练习题答案章节测试题19章全

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！和n2__________。A、>2>，__________。A、__________。A、__________________？________。__________？__________。n{}2__________。；）{；；})2)3)42)22__________。；A、)22__________。；；；；；；；；；；A、____________________？__________22)2Ddddd4，Rr，rdd2,dd3,dd4}{@}}{@}{@n是不小于1}{@{x}}n(n2iin2i11212121nnnniiii)ii=222i1i1i1i1111nn(nn(nn=n(n12412nnn}和Z{}一、选择题1．线性表是具有n个__C_A．表元素B．字符C．数据元素D．数据项2．一个顺序表所占用的存储空间大小与___B___无关。A．表的长度B．元素的存放顺序C．元素的类型D．元素中各字段的类型3．线性表的顺序存储结构是一种__A___。A．随机存取的存储方式C．索引存取的存储方式B．顺序存取的存储方式D．Hash存取的存储方式4.4储地址为100,则第12个元素的存储地址是__B____。A．112B.144C.148D.4125.线性表是__A____。A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空C____。A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O(1)7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。A．n-iB．n+iC．n-i+1D．n-i-18．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。A.n/2B.（n+1）/2C.（n-1）/2D.n9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__CA．O（0）B．O（1）C．O（n）D．O（n）210．线性表中各链接点之间的地址___C____。A．必须连续B．部分地址必须连续D．连续与否无所谓C．不一定连续11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。ii≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．以上都不对12．单链表中，增加一个头结点的目的是为了____C_____。A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_B____。A．head==NULLB．head->next==NULLD．head!=NULLC．head->next==headn的单链表链接在长度为m的单链表后面的算法的时间复杂度采用大O形式表示应该是___C____。A．O（1）15．静态链表中指针表示的是___C____。A．下一个元素的地址B．内存储器的地址B．O（n）C．O（m）D．O（n+m）C．下一个元素在数组中的位置D．左链或右链指向的元素的地址16．非空的循环单链表head的尾结点p满足__A______。A．P->link=headB．P->link=NULLC．P=NULLD．P=head17某线性表用带头结点的循环单链表存储，头指针为head，当．head->next->next==head成立时，线性表的长度是___B____。A．018．在什么情况下，应使用链式结构存储线性表L?___B____A．需经常修改L中的结点值B．需不断对L进行删除插入B．1C．2D．3C．需要经常查询L中的结点值D．L中结点结构复杂19．与单链表相比较，双向链表的优点之一是___D_____。A．可以省略头结点指针C．插入、删除操作更简单B．可以随机访问D．顺序访问相邻结点更灵活20．某线性表常发生的操作为删除第一个数据元素和最后一个元素后添加新元素，采用__D__作为存储结构，能使其存储效率和时间效率最高。A．单链表B．仅用头指针的循环单链表D．仅用尾指针的循环单链表C．双向循环链表点。则采用_D___存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表映数据之间的逻辑关系，则应用___C____。A．顺序方式存储B．散列方式存储C．链接方式存储D．以上方式均可除运算，则利用___A___存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表i时间应采用的存储方式为___D_____。A．单链表B．双向链表C．单循环链表D．顺序表25．下面哪一条是顺序存储结构的优点？___C______A．插入运算方便C．存储密度大B．可方便地用于各种逻辑结构的存储表示D．删除运算方便26．下面关于线性表的叙述中，错误的是___B_____。A.线性表采用顺序存储，必须占用一批连续的存储单元B.线性表采用顺序存储，便于进行插入和删除的操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作p所指的链接点后面插入一个由q所指的链接点的过程是依次执行动作__B____。A．q->link=p；p->link=q；C．q->link=p->link；p=q；B．q-link=p->link；p->link=q；D．p->link=q；q->link=p；q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p->rlink=q；p->llink=q->llink;q->llink=p;____D____。A．q->rlink->llink=p;C．p->rlink->llink=p;B．q->llink->rlink=p;D．p->llink->rlink=p;q所指的链接点后面插入一个由p指的链接点的动作依次为__D____。A．p->llink=q;p->rlink=q->rlink;q->rlink=p;q->rlink->llink=p；B．p->rlink=q->rlink;p->llink=q;q->rlink;q->rlink->llink=p；C．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->llink->rlink=p；D．p->llink=q;p->rlink=q->rlink;q->rlink=p;p->rlink->llink=p；30．在双向链表存储结构中，删除p所指的结点时须修改指针__A____。A．p->llink->rlink=p->rlink;p->rlink->llink=p->llink;B．p->llink=p->llink->llink;p->llink->rlink=p;C．p->rlink->llink=p;p->rlink=p->rlink->rlink;D．p->rlink=p->llink->llink;p->llink=p->rlink->rlink;31．单链表的存储密度为__C____。A．大于1B．等于5C．小于1D．不能确定二．判断题1.线性表的逻辑顺序与存储顺序总是一致的。2.线性表的顺序存储结构比链式存储结构更好。3.线性表中的所有元素都有一个前驱元素和后继元素。（）（）（）4.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）5.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）6.）7.用一组地址连续的存储单元存放的元素一定构成线性表。（）8.（）9.顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）（）（）10.顺序表中所有结点的类型必须相同。11.对链表进行插入和删除操作时不必移动链表中结点。12.非空的双向循环链表中任何结点的前驱指针均不为空。（）13.据元素之间的逻辑顺序。（）（）14.单链表从任何一个结点出发，都能访问到所有结点。15.符号p->next出现在表达式中表示p）16.带表头结点的双向循环链表判空的条件是：first->rlink==（）三、综合应用题1.利用顺序表的操作，实现以下函数：1）从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2）从顺序表中删除第i个元素并由函数返回被删除元素的值，如果i不合理或顺序表为空则显示出错信息并退出运行。3）向顺序表中第i个位置插入一个新元素x。如果i不合理则显示出错信息并退出运行4）从顺序表中删除具有给定值x的所有元素。5）从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。如果s或t不合理或者顺序表为空，则显示错误信息并退出。6）从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出。7）将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表8）从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。2.请设计算法将不带头结点的单链表就地逆置。3.有一个单链表L（至少有1head，编写一个过程将L结点，如此等等。找出最小值结点，且打印该数值。若该数值是奇数，则将其与直接后继结点的数值交换。若该数值是偶数，则将其直接后继结点删除。5.给定（已生成）一个带表头结点的单链表，设head为头指针，结点的结为指针，试写出算法：按递增次序的结点存放归并后的单链表。表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：8.试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(Linklist&L)。9.已知两个单链表A和B，其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共lenA插入到单链表B的第j个元素之前。10.已知非空线性表由list11.带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合，两表中的元素皆为递增有序。请写一算法求A和B的并集AU元素仍保持递增有序，且要利用A和B的原有结点空间。12.已知两个链表A和B分别表示两个集合，其元素递增排列。编写一函数程序，求A与B的交集，并存放于A链表中。13.设计一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B才是C中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。下面的函数append（last，e）是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；在执行A-B运添加，当A-B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。typedefstructnode{intelement;structnode*link;}NODE;;NODE*A,*B,*C;NODE*append(NODE*last,inte){last->link=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){………}14.设一单向链表的头指针为key域，试设计算法，将此链表的记录按照key递增的次序进行就地排序。15.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于等于零的结点（链表A的元素类型为整型，要求B、C表利用A16.将一个带头结点的单链表A分解为两个带头结点的单链表A和AB保持其相对顺序不变。1）写出其类型定义。2）写出算法。17.两个整数序列A=a，a，a，…，a和B=b，b，b，…，b已经存入两2123m13n个单链表中，设计一个算法，判断序列B是否是序列A的子序列。）按顺序存于内存，每个元素都是整数，312n0…,x）变为（-x,-x,-x,coef，指数域exp和指针域next。现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。20．设用带头结点的双向循环链表表示的线性表为L=（a，a,a,…,a312n写出算法将L改造成：L=（a,a,…,a,…,a,a）.413n2结点和结点指针类型定义如下：typedefstructnode{ElemTypedata;Structnode*prior,next;}*DLinkList;21.设有一个头指针为L的带有表头结点的非循环双向链表，其每个结点中除有频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值增1，并使此链表的Locate（L，x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。第三章栈和队列一．选择题1.在一个具有ntop作为栈顶指针，则当做退栈处理时，top变化为A．top不变B．top＝top-n。C．top＝top-1D．top=top+12.在一个顺序存储的循环队列中，队首指针指向队首元素的A．前一个位置B．后一个位置C．队首元素位置3.若进栈序列为A．3,4,2,1B．2,4,3,1C．1,4,2,3。D．队尾元素位置不可能是一个出栈序列。D．3,2,1,44.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是。=rear+1=rear=rear5.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行=0。A．hs->next=s;C．s->next=hs;hs=s;6.下列说法哪个正确：_______B．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;A．堆栈是在两端操作、先进后出的线性表B．堆栈是在一端操作、先进先出的线性表C．队列是在一端操作、先进先出的线性表D．队列是在两端操作、先进先出的线性表7.栈和队列的共同点_______A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点8.以下数据结构中哪一个是非线性结构？_______A．队列B．栈C．线性表D．二叉树9.若已知一个栈的入栈序列是，…，pn，若p1=n，则pi为_______A．iB．n=iC．n-i+1D．不确定10.当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_______语句修改top指针。A．top++11.4个元素进S栈的顺序是A,B,C,D,经运算POP(S)后栈顶元素是_______A．AB．BC．CD．D12.一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_______B．top--C．top=0D．topA.edcbaB.decbaC.dceabD.abcde13．设用链表作为栈的存储结构则退栈操作_______。A．必须判别栈是否为满C．判别栈元素的类型B．必须判别栈是否为空D．对栈不作任何判别14．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是_______。A．n-iB．n-1-iC．n+1-i15．递归函数f(n)=f(n-1)十n(n>1)的递归出口是_______。D．不能确定A．f(1)=016．中缀表达式A-(B+C／D)*E的后缀形式是_______。A．ABC+D／*E-B．ABCD／+E*-C．AB-C+D／E*B．f(1)=1C．f(0)=1D．f(n)=nD．ABC-+D/E*17.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？A.15B.14C.16D.2118.字符A依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_______个不同的字符串？A.1419．判定一个循环队列QU(最多元素为m0)为满队列的条件是_______A．QU->front==QU->rearB．QU->front!=QU->rearB.5C.6D.8C．QU->front==(QU->rear+1)％m0D．QU->front!=(QU->rear+1)％m020.以下哪一个不是队列的基本运算？_______A.在队列第i个元素之后插入一个元素C.判断一个队列是否为空B.从队头删除一个元素D.读取队头元素的值21．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E6、E5和E1，则栈S的容量至少应该是_______。A．6B．4C．322.用链接方式存储的队列，在进行插入运算时_______。D．2A.仅修改头指针C.仅修改尾指针B.头、尾指针都要修改D.头、尾指针可能都要修改23.若用一个大小为6rear和front的值分别为0和和front的值分别为_______？A.1和524．将一个递归算法改为对应的非递归算法时，通常需要使用_______。A.栈B.队列C.循环队列D.优先队列B.2和4C.4和2D.5和125．在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是_______。A.(front-rear+1)%mC．(front-rear+m)%m二．填空题B.(rear-front+1)%mD.(rear-front+m)%m1.栈和队列分别称为_____________的线性表。2.栈结构允许进行删除操作的一端为_____________。3.向一个由HS指向的链栈中插入一个结点时p不空而且无需回收被删除结点）。4.位置插入和删除元素；对于栈只能在____________插入和删除元素；对于队列只能在________插入和_______删除元素。5.栈是一种特殊的线性表，允许插入和删除运算的一端称为___________。不允许插入和删除运算的一端称为_____________。6.栈又称为_______________表，队列又称为___________表。7.当用长度为N满的条件是_____________________。8.9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。10.(a+b)*c+(e*f-h)/(q+r)+3的后缀表达式为__________________________。11.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。三．判断题1.栈是一种线性结构。（）2.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）（）（）（）3.栈是一种插入和删除操作在表的一端进行的线性表。4.出栈序列为abcd，则入栈序列可能是bcda。5.一个栈的输入序列是12345，则栈的输出序列不可能是12345。6.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）7.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。8.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）（）9.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）10.指针。（）（）11.高级语言中通常利用“递归工作栈”来处理递归。四、简答题1.简述栈与队列的相同点与不同点。队列结构？3.写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Pop(S,x);Pop(S,x);Push(S,‘a’);Push(S,y);Push(S,‘t’);Push(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}4.简述以下算法的功能（栈的元素类型SElemType为int）。(1)statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}(2)statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}五．程序算法题1.设头指针），试编写相应的入队列、出队列算法。2.设计一个输出如下形式数值的递归算法。444433322pp1p3.试证明：若借助栈由输入序列12…n得到的输出序列为(它是输入序n2列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使ppp<<。kij表达式求值时操作数栈和运算符栈的变化过程：A-B×C/D+E↑F个函数decpair(exp,flag)；其中exp为表示算术表达式的字符串变量，flag用于返回是否匹配的结果。6.编写一个算法，利用队列的基本运算返回指定队列中的最后一个元素。7.如果用一个循环数组qu[0..m-1]表示队列时，该队列只设置一个头指针0front，设置计数器count用以记录队列中的结点个数。要求：（1）编写实现队列的5个基本运算；（2）队列中能容纳的元素最大个数为多少？8.假定用一个循环单链表表示队列，该队列只设置队尾指针rear，编写函数：（1）向循环链队列中插入一个元素为x的结点；（2）从循环链队列中删除一个结点。第四章串一．选择题1.如下陈述中正确的是________。A．串是一种特殊的线性表C．串中元素只能是字母2.字符串的长度是指________。A．串中不同字符的个数C．串中所含字符的个数B．串的长度必须大于零D．空串就是空白串B．串中不同字母的个数D．串中不同数字的个数3.两个字符串相等的充要条件是________。A．两个字符串的长度相等C．同时具备A和B两个条件4.串是________。B．两个字符串中对应位置上的字符相等D．以上答案都不对A．不少于一个字母的序列C．不少于一个字符的序列B．任意个字母的序列D．有限个字符的序列5.下列关于串的叙述中，正确的是________。A．串长度是指串中不同字符的个数B．串是n个字母的有限序列C．如果两个串含有相同的字符，则它们相等D．只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等6.串是一种特殊的线性表，其特殊性体现在________。A．可以顺序存储C．可以链接存储7.设有两个串p和q，求q在p中首次出现的位置的运算称作________。B．数据元素是一个字符D．数据元素可以是多个字符A．连接B．模式匹配C．求子串D．求串长8.设串s1="ABCDEFG",s2="PQRST",函数con(x,y)返回x和y串的连接串。s的从序号i的字符开始的j返回串s的长度，则的结果串是________。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF9．函数substr("DATASTRUCTURE"，5，9)的返回值为________。B．"DATA"A．"STRUCTURE"C．"ASTRUCTUR"D."DATASTRUCTURE"10．设串S="IAMATEACHER",其长度是________。A.16B.11C.1411.设字符串s1="abcdefg",s2="pqrst"，则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为________。A."bcdef"B."bcdefg"C."bcpqrst"D."bcdefef"1312.设有一个字符串S="windows"，求子串的数目是________。D.15A．25B．26C．27D.28二.填空题1._______________称为空串；_______________________称为空白串。2.一个串的任意个连续的字符组成的子序列称为该串的______，包含该子串的串称为____。三．简答题1．空串与空格串有什么区别？字符串中的空格有什么意思？空串在串的处理中有什么作用？2．串是由字符组成的，长度为1的串和字符是否相同？为什么？3．简述串的静态顺序存储结构与动态顺序存储结构有什么区别，分别写出它们的结构体定义。4．字符串采用静态顺序存储结构。编写一个算法删除S中第i个字符到第j个字符。5．编写一个算法判断s2是否是s1的子串。6.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。intindex(chars[],chart[]){inti=0,j=0;while(i<strlen(s)&&j<strlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i=_______;j=______;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}第五章数组和广义表一．选择题1．在二维数组A中引用A[i,j]的时间_________。A．与i、j的大小有关B．与i、j的大小无关C．与i的大小有关，与j的大小无关D．与i的大小无关，与j的大小有关2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。A．行号B．列号C．元素值D.地址3．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。A．4704．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。A．行号B．列号C．元素值D.地址5．下面的说法中，不正确的是________。B．471C．472D.473A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。A．表达变得简单B．对矩阵元素的存取变得简单D．减少不必要的存储空间的开销C．去掉矩阵中的多余元素7．若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了________个数组元素。A．n28.稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。A.行号B.列号C.元素值D.元素总数9．稀疏矩阵一般的压缩存储方法有两种，即________。B．n*(n-1)C．n*(n+1)／2D．n*(n-1)A．二维数组和三维数组C.三元组和十字链表B．三元组和散列D．散列和十字链表10．有一个10阶对称矩阵A，采用压缩存储方式(以行序为主存储，且A[0Ⅱ0]=1)，则A[8][5]的地址是________。A．5211.数组通常具有的两种基本操作是________。A．建立与删除B．索引和修改C．查找和修改B．48C．54D．53D．查找与索引12．二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到j的范围从1到M至少需要________个字节。A．90B．180C．240D．54013．二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4j的范围从0到5,M按行存储时元素M[3Ⅱ5]的起始地址与M按列存储时元素________的起始地址相同。A．M[2][4]B．M[3][4]C．M[3][5]D.M[4][4]14．下面的说法中，不正确的是________。A．数组是一种线性表结构B．数组是一种定长的线性表结构，C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D．数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作15．数组的逻辑结构不同于下列________的逻辑结构。A．线性表B．栈C．队列D.树16．设有一个10阶的下三角矩阵顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为________。A．10B．19C．28D.5517．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为________。A．100B．40C．55D.80A一维数组B[1，n(n+1)/2]中。下三角部分中任一元素A(i>=j),在一维数组Bij中的下标位置是________。A．i(i-1)/2+j-1C．i(i+1)/2+j-1B．i(i-1)/2+jD.i(i+1)/2+j19.三维数组2个存A[3][4][5]的存储地址为________。A．356B．358C．36020.二维数组Amn按行序为主序存放在内,每个数组元素占1个存储单元,D.362则元素A的地址计算公式是:________。ijA．loc(A)=loc(A)+[(i-1)*m+(j-1)]ij11B．loc(A)=loc(A)+[(j-1)*m+(i-1)]ij11C．loc(A)=loc(A)+[(i-1)*n+(j-1)]ij11D.loc(A)=loc(A)+[(j-1)*n+(i-1)]ij1121.广义表(a,b,c,d)的表头是________。.A．aB．(a)C．a,b,c22.若广义表K满足head(K)=tail(K),则K为________。A.()B.(())C.(()),(())D.((),(),())D.(a,b,c)23.设一个广义表中结点的个数为n,则广义表深度算法的时间复杂度为________。A.O(1)B.O(n)C.O(n)2D.O(logn)224.下列广义表中，深度为2的有________。A.(a，b)B.((c，(a，b))，d)C.(c，(a，b))D.((a，b)，(c，(a，b)))25.广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为________。A.(g)B.(d)C.cD.d二.填空题1.设有一个n阶的下三角矩阵n(n+1)/2A[i][j]与A[0][0]之间有_______个数据元素。AA的长度为3i从1到j从1到10，从首地址100开始连续存放在存储器内，该数组若按行主序存放时，元素A[8][5]的起始地址为A[8][5]的起始地址为__________。3.假设有二维数组A[6][8]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为________；末尾元素A的第一个字节地址为________；若按行存储时，元57素A的第一个字节地址为_________；若按列存储时，元素A的第一个字节14地址为__________。474.若一个n阶矩阵A=A(0<=i,j<=n-1)则称A为________jiij矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为__________。5.已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail(A)))=________。6.一个广义表中的元素分为________元素和________元素两类。7.稀疏矩阵中第2行3列的元素值是5，它的三元组是________。8.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。9.广义表A=(a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。10．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____________。11．设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为___________。________优先存储。13.设广义表L的长度是________；L的深度是________。14.设广义表head(L)是______；tail(L)是___。三.判断题1.在C）））4.已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。（）5.）6.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形）7.）8.）9.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（）10.）四.简答题1．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？2．什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？3．什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？4．已知稀疏矩阵如下：请写出该稀疏矩阵三元组表示。5.请写出下面链表表示的广义表。6.画出广义表list=(5,(3,2,(14,9,3),(),4),2,(6,3,10))的链表表示。五.程序设计题1.设计一个算法求广义表的深度。（1）求数组A靠边元素之和；C.n+1A．207.一棵具有5层满二叉树中结点总数为________。A．31B.32C.3310.把一棵深度4的左单支二叉树改造成完全二叉树时，要增添A．10B．8C．6D．4个空结点。1编号为i结点的左孩子结点的编号为________。A．2i+1B.2iC.i/2D.2i-112.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为________。A.前序遍历B.后序遍历C.中序遍历D.层次遍历13.已知一棵二叉树的前序遍历结果为ABCDEF序遍历的结果为________。A．CBEFDAB.FEDCBAC.CBEDFAD.不定14.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是________。A．acbedB．decabC．deabcD．cedba15.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n中任一结点号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按编号。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次遍历序列16.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是________的二叉树。A.空或只有一个结点C.任一结点无左孩子B.高度等于其结点数D.任一结点无右孩子17.由前序序列和中序序列________唯一确定一棵二叉树。A．能B.不能C.不一定18.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分棵树对应的二叉树。下面结论正确的是________。A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对19.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为2n个，其中________个用于指向孩子结点。A．n-1B.nC.n+1D.n-220.设F是由和T3F对应的二叉树为和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为________。A．N1-1B.N2-1C.N2+N3D.N1+N321.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为__A.23___。B.37C.44D.4622.n个权构成一棵Huffman树，其结点总数为__________。A．2n-1B.2nC.2n+1D.不确定二、填空题1.在一棵二叉树中，度为0的结点的个数为n，度为2的结点的个数为n，20则：n=0。2．结点数为7的二叉树的高度最矮是_______，最高是_______。3．给定二叉树的结点数，要使树高为最大，那么该树应该是_______形状。4．给定二叉树的结点数，要使树高为最矮，那么该树应该是_______形状。5．如果一棵满二叉树的深度为7_______个叶结点。6．深度为5的二叉树，至多有_______个结点。7．深度为k的完全二叉树至少有_______个结点，至多有_______个结点。8．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______个9.设二叉树中度数为0的结点数为1的结点数为总共有_______个结点。10.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是___________________________。11.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。12.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从188的左孩子结点的编号是_______。13.设哈夫曼树中共有n个结点，则该哈夫曼树中有_____个度数为1的结点。14.Huffman树为____，其带权路径长度为_________。15.设一棵Huffman树有6个叶结点，权值分别为结点的权值是_______。16.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_________。三、综合应用题1.这棵树并回答下面问题：（1）树的根节点是哪个，哪些是叶子结点，哪些是非终端结点。（2）树的深度是多少，各个结点的层数是多少。（3）对于G结点，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。2.设二叉树如下图所示，分别写出它的先序遍历、中序遍历、后序遍历序列。ABECFGDHJI3.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。4.某二叉树结点的中序序列为HBCDEFG，后序序列为BDCHFGE，请据此画出该二叉树，再给该树加上中序线索。5.请按照孩子-兄弟表示法，将下图所示树转化为二叉树。ABCDEFG6.若7个带权结点，其权值分别为WPL及该树的结点总数。7.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：（1）什么是哈夫曼树？（2）根据题目所给频率值，画出相应的哈夫曼树。（3）给出各个字符对应的哈夫曼编码。（4）该段文字经过哈夫曼编码后，长度是多少。四、算法设计题1.设计一个求结点x在二叉树中的双亲结点的算法。2.设计判断两个二叉树是否相同的算法。3.设计计算二叉树中所有结点值之和的算法。4.设计求二叉树中值为x的结点所在的层号的算法。第七章图一．选择题1．任何一个无向连通图的最小生成树________。A．只有一棵B．有一棵或多棵D．可能不存在C．一定有多棵2．下列算法中，________算法用来求图中每对顶点之间的最短路径。A．DijkstraB．FloyedC．PrimD．Kruskal3．由N个顶点组成的有向图，最多可以有________条边。A．N*NB．N（N+1）C．N（N-1）D．N(N-1)/24．关键路径是结点网络中________。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路5．在一个图中，所有顶点的度数之和等于所有边数的________倍。A．2B．3C．1D．1.56.下面关于图的存储的叙述中正确的是________。A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关7.AOV网是一种________。A．有向图B．无向图C．无向无环图D．有向无环图8.在一个具有nn(n-1)/2n个顶点的有向完全图中，包含有________条边。A．n+29.设完全无向图中有n个顶点，则该完全无向图中有________条边。A．n(n-1)/2B．n(n-1)C．n(n+1)/2D．(n-1)/2B．n(n-1)C．n2D．2n10.设有向无环图G中的有向边集合则下列属于该有向图G的一种拓扑排序序列的是________。A．1，2，3，4C．1，4，2，3B．2，3，4，1D．1，2，4，311.设某无向图有n个顶点，则该无向图的邻接表中有________个表头结点。A．2nB．nC．n/2D．n(n-1)12.设无向图G中有n个顶点，则该无向图的最小生成树上有________条边。A．nB．n-1C．2nD．2n-113.设无向图G中的边的集合E={(a，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为________。A．aedfcbB．acfebdC．aebcfdD．aedfbc14.有n个顶点e条边的无向图G,它的邻接表中的表结点总数是________。A．2nB．nC．2eD．e15.连通图G中有n个顶点,G的生成树是________连通子图。A．包含G的所有顶点B．包含G的所有边C．不必包含G的所有顶点D．必须包含G的所有顶点和所有的边16.下面关于求关键路径的说法不正确的是________。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和D．关键活动一定在关键路径上17．设某强连通图中有n个顶点，则该强连通图中至少有________条边。A．n(n-1)B．n+1C．nD．n(n+1)18．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为________。A．nB．eC．2nD．2e19.设某有向图的邻接表中有n个表头结点和m条有向边。A．nB．n-1C．mD．m-120．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为________。A．第i行非0元素的个数之和C．第i行0元素的个数之和B．第i列非0元素的个数之和D．第i列0元素的个数之和21．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为________。A．O(n+e)22．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的________。A．先序遍历B．中序遍历C．后序遍历D．按层遍历23.可以判断一个有向图中是否含有环（回路）的方法为________。A．广度优先遍历B．拓扑排序C．求最短路径D．求关键路径24.采用邻接表存储的图的深度优先遍历算法类似于二叉树的________。A．先序遍历B．中序遍历C．后序遍历D．按层遍历B．O(n)C．O(ne)D．O(n)225.一个具有8的差为________。A．16B．8C．026．在有向图中每个顶点的度等于该顶点的________。D．2A.入度B.出度C.入度与出度之和D.入度与出度之差二．填空题1.在图G于该顶点的________，对于有向图来说等于该顶点的________。A出发按深度优先搜索遍历得到的顶点序列为________，按广度优先搜索遍历得到的顶点序列为________。ABCDEF┏011010┓A┃100011┃B┃100100┃C┃001001┃D┃110001┃E┗010110┛F3.有n个顶点的有向连通图最多有________条边，最少有________条边。4.具有n个顶点的完全无向图有________条边，完全有向图有________条边。5.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。6.设一个连通图G中有n个顶点e7.表示图的五种常用的存储结构为_______________________________。8.在有12个结点的无向图中，其边数最多为________条。9.设无向图G中有n个顶点和e头结点和_________个边结点。10.n个顶点的连通图至少____条边。11.在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。12.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于____。13.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。14.在一个具有10n个顶点的有向完全图中，包含有________条边。15.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。16.对于一个具有n个顶点和e所含边结点分别有_______个和________个。17.设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。18.设无向图对应的邻接矩阵为A中第i行上非0元素的个数_________第i列上非019.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。20.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。21.设无向图G中有n个顶点e度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。22.设某无向图G的邻接表为V1->3->2->4;V2->1->3;V3->1->2->4;V4->1->3;则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。23.设有向图G的二元组形式表示为G序列__________。24.AOV网以结点和有向边分别代表____________25.AOV网是一种___________________的图。三、判断题1.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）2.）3.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关）4.）5.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图）6.n个结点的有向图，若它有）7.））9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点）10.）11.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为）四．简答题1．对于一个有向图，不用拓扑排序，如何判定图中是否存在环？2．关？3.无向图给出该图的最小生成树。6.一个网络如下（2）求出它的一棵最小生成树并画出求解过程。7.已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示（1）画出该图的图形；（1）试画出该网。五．算法设计题第八章查找A．n/2,nB．(n+1)/2，n-1C．(n+1)/2，nD．(n-1)/2，n-1C．13.4A．散列存储C．压缩存储B．顺序存储或链接存储D．索引存储A．结点的输入顺序C.结点的取值范围B．结点的存储结构D．计算机的硬件18．对包含n个元素的散列表进行查找，平均查找长度________。A.O(logn)B.O(n)C.不直接依赖于nD.上述三者都不是219.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择________。A．小于等于m的最大奇数C．小于等于m的最大偶数B．小于等于m的最大素数D．小于等于m的最大合数20．设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择________。A．99B．97C．91D．9321.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做________次线性探测。A．n2B．n(n+1)C．n(n+1)/2D．n(n-1)/222.采用开放定址法处理散列表的冲突时，其平均查找长度________。A．低于链接法处理冲突B.高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找23.散列法存储的基本思想是根据A来决定B，碰撞（冲突）指的是C，处理碰撞的两类主要方法是D。供选择的答案：A，B：①存储地址②元素的符号③元素个数④关键码值⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素的关键码值不同，而非码属性相同③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法③除余法和折叠法④拉链法和开地址法24._____是HASH查找的冲突处理方法。A．求余法25.当αA.较慢B.较快C.相同B．平方取中法C．二分法D．开放地址法序查找，但前者比后者的查找速度________。A．必定快C．在大部分情况下要快B．不一定D．取决于表递增还是递减27.当采用分块查找时，数据的组织方式为________。A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序C．数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D．数据分成若干块，每块（除最后一块外）中数据个数需相同28．对二叉排序树进行_________遍历，可以得到该二叉树所有结点构成的有序序列。A．前序B．中序C．后序D．按层次29．一个哈希函数被认为是“好的”，如果它满足条件_________。A．哈希地址分布均匀B．保证不产生冲突C．所有哈希地址在表长范围内D．满足B和C30.哈希表的平均查找长度是__________的函数。B．表中元素的多少A．哈希表的长度C．哈希函数D．哈希表的装满程度31.平均查找长度最短的查找方法是____________。A．折半查找B．顺序查找C．哈希查找D．其他二.判断题1.）2.）3.）4.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）5.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可）6.在散列存储中，装填因子α）7.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）8.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（）9.对于折半查找，其前提条件是待查找序列只要是有序的即可。（）三．填空题1.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。2.以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为________。3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_______个，比较两次查找成功有结点数有_________个。4.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。5.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点的结点数为________，则比较四次查找成功的结点数为________，比较五次________查找成功的结点数为，平均查找长度为________。6.对于长度为n分法查找，则时间复杂度为________。7.根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为_________。8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。9.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。10.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。11.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最程的时间复杂度为____________，空间复杂度为___________。12.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度___________。13.Hash技术关键是________和________两个方面14.在散列存储中，装填因子a的值越大，则____；a的值越小，则____。15.在线性表的散列存储中，处理冲突的常用方法有_______和_______两种。四.简答题1.什么叫动态查找？什么叫静态查找？什么样的存储结构适宜于进行静态查找？什么样的存储结构适宜于进行动态查找？2．什么叫平均查找长度？写出平均查找长度的定义.(2)依此二叉排序树，如何得到一个从小到大的有序序列？4．若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。H(key)=keyMOD13和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。序树并给出构造过程。7.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。8.设散列表的长度为8，散列函数H(k)=kmod7，初始记录关键字序列为(25，法的平均查找长度。9.设有一组关键字，其出现次序为：105，97，28，52，37，22，16，90，45，76，59，74，采用哈希函数为H(key)=keyMOD13,试在0~14的散列地址空间中对该关键字序列构造哈希表。(1)采用线性探测再散列解决冲突。(2)采用二次探测再散列解决冲突。10．给定关键码序列(11,81,23,59,17,19,68)，散列表长度为11，散列函数为H(key)=(5*key)%11，用二次探查法解决冲突，试画出插入所有关键码后得到的散列表，并计算查找成功与查找不成功时的平均搜索长度六．设计题1.设计在顺序有序表中实现二分查找的算法(递归与非递归)。2.设计判断二叉树是否为二叉排序树的算法。3.设计求结点在二叉排序树中层次的算法。4.设计一个算法将二叉排序树按递减次序打印输出。5.设计在二叉排序树上查找结点X的算法。6.设计在有n个结点的顺序表中查找最小的k（1≤k≤n）个结点。一、选择题1.下述排序算法中，稳定的是________。．直接选择排序2.下列排序算法中，________需要的辅助存储空间最大。．快速排序．插入排序C．希尔排序3.下列排序算法中，________是稳定的。．插入、希尔．冒泡、快速4.下列各种排序算法中平均时间复杂度为O(n的是________。．直接插入排序C．快速排序．堆排序．归并排序C．选择、堆排序．基数、归并2．快速排序5.在待排序的元素基本有序的前提下，效率最高的排序方法是________。．简单插入排序．简单选择排序C．快速排序．归并排序6.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为_______。．O(n)．O(nlogn)C．O(n)．O(logn)7.对n个记录进行堆排序，所需要的辅助存储空间为________。．O(1ogn)．O(n)C．O(1)．O(n)8.快速排序在最坏情况下的时间复杂度为________。．O(logn)B．O(nlogn)C．O(n)．堆排序C．归并排序．冒泡排序22222．O(n)2229.设有序列12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为________。．3．4C．5．610.对数据元素序列(49,72,68,13,38,50,97,27排序，前三趟排序结束时的结果依次为：第一趟：13,72,68,49,38,50,97,27；第二趟：13,27,68,49,38,50,97,72；第三趟：13,27,38,49,68,50,97,72；该排序采用的方法是_________。A.直接插入排序B.直接选择排序C.冒泡排序D.堆排序11.发生颠倒，则称该排序算法是不稳定的。________就是不稳定的排序方法。．起泡排序B．归并排序C．直接插入排序．简单选择排序12.设一组初始记录关键字的长度为8，则最多经过________趟插入排序可以得到有序序列。．6．7C．8．913.设一组初始记录关键字序列为CPMSR，则按字母升序的第一趟冒泡排序结束后的结果是________。．，，C，，P，，M，，R，S，，X．P，，C，S，，，，，R，，M，YC．，，C，R，，，M，S，，P，，X．，C，，P，，M，S，R，，，，Y14.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做________排序。．插入．堆C．快速．归并15.每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。．插入B．堆C．快速．归并16.下列________种排序算法的平均时间复杂度为O(nlog。2．简单选择排序17.下列________种排序算法更适合于外部排序。．选择排序B．插入排序C．冒泡排序．简单插入排序C．冒泡排序D．归并排序．归并排序18.设一组初始记录关键字序列，2，6，3，，以第一个记录关键字5为基准进行一趟快速排序的结果为________。．2，3，5，8，6C．3，2，5，6，8．3，2，5，8，6．2，3，6，5，819.二路归并排序的时间复杂度为________。．O(n)．O(n)C．O(nlogn)20.时间复杂度不受数据初始状态影响而恒为O(nlog的是________。．O(logn)2222．堆排序21.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是________。．堆排序．冒泡排序C．快速排序．希尔排序．冒泡排序C．希尔排序．快速排序22.设有500010个记录关键字，则用下列________方法可以达到此目的。．快速排序B．堆排序C．归并排序．插入排序23.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为________。．10，15，14，18，20，36，40，21．10，15，14，18，20，40，36，21C．10，15，14，20，18，40，36，2l．15，10，14，18，20，36，40，2124.设一组初始记录关键字序列为(345253674924627)，则用基数排序需要进行________趟的分配和回收才能使得初始关键字序列变成有序序列。．3．4C．5．825．设一组初始记录关键字序列为(5040952015706045)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为________。．40，50，20，95C．15，20，40，45．15，40，60，20．45，40，15，2026.设一组初始记录关键字序列为(2550153580203670)，其中含有5个长度为2一趟归并后的结果为________。．15，25，35，50，20，40，80，85，36，70．15，25，35，50，80，20，85，40，70，36C．15，25，35，50，80，85，20，36，40，70．15，25，35，50，80，20，36，40，70，8527.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为__________的结点开始。．100．12C．60D．1528.一组记录的排序码为（46，79，56，38，40，84），则堆排序时建立的初始大顶堆为________。．79，46，56，38，40，80C．84，79，56，38，40，46．38，46,56，79，40，84．84，56，79，40，46，38二、填空题1.为增量的一趟希尔排序结束后的结果为_______。2.对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡多需要进行______趟排序才可以完成。3.排序的平均时间复杂度为________。4.个堆排序过程的时间复杂度为________。5.对n个元素的序列进行起泡排序时，最少的比较次数是_______。6.本反序，则选用_______。7.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_______。8.序结束后的结果是________。9.序结束后的结果是_______。10.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_______。11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_________。12.排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时