还剩75页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第一章概论
一、选择题
1、研究数据结构就是研究(D)A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构、存储结构及其基本操作
2、算法分析的两个主要方面是(A)A.空间复杂度和时间复杂度B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性
3、具有线性结构的数据结构是(D)A.图B.树C.广义表D.栈
4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、(B)等5个特性A.可执行性、可移植性和可扩充性B.可执行性、有穷性和确定性C.确定性、有穷性和稳定性D.易读性、稳定性和确定性
5、下面程序段的时间复杂度是(C)fori=0;im;i++forj=0;jn;j++a[i][j]=i*j;A.Om2 B.On2C.Om*nD.Om+n
6、算法是(D)A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列
7、某算法的语句执行频度为(3n+nlog2n+n2+8)其时间复杂度表示(C)A.OnB.Onlog2nC.On2D.Olog2n
8、下面程序段的时间复杂度为(C)i=1;whilei=ni=i*3;A.OnB.O3nC.Olog3nD.On
39、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的()和运算等的学科A.结构B.关系C.运算D.算法
10、下面程序段的时间复杂度是(A)i=s=0;whilesn{i++;s+=i;}A.OnB.On2C.Olog2nD.On
311、抽象数据类型的三个组成部分分别为(A)A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型
12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是()A.正确性算法应能正确地实现预定的功能B.易读性算法应易于阅读和理解,以便调试、修改和扩充C.健壮性当环境发生变化时,算法能适当地做出反应或进行处理,不会产生不需要的运行结果D.高效性即达到所需要的时间性能
13、下列程序段的时间复杂度为(B)x=n;y=0;whilex=y+1*y+1y=y+1;A.OnB.C.O1D.On2
二、填空题
1、程序段“i=1;whilei=ni=i*2;”的时间复杂度为
2、数据结构的四种基本类型中,树形结构的元素是一对多关系
三、综合题
1、将数量级O1ONON2ON3ONLOG2NOLOG2NO2N按增长率由小到大排序答案O1Olog2NONONlog2NON2ON3O2N第二章线性表
一、选择题
1、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度()A.Olog2nB.O1C.OnD.On
22、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用()存储方式最节省时间A.顺序表B.单链表C.双链表D.单循环链表
3、具有线性结构的数据结构是()A.图B.树C.广义表D.栈
4、在一个长度为n的顺序表中,在第i个元素之前插入一个新元素时,需向后移动()个元素A.n-iB.n-i+1C.n-i-1D.i
5、非空的循环单链表head的尾结点p满足()A.p-next==headB.p-next==NULLC.p==NULLD.p==head
6、链表不具有的特点是()A.可随机访问任一元素 B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比
7、在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,修改指针的操作是()A.p-next=q;q-prior=p;p-next-prior=q;q-next=q;B.p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C.q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D.q-next=p-next;q-prior=p;p-next=q;p-next=q;
8、线性表采用链式存储时,结点的存储地址()A.必须是连续的B.必须是不连续的C.连续与否均可D.和头结点的存储地址相连续
9、在一个长度为n的顺序表中删除第i个元素,需要向前移动()个元素A.n-iB.n-i+1C.n-i-1D.i+
110、线性表是n个()的有限序列A.表元素B.字符C.数据元素D.数据项
11、从表中任一结点出发,都能扫描整个表的是()A.单链表B.顺序表C.循环链表D.静态链表
12、在具有n个结点的单链表上查找值为x的元素时,其时间复杂度为()A.OnB.O1C.On2D.On-
113、线性表L=a1a2……an,下列说法正确的是()A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继
14、一个顺序表的第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的存储地址是()A.98B.100C.102D.
10615、在线性表的下列存储结构中,读取元素花费的时间最少的是()A.单链表B.双链表C.循环链表D.顺序表
16、在一个单链表中,若删除p所指向结点的后续结点,则执行()A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p=p-next;D.p=p-next-next;
17、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为()A.O1B.OnC.OmD.Om+n
18、线性表的顺序存储结构是一种()存储结构A.随机存取B.顺序存取C.索引存取D.散列存取
19、顺序表中,插入一个元素所需移动的元素平均数是()A.n-1/2B.nC.n+1D.n+1/
210、循环链表的主要优点是()A.不再需要头指针B.已知某结点位置后能容易找到其直接前驱C.在进行插入、删除运算时能保证链表不断开D.在表中任一结点出发都能扫描整个链表
11、不带头结点的单链表head为空的判定条件是(A)A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL答案B是带头结点的
12、在下列对顺序表进行的操作中,算法时间复杂度为O1的是()A.访问第i个元素的前驱
(1)B.在第i个元素之后插入一个新元素C.删除第i个元素D.对顺序表中元素进行排序答案是A.假设顺序表L长度为n,求第i个节点L[i]直接前驱L[i-1]因此为O
(1)答案B需要移动n-i+1个节点,因此为On答案C也需要移动n-i个节点答案D根据排序方法不同最慢On^2,最快Onlogn
13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为()A.q-next=s-next;s-next=p;B.s-next=p;q-next=s-next;C.p-next=s-next;s-next=q;D.s-next=q;p-next=s-next;
14、在以下的叙述中,正确的是()A.线性表的顺序存储结构优于链表存储结构 B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构
15、在表长为n的顺序表中,当在任何位置删除一个元素的概率相同时,删除一个元素所需移动的平均个数为()A.n-1/2B.n/2C.n+1/2D.n
16、在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入一个结点s,则执行()A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;
17、在单链表中,指针p指向元素为x的结点,实现删除x的后继的语句是()A.p=p-next;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;
18、在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若p-next-next==head,则()A.p指向头结点 B.p指向尾结点C.p的直接后继是头结点D.p的直接后继是尾结点
二、填空题
1、设单链表的结点结构为(datanext)已知指针p指向单链表中的结点,q指向新结点,欲将q插入到p结点之后,则需要执行的语句;答案q-next=p-nextp-next=q
2、线性表的逻辑结构是,其所含元素的个数称为线性表的答案线性结构长度
3、写出带头结点的双向循环链表L为空表的条件答案L-prior==L-next==L
4、带头结点的单链表head为空的条件是答案head-next==NULL
5、在一个单链表中删除p所指结点的后继结点时,应执行以下操作q=p-next;p-next=_q-next___;
三、判断题
1、单链表不是一种随机存储结构
2、在具有头结点的单链表中,头指针指向链表的第一个数据结点
3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针
4、顺序存储方式只能用于存储线性结构
5、在线性表的顺序存储结构中,逻辑上相邻的两个元素但是在物理位置上不一定是相邻的
6、链式存储的线性表可以随机存取X
四、程序分析填空题
1、函数GetElem实现返回单链表的第i个元素,请在空格处将算法补充完整intGetElemLinkListLintiElemtype*e{LinkListp;intj;p=L-next;j=1;whilepji{1;++j;}if!p||jireturnERROR;*e=2;returnOK;}答案1p=p-next2p-data
2、函数实现单链表的插入算法,请在空格处将算法补充完整intListInsertLinkListLintiElemTypee{LNode*p*s;intj;p=L;j=0;whilep!=NULLji-1{p=p-next;j++;}ifp==NULL||ji-1returnERROR;s=LNode*mallocsizeofLNode;s-data=e;1;2;returnOK;}/*ListInsert*/答案1s-next=p-next2p-next=s
3、函数ListDelete_sq实现顺序表删除算法,请在空格处将算法补充完整intListDelete_sqSqlist*Linti{intk;ifi1||iL-lengthreturnERROR;fork=i-1;kL-length-1;k++L-slist[k]=
(1);
(2);returnOK;}答案
(1)L-slist[k+1]
(2)--L-Length
4、函数实现单链表的删除算法,请在空格处将算法补充完整intListDeleteLinkListLintiElemType*s{LNode*p*q;intj;p=L;j=0;while
(1)ji-1{p=p-next;j++;}ifp-next==NULL||ji-1returnERROR;q=p-next;
(2);*s=q-data;freeq;returnOK;}/*listDelete*/答案1p-next!=NULL2p-next=q-next
5、写出算法的功能intLhead{node*head;intn=0;node*p;p=head;whilep!=NULL{p=p-next;n++;}returnn;}答案求单链表head的长度
五、综合题
1、编写算法,实现带头结点单链表的逆置算法答案voidinventLnode*head{Lnode*p*q;if!head-nextreturnERROR;p=head-next;q=p-next;p-next=NULL;whileq{p=q;q=q-next;p-next=head-next;head-next=p;}}
2、有两个循环链表,链头指针分别为L1和L2,要求写出算法将L2链表链到L1链表之后,且连接后仍保持循环链表形式答案voidmergeLnode*L1Lnode*L2{Lnode*p*q;whilep-next!=L1p=p-next;whileq-next!=L2q=q-next;q-next=L1;p-next=L2;}
3、设一个带头结点的单向链表的头指针为head,设计算法,将链表的记录,按照data域的值递增排序答案voidassendingLnode*head{Lnode*p*q*r*s;p=head-next;q=p-next;p-next=NULL;whileq{r=q;q=q-next;ifr-data=p-data{r-next=p;head-next=r;p=r;}else{while!pr-datap-data{s=p;p=p-next;}r-next=p;s-next=r;}p=head-next;}}
4、编写算法将一个头指针为head不带头结点的单链表改造为一个单向循环链表,并分析算法的时间复杂度答案voidlinklist_cLnode*head{Lnode*p;p=head;if!preturnERROR;whilep-next!=NULLp=p-next;p-next=head;}设单链表的长度(数据结点数)为N,则该算法的时间主要花费在查找链表最后一个结点上(算法中的while循环),所以该算法的时间复杂度为O(N)
5、已知head为带头结点的单循环链表的头指针,链表中的数据元素依次为(a1,a2a3a4…an)A为指向空的顺序表的指针阅读以下程序段,并回答问题
(1)写出执行下列程序段后的顺序表A中的数据元素;
(2)简要叙述该程序段的功能ifhead-next!=head{p=head-next;A-length=0;whilep-next!=head{p=p-next;A-data[A-length++]=p-data;ifp-next!=headp=p-next;}}答案1a2a4…2将循环单链表中偶数结点位置的元素值写入顺序表A
6、设顺序表va中的数据元数递增有序试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性答案voidInsert_sqSqlistva[]ElemTypex{intijn;n=lengthva[];ifx=va[i]va[n]=x;else{i=0;whilexva[i]i++;forj=n-1;j=I;j--va[j+1]=va[j];va[i]=x;}n++;}
7、假设线性表采用顺序存储结构,表中元素值为整型阅读算法f2,设顺序表L=373211873写出执行算法f2后的线性表L的数据元素,并描述该算法的功能voidf2SeqList*L{intijk;k=0;fori=0;iL-length;i++{forj=0;jkL-data[i]!=L-data[j];j++;ifj==k{ifk!=iL-data[k]=L-data[i];k++;}}L-length=k;}答案37218删除顺序表中重复的元素
8、已知线性表中的元素以值递增有序排列,并以单链表作存储结构试写一算法,删除表中所有大于x且小于y的元素(若表中存在这样的元素)同时释放被删除结点空间答案voidDelete_listLnode*headElemTypexElemTypey{Lnode*p*q;if!headreturnERROR;p=head;q=p;while!p{ifp-dataxp-datay}i++;ifp==head{head=p-next;freep;p=head;q=p;}else{q-next=p-next;freep;p=q-next;}else{q=p;p=p-next;}}}
9、在带头结点的循环链表L中,结点的数据元素为整型,且按值递增有序存放给定两个整数a和b,且ab,编写算法删除链表L中元素值大于a且小于b的所有结点第三章栈和队列
一、选择题
1、一个栈的输入序列为a,b,c,d,e,则栈的不可能输出的序列是()A.abcdeB.decbaC.dceabD.edcba
2、判断一个循环队列Q(最多n个元素)为满的条件是()A.Q-rear==Q-frontB.Q-rear==Q-front+1C.Q-front==Q-rear+1%nD.Q-front==Q-rear-1%n
3、设计一个判别表达式中括号是否配对的算法,采用()数据结构最佳A.顺序表B.链表C.队列D.栈
4、带头结点的单链表head为空的判定条件是()A.head==NULL B.head-next==NULLC.head-next!=NULLD.head!=NULL
5、一个栈的输入序列为1234,则栈的不可能输出的序列是()A.1243B.2134C.1432D.4312E.
32146、若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0,3当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为()A.1和5B.2和4C.4和2D.5和
17、队列的插入操作是在()A.队尾B.队头C.队列任意位置D.队头元素后
8、循环队列的队头和队尾指针分别为front和rear,则判断循环队列为空的条件是()A.front==rearB.front==0C.rear==0D.front=rear+
19、一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是()A.*S-top=e;S-top++;B.S-top++;*S-top=e;C.*S-top=eD.S-top=e;
10、表达式a*b+c-d的后缀表达式是()A.abcd+- B.abc+*d-C.abc*+d-D.-+*abcd
11、将递归算法转换成对应的非递归算法时,通常需要使用()来保存中间结果A.队列B.栈C.链表D.树
12、栈的插入和删除操作在()A.栈底B.栈顶C.任意位置D.指定位置
13、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到()的编组A.3,4,5,1,2B.2,4,1,3,5C.3,5,4,2,1D.1,3,5,2,
414、判定一个顺序栈S(栈空间大小为n)为空的条件是()A.S-top==0B.S-top!=0C.S-top==nD.S-top!=n
15、在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为()A.front=front-nextB.s-next=rear;rear=sC.rear-next=s;rear=s;D.s-next=front;front=s;
16、一个队列的入队序列是1,2,3,4,则队列的出队序列是()A.1,2,3,4 B.4,3,2,1C.1,4,3,2D.3,4,1,
217、依次在初始为空的队列中插入元素abcd以后,紧接着做了两次删除操作,此时的队头元素是()A.aB.bC.cD.d
18、正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是()A.top不变B.top=0C.top=top+1D.top=top-
119、判断一个循环队列Q(空间大小为M)为空的条件是()A.Q-front==Q-rearB.Q-rear-Q-front-1==MC.Q-front+1=Q-rearD.Q-rear+1=Q-front
20、设计一个判别表达式中左右括号是否配对出现的算法,采用()数据结构最佳A.线性表的顺序存储结构B.队列C.栈D.线性表的链式存储结构
21、当用大小为N的数组存储顺序循环队列时,该队列的最大长度为()A.N B.N+1C.N-1D.N-
222、队列的删除操作是在()A.队首 B.队尾C.队前D.队后
23、若让元素1,2,3依次进栈,则出栈次序不可能是()A.3,2,1 B.2,1,3C.3,1,2D.1,3,
224、循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是()A.rear-front+m%mB.rear-front+1C.rear-front-1D.rear-front
25、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印该缓冲区应该是一个()结构A.堆栈B.队列C.数组D.线性表
26、栈和队列都是()A.链式存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构
27、在一个链队列中,假定front和rear分别为队头指针和队尾指针,删除一个结点的操作是()A.front=front-nextB.rear=rear-nextC.rear-next=frontD.front-next=rear
28、队和栈的主要区别是()A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同
二、填空题
1、设栈S和队列Q的初始状态为空,元素e1e2e3e4e5e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2e4e3e6e5e1,则栈的容量至少应该是答案
32、一个循环队列Q的存储空间大小为M其队头和队尾指针分别为front和rear,则循环队列中元素的个数为答案rear-front+M%M
3、在具有n个元素的循环队列中,队满时具有个元素答案n-
14、设循环队列的容量为70,现经过一系列的入队和出队操作后,front为20,rear为11,则队列中元素的个数为答案
615、已知循环队列的存储空间大小为20,且当前队列的头指针和尾指针的值分别为8和3,且该队列的当前的长度为_______
三、判断题
1、栈和队列都是受限的线性结构
2、在单链表中,要访问某个结点,只要知道该结点的地址即可;因此,单链表是一种随机存取结构
3、以链表作为栈的存储结构,出栈操作必须判别栈空的情况
四、程序分析填空题
1、已知栈的基本操作函数intInitStackSqStack*S;//构造空栈intStackEmptySqStack*S;//判断栈空intPushSqStack*SElemTypee;//入栈intPopSqStack*SElemType*e;//出栈函数conversion实现十进制数转换为八进制数,请将函数补充完整voidconversion{InitStackS;scanf“%d”N;whileN{
(1);N=N/8;}while
(2){PopSe;printf“%d”e;}}//conversion答案
(1)PushSN%8
(2)!StackEmptyS
2、写出算法的功能intfunctionSqQueue*QElemType*e{ifQ-front==Q-rearreturnERROR;*e=Q-base[Q-front];Q-front=Q-front+1%MAXSIZE;returnOK;}
3、阅读算法f2并回答下列问题
(1)设队列Q=(1,3,5,2,4,6)写出执行算法f2后的队列Q;
(2)简述算法f2的功能voidf2Queue*Q{DataTypee;if!QueueEmptyQ{e=DeQueueQ;f2Q;EnQueueQe;}}答案
(1)642531
(2)将队列倒置
五、综合题
1、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列算法(用函数实现)答案voidEnQueueLnode*rearElemTypee{Lnode*new;New=Lnode*mallocsizeofLnode;If!newreturnERROR;new-data=e;new-next=rear-next;rear-next=new;rear=new;}
2、已知Q是一个非空队列,S是一个空栈编写算法,仅用队列和栈的ADT函数和少量工作变量,将队列Q的所有元素逆置栈的ADT函数有voidmakeEmptySqStacks;置空栈voidpushSqStacksElemTypee;元素e入栈ElemTypepopSqStacks;出栈,返回栈顶元素intisEmptySqStacks;判断栈空队列的ADT函数有voidenQueueQueueqElemTypee;元素e入队ElemTypedeQueueQueueq;出队,返回队头元素intisEmptyQueueq;判断队空答案voidQueueInventQueueq{ElemTypex;makeEmptySqStacks;while!isEmptyQueueq{x=deQueueQueueq;pushSqStacksElemTypex;}while!isEmptySqStacks{x=popSqStacks;enQueueQueueqElemTypex;}}
3、对于一个栈,给出输入项ABCD,如果输入项序列为ABCD,试给出全部可能的输出序列答案出栈的可能序列ABCDABDCACDBACBDADCBBACDBADCBCADBCDACBDACBADCDBADCBA第四章串
一、选择题
1、设有两个串S1和S2,求串S2在S1中首次出现位置的运算称作(C)A.连接B.求子串C.模式匹配D.判断子串
2、已知串S=’aaab’,则next数组值为(A)A.0123B.1123C.1231D.
12113、串与普通的线性表相比较,它的特殊性体现在(C)A.顺序的存储结构B.链式存储结构C.数据元素是一个字符D.数据元素任意
4、设串长为n,模式串长为m,则KMP算法所需的附加空间为(A)A.OmB.OnC.Om*nD.Onlog2m
5、空串和空格串(B)A.相同B.不相同C.可能相同D.无法确定
6、与线性表相比,串的插入和删除操作的特点是()A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多
7、设SUBSTRSik是求S中从第i个字符开始的连续k个字符组成的子串的操作,则对于S=’BeijingNanjing’,SUBSTRS45=(B)A.‘ijing’B.‘jing’C.‘ingNa’D.‘ingN’
二、判断题()
1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在(√)
2、KMP算法的最大特点是指示主串的指针不需要回溯(√)
3、完全二叉树某结点有右子树,则必然有左子树
三、填空题
1、求子串在主串中首次出现的位置的运算称为模式匹配
2、设s=’I︺AM︺A︺TEACHER’其长度是____
3、两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同
四、程序填空题
1、函数kmp实现串的模式匹配,请在空格处将算法补充完整intkmpsqstring*ssqstring*tintstartintnext[]{inti=start-1j=0;whileis-lenjt-lenifj==-1||s-data[i]==t-data[j]{i++;j++;}elsej=;ifj=t-lenreturn;elsereturn-1;}
2、函数实现串的模式匹配算法,请在空格处将算法补充完整intindex_bfsqstring*ssqstring*tintstart{inti=start-1j=0;whileis-lenjt-lenifs-data[i]==t-data[j]{i++;j++;}else{i=i-j+1;j=0;}ifj=t-lenreturni-t-len+1;elsereturn-1;}}/*listDelete*/
3、写出下面算法的功能intfunctionSqString*s1SqString*s2{inti;fori=0;is1-lengthis1-length;i++ifs-data[i]!=s2-data[i]returns1-data[i]-s2-data[i];returns1-length-s2-length;}答案.串比较算法
4、写出算法的功能intfunsqstring*ssqstring*tintstart{inti=start-1j=0;whileis-lenjt-lenifs-data[i]==t-data[j]{i++;j++;}else{i=i-j+1;j=0;}ifj=t-lenreturni-t-len+1;elsereturn-1;}答案串的模式匹配算法第五章数组和广义表
一、选择题
1、设广义表L=a,b,c,则L的长度和深度分别为(C)A.1和1B.1和3C.1和2D.2和
32、广义表aa的表尾是(B)A.aB.aC.D.a
3、稀疏矩阵的常见压缩存储方法有(C)两种A.二维数组和三维数组B.三元组和散列表C.三元组和十字链表D.散列表和十字链表
4、一个非空广义表的表头(D)A.不可能是子表B.只能是子表C.只能是原子D.可以是子表或原子
5、数组A[
0..
50..6]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A
[5]
[5]的地址是()A.1175B.1180C.1205D.
12106、广义表G=abcdefg的长度是(A)A.3B.4C.7D.
87、采用稀疏矩阵的三元组表形式进行压缩存储,若要完成对三元组表进行转置,只要将行和列对换,这种说法(B)A.正确B.错误C.无法确定D.以上均不对
8、广义表abc的表尾是(B)A.bcB.bcC.cD.c
9、常对数组进行两种基本操作是()A.建立和删除B.索引和修改C.查找和修改D.查找与索引
10、对一些特殊矩阵采用压缩存储的目的主要是为了(D)A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素D.减少不必要的存储空间的开销
11、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85的地址为()A.13 B.33C.18D.
4012、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1nn-1/2]中,对下三角部分中任一元素aiji=j,在一维数组B的下标位置k的值是(B)A.ii-1/2+j-1B.ii-1/2+jC.ii+1/2+j-1D.ii+1/2+j
13、广义表A=aa的表头是(B)A.aB.aC.bD.a
14、稀疏矩阵一般的压缩存储方法有两种,即(C)A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表D.散列和十字链表
15、假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注矩阵的行列下标均从1开始)(B)A.B.C.D.
16、以下有关广义表的表述中,正确的是()A.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表C.不能递归定义D.不能为空表
17、对广义表L=abcdef执行headtailheadtailL操作的结果是()A.的B.eC.eD.(ef)
二、判断题()
1、广义表中原子个数即为广义表的长度()
2、一个稀疏矩阵采用三元组表示,若把三元组中有关行下标与列下标的值互换,并把mu和nu的值进行互换,则完成了矩阵转置(√)
3、稀疏矩阵压缩存储后,必会失去随机存取功能()
4、广义表的长度是指广义表中括号嵌套的层数(√)
5、广义表是一种多层次的数据结构,其元素可以是单原子也可以是子表
三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOCA
[0]
[0],则A[i][j]的地址是___LocA
[0]
[0]+i*N+j*k____
2、广义表运算式HEADTAILabcxyz的结果是xyz
3、二维数组,可以按照两种不同的存储方式
4、稀疏矩阵的压缩存储方式有和
四、综合题
1、现有一个稀疏矩阵,请给出它的三元组表答案第六章树
一、选择题
1、二叉树的深度为k,则二叉树最多有(C)个结点A.2kB.2k-1C.2k-1D.2k-
12、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[
1..N]中,若结点R[i]有右孩子,则其右孩子是(B)A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]
3、设ab为一棵二叉树上的两个结点,在中序遍历时,a在b前面的条件是(B)A.a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孙
4、设一棵二叉树的中序遍历序列badce,后序遍历序列bdeca,则二叉树先序遍历序列为()A.adbceB.decabC.debacD.abcde
5、在一棵具有5层的满二叉树中结点总数为()A.31B.32C.33D.
166、由二叉树的前序和后序遍历序列(B)惟一确定这棵二叉树A.能B.不能
7、某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点数目为(C)A.3 B.2C.4D.
58、若以{45678}作为权值构造哈夫曼树,则该树的带权路径长度为(C)A.67 B.68C.69D.
709、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为(A)A.98 B.99C.50D.
4810、表达式a*b+c-d的后缀表达式是(B)A.abcd+- B.abc+*d-C.abc*+d-D.-+*abcd
11、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果是(B)A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC
12、树最适合用来表示(C)A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
13、表达式A*B+C/D-E+F的后缀表达式是(C)A.A*B+C/D-E+FB.AB*C+D/E-F+C.ABC+*DE-F+/D.ABCDED*+/-+
14、在线索二叉树中,t所指结点没有左子树的充要条件是()A.t-left==NULL B.t-ltag==1C.t-ltag==1t-left==NULLD.以上都不对
15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()A.不发生改变 B.发生改变C.不能确定D.以上都不对
16、假定在一棵二叉树中,度为2的结点数为15,度为1的结点数为30,则叶子结点数为()个A.15B.16C.17D.
4717、在下列情况中,可称为二叉树的是(B)A.每个结点至多有两棵子树的树 B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵子树
18、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[
1..n]中,若结点R[i]有左孩子,则其左孩子是()A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]
19、下面说法中正确的是()A.度为2的树是二叉树B.度为2的有序树是二叉树C.子树有严格左右之分的树是二叉树D.子树有严格左右之分,且度不超过2的树是二叉树
20、树的先根序列等同于与该树对应的二叉树的()A.先序序列B.中序序列C.后序序列D.层序序列
21、按照二叉树的定义,具有3个结点的二叉树有(C)种A.3 B.4C.5D.
622、由权值为3,6,7,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为(A)A.51B.23C.53D.74
二、判断题()
1、存在这样的二叉树,对它采用任何次序的遍历,结果相同()
2、中序遍历一棵二叉排序树的结点,可得到排好序的结点序列()
3、对于任意非空二叉树,要设计其后序遍历的非递归算法而不使用堆栈结构,最适合的方法是对该二叉树采用三叉链表()
4、在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应做特殊处理(√)
5、一个含有n个结点的完全二叉树,它的高度是log2n+1(√)
6、完全二叉树的某结点若无左孩子,则它必是叶结点
三、填空题
1、具有n个结点的完全二叉树的深度是log2n+
12、哈夫曼树是其树的带权路径长度最小的二叉树
3、在一棵二叉树中,度为0的结点的个数是n0,度为2的结点的个数为n2,则有n0=N2+
14、树内各结点度的最大值称为树的度
四、代码填空题
1、函数InOrderTraverseBitreebt实现二叉树的中序遍历,请在空格处将算法补充完整voidInOrderTraverseBiTreebt{if{InOrderTraversebt-lchild;printf“%c”bt-data;;}}
2、函数depth实现返回二叉树的高度,请在空格处将算法补充完整intdepthBitree*t{ift==NULLreturn0;else{hl=deptht-lchild;hr=deptht-rchild;ifhlhrreturnhl+1;elsereturnhr+1;}}
3、写出下面算法的功能Bitree*functionBitree*bt{Bitree*t*t1*t2;ifbt==NULLt=NULL;else{t=Bitree*mallocsizeofBitree;t-data=bt-data;t1=functionbt-left;t2=functionbt-right;t-left=t2;t-right=t1;}returnt;}答案交换二叉树结点左右子树的递归算法
4、写出下面算法的功能voidfunctionBitree*t{ifp!=NULL{functionp-lchild;functionp-rchild;printf“%d”p-data;}}答案二叉树后序遍历递归算法
五、综合题
1、假设以有序对pc表示从双亲结点到孩子结点的一条边,若已知树中边的集合为{abadaccecfcgcheiejgk}请回答下列问题
(1)哪个结点是根结点?
(2)哪些结点是叶子结点?
(3)哪些结点是k的祖先?
(4)哪些结点是j的兄弟?
(5)树的深度是多少?
2、假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树
3、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成,字母在电文中出现的频率分别为
0.07,
0.19,
0.02,
0.06,
0.32,
0.03,
0.21,
0.10请为这8个字母设计哈夫曼编码答案
4、已知二叉树的先序遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树答案二叉树形态
5、试用权集合{1245612}构造哈夫曼树,并计算哈夫曼树的带权路径长度答案WPL=12*1+4+5+6*3+1+2*4=12+45+12=
696、已知权值集合为{572369},要求给出哈夫曼树,并计算带权路径长度WPL答案1树形态2带权路径长度WPL=6+7+9*2+5*3+2+3*4=44+15+20=
797、已知一棵二叉树的先序序列ABDGJEHCFIKL;中序序列DJGBEHACKILF画出二叉树的形态答案
8、一份电文中有6种字符ABCDEF,它们的出现频率依次为16,5,9,3,30,1,完成问题
(1)设计一棵哈夫曼树;(画出其树结构)
(2)计算其带权路径长度WPL;答案1树形态2带权路径长度WPL=30*1+16*2+9*3+5*4+1+3*5=30+32+27+20+20=
1299、已知某森林的二叉树如下所示,试画出它所表示的森林答案
10、有一分电文共使用5个字符;abcde,它们的出现频率依次为
4、
7、
5、
2、9,试构造哈夫曼树,并给出每个字符的哈夫曼编码
11、画出与下图所示的森林相对应的二叉树,并指出森林中的叶子结点在二叉树中具有什么特点
12、如下所示的二叉树,请写出先序、中序、后序遍历的序列答案先序FDBACEGIHJ中序ABCDEFGHIJ后序ACBEDHJIGF
六、编程题
1、编写求一棵二叉树中结点总数的算法答案 (以先序遍历的方法为例)voidcount_preorderBitree*tint*n{ift!=NULL{*n++;count_preordert-lchild;count_preordert-lchild;}}第七章图
一、选择题
1、
12、对于具有n个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为()A.nB.n2C.n-1D.n-
122、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()A.完全图B.连通图C.有回路D.一棵树
3、关键路径是事件结点网络中()A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路D.最短的回路
4、下面()可以判断出一个有向图中是否有环(回路)A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径
5、带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中()A.第i行非无穷的元素之和 B.第i列非无穷的元素个数之和C.第i行非无穷且非0的元素个数D.第i行与第i列非无穷且非0的元素之和
6、采用邻接表存储的图,其深度优先遍历类似于二叉树的()A.中序遍历B.先序遍历C.后序遍历D.按层次遍历
7、无向图的邻接矩阵是一个()A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵
8、当利用大小为N的数组存储循环队列时,该队列的最大长度是()A.N-2B.N-1C.ND.N+
19、邻接表是图的一种()A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构
10、下面有向图所示的拓扑排序的结果序列是()A.125634 B.516234C.123456D.
52164311、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个()A.顶点序列B.边序列C.权值总和D.边的条数
12、在有向图的逆邻接表中,每个顶点邻接表链接着该顶点所有()邻接点A.入边B.出边C.入边和出边D.不是出边也不是入边
13、设G1=V1E1和G2=V2E2为两个图,如果V1V2E1E2则称()A.G1是G2的子图B.G2是G1的子图C.G1是G2的连通分量D.G2是G1的连通分量
14、已知一个有向图的邻接矩阵表示,要删除所有从第i个结点发出的边,应()A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为
015、任一个有向图的拓扑序列()A.不存在B.有一个C.一定有多个D.有一个或多个
16、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍A.1/2B.1C.2D.
417、下列关于图遍历的说法不正确的是()A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶点仅被访问一次
18、带权有向图G用邻接矩阵A存储,则顶点i的入度为A中()A.第i行非的元素之和B.第i列非的元素之和C.第i行非且非0的元素个数D.第i列非且非0的元素个数
19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.按层次遍历
20、一个具有n个顶点的有向图最多有()条边A.n×n-1/2B.n×n-1C.n×n+1/2D.n
221、已知一个有向图的邻接表存储结构如图所示,根据深度优先遍历算法,从顶点v1出发,所得到的顶点序列是()A.v1v2v3v5v4B.v1v2v3v4v5C.v1v3v4v5v2D.v1v4v3v5v
222、关键路径是事件结点网络中()A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路D.最短的回路
23、以下说法正确的是()A.连通分量是无向图中的极小连通子图B.强连通分量是有向图中的极大强连通子图C.在一个有向图的拓扑序列中若顶点a在顶点b之前,则图中必有一条弧abD.对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图
24、假设有向图含n个顶点及e条弧,则表示该图的邻接表中包含的弧结点个数为()A.nB.eC.2eD.n*e
25、设图的邻接矩阵为,则该图为()A.有向图B.无向图C.强连通图D.完全图
26、为便于判别有向图中是否存在回路,可借助于()A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法
27、任何一个无向连通图的最小生成树()种A.只有一棵 B.有一棵或多棵C.一定有多棵D.可能不存在
28、已知一有向图的邻接表存储结构如图所示,根据有向图的广度优先遍历算法,从顶点v1出发,所得到的顶点序列是()A.v1v2v3v4v5B.v1v3v2v4v5C.v1v2v3v5v4D.v1v4v3v5v
229、对于一个有向图,若一个顶点的入度为k
1、出度为k2,则对应邻接表中该顶点单链表中的结点数为()A.k1 B.k2C.k1+k2D.k1-k
230、一个具有8个顶点的有向图中,所有顶点的入度之和与所有顶点的出度之和的差等于()A.16B.4C.0D.
231、无向图中一个顶点的度是指图中()A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.与该顶点连通的顶点数D.通过该顶点的回路数
二、填空题
1、n个顶点的连通图至少有边答案n-1条
2、一个连通图的生成树是一个,它包含图中所有顶点,但只有足以构成一棵树的n-1条边答案极小连通子图
3、一个图的表示法是惟一的答案邻接矩阵
4、遍历图的基本方法有深度优先搜索和广度优先搜索,其中是一个递归过程答案深度优先搜索
5、在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于答案
16、判定一个有向图是否存在回路,可以利用答案拓扑排序
7、已知一个图的邻接矩阵表示,计算第i个结点的入度的方法是
8、n个顶点的无向图最多有边
9、已知一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是
10、若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数即为顶点vi的
三、判断题
1、图的连通分量是无向图的极小连通子图
2、一个图的广度优先搜索树是惟一的
3、图的深度优先搜索序列和广度优先搜索序列不是惟一的
4、邻接表只能用于存储有向图,而邻接矩阵则可存储有向图和无向图
5、存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关
6、AOV网是一个带权的有向图
7、从源点到终点的最短路径是唯一的
8、邻接表只能用于存储有向图,而邻接矩阵则可存储有向图和无向图
9、图的生成树是惟一的
四、程序分析题
1、写出下面算法的功能typedefstruct{intvexnumarcnum;charvexs[N];intarcs[N][N];}graph;voidfuntionintigraph*g{intj;printfnode:%c\ng-vexs[i];visited[i]=TRUE;forj=0;jg-vexnum;j++ifg-arcs[i][j]==1!visited[j]functionjg;}答案实现图的深度优先遍历算法
五、综合题
1、已知图G的邻接矩阵如下所示
(1)求从顶点1出发的广度优先搜索序列;
(2)根据prim算法,求图G从顶点1出发的最小生成树,要求表示出其每一步生成过程(用图或者表的方式均可)答案1广度优先遍历序列1;234;5;62最小生成树(prim算法)
2、设一个无向图的邻接矩阵如下图所示
(1)画出该图;
(2)画出从顶点0出发的深度优先生成树;答案1图形态2深度优先搜索树
3、写出下图中全部可能的拓扑排序序列答案1,5,2,3,6,41,5,6,2,3,45,1,2,3,6,45,1,6,2,3,45,6,1,2,3,
44、AOE网G如下所示,求关键路径(要求标明每个顶点的最早发生时间和最迟发生时间,并画出关键路径)答案1最早发生时间和最迟发生时间2关键路径
5、已知有向图G如下所示,根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离(给出求解过程)答案终点从v0到各终点的d值和最短路径的求解过程i=1i=2i=3i=4v112v0v112v0v17v0v4v1v24v0v2v39v0v38v0v2v37v0v4v37v0v4v3v45v0v45v0v4vjv2v4v1v3s{v0v2}{v0v4}{v0v4v1}{v0v4v3}
6、已知图G如下所示,根据Prim算法,构造最小生成树(要求给出生成过程)答案prim算法求最小生成树如下
7、已知有向图如下所示,请写出该图所有的拓扑序列答案拓扑排序如下v1v2v4v6v5v3v7v8v1v2v4v6v5v7v3v8v1v2v6v4v5v3v7v8v1v2v6v4v5v7v3v8v1v6v2v4v5v3v7v8v1v6v2v4v5v7v3v
88、如下图所示的AOE网,求
(1)求事件的最早开始时间ve和最迟开始时间vl;事件123456789VeVl
(2)求出关键路径;答案1求ve和vl2关键路径如下所示的有向图,回答下面问题
(1)该图是强连通的吗?若不是,给出强连通分量
(2)请给出图的邻接矩阵和邻接表表示答案1是强连通图2邻接矩阵和邻接表为
9、已知图G的邻接矩阵A=,试画出它所表示的图G,并根据Prim算法求出图的的最小生成树(给出生成过程)答案1图形态2prim算法求最小生成树
10、如下图所示的AOV网,写出其中三种拓扑排序序列
11、已知图G如下,根据克鲁斯卡尔算法求图G的一棵最小生成树(要求给出构造过程)答案kruskal算法的最小生成树
12、已知图G如下所示,求从顶点a到其余各顶点的最短路径(给出求解过程)答案终点最短路径求解过程b6ab5acbc3acd6acd6acde7ace7ace7acef9acdf9acdfvjcbdefS{ac}{acb}{acd}{ace}{acdf}第九章查找
一、选择题
1、已知一个有序表为(11,22,33,44,55,66,77,88,99),则折半查找55需要比较(A)次A.1B.2C.3D.
42、有一组关键字序列{1316634329873127},哈希表的表长为13,哈希函数为Hkey=keyMOD13冲突解决的办法为链地址法,请构造哈希表(用图表示)
3、解决哈希冲突的主要方法有()A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、再哈希法D.线性探测法、再哈希法、链地址法
4、在一棵深度为h的具有n个元素的二叉排序树中,查找所有元素的最长查找长度为()A.nB.log2nC.h+1/2D.h
5、已知表长为25的哈希表,用除留取余法,按公式Hkey=keyMODp建立哈希表,则p应取()为宜A.23B.24C.25D.
266、设哈希表长m=14哈希函数Hkey=keyMOD11表中已有4个结点addr15=4addr38=5addr61=6addr84=7其余地址为空,如用二次探测再散列处理冲突,则关键字为49的地址为(A)A.8B.3C.5D.
97、在散列查找中,平均查找长度主要与(C)有关A.散列表长度B.散列元素个数C.装填因子D.处理冲突方法
8、根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树,当插入到值为的结点时需要进行旋转调整
9、m阶B-树中的m是指()A.每个结点至少具有m棵子树B.每个结点最多具有m棵子树C.分支结点中包含的关键字的个数D.m阶B-树的深度
10、一个待散列的线性表为k={1825635042329},散列函数为Hk=kMOD9,与18发生冲突的元素有()个A.1B.2C.3D.
411、在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插到集合中,这种方式主要适合于()A.静态查找表 B.动态查找表C.静态查找表和动态查找表D.两种表都不适合
12、有一个有序表为{139123241456275778295100}当折半查找值为82的结点时,(B)次比较后查找成功A.1B.4C.2D.
813、在各种查找方法中,平均查找承担与结点个数n无关的查找方法是(C)A.顺序查找B.折半查找C.哈希查找D.分块查找
14、下列二叉树中,不平衡的二叉树是(C)
15、对一棵二叉排序树按(B)遍历,可得到结点值从小到大的排列序列A.先序 B.中序C.后序D.层次
16、解决散列法中出现的冲突问题常采用的方法是(D)A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法
17、对线性表进行折半查找时,要求线性表必须(C)A.以顺序方式存储 B.以链接方式存储C.以顺序方式存储,且结点按关键字有序排序D.以链接方式存储,且结点按关键字有序排序
二、填空题
1、在散列函数Hkey=key%p中,p应取
2、已知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用折半查找90时,需进行2次查找可确定成功
3、具有相同函数值的关键字对哈希函数来说称为
4、在一棵二叉排序树上实施遍历后,其关键字序列是一个有序表
5、在散列存储中,装填因子α的值越大,则存取元素时发生冲突的可能性就越大;α值越小,则存取元素发生冲突的可能性就越小
三、判断题(×)
1、折半查找只适用于有序表,包括有序的顺序表和链表()
2、二叉排序树的任意一棵子树中,关键字最小的结点必无左孩子,关键字最大的结点必无右孩子()
3、哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法()
4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树(√)
5、AVL是一棵二叉树,其树上任一结点的平衡因子的绝对值不大于1
四、综合题
1、选取哈希函数H(k)=(k)MOD11用二次探测再散列处理冲突,试在0-10的散列地址空间中对关键字序列
(2241534630130167)造哈希表,并求等概率情况下查找成功时的平均查找长度答案1表形态2ASL ASL7=1*5+2*1+3*1/7=5+2+3/7=10/
72、设哈希表HT表长m为13,哈希函数为Hk=kMODm,给定的关键值序列为{19142310682084275511}试求出用线性探测法解决冲突时所构造的哈希表,并求出在等概率的情况下查找成功的平均查找长度ASL答案1表形态2平均查找长度ASL10=1*5+2*4+3*1/10=
1.
63、设散列表容量为7(散列地址空间
0..6),给定表(30,36,47,52,34)散列函数H(K)=Kmod6,采用线性探测法解决冲突,要求
(1)构造散列表;
(2)求查找数34需要比较的次数答案1表形态2查找34的比较次数
34、已知下面二叉排序树的各结点的值依次为1-9,请标出各结点的值答案
5、若依次输入序列{62683061251453479084}中的元素,生成一棵二叉排序树画出生成后的二叉排序树(不需画出生成过程)
6、设有一组关键字{19123145520842768111077}采用哈希函数Hkey=keyMOD13采用开放地址法的二次探测再散列方法解决冲突,试在0-18的散列空间中对关键字序列构造哈希表,画出哈希表,并求其查找成功时的平均查找长度
7、已知关键字序列{112132651849},设哈希表表长为16,哈希函数Hkey=keyMOD13,处理冲突的方法为线性探测法,请给出哈希表,并计算在等概率的条件下的平均查找长度
8、设散列表的长度为m=13,散列函数为Hk=kMODm,给定的关键码序列为19,14,23,1,68,20,84,27,55,11,13,7,试写出用线性探查法解决冲突时所构造的散列表答案表形态
9、依次读入给定的整数序列{716482096185},构造一棵二叉排序树并计算在等概率情况下该二叉排序树的平均查找长度ASL(要求给出构造过程)
10、设有一组关键字(19,1,23,14,55,20,84,27,68,11,10,77),采用哈希函数Hkey=key%13,采用二次探测再散列的方法解决冲突,试在0-18的散列地址空间中对该关键字序列构造哈希表答案第十章内部排序
一、选择题
1、若需要在Onlog2n的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()A.快速排序 B.堆排序C.归并排序D.直接插入排序
2、下列排序方法中()方法是不稳定的A.冒泡排序B.选择排序C.堆排序D.直接插入排序
3、一个序列中有10000个元素,若只想得到其中前10个最小元素,则最好采用()方法A.快速排序 B.堆排序C.插入排序D.归并排序
4、一组待排序序列为
(467956384084),则利用堆排序的方法建立的初始堆为()A.794656384080B.847956384046C.847956464038D.
8456794046385、快速排序方法在()情况下最不利于发挥其长处A.要排序的数据量太大B.要排序的数据中有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数
6、排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置,这是()排序的基本思想A.堆排序B.直接插入排序C.快速排序D.冒泡排序
7、在任何情况下,时间复杂度均为Onlogn的不稳定的排序方法是()A.直接插入 B.快速排序C.堆排序D.归并排序
8、如果将所有中国人按照生日来排序,则使用()算法最快A.归并排序 B.希尔排序C.快速排序D.基数排序
9、在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是()A.Olog2n B.O1C.OnD.Onlog2n
10、排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为()A.希尔排序B.冒泡排序C.插入排序D.选择排序
11、一组记录的的序列未(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为()A.79,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,
3812、用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下⑴25,84,21,47,15,27,68,35,20⑵20,15,21,25,47,27,68,35,84⑶15,20,21,25,35,27,47,68,84⑷15,20,21,25,27,35,47,68,84则所采用的排序方法是()A.选择排序B.希尔排序C.归并排序D.快速排序
13、设有1024个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用()A.冒泡排序 B.选择排序C.快速排序D.堆排序
14、下列排序方法中,平均时间性能为Onlogn且空间性能最好的是()A.快速排序 B.堆排序C.归并排序D.基数排序
15、希尔排序的增量序列必须是()A.递增的 B.递减的C.随机的D.非递减的
二、填空题
1、在插入和选择排序中,若初始数据基本正序,则选用,若初始数据基本反序,则选用答案递增排列递减排列
2、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有
三、判断题
1、直接选择排序是一种稳定的排序方法
2、快速排序在所有排序方法中最快,而且所需附加空间也最少
3、直接插入排序是不稳定的排序方法
4、选择排序是一种不稳定的排序方法
四、程序分析题
五、综合题
1、写出用直接插入排序将关键字序列{542389486450259034}排序过程的每一趟结果答案初始54,23,89,48,64,50,25,90,341(23,54),89,48,64,50,25,90,342(23,54,89),48,64,50,25,90,343(23,48,54,89),64,50,25,90,344(23,48,54,64,89),50,25,90,345(23,48,50,54,64,89),25,90,346(23,25,48,50,54,64,89),90,347(23,25,48,50,54,64,89,90),348(23,25,48,50,54,64,89,90,34)
2、设待排序序列为{10184361219158}请写出希尔排序每一趟的结果增量序列为5,3,2,1答案初始10,18,4,3,6,12,1,9,15,8d=510,1,4,3,6,12,18,9,15,8d=33,1,4,8,6,12,10,9,15,18d=23,1,4,8,6,9,10,12,15,18d=11,3,4,6,8,9,10,12,15,
183、已知关键字序列{418,347,289,110,505,333,984,693,177},按递增排序,求初始堆(画出初始堆的状态)答案418,347,289,110,505,333,984,693,
1774、有一关键字序列(265,301,751,129,937,863,742,694,076,438),写出希尔排序的每趟排序结果(取增量为5,3,1)答案初始265,301,751,129,937,863,742,694,076,438d=5265,301,694,076,438,863,742,751,129,937d=3076,301,129,265,438,694,742,751,863,937d=1076,129,265,301,438,694,742,751,863,
9375、对于直接插入排序,希尔排序,冒泡排序,快速排序,直接选择排序,堆排序和归并排序等排序方法,分别写出
(1)平均时间复杂度低于O(n2)的排序方法;
(2)所需辅助空间最多的排序方法;答案1希尔、快速、堆、归并2归并
6、对关键子序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列(最小堆),请写出排序过程中得到的初始堆和前三趟的序列状态答案12345324524^^^^^543223356abdfce。