python数据结构习题汇总.docx

《python数据结构习题汇总.docx》由会员分享，可在线阅读，更多相关《python数据结构习题汇总.docx（21页珍藏版）》请在课桌文档上搜索。

1、第1章数据结构导论一、选择题1 .算法的时间复杂度取决于AOA.问题的规模B.变量的多少C.问题的难度D.A和B2 .算法能正确的顺利结束的特性为算法的B0A.有效性B.有限性C.健壮性D.高效性3 .数据的物理结构主要包含A这几种结构。A.顺序结构和链表结构B.线性结构和非线性结构C.动态结构和静态结构D.集合、线性结构、树形结构、图形结构4 .数据在计算机内存中的表示是指A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系5.数据结构被形式化定义为二元组(D,S),其中D是B的有限集合。,算法B.数据元素C.数据操作D.数据关系6 .算法效率的度量是DA.正确度和简明度B

2、.数据复杂度和程序复杂度C.高的速度和正确度D.时间复杂度和空间复杂度7 .在存储数据时，通常不仅要存储各数据元素的值，杯要存储DA.数据的存储方法B.数据处理的方法C.数据元素的类型D.数据元素之间的关系8 .以下叙述不正确的是CoA.数据结构是指数据以及数据相互之间的联系B,数据结构主要指数据的逻辑结构，与计算机的存储和处理无关C.数据的存储结构是指数据在计算机中的存储方式，主要包括线形和非线性D.对于给定的n个元素，可以构造出的逻辑结构有多种9 .下列程序段违反了算法特征。count=0whilecount!=3：print(count)A.明确性B.有限性C.有效性D.功能性10 .下

3、列程序的时间复杂度为Doforiinranged,n+l)：J=iforkinrange(j+l,n+l):x=x+l.0(i*j)B.0(n(n-l)2)C.O(n22)D.O(n2)二、解答题1 .下列程序段中，函数InVfun(i.k)的执行次数是n(n+D2,该程序的时间复杂度为0(rf2)。forkinrange(l,n+l)：foriinrange(0,k)：ifi!=k:myfun(i,k)2 .求下列程序段中有数字标号的各语句的执行次数，然后求出该程序段的时间复杂度。deffun(n)： i=s=l whilesn：i=i+l s=s+i returni答：1次(2n)12次(

4、2n)12-1次1次0(nl2)第2章数组结构一、选择题1 .线性表是一个AB.有限序列，不能为空D.无限序列，不能为空.有限序列，可以为空C,无限序列，可以为空2 .下面关于线性表的叙述中，错误的是BoA.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于进行插入和删除操作3.某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100,则第12个元素的存储地址为OA.144B.145C.147I).1484若长度为n的顺序存储结构线性表，删除第i个数据元素.需要向前移

5、动A个数据元素。A.niB.n+iC.n-i-1D.n-i+15 .若长度为n的顺序存储结构线性表，在第i个位置插入一个元素，需要依次向后移动D个元素。.n-iB.n+iC.n-i-lD.11-i+l6 .一个顺庠表所占存储空间的大小与D无关。.顺序表长度B.结点类型C.结点中个数据域的类型D.结点的存放次序7 .以下叙述不正确的是DoA.数据的逻辑结构包括线性和非线性结构，非线性结构包括树和图两种。8 .数据的逻辑结构主要指元素间的关系，与计算机的存储和处理无关C.数据的存储结构是指数据在计算机中的存储方式，主要包括顺序和链式两种D.对于给定的n个元素，可以构造出的逻辑结构有顺序表和链表两种

6、8 .某线性表采用顺序存储结构，则下列叙述正确的是B.删除顺序表第i个元素和在第i位置插入一个元素所需移动的元素个数一样B.删除顺序表第i个元素和在第i位置插入一个元素的时间复杂度一样C.删除顺序表第i个元素和取第i元素的值的时间复杂度一样D.在顺序表表头插入和表尾插入的时间复杂度一样9 .对线性表，在下列情况下应当采用顺庠表表示的是A。.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中每个元素需要的字节数比较大D.表中的元素个数不变10 .在含有n个元素的顺序表中，算法的时间复杂度是0(1)的操作是A.A.访问第i个元素(lin)和求第i个元素的直接前驱(2in)B.在第i个元素

