1、试卷代号：1252 座位号亡亡国家开放大学2019年秋季学期期末统一考试数据结构（本）试题2020年1月三巨三一、单项选择题（每小题3分，共30分）1.以下说法不正确的是（）。A.线性表的链式存储结构不必占用连续的存储空间B.一种逻辑结构只能有唯一的存储结构C.一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占用连续的存储空间2.单向链表所具备的特点之一是（）。A.可以随机访问表中任一结点B.需要占用连续的存储空间C.插入元素和删除元素的操作不需要移动元素D.可以通过指向某元素的指针操作，直接访问到该结点的直接前驱结点3.线性结构中数据元素的位置之间存在（）的关系。A.多对多B.一
2、对多C.一对一D.每一个元素都有一个直接前驱和一个直接后继549 4.在一个单向链表中，p和q分别是指向结点类型的指针，要删除p所指结点的直接后继结点，可执行（）。A.q=pnext;p-next=q-next B.q=p;p=q-next C.q=pnext;p-next=q D.q=p;p-next=q 5.设有带头结点的且头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为不带头结点的单向循环链表，则可利用下述语句：head=head-next;和（）。A.p=head C.p-next=head B.p=NULL D.head=p 6.元素20,14,160,180
3、按顺序依次进栈，则该栈的不可能输出序列是（栈可以交替进行）。A.180,160,14,20 C.180,160,20,14 B.20,14,160,180 D.14,20,180,160）。（进栈出7.设有一个15阶的对称矩阵A(第一个元素为a口I)采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a釭3在一维数组B中的下标是（）。A.11 B.13 C.14 D.12 8.设一棵有n个叶结点的二叉树，度数为1的结点有4个，则该树共有（）个结点。A.2n C.2n+2 B.2n+3 D.2n+4 9.设根结点所在层为第一层，一棵具有5层的完全二叉
4、树，最后一层有6个结点，则该树总共有（）个结点。550 A.22 C.21 B.20 D.19 10.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.abecdfg C.aebcfdg 图1B.acfebdg D.aedfcbg 尸尸二、填空题（每小题2分，共21分）11.把数据存储到计算机中，并具体体现数据元素间的逻辑关系称为结构。12.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为13.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为14.设一棵哈夫曼树共有18个非叶结点，则该树总共有个结点。15.栈元素
5、的进、出栈次序是：后进16.在对10个记录的序列(8,36,19,78,4,10,53,45,27,68)进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元索间需比较次。17.n个元素进行冒泡法排序，通常需要进行n-1趟冒泡，其中第j趟冒泡共需要进行次元素间的比较。18.序列7,1,4,2,5,3,8,6用归并法排序（升序），经一次归并后的结果序列是19.中序遍历一棵树可得到一个有序序列。20.广义表Ch,(b,a),f,e,(Ci,j),k)的深度是。21.结构中，数据元素间存在一对多的关系。22.字符串al=beijing,a2=bef,a3=beifang,a4=b
6、efi最小的是。551 得分1评卷人三、综合题（每小题中每问6分，共30分）23.设查找表为飞：I,I 12.I 231 I 2:1,53 1,1 I;,18:I:I:I,1:3(1)画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。(2)说明不成功查找元素45需要经过多少次比较？(3)求在等概率条件下，成功查找的平均比较次数？24.(1)一组记录的关键字序列为(37,67,43,25,27,32),给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。(2)对关键字序列(40,73,49,31,33,77)采用快速排序，给出以第一个关键字为分割元素，
7、经过一次划分后的结果。1得分！评卷人四、程序填空题（每空2分，共16分）25.以下函数在aO到an-1中，用折半查找算法查找关键字等于K的记录，查找成功返回该记录的下标，失败时返回1,完成程序中的空格。typedef struct int key;NODE;int Binary_Search(NODEaJ,int n,int k)552 int low,mid,high;low=O;(1)while Clow=high)mid=(Z)if(amid.key=k)return(3)else if(amid.keyright);利用上述程序对下图进行遍历，结果是(3)厂图2553 试卷代号：125
8、2 国家开放大学2019年秋季学期期末统一考试数据结构（本）试题答案及评分标准（供参考）2020年1月一、单项选择题（每小题3分，共30分）1.B 2.C 6.C 7.B 二、填空题（每小题2分，共24分）11.存储（物理）12.14 13.2i+l 14.37 15.先出16.4 17.nj 18.1,7,2,4,3,5,6,8 19.二叉排序树20.3 21.树形22.a2 3.C 8.B 三、综合题（每小题中每问6分，共30分）23.(1)11(2)4次4.A 9.C(3)平均查找长度=0+2*2+3*4+4*4)/11=3 554 5.C 10.D 24.(1)25,27,32,67,37,43(2)33,31,40,49,73,77 四、程序填空题（每空2分，共16分）25.O)high=n-1(2)low+high)/2(3)mid(4)high=mid-1(5)return-1 26.(l)printf(%c,BT-data)(2)PreorderCBTleft)(3)a b d f g e c 555
