资源描述：
《0907数据结构(本)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、试卷代号:1252座位号CD中央广播电视大学2008-2009学年度第二学期"开放本科"期末考试数据结构(本)试题2009年7月
2、题号I--I二l三l四l总分
3、
4、分数IIIIIII
5、得分
6、评卷人
7、II一、单项选择题(每小崎题2分如盯，如共扫3t3ωO1.针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用()存储方式最节省时间。A.单链表B.双链表C单循环链表D.顺序表2.数据结构中，与所使用的计算机无关的是数据的()结构。A.物理B.存储巳逻辑与物理D.逻辑3.以下特征中，()不是算法的特性。A.有穷
8、性B.确定性C.可行性D.有O个或多个输出4.设有一个长度为n的顺序表，要在第i个元素之前(也就是插入元素作为新表的第i个元素)，则移动元素个数为()。A.n-j+1B.n-jC.n-j-1D.j13405.械的插入删除操作在()进行。A.找底B.任意位置c.指定位置D.战顶6.以下说法正确的是()。A.拢的特点是先进先出，队列的特点是先进后出B.械和队列的特点都是先进后出c.枝的特点是先进后出，队列的特点是先进先出D.械和队列的特点都是先进先出7.元素2，4，6，8按顺序依次进枝，则该拔的不可能输出序列是()(进拔
9、出棋可以交替进行)。A.8,6,4,2B.2,4,6,8C.4,2,8,6D.8,6,2,48.设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中〈数组下标从1开始)，则矩阵中元素a7，6在一维数组B中的下标是()。A.42B.13C.27D.329.串函数StrCmp("d"，"D勺的值为()。A.aB.1C.-1D.310.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为()。A.2iB.2i-1C.2i十2D.2i十111.设一棵有n个叶结点采用链式存储
10、的二叉树，除叶结点外每个结点度数都为2，则该树共有()个指针域为空。A.2nB.2n十lC.2n十2D.n十1134112.已知如图l所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为()。图1A.abcedfB.abcefdC.aebcfdD.acfdeb13.在有序表{1，3，8，13，33，42，46，63，76，78，邸，97，100}中，用折半查找值86时，经()次比较后查找成功。A.6B.3C.·8D.414.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况
11、下查找成功的平均比较次数为()。A.29/10B.31/10C.26/10D.29/915.一组记录的关键字序列为(37，70，47，29，31，8日，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为()。A.31,29,37,47,70,85B.29,31,37,47,70,85C.31,29,37,70,47,85D.31,29,37,85,47,701342
12、得分l评卷人
13、二、填空题(每小题2分，共24分)III1.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。2.结构中的数据元素存在
14、一对-的关系称为结构。3.在双向链表中，每个结点有两个指针域，一个指向，另一个指向4.设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next==NULL,通过操作，就可使该单向链表构造成单向循环链表。5.从-个战顶指针为h的链战中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和(结点的指针域为next)6.两个串相等的充分必要条件是7.对二叉树的遍历可分为一一一一、一←一一一、一一-一、一一一-四种不同的遍历次序。8.一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该
15、树共有个结点。9.一棵有14个结点的完全二叉树，则它的最高层上有个结点。10.如图2所示的二叉树，其先序遍历序列为图2134311.哈希函数是记录关键宇值与该记录之间所构造的对应关系。12.二叉树排序中任一棵子树都是二叉排序树，这种说法是的。(回答正确或不正确)
16、得分l评卷人
17、三、综合题(每小题10分，共30分)I1-,1.设一组记录的关键宇序列为(49，83，59，41，43，47)，采用堆排序算法完成以下操作:(要求小根堆，井画出中间过程)(1)以二叉树描述6个元素的初始堆;(2)以二叉树描述逐次取走堆顶元素后，
18、经调整得到的5个元素、4个元素的堆。•2.设有序表为(13，19，25，36，48，51，63，84，91，116，135，200)，元素的下标依次为1，2,…..,120(1)说出有哪几个元素需要经过4次元素间的比较才能成功查到p(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示h(3)设查找元素为5，需要进行多少次元素间的比
