全国自考数据结构试题及答案解析doc.docx

1、全国自考数据结构试题及答案解析doc全国2018年10月高等教育自学考试 数据结构试题 课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项屮只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选 均无分。1.数据结构是（ ）A . 一种数据类型B数据的存储结构C. 一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2.算法分析的目的是（ ）A .辨别数据结构的合理性B 评价算法的效率C.研究算法中输入与输出的关系D .鉴别算法的可读性3.在线性表的下列运算中，不.改变数据元素之间结构关系的运算是（ ）

2、A 插入B 删除C.排序D定位4.若进栈序列为1,2, 3, 4, 5, 6,且进栈和出栈可以穿插进行，则可能出现的岀栈序列为（ ）A 3, 2, 6, 1, 4, 5 B 3, 4, 2, 1, 6, 5C . 1, 2, 5, 3, 4, 6 D 5, 6, 4, 2, 3, 15.设串 st= D ata S tmciuxes w ith Java ,s2二it ,则 了串定位函数 hdexfcl,s2)的值为( )A . 15 B 16C . 17 D 186.二维数组A按行优先顺序存储，若数组元素 A刃引的存储地址为1087, AE4JE7的存储地址为 1153,则数组元素AB昭的存

3、储地址为（ ）B . 1209A 1207D . 1213C . 12117.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）A 队列 B栈C 线性表 D .有序表8.在任意一-棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）A 不一定相同 B都相同C .都不相同 D互为逆序9.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ ）A 层次遍历算法 B前序遍历算法C 中序遍历算法 D后序遍历算法10.若用邻接矩阵表示一个有向图，则其屮每一列包含的 1的个数为（ ）B图中每个顶点的出度D .图中连通分量的数目）A 图中每个顶点的入度C.图中弧的条数11.图

4、的邻接矩阵表示法适用于表示（A 无向图C.稠密图D 稀疏图12.i趟排序在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第 之前，无序区中关键字元素的个数为（ ）A . i B HlC n-i D . n-Hl13.下列排序算法中，其时间复杂度和记录的初始排列无关的是（ ）A 插入排序 B 堆排序C 快速排序 D冒泡排序14.若有序表的关键字序列为（b,c,d,e,g,q,r,s,t）,则在二分查找关键字 b的过程屮，先后进行比较的关键字依次为（ ）A c,b B . d,bC g,c,b D g,d,b15.若在文件中查询年龄在 60岁以上的男性及年龄在

5、 55岁以上的女性的所有记录，则查询条件为（ ）A .（性别二“男”）0R （年龄60）0 R （性别二“女”）0R （年龄55）B .（性别二“男”）0R （年龄60）AND （性别二“女”）0R（年龄55 ）C .（性别二“男”）AND （年龄 60）0 R （性别二“女”）AND （年龄55 ）D .(性别二“男”)AND (年龄 60)AND (性别二“女”)AND (年龄 55)二、填空题(本大题共 10小题，每小题2分，共20分)请在每小题的空格屮填上正确答案。错填、不填均无分。16.称算法的时间复杂度为 0眦n),其含义是指算法的执行时间和 的数量级相同。17.在一个长度为n的单

6、琏表L中，删除链表中 即的前驱结点的时间复杂度为 。18.假设为循环队列分配的向量空间为 Q眩0,若队列的长度和队头指针值分别为 13和17,则当前尾指针的值为19.设s二IAM A ATHLETE ,匸GOOD “ ,则执行下列串操作序列之后得到的 subl为 。substr (subl,s,5,2)； substr(sub2,s,6,8); strcpystrcat(tl,sub2); strcat(subl,tl);20.广义表的深度是指 o21.-棵含999个结点的完全二叉树的深度为 o22.含n个顶点的无向连通图中至少含有 条边。23.对表长为9000的索引顺序表进行分块查找，假设每

