6月数据结构自考试题及答案 .docx

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

1、精品名师归纳总结全国 2006 年 10 月高等训练自学考试数据结构试卷课程代码： 02331一、单项挑选题 本大题共 15 小题，每道题 2 分，共 30 分）在每道题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项或未选均无分。1数据结构是 ） A 一种数据类型B数据的储备结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是 ）A 辨别数据结构的合理性B评判算法的效率 C讨论算法中输入与输出的关系D鉴别算法的可读性3. 在线性表的以下运算中，不 转变数据元素之间结构关系的运算是）A 插入B 删除C排序D 定

2、位4. 如进栈序列为1， 2， 3，4， 5， 6，且进栈和出栈可以穿插进行，就可能显现的出栈序列为 的值为）A 15B 16C 17D 186二维数组A89 按行优先次序储备，如数组元素A23 的储备的址为1087 ， A47 的储备的址为1153，就数组元素A67的储备的址为 ）A 1207B 1209C 1211D 12137. 在按层次遍历二叉树的算法中，需要借助的帮助数据结构是）A 队列B 栈C线性表D 有序表8. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系）A 不肯定相同B 都相同可编辑资料 - - - 欢迎下载精品名师归纳总结C都不相同D 互为逆序9. 如采

3、纳孩子兄弟链表作为树的储备结构，就树的后序遍历应采纳二叉树的）A 层次遍历算法B 前序遍历算法C中序遍历算法D 后序遍历算法10如用邻接矩阵表示一个有向图，就其中每一列包含的1的个数为 ）A 图中每个顶点的入度C图中弧的条数B 图中每个顶点的出度D 图中连通重量的数目11图的邻接矩阵表示法适用于表示A 无向图）B 有向图C稠密图D 稀疏图12. 在对 n 个关键字进行直接挑选排序的过程中，每一趟都要从无序区选出最小关键字元素，就在进行第i趟排序之前，无序区中关键字元素的个数为）A iB i+1C n-iD n-i+113. 以下排序算法中，其时间复杂度和记录的初始排列无关的是）A 插入排序B

4、堆排序C快速排序D 冒泡排序14. 如有序表的关键字序列为b,c,d,e,f,g,q,r,s,t），就在二分查找关键字b 的过程中，先后进行比较的关键字依次为 ）A f,c,bB f,d,bC g,c,bD g,d,b15 如在文件中查询年龄在60 岁以上的男性及年龄在55 岁以上的女性的全部记录，就查询条件为）A 60OR 性别=“女”） OR55） B 60AND 性别 =“女”） OR55 ）C 60OR 性别 =“女”） AND55 ） D 60AND 性别 =“女”） AND55 ） 二、填空题 ，其含义是指算法的执行时间和 的数量级相同。17. 在一个长度为 n 的单链表 L 中，

5、删除链表中 *p 的前驱结点的时间复杂度为 。18. 假设为循环队列安排的向量空间为Q20 ，如队列的长度和队头指针值分别为13 和 17，就当前尾指针的值为。19. 设 s= I AM A ATHLETE ,t= GOOD ，就执行以下串操作序列之后得到的sub1 为。substr sub1,s,5,2。substrsub2,s,6,8。 strcpyt1,t 。可编辑资料 - - - 欢迎下载精品名师归纳总结strcatt1,sub2 。 strcatsub1,t1。20广义表的深度是指。21. 一棵含 999 个结点的完全二叉树的深度为 。22. 含 n 个顶点的无向连通图中至少含有 条

6、边。23. 对表长为 9000 的索引次序表进行分块查找，假设每一块的长度均为15，且以次序查找确定块，就在各记录的查找概率均相等的情形下，其查找胜利的平均查找长度为 。24如对关键字序列43 ， 02， 80， 48， 26， 57， 15， 73， 21， 24， 66）进行一趟增量为3 的希尔排序，就得到的结果为。25. ISAM 文件由主索引、和主文件组成。三、解答题 本大题共 4 小题，每道题 5 分，共 20 分）26. 某广义表的表头和表尾均为 ），画出该广义表的图形表示。27. 已知二叉树的先序序列和中序序列分别为HDACBGFE和 ADCBHFEG 。1）画出该二叉树。2）画

