2021年4月自考02142数据结构导论试题及答案含评分标准.docx

《2021年4月自考02142数据结构导论试题及答案含评分标准.docx》由会员分享，可在线阅读，更多相关《2021年4月自考02142数据结构导论试题及答案含评分标准.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、绝密 考试结束前全国2021年4月高等教育自学考试数据结构导论试题课程代码:021421.请考生按规定用笔将所有试题的答案涂、写在答题纸上。 2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。选择题部分注意事项: 每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。 自考押题vx344647公众号顺通考试资料1.设某数据结构 A的二元组形式表示为 A

2、= (D,R),数据元素集合 D = 01,02,03,04,05,06, 07 ,08 ,09 ,数 据 元 素 之 间 的 关 系 R = r,r= , , , , , , , ,则数据结构 A属于 A.线性结构 B.树形结构 C .存储结构 D.图结构2 .算法指的是求解给定问题所需的A.计算机程序 B.查找方法 C .排序方法 D.处理步骤3.若长度为 n的线性表采用顺序存储结构,在其第i(1in+1)个位置插入一个新元素的算法的时间复杂度为A.O(1) B .O (log2n) C.O (n) D .O (n2)4 .在单链表指针为p的结点之后插入指针为s的结点,正确的指针操作是A

3、.p- next=s;s- next=p- next; B.s- next=p- next;p- next=s;C.p- next=s;p- next=s- next; D.p- next=s- next;p- next=s;5 .设数组datam 作为循环队列 SQ的存储空间,front为队头指针,rear为队尾指针,则执行 出队操作后其头指针front值为 A .SQ .front= SQ .front+1 B.SQ .front= (SQ .front+1)% (m -1) C .SQ .front= (SQ .front-1)% m D .SQ .front= (SQ .front+1

4、)% m6 .对稀疏矩阵使用三元组表示法的目的是 A.节省存储空间 B.降低时间复杂度C .便于矩阵运算实现 D.便于输入和输出浙02142#数据结构导论试题 第 1页(共4页)7 .操作系统中的进程调度使用先到先服务的方法,所采用的数据结构是A.最小堆 B.堆栈 C .队列 D.二叉树8 .假设通信电文使用的字符集为a ,b ,c,d ,e ,f,各字符在电文中出现的频率分别为34 ,5 ,12 ,23 ,8 ,18 ,利用构造 Huffman树对每个字符进行编码,则其中编码长度最长的字符是A .a,b B .a,d C .b,e D .e,f9 .一个具有1025个结点的二叉树的高度 h在

5、 A.10至1024之间 B.10至1025之间 C.11至1024之间 D.11至1025之间10 .由3个结点可以构造出多少种不同的二叉树?A.2种 B.3种 C.4种 D.5种11 .要使具有 n个顶点的有向图是强连通图,至少需要的边数是A.n-1 B.n C.n+1 D .2n12 .某散列表表长为40 ,散列函数为 H (key)= key%p, 则p通常选择A .36 B .37 C .38 D .3913 .若采用链地址法构造散列表,散列函数为 H (key)=key mod17,链表的链首指针构成一个指针数组,数组的下标范围为A .016 B.017 C.116 D.11714

6、 .取键值55为基准,执行一趟快速排序后可能得到的序列是 A .63,12,34,45,2755 41,72 B .45,34,12,4155 72,63,27C .41,12,34,45,2755 72,63 D .12,27,45,4155 34,63,7215 .设有 n个待排序的记录,则在堆排序中需要用作辅助存储空间的记录数是A .n2 B.n C .nlog2n D.1非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。二、填空题:本大题共13空,每空2分,共26分。16 .数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机

7、内的存储方式,以及定义在该组数据上的一组 。17 .数据元素由 组成。18 .下列程序段的时间复杂度为 。k=0;for(i= 1 ;i+) ;i =nk+;for(j= 1 ;j+) ;jnext 22 .栈顶 23 .n(n+1 )/224 .2k-1 25 .n0=n2+126 .强连通分量 27 .同义词 28.O (1)三、应用题:本大题共5小题,每小题6分,共30分。29 .共有5种可能的输出序列。(1分)它们分别是:ABC、(1分)BCA、(1分)BAC、(1分)CBA 、(1分)ACB。 (1分)30 .自考押题vx344647公众号顺通考试资料答30图(注:每棵子树根结点正确

8、得1分,全部答对得满分)31 .步骤1(2分) 答31-1图步骤2(1分) 答31-2图步骤3(1分) 步骤4(2分) 答31-3图 答31-4图数据结构导论试题答案及评分参考第 1页(共3页)其中步骤2也可以是:32 .答31-5图答32-1图 答32-2图 答32-3图 答32-4图 答32-5图 答32-6图(注:每个步骤1分)33 .直接插入排序:11 ,25 ,22 ,34 ,5 ,44 ,76 ,61 ,100 ,3 ,14 ,120 。 (3分) 冒泡排序:11,22,25,5,34,44,61,76,3,14,100,120。 (3分)四、算法设计题:本大题共2小题,每小题7分

9、,共14分。34 .int LengthLinkList (LinkList head ) ; (1分) Node *p=head; (1分) int cnt= 0while (p- next !=NULL) (1分); (2分) p=p-next; (1分) cnt+; (1分) return cnt数据结构导论试题答案及评分参考第 2页(共3页)35 .二叉链表结点结构如下: (2分)typedef struct btnode DataType data;struct btnode * lchild, * rchild;* BinTree;求二叉树的结点个数的算法如下:int node_ num (BinTree bt ) if (bt= =NULL) return 0; (2分)elsereturn node_ num (bt-lchild )+ node_ num (bt-rchild )+ 1; (3分)数据结构导论试题答案及评分参考第 3页(共3页)