1、试卷代号：1252国家开放大学2021年春季学期期末统 一 考试数据结构(本) 试题答案及评分标准(供参考)2021年7月一、单项选择题(每小题3分，共45分)1.D 2.D 3.D 4.C 5.C6.B 7.C 8.B 9.D 10.D11.C 12.C 13.D 14.B 15.C二、判断题(每小题2分，共30分)16. 17.X 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.X 28. 29. 30. 三、综合应用及程序设计题(每小题5分，共25分)31.C. 或 p=p-next(3 分) B. 或 p!=NULL(2 分) 32.B. 或1215530
2、1833.(1)D.(2)B. 或234.B. 或 i+;(2 分)B. 或 ai.key=k(3 分)35. (1)B. 或37,24,12,30,53,45,96(3分)(2)B. 或1(2分)(1252号)数据结构(本)答案第1页(共1页)密 封 不 要 答 题O一号名站 )O-试卷代号：1252座位号 国家开放大学2021年春季学期期末统 一考试数据结构(本) 试题2021年7月题号一二三总 分分数得 分评卷人一 、单项选择题(把合适的选项编号填写在括号内。每小题3分，共45分)1. 下面程序段的时间复杂度是( )。for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0
3、;for(k=1;knext=s;s-next=p-nextB. p-next=s-nextC. p=s-nextD. s-next=p-next;p-next=s(1252号)数据结构(本)试题第1页(共6页)4. 在一个单链表中，p、q分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句( )。A. p=q-next B. p-next=qC. p-next=q-next D. q-next=NULL5. 若让元素1,2,3依次进栈，则出栈顺序不可能为( )。A. 3,2,1 B.2,1,3C. 3,1,2 D. 1,3,26. 表达式 a*(
4、b+c)-d 的后缀表达式是( )。A. abcd*+- B. abc+*d-C. abc*+d- D. 一 + * abcd7. 判断顺序栈 s 满(元素个数最多n 个)的条件是( )。A. s-top=0 B. s-top!=0C. s-top=n- 1 D. s-top!=n- 18. 串的长度是指( )。A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数9. 广义表的(a,(d,a,b),h,(e,(i,j),k) 深度是( )。A. 6 B. 10C. 8 D. 410. 在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子
5、的顺序编号为( )。A. 18 B. 16C. 15 D. 1711. 在一棵二叉树上，第5层的结点数最多为( )。A. 8 B. 15C. 16 D. 3212. 一个具有n 个顶点的无向完全图包含( )条边。A. n(n- 1) B. n(n+1)C. n(n- 1)/2 D. n(n+1)/2(1252号)数据结构(本)试题第2页(共6页)密 封 内 答 题得 分评卷人得 分三、综合应用及程序设计题(每小题5分，共25分)13. 对于一个具有 n 个顶点和e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为( )。A. n B. eC. 2n D. 2e14. 对于一个线性
6、表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( )。A. 以顺序存储方式B. 以链接存储方式C. 以索引存储方式D. 以散列存储方式15. 从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为( )。A. 插入排序 B. 交换排序C. 选择排序 D. 归并排序二、判断题(根据叙述正确与否在其后面的括号内打对号“ ”或打叉 号“”。每小题2分，共30分)16. 数据的逻辑结构与数据元素本身的内容和形式无关。( )17. 通常可以把一本含有不同章节的书的目录结构抽象成线性结构。( )18. 要在一个单向链表中删除 p 所指向的结点，已知q 指向
7、p 所指结点的直接前驱结点，若链表中结点的指针域为 next,则可执行 q-next= p-next。( )19. 要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为 next,头指针为 head,尾指针为 p,则可执行 head=head-next; p-next=head; 。( )20. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。( )21. 递归定义的数据结构通常用递归算法来实现对它的操作。( )22. 队列的特性是先进后出。( )23. 用字符数组存储长度为 n 的字符串，数组长度至少为n+1。( )24. 一
8、个广义表的表头总是一个广义表。( )25. 若树的度为2时，该树为二叉树。( )(1252号)数据结构(本)试题第3页(共6页)26. 深度为5的二叉树最多有31个结点。( )27. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。( )28. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。( )29. 理想情况下，哈希表查找等概率查找成功的时间复杂度是O(1)。( )30.n 个元素进行冒泡法排序，通常第j 趟冒泡要进行 n-j 次元素间的比较。( )评卷人31. 设线性表以不带头结点的单向链表存储，链表头指针为 head。 以下程序的功能是输出链表中各结
9、点中的数据域 data,完成程序中空格部分。#define NULL Oyoid main()NODE * head,*p;p=head;/p 为工作指针*/doprintf(“%dn”,p-data); ; while( ); (3分)B.p=head-nextD.head=head-nextA.head=p-nextC.p=p-next (2分)B.p!=NULLD.p=headA.p=NULLC.p!=head(1252号)数据结构(本)试题第4页(共6页)密 封 线 内 不 要 答 题32. 写出下列程序执行后的结果SeqQueue Q;InitQueue(Q);int a4=5,8,
10、12,15;for(int i=0;i4;i+)InQueue(Q,ai);InQueue(Q,OutQueue(Q);InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(! QueueEmpty(Q)printf(“%d”,OutQueue(Q);执行后的输出结果为： A.58121530 B.121553018C.812153018 D.12155183033. 设查找表为：序号12345678序列412181937556577(1)画出对上述查找表进行折半查找所对应的判定树是( )。(3分)A.C.B.D.(1252号)数据结构(本)试题第5页(共
11、6页)(2)用折半查找在该查找表成功查找到元素55需要经过( )次比较。(2分)A.1 B. 2C. 3 D. 434. 顺序查找算法如下，完成程序中空格部分。int search (NODE a,int n, int k)/ * 在ao,a1an-1 中查找关键字等于k 的记录，查找成功返回记录的下标，失败时 返 回 - 1 * / int i=0;while (in&ai.key!=k) if( return i;else return - 1; (2分)A.k+; B.i+;C. n+; D. a+; (3分)A. ai.key=nB. ai. key=kC. an.key=kD. an.key=i35. 设数据序列为：53,30,37,12,45,24,96(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是( )。(3分)A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96C. 12,24,30,37,45,53,96 D.30,24,12,37,45,96,53(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key)=key mod 13,则散列地址为1的链中有( )个记录。(2分)A.0 B. 1C. 2 D. 3(1252号)数据结构(本)试题第6页(共6页)
