中央广播电大数据结构试题及答案2

1、中央广播电视大学20082009学年度第二学期、幵放本科“期末考试数据结构试题一、单项迭择题（在括号内填写所迭择的标号，每小题2分，共L8分）1-当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时，则对应的形彗应说明为（）。A. 基本类型 B.引用型C.传值型 D.常值引用型2. 在一个长度为n的顺序表的任一位羞插入一个新元素的时间复杂度为（）。A. O（n）B O<n/2）C. 0（1）D. 0（ n1）3. 栈的插入和删除操作在（）进行.QA栈顶B栈底"C任議位置D.中间位复“4. 已知一个厂义表为A（a, b, c）. （d, e, 0）,从A中取出原子e的运算

2、是（）A. Tail(Hcad(A»B. Head(TaiKA)C. HeacKTailCHeadCTaiKD. HeadCHeadCTailCTaiKA)5. 在一棵二叉树的徒接存储中，每个存储结点至少要包含（）个指针域。AI B2 C3 D46有向團中的一个顶点的度数等于该顶点的（）。A入度B.出度C入度与出度之和 D.（入度十出度）/27.与邻接矩阵相比，邻接表更适合于存储（）。A.无向團 B.连通團C. 稀疏图 D.稠密图8在通常情况下，查找数据较快的方法是（）查找方法。A.顺序 B.折半C二叉树 D散列9.在一棵m阶B树中，每个结点所包含的子树个数最多为（）个。A m/2

3、B m-1C. m D. m4-l二、填空题（在横线处填写合适的內容，每小题2分，共14分）1. 在单琏表中设蚤表头附加结旦的作用是在插入和刪除表中任一个元素时的操作都（）。2.设眾序栈的址大容議为MaxSizctcp-一1表示栈空侧判斯投摘的条件爬top-3. 在一棵高皮为4的完全二叉树中，最多包含有（）个结点。假:£树根结点的高皮为0。4在一个最大堆中，堆顶结点的值是所有结点中的<）o5. 具有n个顶点的连通图的生成树含有（）条边。6. 在对n个结点逬行的堆排序中，对任意一个分支结点进行调整（筛）运章的时间复杂度（。7假定一个线性表的关健码序列为(12, 23, 74, 5

4、5, 63, 40, 82, 36)，若按key%3条件。进行划 分，使得同一余数的元素成为一个子表，则元素74所在子表的长度为()o三、利断题(在每小题前面打对号表示正确或打叉号表示错误，毎小题2分，共14分)()1.在顺序耒中，逻辑上相邻的元素在物理位置上不一定相邻。()2.琏式栈占顺序栈相比，一个明显的优点泉通常不会出现栈満的情况。()3.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为 止。()4.在一棵二灵树中，很定每个结点只有右子女，没有左子女，则对它分别进行前舟遍历和后序遍历吋，将 具有相同的结果。()5.向具有n个结点的堆中插入一个元素的

5、时间复杂度为O(n)。()6在二叉擾索尉中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的将是最优 二叉扌叟索树。()7.对一个有向图进行拓扑排序，一定可以将图中的所有顶点秤列成一个线性有序的拓扑序列。得分评雅人S3、运体翹(曲小15 6分共30分)】巳知一棵二戈轲的中斤和后序序列如下求岀该二叉轲的所有分支结点数和叶子结点数 中序用列:c»biJe»«»gJ厉序厚列；CY,d,bRfm2.已知图G-<V,E>.其中E® «a.b>.<a.<t>.<a,e>,<b

6、,a>.<c*b>,<eJ>.<d,e>,<e»c>)假定该图采用邻按衣作为存嶄结构我个顶点邻搖好按除頂点ASCII码值的次序储體 的，试分JM写出从頂点a开始进行深度和广度授索追历所鮒到的頂点序列深度找猱顶点序列，ruta*頂点序対:3已知一个芾权厠的顶点集V和边集G分别为：V=0, 1, 2, 3, 4, 5)E=(0, 1)19, (0, 2)10, (0, 3)14, (1, 2)6, (1, 5)5, (2, 3)26, (2, 4)15, (3, 4)18, (4, 5) 6;试根据迪克斯特拉(Dijkstra)算法求

