试卷代号：1252 座位号■■ 中央广播电视大学2012一2013学年度第二学期“开放本科”期末考试 数据结构（本） 试题 2013年7月 题 号 二 三 四 总分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A.4 B.3 C.6 D.12 2.串函数StrCat(a,b)的功能是进行串( ) A.比较 B.复制 C.赋值 D.连接 3.一棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A.n+1 B.n C.n-1 D.n-2 4.设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。 A.n B.n+1 C.n-1 D.2n 5.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执 行( )。 A.x=top->data;top=top->next B.x=top->data C.top=top->next;x=top->data D.top=top->next;x=data 6.一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。 A.30 B.20 C.21 D.23 1134
试卷代号 座位号 中央广播电视大学 3学年度第二学期"开放本科"期末考试 数据结构(本)试题 2013 年7 题号 - |分数 I I I I I 分l 评卷人i ,I I I- 选择 每小 1.在 字符 )个字节。 A. 4 B. 3 C. 6 D. 12 2. 数StrCat(a b) 功能是进 )。 A. 值D.连接 3. 个结点 采用链 )个指针域为空。 A.o+1 c. B. 0 D.0-2 4. 哈夫 该树 )个叶结点。 A.o C. 0-1 B. 0+1 D. 20 5. 钱顶 为top 链楼 除一个结 用 变 量x 行( )。 A. x=top->data;top=top->oext C. top=top->oext;x=top->data B. x=top->data D. top=top->next;x=data 6. 有5 第5 上有 树共 )个结点。 A. 30 B. 20 C. 21 D. 23 1134
7.在一个无向图中，所有顶点的度数之和等于边数的(·)倍。 A.3 B.2.5 C.1.5 D.2 8.已知如图1所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为()。 A.Vi V2 V Ve Vi V:V.V7 B.VV2VV;VaV,V Vz V C.VV2VVa V3Vs V V7 D.VV:Vi V V2 VV;Vs 图1 9.已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到 的一种顶点序列为()。 A.abcedf B.abcefd C.aebcfd 图2 D.acfdeb 10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。 A.按层次 B.后序 C.中序 D.前序 11.在有序表{2,4,7,14,34,43,47,64,75,80,90,97,120}中，用折半查找法查找值80 时，经( )次比较后查找成功。 A.4 B.2 点 C.3 D.5 12.有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为()。 A.25/10 B.25/9 C.20/9 D.17/9 1135
7. 一个无 图 中 数之 等于 )倍。 A. 3 C. 1.5 B. 2.5 D. 2 8. 知 如 图1 若从 深度优先搜 索 进 行遍 能得 到的一种顶点序列为( )。 VI A. VjVZV4V8VSV3V6V7 B. VI VzV4VsV8V3V6V7 c. VjVZV4V8V3VSV6V7 D. VjV3V6V7VZV4VSV8 G)-毛〉 9. 图2 广 度优先搜 索法进 的一种顶点序列为( )。 A. abcedf B. abcefd C. aebcfd D. acfdeb 10. 树进 )遍历，可以便遍历所得到的序列是有序序列。 A. 按层次B. c. 1. 序 表 2, 4, 7, 14, 34 ，47 ，64 ，75 ，80 ，90 ，97 ，120} 半 查 值80 时，经( )次比较后查找成功。 A. 4 c. 3 B. 2 D. 5 12. 有一个长 半查找 表进 在等概率情 查找 平均比较次数为( )。 A. 25/10 C. 20/9 B. 25/9 D. 17/9 1135
13.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是()。 A.冒泡 B.直接插人 C.折半插入 D.选择排序 14.一组记录的关键字序列为(46,79,56,38,40,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.排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的 一端的方法，称为()排序。 A.归并 B.插人 C.快速 D.选择 得 分 评卷人 二、填空题（每小题2分，共24分） 16. 在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是 右指针。 17.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为 18.串的两种最基本的存储方式是 和 19.一棵有2n一1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个叶结点。 20.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有 个指针域 为空。 21. 遍历二叉排序树可得到一个有序序列。 1136
个指针域 13. 未排序序列 依次 进行 比较(要求比较次数尽量少) ，然后将其放人巳排序序列的正确位置的方法是( )。 A. B. 接插 c. 折半插 D. 排序 14. 关键字序 为(46 ，79 ，56 ，38 ，40 ，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. 序序 将其依次放 为空 一端的方法，称为( )排序。 A.归并 B. 插人 c. D. 得分 二、填空题{每小题 2分，共 4分} 16. 储结 常 每 它 们 、右指针。 17. 序 编 右 孩 子 孩 子 别 为 18. 存储方式 19. 一棵有2n-l 每一 数都为2 个叶结点。 20. 于一棵具 个结 式存储 为空。 1. 一一 遍历 排序 1136
22.如图3所示的二叉树，其后序遍历序列为 e h 图3 23.如图4所示的二叉树，其先序遍历序列为 g 图4 24.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。（回答正确或不正确） 25.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其 右孩子的值。这种说法是 的。（回答正确或不正确） 26.对记录序列排序是指按记录的某个关键字排序，记录序列按 排序 结果是唯一的。 27.按某关键字对记录序列排序，若 在排序前和排 序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。 1137
22. 图3 二叉树 后序遍历 列 为 23. 图4 所示 其先序遍 序列 为 d p C g 24. 优 先 广 度 先 搜 索 序 列 一 定 此 断 的。(回答正确或不正确) 25. 必要 件是 任一 均 大 孩 子 右孩子的值。这种说法是的。(回答正确或不正确〉 26. 对记 序 列 按记 个关 字排 录 序 结果是唯一的。 27. 按某关键 对记 排序 在排序 序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。 1137
得 分 评卷人 三、综合题（每小题10分，共30分） 28.设查找表为(16,15,20,53,64,7)， (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对个元素 进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据 元素作为树结点)。 29.(1)设有查找表{5,14,2,6,18,7,4,16,3}，依次取表中数据，构造一棵二叉排序树。 (2)说明如何由序列的二叉排序树得到相应序列的排序结果。 30.(1)对给定权值2,1,3,3,4,5，构造哈夫曼树（要求每个结点的左子树根结点的权小于 等于右子树根结点的权)。 (2)给出各权值的哈夫曼编码。 得 分 评卷人 四、程序填空题（每空2分，共16分）】 31.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输出链 表中各结点中的数据。 define NULL 0 void main() (NODE a,b,c,d,head,p; a.data=6; b.data=10; c.data=16; d.data=4;/*d是尾结点/ head=(1) a.next=&.b; b.next=&c; c.next=&d; (2) ;/*以上结束建表过程*/ p=head;/*p为工作指针，准备输出链表*/ do {printf(“%d\n”,(3) (4) )while((5) 1138
I I I I -、综合题{每小题 0分，共 0分} 28. 查找表为(16 ，15 ，20 ，53 ，64 ，7) (1)居留浩法对该表进行排序〈要求升序排列) ，写出每一越的排革过程，逼常对 8个完素 进行冒泡排序要进行多少躏冒泡?第 j趟弹进行多少次元素间的比较? (2) 序后 有序 础上 所对 判 定 要求 元素作为树结点)。 29. (1)设有查找表 5， 4， 2， 6， 8， 7， 4， 6， }，依次取表中数据，构造一棵二叉排序树。 (2) 序亮 捧序 应序 30. (1)对给定权值 2， 1， 3， 3， 4， 5，构造晗夫曼树(要求每个结点的左子树根结点的权小于 等于右子树根结点的权)。 (2) 各权 得分 i评卷人 阳、程序墙空题(每空 2分，共 6分} 1. 为(6 ，10 ，16 下 程序 用 方 法 链表 并输 表中各结点中的数据。 # define NULL ° void maine) {NODE ，b ，c ，d 快head 铃p; a.data=6; b. data=10; c. data= 16; d. data=4;/ 铃d head::: (1 a. next= &.b; b. next= &.c; c. next= &.d; (2) ;/祷以上结束建表过程特/ p=head;/ 铸p 工作 链表 do {print£<"%d\n" , (3) (4) }while«5) ); 1138
32.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、 右指针域分别为left和right,数据域data为字符型，BT指向根结点)。 voidPostorder(structBTreeNode BT) { if(BT！=NULL){ (1) (2) (3) } .} 1139
32. 程序 后序遍历 算法 完成程序 格部 右指针域分别为 ft g h t，数据域 a为字符型， T指向根结点)。 voidPostorder(structBTreeNode 铃BT) i£<BT! =NULL){ (1) (2) (3) 1139
试卷代号：1252 中央广播电视大学2012一2013学年度第二学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2013年7月 一、单项选择题（每小题2分，共30分） 1.A 2.D 3.A 4.B 5.A 6.C 7.D 8.A 9.B 10.C 11.B 12.B 13.C 14.B 15.D 二、填空题（每题2分，共24分）】 16.值域 左指针 右指针 17.2i 2i+1 18.顺序存储 链式存储 19.n 20.n+1 21.中序 22.gdbeihfca 23.abdefeg 24.正确 25.不正确 26.主关键字 27.关键字相等的记录 1140
试卷代号 中央广播电视大学 3学年度第二学期"开放本科猝期末考试 数据结构(本)试题答案及评分标准 (侯参考〉 2013 年7 一、单项选择题{每小题 LA 6. C 11. B 2.D 7. D 12. B 3. A 8.A 13. C 4. B 9. B 14. B 5.A 10. C 15. D 二、填挠题(每题 16. 指针 右 17. 2i 2i 十1 18. 链式存 19. n 20. 1. 22. gdbeihfca 23. abdefcg 24. 25. 不正 26. 27. 1140
三、综合应用题（每小题10分，共30分） 28.(1)原序列16152053647 15162053764 15162075364 15167205364 15716205364 71516205364 n一1趟 n一j次 (2) 16 53 15 20 64 图4 (3)平均查找长度=(1*1十2*2+3￥3)/6=14/6 29.(1) 6 18 3 16 图5 1141
三、综合应用题{每小题 28. (1)原序列 15 20 53 64 7 15 16 20 53 7 64 15 16 20 7 53 64 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 n-l n-J (2) (3) 均查 长度 (1 赞1+2 祷2 十3 祷3)/6=14/6 29. (1) 1141
(2)中序遍历 30.(1)答 18 3 (2)答 2:001 1: 000 3:110 3:111 4:01 5:10 四、程序填空题（每空2分，共16分） 31.(1)8.a (2)d·next=NULL (3)p->data (4)p=p->next (5)p！=NULL 32.(1)Postorder(BT->left) (2)Postorder(BT->right) (3)printf(“%c”,BT->data) 1142
(2) 序遍 30. (1)答 (2) 2 , 001 1 , 000 3 , 110 3: 111 4, 01 5 , 10 四、程序填空题(每空 31. (1) &.a (2)d· next=NULL (3)p->data (4)p=p->next (5)p! =NULL 32. (1 ) Postorder ( BT-> left) (2) Postorder(BT->right) (3) print£ data) 1142