国开大学2015年01月《数据结构（本）》计算机科,软件工程考试真题

试卷代号:1252座位号rn国家开放大学(中央广播电视大学)2014年秋季学期开放本科期末考试数据结构(本)试题2015年1月国E 一、单项选择题(每小题2分，共30分)1.一种逻辑结构在存储时()。A.只要存储数据元素间的关系c.可采用不同的存储结构2.对链表，以下叙述中正确的是(A.不能随机访问任一结点B.结点占用的存储空间是连续的c.插入删除元素的操作一定要移动结点B.只能采用一种存储结构D.只要存储数据元素的值D.可以通过下标对链表进行直接访问3.线性表在存储后，如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用()存储方式是不可行的。A.单链表c.单循环链表4.械和队列的共同特点是()。A.都是先进后出c.只容许在端点处插入和删除元素1028 B.双链表D.顺序表B.元素都可以随机进出D.都是先进先出5.元素2，4，6，8按顺序依次进拢，按该校的可能输出序列依次人队列，该队列的可能输出序列是()(进找出校可以交替进行)。A.8,6,2,4 C.6,2,4,8 B.8,4,2,6 D.8,6,4,2 6.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为()。A.x=rdata;r=rnext;B.r=rnext;x=rdata C.x=fdata;f=fnext;D.f=fnext;x=fdata 7.设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则数组中第38号元素对应于矩阵中的元素是()。(矩阵中的第1个元素是al，l)A.alO,8 B.a7,6 C.a9,2 D.句，58.在C语言中，分别存储S和s，各需要占用()字节。A.一个和两个B.两个c.一个D.两个和一个9.一棵有n个结点，采用链式存储的二叉树中，共有()个指针域被有效使用(即指针域为非空)。A.n+1 C.n-1 B.n D.n-2 10.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为()。A.i/2.0 C.2i+1 B.i/2向下取整D.i十211.设一棵哈夫曼树共有2n十1个结点，则该树有()个非叶结点。A.n c.n一1B.n十lD.2n 12.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有(根为第一层)。A.5 C.3 B.4 D.9)个非叶子结点1029 13.如图1所示的一个圈，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。A.abedfc C.aebcdf 因1B.acfebd D.aebcfd 14.一组记录的关键字序列为(56，30，89，66，48，50，94，87，100)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为()。A.30,50,48,56,66,89,94,100,87 B.50,30,48,56,66,89,94,87,100 C.48,30,50,56,66,89,94,87,100 D.50,30,48,66,56,89,94,87,100 15.线性表以()方式存储，能进行折半查找。A.关键字有序的链接B.顺序C.关键字有序的)19序D.数组二、填空题每小题2分，共24分)16.数据的逻辑结构在计算机中的表示称为结构。17.求两个n阶矩阵的乘积，算法的基本操作为，时间复杂度为18.设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为8，9，10，11，25，某人想要在第8个元素前插入1个元素7(也就是插入元素作为新表的第8个元素)，他的做法是从第8号元素开始，直到第25号元素依次向后移动1个位置，然后把7存放在8号位置，其结果是新表中第25号元素的值为1030 19.在双向链表中，要在p所指结点后插入q所指的结点(设q所指的结点已赋值)，其中所用的一条语句句一next)一prior=q;功能是使P所指结点的指向q。20.设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有pnext=为=NULL，现要删除头结点，并使该单向链表构造成单向循环链表，通过操作head=head-next;21.从一个战顶指针为top的链战中删除一个结点时，用d保存被删结点的值，可执行。(结点的指针域为next，数据域为data)22.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize，采用少用-个元素的模式)，判断循环链队列为满的条件为23.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素，则矩阵A共有个零元素。点。24.一棵有8个权垂值构造的哈夫曼树，共有一一一一一个结点。25.一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有26.如图2所示的二叉树，其先序遍历序列为C|要1227.在查找表中，通过记录的某关键宇能唯一地确定一个记录，该关键宇称为个1度结1031 三、综合题(每小题10分，共30分)28.(1)对给定权值3，1，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层)(2)求树的带权路径长度。(3)链接存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由。29.(1)如下的一棵树，给出先序遍历序列(2)把1，2，3，4，5，6，7，8，9填人，使它成为一棵二叉排序树提示:设图中的树是二叉排序树，找出中序遍历序列与1，2，9的对应关系(3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。|尝1330.设查找表为(5，6，7，8，9，10，11，12，13，14)(1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点(2)给出二叉排序树的定义，针对上述折半查找所对应的判定树的构造过程，说明判定树是否是二叉排序树(设树中没有相同结点)?(3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到?1032|得分|评卷人|I I 四、程序填空题(每空2分，共16分)31.以下函数为直接选择排序算法，对a口，a2J，anJ中的记录进行直接选择排序，完成程序中的空格typedef struct int key;NODE;void selsort(NODE a口，intn)inti,j,k;NODE temp;for(i=1;i=k=i;i+)for(j=i十l;j=;j十+)if(ajJ.keydata;while(q一next!=NULL)q=q一next;q=p;p=p一next;while(p一data!=x)q=p;1034 试卷代号:1252国家开放大学(中央广播电视大学)2014年秋季学期开放本科期末考试数据结构(本)试题答案及评分标准(供参考)一、单项选择题(每小题2分，共30分)1.C 2.A 6.C 7.C l1.A 12.B 二、填空题每题2分，共24分16.物理(存储)17.乘法。(n3)18.8 19.直接前驱的左指针20.p一next=head;3.A 8.D 13.C 21.d=top-data;top=top-next;22.front=(rear+l)%MaxSize 23.34 24.15 25.1 26.215347896 27.主关键宇三、综合应用题(每小题10分，共30分)28.(1)图44.C 9.C 14.B 5.D 10.B 15.C 2015年1月1035(2)WPL=3养4+1提4+4祷3+6祷2+4铃2十5铃2=58(3)共11个结点，22个指针域，除根结点外，每个结点对应一个指针域，共10个指针域非空，故有22-10=12个空指针域，29.(1)A1 A2 A4 A7 A8 A5 A9 A3 A6(2)(3)6 图530.(1)图6 C(2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉树:若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空，则右子树的所有结1036 点的值都大于(若允许结点有相同的值，则大于等于)它的根结点的值;左，右子树也是一棵二叉排序树，按定义判定树是二叉排序树。(3)3次四、程序填空题每空2分，共16分)31.(1)n一1(2)n(3)k=j(4)aiJ=akJ(5)akJ=temp 32.(1)q一next=head;(2)p=p一next;(3)q一next=p-next;1037