资源简介

第一章 认识数据和数据结构 章节测试
一、选择题
1．数据元素及其关系在计算机存储器内的表示，也称为数据的（ ）
A．线性结构 B．物理结构 C．逻辑结构 D．空间结构
2．下到关于数据结构与算法效率的描述，不正确的是（ ）
A．数据元素是数据的基本单位
B．数据的存储结构应能体现其逻辑结构
C．使用数组结构存储插入、删除较多的数据时，效率较低
D．某单向链表（结点数>2）设有头尾指针，在该链表尾节点后插入一个新节点时需要遍历多个结点
3．在Python程序中，列表(List)就是一批变量的集合。已知列表m[2,4,0,23,1,20]，那么m[1]表示的元素是（ ）
A．1 B．2 C．4 D．20
4．下列关于线性表的描述，正确的是（ ）
A．链表在访问、插入、删除节点操作时，算法效率比数组高
B．栈是一种“先进先出，后进后出”的线性表结构
C．循环队列是首尾相连的队列，数据入队时无需考虑是否会“溢出”
D．字符串是元素个数有限的线性表结构
5．以下说法错误的是（ ）
A．栈是一种先进后出的数据结构 B．队列是一种先进先出的数据结构
C．C++ STL中的map查询时间复杂度为0(1) D．使用哈希时，可能会发生哈希冲突
6．下列场景中蕴含的数据结构思想与图一致的是（　　）
图一：排队做核酸
A．Excel执行撤销操作 B．编号不重复的名单
C．寻宝游戏路线 D．打印机任务面板
7．下列有关数据结构的说法，正确的是（　　）
A．数组、链表、队列、栈、树均为线性表
B．数组和链表的存储空间都是固定不变的
C．在数组中，可通过数组名和下标直接访问数组元素
D．链表中的一个节点就是一个元素，同一链表中每个节点的结构可以不相同
8．下列有关数据结构的说法不正确的是：（　　）
A．频繁进行数据插入和删除操作，链表效率要比数组高
B．单击浏览器“后退”按钮可回到刚才浏览过的网页， 说明网页数据是采用栈进行组织的
C．队列是一种先进先出的线性表，插入一端为队首，删除一端为队尾
D．使用数组在进行数据插入和删除操作时，不一定会引起数据移动
9．下列关于数据结构的说法不正确的是（ ）
A．数据结构是指数据的组织形式 B．二维数组属于线性数据结构
C．链表是一种优于数组的数据结构 D．队列是限定仅在一端进行插入，在另一端进行删除的线性数据结构
10．下列关于数据结构的说法，正确的是（ ）
A．用程序实现问题解决时只能采用一种数据结构
B．数据的逻辑结构是指数据元素间的关系
C．链表比数组更适合大量数据元素的随机访问
D．数组不必占用一片连续存储的单元
11．已知Python列表a=［'W'，'o'，'r'，'d'］，依次执行a.pop()、a.append(1)、a.append(d)操作，列表a的值为（　　）
A．［'W'，'o'，'r'，'d'］
B．［'W'，'o'，'r'，'1'，'d'］
C．［'o'，'r'，'d'，'1'，'d'］
D．［'1'，'d'，'o'，'r'，'d'］
12．图形结构中的每一个结点（ ）
A．无直接后继结点 B．无直接前驱结点
C．只有一个直接前驱结点和一个直接后继结点 D．可能有多个直接前驱结点和多个直接后继结点
13．下列对数据结构的描述不正确的是（ ）
A．数据的逻辑结构是数据元素在计算机存储器中的存储方式
B．对同一事物构造的数据结构不同，数据处理的过程就不同
C．数据的存储结构不同，对数据进行同一操作的实现方法也不同
D．顺序存储结构是最基本的存储方法
14．以下数据结构中哪一个是非线性结构？（ ）
A．队列 B．列表
C．树 D．线性表
15．以下选项中，属于integer类型常量的是（ ）
A．123 B．3.1415
C．’ 1.23E+04’ D．True
16．如下图所示，从图中可知中国的人均GDP处于上涨状态。以上采用的数据分析方法是（ ）
A．平均分析和交叉分析 B．对比分析和交叉分析
C．平均分析和对比分析 D．对比分析和结构分析
17．除了首元素没有前趋元素，尾元素没有后续元素外其他所有元素都只有一个前趋元素和后续元素，这种数据结构属于（ ）
A．树结构 B．图结构 C．线性结构 D．集合结构
18．下列关于数据结构的说法正确的是（ ）
A．同一数据元素中各数据项的数据类型一定相同
B．跳跃表是立足链表、借鉴二分查找的思想而形成的数据结构
C．若入栈序列为 abcd，则出栈序列可能为 dbca
D．在浏览器中执行“后退”、“前进”操作的原理与队列的特点相同
19．一份有效的数据分析报告，能够帮助用户（ ）
A．了解事物发展现状，预判事物发展趋势 B．有效判断所需解决问题的影响因素
C．有针对性地选择解决问题的方案 D．以上都是
20．在一个单向链表（如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点），则执行的操作是(　　)
A．tail所指节点的data3值赋为r所指节点的data4值
B．r所指节点的next值赋为tail
C．r所指节点的next值赋为－l
D．tail所指节点的next赋为r,r所指节点的next值赋为－l
21．一个栈的入栈序列为1，2，3，4，5，其出栈序列为s1，s2，s3，s4，s5。若s2是3，则s1不可能是（ ）
A．1 B．2 C．4 D．5
22．下列关于数据和信息的说法正确的是（ ）
A．数据是信息的载体，数据是信息所表示的意义 B．数据是信息的载体，信息是数据所表示的意义
C．信息是数据的载体，数据是信息所表示的意义 D．信息是数据的载体，信息是数据所表示的意义
23．用两个列表a、b分别保存单向链表中的数据区域和指针区域。如下图所示，在节点x与节点y之间插入一个新节点，操作步骤正确的是（ ）
①b[i]= b[y] ②b[i]= b[x] ③b[y]= i
④b[x]=i ⑤b[i]= x ⑥b[i]= y
A．③⑥ B．④② C．①③ D．②④
24．有如下python程序段：
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end="->")

