1、评卷人得 分一 、单项选择题(每小题2分，共30分)试卷代号：1252 座位号C 国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试数据结构(本) 试 题2016年7月题 号二三四总 分分 数1. 对稀疏矩阵进行压缩存储，可采用三元组表， 一个10行8列的稀疏矩阵A 共有73个零元素，其相应的三元组表共有( )个元素。A.8 B.80C.7 D.102. 字符串( )是“abcd321ABCD” 的子串。A.“21AB” B.abcDC.“aBCD” D.“321a”3.栈和队列的共同特点是( )。A. 都是操作受限的线性结构B. 元素都可以随机进出C. 都是先进后出D.
2、都是先进先出4.在一个链队中，假设f和 r 分别为队头和队尾指针，p 指向一个新结点，要为结点p 所指结点赋值 x, 并入队的运算为p-data=x;p-next=NULL;( )。A.f-next=p;f=p; B.r-next=p;r=p;C.r=p;p-next=r; D.p-next=f;f=p;5.数据结构中，与所使用的计算机无关的是数据的( )结构。A. 逻辑 B. 存储C. 逻辑与存储 D. 物理8426.顺序表所具备的特点之一是( )。A. 可以随机访问任一结点B. 不需要占用连续的存储空间C. 插入元素的操作不需要移动元素D. 删除元素的操作不需要移动元素7.数据元素是数据的
3、基本单位，它( )。A. 只能有一个数据项组成B. 至少有二个数据项组成C. 可以是一个数据项也可以由若干个数据项组成D. 至少有一个数据项为指针类型8.设有头指针为head 的非空的单向链表，指针 p 指向其尾结点，要使该单向链表成为单向循环链表，则可利用下述语句( )。A.p=head; B.p=NULL;C.p-next=head; D.head=p;9.在线性表的顺序结构中，以下说法正确的是( )。 A. 逻辑上相邻的元素在物理位置上不一定相邻 B. 数据元素是不能随机访问的C. 逻辑上相邻的元素在物理位置上也相邻D. 进行数据元素的插入、删除效率较高10.对链表，以下叙述中正确的是(
4、 )。A. 不能随机访问任一结点B. 结点占用的存储空间是连续的C. 插入删除元素的操作一定要要移动结点D. 可以通过下标对链表进行直接访问11.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作 为新表的第5个元素),则移动元素个数为( )。A.30 B.31C.5 D.612.设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为( )。A.11 B.10C.30 D.31843得 分二、填空题(每小题2分，共24分)13.设有一个25阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中(数组下标从1开始)
5、,则矩阵中元素ays在一维数组B 中的下标是( )。A.25 B.24C.26 D.2714.线性表在存储后，如果相关操作中有要求：利用已知的指向某结点的指针或序号，访问该结点的前驱结点，则采用( )的存储方式是不可行的。A. 单向链表B. 双向链表C. 单向循环链表D. 顺序表15.在一棵二叉树中，若编号为i的结点存在左孩子，i结点的左孩子的顺序编号为( )。A.i/2.0 B.2*iC.2*i+1 D.i+2评卷人结构。16.广义表(b,a,c),c,d,f,e,(i,j),k)的长度是17.数据结构中，数据元素之间的抽象关系称为18.栈的操作特点是后进19.广义表(b,a,c),c,d,
6、f,e,(i,j),k)的表头是 20.设有一个长度为18的顺序表，第8号元素到第18号元素依次存放的值为8,9,18.某人想要删除第8号元素，程序中他的做法是用语句 for(i=18;idata=x;846试卷代号：1252国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试数 据 结 构 ( 本 ) 试 题 答 案 及 评 分 标 准( 供 参 考 )2016年7月一、单项选择题(每小题2分，共30分)1.C 2.A 3.A 4.B 5.A6.A 7.C 8.C 9.C 10.A11.B 12.C 13.C 14.A 15.B二、填空题(每题2分，共24分)16.617.
7、逻辑18.先出19.(b,a,c)20.1821.522.623.二叉排序树24.10,12,11,13,14,1625.1526.1527.3847三、综合应用题(每小题10分，共30分)28. (1)图3图3(2)4次(3)(1+2*2+3*4+4#4)/11=33/11=3 29.(1)acdbfeh(2)152364或152634或156234 30. (1)图4图4(2)4(3)3,4,5,6,7,8,9848四、程序填空题(每空2分，共16分)31.(1)low=high(2)mid(3)amid.keyk(4)high=mid- 1(5)return32.(1)sizeof(struct node)(2)pnext=top(3)top=p849
