电大本科数据结构14-17年试题.pdf

试卷代号:1252座位号CD 中央广播电视大学2013-2014学年度第一学期“开放本科“期末考试 数据结构本)试题 2014年1月 题号|一|二|三|四|总分| |分数IIIIII |得分|评卷人 11一、单项选择题每小题2分，共30分 1.在数据结构和算法中，与所使用的计算机有关的是()。 A.数据元数间的抽象关系且数据的存储结构 C.算法的时间复杂度D.数据的逻辑结构 2.对顺序表，以下叙述中正确的是 A.用一组地址连续的存储单元依次存放线性表的数据元素 B.各个数据元素的首地址是连续的 C数据元素不能随机访问 D.插入操作不需要移动元素 3.设有一个长度为25的顺序表，要删 除第10个元素(下标从1开始)，需移动元素的个 、数为()。 A.9 C. 15 B.10 D.16 4.设单向链表中，指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为 ()。 A.p一next=p-next一next; c.p=p一next-next; B.p=p一next; D.p一next=p; 1091 5.元素1，3，5 ，7按顺序依次进钱，按该校的可能输出序列依次人队列，该队列的可能输 出序列是().(进找出钱可以交替进行 A.7,5,3.1 C.7,5,1.3 B.7,3,1 ,5 D.5,1.3,7 6.对一个战顶指针为top的链钱进行进校操作，设P为待进榜的结点，则执行()。 A.p=top一next;top=topnext;B.p-next=top; C.p一next=top;top=p;D.top=p; 7.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始).则数组中第33号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是al.l) A.a1.6 C.a9.2 B.alO.S D.as.s 8.设有一个17阶的对称矩阵A.采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中数组下标从1开始).则矩阵中元素alO.6在一维数组B中的下标是()。 矩阵中的第1个元素是al.l) A.45.B.18 C.51D.53 9.串函数StrCmp(“ABCd“，“ABCD勺 的值为()。 A.OB.一1 C.1D.3 10.一棵采用链式存储的二叉树中有n个指针域为空4该二叉树共有()个结点。 A.n十1 C.n-l B.n D.n一2 11.设一棵哈夫曼树共有n个非叶结点，则该树有()个结点。 A.2n C.2n-1 B.2n+2 D.2n+l 12.一棵结点数31next=p一next;(p一next)一prior=q;然后再用语句q一prior=p; 和语句 20.在一个单向链表中，要删除p所指结点的直接后继结点.则可以用操作 (用一条语句 21.向一个钱顶指针为top的链战中插入一个p所指结点时，可执行 操作。(填两条语句，结点的指针域为next) 22.在一个带头结点的链队中，设front和rear分别为 队头和 队尾指针，则删除一个结点 的操作为p=front一next;=p一next;(结点的指针域为 next,p为辅助用指针 23.设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，S的下标从零开始，最 后一个元素的下标为27，则n=(矩阵中的第1个元素是al，l) 24.一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有个叶 结点. 25.一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有个 结点 26.如图2所示的二叉树，其中序遍历序列为 图2 1094 27.二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排z若它的左子树非 空，则左子树的所有结点的值都小于它的根结点的值$若它的右子树非空，Jt右子的所有结点 的值都大于(若允许结点有相同的值，则大于等于它的根结点的值。这种说法是-“的。 回答正确或不正确 |得分|评卷人| III 三、综合题每小题10分，共30分 28.(1)以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵晗夫曼树有2n-1个结点，它是共有多少个权童值构造而成的?简述理由? 29.(1)简述拓扑排序的步骤。 (2)说明有向图的拓扑序列不一定是唯一的原因. (3)如何利用拓扑排序算法判定图是否存在回路。 (4)设有向图G如下，写出首先删除顶点1的3种拓扑序列。 图3 30.设有序表为(21，22 ，23 ，24 ，25 ，26，27 ，28，29 ，30，31，32)，元素的下标从O 开始。 (1)说出有哪几个元素需要经过4次元素间的比较才能成功查到。 (2)画出对上述有序表进行折半查找所对应的判定树(树结点用数值表示 (3)设查找元素为5，需要进行多少次元素间 的比较才能确定不能查到。 (4)求在等概率条件下，成功查找的平均比较次数? 1095 |得分|评卷人! III 四、程序填空题每空2分，共16分 31.以下程序是快速排序的算法 设待序的记录序列存放在astart，aendJ中，按记录的关键宇进行快速排序，先进行 一次划分，再分别进行递归调用 void quicksort ( NODEa,intstart,intend) 5 J , 且 且 n A NODEmid; if(start= end ) return; i=start; j=end; mid=ai; whileOmid.key) ifOdata=x; p-next=NULL; rear= 1097 试卷代号:1252 中央广播电视大学2013-2014学年度第一学期“开放本科“期末考试 数据结构本试题答案及评分标准 (供参考) 2014年1月 一、单项选择题每小题2分，共30分 1.B2.A3.C 6. C7. D8. C l1.D12.A13.A 二、填空题每题2分，共24分 16.逻辑 17.元素间的比较O(n) 18.25 19.p一next=q; 20.p一next=p一next一next; 21.p一next=top;top=p; 22.front一next 23.7 24.5 25.15 26.512389746 27.不正确 三、综合应用题每小题10分，共30分 28.(1) 4.A 9.C 14. B 5.A 10. C 15. A 图4 1098 (2)30000 40001 5001 1001 810 911 (3)n个，因为非叶结点数比叶结点数少一个，而权值个数z叶结点数 29.(1)循环执行以下两步 选择一个度为O的顶点并输出 从网中删除此结点及所有出边 (2)因为选择一个度为O的顶点时不一定是唯一的 (3)由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱 (4)152364152634156234 30.(1)5 (2) 罔5 (3)3 (4)ASL=(l+2铸2+3铃4+5铸的112=37/12 四、程序填空题每空2分，共16分 31.(1)i十+; (2)i十 十p (3)aCi=ai; (4)j一-; (5)(a,i+1,end) ; 32.(l)malloc(sizeof(structnode (2)rear一next=p (3)p 1099 试卷代号:125 2座位号CD 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期末考试 数据结构(本)试题 2014年7月 |题号|一|二|三|四|总分| |分数IIIIII |得分|评卷人 11-、单项选择题每小题2分，共30分) 1.结构中的元素之间存在一对多的关系是()。 A.集合B.线性结构 C树形结构D.图状结构 2.对不带头结点的单向链表，判断是否为空的条件是()(设头指针为head)。 A. head= =NULL C.head一next=head B.head一next=NULL D. head =NULL 3.在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删 除第一个结点，可用的语句是()。 A.p=q一next;p=p-next; c.p一next=q- next;q=p; B.p一next=q;p=p一next; D.p=p一next;q-next=p; 4.一个校的进技序列是1，2 ，3 ，4，5，则钱的不可能输出序列是()(进找出战可以交替 进行)。 A.12345 C.45321 B.43512 D.54321 5.-个队列的人队序列是2，4， 6，8，按该队列的输出序列使各元素依次入钱，该枝的可能 输出序列是()。 A.8,6 ,4 ,2 C.8,4 ,2 ,6 B.6,2 ,4 ,8 D.8,2 ,4 ,6 1033 6.在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点p，要为结点p赋 值x，并入队的运算为()。 A.p一data=x;p一next=NULL;f-next=p;f=p; B.p一data=x;p一next=NULL;r一next=p;r=p; C.p一data=x;p一next=r;r=s; D.p一data=x;p一next=f;f=s; 7.设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始)，则矩阵中元素.a7.6在一维数组B中的下标是()。 (矩阵中的第1个元素是旬.1) A.34B.14 C.260.27 8.以下程序段的结果是c的值为()。 chara5= “1236789“,int铃p=a，intc=O; while(祷p+)c十 +; A.8_B.7 C.100.12 9.一棵有23个结点，采用链式存储的二叉树中，共有()个指针域为空。 A.24B.25 C.23D.45 10.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号 为()。 A.i/2B.2i-1 C.2i+1D.i/2-1 11.设一棵哈夫曼树共有2n十1个叶结点，则该树有()个叶结点。 A. n一l C.n+l B.n 0.2n 12.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为()。 图1 1034 A. abecdf C. aebcfd B.aefebd D. aedbfc 13.已知如图2所示的一个图，若从顶点B出发，按广度优先法进行遍历，则 可能得到 的 一种顶点序列为()。 0-毛 图2 A.BADEHCFG B.ADEHCGF e.BADECHFG D.BADEHCFG 14.一组记录的关键宇序列为(46，38 ，56 ，40，79，84)，利用快速排序，以第一个关键字为 分割元素，经过一次划分后结果为()。 A.40,38 ,46,79 ,56 ,84 B.40，38，46，5679，84 C.40,38 ,46,84 ,56 ,79 D.38,40 ,46 ,56 ,79 ,84 15.在有序表21，23 ，28 ，33 ，43，屿，46，73，77，78，的，99，106中，用折半查找值43时，经 ()次比较后查找成功。 A.6 e.8 |得分|评卷人| III B.3 D.4 二、填空题(每小题2分，共24分) 16.本书中介绍的树形结构和属非线性结构。 17.设有一个长度为18的顺序表，要在第4个元素之前插入2个元素(也就是插入元素 作为新表的第5个和第4个元素).则最少要移动元素的个数为 1035 18.在双向链 表中，要删除p所 指的结点，可以先用语句句一prior)一next= p一next;然再用语句 19.在一个单向链表中p所指结点之后插人一个s所指向的结点时，应执行s一next= p-next;和的操作。 20.一个钱和一个队列的输入序列都为abcdefg，它们可能有相同 的输出序列 吗? 。(若没有则回答没有，若有则写出序列，进找出钱可以交替进行) 21.从一个钱顶指针为top的链战中取钱顶元素，用d保存楼顶元素的值，可执行 。(结点的数据域为data) 22.循环链队列中，设front和rear分别 为 队头和 队尾指针，(最多元素为MaxSize，)，判 断循环链队列为空的条件是为真。 23.对稀疏矩阵进行压缩存储，可采用三元组表，设a是稀疏矩阵A相应的三元组表类型 (结构体类型)变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若 a.dataO.i=2;a.data0.j=3;a.dataOJ.v=16;它提供的A数组的相关信息有 24.设有一棵深度 为5的完全二叉树，该树共有20个结点，第 五层上有 点。(根所在结点为第1层) 25.中序遍历树可得到个有序序列。 26.如图1所示的二叉树，其后序遍历序列为 图1 27.给定-组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是 的。(回答正确或不正确) 1036 个叶结 |得分|评卷人| III 三、综合题(每小题10分，共30分) 28.(1)说明什么是顶点活动网(AOV网)和拓扑序列 (2)设有向图G如下，写出3种拓扑序列， (3)在图G中增加一条边，使图G仅有一条拓扑序列 图3 29.如下是一棵二叉排序树，AI，A2，A9代表1，2，3，9中各个不同数字， (1)给出对该树中序遍历的结果 (2)A3，A5 ，A7的值各为多少? (3)请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树 A7 图4 30.(1)设有查找表17，26，14，16，15，30，18，19，28，依次取表中数据构造一棵二叉排序树。 (2)对上述二叉树给出后序遍历的结果 (3)对上述二叉树给出中后序遍历的结果 (4)在上述二叉树中查找元素15共要进行多少次元素的比较? 1037 |得分|评卷人| III 四、程序填空题每空2分，共16分) 31.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针p(查找成功p指向查到的树结点，不成功p指向为NULL)完成 程序中的空格 typedefstructBnode intkey; structBnode蒋left; structBnode祷right; Bnode; Bnode头BSearch(Bnode祷bt，intk) /提bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字诀 / Bnode秘p; if(bt= return(bt); p=bt; while(p一key! if(kkey) else 1038 if(p=NULL)break; return(); 32.设有一个头指针为head的不带头结点单向链表，p 、q是指向链表中结点类型的指针 变量，p指向链表中结点a，(设链表中没有结点的数据域与结点a的数据域相同)，写出相关 语句 (1)使该单向链表成为单向循环链表 (2)插入结点S，使它成为a结点的直接前驱 q=p;x=p-data; while ( q一next=head; q=p;p=p-next; while(p一data!=x) q=p; s一next=p; )q=q一next; 1039 试卷代号:1252 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期末考试 数据结构(本)试题答案及评分标准 (供参考) 2014年7月 -、单项选择题(每小题2分，共30分 1.C2.A3.D 6. B7. D8. B 11.C12.D13.C 4. B 9. A 14.B 5. A 10.A 15.B 二、填空题(每题2分，共2 4分 16.图状结构 17.15 18.(p一next)一prior=p一prior; 19.p-next=s; 20.abcdefg 21.d=top-data; 22.front=rear 23.A的第一个非零元素的下标为2，3，元素为16 24.5 25.二叉排序 26.519876432 27.不正确 三、综合应用题每小题10分，共30分) 28.(1)用顶点表示活动，边表示活动间先后关系的有向图称为顶点活动网 在顶点活动网中，若不存在回路，则所有活动可排列成个线性序列，使每个活动的所有 前驱活动都排在该活动的前面，称此序列为拓扑序列 (2)abdc adbcdabc (3)在b和d间添加有向边 29.(1)A7 A4 A8 A2 AS A9 Al A3 A6 123456789 1040 (2)8 5 1 (3) 图5 30.(1)见图6 (2)15,16,14,19,18,28,30,26,17 (3)14,15,16,17,18,19,26,28,30 (4) 4 图6 四、程序填空题每空2分，共16分 31.(1)NULL (2)k (3)p=p一left (4)p=p一right (5)p 32.(1)q一next!=NULL (2)p=p一next; (3)q一next=s; 1041 试卷代号:1252座位号E口 国家开放大学(中央广播电视大学)2014年秋季学期“开放本科“期末考试 数据结构(本)试题 2015年1月 E 三 一、单项选择题(每小题2分，共30分) 1.一种逻辑结构在存储时()。 A.只要存储数据元素间的关系 c.可采用不同的存储结构 2.对链表，以下叙述中正确的是( A.不能随机访问任一结点 B.结点占用的存储空间是连续的 c.插入删除元素的操作一定要移动结点 B.只能采用一种存储结构 D.只要存储数据元素的值 D.可以通过下标对链表进行直接访问 3.线性表在存储后，如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结 点，则采用()存储方式是不可行的。 A.单链表B.双链表 c.单循环链表D.顺序表 4.校和队列的共同特点是()。 A.都是先进后出B.元素都可以随机进出 D.都是先进先出c.只容许在端点处插入和删除元素 1028 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;=fnext; D. f=fnext; x=fdata 7.设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始)，则数组中第38号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是旬，1) A. alO,g B. a7,6 C. a9,2 D. ag,5 8.在C语言中，分别存储“S“和s，各需要占用()字节。 A.一个和两个B.两个 c.一个D.两个和一个 9.一棵有n个结点，采用链式存储的二叉树中，共有)个指针域被有效使用(即指针 域为非空)。 A. n+1 C. n-1 B.n D.口一2 10.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为)。 A. i/2. 0 C. 2i十1 B. i/2向下取整 D.i十2 11.设一棵哈夫曼树共有2n十1个结点，则该树有()个非叶结点。 A.n c.n一1 B. n十1 D.2n 12.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有( (根为第一层)。 A.5 C.3 B.4 D.9 )个非叶子结点 1029 13.如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的 一种顶点序列为()。 A. abedfc c. aebcdf i到1 B. 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.关键字有序的顺序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所指结点的 指向q0 20.设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p next=为=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，则该树共有个1度结 占。 26.如图2所示的二叉树，其先序遍历序列为 l剖2 27.在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键宇称为 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作为叶结点，并使它仍然是一棵二叉排序树。 民13 30.设查找表为(5，6，7，8，9，10，11，12，13，14) (1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2)给出二叉排序树的定义，针对七述折半查找所对应的判定树的构造过程，说明判定树 是否是二叉排序树(设树中没有相同结点)? (3)为了查找元素5.5，经过多少次元素间的比