7、后插入一个新元素(lin)C.删除第i个元素(lin)D.将n个元素从小到大排序二、填空题1. 一个一维数组(列表)A的长度为500,起始(A0)地址为2000,每个元素占4个字节，则A-80!的地址是2320C2. 一个4*6的二维数组A,每个元素占4个字节，假设该数组起始元素A(Ij)的地址是110,若以行为主存储，则A(3,5)的地升息174，若以列为主存储，A(3,5)的地址是182。3. 以顺序存储结构实现的线性表简称为顺序表,它要求存储空间必须是连续的,并以下标来体现元素之间的关系,在顺序表中访问第i个元素的时间复杂度为0(1),因此，顺序表也称为随机存取的数据结构。以链式存储结构

8、实现的线性表称为密表o其存储空间可以易不像续的以指生来体现元素之间的关系。在链表中访问第i个元素的时间复杂度为四匕一链表也称为顺序访问的数据结构。三、算法设计题.设有一个顺序表L,其元素为整型数据，编写一个要求时间复杂度为0(n)、空间复杂度为0(1)的算法，将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。提示：从L的两端查找，前端找大于0的数据，后端找小于0的数据，然后将两位置的数据交换。1.=1,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10n=Ien(L)Print(原顺序表：n0,format(L)j=0k=0forii

9、nrange(n)：ifLiiorx=i:Print(W元素X大于或等于。,程序继续format(i)continueelse：Print(M元素X小于,程序停止，format(i)breakifname=wmain_w:x=eval(input(请输入要查找的元素x：)1.=Ix2,3,4,5,6,7,8,9found(L,x)2 .已知一个n*n的二维数组a已经以行为主存放在一个大小为n2的一维数组b中，编写一个函数计算此二维数组的主对角线元素之和。COUnt(b,n)defcount(b,n)：x=0i=0whiIeTrue：x+=bii+=n+1ifiIen(b)：breakPrint

10、(主对角线元素之和为：1MfX)ifname=,main_,:a=l,2,3,4,5,6,7t8,9b=n=Ien(a)Print(二维数组A为：w)foriinrange(n)：forjinrange(n)：b.append(aij)print(,%d%aij,end=*t)print()Printc存放在一维数组b中为：m)print(b)count(b,n)4.有一值为整型、长度为n的顺序表(列表)，写一个函数，计算该顺序表所有元素的平均值，并输出所有大于平均值的元素。defAverage(L,n)：nsum=0foriinrange(n)：nsum+=Liaverage=nsum/np

11、rint(平均数为:%dw%average)Print(所有大于平均值的元素为：”)foriinL：ifiaverage：print(i,end=*)else：continueifname=,main_：1.=1,354,56,57,2,8,9,46,767,678n=Ien(L)Average(L,n)笫3章链表一、选择题1.以下关于链式存储结构的叙述中，C是不正确的。A.结点除自身信息外还包括指针域，因此空间利用率小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除运算操作方便，不必移动结点2 .在下列存储结构中，最适合实现在线性表中

12、进行随机访问的是A.数组B.双向链表C.单向链表D.循环链表3 .与单链表相比，双转亮的优点之一是I)C.可以由最后一个结点找到头结点B.可随机访问C.插入、删除操作更加简单D.访问前驱结点更加方便4如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素,则最好使用OA.顺序表B.单链表C.双向链表D.具有表尾指针的循环单链表5 .在表头指针为head且表长大于1的单向循环锥表中，指针p指向表中的某个结点，若p.next,next=head,则DB. P指向尾结点A.P指向头结点C. P所指结点的直接后继是头结点I). P所指结点的直接后继是尾结点6 .带表头附加结点的单

13、链表head为空的判断条件是B.A. head=None#不带头结点的空链表B. head.next=NoneC.head,next=headD.head!=Nono7 .一个单链表中，若要在指针S所指结点的后面插入一个由指针P所指向的结点，则执行p. ncxt = s. next；s=pp. next = ss. next=pA. s.next=pB. p.next=s.nextC. s.next=p.nextD. p.next=s.next8 .对线性表，在下列情况下应当采用链表表示的是B,A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表

14、中的元素个数不变9 .如果最常用的操作是取第i个结点及前驱，则采用A存储方式最节省时间。A.顺序表B.双链表C.单循环链表D.单链表10 .从一个具n个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较D个结点。A. nB. n/2C. (n-l)2D. (n+l)211 .在单链表中，指针P指向元素为X的结点，实现删除X的后继的语句是B.A.p=p.nextB.p.next=p.next,nextC.p.next=pD.p=p.next,next12.循环链表的主蓼优点是D。A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保

15、证链表不断开D.从表中任一结点出发都能遍历整个链表二、填空题1 .一个单链表结构中，每个结点都包含有两个域，称为&S域和指域。2 .已知一个双向链表(指针域名为next和Prior)中间局部如下图所示，现要求将P所指的结点插入到X和y结点之间(即P所指结点后面)，其操作步骤为:p.next-q.next；p.PriOr-q；q.next-P;.next；pMoF=P;3 .已知L是不带头结点的单链表，阅读下列函数，回答问题。deffun(L)：#L是不带头结点的单链表的头指针if(L!=None&L.next!=None)：#语句1q=L1.=L.nextP二Lwhi1e(p.next!=No

16、ne)：#语句5p=.nextp.next=qq.next=NonereturnL；(1)说明该函数执行的条件，即语句1的功能1.en(L)1(2)说明语句5(即While循环)的功能查找尾结点(3)若链表L的初始状态如下图，画出执行上述函数后的链表L的示意图。Gl|a2Ia3j4JWa5aHZI-LL三、算法设计题1 .编写一个函数，实现从单链表中查找出所有元素的最大值，该值由函数返回。deffun(L)：ifL.next-None：return0Max=L.next,dataP=L.next,nextwhilep!=None：ifp.datamax：max=p.datap=p.nextre

