1、试卷代号:1252座位号仁口国家开放大学(中央广播电视大学)2017年秋季学期开放本科期末考试数据结构(本)试题2018年1月口二l三l牛气一、单项选择题每小题3分，共30分)1.设有头指针为head的带有头结点的非空单向循环链表，指针p指向其尾结点，要删除头结点，并使其仍为单向循环链表，则可利用下述语句head=head一next;()。A.p=head;B.p=NULL;c.p一next=head;D.head=p;2.以下说法不正确的是()。A.线性表的链式存储结构不必占用连续的存储空间B.一种逻辑结构只能有唯一的存储结构c.一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占
2、用连续的存储空间3.把数据存储到计算机中，并具体体现()称为物理结构。A.数据元素间的逻辑关系B.数据的处理方法c.数据的性质D.数据的运算4.链表所具备的特点之一是()。A.可以随机访问任一结点B.需要占用连续的存储空间c.插入元素的操作不需要移动元素D.删除元素的操作需要移动元素720 5.图状结构中数据元素的位置之间存在()的关系。A.一对一B.多对多C.一对多D.每一个元素都有一个直接前驱和一个直接后继6.元素15，9，11，13按顺序依次进找，则该校的不可能输出序列是(交替进行)。A.13,11,9,15 C.13,11,15,9 B.15,9,11,13 D.9,15,13,11)
3、(进找出钱可以7.设有一个14阶的对称矩阵A(第一个元素为al.l)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素缸.3在一维数组B中的下标是()。A.9 B.10 C.11 D.8 8.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为()。A.18 C.15 B.16 D.17 9.设一棵哈夫曼树共有14个非叶结点，则该树总共有()个结点。A.29 C.30 B.27 D.28 10.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为()。A.abecdf C.aebcfd 图1B.a
4、cfebd D.aedbfc 721 二、填空题(每小题2分，共24分11.队列的特点之一是E元素进、出队的次序是=先进12.结构中，数据元素间存在一对多的关系。13.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是14.在对11个记录的序列02，35，9，7,2,11,56,95,37,58，60)进行直接插入排序时，当把第6个记录11插入到有序表时，为寻找插入位置，元素间需比较次。(由小到大排列)15.晗希函数是记录关键字的值与该记录之间所构造的对应关系。16.20个元素进行冒泡法排序，通常需要进行19趟冒泡，其中第10趟冒泡共需要进行一一一一次元素间的比较。1
5、7.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有个指针域为空。18.中序遍历一棵树可得到一个有序序列。19.二叉排序树插入操作中，新插入的结点总是以树的一一一一结点被插入的。20.广义表的(a,(d,a,b),h,(e,(i,j),k)深度是一一一o21.序列4，2，5.3，8，6，7，9，采用归并排序算法(升序)，经一趟归并后，序列的结果z22.字符串a1=teijing，a2=tef,a3=teifang，a4=tefi最小的是一一一一一。三、综合题(每小题中每问6分，共30分)23.设查找表为(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)。722(2)
6、说明成功查找到元素86需要经过多少次比较?(3)求在等概率条件下，成功查找的平均比较次数?24.(1)一组记录的关键字序列为(26，59，36，18，20，2日，给出利用堆排序(堆顶元素是最小元素的方法建立的初始堆(要求以完全二叉树描述)。(2)对关键字序列(26，59，36，18，20，64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。|得分|评卷人|I I 四、程序填空题(每空2分，共16分25.以下函数在aO到an-1中，用折半查找算法查找关键宇等于k的记录，查找成功返回该记录的下标，失败时返回一1，完成程序中的空格typedef struct int key;NO
7、DE;int Binary_Search(NODE a,int n,int k)int low,mid,high;low=O;high=n-1;while(1)K 一一一一VJ、，E?-LU且(一hda m山return(3)else if(4)723 low=mid+l;else(5)return-1 26.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。724 void lnorder(struct BTreeNode铃BT)if(BT!=NULL)(1)(2)Inorder(BT一一r
8、ight);利用上述程序对图2进行先序遍历，结果是(3)图2o 试卷代号:1252国家开放大学(中央广播电视大学)2017年秋季学期开放本科期末考试数据结构(本)试题答案及评分标准(供参考)一、单项选择题每小题3分，共30分)1.C 6.C 2.B 7.A 二、填空题(每小题2分，共24分)11.先出12.树形13.行下标列下标数组元素14.3 15.存储位置16.10 17.20 18.二叉排序树19.叶20.4 21.2,4,3,5,6,8,7,9 22.a2 3.A 8.D 4.C 9.A 5.B 10.D 2018年1月725 三、综合题(每小题中每问6分，共30分)23.(1)(2)3次18 4 图3(3)平均查找长度=0+2赞2十3铃4+4赞4)/11=324.(1)18,20,25,59,26,36(2)20,18,26,36,59,64 四、程序填空题(每空2分，共16分)25.(1)low=high(2)(low十high)/2(3)mid;(4)amidJ.keydata)(2)Inorder(BT一left)(3)a b d f e c 726 图4
