国家开放大学2022春（202207）《1252数据结构（本）》期末考试真题及答案-开放本科

试卷代号:1252国家开放大学2022年春季学期期末统一考试数据结构(本)试题答案及评分标准(供参考)2022年7月一、单项选择题(每小题3分,共45分)1.D2.D3.C4.C5.B6.D7.A8.C9.D10.C11.A12.A13.D14.C15.C二、判断题(每小题2分,共30分)16.√17.×18.√19.×20.×21.√22.√23.√24.√25.×26.×27.×28.√29.×30.√三、综合应用及程序设计题(每小题5分,共25分)31.C.或q->rear=q->front;32.C.或printf(“%c”,BT->data)33.C.34.C.j--35.(1)B.或37,24,12,30,53,45,96(本小题3分)(2)B.或1(本小题2分)试卷代号：1252国家开放大学2022年春季学期期末统一考试数据结构（本）试题2022年7月一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）1.线性结构、树形结构、图形结构都是按数据的()来分类的。 A.存储结构 B.物理和存储结构 C.物理结构 D.逻辑结构2.在数据结构中，从逻辑上可以把数据结构分为()。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.内部结构和外部结构 D.线性结构和非线性结构3.设有一个长度为n的顺序表，要删除第i个元素，则需移动元素的个数为()。 A.i B.n-i-l C.n-i D.n-i+l4.设有一个长度为10的顺序表，要在第3个元素之后插入一个元素，则需移动元素的个数为()。 A.3 B.6 C.7 D.85.-个队列的入队序列是10，20，30，40。则队列的输出序列是()。 A.40,30,20,10 B.10,20,30940 C.10,40,30,20 D.30,20,40,106.在一棵二叉树中（其根结点编号为1），若编号为8的结点存在右孩子，则该右孩子的顺序编号为()。 A.18 B.16 C.15 D.177.队列的出队操作在()进行。 A.队头 B.队尾 C.任意位置 D.指定位置8.串函数index(a,b)的功能是进行()。 A.求子串 B.串连接 C.模式匹配 D.求串长9.一个非空广义表的表头元素()。 A.不可能是原子 B.只能是子表 C.只能是原子 D.可以是子表或原子10.链表所具备的特点之一是()。 A.可以随机访问任一结点 B.需要占用连续的存储空间 C.插入元素的操作不需要移动元素 D.删除元素的操作需要移动元素11.树中所有结点数等于所有结点的度加()。 A.1 B.O C.2 D.-112.在一个无向图G中，所有边数之和等于的所有顶点的度数之和()倍。 A.1/2 B.1 C.2 D.413.对于一个具有4个顶点和5条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为()。 A.4 B.5 C.8 D.1014.有一个长度为5的线性表，按顺序查找某关键字，在等概率情况下查找成功的平均比较次数为()。 A.2 B.2.5 C.3 D.3.515.假定一组记录的排序码为(46，79，56，38，40，80)，对其进行归并排序的过程中，第二趟归并后的结果为()。 A.46,79,56,38,40,80 B.46979,38,56,40,80C.38,46,56,79,40,80 D.38,40,46,56,79,80二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）16.数据的逻辑结构与数据元素本身的内容和形式无关。()17.数据结构中，元素之间存在一对多的关系称为图状结构。()18.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。()19.线性表用关键字的顺序方式存储，可以用二分法查找。()20.往栈中插入元素的操作方式是：先写入元素，后移动栈顶指针。()21.栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。()22.递归定义的数据结构通常用递归算法来实现对它的操作。()23.串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是字符。()24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。()25.二叉树只能采用二叉链表来存储。()26.完全二叉树中没有度为1的结点。()27.图的生成树是惟一的。()28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。()29.在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快。()30.对n个元素进行冒泡法排序，最多需要进行n-l趟冒泡。()三、综合应用及程序设计题（每小题5分，共25分）31.在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。Intwrite(LinkQueue*q){QueueNode*p；if(q->front==q->rear)／*队空*／{printf(“队空！无元素可取”)；exit(0)；｝while(q->front->next!=NULL){p=q->front->next；q->front->next=p->next;／*出队*／printf(“%4d”,p->data);free(p)；／*释放已出队结点*／｝_____________/*队空时，头尾指针指向头结点*／｝程序中空格部分的选项为： A.q->front=q->rear; B.q=q->next; C.q->rear=q->front; D.p=p->next;32.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为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) C.printf(“%c”,BT->data) D.printf(“%d，BT->data)330-组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？()34.以下利用直接插入排序算法对存放在a[0]，a[l]，...，a[n-l]中，长度为n的记录序列按关键字key由小到大排序，完成程序中空格部分。Voiddisort(NODEa[],intn){inti，j；NODEtemp；for(i=l；i<n；i++){temp=a[i]；j=i-l；while(j>=0＆＆temp.key<a[j].key){a[j+1]一a[j]；_________________________；｝a[j+l]=temp;｝｝程序中空格部分的选项为： A.j++ B.i++ C.j-- D.i--35.设数据序列为：{53，30，37，12，45，24，96）。(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是()。（本小题3分） A.45