2021国家开放大学电大本科《数据结构》期末试题及答案(试卷号：1252).docx

2021国家开放大学电大本科数据结构期末试题及答案（试卷号：1252）一、单项选择题（每小题3分，共30分）I.设主串为F&CDABcdEFdBc”.以下模式申能与主申成功匹配的是（）.A dlk11 BCdC. DBC2 .顺序表所具备的特点之一是（）.A.可以随机访问任一结点C插入删除操作不需要移动元素D. AbeK不用占用连技的存储空间D.必须要有头指针3.在一个伎队中,假役f和，分别为队头和队尾指什.P指向一个巳生成的结点现要为该结点的数据域赋值c并使结点入队的运算为PA. furxt = p： f = pC pncx【= r$r = pdnta c；pncxt = NULLs 和（ 儿B. r nextpirpD. pnext=hf = p4.在一个头指针为hmd的带头结点的单向循环链表中，p指向尼结点要使该轻&成为不带头结点的琪向伎表.可执行.A head head next|p= NULLR. hsd= head ncxt ；P next = headC. head next = p nextD. hcad= hrnd-next；p next = NULL5. 元16出序列建（XiSft出ttm交铸现行）.A. 212.214.216.218H. C 214.212.218.216IX 6. 没右一个25阶的对鼻姬降A（W 个元素为.采帽压存WIKF三角 邮分以行序为主序41冒一!1敬川B中（故fl| F机从I并理隋中元素在B中的下保星（A. 10R9C ?D.87- ft - 9 SXH中编9为19的拈史的以亲结盘的序缀号为（.A. 9R8a 34II358.方式，储.能透行折宇黄我.A.美嫁字布序的C fi!KB. 序a关健字布序的序9.1所示的一个图.若从厦点出发枝深度优无技京法进行遍历则可能得到的一#0（*序列为K accbdfgIl aedfcbgA. atecdfgG aebcfdg10. 设哈夫。骨共有31个站jft.则故钙共有个非叶子靖点卵卷人二.堵女（每小224分）H.靖构中.也元It的位置之冏存在多对多的关系.12. W-个长度为20Mi6个元素.1铃动元蜜的个 姑.13. 1 char -fh|（Uspw a6j中存故的是.14. 序列4.2, 15. 13. 18.16.采川口港I序U法.般一 IB ft15. W 19个元席的序列用!flfillfitiH7 IBWHU迸行次元腐倒的比较.16. 对一组ft!兼（41.25.93,20。2.78.，】.89）进行直撞插入祷序由小品大排序）.当招郦7个蛆媾拓捅人希序我.为，报殖入位需比牧 次.17. 设有一棒跺ar为5s层上有，个雄点.该村共有 个结点（IS所在靖株为第I M）18. */f pl -DEADFG.P2- WDEAFDF*.P3 WDEAI）FABWP4 *DEAFEW.四个申中豪大的是.19. 一株有A个叶结右的*夫厦村,踞该树共有 个靖点20. 谄历二又措序RSJffl到一个有序序列.ZL 广jtS（geMXL . 三、综合题（每小题中每间6分，共30分）23. （1）设有数据集合（0, 39, 17, 83111, 14, 65, 13, 91, 102, 49）,依次取集合中各数据构造一棵二叉排 序树。（2） 一组记录的关键字序列为（6, 9, 7 ,4,5,8）,利用堆排序（堆顶元素是最小元素）的方法建立初始 堆。（要求用完全二叉树表示）24. （1）如下为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树。（2）按折半查找对 该表进行查找，求在等概率情况下查找成功的平均比较次数。序u12345678910序列28356075798086909599 以1.2,3 &7,8作为叶的点的权构论-棵呛夫-树.四、程序填空题（每空2分，共16分）25. 设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是：（1）输出链表中各 结点中的数据城data. （2）把该单向链表改为以p作为尾指针的单向循环链表。（链表中结点的指针域为 next,数据域为data）。# define NULL 0void mtn()(NODE head p ip =/ p 为 /doprintl(MK(2tIwhikCp nrxt | (3)i printfdm)i26. 以下程序是后序遍历_又树的法的程序.完成程序中空格怖分(树靖构中左.右指针域分别为域dm为字符型，町揩向根结点).完成程序中空格簿分.void pasturdcr (struct BTreeNode BT)left) i(2)(3) )利用上述程序对卜图所示二乂捌遍历的拈果为 试题答案及评分标准(仅供参考)一、单项选择超(每小题3分,共3。分)6. B7. A8.D9.D10. B二、填空0每小题2分，共24分)11. 图状12. 1513. 字符p16. 317. 19】19. 1520. 中序21. S22. Pneif三、爆合(每小中间6分，共30分)2X(1)(2) (1 + 2 2 卜3 1+4 3)/1029/10EL程序堵玄（每空216分）25. (1) p daui(2) pp next(3) NULL(2) pontorder(BT right)(3) pnntf(*oc*BTdau)(4)