print(a[p][0])
上述程序段要遍历链表中的所有元素，划线处应添加的代码是（）
A．p+=1 B．a[p][1]+=1 C．p=a[p][1] D．a[p][1]=a[a[p][1]][1]
25．下列关于数据结构的说法，正确的是（ ）
A．基本数据类型是在程序设计时利用结构数据类型构造出的新类型
B．数据结构设计主要考虑数据之间的存储结构
C．Python列表中数据的存储结构和逻辑结构相同
D．行优先的6行10列方阵a首地址为SA，每个元素占10个字节，那么a[2][3]的起始地址为SA+230
二、操作题
26．张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。
（1）根据题意，部分的单词库数据逻辑结构如图所示，查找单词“byte”的过程是“binary”→“bit”→“byte”，补充图中空白单元格的值为
列表索引 数据区域 指针区域
0 audio 音频 -1
1 binary 二进制数 6
2 byte 字节 -1
3 cursor 光标 -1
4 access 存取 1
5 cache 高速缓存 3
6 bit 比特 ________
（2）wordlist（data，info）函数实现将词汇数据库data以链表的方式按字母序升序排列。info表示词汇数据库中各字母开头的最小单词位置，如info[0]表示字母a开头的最小单词在词汇数据库data中的位置。实现该功能的程序如下，请在划线处填入合适的代码。
def wordlist（data，info）：
n=len（data）
for i in range（n）：
data[i]．append（—1） #data[i]追加一个元素—1
for i in range（n）：
d=data[i][0]
①
if info[k] ==-1：
info[k] = i
else：
head=info[k]
q=head
while②
p=q
q=data[q][2]
if q！=head：
data[p][2]=i
data[i][2]=q
else：
data[i][2]=head
③
return data，info
（3）searchword（data，info，key）函数实现单词的查找。程序如下，请在划线处填入合适的代码。
def searchword（data，info，key）：
k=ord（key[0]）—ord（"a"）
head=info[k]
p=head
while p！=-1：
if data[p][0]==key：
return
p=data[p][2]
return"没有找到该单词"
读取词汇数据库，存入列表data中，列表的每个元素包含2个数据项，分别为英文单词和中文翻译，如data=[['audio'，'音频']，['binary'，'二进制数']…]，数据读取存入的代码略。
’’’
info=［-1]*26
data，info=wordlist（data，info）
key=input（"请输入查找单词："）．lower() #转化为小写字母
res=searchword（data，info，key）
print（key，“查找结果是：”，res）
27．有个火车站的铁轨调度方法如下：火车从一方1,2,3,4…依次进入，由于每个火车皮要去的目标车站不一样，想让车皮到站后能以最少的时间从火车上脱离，就让最近到的车皮放在整列火车的最后。因此需要转换站来达成这样的目标，转换站只能在同一个地方进与出。例如有四个车皮1,2,3,4进入，2,4,3,1到站，即2号车皮目的地最远，4号车皮倒数第二远，3号车皮倒数第三远，1号车皮最近。
为了能快速指挥车辆进出站转换，小王编写例如下程序
a=[1,2,3,4,5,6] #待车皮进站
b=[3,2,1,6,5,4] #出站顺序
stack=[0]*len(a)
top=0
stack[top]=a[0]
s=str(a[0])+"进"
ha=1;hb=0
while :
while top>-1 and :
s=s+str(stack[top])+"出"
top-=1
if hatop+=1
stack[top]=a[ha]
s=s+str(a[ha])+"进"
ha+=1
elif ha==len(a) and top>-1 and :
print("无法调度")
break
if top==-1:
print(s)
代码显示结果：1进2进3进3出2出1出4进5进6进6出5出4出
(1)修改加框处代码
(2)将划线处代码补充完整，使功能完善
28．双向链表也叫双链表，也是链表的一中，它的每个数据都有两个指针，分别指向前驱节点和后继节点。在python中用二维列表来模拟双向链表，用包含3个元素的列表来表示每一个节点，其中第一个元素存储数据，后两个元素分别存储指向前驱节点和后继节点的指针。若没有前驱或后继节点则对应的指针值为-1。下列程序产生了一些两位随机正整数，并依次存储到双向链表a中。现要求删除其中值为偶数的节点，请完善代码：
import random
a=[]
head=-1
for i in range(8):
node=[ ① ,head,-1]
a.append(node)
if head!=-1:
a[head][2]=i
head= ②
p=head=0
while p!=-1:
if a[p][0]%2==0:
if ③ :
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
a[a[p][2]][1]=a[p][1]
if head==p:
head= ④
p=a[p][2]
参考答案
1．B
2．D
3．C
4．D
5．C
6．D
7．C
8．C
9．C
10．B
11．B
12．D
13．A
14．C
15．A
16．C
17．C
18．B
19．D
20．D
21．D
22．B
23．D
24．C
25．D
26．2 k=ord(d[0])—ord(“a”) q != -1 and d>data[q][0] info[k]=i data[p][1]
27．top>-1 and hb<=len(b) stack[top]==b[hb] hb+=1 stack[top]!=b[hb]
28．random.randint(10,99) i a[p][1]!=-1 a[p][2]

展开更多......

收起↑