资源描述
试卷代号: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
展开阅读全文
温馨提示:
金锄头文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
相关搜索