7、出与 1 ）求得的二叉树对应的森林。1）2）28. 已知带权图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点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已知用有序链表

8、储备整数集合的元素。阅读算法f30 ，并回答以下问题：1）写出执行f30a,b ）的返回值，其中a 和 b 分别为指向储备集合 2 ， 4， 5， 7，9， 12 和2 ， 4， 5，7， 9的链表的头指针。2）简述算法 f30 的功能。/LinkList是带有头结点的单链表/ha 和 hb 分别为指向储备两个有序整数集合的链表的头指针LinkList pa,pb 。pa=ha-next 。pb=hb-next 。whilepa & pb & pa-data=pb-data pa=pa-next 。pb=pb-next 。ifpa=NULL & pb=NULL return 1。else re

9、turn 0。12331. 已知稀疏矩阵采纳带行表的三元组表表示，其形式说明如下： #define MaxRow 100/ 稀疏矩阵的最大行数typedef struct int i,j,v 。/ 行号、列号、元素值TriTupleNode 。typedef structTriTupleNode dataMaxSize 。int RowTabMaxRow+1。/ 行表int m,n,t 。/矩阵的行数、列数和非零元个数可编辑资料 - - - 欢迎下载精品名师归纳总结RTriTupleTable 。以下算法 f31 的功能是，以行优先的次序输入稀疏矩阵的非零元行号、列号、元素值），建立稀疏矩阵

10、的带行表的三元组表储备结构。请在空缺处填入合适内容，使其成为一个完整的算法。 int i,k 。scanf %d %d %d ,&R-m,&R-n,&R-t。R-RowTab1=0 。k=1。 /k 指示当前输入的非零元的行号fori=0 。 。 i+ scanf %d %d %d , ， &R-datai.v 。whilekdatai.i。R-RowTabk=i 。32. 已知二叉树的储备结构为二叉链表，其类型定义如下： typedef struct NodeType DataType data。struct NodeType *lchild,*rchild。BinTNode,*BinTre

11、e。阅读算法 F32，并回答以下问题：1 对于如下列图的二叉树，画出执行算法f32 的结果。可编辑资料 - - - 欢迎下载精品名师归纳总结BinTree bt2 。ifbt1=NULL bt2=NULL 。else bt2=BinTNode *mallocsizeofBinTNode。bt2-data=bt1-data 。bt2-rchild=f32bt1-lchild。bt2-lchild=f32bt1-rchild。return bt2 。1233. 假设有向图采纳邻接表表示法，其定义如下： typedefstruct VertexNodeadjlistMaxVertexNum。intn

12、,e 。/ 图的当前顶点数和弧数 ALGraph 。/ 邻接表类型可编辑资料 - - - 欢迎下载精品名师归纳总结其中顶点表结点 VertexNode 结构为：vertexfirstedge可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结边表结点 EdgeNode 结构为：adjvexnext可编辑资料 - - - 欢迎下载精品名师归纳总结以下算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序。1 ）阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法。 int i,j,k,count=0 。int indegreeMaxV

13、ertexNum。EdgeNode *p 。/p 为指向边表结点的指针Queue Q。/Q 为队列FindIndegreeG, indegree 。 / 求各顶点的入度，并置于入度向量indegree InitQueue&Q 。fori=0 。i if.indegreeiEnQueue&Q,i。while.QueueEmpty&Q j= 。topoj=+count 。forp=G .adjlistj.firstedge 。p。p=-next k=p-adjvex 。if.-indegreek。ifcountprintf n 图 G 中存在有环路 。1）可编辑资料 - - - 欢迎下载精品名师归纳总结2） topo01234567可编辑资料 - - - 欢迎下载精品名师归纳总结五、算法设计题 本大题 10 分） 34假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct node DataType data。struct node *nextLinkNode, *LinkList。编写算法，从有序表A 中删除全部和有序表B 中元素相同的结点。7 / 7可编辑资料 - - - 欢迎下载