7、一块的长度均为 15,且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 o24.若对关键字序列( 43, 02, 80, 48, 26, 57, 15, 73, 21, 24, 66)进行一趟增量为3的希尔排序，则得到的结果为 o25.EAM文件由主索引、 、 和主文件组成。三、解答题(本大题共 4小题，每小题5分，共20分)26.某广义表的表头和表尾均为( a,(b,c),画出该广义表的图形表示。27.已知二叉树的先序序列和屮序序列分别为 HDACBGFE和ADCBHFEG。(1)画出该二叉树；(2)画出与(1)求得的二叉树对应的森林。(1)(2)28.已知

8、带权图的邻接表如下所示，其屮边表结点的结构为:23依此邻接表从顶点C出发进行深度优先遍历。(1)画出由此得到的深度优先生成树；(2)写出遍历过程屮得到的从顶点C到其它各顶点的带权路径及其长度。(1)(2)29.从空树起，依次插入关键字 37, 50, 42, 18, 48, 12, 56, 30, 23,构造一棵二叉排序树。(1)画出该二叉排序树；(2) 画出从(1)所得树中删除关键字为 37的结点之后的二叉排序树。(1)(2)四、算法阅读题(本大题共 4小题，每小题5分，共20分)30.已知用有序链表存储整数集合的元素。阅读算法 C0,并回答下列问题：(1)写出执行CO ( a,b)的返回值

9、，其中a和b分别为指向存储集合 2 , 4, 5, 7, 9, 12和2 , 4, 5, 7, 9的链表的头指针；(2)简述算法30的功能；(3)写出算法30的时间复杂度。htCO (LinkListhaLinkListhb)ZthkList是带有头结点的单链表Zha和hb分别为指向存储两个有序整数集合的链表的头指针LhkListpa,pb;pa=ha-next;pb=hbnex t;while (pa & pb & 二二pbTdata) pa=panext;pb=pbnext;盼二二NULL & pb二二NULL)etum 1;else xetiiin 0;(1)(3)31.已知稀疏矩阵采用

10、带行表的三元组表表示，其形式说明如下：#defee M axR ow 100 佈疏矩阵的最大行数lypedef strnct iit ijv; 亍号、列号、元素值TriTupeN ode;typedef stmc tTriTupleN ode data |M axS ize;iitR owTab M axR ow + 1 上 亍表htm ,n,t； 力矩阵的行数、列数和非零元个数R TriTupleTable;,建立稀疏矩阵的带行(注：矩阵的行、列下标均从 1&R Hdata U.v);下列算法 伐1的功能是，以行优先的顺序输入稀疏矩阵的非零元(行号、列号、元素值)表的三元组表存储结构。请在空

11、缺处填入合适内容，使其成为一个完整的算法。起计)void Cl (R TriTupleTabh *R )htik;scanf(/z % d % d % d ，&Rm，&R-n,&R-t);R-RowTabl=0;k二1; 加指示当前输入的非零元的行号for(F0 : ； H+) scanf( % d % d % d , , (3) ,while(kdataf.i :R -R ow T ab k=i;32.已知二叉树的存储结构为二叉链表，其类型定义如下:iypedefstmctNodeType D ataT ype data ;structN odeType hhikijrchiJd ;B hT

12、N ode,桩 hTxee ;阅读算法F32,并回答下列问题：(1)对于如图所示的二叉树，画岀执行算法 仍2的结果;(2)简述算法62的功能。B hTiee C2 (B hTiee btl)B inTiee bl2;if (btl 二二 NULL)bt2 二 NULL;else bt2= (B hTN ode *)m alloc (sizeof hTN ode);b 12 - data 二 btl T data;bt2-rchiJd=f32(btl-child);bl2-Jchild=C2(btl-rchid);rctum bi2;(1)33.假设有向图采用邻接表表示法，其定义如下：lyped

13、ef stmc tV ertexN ode ad jlistlNl axV ertexN um ;tit n,e; 图的当前顶点数和弧数ALG mph; 於B接表类型其屮顶点表结点VertexN ode 结构为:vertexfirstedgead j/exnext边表结点EdgeN ode结构为:下列算法 伐3的功能是，对以邻接表表示的有向图进行拓扑排序。(1)阅读算法伐3,并在空缺处填入合适的内容，使其成为一个完 整的算法；(2)对于如图所示的邻接表，将执行 算法伐3后的topo结果填入给 定的数组中。void S3(ALG xaph G , tittopo )intijk,countF0;

14、tit hdegiee IM axV ertexN um ;EdgeN ode 即；h为指向边表结点的指针Q ueue Q ;加为队列Fhdlndegrce (& , hdegrce); 你各顶点的入度，并置于入度向量 hdegreehiiQ ueue &Q );for(i=O;inext) k=pad j/ex;if(!(ridegiee k) if(countG . n)prhtf(”巾图G中存在有环路)；(1)0 1 2 3 4 5 6 7(2 ) topo五、算法设计题（本大题 10分）34.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef stmc tn ode D ataType data;stmc tn ode ex tLhkN ode, *LhkList;编写算法，从有序表 A中删除所有和有序表 B屮元素相同的结点。