python数据结构习题汇总

1、第章数据结构导论一、选择题1算法的时间复杂度取决于A。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 是B的有限集合。A算法B数据元素C数据操作D数据关系6算法效率的度量是DA正确度和简明度B数据复杂度和程序复杂度C高的

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

3、in range(1,n+1):j=ifor k in range(j+1,n+1):x=x+1A O(i*j)BO(n(n-1)/2)C O(n2/2)DO(n2)二、解答题1下列程序段中，函数my_fun(i,k)的执行次数是n(n+1)/2，该程序的时间复杂度为O(n2)。for k in range(1,n+1):for i in range(0,k):if i!=k:my_fun(i,k)2求下列程序段中有数字标号的各语句的执行次数，然后求出该程序段的时间复杂度。def fun (n) : i=s=1 while sn :i=i+1s=s+ireturn i答： 1 次（2n） 1/

4、2 次（2n） 1/2 - 1次 1 次 O（ n1/2 ）第章数组结构一、选择题1线性表是一个A。A. 有限序列，可以为空B.有限序列，不能为空C. 无限序列，可以为空D.无限序列，不能为空.2下面关于线性表的叙述中，错误的是B。A. 线性表采用顺序存储，必须占用一片连续的存储单元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 个位置插入一个元素，需要依次向后移动D个元素。A. n-iB. n+iC. n-i-1D. n-i+16一个顺序表所占存储空间的大小与D无关。A 顺序表长度B结点类型C结点中个数据域的类型D结点的存放次序7.以下叙述不正确的是D。A. 数据的逻辑结构包括线性和非线性结构，非线性结构包括树和图两种。B. 数据的逻辑结构主要指元素间的关系，与计算机的存储和处理无关C. 数据的存储结构是指数据在计算机中的存储方式，主要包括顺

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

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

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

9、= 1,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10n = len(L)print(原顺序表： n.format(L)j = 0k = 0for i in range(n):if Li i or x = 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 的

10、二维数组a 已经以行为主存放在一个大小为n2 的一维数组b 中，编写一个函数计算此二维数组的主对角线元素之和。count(b,n)def count(b,n):x=0i=0while True:x += bii += n+1if i len(b):breakprint(主对角线元素之和为:%d%x)if _name_ = _main_:a = 1,2,3,4,5,6,7,8,9b = n = len(a)print(二维数组A 为： )for i in range(n):.for j in range(n):b.append(aij)print(%d%aij,end=t)print()prin

11、t(存放在一维数组b 中为： )print(b)count(b,n)4. 有一值为整型、长度为 n 的顺序表 （列表），写一个函数，计算该顺序表所有元素的平均值，并输出所有大于平均值的元素。def Average(L,n):nsum = 0for i in range(n):nsum += Liaverage = nsum / nprint(平均数为 :%d%average)print(所有大于平均值的元素为：)for i in L:if i average:print(i,end= )else:continueif _name_ = _main_:L = 1,354,56,57,2,8,9,

12、46,767,678n = len(L)Average(L,n)第章链表一、选择题1以下关于链式存储结构的叙述中，C是不正确的。A结点除自身信息外还包括指针域，因此空间利用率小于顺序存储结构B逻辑上相邻的结点物理上不必邻接C可以通过计算直接确定第i 个结点的存储地址D插入、删除运算操作方便，不必移动结点2.在下列存储结构中，最适合实现在线性表中进行随机访问的是A。A. 数组B.双向链表C.单向链表D.循环链表.3.与单链表相比，双链表的优点之一是D。A可以由最后一个结点找到头结点B可随机访问C插入、删除操作更加简单D访问前驱结点更加方便4如果对线性表的运算只有2 种，即删除第一个元素，在最后一

13、个元素的后面插入新元素，则最好使用D。A顺序表B单链表C双向链表D具有表尾指针的循环单链表5在表头指针为head 且表长大于1 的单向循环链表中，指针p 指向表中的某个结点，若p.next.next=head，则D。A. p 指向头结点B. p指向尾结点C. p 所指结点的直接后继是头结点D. p所指结点的直接后继是尾结点6带表头附加结点的单链表head 为空的判断条件是B。A. head=None#不带头结点的空链表B. head.next=None C. head.next=headD. head!=None7.一个单链表中，若要在指针s 所指结点的后面插入一个由指针P 所指向的结点，则执

14、行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. 表中元素需要占据一片连续的存储空间D. 表中的元素个数不变9如果最常用的操作是取第i 个结点及前驱，则采用A存储方式最节省时间。A顺序表B双链表C单循环链表D单链表10从一个具n 个结点的单链表中查找其值等于x 的结点时， 在查找成功的情况下，需平均比较D个结点。.A nB n/2C (n-1)

15、/2D (n+1)/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. 在进行删除操作后，能保证链表不断开D. 从表中任一结点出发都能遍历整个链表二、填空题1.一个单链表结构中，每个结点都包含有两个域，称为数据域和指针域。2. 已知一个双向链表（指针域名为next 和 prior ）中间局部如下图所示，现要求将p 所指的结点插入到x 和 y 结点之

16、间（即p 所指结点后面） ，其操作步骤为：p.next = q.next;p.prior = q;q.next = p;p.next.prior = p;2. 已知 L 是不带头结点的单链表，阅读下列函数，回答问题。def fun(L): #L是不带头结点的单链表的头指针if ( L!=None & L.next!=None ):#语句 1q=LL=L.nextp=Lwhile(p.next!=None):#语句5p=p.nextp.next=qq.next=Nonereturn L;（1）说明该函数执行的条件，即语句1 的功能Len（ L） 1.（2）说明语句5（即 while循环）的功能查

17、找尾结点（3）若链表L 的初始状态如下图，画出执行上述函数后的链表L 的示意图。La 2a 3a 4a 5a 1pq三、算法设计题1编写一个函数，实现从单链表中查找出所有元素的最大值，该值由函数返回。def fun(L)：if L.next= None:return 0Max = L.next.datap = L.next.nextwhile p != None:if p.data max:max = p.datap = p.nextreturn max2编写一个函数，实现单链表中删除一个最小值节点的算法（假设该链表中每个节点的值不重复）。def fun1(L)：if L.next= None

18、:return Noneptr = L.nextp = L.next.nextwhile p != None:if p.data n:return m + 1else:return n + 1第章图形结构一、选择题1在一个具有n 个顶点的有向完全图中，所含的边数为_B_。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/22在一个有向图中，所有顶点的度之和与图的边数之比为B。A.1 ：1B.2：1C.1：2D.不确定3一个具有n 个顶点的无向图，要确保是一个连通图，至少需要A条边。A. n-1B. nC. n+1D. n/24在一个有向图中，所有顶点的入度之和等于所有顶点的出

19、度之和的C倍。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 条边，则该图至少有B个顶点。 n(n-1)/2=28n=8+1=9A.16B.9C.8D.79在一个有向

20、图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_A_。A.出边数B.入边数C.度数D.度数减10对某个无向图的邻接矩阵来说，下列叙述错误的是A。A. 第 i 行与第 i 列上的非零元素的总数等于顶点vi 的度数B. 矩阵中的非零元素个数等于图中的边数的2 倍.C. 第 i 行上的非零元素个数和第i 列上的非零元素个数一定相等D. 矩阵是一个 n n 的方阵（ 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 的度为4，它的所有邻接点为a,d,e,f。2 一 个 有 向 图 的 顶 点 集 为 a,b,c,d,e,f,边 集 为 ,则出度为的顶点个数为2，入度为的顶点个数为4。3一个有 n 个顶点的无向完全图有