python数据结构习题汇总.docx

第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.数据复杂度和程序复杂度C.高的速度和正确度D.时间复杂度和空间复杂度7 .在存储数据时，通常不仅要存储各数据元素的值，杯要存储DA.数据的存储方法B.数据处理的方法C.数据元素的类型D.数据元素之间的关系8 .以下叙述不正确的是CoA.数据结构是指数据以及数据相互之间的联系B,数据结构主要指数据的逻辑结构，与计算机的存储和处理无关C.数据的存储结构是指数据在计算机中的存储方式，主要包括线形和非线性D.对于给定的n个元素，可以构造出的逻辑结构有多种9 .下列程序段违反了算法特征。count=0whilecount!=3：print(count)A.明确性B.有限性C.有效性D.功能性10 .下列程序的时间复杂度为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 whiles<n：i=i+l s=s+i returni答：1次(2n)12次(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个数据元素.需要向前移动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个元素，可以构造出的逻辑结构有顺序表和链表两种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个元素后插入一个新元素(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),因此，顺序表也称为随机存取的数据结构。以链式存储结构实现的线性表称为密表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=0foriinrange(n)：ifLi<0：k=Li1.i=Lj1.j=kj+=1else：continuePrint("排序后顺序表：nff.format(L)1 .在一个有序列表中查找元素X,当被查元素X小于列表中某个元素时就可停止。请编写一个函数实现上述查找，并分析此查找在最好情况、最坏情况以及平均情况下的性能。deffound(L,x)：Print("查找元素”)foriinL：ifx>iorx=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+1ifi>Ien(b)：breakPrint("主对角线元素之和为：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/nprint("平均数为:%dw%average)Print("所有大于平均值的元素为：”)foriinL：ifi>average：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 .在下列存储结构中，最适合实现在线性表中进行随机访问的是A.数组B.双向链表C.单向链表D.循环链表3 .与单链表相比，双转亮的优点之一是I)C.可以由最后一个结点找到头结点B.可随机访问C.插入、删除操作更加简单D.访问前驱结点更加方便4如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素,则最好使用OA.顺序表B.单链表C.双向链表D.具有表尾指针的循环单链表5 .在表头指针为head且表长大于1的单向循环锥表中，指针p指向表中的某个结点，若p.next,next=head,则D«B. P指向尾结点A.P指向头结点C. P所指结点的直接后继是头结点I). P所指结点的直接后继是尾结点6 .带表头附加结点的单链表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.表中的元素个数不变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.在进行删除操作后，能保证链表不断开