资源描述：
《中央电大历届数据结构(本)试题库试卷代号1252》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、试卷代号:1252座位号中央广播电视大学20112012学年度第二学期"开放本科"期末考试数据结构(本)试题2012年7月题号一一一-四总分一一分数得分
2、评卷人一、单项选择题{每小题2分，共30分}1深度为5的完全二叉树共有20个结点，则第5层上有()个结点(根所在结点为第一层)。A3B8C5D62已知一个图的边数为m，则该图的所有顶点的度数之和为()。A2mBmC2m+1Dm/23数据结构中，与所使用的计算机元关的是数据的()结构。A物理B存储C逻辑与物理D逻辑4链表所具备的特点是()。A可以随机前问任一结点B占用连续的存储空间C插入删除不需要移动元素结点D可以通过下标对链表进行直
3、接由问5线性表只要以()方式存储就能进行折半查找。A链接B顺序C关键字有序的顺序D二又树6散列查找的原理是()。A在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B按待查记录的关键字有序的顺序方式存储C按关键字值的比较进行查找D基于二分查找的方法13527对n个元素进行冒泡排序若某趟冒泡中只进行了()次元素间的交换，则表明序列已经排好序由AlB2CODn18排序过程中，每一趟从元序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是()。A直接插入排序B快速排序C冒泡排序D选择排序9在对一组元素(64，48，106，
4、33，25，82，70，55，93)进行直接插人排序时，当进行到要把第7个元素70插人到已经排好序的子表时，为找到插人位置，需进行()次元素间的比较(指由小到大排序)。A6B2C3D410采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法)，最坏的情况下要进行()次元素间的比较。An十2BnCn1D0/211如图，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为AacebdgfBabecdgfCacfedgboabecfdg12元素2，4，6，8按顺序依次进钱，则该校的不可能输出序列是()(进找出钱可以交替进行)0A8,6,4,2B2,4,6,8C4,2
5、,8,6D8,6,2,413排序方法中，从未排序序列中挑选元素，并将其依次放人己排序序列(初始为空)的一端的方法，称为()排序。A归并B插入C选择D快速14一棵哈夫曼树总共有23个结点，该树共有()个叶结点(终端结点儿A10B13C11D12135315队列的插人操作在()进行。A队头B队尾C队头或队尾D在任意指定位置得分
6、评卷人二、填空题(每小题2分，共24分)16一棵二又树没有单分支结点，有6个叶结点，则该树总共有个结点。17设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二又树一共有个结点。18按照二又树的递归定义，对二叉树遍历的常
7、用算法有先序、、二种。19结构中的数据元素存在一对多的关系称为结构。20把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。21结构中的数据元素存在一对→的关系称为结构。22如图2所示的二又树，其后序遍历序列为口的。、....回的记录在排序前和排序后仍保持它得分
8、评卷人三、综合题{每小题10分，共30分)28(1)利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆(小根堆)，画出该堆(不要求中间过程)。(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。29设查找表为(16，15，20，53，64，7)，(1)用冒泡法对该表进行排序(要求升序排
9、列)，要求写出每一趟的排序过程。(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(要求以数据元素作为树结点)。(3)求在等概率条件下，对上述有序表成功查找的平均查找长度。30(1)设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。(2)利用上述二叉排序树，为了查找110，经多少次元素l司的比较能成功查到，为了查找15，经多少次元素间的比较可知道查找失败?得分
10、评卷人四、程序填空题{每空2分，共16分)31以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针s
11、tructnode{ElemTypedata,structnode祷next，structnode祷front，赞rear，VOIdInQueue(ElemTypex)structnode赞p，p=(structnode势)(1),p->data=x,P->next=NULL,(2),rear=(3),135532以下函数在head为头指针的具有头结点的单向链表中删除第1个结点，structnode{mtdata,structnode祷next，typed