7、出从顶点0到其余各顶点的最矩路径，在下表中填写应的路径长度。顶点：012345路径长 gh |0|4. 设散列表的长度m=7,散列函数为H(K) = Kmod m,若采用线性探查法解决冲突，依次插入的关镇硝序列为 19 14, 23, 68, 20, 84,分别求出查我14、20、84时的搜索长度。查找14、20、84的扌叟索长度分别为；5. 已知一个数据集合为36, 25, 30, 62, 40, 53, 46,试把它调整为一个最大堆。最犬堆：)分评卷人五、算法分析£6(每小题6分其12分)1. 该算法功能为：从否头捋针为I的单磁表中删陈号X值相同的所育结点朋毎表中的点结构为(da

8、uJink).阅ifi算法茯划有&线的上张填骂合适的内容.void purge_linkM( Us iNode & L. int X)(if(L "NULL) returniLiriNock * p> * pl* p2jp pl new List Node ipl>link"fcp2-tLiwhile (p2>if(p2>dau= = X) (pl>link=p2>link» delete p2< p2cpl >link；>&址 «8JL = p>)inkidelete2

9、. 拒出下面算法的功能ini unknown(int A ini n) if(n = = 1) return 人0$ini tcinp*,runkaownCA« n 1):iR An 1 J5>iemp) return An 1J i elc return lcrnj> ;算法功能整用分评卷人六、算法设计題(甸小題6分共12分L已知二又树中的结点类型BinTrzNwk定文为：struct BinTrceNodc char dam； BinTrccNodc * left, * rigbii) iJt中da“为结点和xiKhc分别为招树左.右子女绍点的需針域，抿滋下面国效/

10、明编弓岀求-操二又树中叶子结点总敷的算法该总最值由函效遞回假定金数BT初始彳 佝这棵二叉树的根结点.ini BTrccLcafC&untCBinTreeNode BT) i2. 取犀下阖函数“几理旳恥通过扫描一遍山2数俎达到蛍飭摊列数据的目的便得/ 有负值敘莖位于所有非负值和0值敷愣之前.济补充完整rcArra.iKc函数体中遗沥部分M 其能够完成所麼求的功陡.void reArrangcCT daiaCJ«ir>t sixe)iint Qisixe 1 $T tempiwhic<daui<0 && iVj> i+ + * whi】e(

11、cUtaj>0 && j>i)j</拄下面空行添加if语旬的内容i+ + 8 j、单项选择题（在括号内填写所选择的标号，每小题2分，共L8分）1B 2A 3A 4C 5B6. C 7. C 8. D 9. C二、填空题（在横线处填写合适的内容，每小题2分，共14分）1. 相同2. MaxSize13314最大值5 n1G. O（logn）72三、判断题（在毎小题前面打对号表示正确或打叉号表示错误，毎小眈分，共14分1 X 2. V 3. V 4. x 5 x6. V 7. x四、运算题（毎小题6分，共3吩）1. 分支结点数：4、叶子结点数：3/全对给6分，否则

12、。分2. 深度搜索顶点序列；6 b, d, e, c/3分广度搜索顶点序列；6 b, d, e, c /3分3. 译分标准：对1个给1分，全对给6分。現点：0!23451 01C10 I 1425Z14. 查找23、68、84的搜索长度分别为；I、3、4 /毎个数据占2分5. 最大堆：62, 40, 53, 25, 36, 30, 46五、算法分析髓（毎小国6分，共12分）pl-p2、p2=p2A】inkX p2p->IMk）每空 3 分2求出井返回效组An中门个数黠的直大值.木上法设i+a（W小理6分，共12分1.评分标准；根据須程酌情给分ini BTrccLcfCount（Bin 1 rceNodc * Bl）i(BT® NULL) return Oielse if(BT->lefi-NULL &a