国家开放大学2021年（202101-202107）《1252数据结构（本）》期末考试真题及答案完整版（共2套）

试卷代号：1252国家开放大学2020年秋季学期期末统一考试数据结构（本）试题2021年1月一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.在数据结构中，从逻辑上可以把数据结构分为()。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.内部结构和外部结构 D.线性结构和非线性结构2.下面程序段的时间复杂度是()。for(i=l;i<=n；i++)for（j=l；j<=n；j++）{c[i][j]=0；for(k=l；k<=n；k++)c[i][i]=c[i][j]+a[i][k]*b[k][i];}A.0(1) B.O(log2n)C.O(n) D.0(n3)3.在一个单链表中p指向结点a，q指向结点a的直接后继结点b，要删除结点b，可执行()。A.p->next=q->next B.p=q->nextC.p->next=q D.p->next=q4.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为()。A.n-i B.n-i-lC.n-i+l D.i5.一个队列的人队序列是1，2，3，4。则队列的输出序列是()。A.4,3，2，1 B.1,2,3,4C.1，4，3，2 D.3,2.4,16.在一个栈顶指针为top的链栈中，将一个p指针所指的结点人栈，应执行()。A.top->next=pB.p->next=top->next;top->next=pC.p->next=top；top=pD.p->next=top->next,top=top->next7.判断一个循环队列Q(最多元素为m)为满的条件是()。A.Q->front==Q->rearB.Q->front！=Q->rearC.Q->front==(Q->rear+l)%mD.Q->front!=(Q->rear+l)%m8.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为()。A.求子串 B.连接C.模式匹配 D.求串长9.一个非空广义表的表头()。A.不可能是原子 B.只能是子表C.只能是原子 D.可以是子表或原子10.树中的结点数等于所有结点的度数加()。A.1 B.0C.2 D.-111.在一棵二叉树上，第5层的结点数最多为()。A.8 B.15C.16 D.3212.在一个图G中，所有顶点的度数之和等于所有边数之和的()倍。A.1/2 B.1C.2 D.413.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为()。A.n B.eC.2n D.2e14.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为()。A.37/12 B.39/12C.41/12 D.35/1215.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为()。A.插入排序 B.交换排序C.选择排序 D.归并排序二、判断题（根据叙述正确与否在奠后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）16.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。()17.数据结构中，元素之间存在多对多的关系称为图状结构。()18.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。()19.设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p->next==head;的结果为真，则p所指结点为尾结点。()20.栈和队列都是特殊的线性表，但它们对存取位置的限制不同。()21.栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。()22.递归定义的数据结构通常用递归算法来实现对它的操作。()23.一个空格的串的长度是0。()24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。()25.深度为k的完全二叉树至少有2k-l个结点。()26.完全二叉树中没有度为1的结点。()27.图的生成树是惟一的。()28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。()29.在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的查找方法是折半查找。()30.n个元素进行冒泡法排序，通常需要进行n-l趟冒泡。()三、综合应用及程序设计题（每小题5分，共25分） 31.在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。 intwrite(LinkQueue*q) (QueueNode*p； if(q->front==q->rear)*队空*／ {printf（“队空！无元素可取”）； exit(0)；} while(q->fronr->next!=NULL)（p=q->front->next；q->front->next=p->next;／*出队*／printf(“%4d”,p->data);free(p)；／*释放已出队结点x／}／*队空时，头尾指针指向头结点*／} A.q->front=q->rear B.q=q->next C.q->rear=q->front D.p=p->next32.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidPreorder(structBTreeNode*BT)(if(BT!=NULL){____；Preorder(BT->left)；Preorder(BT->right)；}}A.printf(“%c”,BT->left) B.printf(“%c”.BT->right)Cprintf(“%c”,BT->data) D.printf(“%d”,BT->data)33.一组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？()34.设关键字序列为：(36，69，46，28，30，74)(1)将此序列用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为()。（本小题3分）A.30,28.46,36,69,74 B.28,30,36,46,69,74C.28,30,46,36,69,74 D.30,28.36,46,69,74(2)用冒泡法对上述序列排序，经过两趟冒泡的结果序列为()。（本小题2分）A.36,28,30,46,69,74 B.36,46,28,20,69,74C.38,36,30,46,69,74 D.28,36,30,46,69,7435.设数据序列为：{53，30，37，12，45，24，96)(l)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是()。（本小题3分）A.45,24,53,12,37,96,30 B.37,24,12,30,53,40,96C.12,24,30,37.45,53,96 D.30,24,12,37,45,96,53(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key)=keymod13，则散列地址为1的链中有()个记录。（本小题2分）A.0 B.1C.2 D.3试卷代号：1252国家开放大学2021年春季学期期末统一考试数据结构（本）试题2021年7月一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.下面程序段的时间复杂度是（）。for（i=1；i＜=n；i++）for（j=1；j＜=n；j++）{c[i][j]=O；for(k=l；k＜=n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；} A.O(1) B.O(log2n) C.O(n) D.O(n3)2.数据的存储结构包括数据元素的表示和（）。 A.数据处理的方法 B.相关算法 C.数据元素的类型 D.数据元素间的关系的表示3.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 A.p->next=s；s->next=p->next B.p->next=s->next C.p=s->next D.s->next=p->next；p->next=s4.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 A.p=q->next B.p->next=q C.p->next=q->next D.q->next=NULL5.若让元素1，2，3依次进栈，则出栈顺序不可能为（）。 A.3，2，1 B.2,1,3 C.3，1，2 D.1，3,26.表达式a*(b+c)-d的后缀表达式是（）。 A.abcd*+- B.abc+*d- C.abc*++d- D.-+*abcd7.判断顺序栈s满（元素个数最多n个）的条件是（）。 A.s->top==0 B.s->top!=0 C.s->top==n-l D.s->top!=n-l8.串的长度是指（）。 A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数9.广义表的(a，(d，a，b)，h，(e，((i，j)，k)))深度是（）。 A.6 B.10 C.8 D.410.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（）。 A.18 B.16 C.15 D.1711.在一棵二叉树上，第5层的结点数最多为（）。 A.8 B.15 C.16 D.3212.-个具有n个顶点的无向完全图包含（）条边。 A.n(n-l) B.n(n+1) C.n(n-l)/2 D.n(n+l)/213.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。 A.n B.e C.2n D.2e14.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（）。 A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式15.从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为（）。 A.插入排序 B.交换排序 C.选择排序 D.归并排序二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）16.数据的逻辑结构与数据元素本身的内容和形式无关。 （）17.通常可以把一本含有不同章节的书的目录结构抽象成线性结构。 （）18.要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为next，则可执行q->next=p->next。 （）19.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，则可执行head=head->next；p->next=head；。 （）20.若让元素1，2，3依次进栈，则出栈次序1，3，2是不可能出现的情况。 （）21.递归定义的数据结构通常用递归算法来实现对它的操作。 （）22.队列的特性是先进后出。 （）23.用字符数组存储长度为n的字符串，数组长度至少为n+l。 （）24.-个广义表的表头总是一个广义表。 （）25.若树的度为2时，该树为二叉树。 （）26.深度为5的二叉树最多有31个结点。 （）27.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 （）28.图的深度优先搜索序列和广度优先搜索序列不是惟一的。 （）29.理想情况下，哈希表查找等概率查找成功的时间复杂度是O(1)。 （）30.n个元素进行冒泡法排序，通常第j趟冒泡要进行n-j次元素间的比较。 （）三、综合应用及程序设计题（每小题5分，共25分）31.设线性表以不带头结点的单向链表存储，链表头指针为head。以下程序的功能是输出链表中各结点中的数据域data，完成程序中空格部分。#defineNULL0Voidmain（）{NODE*head，*p；p=head；／*p为工作指针*／do{printf(“%d\n”,p->data)；   ①   ；}while(②)；}①（3分）A.head=p->nextB.p=head->nextC.p=p->nextD.head=head->next②（2分）A.p==NULLB.p!=NULLC.p!=headD.p==head32.写出下列程序执行后的结果SeqQueueQ；InitQueue(Q)；inta[4]={5,8,12,15)；for(inti一0；i<4；i++)InQueue(Q,a[i])；InQueue(Q,OutQueue(Q》；InQueue(Q,30)；InQueue(Q,OutQueue(Q)+10)；while(!QueueEmpty(Q》printf("%d”,OutQueue(Q》；执行后的输出结果为：____。A.58121530B.121553018C.812153018D.12155183033.设查找表为：序号12345678序列412181937556577(1)画出对上述查找表进行折半查找所对应的判定树是（）。（3分）(2)用折半查找在该查找表成功查找到元素55需要经过（）次比较。（2分） A.1 B.2 C.3 D.434.顺序查找算法如下，完成程序中空格部分。Intsearch(NODEa[],intn,intk)／*在a[0]，a[1]…a[n-1]中查找关键字等于k的记录，查找成功返回记录的下标，失败时返回-1*／(inti=0；while(i<n&&a[i].key!=k)   ①   if（   ②   ）returni；elsereturn-1,}①（2分） A.k++； B.i++； C.n++； D.a++：②(3分) A.a[i].key==n B.a[i].key==k C.a[n].key==k D.a[n].key==i35.设数据序列为：{53，30，37，12，45，24，96）(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是（）。（3分） A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96 C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,53(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key)=keymod13，则散列地址为1的链中有（）个记录。（2分） A.0 B.1 C.2 D.3试卷代号：1252国家开放大学2020年秋季学期期末统一考试数据结构(本)试题答案及评分标准(供参考)2021年1月一、单项选择题(每小题3分,共45分)1.D 2.D 3.A 4.C 5.B6.C 7.C 8.C 9.D 10.A11.C 12.C 13.D 14.A 15.A二、判断题(每小题2分,共30分)16.√ 17.√ 18.√