专题12 链 表 知识点一 链表的遍历 1.在一个包含n(n>1)个节点的单链表上，设有头和尾两个指针，下列操作需要遍历多个节点的是( ) A.删除该链表中的第一个节点 B.删除该链表中的最后一个节点 C.在该链表第一个节点前插入一个新节点 D.在该链表最后一个节点后插入一个新节点 2.下列关于单向链表的说法正确的是( ) A.必定有头指针和尾指针 B.每个节点都有一个后继节点 C.删除一个节点，需要修改两个指针 D.查找任一节点的算法时间复杂度为O(n) 3.链表不具备的特点是( ) A.所需存储空间与存储元素个数成正比 B.插入、删除操作不需要移动元素 C.无须事先估计存储空间的大小 D.可随机访问任何一个元素 4.王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下：a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假设head＝3，小明同学的号码是“215”，则他的出场次序是( ) A.2 B.4 C.5 D.6 5.使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为( ) A.0 1 2 3 B.3 1 0 2 C.2 0 －1 1 D.2 0 1 －1 6.某Python程序如下： head＝4 a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]] p＝head while a[p][1]！＝－1： print(a[p][0]，end＝″→″) p＝a[p][1] 程序运行后，输出的结果是( ) A.1→2→3→5 B.1→2→3→5→ C.1→2→3→5→6 D.1→2→3→5→6→ 7.有如下Python程序段： a＝[] h＝－1 for i in range(4)： t＝int(input()) a.append([t，h]) #为列表 a 添加一个新元素 h＋＝1 while a[h][1]！＝－1： print(a[h][0]，end＝″→″) h＝a[h][1] 执行该程序段，依次输入 1、2、3、4 之后，输出的是( ) A.″1→2→3→4→″ B.″1→2→3→″ C.″4→3→2→1→″ D.″4→3→2→″ 8.某超市举办特卖活动，限定对n种商品进行打折大优惠，顾客可通过一体机输入所选商品的条形码信息，查询哪些商品能参加本次特卖。将n种商品的条形码信息存数组a；将顾客所选商品信息存数组b，其中b[i][0]表示某种商品的条形码信息，b[i][1]表示该种商品的名称。查询过程的Python程序部分代码如下： p＝len(b) i＝0 while i
0： p＝a[p][1] k－＝1 while p！＝1： q＝a[q][1] p＝a[p][1] print(a[q][0]) 运行后，输出值不可能是( ) A.g B.h C.u D.o 10.某Python程序如下： data＝[] for i in range(len(a))： data.append([a[i]，i＋1]) data[－1][1]＝－1 la＝head＝0 t＝data[head][1] key，c＝2，0 while c<3 and t！＝－1： if data[t][0]－data[la][0]