17、turnmax2 .编写一个函数，实现单链表中删除一个最小值节点的算法(假设该链表中每个节点的值不重复)。deffunl(L)：ifL.next=None：returnNoneptr=L.nextp=L.next,nextwhilep!=None：ifp.dataMAX:元素出队列时队头指针的变化为front二(front+l)lMAX:队列中的元素个数为(rcar-front+MAX)MAX0队满的判别条件为为(rcar+l)MAX=Iicnt.队空的判别条件为rent一一rmro3 .一个中缀表达式a+b*(a+c)-cd的前缀表达式为S*b+acCd,后缀表达式为abac+*+cd-C一

18、个后缀表达式21+42-*3+的值为94 .下列函数的功能是乘n2Mn12Mn221的和Cdefsum(n)：ifn=0:return0else：returnsum(n-l)+n*n5 .下列算法的功能判断输入的字符串是否是回文。deffunc()：Creatstack(三)#初始化构造一个空栈SCreatqueue(Q)#初始化构造一个空队列Qstr=input(输入一个字符串：”)forchinstr：push(ch)enqueue(ch)whilenotisempty(三)：a=popOb=dequeue()ifa!=b:return0return1三、解答题1 .用一维数组a7顺序存储

19、一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：22,30,16,36,58,其中22是队首，front值为5,请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80,55依次进队，请再画出对应的存储状态图。2 .用一个带头结点的循环链表来表示循环队列，且该队列只设尾指针。编写初始化、入队、出队操作算法。classQnode：definit_(self,data,next=None)：self.data=dataself.ncxt=Noncrear=Qnode0rear,next=reardefenqueue(item)：globalr

20、earnewQueue=Qnode()ncwQucue.data=itemnewQueue.next=rear.nextrear,next=newQueuerear=newQueuedefdequeue(item)：globalrearifrear,next=rear：Print(队列已空！”)else：item=rear.next,datarear,next=rear.next,nextreturnitem笫5章树形结构一、选择题1 .按照二叉树定义，具有3个结点的二叉树共有C种形态。（八）3(B)4(C)5(D)62 .具有五层结点的完全二叉树至少有D个结点。（八）9(B)15(C)31(

21、D)163 .以下有关二叉树的说法正确的是（八）二叉树的度为2(B)一棵二叉树的度可以小于2(C)至少有一个结点的度为2(D)任一结点的度均为24 .已知二叉树的后序遍历是dab,中序遍历是debac,则其前序遍历是U（八）acbed(B)decab(C)deabc(D)cedba5将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1,则编号为49的结点的右孩子编号为LO（八）98(B)99(C)50(D)没有右孩子6对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有D为空。说明：n=n+nl+n2指针域为空的个数：2*n0+nl=n+nl+n2+1=1

22、01() 50(B) 99(C) 100(D) 1017.设二叉树的深度为h,且只有度为1和O的结点，则此二叉树的结点总数为C,（八）2h(B)2h-l(C)h(D)h+18对一棵满二叉树，m个树叶，n个结点，深度为h,则D。（八）n=h+m(B)h+m=2n(C)m=h-l(D)n=2h-1a某二叉树的先序序列和后序序列正好相反，则下列说法错误的是（八）二叉树不存在(B)若二叉树不为空，则二叉树的深度等于结点数(C)若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子(D)若二叉树不为空，则任一结点的度均为1IQ对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点

