首页 历年真题2010年1月自考数据结构导论试题

历年真题2010年1月自考数据结构导论试题

举报
开通vip

历年真题2010年1月自考数据结构导论试题全国2010年1月高等教育自学考试 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是( ) A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为( ) A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二...

历年真题2010年1月自考数据结构导论试题
全国2010年1月高等教育自学考试 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是( ) A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为( ) A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 表示时,空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中,所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示,若只设头指针,则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 中,要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序,在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)/2 8.对线性表进行二分查找时,要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储,且结点按关键字有序排列 D.以链接方式存储,且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算,其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时,该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述,错误的是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中,则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)%(m-1) C.rear=(rear+1)%m D.rear=(rear+1)%(m+1) 14.关于串的的叙述,不正确的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 15.对称矩阵A[N][N],A[1][1]为首元素,将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)/2]中,则任一上三角元素A[i][j]存于T[k]中,下标k为( ) A.i(i-1)/2+j B.j(j-1)/2+i C.i(j-i)/2+1 D.j(i-1)/2+l 二、填空题(本大题共13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) s=i+j+k; 17.在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为____________。 18.在单链表中,存储每个结点有两个域,一个是数据域,另一个是指针域,指针域指向该结点____________的。 19.在栈结构中,允许插入的一端称为____________。 20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动____________个元素。 21.一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素为____________。 22.循环队列被定义为结构类型,含有三个域:data、front和rear,则循环队列sq为空的条件是____________。 23.一个10阶对称矩阵A,采用行优先顺序压缩存储上三角元素,a00为第一个元素,其存储地址为0,每个元素占有1个存储地址空间,则a45的地址为____________。 24.对于一棵满二叉树,若有m个叶子,则树中结点数为____________。 25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。 26.在图中,第一个顶点和最后一个顶点相同的路径称为____________。 27.动态查找中两个元素X,Y存入同一个散列表时,X、Y键值相同,则这种情况称为____________。 28.堆排序需____________个记录大小的辅助存储空间。 三、应用题(本大题共5小题,每小题6分,共30分) 29.有一字符串的次序为-3*y+a/y!2,试利用栈将输出次序改变为3y*-ay!2/+,试写出进栈和退栈的操作步骤。(用push(x)表示x进栈,pop(x)表示x退栈) 30.已知一棵二叉树的先根遍历序列为ABCDEGHF,中根遍历序列为CBEDAGFH,画出该 二叉树。 31.题31图中二叉排序树的各结点的值为32~40,标出各结点的值。 题31图 32.下述矩阵表示一个无向网,画出该无向网,并构造出其最小生成树。 33.什么是堆?写出对应于序列(10,20,7,75,41,67,3,9,30,45)的初始堆(堆顶元素取最小值)。 四、算法设计题(本大题共2小题,每小题7分,共14分) 34.二叉树按二叉链表形式存储,编写一个算法判别给定的二叉树是否为完全二叉树。 35.试写出直接插入排序算法。
本文档为【历年真题2010年1月自考数据结构导论试题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_188950
暂无简介~
格式:doc
大小:38KB
软件:Word
页数:4
分类:工学
上传时间:2018-09-10
浏览量:5