国家开放大学2020年秋季学期期末统一考试数据结构（本）试题2021年1月一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.在数据结构中，从逻辑上可以把数据结构分为（）oA.动态结构和静态结构C.内部结构和外部结构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.0（log2n）C.O（n）D.0（n3）3.在一个单链表中p指向结点a,q指向结点a的直接后继结点b,要删除结点b,可执行（）oA.p->next=q->nextB.p=q->nextC.p->next=qD.p->next=q4.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。A.n-iB.n-i-1C.n-i+1D.i5.一个队列的人队序列是1,2,3,4。则队列的输出序列是（）oA.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2.4,16.在一个栈顶指针为top的链栈中，将一个p指针所指的结点人栈，应执行（）oA.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的子串，)oA.求子串C.模式匹配9.一个非空广义表的表头()oA.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子试卷代号：1252B.紧凑结构和非紧凑结构D.线性结构和非线性结构）。求q在p中首次岀现的位置的算法称为（B.连接D.求串长10.树中的结点数等于所有结点的度数加（）。A.1B.0C.2D.-111.在一棵二叉树上，第5层的结点数最多为（）。A.8R.15C.16D.3212.在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。A.1/2B.1C.2D.413.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）oA.nB.eC.2nD.2e14.有一个长度为12的有序表，按折半査找对该表进行査找，在等概率情况下査找成功的平均比较次数为（）。A.37/12B.39/12C.41/12D.35/1215.从未排序序列中依次取出元素与己经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为（）oA.插入排序B.交换排序C.选择排序D.归并排序二、判断题（根据叙述正确与否在奠后面的括号内打对号“或打叉号“X”。每小题2分，共30分）16.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（）17.数据结构中，元素之间存在多对多的关系称为图状结构。（）18.设有一个单向链表，结点的指针域为next,头指针为head,p指向尾结点，为了使该单向链表改为単向循环链表，可用语句p->next=heado（）19.设有一个单向循环链表，结点的指针域为next,头指针为head,指针p指向表中某结点，若逻辑表达式p->next=二head;的结果为真，贝ijp所指结点为尾结点。（）20.栈和队列都是特殊的线性表，但它们对存取位置的限制不同。（）21.栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先岀表。（）22.递归定义的数据结构通常用递归算法来实现对它的操作。（）23.-个空格的串的长度是0。（）24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。（）25.深度为k的完全二叉树至少有个结点。（）26.完全二叉树中没有度为1的结点。（）27.图的生成树是惟一的。（）28.对连通图进行深度优先遍历可以访问到该图屮的所有顶点。（）29.在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的査找方法是折半査找。（）30.n个元素进行冒泡法排序，通常需要进行n-1趟冒泡。（）三、综合应用及程序设计题（每小题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）；/*队空时，头尾指...
