1、试卷代号：1252 座位号rn国家开放大学（中央广播电视大学）2018年春季学期“开放本科”期未考试数据结构（本）试题2018年7月巨一四厂勹得分1评卷人一、单项选择题（每小题3分，共30分）1.数据的存储结构包括数据元素的表示和()。A.数据处理的方法B.相关算法C.数据元素的类型D.数据元素间的关系的表示2.在一个头指针为head的单向链表中，p指向尾结点，要使该链表成为单向循环链表可执行（）。A.p=head-next;C.head-next=p-next;B.head-next=p;D.p-next=head;3.元素111,113,115,117按顺序依次进栈，则该栈的不可能输出序列
2、是（）（进栈出栈可以交替进行）。A.117,115,113,111 C.117,115,111,113 4.以下说法正确的是()。A.栈的特点是先进后出C.队列的特点是先进后出B.111.113,115,117 D.113,111,117,115 B.栈的特点是先进先出D.栈和队列的特点都是先进后出5.设有一个20阶的对称矩阵A(第一个元素为a,1),采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是()。A.24 B.17 C.16 D.23 703 6.设一棵有2n+l个结点的二叉树，除叶结点外每个结点度数都为2
3、,则该树共有（)个叶结点。A.n C.n+z B.n+l D.n1 7.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.abecdf C.aebcfd 图1B.aecbdf D.aedfcb 8.线性表以（）方式存储，能进行折半查找。A.关键字有序的顺序B.顺序C.链接D.二叉树9.一棵具有38个结点的完全二叉树，最后一层有（）个结点。A.7 B.5 C.6 D.8 10.对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行704 A.e=top-next;top-data=e;B.top=top-next;e=top
4、-data;C.e=top-data;top=top-next;D.top=top-next;e=data;三二、填空题（每小题2分，共24分）11.数组a经初始化chara J=English;a7中存放的是12.设有串pl=ABADF,P2=ABAFD,P3=ABADF AP4=ABAF,四个串中最大的是13.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为14.设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为15.结构中的数据元素存在多对多的关系称为结构。16.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有（根所在结点为第1层）
5、17.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2,则该树共有个叶结点。个结点。18.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较次。（由小到大排序）19.n个元素进行冒泡法排序，第j趟冒泡要进行次元素间的比较。20.一棵有n个叶结点的哈夫曼树，则该树共有个结点。21.中序遍历可得到一个有序序列。22.广义表CCa,b),d,e,(Ci,j),k)的长度是。705 得分1评卷人三、综合题（每小题中每问6分，共30分）23.(1)设有数据集合40,29,7,73,101,4,55,2,81
6、,92,39,依次取集合中各数据构造一棵二叉排序树。(2)一组记录的关键字序列为(5,8,6,3,4,7),利用堆排序（堆顶元素是最小元素）的方法建立初始堆。（要求用完全二叉树表示）21.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树。(2)给出上述哈夫曼树叶结点的哈夫曼编码。(3)一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。（从小到大排序）I I 得分1评卷人四、程序填空题（每空2分，共16分）25.设线性表为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中
7、的数据。706#define NULL 0 void main()NODE a,b,c,d,*head,关 p;a.data=6;b.data=lO;c.data=l6;d.data=4.;/*d是尾结点head=(1)a.next=&b;b.next=&c;c.next=&d;(2)/以上结束建表过程*p=head;/*p为工作指针，准备输出链表do printf(%dn,(3)(4)while(5););26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点）。void Inorder(st
8、ruct BTreeNode*BT)if CBT!=NULL)(1)(2)Inorder(BT-right);利用上述程序对右图进行遍历，结果是(3)图2707 试卷代号：1252 国家开放大学（中央广播电视大学）2018年春季学期“开放本科”期末考试数据结构（本）试题答案及评分标准（供参考）2018年7月一、单项选择题（每小题3分，共30分）1.D 6.B 2.D 7.B 二、填空题（每小题2分，共24分）11.字符串的结束符14.13 17.n+l 3.C 8.A 12.p2 15.图状18.3 20.2n-l 21.二叉排序树三、综合题（每小题中每问6分，共30分）23.(1)708 图34.A 9.A 5.B 10.C 13.2i+l 16.12 19.n-j 22.4(2)3,4,6,8,5,7 24.(1)(2)2:0000 3 0001 4 001 7 10 8 11 9 01(3)31,29,37,47,70,85 图4图5709 四、程序填空题（每空2分，共16分）710 25.(1)&.a(2)d-next=NULL(3)p-data(4)p=p-next(5)p!=NULL 26.(l)InorderCBT-left)(2)printf(%c,BT-data)(3)bedafc
