数据结构历年试题及答案

1、试卷代号：1252 中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试 、单项选择题（每小题 2 分，共 30 分） C. top= top-next; x=top-data D.top=top-next;x=data 6. 一棵完全二叉树共有 5 层，且第 5 层上有六个结点，该树共有 （ ）个结点。 A. 30 B. 20 C. 21 D. 23 7. 在一个无向图中，所有顶点的度数之和等于边数的 （ ）倍。AA . O 上；.B . 3 C. 1.5 D . 2 8. 已知如图 1 所示的一个图，若从顶点 V,出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为

2、（ ）。 D- V.ViV.VrVtV.V.V 图 1 2 9. 已知如图 2 所示的一个图，若从顶点 a 出发，按广度优先搜索法进行遍历，则可能得到 的一种顶点序列为 （ ）。A. abcedfB. abcefdC. aebcfdD. acfdeb 10. 对二叉排序树进行（ ）遍历，可以使遍历所得到的序列是有序序列。 A.按层次 B.后序 C.中序 D.前序 11. 在 有 序表（2, 4, 7, 14, 34, 43, 47, 64, 75, 80, 90, 97, 120）中，用折半查找法查找值 80 时，经（ ）次比较后查找成功。 A . 4 B . 2 C. 3 D . 5 12.

3、 有一个长度为 9 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为（）。 A. 25/10 B . 25/9 C. 20/9 D . 17/9 13. 排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是 （）。 A .冒泡 B。直接插入 C .折半插入 D .选择排序 14 .一组记录的关键字序列为 （46 , 79, 56, 38, 40, 84）,利用快速排序，以第一个关键字为 分割元素，经过一次划分后结果为 （）。A . 40,38946,79956,84 B .

4、40,38946,56,79,84 C . 40, 38,46,84,56,79 D . 38, 40,46956,79,84 15. 排序方法中，从尚未排序序列中挑选兀素，并将其依次放人已排序序列（初始为空）的 一端的方法，称为（） 排序。A.归并 B.插入 C.快速 D.选择 1 . A 2 . D3. A 4. B5.A6. C 7. D 8 . A 9 . B10.C11 . B 2 . B 13 . C 14 . B15.D 1. 在 C 语言中，顺序存储长度为 3 的字符串，需要占用（ ）个字节。 2. 串函数 StrCat（a, b）的功能是进行串（ ）。A.比较 B.复制 3.

5、 -棵有 n 个结点采用链式存储的二叉树中， 共有（ ） 个指针域为空。 4 .设一棵哈夫曼树共有 n 个非叶结点，则该树有（ ）个叶结点。A . A . 4 B. C.赋值 A . n+l B. n n B . n+l C . n-l x保存被删结点的值，则执 3 C. 6 D. 12 D.连接 C. n-l D . n-2 D. 2n A. VWNNNN* CL 吼呢矶 二、填空题（每小题 2 分。共 20 分） 16. 在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是 （值域）（左指针）（右指针）。 17. 一棵二叉树中顺序编号为 i的结点，若它存在左、右孩子，贝 U 左、右孩

6、子编号分别为（2i、2i+l） 18. 串的两种最基本的存储方式是 （顺序存储）和（链式存储）。 19. - 棵有 2n-l个结点的二叉树，其每一个非叶结点的度数都为 2,则该树共有（n）个叶结点。 20. 对于一棵具有 n 个结点的二叉树，其相应的链式存储结构中共有（ n+1）个指针域为空。 21 （中序）遍历二叉排序树可得到一个有序序列。 22. 图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是（ 正确）的。 23. 二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种 说法是（不正确）的。（回答正确或不正确） 24. 对记录序列排序是指按记录

