试卷代号：1252 座位号■ 国家开放大学（中央广播电视大学）2014年春季学期“开放本科”期末考试 数据结构（本） 试题 2014年7月 题 女 二 三 四 总 分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.结构中的元素之间存在一对多的关系是( A.集合 B.线性结构 C.树形结构 D.图状结构 2.对不带头结点的单向链表，判断是否为空的条件是( )(设头指针为head)。 A.head==NULL B.head->next==NULL C.head->next==head D.head =NULL 3.在一个不带头结点的单循环链表中，P、q分别指向表中第一个结点和尾结点，现要删 除第一个结点，可用的语句是()。 A.p=q->next;p=p->next; B.p->next=q p=p->next; C.p->next=q->nextiq=p; D.p=p->next;q->next=p; 4.一个栈的进栈序列是1,2,3,4,5，则栈的不可能输出序列是()（进栈出栈可以交替 进行)。 A.12345 B.43512 C.45321 D.54321 5.一个队列的入队序列是2,4,6,8，按该队列的输出序列使各元素依次入栈，该栈的可能 输出序列是（)。 A.8,6,4,2 B.6,2,4,8 C.8,4,2,6 D.8,2,4,6 1033
试卷代号 2 5 2 座位号CD 国家开放大学(中央广播电视大学 4年春季学期"开放本科"期末考试 数据结构(本)试题 2014 年7 |题号|一|二|三|四|总分| |分数 I I I I I |得分|评卷人 11- 选择 1.结构中的元素之间存在一对多的关系是( )。 A. 合B. 性结 树形结构D. 状结 2. 为空 ) (设头指针为 A. head= = NULL C. head 一>next= =head B. head 一>next= =NULL D. head = NULL 3. 在一 链 表 第 一个结 现要 除第一个结点，可用的语句是( )。 A.p=q一>next; p=p->next; c. 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开始），则矩阵中元素.，.6在一维数组B中的下标是()。 (矩阵中的第1个元素是a1.1) A.34 B.14 C.26 D.27 8.以下程序段的结果是c的值为()。 char a[5]=“1236789”,intp=a,intc=0; while(*p+)c++; A.8 B.7 C.10 D.12 9.一棵有23个结点，采用链式存储的二叉树中，共有( )个指针域为空。 A.24 B.25 C.23 D.45 10.在一棵二叉树中，若编号为1的结点是其双亲结点的左孩子，则双亲结点的顺序编号 为( ）。 A.i/2 B.2i-1 C.2i+1 D.i/2-1 11.设一棵哈夫曼树共有2n十1个叶结点，则该树有( )个叶结点。 A.n-1 B.n C.n+1 D.2n 12.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为()。 图1 A.abecdf B.acfebd C.aebcfd D.aedbfc 1034
6. 个链 假设 队头 个结 结点 x，并入队的运算为( )。 A.p 一>data=x; 一>next=NULL; f->next=p; f=p; B. 一>data=x; 一>next=NULL ;r 一>next=p;r=p; C. 一>data=x; 一>next= r; r= s; D.p一>data=x; 一>next=f;f=s; 7. 设有 个25 阵A 方式 下三 行序为主 到一维数组B中(数组下标从1开始) ，则矩阵中元素.a7.6 一维 )。 (矩阵中的第 1个元素是旬 ) A. 34 B.14 C. 26 0. 27 8. )。 char a[5] = "1236789" , int 铃p=a int c=O; while( 祷p++)c十 + A.8_ B.7 C.10 0. 12 9. 存储 )个指针域为空。 A.24 B.25 C. 23 D.45 10. 在一 左孩 则 双 为( )。 A.i/2 B.2i-1 C. 2i+1 D. i/2 -1 1. 树共 十1 )个叶结点。 A. n C. n+l B.n 0. 2n 12. 知如 图1 所示 点a 按深 优先 遍历 到的一种顶点序列为( )。 1034 A. abecdf C. aebcfd B. aefebd D. aedbfc
13.已知如图2所示的一个图，若从顶点B出发，按广度优先法进行遍历，则可能得到的 一种顶点序列为()。 图2 A.BADEHCFG B.ADEHCGF C.BADECHFG D.BADEHCFG 14.一组记录的关键字序列为(46,38,56,40,79,84)，利用快速排序，以第一个关键字为 分割元素，经过一次划分后结果为()。 A.40,38,46,79,56,84 B.40,38,46,56,79,84 C.40,38,46,84,56,79 D.38,40,46,56,79,84 15.在有序表{21,23,28,33,43,45,46,73,77,78,89,99,106}中，用折半查找值43时，经 ()次比较后查找成功。 A.6 B.3 C.8 D.4 得 分 评卷人 二、填空题（每小题2分，共24分） 16.本书中介绍的树形结构和 属非线性结构。 17.设有一个长度为18的顺序表，要在第4个元素之前插人2个元素（也就是插入元素 作为新表的第5个和第4个元素)，则最少要移动元素的个数为 1035
13. 图2 所示 若从 点B 优先 进行遍历 则 可 到 的 一种顶点序列为( )。 0--毛〉 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 ，56~79 ，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 |得分|评卷人| I I I B.3 D.4 二、填空题(每小题 16. 树形结构 非线性结构 17. 设有一个 为18 序 表 第4 入2 个元 就是 入 元 作为新表的第 5个和第 4个元素) .则最少要移动元素的个数为 1035
l8.在双向链表中，要酬除p所指的结点，可以先用语句(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.data[0].i=2;a.data[0].j=3;a.data[0].v=l6;它提供的A数组的相关信息有 24.设有一棵深度为5的完全二叉树，该树共有20个结点，第五层上有 个叶结 点。（根所在结点为第1层） 25.中序遍历 树可得到一个有序序列。 26.如图1所示的二叉树，其后序遍历序列为 图1 27.给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是 的。（回答正确或不正确） 1036
18. 链 表 除p 所 指 prior) 一>next = 一>next; 19. 个单 链表 中p 指结 插人 个s 所指 点 时 行s一>next= p->next; 操作 20. 个钱 输入序列 为abcdefg 们可 同 的 列 吗 。(若没有则回答没有，若有则写出序列，进找出钱可以交替进行) 1. 钱顶 为top 顶元 用d 保存 顶元 。(结点的数据域为 22. 环链 队列 设front 和rear 别 为 队头 和 队尾指 (最多元素为 e，) ，判 断循环链队列为空的条件是为真。 23. 对稀疏矩 进行压缩存储 可采用 是稀疏矩 相应 表类 (结构体类型)变量， a中的一个成员项是三元组类型的结构体数组 a，按书中定义，若 a. data[O]. i=2;a. data[0].j=3;a. data [OJ. v=16; 数组 息有 24. 度 为 树共有20 第 五 点。(根所在结点为第 1层) 25. 遍历 序序 26. 图1 后序 历序 27 .给定-组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是 的。(回答正确或不正确) 1036 个叶结
得分 评卷人 三、综合题（每小题10分，共30分） 28.(1)说明什么是顶点活动网(AOV网)和拓扑序列 (2)设有向图G如下，写出3种拓扑序列， (3)在图G中增加一条边，使图G仅有一条拓扑序列 图3 29.如下是一棵二叉排序树，A1,A2,…A9代表1,2,3，…9中各个不同数字， (1)给出对该树中序遍历的结果 (2)A3,A5,A7的值各为多少？ (3)请在该树中再插人一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树 A2 A3 y A7 A8 A9 图4 30.(1)设有查找表{17,26,14,16,15,30,18,19,28}，依次取表中数据构造一棵二叉排序树。 (2)对上述二叉树给出后序遍历的结果 (3)对上述二叉树给出中后序遍历的结果 (4)在上述二叉树中查找元素15共要进行多少次元素的比较？ 1037
|得分|评卷人| I I I 三、综合题(每小题 28. (1)说明什么是顶点活动网 AOV网)和拓扑序列 (2) 图G 出3 种拓扑序列 (3) 图G 加一 图G 仅有一 拓扑 29. 棵二 ，AI 2，… 9代表 1， 2， 3，… 9中各个不同数字， (1)给出对该树中序遍历的结果 (2) A3 ，A5 ，A7 (3) 插入 个结点9 .5 并使 然是一 排序 A7 30. (1)设有查找表 7， 6， 4， 6， 5， 0， 8， 9， }，依次取表中数据构造一棵二叉排序树。 (2) 对上述二 (3)对上述二叉树给出中后序遍历的结果 (4) 述二 查找 行多少次元 1037