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

精品名师归纳总结全国 2006 年 10 月高等训练自学考试数据结构试卷课程代码： 02331一、单项挑选题 <本大题共 15 小题，每道题 2 分，共 30 分）在每道题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项或未选均无分。1数据结构是 <） A 一种数据类型B数据的储备结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是 <）A 辨别数据结构的合理性B评判算法的效率 C讨论算法中输入与输出的关系D鉴别算法的可读性3. 在线性表的以下运算中，不 转变数据元素之间结构关系的运算是<）A 插入B 删除C排序D 定位4. 如进栈序列为1， 2， 3，4， 5， 6，且进栈和出栈可以穿插进行，就可能显现的出栈序列为<）A 3，2， 6， 1， 4， 5B 3， 4， 2，1， 6， 5C 1，2， 5， 3，4， 6D 5， 6， 4， 2， 3，15设串sl= Data Structures with Java ,s2=it ，就子串定位函数indexs1,s2> 的值为<）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. 如采纳孩子兄弟链表作为树的储备结构，就树的后序遍历应采纳二叉树的<）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 堆排序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 <性别 =“男”） OR 年龄 > 60>OR< 性别=“女”） OR<年龄 >55） B <性别=“男”） OR 年龄 > 60>AND< 性别 =“女”） OR<年龄 >55 ）C <性别=“男”） AND 年龄 > 60>OR< 性别 =“女”） AND< 年龄 >55 ） D <性别 =“男”） AND 年龄 > 60>AND< 性别 =“女”） AND< 年龄 >55 ） 二、填空题 <本大题共 10 小题，每道题2 分，共 20 分）请在每道题的空格中填上正确答案。错填、不填均无分。16. 称算法的时间复杂度为Ofn>> ，其含义是指算法的执行时间和 的数量级相同。17. 在一个长度为 n 的单链表 L 中，删除链表中 *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 个顶点的无向连通图中至少含有 条边。23. 对表长为 9000 的索引次序表进行分块查找，假设每一块的长度均为15，且以次序查找确定块，就在各记录的查找概率均相等的情形下，其查找胜利的平均查找长度为 。24如对关键字序列<43 ， 02， 80， 48， 26， 57， 15， 73， 21， 24， 66）进行一趟增量为3 的希尔排序，就得到的结果为。25. ISAM 文件由主索引、和主文件组成。三、解答题 <本大题共 4 小题，每道题 5 分，共 20 分）26. 某广义表的表头和表尾均为<a,b,c> ），画出该广义表的图形表示。27. 已知二叉树的先序序列和中序序列分别为HDACBGFE和 ADCBHFEG 。<1）画出该二叉树。<2）画出与 <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已知用有序链表储备整数集合的元素。阅读算法f30 ，并回答以下问题：<1）写出执行f30<a,b ）的返回值，其中a 和 b 分别为指向储备集合 2 ， 4， 5， 7，9， 12 和2 ， 4， 5，7， 9的链表的头指针。<2）简述算法 f30 的功能。<3）写出算法 f30 的时间复杂度。int f30LinkList ha,LinkList hb>/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 return 0。1>2>3>31. 已知稀疏矩阵采纳带行表的三元组表表示，其形式说明如下： #define MaxRow 100/ 稀疏矩阵的最大行数typedef struct int i,j,v 。/ 行号、列号、元素值TriTupleNode 。typedef structTriTupleNode dataMaxSize 。int RowTabMaxRow+1。/ 行表int m,n,t 。/矩阵的行数、列数和非零元个数可编辑资料 - - - 欢迎下载精品名师归纳总结RTriTupleTable 。以下算法 f31 的功能是，以行优先的次序输入稀疏矩阵的非零元<行号、列号、元素值），建立稀疏矩阵 的带行表的三元组表储备结构。请在空缺处填入合适内容，使其成为一个完整的算法。<注：矩阵的行、列下标均从 1 起计） void f31RTriTupleTable *R> 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> 。whilek<R->datai.i>。R->RowTabk=i 。32. 已知二叉树的储备结构为二叉链表，其类型定义如下： typedef struct NodeType DataType data。struct NodeType *lchild,*rchild。BinTNode,*BinTree。阅读算法 F32，并回答以下问题：1> 对于如下列图的二叉树，画出执行算法f32 的结果。可编辑资料 - - - 欢迎下载精品名师归纳总结<2 ）简述算法 f32 的功能。BinTree f32BinTree bt1>BinTree bt2 。ifbt1=NULL> bt2=NULL 。else bt2=BinTNode *>mallocsizeofBinTNode>>。bt2->data=bt1->data 。bt2->rchild=f32bt1->lchild>。bt2->lchild=f32bt1->rchild>。return bt2 。1>2>33. 假设有向图采纳邻接表表示法，其定义如下： typedefstruct VertexNodeadjlistMaxVertexNum。intn,e 。/ 图的当前顶点数和弧数 ALGraph 。/ 邻接表类型可编辑资料 - - - 欢迎下载精品名师归纳总结其中顶点表结点 VertexNode 结构为：vertexfirstedge可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结边表结点 EdgeNode 结构为：adjvexnext可编辑资料 - - - 欢迎下载精品名师归纳总结以下算法 f33 的功能是，对以邻接表表示的有向图进行拓扑排序。<1 ）阅读算法 f33，并在空缺处填入合适的内容，使其成为一个完整的算法。<2 ）对于如下列图的邻接表，将执行算法 f33 后的 topo 结果填入给定的数组中。可编辑资料 - - - 欢迎下载精品名师归纳总结void f33ALGraph G , int topo > int i,j,k,count=0 。int indegreeMaxVertexNum。EdgeNode *p 。/p 为指向边表结点的指针Queue Q。/Q 为队列FindIndegreeG, indegree> 。 / 求各顶点的入度，并置于入度向量indegree InitQueue&Q> 。fori=0 。i<G.n。 i+> if.indegreei>EnQueue&Q,i>。while.QueueEmpty&Q>> j= 。topoj=+count 。forp=G .adjlistj.firstedge 。p。p=->next> k=p->adjvex 。if.-indegreek>>。ifcount<G . n>printf n 图 G 中存在有环路 >。<1）可编辑资料 - - - 欢迎下载精品名师归纳总结<2） topo01234567可编辑资料 - - - 欢迎下载精品名师归纳总结五、算法设计题 <本大题 10 分） 34假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct node DataType data。struct node *nextLinkNode, *LinkList。编写算法，从有序表A 中删除全部和有序表B 中元素相同的结点。7 / 7可编辑资料 - - - 欢迎下载