1252数据结构（本）-国家开放大学2022年1月（2021秋）期末考试真题-开放本科.docx

试卷代号：1252国家开放大学2021年秋季学期期末统一考试数据结构（本）试题2022年1月一、单项选择题（把合适的选项编号填写在括号内。每题3分，共45分）1 .以下说法中，不正确的选项是（）。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可有假设干个数据元素构成D.数据项可由假设干个数据元素构成'.每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）存储方式。A.顺序B.链接C.索引D.散列.在一个单链表中p指向结点a, q指向结点a的直接后继结点b,要删除结点b,可执行 （ ）。A.p->next=q->nextC.p->next=qB.p=q->nextI). p->next=q4.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。A. p->ncxt=s;s->noxt=p->ncxtB. p->next=s->nextC. p=s->nextI）. s->next=p->next, p->next=s5.向顺序栈中压入新元素时，应当（A.先移动栈顶指针，再存入元素C.先后次序无关紧要）。B.先存入元素，再移动栈顶指针D.同时进行6. 一般情况下，将递归算法转换成等价的非递归算法应该设置（A.栈C.堆栈或队列B.队列D.数组7.判断一个循环队列Q(最多元素为m)为满的条件是(A. Q->front=Q->rearB. Q->front!=Q->rearC. Q->front=(Q->rear+l)%mD. Q->front! = (Q->rcar+l)%m.空串与空格串（）。A.相同C.可能相同.广义表（f, h, （a, b, d, c）, d, e, （i,A. 6C.8.二叉树第k层上最多有（）个结点。A. 2kC. 2k-l.树中的结点数等于所有结点的度数加（A. 1B.不相同I）.无法确定 j）, k）的长度是（B. 10D. 4B. 2k-1D. 2k-l)oB.O）。C.2D.-l.对于具有n个顶点的图，假设采用邻接矩阵表示，那么该矩阵的大小为（）。A. nB. n2C. n-lD. （n-l）2.对于一个具有n个顶点和e条边的无向图，假设采用邻接表表示，那么所有顶点邻接表中的 结点总数为（）。A. nB. eC. 2nD. 2e.采用折半查找方法查找长度为n的线性表时，其算法的时间复杂度为（）。A. 0（n2）B. 0（nlog2n）C.O（n）D.0（log2n）.从未排序序列中依次取出元素与已经排好序的序列中的元素作比拟。将其放人已排序序 列的正确的位置上，此方法称为（）。A,插入排序B.交换排序C.选择排序D.归并排序二、判断题（根据表达正确与否在其后面的括号内打对号“ 或打叉号“X”。每题2 分,共30分）12 .数据元素可以有一个或多个数据项组成。（）13 .数据结构中，元素之间存在多对多的关系称为图状结构。（）14 .设有一个单向链表，结点的指针域为next,头指针为head, p指向尾结点，为了使 该单向链表改为单向循环链表，可用语句p->next=head。（）15 .设有一个单向循环链表，结点的指针域为nexl,头指针为head,指针p指向表中某 结点，假设逻辑表达式p->next=head;的结果为真，那么p所指结点为尾结点。（）16 .循环队列队头指针在队尾指针前一个位置，队列是“满”状态。（）17 .栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。（）18 .向一个栈顶指针为h的链栈（结点的指针域为next）中插入一个s所指结点时，先执 行s->next=h,再执行h二s操作。（）19 .串的两种最基本的存储方式是顺序和链接。（）20 .对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、 列号和元素值三项信息。（）21 .深度为k的完全二又树至少有2k-l个结点。（）22 .如果结点A有3个兄弟，而且B是A的双亲，那么B的度是4。（）23 .用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有 关。（）24 .对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）25 .二叉排序树在呈单支二叉树时，查找效率最低。（）26 .冒泡排序是一种比拟简单的插入排序方法。（）三、综合应用及程序设计题（每题5分，共25分）27 .设有一个头指针为head的不带头结点单向链表中（结点类型为NODE）, p为指向链表 中某个结点的指针。以下程序段为插入一个指针为s的结点，使它成为p结点的直接驱，请 选择其中空格的选项。NODE*q；q=head；while(q->next!=p) ； s->next=p；(3分)while(q->next!=p) ； s->next=p；(3分)A.p=p->next C.s=s->next(2分)B.q=q->nextD.head=head->nextA.p->next=qB.p->next=sC.q->next=sD. q->next=p32.以下为求二叉树深度的算法，完成程序中空格局部。intBTj'oeDcpth (BTrceNode*BT) if (BT=NULL) return 0； else(int depl=BTreeDepth(BT->left) ； /*计算左子树的深度*/ Int dep2=BTreeDepth(BT->right) ； /*计算右子树的深度*/ if() return depl+1； else return dcp2+!； ) ) A.depl>dep2B.depl<dep2C. BT>left=NL-LLD. BT->right=NULL33.设有数据集合：(50, 39, 17, 83, 91, 14, 65)(1)依次取集合中各数据构造一棵二叉排序树是以下图中的()o (3 分)二叉排序树的（）遍历是有序序列。（2分）A.先序B.中序C.后序D.按层34.某带权图的邻接矩阵如下所示:(0615oooo'605oo3coI1505645850oo2oo36co06cooo4260从顶点1出发的广度优先搜索序列为()。A. 1,2, 3, 4,5,6B. 1,4,3, 2, 6,5C. 1,3, 2, 4, 6, 5I). 1,2,4, 3,5,635.以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功 返回该记录的下标，失败时返归卜1,完成程序中的空格选项。typedef struct int key;NODE；Int Binary_Search(NODE a, int n, int k) int low, mid, high;1ow=0;high=n-l;while () mid=() if (amid. kcy=k) return mid;elseif(amid. key<k) low=mid+l, elsehigh = midT, )return-1)(3分)B. amid. key>kD. low<=highB.mid+1I), low+highA. key-kC. afmidL key<k(2分)A. (low+high)/2C. mid-1