国开电大2023年春季期末考试《数据结构》试题(试卷代号1252)

国家开放大学2023年春季学期开放专科期末考试第第页国家开放大学2023年春季学期期末统一考试数据结构(本)试题一、单项选择题(把合适的选项编号填写在括号内。每小题3分,共45分)1.线性结构、树形结构、图形结构都是按数据的()来分类的。A.存储结构B.物理和存储结构C.物理结构D.逻辑结构2.在数据结构中,从逻辑上可以把数据结构分为().A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构3.设有一个长度为n的顺序表,要删除第i个元素,则需移动元素的个数为()。A.iB.n-i-1C.n-iD.n-i+14.设有一个长度为10的顺序表,要在第3个元素之后插入一个元素,则需移动元素的个数为().A.3B.6C.7D.85.一个队列的人队序列是10,20,30,40。则队列的输出序列是().A.40,30,20,10B.10,20,30,40C.10.40,30,20D.30,20,40,106.在一棵二叉树中(其根结点编号为1),若编号为8的结点存在右孩子,则该右孩子的顺序编号为()。A.18B.16C.15D.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.1B.0C.2D.-1在一个无向图G中,所有边数之和等于的所有顶点的度数之和()倍。A.1/2B.1C.2D.413.对于一个具有4个顶点和5条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为()。A.4B.5C.8D.1014.有一个长度为5的线性表,按顺序查找某关键字,在等概率情况下查找成功的平均比较次数为()。A.2B.2.5C.3D.3.515.假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果为()。A.46,79,56,38,40,80B.46,79,38,56,40,80C.38,46,56,79,40,80D.38,40,46,56,79,80得分|评卷人二.判断题(根据叙述正确与香在其后面的括号内打对号“V"或打叉号"X"。每小题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-1趟冒泡。()三、综合应用及程序设计题(每小题5分,共25分)31.在下面空格处填写一条语句,以使下面的链式队列全部元素出队的算法完整。intwrite(LinkQueue*q){QueueNode*p;.if(q->front==q->rear)/*队空*/{printf(“队空!无元素可取");exit(0);.{while(q->front->enxt!=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.print("%c",BT->right)C.printf("%c",BT->-data)D.printf("%d",BT->data)33.一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序(堆顶元素是最小元素)的方法建立初始堆是如下哪个图?()34.以下利用直接插人排序算法对存放在a[0],a[1],●●●,a[n-1]中,长度为n的记录序列按关键字key由小到大排序,完成程序中空格部分。voiddisort(NODEa[].intn){inti,j;NODEtemp;for(i=1;i<nji++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[i].key){a[j+1]=a[j];____________________;}a[j+1]=temp;}}程序中空格部分的选项为:A.j++B.i++C.j--D.i--35.设数据序列为:{53,30,37,12,45,24,96}.(1)从空二叉树开始逐个插人该数据序列来形成二叉排序树,若希望高度最小，应该选择:的序列是()。(本小题3分)A.45,24,53,12,37,96,30B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53(2)用链接地址法将该数据序列构造哈希表,哈希函数为H(key)=keymod13,则散列地址为1的链中有()个记录。(本小题2分)A.0B.1C.2D.3

国家开放大学2023年春季学期期末统一考试数据结构(本)试题答案及评分标准(供参考)一、单项选择题(每小题3分,共45分)1.D2.D3.C4.C5.B6.D7.A8.C9.D10.C11.A12.A13.D.14.C15.C二、判断题(每小题2分,共30分)16.V17.X18.V19.X.20.x21.V22.V23