python数据结构习题汇总

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

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

3、功能性10.下列程序的时间复杂度为DOforiinrange(1,n+1):j=iforkinrange(j+1,n+1):x=x+1A.O(i*j)B.O(n(n-1)/2)C.O(n2/2)D.O(n2)二、解答题1. 下列程序段中，函数my_fun(i,k)的执行次数是n(n+l)/2，该程序的时间复杂度为0(n2)。forkinrange(1,n+1):foriinrange(0,k):ifi!=k:my_fun(i,k)2. 求下列程序段中有数字标号的各语句的执行次数，然后求出该程序段的时间复杂度。deffun(n):i=s=1whilesn:i=i+1s=s+ireturni答：1

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

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

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

7、1WiWn)和求第i个元素的直接前驱(2WiWn)B. 在第i个元素后插入一个新元素(1WiWn)C. 删除第i个元素(1WiWn)D. 将n个元素从小到大排序二、填空题1. 一个一维数组(列表)A的长度为500,起始(A0)地址为2000,每个元素占4个字节，则A80的地址是2320。2. 一个4*6的二维数组A,每个元素占4个字节，假设该数组起始元素A(1,1)的地址是110,若以行为主存储，则A(3,5)的地址是辽4；若以列为主存储，A(3,5)的地址是182。3. 以顺序存储结构实现的线性表简称为，它要求存储空间必须是连续的，并以下标来体现元素之间的关系，在顺序表中访问第i个元素的时间

8、复杂度为，因此，顺序表也称为随机存取的数据结构。以链式存储结构实现的线性表称为。其存储空间可以是不连续的，以指针来体现元素之间的关系。在链表中访问第i个元素的时间复杂度为O(n)，因此，链表也称为顺序访问的数据结构。三、算法设计题1设有一个顺序表L，其元素为整型数据，编写一个要求时间复杂度为0(n)、空间复杂度为0(1)的算法，将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。提示：从L的两端查找，前端找大于0的数据，后端找小于0的数据，然后将两位置的数据交换。L=1,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10n=len(L)

9、print(原顺序表：n.format(L)j=0k=0foriinrange(n):ifLiiorx=i:print(元素x大于或等于,程序继续.format(i)continueelse:print(元素x小于,程序停止.format(i)breakif_name_=_main_:x=eval(input(请输入要查找的元素x：)L=1,2,3,4,5,6,7,8,9found(L,x)3. 已知一个n*n的二维数组a已经以行为主存放在一个大小为n2的一维数组b中，编写一个函数计算此二维数组的主对角线元素之和。count(b,n)defcount(b,n)：x=0i=0whileTrue：

10、x+=bii+=n+1ifilen(b)：breakprint(主对角线元素之和为：d%x)if_name_=_main_：a=1,2,3,4,5,6,7,8,9b=n=len(a)print(二维数组A为：)foriinrange(n)：forjinrange(n):b.append(aij)print(%d%aij,end=t)print()print(存放在一维数组b中为：)print(b)count(b,n)4. 有一值为整型、长度为n的顺序表(列表)，写一个函数，计算该顺序表所有元素的平均值，并输出所有大于平均值的元素。defAverage(L,n):nsum=0foriinrang

11、e(n):nsum+=Liaverage=nsum/nprint(平均数为：d%average)print(所有大于平均值的元素为：)foriinL：ifiaverage：print(i,end=)else：continueif_name_=_main_：L=1,354,56,57,2,8,9,46,767,678n=len(L)Average(L,n)第3章链表一、选择题1. 以下关于链式存储结构的叙述中，C是不正确的。A. 结点除自身信息外还包括指针域，因此空间利用率小于顺序存储结构B. 逻辑上相邻的结点物理上不必邻接C. 可以通过计算直接确定第i个结点的存储地址D. 插入、删除运算操作方

12、便，不必移动结点2. 在下列存储结构中，最适合实现在线性表中进行随机访问的是A.数组B.双向链表C.单向链表D.循环链表3.与单链表相比，双链表的优点之一是DA.可以由最后一个结点找到头结点B.可随机访问C.插入、删除操作更加简单D.访问前驱结点更加方便4. 如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素则最好使用_。A.顺序表B.单链表C.双向链表D.具有表尾指针的循环单链表5. 在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p.next.next二二head。A.p指向头结点B.p指向尾结点C.p所指结点的直接后继是头结点D.p

13、所指结点的直接后继是尾结点6. 带表头附加结点的单链表head为空的判断条件是B。A. head=None#不带头结点的空链表B. head.next=NoneC. head.next=headD. head!=None7. 一个单链表中，若要在指针s所指结点的后面插入一个由指针P所指向的结点，则执行D。A.s.next=pp.next=s.next；B.p.next=s.nexts=pC.s.next=p.nextp.next=sD.p.next=s.nexts.next=p8. 对线性表，在下列情况下应当采用链表表示的是B。A. 经常需要随机地存取元素B. 经常需要进行插入和删除操作C.

14、表中元素需要占据一片连续的存储空间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的后继的语句是BA.p=p.nextB.p.next=p.next.nextC.p.next=pD.p=p.next.next12. 循环链表的主要优点是D。A. 不再需要头指针了B. 已知某个结点的位置后，能很容易找到它的

15、直接前驱结点C. 在进行删除操作后，能保证链表不断开D. 从表中任一结点出发都能遍历整个链表二、填空题1. 一个单链表结构中，每个结点都包含有两个域，称为数据域和指针域C2. 已知一个双向链表(指针域名为next和prior)中间局部如下图所示，P-*现要求将p所指的结点插入到x和y结点之间(即p所指结点后面)，其操作步骤为:p.next二q.nextp.prior二qq.next二pp.next.prior二p2.已知L是不带头结点的单链表，阅读下列函数，回答问题。deffun(L)：#L是不带头结点的单链表的头指针辻(L!二None&L.next!二None)：#语句1q=LL=L.nex

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

17、turnmax2.编写一个函数，实现单链表中删除一个最小值节点的算法(假设该链表中每个节点的值不重复)。deffun1(L):ifL.next=None：returnNoneptr二L.nextp=L.next.nextwhilep!=None：ifp.datan:returnm+1else:returnn+1第6章图形结构一、选择题1. 在一个具有n个顶点的有向完全图中，所含的边数为_B。A. nB.n(n-1)C.n(n-1)/2D.n(n+1)/22. 在一个有向图中，所有顶点的度之和与图的边数之比为。A.1：1B.2：1C.1：2D.不确定3. 个具有n个顶点的无向图，要确保是一个连通

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

19、)/2=28n=8+1=9A.16B.9C.8D.79. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_A。A.出边数B.入边数C.度数D.度数减110. 对某个无向图的邻接矩阵来说，下列叙述错误的是A。A. 第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.依附于顶点v的弧数二、填空题1.已知某无向图的二元组表示为DS=(K,R),K=a,b,c,d,e,f，R二(a,b),(a,c),(a,d),(b,e),(d,e),(c,d),(c,e),(c,f),则顶点c的度为,它的所有邻接点为。2.一个有向图的顶点集为a,b,c,d,e,f,边集为a,c，a,e，c,f，d,c，e,b，e,d,则出度为0的顶点个数为，入度为1的顶点个数为4。3. 一个有n个顶点的无向完全图有