1、试卷代号：1252 国家开放大学2021年春季学期期末统一考试数据结构（本）试题答案及评分标准（供参考）2021年7月一、单项选择题（每小题3分，共45分）1.0 6.B 2.D 7.C 3.D 8.B 11.C 12.C 13.D 二、判断题（每小题2分，共30分）16.J 21.J 26.J 17.X 22.X 27.X 18.-J 23.-J 28.-J 三、综合应用及程序设计题（每小题5分，共25分）31.CD c.或p=p-next(3分）B.或p!=NULL(2分）32.B.或1215 5 30 18 33.Cl)D.(2)B.或234.(DB.或i+;(2分）B.或ai.key=
2、k(3分）35.(l)B.或37,24,12,30,53,45,96(3分）(2)B.或1(2分）4.C 9.D 14.B 19.J 24.X 29.J 5.C 10.D 15.C 20.X 25.X 30.J(1252号）数据结构（本）答案第1页（共1页）试卷代号：1252 座位号DJ国家开放大学2021年春季学期期末统一考试数据结构（本）试题o-2021年7月刁了吕瞰弥眯长名站）蓝o-三巨一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.下面程序段的时间复杂度是（）。三三勹for(i=l;i=n;i+)for(j=l;j=n;j+)cij=O;for(k=l;knex
3、t=s;s-next=pnext B.p-next=s-next C.p=s-next D.s-next=pnext;pnext=s(1252号）数据结构（本）试题第1页（共6页）4.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A.p=qnext C.Pnext=q-next B.p-next=q D.qnext=NULL 5.若让元素1,2,3依次进栈，则出栈顺序不可能为（）。A.3,2,1 c.3,1,2 A.s-top=O C.stop=n1 B.2,1,3 D.1,3,2 6.表达式a*(b+c)-d的后缀表达
4、式是（）。A.abed*+-B.abc+*d C.abc*+cl-D.-+*abed 7.判断顺序栈s满（元素个数最多n个）的条件是（）。B.s-top!=O D.s-top!=n-1 8.串的长度是指（）。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数9.广义表的(a,(d,a,b),h,(e,(Ci,j),k)深度是（）。A.6 C.8 B.10 D.4 10.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（）。A.18 C.15 B.16 D.17 11.在一棵二叉树上，第5层的结点数最多为（）。A.8 B.15
5、C.16 D.32 12.一个具有n个顶点的无向完全图包含（）条边。A.n(n-1)B.n(n+D C.n(n1)/2 D.n(n+l)/2(1252号）数据结构（本）试题第2页（共6页）13.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。A.n C.2n B.e D.2e 14.对千一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该()。A.以顺序存储方式C.以索引存储方式B.以链接存储方式D.以散列存储方式15.从未排序序列中挑选元素，并将其放入巳排序序列的一端，此方法称为（A.插入排序B.交换排序
6、C.选择排序D.归并排序得分1评卷人）。二、判断题（根据叙述正确与否在其后面的括号内打对号1或打叉号X。每小题2分，共30分）16.数据的逻辑结构与数据元素本身的内容和形式无关。（)17.通常可以把一本含有不同章节的书的目录结构抽象成线性结构。（)18.要在一个单向链表中删除p所指向的结点，巳知q指向p所指结点的直接前驱结点，若链表中结点的指针域为next,则可执行q-next=p-next。()19.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next,头指针为head,尾指针为p,则可执行head=head-next;p-next=he
7、ad;。（）20.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（)21.递归定义的数据结构通常用递归算法来实现对它的操作。()22.队列的特性是先进后出。（)23.用字符数组存储长度为n的字符串，数组长度至少为n+l。()24.一个广义表的表头总是一个广义表。（)25.若树的度为2时，该树为二叉树。（)(1252号）数据结构（本）试题第3页（共6页）26.深度为5的二叉树最多有31个结点。()27.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（)28.图的深度优先搜索序列和广度优先搜索序列不是惟一的。（)29.理想情况下，哈希表查找等
8、概率查找成功的时间复杂度是0(1)。（)30.n个元素进行冒泡法排序，通常第j趟冒泡要进行n-j次元素间的比较。（尸三、综合应用及程序设计题（每小题5分，共25分）31.设线性表以不带头结点的单向链表存储，链表头指针为head。以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。#define NULL 0 void main()NODE*head,*p;p=head;/*p为工作指针do print(%dn,p-data);。while();(D(3分）A.head=p-next C.p=pnext(2分）A.p=NULL B.p=head-next D.head=hea
9、d-next B.p!=NULL C.p!=head D.p=head(1252号）数据结构（本）试题第4页（共6页）)哉造烯卫头艰嗦谯32.写出下列程序执行后的结果(2)用折半查找在该查找表成功查找到元素55需要经过（）次比较。(2分）瞰抑郎长芒悉蓝衵SeqQueue Q;lnitQueue(Q);int a 4=5,8,12,15;for(int i=O;i4;i+)InQueue(Q,中）；InQueue(Q,OutQueue(Q);InQueue(Q,30);In Queue(Q,Out Queue(Q)+10);while(!QueueEmpty(Q)printf(%cl,OutQu
10、eue(Q);A.1 B.2 C.3 D.4 34.顺序查找算法如下，完成程序中空格部分。int search(NODE a ,int n,int k)在aO,alan-1中查找关键字等于k的记录，查找成功返回记录的下标，失败时返回一1*/执行后的输出结果为：A.5 8 12 15 30 C.8 12 15 30 18 33.设查找表为：A.C.B.12 15 5 30 18 D.12 15 5 18 30:I:I/2 I ts I/913571 5651:51787(1)画出对上述查找表进行折半查找所对应的判定树是（B)。(3分）D.(1252号）数据结构（本）试题第5页（共6页）int i
11、=O;while Ci n&.&.ai.key!=k)。if()return i;else return1;(D(2分）A.k+;C.n+;(Z)(3分）A.a臼.key=n B.ai.key=k C.an.key=k D.an.key=i 35.设数据序列为：53,30,37,12,45,24,96(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择B.i+;D.a+;的序列是（)。(3分）A.45,24,53,12,37,96,30 C.12,24,30,37,45,53,96 B.37,24,12,30,53,45,96 D.30,24,12,37,45,96,53(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key)=keymod 13,则散列地址为1的链中有（）个记录。(2分）A.o C.2 B.1 D.3(1252号）数据结构（本）试题第6页（共6页）