7、的某个关键字排序，记录序列按（ 主关键字）排序结果是唯一的。 25. 按某关键字对记录序列排序，若（ 关键字相等的记录）在排序前和排序后仍保持它们的前后关系， 则排序算法是稳定的，否则是不稳定的。 三、综合题（每小题 10 分。共 30 分） 26 .设查找表为（16 , 15, 20, 53, 64, 7）, （1） 用冒泡法对该表进行排序（要求升序排列） ，写出每一趟的排序过程，通常对 n 个元素进行冒泡排 序要进行多少趟冒泡？第 j趟要进行多少次元素间的比较？ （2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。 （要求以数据元素作为树结点） 27 . （1）设有查找表（

8、5 , 14, 2, 6, 18, 7, 4, 16, 3）,依次取表中数据，构造一棵二叉排序树。 说明如何由序列的二叉排序树得到相应序列的排序结果。 38 . （1）对给定权值 2, 1, 3, 3, 4, 5,构造哈夫曼树（要求每个结点的左子树根结点的权小于 等于右子树根结点的权）。（2）给出各权值的哈夫曼编码。 答 2, 001 I- OyQ 110 3i m 01 Si 10 四、程序填空IB鲫空2分共分) * iicxi NULL (3) (4 ) |j = p- ncxl (5)pf .12- ( I ) | E ci ( lil :lef t) (2 J P&fttGFd

9、erC 1 riizliO CO pnntf (* *BT-dala) Jl.tl 膜弊刊廿 L5 7 15腭就待；M 1! M 20 ? 5J44 15 16 ? KI 1CBIS3 44 7 15 1 2C SJ Si 四、程序填空题【每空 2 分。共 16 分） 3L 铤 It 性衰为 46.1QU4” 以下理中说.也蛹构如 It 的力 达世 立项 阿站左H t 山链 &中料切成中的帔蛔. define NULL 0 void rn n %. fZClJE： H* A f* s Lu data IO g. fiiflTR = 1 fii j a. Jiia4 i/ * d 呈A靖

10、-叔 * / */ *以上结束 rtssitre * p hencl i / * f) 为 T件棉 H ,市舞 Jlft 出 fit & * / (|j r i ii I f ( * % d n (4 30.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点)。voidPostorder( structBTreeNode* BT) 试卷代号：1252 中央广播电视大学2012-2013学年度第一学期 开放本科”期末考试 5. 以卜 ,町以 L Ik 仪山卷 4聂 rx wi

11、r *( i-next = i CX i- Ancm = -a rwx* 1X cj-a rweact5 ZUT. 饥 从一个校质街侧 为 的琏快中 !际一个，月】突 Ht x 俾# 戡删站点；的$ C# topto*-3*ri?xt * x top-j next i x- dntn io. 在:一个铤 LA中.愉姓 f和丁分为叭火:初队 E 拘公.则 JIM 藤：-个细晟的场坪为 y, r = ；* next f B, i r -next f C. ffrAnuxt* LXrAnKf/ n+ 蚀 gift.校，警啊 J 屈 ,州楂 g 耳二 nJ 能柚 Hl)列jy； t 、(进+ftrti

12、 仙 尸丁以女 初进才亍_ A. decs H Fi edctifl C- dwljn G* AIjcdle 乳-个 it应力 1 (KT村太,扣亍牛&找 X 寸僚*进行位找柝*怖山下女我成功 的平均比枝吹散为 t J - 26/10 15- 29/10 C 29/9 IX 31/10 】：妇件号辨志中-从未+1匡可邙列中依次坡出一元来勺匚抑普土列 H初照为当八中时无*进中亍 比皎匚假善比*次 tHt -燃足人 1_1畏匕*如 J fJ K配 J 为活暴(： - A, TJfPd 氏宜技插入 Q-折牛刷人 6 抵行悟* A. &-b| tu next = &- c M.

13、 nrx.t d t C2) (if(BT! =NULL)( (1) (2) (3) 儿 g 诃钮我 乱算法的时间食众度与 t Xzo /V丽使 Hi 曲 H 算初 L 一、 单项选择题（每小题 2 分，共 30 分） 1. 同一种逻辑结构（）。A.只能有唯一的存储结构 B. 可 以 有 不同的存储结构 C.只能表示某一种数据元素之间的关系 n 以上三种说法均不正确 2. 链表所具备的特点是（）。A 可以随机访问任一结点 B占用连续的存储空间 C 插入删除元素的操作不需要移动元素结点 D 可以通过下标对链表进行直接访问 3. 数据的物理结构（）。A 与数据的逻辑结构无关 B 仅 仅包括数据元素

14、的表示 C 只包括数据元素间关系的表示 n 包括数据元素的表示和关系的表示 4. 线性结构中数据元素的位置之间存在 （）的关系。 A-对一 B一对多 C 多对多 D.每一个元素都有一个直接前驱和一个直接后继 14. 设有一个 10 阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主存储到 一维数组 B中（数组下标从 1 开始），则矩阵中元素氏。在一维数组 B中的下标是.（）。 A . 33 B. 32 C. 85 D . 41 15. 在一个无向图中，所有顶点的度数之和等于边数的 （）倍。A3 & 2.5 C 1.5 D. 2 1 . B 2 . C 3 . D 4 . A

15、5. D6. C 7 . B 8 . C 9 . A 10 . C11. A 12 . B 13 . C 14 . A 15 . D 二、 填空题（每小题 2 分，共 24 分） 16. 栈和队列的操作特点分别是（ 后进先出）和（先进先出）。 17. 结构中的数据元素存在多对多的关系称为（ 网状）结构。 18. 根据数据元素间关系的不同特性，通常可分为集合、线性、 （树形）、（图形）、四类基本结构。 19. 要求在 n 个数据元素中找其中值最大的元素， 设基本操作为元素间的比较。 则比较的次数和算法的 时间复杂度分别为（n-1）和（O（n）。 20. 在一个单向链表中 p 所指结点之后插入一个

16、 s 所指向的结点时，应执行（s-next=s）和（p-next=s）的操作。 21 .在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、 （左指针）、（右指针）。 22. 一棵二叉树中顺序编号为 i 的结点，若它存在左、右孩子，贝 U 左右孩子的编号分别为（ 2i）、（2i+1） 23. 向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 （s-next=h）;和（n=s）。 24. 在一个链队中，设 f和 r分别为队头和队尾指针， 则插入 s 所指结点的操作为（r-next=s）和 r=s;（结 点的指针域为 next）。 25. 设有一棵深度为 4 的完全二叉树

17、，第四层上有 5 个结点，该树共有（12）个结点。（根所在结点为第 1 层） 26. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的（ 行下标）、（列下标） 和非零元素值三项信息。 27. 在对一组记录（55, 39, 97, 22, 16, 73, 65, 47, 88）进行直接插入排序时，当把第 7 个记录 65 插 入到有序表时，为寻找插入位置，需比较（ 3）次。 三、 综合题（每小题 10 分，共 30 分） 28. （1）以 2, 3, 4, 7, 8, 9 作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小 于等于右子树根结点的权），给出相应权重

18、值叶结点的哈夫曼编码。 （2）-棵哈夫曼树有 n 个叶结点，它一共有多少个结点？简述理由。 29. 一组记录的关键字序列为 （46, 79, 56, 38 , 40, 84） （1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果 （给出逐次交换元素的过程，要求 以升序排列） 。（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 30. 设查找表为（50, 60, 75, 85, 96, 98, 105, 110, 120, 130） （1） 说出进行折半查找成功查找到元素 120 需要进行多少次元素间的比较？ （2） 为了折半查找元素 95,经过多少次元素间

19、的比较才能确定不能查到？ （3） 画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点） 。 四、 程序填空题（每空 2 分，共 16 分） 11 ri. rHmmia 也，占 rt. 11 r* 、 r *占尽 ft勺 e n-v H* rAi 裾w * *占成I* 的旅 tu i 丛即 j Uu Ai 佻庆为 1 *.：，：，- . r * 免 nst w瞻 r ,空怖 mi 女* - r*4 1 ，crrci tcj-C ti r*4FJFZ * hmci * p v * | v inf i # ti ntnlUicC i-ilicoCC ZW FF： t h“q t n

20、 鼻：2 . jsa，”ujtt_fsiI_JILI” i/ * .d? y. -*i jsfti * / f r P C W _ _ ZLJLl 八 * MrHr JI % （4I， 喜 t|）l 4 I rvum（ biwirfe j | 以下W MME中序ig厌二又例此通月IT也:帕布普,旬由程序中空整警井f间舫四q A彩 rft*会甲和ricM fl配域 4 皇为字特墨LWT希向&母rdU. 心4 HTD 4（1 -Nlrt.IJE 。） 四 , （独 , gR tiiD a. ini L lie ?i oo I.叫 9i W 做 A】中用*#*|枷速株恤点（UK 耕哥审序眄

21、t，KtJ! JD.M #J*麻，邪.圈 物四* .如徉.54 尊，3肌随应.叫刷 枷,明，国，HE.的 四.理停璋此幢查I丹，排16# m 3 枚 (1)4 R A 4B 3 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 一、单项选择题（每小题 2 分。共 30 分） 1 .链表所具备的特点是（）。A.可以随机访问任一结点 B.占用连续的存储空间 C .插入删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问 2 .线性结构中数据元素的位置之间存在（）的关系。 A .一对一 B. 一对多 C .多对多 D 。每一个元素都有一个直接前驱和一个直接后继 3

22、 .算法的时间复杂度与（） 有关。7 A .所使用的计算机 B .与计算机的操作系统 C .与算法本身 D .与数据结构 4 .在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 P所指结点的直接后继, 现要删除 q 所指结点，可用的语句是 （）。 A . p=q-next B . p-next=q C . p-next=q-next D . q-next=NULL 5. 在一个链队中，假设 f和 r分别为队头和队尾指针，则删除一个结点的运算为 （）。 A. r=f-next B . r=r-next C . f=f 一 next ; D . f=r 一 next : 6

23、.元素 3, 6, 9 按顺序依次进栈，则该栈的不可能输出序列是 （）（ 进栈出栈可以交替进行）。 A . 9, 6, 3 B . 9, 3, 6 C . 6, 3, 9 D . 3, 9, 6 7 .设有一个 l0阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组 8 中（数组下标从 1 开始），则矩阵中元素氏，。在一维数组 B中的下标是（.）。 A . 33B. 32 C . 85 D . 41 8 .在 C 语言中，顺序存储长度为 3 的字符串，需要占用（） 个字节。 C . 6 D. 12 9 .一棵有 n 个结点采用链式存储的二叉树中，共有 （） 个指针域为

24、空。 A . n+1B. n C . n 一 1 D . n-2 10 .设一棵哈夫曼树共有 n 个叶结点，则该树有（） 个非叶结点。 A . nl B . n C . n+1 D. 2n 11 .在一个无向图中，所有顶点的度数之和等于边数的 （） 倍。 A . 3B. 2. 5 C . 1. 5 D. 2 12 .已知如图 1 所示的一个图，若从顶点 V。出发，按广度优先进行遍历，则可能得到的一种顶点序 |A. | B. 夹V, WV矶V C. C. VzVjVV.VrV Vr 13 .在有序表（2 , 4, 7, 14, 34, 43, 47, 64, 75, 80, 90, 97, 12

25、0）中，用折半查找法查找值 80 时，经（）次比较后查找成功。 A . 4 B . 2 C . 3 D . 5 14 .排序算法中，从未排序序列中依次取出元素与已排序序列 （初始为空）中的元素进行比较（要求比 较次数尽量少），然后将其放入已排序序列的正确位置的方法是 C .折半插人 D .选择排序 列为（） V, 15 .排序方法中，从尚未排序序列中挑选兀素， 并将其依次放入已排序序列 （初始为空）的一端的方法, 称为（）排序。 A .归并 B .插入 C .快速 D .选择 二、填空题（每小题 2 分。共 24 分） 1 结构中的数据元素存在多对多的关系称为结构。 2.要求在 n 个数据元素

26、中找其中值最大的元素，设基本操作为元素间的比较。则比较的 次数和算法的时间复杂度分别为 和 - 3 设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p 一 next= ,则 P所指结点为尾结点。 4 向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 s next=h ;和 - 5 在一个链队中，设 f和 r分别为队头和队尾指针，则插入 s 所指结点的操作为- 和 r=s ;（结点的指针域为 next） 6. 设有 n 阶对称矩阵 A,用数组 s 进行压缩存储，当 inext=NULL; head=(1) - ; 一一； for(i=1 ； idata=i ;

27、 p-next=NULL ; 在排序前和排序后仍保持它们的前后关系，则排序算法 else p-next2（4） - ; q 一 next2（5） - ; return（head） ; 2 .以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分 （树结构中，左、右指针域分 别为 left和 right，数据域 data 为字符型；BT指向根结点）。 void Postorder（struct BTreeNode*BT） if（BT!=NULL） - ； - ； - ； 试卷代号:1252 中央广播电视大学 2008-2009 学年度第一学期“开放本科 ”期末考试 数据结构（本）试题答案及

28、评分标准 （供参考） 一、 单项选择题（每小题 2 分，共 30 分） 1 . C 2 . A 3 . C 4 . C 5 . C 6 . B 7 . A 8 . A 9 . A 10 . A 11 . D 12 . C 13 . A 14 . C 15 . D 二、 填空题（每小题 2 分。共 24 分） 1- 图状（网状） 2 . n 一 1, 0（n） 3 . head 4 . H=s; 5 . r 一 next=S ; 6 . i（i 一 1） / 2+j 7 . 2i 和 2i+1 8 . n 9 .中序 10 . abdefeg 11 .不正确 12 .关键字相等的记录 三、综合题

29、（每小题 10 分。共 30 分） 1 . (1)初始序列 46, 79, 56, 38, 40, 84 40 , 79, 56, 38,回，84 40 ，回,56,38 , 79, 84 40 , 38, 56,围，79, 84 . 40 , 38,回，56, 79, 84 40 , 38, 46, 56, 79, 84 , 图 3 2. (1)原序列 16152053647 n 一 1 躺 n j次 71516205364 (3) 平均查找长度一(1*1+2*2+3*3) / 6-14/6 3. (1)不正确，二叉排序树要求其子树也是二又排序树。 图打 后续遍历 5, 6, 4, 9, 8

30、, 18, 20, 16, 7 四、程序填空题(每空 2 分。共 16 分) 1 . (1)P (2)q=P (3) (NODE*)malloc(sizeof(NODE) (4) q-next (5) p 2 . (1)Postorder(BT 一left) (2)Postorder(BT 一 right) (3)printf( c” , BT一data) 试卷代号：1010 中央广播电视大学 2007-2008 学年度第一学期“开放本科 期末考试 计算机专业 数据结构试题 2008 年 1 月 一、单项选择题。在括号内填写所选择的标号 (每小题 2 分。共 18 分) 1. 下面程序段的时间

31、复杂度为 ()。 for(int i=0 ; im ; i+) for(int j=0 ; jlink=S ; B. s 一 link=top 一 link ; top 一link=S ; C. S-link=top ; top S; D . s 一 link=top ; top top 一 link ; 6. 一棵具有 35 个结点的完全二叉树的高度为 （）。假定空树的高度为一 l。 A. 5 B . 6 C . 7 D . 8 7. 向具有 n 个结点的堆中插入一个新元素的时间复杂度为 （）。 A. O（1） B . 0（n） C . O（log 2n）D . O（nlog 2n） 8.

32、在一棵 AVL 树中，每个结点的平衡因子的取值范围是 （）。 A. l 1 B . 2 2 C . 1 2 D .。1 9. 一个有 n 个顶点和 n 条边的无向图一定是（） 的。 A.连通 B .不连通 C .无回路 D .有回路 有回路 二、填空题，在横线处填写合适的内容 （每小题 2 分，共 l4分） 1 .数据结构包括（）、存储结构和对数据的运算这三个方面。 2. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 （）存取的。 3. 将一个 n 阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一 维数组需要至少具有（）个元素。 4 .对于一棵具有

33、n 个结点的树，该树中所有结点的度数之和为 （）。 5 .在一棵高度为 3 的理想平衡二叉树中，最少含有 （）个结点，假定树根结点的高度为 0。 6 .假定对长度 n=50 的有序表进行折半搜索，贝 U 对应的判定树中最底层的结点数为 （）个。 7 .用邻接矩阵存储图，占用的存储空间与图中的 （）数有关。 三、判断题。在每小题前面打对号表示正确或打叉号表示错误 （每小题 2 分。共 14 分） （）1 .算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 （）2 .用字符数组存储长度为 n 的字符串，数组长度至少为 n+1。 （）3 .在用循环单链表表示的链式队列中，可以

34、不设队头指针，仅在链尾设置队尾指针。 （）4 .邻 接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。 （）5 .对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 （）6 .在索引 顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 （）7 .图中各个顶点的编 号是人为的，不是它本身固有的，因此可以根据需要进行改变。 四、运算题（每小题 6 分，共 30 分） 1 .假定一棵二叉树广义表表示为 a（b（c） , d（e, f）,分别写出对它进行中序、后序、按层遍历的结 果。 中序：后序：按层： 2 .一个一维数组 all2中存储着有序表（15 , 26,

35、34, 39, 45, 56, 58, 63, 74, 76, 80, 86）,根据 折半搜索所对应的判定树，写出该判定树中度为 1 的结点个数，并求出在等概率情况下进行成功搜索时的 平均搜索长度。 度为 l的结点个数：平均搜索长度： 3 .假定一个线性序列为（38 , 42, 55,15, 23, 44, 30, 74, 48, 26）,根据此线性序列中元素的排 列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结 点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点： 4 .已知一个

36、图的顶点集 V 和边集 G分别为：V=1 , 2, 3, 4, 5, 6; E=, , , , , , , , , ; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出： (1)从顶点 l出发进行深度优先搜索所得到的顶点序列； (2)9,N 点 1 出发进行广度优先搜索所得到的 顶点序列。 (1): (2): 5. 已知一个数据序列为(16 , 45, 27, 23, 41 , 15, 56, 64，请把它调整为一个最大堆。最大堆： 五、算法分析题(每小题 6 分。共 12 分) 1 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表

37、头指针。阅 读算法，在划有横线的上面填写合适的内容。 ListNode*Mergel(ListNode* . & pl , ListNode*&p2) ( ListNode*p=new ListNode , *f=p ; while(p1!=NULL & p2!=NULL) ( if(pl-datadata)( p-link=pl ； ; else(p-link=p2 ; p2=p2 一link ; if(pl!=NULL)p-link=pl ; else p 1ink=p2 ; pl=p2=NULL; 2 .已知二叉树中的结点类型 BinTreeNode定义为: st

38、ruct BinTreeNodeElemType data ; BinTreeNode*left , *right ; ; 其中 data 为结点值域，left和 right分别为指向左、右子女结点的指针域。根据下面算法的定义指 出其功能。算法中参数 BT指向一棵二叉树。 return f link BinTreeNode*BTreeSwopX(BinTreeNode*BT) if(BT= =NULL)return NULL ; else BinTreeNode*pt=new BinTreeNode ； pt 一 data BT 一 data ; pt 一 right BTreeSwopX(B

39、Tleft); pt 一 left=BTreeSwopX(BT-right) ; return pt 算法功能： 六、算法设计题(每小题 6 分，共 12 分) 1 .已知 f为单链表的表头指针，单链表中的结点结构为 (data , link),并假定每个结点的值均为大 于 0 的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数 值 0。 int Max(LinkNode*f) ; 2 .设 Q 是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明 写出从此队列中删除一个元素的算法。 /循环队列定义 struct CyclicQueue

40、ElemType elemEM ; / M 为已定义过的整型常量 int rear ; / rear指向队尾元素的后一个位置 int length : / length 指示队列中元素个数 5 /若队列非空则删除队头元素并由引用参数 x带回，同时返回 true ;否则若队列为空则返回 false bool DelCQueue(CyclicQueue Q , ElemType&x); 试卷代号：1010 中央广播电视大学 2007- 2008 学年度第一学期“开放本科期末考试 计算机专业 数据结构试题答案及评分标准 （供参考） 2008 年 1 月 一、 单项选择题，翟括号内填写所选择的

41、标号 （每小题 2 分，共 18 分） 1 . C 2 . C 3 . B 4 . B 5 . C6. A 7 . C 8 . A 9 . b 二、 填空题。在横线处填写合适内容 （每小题 2 分，共 14 分） 1 .逻辑结构 2 .下标（或顺序号）3 . n（n+1） /24. n 一 15. 86. 197.顶点 三、 判断题，在每小题前面打对号表示正确或打叉号表示错误 （毒小题 2 分。共 14 分） 1.错 2 .对 3 .对 4 .错 5 .对 6 .错 7 .对 7.对 四、运算题 （每小题 6 分， 共 30 分） 1 .中序: C, b, a, e, d, f 后序：C, b

42、, e, f, d, a 按层：a, b, d, C, e, f 2度为 1 的结点个数：5 平均搜索长度：37/12 3. 左子树为空的所有单支结点： 15 , 23, 42, 44 右子树为空的所有单支结点： 30 所有叶子结点：26, 48, 74 4. （1）1 , 2, 4, 5, 3, 6 / 3 分 （2）1 , 2, 3, 4, 5, 6 / 3 分 5. 最大堆：64 , 45, 56, 23, 41, 15, 27, 16 五、 算法分析题（每小题 6 分。共 12 分） 1 . pl2p1 link、p=p link /每空 3 分 2 .生成一棵新二叉树并返回树根指针，

43、该二叉树是已知二叉树 BT中所有结点的左、右 子树（或左、右孩子的值）交换的结果。 六、 算法设计题（每小题 6 分。共 12 分） 1. 评分标准：按注释酌情给分。 int Max（LinkNode*f） ( if(f= =NULL)return 0 if(f 一 link= =NULL)return f 一data ; int temp=Max(f-link) ; if(f 一 datatemp)return f 一 data ; else return temp ； 2. 评分标准：按注释酌情给分： bool DelCQueue(CyelieQueue Q , ElemType&

44、x) ( if(Q . 1ength=O)return false ; xQ elem(Q . rear Q 1ength-t-M) % M; Q. 1ength 一一； return true ； 试卷代号：1010 中央广播电视大学 2006-2007 学年度第二学期“开放本科 ”期末考试 计算机专业数据结构试题 2007 年 7 月 一、单项选择题。在括号内填写所选择的标号 (每小题 2 分。共 18 分) 1 .若需要利用形参直接访问实参，则应把形参变量说明为 () 参数。 A.指针 B .引用 C .传值 D .常值 2 .在二维数组中，每个数组元素同时处于 () 个向量中。 A.

45、O B . 1 C . 2 D. n 3 .已知单链表 A 长度为 m单链表 8 长度为 n,它们分别由表头指针所指向，若将 B整体连接到 A 的 末尾，其时间复杂度应为()。 A . O(1) B . O(m) C . O(n) D . O(m 十 n) 4 .假定一个链式队列的队头和队尾指针分别为 front和 rear ,则判断队空的条件为 A. 3, 2, 1 B. 2, 1, 3 向具有 n 个结点的二叉搜索树中插入一个结点的时间复杂度大致为 A. O(1) B . O(1og2n) C. 后根 D .层次 A. iront= =rear B .front!=NULL C. rear

46、! = NULL D .front= =NULL 5 .若让元素 l , 2, 3 依次进栈，则出栈次序不可能出现 （） 种情况。 C. 3, 1 , 2 D . 1, 3, 2 6.在一棵高度为 5（假定树根结点的高度为 0）的完全二叉树中, 所含结点个数至少等于 A. 16 B. 64 二、填空题。在横线处填写合适的内容 （每小题 2 分，共 14 分） 1.链表只适用于（ ） 查找。 2.设双向循环链表中每个结点的结构为 （data , llink , rlink），则结点*P的前驱结点的地 址为（ ） 3.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有 4.假定一棵

47、树的广义表表示为 a（b , c, d（e , f） , g（h），则结点 f的层数为（ 个结点。 假定树根结点 的层数为 0。 5.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的 继续搜索。 6.每次从第 i至第 n 个元素中顺序挑选出一个最小元素，把它交换到第 i个位置，此种排 序方法叫做（ ） 排序。 7 .快速排序在最坏情况下的时间复杂度为 （） 二、判断题，在每小题前面打对号表示正确或打叉号表示错误 （每小题 2 分。共 14 分） 7. C. O(n)D. O(nlog 2n) 8. 具有 n 个顶点的有向图最多可包含有 （） 条有向边。 C. 9. A.

48、A. n 1 B. n n(n 一 1) / 2 D . n(n 一 1) 先根 B .中根 遍历。 ()1 .数据的逻辑结构与数据元素本身的内容和形式无关。 ()2 .使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 ()3 .在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历 时具有相同的结果。 ()4 .能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 相同。 ()5 .邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 ()6 .在索 引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数

49、有关，而且与每一个子表 中的对象个数有关。 ()7 .向一棵 8 树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高 度减少 1。 四、运算题(每小题 6 分。共 30 分) 1 .假定一棵二叉树广义表表示为 a(b(c( , g) , d(e , f),分别写出对它进行先序、中序和后序遍历 的结果。 先序： 中序： 后序： 2 .有 7 个带权结点，其权值分别为 3,乙 8, 2, 6, 10, 14,试以它们为叶子结点生成一棵霍夫曼树， 求出该树的带权路径长度。 带权路径长度： 3 .已知图 G=(V, E),其中 V=a, b, c, d, e, E=(, , , , ,

50、, 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。 顶点： a b c d e 边结点数： 4. 已知一个 AOV 网的顶点集 V 和边集 G分别为： V=0, 1, 2, 3, 4, 5, 6, 7; E=, , , , , , , , , ; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。 拓扑序列： 5 .已知有一个数据表为 30 , 16, 20, 15, 38, 12, 44, 53, 46, 18, 26, 86,给出进行归并排序 的过程中每一趟排序后的数据表变化。 (o)3

51、 (4) 五、算法分析题(每小题 6 分。共 12 分) 1 .该算法功能为：从表头指针为 la 的、按值从小到大排列的有序链表中删除所有值相同的多余元素， 并释放被删结点的动态存储空间。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode * &la) ListNode*P , *q; if(1a= =NULL)return ； q=1a; p=la-link ; while(p) if(p-dataq-data)q=p ； p=p-link ； else q -link ； delete(p); p=； 2 .已知二叉树中的结点类型 Bi

52、nTreeNode定义为： struct BinTreeNodeElemType data ; BinTreeNode*left , *right ; ; 其中 data 为结点值域，left和 right分别为指向左、布子女结点的指针域。下面函数的功能是从二 叉树 BT中查找 值为 X 的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面 填写合适的内容。 BinTreeNode*BTF(BinTreeNode*BT , ElemType x) if(BT=NULL)NULL ; else( if(BT 一 data= =x) ; else( BinTreeNode*t ; if(t BTF(BT 一 left , x)return t : if(t=)return t ; return NULL ; 六、算法设计题(每小题 6 分，共 12 分) 1. Q 是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyelieQueue /循环队列定义 ( ElemType elemM ，/ M 为已定义过的整型常量 int rear ; / rear指向队尾元素的后一个位置 int length ; / length 指示队列中元素个数 ； bool E