23、的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用J遍历实现编号。（八）先序(B)中序(C)后序(D)层序11.一个具有1025个结点的二叉树的高h为工一（八）10(B)H(C)IP1025(D)10102412.设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是。（八）n在In右方(B)n是m祖先(C)n在m左方(D)n是m子孙13 .实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用U储结构。（八）二叉链表(B)广义表(C)三叉链表(D)顺序14 .一棵树可转换成为与其对应的二叉树，则下面愈述正确的县A（八）树的先根遍历序列与其对应的二叉树的先序遍

24、历相同(B)树的后根遍历序列与其对应的二叉树的后序遍历相同(C)树的先根遍历序列与其对应的二叉树的中序遍历相同(D)以上都不对二、填空题1对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度;当它走分支二叉树时,具有最大高度。2在二叉树的第i(i2l)层上至多有2(iT)个结点,深度为k(kl)的完全二叉树至多2飞-1个结点,最少2XkT)个结点；3.如果二叉树的终端结点数为阳，度为2的结点数为r)2,则阳=n2l4已知一棵二叉树的中序序列是CbCdahgijf,后序序列是Mdbhjigfa,则该二叉树的先序序列是abcdefehii,该二叉树的深度为5。5若一棵二叉树的中序遍历结果

25、为ABC,则该二叉树有5种不同的形态C6在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是Io晨2)i二IOR(2)i。7.已知完全二叉树的第7层有8个结点，则其叶子结点数为36个。总结点数为71工。8在对二叉树进行非递归中序遍历过程中，需要用接*暂存所访问结点的地址；进行层序遍历过程中，需要用队列来暂存所访问结点的地址:9高度为h,唐为k的树中至少有h+kT个结点,至多有KhT，、结点。IQ一维数组存放完全二叉树：bcdefghi,则后序遍历该二叉树的序列为HIDEBFGCa。三、应用题1 .应用题：说明分别满足下列条件的二叉树各是什么？先序遍历和中序遍历相同；右斜二叉树、空树，

26、只有一个跟节点的二叉树(2)中序遍历和后序遍历相同；左斜二叉树、空树，只有一个跟节点的二叉树先序遍历和后序遍历相同；空树，只有一个跟节点的二叉树2 .已知一棵二叉树的中序序列是Cbedahgijf,后序序列是Cedbhjigfa,画出这棵二叉树的逻辑结构图。3 .一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，试构造出该二叉树。先序序列：ABCDEEGHlJK中序序列：Cbedfahjkig后序序列：CEFDBKJIHG.A4 .有n个结点的二叉树，已知叶子结点个数为n,回答下列问题：O(1)写出求度为1的结点的个数n的计算公式；nl=n+l-2n1若此树是深度为k的完全二叉树，写出n

27、为最小的公式；n(min)=2k-l)若二叉树中仅有度为O和度为2的结点，写出求该二叉树结点个数n的公式；n=2n-l5.按列表为32,25,16,35,34,20,40中的数据创建一棵二叉查找树，画出此二叉查找树，并写出此二叉查找树的先序、中序、后序遍历序列。先序：32251620353440中序:16 20 25 3234 35 40后序:2016 25 34 40 35 32四、算法设计题1 .编写求二叉树BT中结点总数的算法。defnodecount(BT)：ifBT=None：return0else：n=nodecount(BT.left)+nodecount(BT.right)+1

28、returnn2 .编写求二叉树BT中叶子结点数的算法。defIeavecount(BT)：ifBT=None：returnOelifBT.left=NoneandBT.right=None：return1else：m=leavecount(BT.left)+leavecount(BT.right)returnm3 .若已知两棵二叉树BTI和BT2皆为空，或者皆不为空且BTI的左、右子树和BT2的左、右子树分别相似，则称二叉树BTl和BT2相似。编写算法，判别给定的两棵二叉树是否相似。defBTreeSim(BT1,BT2):ifBTl=NoneandBT2=None：return1elifB

29、Tl=NoneorBT2=None：returnOelse：m=BTreeSim(BTl.left,BT2.left)n=BTreeSim(BTl.right,BT2.right)returnm,n4 .编写算法，求二叉树中以元素值为X的结点为根的子树的深度。defgetDepth(BT,x)：ifBT=None：returnOelifBT.data=x：returnbtreedeth(BT)elifBT.left!=Null：returngetDepth(BT.left,x)elifBT.right!=Null：returngetDeth(BT.right,x)else：returnOdef

