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

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

一、单项选择题（每小题3分，共30分）
I.设主串为F&CDABcdEFdBc”.以下模式申能与主申成功匹配的是（ ）.
A・ dlk
11 BCd
C. DBC
2 .顺序表所具备的特点之一是（ ）.
A.可以随机访问任一结点
C插入删除操作不需要移动元素
D. Abe
K不用占用连技的存储空间
D.必须要有头指针
3.在一个伎队中,假役f和，分别为队头和队尾指什.P指向一个巳生成的结点•现要为该结
点的数据域赋值c并使结点入队的运算为P・
A. f—>urxt = p： f = p
C・ p—>ncx【= r$r = p
>dnta "c；p—>ncxt = NULLs 和（ 儿
B. r —>next~pir~p
D. p—>next=hf = p

4.在一个头指针为hmd的带头结点的单向循环链表中，p指向尼结点•要使该轻&成为
不带头结点的琪向伎表.可执行< >.
A« head — head— >next|p= NULL
R. hsd= head — >ncxt ；P — >next = head
C. head — >next = p — >next
D. hcad= hrnd->-next；p — >next = NULL
5. 元16■出序列建（ XiSft出
tt»m交铸现行）.
A. 212.214.216.218 H.
C 214.212.218.216 IX
6. 没右一个25阶的对鼻姬降A（W 个元素为■.・.采帽压■存WIKF三角 邮分以行序为主序4«1冒一!1敬川B中（故fl| F机从I并理隋中元素在
B中的下保星（
A. 10 R 9
C ? D. 8
7- ft - 9 SXH中•编9为19的拈史的以亲结盘的■序缀号为（ >.
A. 9 R 8
a 34 II 35
8.>方式，储.能透行折宇黄我.
A.美嫁字布序的
C fi!K
B. ♦序
a关健字布序的■序
9.1所示的一个图.若从厦点■出发•枝深度优无技京法进行遍历•则可能得到的一
#0（*序列为《 >•

K accbdfg
Il aedfcbg

A. at»ecdfg
G aebcfdg
10. 设哈夫。骨共有31个站jft.则故钙共有《 >个非叶子靖点•

卵卷人
二.堵女■（每小・224分）

H.靖构中.也《元It的位置之冏存在多对多的关系.
12. «W-个长度为20Mi6个元素.1»铃动元蜜的个 姑.
13. »«1 • char •[ ]--fh|（Uspw< a[6j中存故的是.
14. 序列4.2, 15. 13. 18.16.采川口港I•序U法.般一 IB» « ft
15. 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（ge<A«b.d.c）«d.e.（ （UJ）tk））的长度是•
22. q拆向P所扮结女的食接前驱结.株,现夏■除P所指靖右，
■可以用掾作 q ■ >MXL . •
三、综合题（每小题中每间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）按折半查找对 该表进行查找，求在等概率情况下查找成功的平均比较次数。
序u
1
2
3
4
5
6
7
8
9
10
序列
28
35
60
75
79
80
86
90
95
99
⑴ 以1.2,3 &7,8作为叶的点的权•构论-棵呛夫-树.
四、程序填空题（每空2分，共16分）
25. 设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是：（1）输出链表中各 结点中的数据城data. （2）把该单向链表改为以p作为尾指针的单向循环链表。（链表中结点的指针域为 next,数据域为data）。
# define NULL 0
void m«tn()
(NODE • head • • p i
p = / • p 为• /
do
^printl(MK<! \n*t(l) )>
(2>t
IwhikCp ~>nrxt | »(3)>i printf<-Sd\n* p—>dm)i
26. 以下程序是后序遍历_又树的法的程序.完成程序中空格怖分(树靖构中左.
右指针域分别为域dm为字符型，町揩向根结点).完成程序中空格簿分.
void pasturdcr (struct BTreeNode • BT)
<
if((n x
postordvrC BT — >left) i
(2)
(3) »
)
利用上述程序对卜'图所示二乂捌遍历的拈果为

试题答案及评分标准
(仅供参考)
一、单项选择超(每小题3分,共3。分)

6. B 7. A 8.D 9.D 10. B
二、填空0每小题2分，共24分)
11. 图状
12. 15
13. 字符p
16. 3
17. 19
】
19. 15
20. 中序
21. S
22. P—>neif
三、爆合■(每小■中■间6分，共30分)
2X(1)

(2) (1 + 2 • 2 卜3 ・ 1+4 • 3)/10^29/10
EL程序堵玄■（每空216分）
25. (1) p —>daui
(2) p«p —>next
(3) NULL

(2) pontorder(BT— >right)
(3) pnntf(*>oc**»BT—>dau)
(4)