1、试卷代号：1252 座位号I国家开放大学2020年秋季学期期末统一考试数据结构（本）试题2021年1月I:1I二I二I总分1三一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.在数据结构中，从逻辑上可以把数据结构分为（）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构2.下面程序段的时间复杂度是（）。for(i=l;i=n;i+)for(j=l;j=n;j+)心j=O;for(k=l;knext=q-next C.p-next=q B.p=q-next D.p-next=q 4.设有一个长度为n的顺序表，要在第i个元素之前（也
2、就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。A.n-i B.ni-1 C.n-i+l D.1 5.一个队列的入队序列是1,2,3,4。则队列的输出序列是（）。A.4,3,2,1 C.1,4,3,2 B.1,2,3,4 D.3,2,4,1 6.在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。A.topnext=p B.p-next=top-next;top-next=p C.Pnext=top;top=p D.p-next=tcip-next;top=topnext 7.判断一个循环队列Q(最多元素为m)为满的条件是()。A.Q-front=Q
3、-rear B.Q-front!=Qrear C.Q-front=(Q-rear+1)%m D.Qfront!=(Q-rear+1)%m 8.设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A.求子串C.模式匹配9.一个非空广义表的表头（）。A.不可能是原子B.连接D.求串长B.只能是子表C.只能是原子D.可以是子表或原子10.树中的结点数等于所有结点的度数加（）。A.1 B.0 C.2 D.一111.在一棵二叉树上，第5层的结点数最多为()。A.8 C.16 B.15 D.32 553 12.在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。A.1/2 C
4、.2 B.1 D.4 13.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为()。A.n C.2n B.e D.2e 14.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A.37/12 B.39/12 C.41/12 D.35/12 15.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）。A.插入排序C.选择排序得分1评卷人B.交换排序D.归并排序二、判断题（根据叙述正确与否在其后面的括号内打对号,J或打叉号X。每小题2分，共30分）16.数据的逻
5、辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（)17.数据结构中，元素之间存在多对多的关系称为图状结构。()18.设有一个单向链表，结点的指针域为next,头指针为head,p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p-next=head。()19.设有一个单向循环链表，结点的指针域为next,头指针为head,指针p指向表中某结点，若逻辑表达式p-next=head;的结果为真，则p所指结点为尾结点。（)20.栈和队列都是特殊的线性表，但它们对存取位置的限制不同。（)21.栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。（)22.递归定义的数据
6、结构通常用递归算法来实现对它的操作。()23.一个空格的串的长度是0。()554 24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。()25.深度为k的完全二叉树至少有2k-l个结点。（)26.完全二叉树中没有度为1的结点。（)27.图的生成树是惟一的。（)28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。（)29.在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的查找方法是折半查找。()30.n个元素进行冒泡法排序，通常需要进行n-1趟冒泡。()得分1评卷人三、综合应用及程序设计题（每小题5分，共25分）31.
7、在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。int write(LinkQueue*q)QueueN ode*p;if(q-front=q-rear)print(队空！无元素可取);exit(0);while(q-front-next!=NULL)p=q-front-next;q-front-next=p-next;print(%4d,pdata);free(p);A.q-front=q-rear C.q-rear=q-front 队空出队释放已出队结点队空时，头尾指针指向头结点B.q=q-next D.p=p-next 555 32.以下程序是先序遍历二叉树的递归算法
8、的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点）。void Preorder(struct BTreeNode*BT)if CBT!=NULL)Preorder(BTleft);Preorder(BTright);A.printf(%c,BT-left)C.printf(%c,BT-data)B.print(%c,BT-right)D.printC%d,BTdata)33.一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？（)A.B C.:_/.:._/.:._/D
9、.34.设关键字序列为：(36,69,46,28,30,74)(1)将此序列用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为（）。（本小题3分）A.30,28,46,36,69,74 C.28,30,46,36,69,74 B.28,30,36,46,69,74 D.30,28,36,46,69,74 556(2)用冒泡法对上述序列排序，经过两趟冒泡的结果序列为（）。（本小题2分）A.36,28,30,46,69,74 C.38,36,30,46,69,74 B.36,46,28,20,69,74 D.28,36,30,46,69,74 35.设数据序列为：53,30,37,12,4
10、5,24,96(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是（）。（本小题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)=key mod 13,则散列地址为1的链中有（）个记录。（本小题2分）02 AC B.1 D.3 557 试卷代号：1252 国家开放大学2020年秋季学期期末统一考试数据结构（本）试题答案及评分标准（供参考）2021年1月一、单
11、项选择题（每小题3分，共45分）1.D 6.C 11.C 2.D 7.C 12.C 二、判断题（每小题2分，共30分）16.,J 21.X 17.22.3.A 8.C 13.D 18.j 23.X 4.C 9.D 14.A 19.24.-/5.B 10.A 15.A 20.,J 25.X 26.X 27.X 28.29.X 30.三、综合应用及程序设计题（每小题5分，共25分）31.C.或q-rear=qfront32.C.或printf(%c,BTdata)33.C.34.(l)D.或30,28,36,46,69,74(本小题3分）(2)A.或36,28,30,46,69,74(本小题2分）35.(l)B.或37,24,12,30,53,45,96(本小题3分）(2)B.或1(本小题2分）558
