2021国家开放大学电大本科《数据结构》期末试题及答案

1、2021国家开放大学电大本科数据结构期末试题及答案（试卷号：1252）一、单项选择题（每小题3分，共30分）1. 以下说法不正确的是（）。a. 线性表的链式存储结构不必占用连续的存储空间b. -种逻辑结构只能有唯一的存储结构c. 一种逻辑结构可以有不同的存储结构d. 线性表的顺序存储结构必须占用连续的存储空间2. 单向链表所具备的特点之一是（）。a. 可以随机访问表中任一结点b. 需要占用连续的存储空间c. 插入元素和删除元素的操作不需要移动元素d. 可以通过指向某元素的指针操作，直接访问到该结点的直接前驱结点3. 线性结构中数据元素的位置之间存在（）的关系。a. 多对多b. 一对多c. 一对

2、一d. 每一个元素都有一个直接前驱和一个直接后继在一个单向饶表中p和q分别是指向结点类型的指针.要删除p所指结点的百援后维结点，可执行（）.a. >ncxtip>nexrq >nextr q=pip=q>rwxtc. q=p >nrxl；p>ntxt = qd. q = p;p>next = q5 .设有带头纳点的旦头指针为head的非空的羊向也表，指针p折向其尾结点.要使该单向饨表成为不带头结点的单向循环锤表.则可利用下述语句shead=head->ncxt;ffi（）.a. p33 headb. p= nullc. p2>nexthea

3、dd. hcad=»p6：元素2（）.14.160.180按顺序依次进栈.则该找的不可能输出序列是（迎栈出枝可以交替进行）.a. 180.l60th.20b, 20,14.160,18()c. 180,160.20.14i). 14.20.180.1607 .设有一个15阶的对林加阵a华一个元素为5.）.采用压端存储的方式.将其下三角 部分以行序为卜:序存储到一雄数tfl h中（数坦下标从】井婿），则炬仰中元素hv.i在一雄散出 b中的下坏j8k ）.8. 设 棵4 n个叶纳点的二又树.度数为1的结点有4个.则成柯共有（个靖点.k 2n+3d. 2n + -1c2n4-29. 役根靖

4、点所在层为第-层，-棵具有5层的完全二叉树，感后一层有6个结点恻1安同感共有（）个拍点15已知加图1所示的一个图.若从顶点&出发,按深度优先搜京法进行遍历，则可能得k atrfebdgd. nrdfcbg到的一种t#点序列为（>-a.abecdlgc. aebcldg评卷人二.填空ih （每小题2分.共24分）11. 把数据存储到计算机中.并具体体现数据元素间的造料关系称为靖构.12. 设有一个长度为22的iffi序表，要jm除第8个元素需移动元震的个数为.13. 在一二叉何中.若编号为i的结点存在右孩f 则右孩孑的整序海号为14. 说一摞吩夫曼树共有18个非叶结点则该树慈共有

5、个结点15. 校元素的进,出栈次序是：后进.16. 在对10个记录的序列（8,36.19,7b,l1o.53.45.27.68迪行直接捅入措序时，当把第6个延承10抽入别&序衣时.为寸找隔人元素间需比较次7. n个元京进行1泡法检序通1t需要避打« i m9w泡，武中串i 48k他旌1要罐行次元k间的比较.低序列7.ll2s.3.b.6 iii t ftttfll-次h并后的m眼序列肥19. 中序iuffi »w <4 fs w ,个"序序列20. 广义a(hub.a)«f»e«(id)»k)的保fltjk _

6、 _21. _ 姑知中.敢据元素向存在对霉的关系.22. 字符申l mboijin|m.42b mbrf .m3-brifnngm.a 1 *"mcm小的是% »if tta三小ik中昭间6分,共m分）23. 设庄我&为x1231&67h0i"11甲列1116?4254361?183vi.1 _ 92123（d岫出切i述在也如tt行折半介枚me应的判定树也中靖盘用下抓5小）.（2）说明不成功食成元庶45隔鹭弗过多少次比枚？（3）求在牌慨骡* （1卜.成功有我的平均比较次也,，24. micl*的炸字中列为（37,67.43.25.27.32）.tf

7、t出柯用地抑序（坝仲元素h m 小无k）的方维债0的初的地（嘤求以兜金二乂 w«h£）对关峥亨序列（40.73.49.3l.3jm7果用快速序.帝山以第一个。字为分割无素.谜姓一次刻分i8的怕果.w »怦卷人四、牧序坝空（每空2分.共16分）25. 以卜袍ft在"o'到岳t1中.用折半台戏法作找美址字秒十k的记栗奁找成功 退抑域记米的f标，失败时返刖一1 .兜蛇但序中的空格.typcdcf wtrurtint keyi|n(h)e»int binary.srarch(n()dea9inf n<inl k)mt low mid>

8、;htghilow 0>(bwhile(_k>w v = high)eid= if(nmi(t. keyr =k>retum(3)else iftalmidj. keyvk)low" mid+ 1 ；eue(4)c5)26. 以下程序是作序遍历二叉徊的递归算法的程序，先成程序中空格部分(时结构中左.右指针域分别为left和right.数据域血s为字符asm 指向根站点)，void preorder (struct bt reenode * bt) ikbt! =null)(cl)(2 prcordcr( bt > right)ji利用上述程序对下图进行遍妨.结果是(3)试题答案及评分标准小朋3分,共3u分)1.b6-ci. a9.c5a c1 e i)二ji堂小.2分.共24分)11. 存储(物理12. 1113.21 114.3715.先出16.418. 1.7.2.4.3.5»6,819. 二又挥序树20.321. 树形22. 点三、嫁合18(每小!中每问6分.共30分)23. (1)4次(3)平均食找长度一u+22 + 34 + l - 0/11=324. (1)25,27.32,67,373(2>33.31.to.w>