试卷代号：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
得分 评卷人 四、程序填空题（每空2分，共16分） 31.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针p(查找成功p指向查到的树结点，不成功p指向为NULL)完成 程序中的空格 typedef struct Bnode int key; struct Bnode left; struct Bnode *right; )Bnode; Bnode BSearch(Bnode bt,int k) /bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字/ Bnode p; if(bt== return (bt); p=bt; while(p->key！= if(kkey) else if(p==NULL)break; return( 1038
|得分|评卷人| I I I 四、程序填空题{每空 2分，共 6分) 1. 算法 若二叉 根结 否则 值是指向树结点的结构指针 (查找成功 p指向查到的树结点，不成功 p指向为 NULL)完成 程序中的空格 typedef struct Bnode int key; struct Bnode 蒋left; struct Bnode 祷right; } Bnode; Bnode 头BSearch(Bnode 祷bt int k) /提 接收二 要查找 关键 诀 / { Bnode 秘p; if(bt== return (bt); p=bt; while(p一>key! { f(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=q->next; q->next=head; q=p;p=p->next; while(p->data！=x) {q=p; s->next=p; 1039
32. 有一个头指 为head 不带 链表 ，p 、q 变量， p指向链表中结点 a， (设链表中没有结点的数据域与结点 a的数据域相同) ，写出相关 语句 (1)使该单向链表成为单向循环链表 (2) 入结 q=p; x=p->data; while ( 一>next=head; q=p; p=p->next; while(p一>data! =x) { q=p; 一>next=p; )q=q一>next; 1039
试卷代号：1252 国家开放大学（中央广播电视大学）2014年春季学期“开放本科”期末考试 数据结构（本）试题答案及评分标准 (供参考) 2014年7月 一、单项选择题（每小题2分，共30分） 1.C 2.A 3.D 4.B 5.A 6.B 7.D 8.B 9.A 10.A 11.C 12.D 13.C 14.B 15.B 二、填空题（每题2分，共24分）】 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 adbc dabc (3)在b和d间添加有向边 29.(1)A7A4A8A2A5A9A1A3A6 123456789 1040
试卷代号 国家开放大学(中央广播电视大学 4年春季学期"开放本科"期末考试 数据结构(本)试题答案及评分标准 (供参考) 2014 年7 -、单项选择题(每小题 1. C 2. A 3. D 6. B 7. D 8. B 11. C 12. D 13. C 4. B 9. A 14.B 5. A 10. A 15. B 二、填空题(每题 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. 为2 ，3 ，元素为 24. 5 25. 26.519876432 27. 三、综合应用题{每小题 28. (1)用顶点表示活动，边表示活动间先后关系的有向图称为顶点活动网 在顶点活动网中，若不存在回路，则所有活动可排列成→个线性序列，使每个活动的所有 前驱活动都排在该活动的前面，称此序列为拓扑序列 (2) abdc adbc dabc (3)在 d间添加有向边 29. (1 ) A7 A4 A8 A2 AS A9 Al A3 A6 1 234 5 6 789 1040
(2)851 (3) 7 4 8 2 5 9 6 9.5 图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 17 14 26 16 18 30 15 19 28 图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
(2) 8 5 1 (3) 30. (1)见图 (2) 15 ,16,14,19 ,18,28,30,26,17 (3) 14 ,15,16,17,18,19 ,26,28,30 (4) 4 四、程序填空题{每空 31. (1 ) NU LL (2)k (3)p=p一>left (4)p=p一>right (5)p 32. (1) 一>next! =NULL (2) p=p一>next; (3)q一>next=s; 1041