试卷代号：1252 座位号■■ 中央广播电视大学2011一2012学年度第二学期“开放本科”期末考试 数据结构（本）试题 2012年7月 题 号 三 四 总 分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1深度为5的完全二叉树共有20个结点，则第5层上有( )个结点（根所在结点为第 一层)。 A3 B8 C5 D6 2已知一个图的边数为，则该图的所有顶点的度数之和为( )。 A 2m Bm C2m+1 D m/2 3数据结构中，与所使用的计算机无关的是数据的( )结构。 A物理 B存储 C逻辑与物理 D逻辑 4链表所具备的特点是()。 A可以随机访问任一结点 B占用连续的存储空间 C插人删除不需要移动元素结点 D可以通过下标对链表进行直接访问 5线性表只要以()方式存储就能进行折半查找。 A链接 B顺序 C关键字有序的顺序 D二又树 6散列查找的原理是()。 A在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系 B按待查记录的关键字有序的顺序方式存储 C按关键字值的比较进行查找 D基于二分查找的方法 1352
试卷代号 2 5 座位号 中央广播电视大学 2 0 11 2012 度第二 放本 数据结构(本)试题 2012 年7 题号 - 总分 分数 得分|评卷人 一、单项选择题{每小题 2分，共 0分} 深度为5 全二叉树 有20 第5 上有 )个结点(根所在结点为第 一层)。 A 3 B 8 C5 D6 图 的 顶点 )。 A 2m B m C 2m+1 D m/2 理B 元关 是数 )结构。 链表所具备 理D )。 任一 点B 用连 存储 入删除不需 点D 对链表 接B )方式存储就能进行折半查找。 顺序 键字有序 序D二又 理是 )。 关键 该记 对应 方式存储 按关 方法 1352
7对个元素进行冒泡排序若某趟冒泡中只进行了()次元素间的交换，则表明序列 已经排好序。 A1 B 2 Co D n-1 8排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经 排好序的子序列的适当位置，直到全部排好序为止，该排序算法是()。 A直接插人排序 B快速排序 C冒泡排序 D选择排序 9在对一组元素(64,48,106,33,25,82,70,55,93)进行直接插人排序时，当进行到要把 第7个元素70插人到已经排好序的子表时，为找到插人位置，需进行()次元素间的比较 (指由小到大排序)。 A6 B2 C3 D4 10采用顺序查找法对长度为的线性表进行查找（不采用表尾设监视哨的方法），最坏 的情况下要进行( )次元素间的比较。 A n+2 Bn C n-1 D n/2 11如图，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为 () A acebdgf B abecdgf C acfedgb D abecfdg 12元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交 替进行)。 A8,6,4,2 B2,4,6,8 C4,2,8,6 D8,6,2,4 13排序方法中，从未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一 端的方法，称为()排序。 A归并 B插人 C选择 D快速 14一棵哈夫曼树总共有23个结点，该树共有()个叶结点（终端结点）。 A10 B13 C11 D12 1353
若某 )次元素间的交换，则表明序列 已经排好序由 COD AlB2 n 1 过程 一趟 序 子 排好序的子序列的适当位置，直到全部排好序为止，该排序算法是( )。 接插 一组 4 8 0 6 ，33 8 2 ，70 ，93) 进 行 7个元素 0插人到已经排好序的子表时，为找到插人位置，需进行( )次元素间的比较 (指由小到大排序)。 A 6 B 2 C3 D4 10 采 用 表尾 哨 的 ，最坏 的情况下要进行( )次元素间的比较。 A B n C n 1 D 0/2 11 顶 点 先 搜 能 得 A acebdgf B abecdgf C acfedgb o abecfdg 12 素2 ，4 ，6 ，8 次进 )(进找出钱可以交 替进行) 0 A 8 ,6 ,4,2 C 4,2 ,8 ,6 B 2,4 ,6 ,8 D 8, 6 ,2 ,4 13 排 序 序 端的方法，称为( )排序。 14 择D 有23 个结 )个叶结点(终端结点儿 A 10 B 13 C 11 D 12 1353
15队列的插人操作在( )进行。 A队头 B队尾 C队头或队尾 D在任意指定位置 得分 评卷人 二、填空题（每小题2分，共24分） 16一棵二又树没有单分支结点，有6个叶结点，则该树总共有 个结点。 17设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点 的编号为10，该完全二又树一共有个结点。 18按照二又树的递归定义，对二叉树遍历的常用算法有先序、 三种。 19结构中的数据元素存在一对多的关系称为 结构。 20把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 结构。 21结构中的数据元素存在一对一的关系称为 结构。 22如图2所示的二又树，其后序遍历序列为 h 图2 23n个元素进行冒泡法排序，通常需要进行 趟排序。 24二叉树为二又排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其 右孩子的值。这种说法是 的。（回答正确或不正确） 25图的深度仇先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。 (回答正确或不正确) 26根据搜索方法的不同，图的遍历有 两种方法。 27按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它 们的前后关系，则排序算法是稳定的，否则是不稳定的。 1354
15 队列 插人 )进行。 队头 头 或 得分|评卷人 二、填空题(每小题 二种。 16 单分支结 有6 个结 17 的编号为 0，该完全二又树一共有个结点。 18 树遍 常用 19 在一 20 把数 存储 算 机 体现 21 存在 22 图2 所示 的。 .... 的记录在排序前和排序后仍保持它
得分 评卷人 三、综合题（每小题10分，共30分） 28(1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆（小根堆），画出该堆（不 要求中间过程)。 (2)写出对上述堆对应的完全二又树进行中序遍历得到的序列。 29设查找表为(16,15,20,53,64,7)， (1)用冒泡法对该表进行排序（要求升序排列），要求写出每一趟的排序过程。 (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据 元素作为树结点)。 (3)求在等概率条件下，对上述有序表成功查找的平均查找长度。 30(1)设有一个整数序列{50,38,16,82,110,13,64}，依次取出序列中的数，构造一棵二 叉排序树。 (2)利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找 15,经多少次元素间的比较可知道查找失败？ 得 分 评卷人 四、程序填空题（每空2分，共16分）】 31以下函数为链队列的人队操作，x为要人队的结点的数据域的值，front、rear分别是 链队列的队火、队尾指针 struct node ElemType data, struct node米next, }, struct node front,rear, void InQueue(ElemType x) { struct node p, p=(struct node *)(1) p->data=x, p->next=NULL, (2) rear=(3) } 1355
得分|评卷人 三、综合题{每小题 0分，共 0分) 28 (1)利用筛选过程把序列 2， 8 2， 7， 0 2， 6， 2， 7， }建成堆(小根堆) ，画出该堆(不 要求中间过程)。 (2) 堆对应 完全 树进行 序遍历 29 找表为(16 ，15 ，20 ，53 ，64 ，7) (1)用冒泡法对该表进行排序(要求升序排列) ，要求写出每一趟的排序过程。 (2) 序后 有序 其进 半 查 所对应 判 定 元素作为树结点)。 (3) 求在 率条件下 对上 表成 查找 30 (1)设有一个整数序列 0， 8， 6， 2， 1 1 0， 3， }，依次取出序列中的数，构造一棵二 叉排序树。 (2) 利用 排序 找110 多 少 次元 功 查 15 次元 间 的 可知 查找失 得分|评卷人 四、程序填空题{每空 2分，共 6分) 31 ，x 据域 front 、rear 分别是 链队列的队头、队尾指针 struct node { ElemType data , struct node 祷next struct node 祷front 赞rear VOId InQueue(ElemType x) struct node 赞p p= (struct node (1) p->data= x, P->next=NULL, (2) rear= (3) , , , 1355
32以下函数在head为头指针的具有头结点的单向链表中删除第1个结点， struct node int data, struct node next, }, typedef struct node NODE int delete(NODE head,int 1) { NODE p,*q, int J, q=head, J=0, while((q!=NULL)&&.((1) ) { (2) J十十， if(q==NULL) return(0), p=(3) (4) =p->next, free((5) return(1), 1356
32 在head 头指 有头 除第 struct node { mt data , struct node 祷next typedef struct node NODE mt delete(NODE祷head，mt 1) NODE 祷p 祷q » , mt J, q=head , J=O , whI1e«q' = NULL) &. &.( (1) (2) J++ , l{Cq==NULL) return(O) , p= (3 ) (4) free«5) , =p->next , ) , return(1 ) , 1356
试卷代号：1252 中央广播电视大学2011一2012学年度第二学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2012年7月 一、单项选择题（每小题2分，共30分） 1C 2A 3D 4C 5C 6A 7C 8A 9 C 10B 11B 12D 13C 14D 15B 二、填空题（每题2分，共24分） 1611 17 21 18中序 后序 19树形 20物理（存储） 21线性 22 gdbeihfca 23 n-1 24不正确 25正确 26深度优先搜索遍历 广度优先搜索遍历 27相等 1357
试卷代号 中央广播电视大学 2012 学年度第二学 开放 末考 数据结构(本)试题答案及评分标准 (供参考) 2012 年7 -、单项选择题(每小题 2分，共 0分} 1 C 6 A lI B 2 A 7 C 12 D 3 D 8 A 13 C 4 C 9 C 14 D 5 C 10 B 15 B 二、填空题{每题 2分，共 4分} 17 21 18 19 20 物理 21 22 gdbelhfca 23 n-l 24 不正 25 26 优先搜索 广度优先 27 相等 1357
三、综合应用题（每小题10分，共30分） 28(1) 16 42 32 52 82 67 57 102 (2)102,52,42,82,16,67,32,57 29(1)原序列16152053647 15162053764 15162075364 15167205364 15716205364 71516205364 (2) 7 5 64 (3)平均查找长度=(1*1+2*2+3*3)/6=14/6 1358
三、综合应用题{每小题 28 (1) (2)102 ,52 ,42 ,82 ,16 ,67 ,32 ,57 29 (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 (2) (3) 找长度 (1 祷1 十2 祷2+3 铃3)/6=14/6 1358
30(1) 50 38 82 16 64 10 13 (2)三次，四次 四、程序填空题（每空2分，共16分） 31 (1)malloc(sizeof(struct node)) (2)rear->next=p (3)p 32（1)力next (3)q->next (4)q->next (5)p 1359
30 (1) (2) 四、程序填空题(每空 31 (1) malloc(slzeof(struct node)) (2) rear->next = p (3)p 32 (1)Jnext (3)q->next (4)q->next (5)p 1359