数据结构与算法习题库(考前必备).pdf
- 文档编号:14659637
- 上传时间:2023-06-25
- 格式:PDF
- 页数:24
- 大小:493.11KB
数据结构与算法习题库(考前必备).pdf
《数据结构与算法习题库(考前必备).pdf》由会员分享,可在线阅读,更多相关《数据结构与算法习题库(考前必备).pdf(24页珍藏版)》请在冰点文库上搜索。
第一章第一章绪论绪论一选择题一选择题1数据结构被形式地定义为(K,R),其中K是_B_的有限集合,R是K上的_D_的有限集合。
A算法B数据元素C数据操作D逻辑结构A操作B映象C存储D关系2算法分析的目的是C,算法分析的两个主要方面是A。
A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性A空间复杂性和时间复杂性B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性3在计算机存储器内表示时,物理地址和逻辑地址相同并且是连续的,称之为(B)A逻辑结构B顺序存储结构C链表存储结构D以上都不对4数据结构中,在逻辑上可以把数据结构分成:
(C)。
A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构5以下属于顺序存储结构优点的是(A)。
A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示6数据结构研究的内容是(D)。
A数据的逻辑结构B数据的存储结构C建立在相应逻辑结构和存储结构上的算法D包括以上三个方面7链式存储的存储结构所占存储空间(A)。
A分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针B只有一部分,存放结点值C只有一部分,存储表示结点间关系的指针D分两部分,一部分存放结点值,另一部分存放结点所占单元数8一个正确的算法应该具有5个特性,除输入、输出特性外,另外3个特性是(A)。
A确定性、可行性、有穷性B易读性、确定性、有效性C有穷性、稳定性、确定性D可行性、易读性、有穷性9以下关于数据的逻辑结构的叙述中正确的是(A)。
A数据的逻辑结构是数据间关系的描述B数据的逻辑结构反映了数据在计算机中的存储方式C数据的逻辑结构分为顺序结构和链式结构D数据的逻辑结构分为静态结构和动态结构10算法分析的主要任务是(C)。
A探讨算法的正确性和可读性B探讨数据组织方式的合理性C为给定问题寻找一种性能良好的解决方案D研究数据之间的逻辑关系二解答二解答设有一数据的逻辑结构为:
B=(D,S),其中:
D=d1,d2,d9S=,画出这个逻辑结构示意图。
d1d8d3d2d4d5d9d7d6第二章第二章线性表线性表一、选择题1下述哪一条是顺序存储结构的优点?
(A)A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中,错误的是哪一个?
(B)A线性表采用顺序存储,必须占用一片连续的存储单元。
B线性表采用顺序存储,便于进行插入和删除操作。
C线性表采用链接存储,不必占用一片连续的存储单元。
D线性表采用链接存储,便于插入和删除操作。
3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。
A顺序表B双链表C带头结点的双循环链表D单循环链表4某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(D)存储方式最节省运算时间。
A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表5在一个长度为n的顺序表中删除第i个元素(0=inext=p-next-next;Bp=p-next;Cp=p-next-next;Dp-next=p;8在一个单链表中,已知q结点是p结点的前趋结点,若在q和p之间插入s结点,则须执行(B)As-next=p-next;p-next=sBq-next=s;s-next=pCp-next=s-next;s-next=pDp-next=s;s-next=q9线性表的顺序存储结构是一种(A)的存储结构。
A随机存取B顺序存取C索引存取D散列存取二、填空1在线性表的顺序存储中,元素之间的逻辑关系是通过物理位置相邻决定的;在线性表的链接存储中,元素之间的逻辑关系是通过指针决定的。
2在双向链表中,每个结点含有两个指针域,一个指向.直接前驱结点,另一个指向直接后继结点。
3当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用_顺序存储结构为宜。
相反,当经常进行的是插入和删除操作时,则采用链式存储结构为宜。
三、算法设计1设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法(要求用最少的时间和最小的空间)确定在序列中比正整数x大的数有几个(相同的数只计算一次)将单链表中比正整数x小的偶数从单链表中删除intcount(Linklisth,intx)intnum=0;Linknode*p;p=h-next;while(p&p-datanext;while(p)if(p-next&p-data=p-next-data)/若p没有指向链表中同一数值的最后一个结点,则向后移动p=p-next;else/若p指向数值相同的结点中的最后一个,则num加1,p指针后移,继续执行while循环num+;p=p-next;returnnum;voiddelevenl(Linklist&h,intx)Linknode*p,*r;p=h-next;r=h;while(p&p-datadata%2=0)r-next=p-next;free(p);p=r-next;elser=p;p=p-next;2设有一个表头指针为h的单链表。
试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转,如下图所示。
要求逆转结果链表的表头指针h指向原链表的最后一个结点。
2voidconverse(Linklist&h)Linknode*p,*q;p=h-next;h-next=NULL;q=p-next;while(q)p-next=h;h=p;p=q;q=q-next;p-next=h;h=p;3设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点)。
3voiddecompose(LinklistLa,Linklist&Lb,Linklist&Lc)Linknode*p;Lc=(Linknode*)malloc(sizeof(Linknode);Lc-next=NULL;p=La-next;Lb=La;Lb-next=NULL;while(p)La=p-next;if(p-data0)p-next=Lc-next;Lc-next=p;phhelsep-next=Lb-next;Lb-next=p;p=La;4.假设链表A、B分别表示一个集合,试设计算法以判断集合A是否是集合B的子集,若是,则返回1,否则返回0,并分析算法的时间复杂度。
4intsubset(LinkListla,LinkListlb)LinkNode*pa,*pb;pa=la-next;while(pa)pb=lb-next;while(pb&(pb-data!
=pa-data)pb=pb-next;if(!
pb)return0;pa=pa-next;return1;算法时间复杂度O(A.Length*B.Length)5设有一单循环链表la,其结点有三个域:
prior、data与next,其中data为数据域,,next域指向直接后继,prior域应指向直接前驱,但目前空着。
试写一算法将此单循环链表改造为双向循环链表。
5voidpriorset(DuLinkList&la)p=la;q=la-next;while(q!
=la)q-prior=p;p=q;q=q-next;q-prior=p;第三章第三章栈和队列栈和队列一、选择题一、选择题1已知栈的最大容量为4。
若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为(C)A.5,4,3,2,1,6B.2,3,5,6,1,4C.3,2,5,4,1,6D.1,4,6,5,2,3设有一个栈,元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列(C)AA,B,C,D,EBB,C,D,E,ACE,A,B,C,DDE,D,C,B,A2在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为(C)Atop不变Btop=0Ctop-Dtop+3向一个栈顶指针为hs的链栈中插入一个s结点时,应执行(B)Ahs-next=s;Bs-next=hs;hs=s;Cs-next=hs-next;hs-next=s;Ds-next=hs;hs=hs-next;4在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为(D)Arearn=frontB(front+l)n=rearCrearn-1=frontD(rear+l)n=front5在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队空的条件为(C)Arearn=frontBfront+l=rearCrear=frontD(rear+l)n=front6在一个链队列中,假定front和rear分别为队首和队尾指针,则删除一个结点的操作为(A)Afront=front-nextBrear=rear-nextCrear=front-nextDfront=rear-next7某堆栈的输入序列为1,2,3,n,输出序列的第一个元素是n,则第i个输出元素为(C)AiBn-iCn-i+1D哪个元素无所谓8用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时(D)。
A仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改二、解答题1一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法,其中i为0或1,用以表示栈号。
1双向栈./双向栈类型定义#defineSTACK_SIZE100;TypedefstructSElemType*base_one,*base_two;/栈底指针栈底1栈底2SElemType*top_one,*top_two;/栈顶指针intstacksize;SqStack;StatusInitStack(SqStack&S)/初始化双向栈S.base_one=S.top_one=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType);/第一个栈底和栈顶指向数组起点S.base_two=S.top_two=S.base_one+STACK_SIZE-1;/第二个栈底和栈顶指向数组终点S.stacksize=STACK_SIZE;returnOK;/InitStackStatusPush(SqStack&S,inti,SElemTypee)/入栈操作,i=0时将e存入前栈,i=1时将e存入后栈if(S.top_twoS.top_one)returnOVERFLOW;/栈满,不考虑追加空间if(i=0)*S.top_one+=e;else*S.top_two-=e;returnOK;/PushSElemTypePop(SqStack&S,inti)/出栈操作,i=0出前栈,i=1出后栈if(i=0)if(S.top_one=S.base_one)returnERROR;S.top_one-;e=*S.top_one;elseif(S.top_two=S.base_two)returnERROR;S.top_two+;e=*S.top_two;returne;/Pop2利用两个栈S1、S2模拟一个队列时,如何使用栈的运输实现队列的插入、删除运算。
2#defineM3structStackQelemtypedataM;inttop;structQueueStacks1;Stacks2;voidInitQueue(Queue&Q)/初始化队列Q.s1.top=0;Q.s2.top=0;intIsEmpty(Queue&Q)/判断队列是否为空if(Q.s1.top=0&Q.s2.top=0)return1;if(Q.s2.top=0&Q.s1.top!
=0)while(Q.s1.top!
=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;return0;intIsFull(Queue&Q)if(Q.s1.top=M&Q.s2.top!
=0)return1;if(Q.s1.top=M&Q.s2.top=0)while(Q.s1.top!
=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;return0;if(Q.s1.top!
=M)return0;voidInQueue(Queue&Q,Qelemtypee)if(IsFull(Q)coutOVERFLOWendl;return;Q.s1.dataQ.s1.top+=e;voidDeQueue(Queue&Q,Qelemtype&e)if(IsEmpty(Q)coutUNDERFLOWnext=Q.rear;intEmptyQueue(LinkQueueQ)/判队空returnQ.rear=Q.rear-next;voidEnQueue(LinkQueue&Q,Qelemtypee)/元素入队QueueNode*p;/新建一个结点,并置其值为ep=newQueueNode;p-data=e;/将结点插入队列末尾p-next=Q.rear-next;Q.rear-next=p;/修改队尾指针Q.rear=p;voidDeQueue(LinkQueue&Q,Qelemtype&e)/元素出队QueueNode*p;if(EmptyQueue(Q)/若队中无元素,则无法执行出队操作couterrornext-next;/让p指向队头元素e=p-data;if(p=Q.rear)/如队中只有一个元素,则要rear指向头结点,头结点的next指针指向自身Q.rear=Q.rear-next;Q.rear-next=Q.rear;else/若队中不只一个元素,则删除p所指向的结点。
Q.rear-next-next=p-next;deletep;/释放被删除结点的存储空间5假设以I和O表示入栈和出栈操作,栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列。
称可以操作的序列为合法序列,否则称为非法序列。
(1)下面所示的序列中哪些是合法的?
AIOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO
(2)通过对问题的分析,写出一个算法判定所给的操作序列是否合法。
若合法返回TRUE,否则返回FALSE。
(假定被判定的操作序列已经存入一维数组中)5typedefstructchardata10;inttop;stack;intdescion(char*str)stacks;inti;s.top=0;for(i=0;stri;i+)switch(stri)caseI:
s.datas.top+=stri;break;/若为I,则如栈caseO:
if(s.top=0)return0;s.top-;/若为O,则从栈中弹出一个Iif(s.top=0)return1;elsereturn0;第四章第四章串串一选择题一选择题1.若串S=software,其子串的数目是(B)A.8B.37C.36D.92.设有两个串p和q,求q在p中首次出现的位置的运算称作(B)A.连接B.模式匹配C.求串长D.求子串3设字符串S1=“ABCDEFG”,S2=“PQRST”,则运算:
S=CONCAT(SUBSTR(S1,2,LEN(S2);SUBSTR(S1,LEN(S2),2);后的串值为(D)AABCDEFBBCDEFGCBCDPQRSTDBCDEFEF4.下面的说法中,只有(A)是正确的A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串5.两个字符串相等的条件是(D)A.两串的长度相等B.两串包含的字符相同C.两串的长度相等,并且两串包含的字符相同D.两串的长度相等,并且对应位置上的字符相同二、填空题二、填空题1.令t1=“aaab”,t2=“abcabaa”,t3=“abcaabbabcabaacba”,试分别求出他们的nex函数值0123,0111232,01112231234532211。
2.空格串的长度为空格数,空串的长度为0。
3.设串S=Howareyou,则串的长度为11。
三、问答题三、问答题回文是指正读反读均相同的字符序列,如abba和abdba均是回文,但good不是回文。
试写一个算法判定给定的字符变量是否为回文。
StatusIsHuiwen(char*S)i=0;while(si!
=0)i+;i=i-1;j=0;while(j0)的满二叉树对应森林的由棵树构成。
三已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA。
1画出该二叉树。
2画出该二叉树的先序线索二叉树。
四试找出分别满足下列条件的所有二叉树:
1先序序列和中序序列相同。
2中序序列和后序序列相同。
3先序序列和后序序列相同。
五、设二叉树用二叉链表表示,设计算法求二叉树的高度。
intDepth(BiTreet)(后序遍历)(后序遍历)if(!
t)d=0;elsedl=Depth(t-lchild);dr=Depth(t-rchild);d=1+(dldr?
dl:
dr);returnd;六、设T是一棵具有n个结点的二叉树,若给定二叉树T的先序序列和中序序列,并假设T的先序序列和中序序列分别放在数组PreOrder1.n和InIrder1.n中,设计一个构造二叉树T的二叉链表存储结构的算法。
六/根据二叉树的先序序列和中序序列创建二叉链表voidcreateBiTree(charpre,charin,intstart,intend,int&count,BiTree&T)/按先序次序创建二叉链表,pre为存放先序序列的字符数组,in为存放中序序列的字符数组,/count为二叉树的根结点在先序序列中的序号/start和end为以precount为根的二叉树在中序序列中的起始位置和结束位置/T为二叉链表的根指针,if(startend)T=0;elseT=(BiTNode*)malloc(sizeof(BiTNode);/新建根结点if(!
T)exit(0);T-data=precount;T-lchild=T-rchild=0;for(inti=0;ini!
=0;i+)/查找根结点在中序序列in中的下标if(ini=precount)break;count+;if(ini=0)coutinputerrorlchild);/根据先序序列和中序序列创建左子树createBiTree(pre,in,i+1,end,count,T-rchild);/根据先序序列和中序序列创建右子树七、设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成,它们在电文中出现的频率分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04,回答下列问题:
为这7个字母设计哈夫曼编码若对这7个字母进行等长编码,至少需要几位二进制数?
、哈夫曼树a:
10b:
110c:
010d:
1110e:
011f:
00g:
1111等长编码至少需要3位二进制位。
八设计算法以输出二叉树中先序序列的前k(k0)个结点的值。
八八voidpreintraverse(BiTreeT,int&n)if(T)n+;if(n=k)coutdata;intraverse(T-lchild,n);intraverse(T-rchild,n);九编写算法,对一棵二叉树统计叶子的个数九九、voidCountLeaf(BiTreet,int&count)(先序遍历)(先序遍历)if(t)if(t-lchild=NULL)&(t-rchild=NULL)count+;CountLeaf(t-lchild,&count);CountLeaf(t-rchild,&count);第七章第七章图图一选择题1n个顶点,e条边的有向图的邻接矩阵中非零元素有C个。
A.nB.2eC.eD.n+e2用邻接表存储图所用的空间大小(A)A与图的顶点数和边数都有关B只与图的边数有关C只与图的顶点数有关D与边数的平方有关3有n条边的无向图的邻接表存储法中,链边中结点的个数是(B)个。
AnB2nCn/2Dn*n4一个带权无向连通图的最小生成树(A)。
A有一棵或多棵.B只有一棵C一定有多棵D可能不存在二如下所示有向图:
1请给出每个顶点的度,入度和出度。
ABCD入度1121出度2111度32322请画出其邻接矩阵、邻接表、逆邻接表、十字链表。
0101001010000010邻接矩阵ABCD13202邻接表3ABCD200逆邻接表313ABCD0103122032十字链表三试对下图所示的AOE网络,解答下列问题。
1求每个事件的最早发生时间vei和最迟发生时间vli。
2求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。
3指出哪些活动加速可使整个工程提前完成。
事件ABCDEF最早发生时间vei032668最迟发生时间vli042678活动a1a2a3a4a5a6a7a8最早开始时间00332266最迟开始时间10442567关键活动为a2a5a7,加速这些关键活动可使整个工程提前完成。
四写出下图所示的AOV网的所有拓扑有序序列。
四、拓扑有序序列ABCDEFABCEDFACBDEFACBEDFACEBDF第九章第九章查找查找一填空题采用二分法进行查找的查找表,应选择_顺序_方式的存储结构设在有序表A09中进行二分查找,比较一次查找成功的结点数为_1_,比较二次查找成功的结点数为_2_,比较三次查找成功的结点数为_4_,比较四次查找成功的结点数为_3_,比较五次查找成功的结点数为_0_,平均查找长度为_(1+2*2+3*4+4*3)/10=2.9_。
(3)设在线性表R059中进行分块查找,共分10块,每块长度为6,若利用顺序查找法对索引表和子块进行查找,则查找每个元素的平均查找长度为_9_。
二选择题对线性表进行二分查找时,要求线性表必须(B)A键值有序的链接表B键值有序的顺序表C链接表但键值不一定有序D顺序但键值不一定有序有一个有序表1,4,6,10,18,35,42,53,67,71,78,84,92,99,当用二分查找法查找键值为84的结点时,经(C)比较后查找成功。
A2B3C4D12顺序检索一个具有n个数据元素的线性表,其时间复杂度为_,二分检索一个具有n个数据元素的线性表,其时间复杂度为(AB)AO(n)BO(log2n)CO(n2)DO(nlog2n)设散列表长度为m,散列函数为H(key)=key%p,为了减少发生冲突的可能性,p应取(B)A小于m的最大奇数B小于m的最大素数C小于m的最大偶数D小于m的最大合数三解答题给定表19,14,22,01,66,21,83,27,56,13,10试按元素在表中的顺序构造一棵二叉排序树;判断该二叉排序树是否平衡,若不平衡,调整其为平衡二叉树。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 习题 考前 必备