试卷代号：1252 座位☐ 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试 数据结构（本） 试题 2009年7月 题 炒 君 四 磁分 分 数 得 分 评爸人 一，单项选择丛（每小题2分，共30分】 1.|对线性农，在：储：如果位常用的操作处以第；个结成及其前服，则采用( )存惭 方式录丹省时间。 A.弹过表 B.双链表 C.单仍环销 ).顺序表 2.数据结构，与所使用的计算机无关的是数据的( )纳构。 A.物理 3.存储 (逻辑与物理 D.逻辑 3.以下特征中，( )不是算法的特性。 A.行穷性 B.确定性 C.可行性 D,有D个或多个输出 4.设有一个长度为n的顺序表，婴在第i个元素之前（也就是插人元寒作为新表的第：个 元常)，则移动元素个数为〔)。 A.n-i+] B.n-i C.n-i-I D.i 130
5.找的插人删除操作在( )进行。 A戈底 B.任意位爱 (指定位置 .伐顶 6.以下说法正确的是()。 A.栈的特点是先进先出，队列的杵点是先进示出 以.栈和队列的每都是先进后出 (.栈的料点是抗：出，队列的转点足先进先出 1,搜和队列的特点都心先进先 7.店素么，A,,K按购宝欣次边找，则该找的太可能输H序刘从：( (进代：出找可以父州 训). A8,G,1,2 H.2,4,6,8 .,2,H, i.H,6,2. 8.设行个妇阶的对称刻件入.采站有销的方式，将北下角邢分以彳序为.亦打 体列·维数纠细小（数圳外从1开始），则知阵中心掌，.个·维数组出中的下()… A.42 3.13 〔.27 1.32 4.电的数S1n“",“1))的值为( A.0 .1 .·J 121 1山.任梯叉树小，并编号为i的钻点存在右孩子.则右孩了的顺序缩号为()， 八.2 .2i-1 C.2i:2 1).2+1 1.设-郴有力个叶结点采中性式存储的艾树，除叶结点外每个先点度数都为2，则浅 树非行( )个指针域为空。 A.2n 13.2n11 (2n+2 I0.n+1 1341
12.已知如图1所示的个图，若从预点出发，按广度优先搜东法进行遍历，则可能得到 的一种顶点序列为()。 b 图小 A.alxerd B.nhcefd C..aehcfd D).sofdleb 】3.在有序我1】，3,8,13,33,42,46.3,76.78,80,97,1001中，月折半查找仪86时，始 )次比校后查找成功， A.6 1h.3 .8 1.4 1.有·个长度为0的有序表.按折半查找对该表进行查找，在等概率情况下查找成功的 Ψ均比较次数为( >。 Λ.2/10 B.3t/1c (.26/10 0.29/9 15.一组记录的键字序列为(37,70,47,29,31,85)，利用快速排序，以第一个关键字为分 割元素，经过一次划分后结梨为()。 A.31.29.37,47,70,85 5.29,31,37,47,70,85 C.31,29,37,70,47,85 D.31,29,37,85,47,70 1342
得分 评卷人 二、填空原（每小题2分，共24分】 1,把数拼杯闭到计算机中，并其体保现数据之间的逻辑结构称为一一结构。 2.特构中的数据元寒存在·对-的关系称为 结构 3,在以问值表中，相个结《有两个指针域，-一个指向 ,分 -个报向 4,设打·个头指|为h的的问过表，y指的表中某个结点，l行yx1-一1L, 通过操种 一一一。。…，就叫使该单向战构进城单向研坏经表 5.从·个栈顶指什为h的品栈中糊除个钻点时，用x保：被删结点的处，国执 xu1和_. 。一一·（绪点的指|城为x) G.两个中相等的充分必要年付品 7.对：义树的清历可分为。， 四]种不同的海店次序。 州.棵有n个结点的义树，（到个非外结点的度效都为，州该树共有.一一个纳 点… 只.…探行14个纳点的完全：义树，则它的最席层上有一_个排点。 10.图2所示的义树，其先光：序遍历序列为 d g 图2 1343
11.哈希函数是记录关键字值与该记录 之间所构造的对应关系。 12.二叉树排序中任一操子树都是二叉排序树，这种说法是 的。（回答 正确或不正确) 得 分 评卷人 三、综合题{每小厦10分，共30分} 1.设一组记录的关键子序列为(49,83,59,41.43,47)，采用堆排序算法完戒以下领作：（要 求小根堆，那画出中间过程) (1)以一.芝树捕述6个心紫的初始堆： 2)以一义树排述逐次收走堆顶元意，经调整得到的5个心素、4个元素的堆 .没1序为(13,19,25,3,48,1.63,84.91,116,135,200)，元款的下标依次为↓.2， …,2 (1)说出有哪几个尤东形要经过4次元常回的比较能成功查列： (2)出对述行序表进忻平查找所对应的判是树（树结点用下标表示）： (3)设作找元求为5，孤婆进行多少次元素间的比较才能确定不能查到。 3.(13对给烂数列[7，]6,4,8.20,9,6,18,5}，依次娘数刿中的数据，构滥-一棵.一义排序树。 (2)对一个给定的查找值，简述针对二“叉排序树进行查找的算法步骤，在上述二叉树中查 找元东20共要进j多少次元素的比较？ 1344
得分 评卷人 四、程序填空题【每空2分，共16分】 1,以下目泡法程序对存放在A[门，[2]…，[n]中的序列进行排序完成得序中的： 格部分，其中n是元京个数，婴求按开序排列。 void bsort (N(DE aL J,int n) NODE temp int i.).flag: 【r(i1,(1) 十中)： iflag'd furki 1<2) if(ntikey'.nfil 11.key) g=1+ ImEp-nl: () (4) (Gag Q}break i 程序中ug的功他是(5) 2.以下程序是先光序证历二叉树的递算决的程序，完成程序中空：格部分（树钻构中：， 指针域分别为【1和ig1,数据域dla为字符型，BF指向根结点). void Preorder (struct BT'reeNade:BT) i(BT =NULL) (1) (2) (3) 135
试卷代号：1252 中央广摇电视大学2008一2009学年度第二学期“开放本科"期未考试 数据结构（本） 试题答案及评分标准 (供参者) 2009年7刀 一、单项选择题（每小题2分，共30分】 1.1) 2.) 3.0 4.八 5.10 6.C 7.1D 8.t 9.h 10.TD 1. 12.B 13.1 14.A 5.九 二，填空显每小题2分，共24分 1,物理（待储） 2.线M 3,结点的接后继 结点的九接前昭 4.-^Ix1…hl: 5.山=1-t:x1i 6.串长度相等几对应位置的字符相等 7.先序 中序 后序层次 8.2n-1 9.7 10.abdgcefhi 11.存储地址 12.年 1346
三、综合题【每小题10分，共30分) 1.(1) 9 59 哈 83 41 7 50 1图3 (2) M 0 43 9 47 9 g 47 47 图4 1347
2.(1)19,48,84,116,200 (2) 12 图5 (3)3次 3.(1) 公 20 18 图5 (2)先将给定值与根结点比较，若相等则查找成功，杏则若小于根结点则在左了树中继织 查找，大予报结点在右子树中查找，查找20北进行3次比较。 四、程序填空（每空2分，共16分】 1.1)jdata) (2)Preorder(BT->left) (3)Prtorder(BT->right) 1348