30、btreedepth(ptr)：#求二叉树的高度ifptr=None：returnOelse：m=btreedepth(ptr.left)n=btreedepth(ptr.right)ifmn：returnm+1else：returnn+1笫6章图形结构一、选择题1 .在一个具有n个顶点的有向完全图中，所含的边数为_BoA.nB.n(n-l)C.n(n-l)2I),n(n+l)22 .在一个有向图中，所有顶点的度之和与图的边数之比为。.1：1B.2：1C.1:2D.不确定3 .一个具有n个顶点的无向图，要确保是一个连通图，至少需要A条边。A.n-lB.nC.n+1D.n/24 .在一个有向图中

31、，所有顶点的入度之和等于所有顶点的出度之和的C倍。A.4B.2C.1D.1/25 .对于一个有向图，若一个顶点的度为kl,出度为k2,则对应邻接表中该顶点在表结点中出现的结点数为_C。A.klB.k2C.kl-k2D.kl+k26 .在无向图G的邻接矩阵A中，若Ai,j等于1,则Aj,i等于_B。A.无穷大B.1C.OD.无法确定7 .在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为AoA.nB.2nC.eD.2e8 .G是一个非连通无向图，共有28条边，则该图至少有B个顶点。n(nT)2=28n=8+l=9.16B.9C.8D.79 .在一个有向图的邻接

32、表中，每个顶点单链表中结点的个数等于该顶点的_AoA.出边数B.入边数C.度数D.度数减110 .对某个无向图的邻接矩阵来说，下列叙述错误的是3o.第i行与第i列上的非零元素的总数等于顶点Vi的度数B.矩阵中的非零元素个数等于图中的边数的2倍C.第i行上的非零元素个数和第i列上的非零元素个数一定相等D.矩阵是一个nXn的方阵(n为图的顶点数)11 .对于C,从它的某个顶点出发进行一次深度或广度优先搜索就可以访问到该图的每一个顶点。A.无向图B.有向图C.无向连通图D.任何一个图12 .在有向图的邻接表存储结构中，顶点V在表结点中出现的次数等于C。A.顶点V的度B.顶点V的出度C.顶点V的入度D

33、.依附于顶点V的弧数二、填空题1 .已知某无向图的二元组表示为DS=(K,R),K=a,b,c,d,erf,R=(a,b)(a,c)(a,d),(b,e),(d,e),(c,d),(c,e),(c,f),则顶点C的度为4,它的所有邻接点为/一,2 .一个有向图的顶点集为a,b,c,d,e,f,边集为,则出度为O的顶点个数为二入度为1的顶点个数为13 .一个有n个顶点的无向完全图有n(n1)/2条边。在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-l条边。4 .n个顶点的有向强连通图至少有n条边，最多有n(nT)条弧。若一个无向图有10条边，若要使该无向图是一个非连通图，至少需要_个顶点

34、；若要使该无向图是一个连通图，至多可以有11个顶点。5 .在有向图的邻接矩阵中，第i行中“1”的个数是第i小顶点的出唐.第i列中“1”的个数是第i个顶点的3在无向图的邻接矩阵中，第i行(列)中“1”的个数是第i个顶点的言O6 .图结构的数据元素之间存在多对多的关系。对稠密图来说，应选用邻接矩阵存储结构较合适。7 .图的广度优先遍历算法使用了数据结构队列操作。8 .在有向图G中，如果对于每一对顶点vj,VjV,vjvj,从Vi到Vj和从Vj到Vj都存在路径，则称G是一强连通图。三、应用题1.设有向图G=(V,E),V=VO,V1,V2,V3,V4,V5,E=,请给出图G的邻接矩阵存储结构示意图。O 1O 11231452 3 4 511 111 1请写出顶点V3的入度与出度。入度2出度1请按照上述邻接矩阵存储结构，写出从顶点VO出发分别进行深度优先和广度优先搜索所得到的顶点访问序列；深度：V0V1V4V5V3V2广度：V0V1V2V4V5V32.已知一个有向图的邻接链表存储结构如下:(1)根据有向图的深度优先遍历算法，写出从顶点Vl出发所得到的顶点序列。V1V2V3V6V5V4(2)根据有向图的广度优先遍历算法，写出从顶点Vl出发所得到的顶点序列。V1V2V5V4V3V6