高中信息技术粤教版(2019)选修一 1.3 认识数据结构

高中信息技术粤教版(2019)1.3 认识数据结构 一、选择题 1．数据结构在程序设计中的作用不包括（     ） A．提高程序运行效率 B．方便数据的存储和检索 C．增加代码的复杂度 D．有助于算法设计 2．列表d中存入了一列数据如表所示，采用顺序查找的方法查找数据，以下叙述正确的是（    ） d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] 12 33 15 －7 11 13 17 19 43 29 A．顺序查找只能从d[1]开始，逐一进行比较 B．无论是否找到，顺序查找必须完成对所有的数据的比对查找 C．在数据规模较大的情况下，顺序查找的平均查找效率低于对分查找 D．必须先将数据排序之后才可以采用顺序查找 3．在C语言的变量类型说明中，int,char,float等类型的长度是（  ） A．固定的 B．由用户自己定义的 C．任意的 D．与机器字长有关的 4．数据元素及其关系在计算机存储器内的表示，也称为数据的（   ） A．线性结构 B．物理结构 C．逻辑结构 D．空间结构 5．栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”，则所有可能的出栈序列中，以“旦”结尾的序列个数为（   ） A．3 B．4 C．5 D．6 6．在浏览网页时，可以通过超链接的方式实现网页间的跳转。与这种网页之间相互链接的表现形式相似的数据结构是（   ） A．队列 B．栈 C．链表 D．树 7．在数据结构中，从逻辑上可以把数据结构分成（   ） A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非性结构 D．内部结构和外部结构 8．下列有关数组的描述，错误的是（   ） A．数组是由相同数据类型的变量组成的一个序列 B．数组中的每个元素按照下标顺序依次存储 C．二维数组中的元素在内存中的存储方式有行优先存储和列优先存储两种 D．在数组中进行插入、删除操作时无需移动数据元素 9．数据结构设计的主要目的是（     ） A．只为了数据的存储 B．反映数据之间的逻辑关系并提高数据处理效率 C．仅仅为了美观地展示数据 D．无特定目的，仅作为编程习惯 10．下图是物流配送线路图，是树结构，下列说法错误的是( ) A．一级快件集散中心是树的根结点 B．二级公共配送中心进行地域分配，是一级快件集散中心根结点下的子树 C．共同配送点是二级公共配送中心的子树 D．共同配送点-社区便利店的树的深度是3 11．用两个列表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．②④ 12．在存储数据时，通常不仅要存储各数据元素的值，还要存储（　　） A．数据的存储方法 B．数据处理的方法 C．数据元素的类型 D．数据元素之间的关系 13．在Python中，若需将100位学生的姓名分别存储在数组元素name[0]～name[99]中，则下列创建方法正确的是（   ） A．name[0:99]="" B．name[100]="" C．name=[0 for i in range(100)] D．name=[""]*100 14．某二叉树使用一维数组存储结构进行存储： 索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 节点 A B C D E F G H I 下列有关该二叉树的说法正确的是（   ） A．该树的中序遍历为B-D-A-G-E-H-C-I-F B．该树中共有3个叶子节点，分别是D、G、H C．该树的深度为4，度为2的节点有5个 D．某节点的索引是 i，那么它的左子节点索引为2*i，右子节点索引为2*i+1 15．列表顺序列出了7个同学的身高（单位：厘米）（见下表），若用对分查找算法查找数值168，则依次被访问到的数据是（   ） 188 177 175 172 168 166 155 A．172、155、158 B．172、166、168 C．188、155、168 D．155、166、168 二、填空题 16．在计算机编程中， 是一种用于描述程序中数据的组织方式。 17．小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1，停靠站时间忽略不计；换乘地铁的用时也都相等，记为t2。 （1）如果t1＝t2，小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线。 （2）设t1＝2min，t2＝lmin，则小明从A站出发到达B站的最短用时为 min。 18．指出下列数据所属的数据类型 （1）789( )（2）345.890( ) (3)‘N’( ) （4）1.23e2( )（5）“C语言”( ) 19．数据结构中的堆是一种特殊的完全二叉树，其中每个节点的键值都大于或等于其子节点的键值，这种堆称为 。 20．有一维数组1、2、3、4、5，依次按照某一线性存储，请回答以下问题： （1）如果该线性结构是队列，写出出队序列。 （2）如果该线性结构是栈，输出序列可能是4、3、5、1、2吗？为什么？ 三、操作题 21．某技能培训需要修完n（编号为0～n-1）门课程，但在学习某些课程前必须先完成其他课程的学习，每门课程可以有若干个前置课程，最多只能作为一门课程的前置课程。若n=5，如图a表示课程间的依赖关系，从中可知：完成课程4必须先完成课程0与课程5，完成课程3必须先完成课程1与课程4。 现根据各门课程之间的依赖关系判断能不能顺利按要求学完所有的课程，若可以，则输出任意一种课程顺序，如根据图a可行的一种课程顺序可以为：0，5，4，1，3，2。     图a                        图b （1）若将图a加框处中的“3”改为“4”，请写出其中一组可行的课程顺序： 。 （2）小明发现若所有课程都有前置课程，如图b，则不能完成所有课程的学习，于是他设计了如下judge（n，kc）函数用于判断是否有可行的课程顺序来完成所有课程的学习，其中参数kc是存储各门课程之间依赖关系的列表，如kc=[[0，1]，[1，2]，[2，0]]。 defjudge（n，kc）： link=[-1]*n pre=[0]*n for i in range（len（kc））： link[kc[i][0]]=kc[i][1] pre[kc[i][1]]=1 c=0 for i in range（len（pre））： if pre[i]==0： c+=1 if c==0： return False else： return True ①小明在调试过程中，发现上述程序存在问题，不能完全判断是否有可行的课程顺序，下列选项中，若n均为4，则哪一组测试数据能发现问题 （单选，填字母）。 A．kc=[[2，3]，[3，1]，[0，1]] B．kc=[[0，2]，[2，3]，[3，1]，[1，2]] C．kc=[[1，2]，[2，1]，[0，3]，[3，0]] D．kc=[[0，1]，[1，2]，[2，3]，[3，0]] ②小明重新设计了如下算法，对变量f赋初值的语句f=[0]*n应填在哪一处位置： （选填A或B） defjudge（n，kc）： link=[-1]*n for i in range（len（kc））： link[kc[i][0]]=kc[i][1] i=0 A while i<len（kc）： p=i B while p!=-1： if f[p]==0： f[p]=1 else： return False p=link[p] i+=1 return True （3）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。 #读取总课程数存入n，代码略。 #读取各门课程之间的依赖关系存入kc，代码略。 link=[-1]*n pre=[0]*n for i in range（len（kc））： link[kc[i][0]]=kc[i][1] ① if judge（n，kc）： que=[0]*（n+1） head=0；tail=0 for i in range（n）： if② ： que[tail]=i tail+=1 ans=[] while head!=tail： u=que[head] head=head+1 ans.append（u） pre[link[u]]-=1 if pre[link[u]]==0： ③ tail+=1 print（“可能的选修课程顺序为：”，ans） else： print（“不存在可行的选修顺序！”） 22．下列程序的功能是将两个存放升序数据的数组合并为一个新数组，要求新数组中的数据仍保持有序。 实现上述功能的程序如下，请在程序划线处填入合适的代码。 #输入一个有序数据序列，并存储在数组a中，代码略 #输入一个有序数据序列，并存储在数组b中，代码略 n1=len(a) n2=len(b) c=[0]*(n1+n2) #存放合并后的数据 k=i=j=0 while ① : #a、b数组均有数据时     if a[i]<=b[j]:         ②         i+=1         k+=1     else:         c[k]=b[j]         j+=1         k+=1 while i<n1: #a数组还剩有数据时     c[k]=a[i]     i+=1     k+=1 while j<n2: #b数组还剩有数据时     ③     j+=1     k+=1 print(′合并后数组c中的元素为:′,c) 程序划线①处应填入的代码为： ； 程序划线②处应填入的代码为： ； 程序划线③处应填入的代码为： 。 四、简答题 23．链表的特点？ 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．C 3．A 4．B 5．C 6．C 7．C 8．D 9．B 10．D 11．D 12．D 13．D 14．A 15．B 16．数据结构 17． A-L-K-H-G-B 或 A-L-K-J-I-B 12 18． int float char double char 19．大顶堆（或最大堆） 20． 1、2、3、4、5 不可能，因为：4是第一出栈字符，说明1，2已别压入栈内，并且压入栈的次序为12345；由以上得出：1、2出栈的顺序只能是2、1，而不是1、2。所以，出栈序列4、3、5、1、2是不可能的。 21． 0 1 5 4 3 2（015的顺序可以任意） B B pre[kc[i][1]]+=1 pre[i]==0 que[tail]=link[u] 22． i<n1 and j<n2 c[k]=a[i] c[k]=b[j] 23．只需知道数据之间相互链接的顺序 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$