【学历类职业资格】数据结构自考题分类模拟1及答案解析.doc
《【学历类职业资格】数据结构自考题分类模拟1及答案解析.doc》由会员分享,可在线阅读,更多相关《【学历类职业资格】数据结构自考题分类模拟1及答案解析.doc(8页珍藏版)》请在麦多课文档分享上搜索。
1、数据结构自考题分类模拟 1及答案解析(总分:71.00,做题时间:90 分钟)一、单项选择题(总题数:10,分数:20.00)1.内部排序的方法有许多种, _ 方法是从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上。(分数:2.00)A.归并排序B.插入排序C.快速排序D.选择排序2.对长度为 n的关键字序列进行堆排序的空间复杂度为 _(分数:2.00)A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)3.在一棵完全二叉树的顺序存储方式中,若编号为 t的结点有右孩子,则此结点右孩子的编号为 _(分数:2.00)A.2tB.2t-1C.2t
2、+1D.t/24.排序的重要目的是为了以后对已排序的数据元素进行 _(分数:2.00)A.打印输出B.分类C.查找D.合并5.设有一个无向图 G=(V,E)和 G“=(V“,E“),如果 G“是 G的生成树,则下面不正确的说法是 _(分数:2.00)A.G“为 G的子图B.G“为 G的连通分量C.G“为 G的极小连通子图且 V“=VD.G“是 G的一个无环子图6.广义表()和()的长度分别是_和()的长度分别是_(分数:2.00)A.0;1B.1;1C.0;0D.1;07.含有 n个顶点和 e条边的有向图的邻接矩阵中,零元素的个数是_ A.e B.2e C.n2-2e D.n2-e(分数:2.
3、00)A.B.C.D.8.堆(Heap)是 _(分数:2.00)A.完全二叉树B.线性表C.二叉排序树D.平衡二叉树9.如图所示二叉树的中序遍历序列是 _ (分数:2.00)A.a b c d g e fB.d f e b a g cC.d b a e f c gD.d e f b a g c10.对于栈顶指针为 top的顺序栈 S,判断栈空的条件是_(分数:2.00)A.top=0B.top0C.top=StackSize-1D.top=StackSize二、填空题(总题数:8,分数:16.00)11.就文件而言,按用户的观点所确定的基本存储单元称为 1。按外设的观点所确定的基本存储单元称为
4、 2。 (分数:2.00)12.在 5阶 B-树中,每个结点至多含 4个关键字,除根结点之外,其他结点至少含 1 个关键字。 (分数:2.00)13.对表长为 9000的索引顺序表进行分块查找,假设每一块的长度均为 15,且以顺序查找确定块,则在各记录的查找概率均相等的情况下,其查找成功的平均查找长度为 1。 (分数:2.00)14.已知广义表 A=(a,b,c),(d,e,f),则运算 head(head(tail(tail(A)= 1。 (分数:2.00)15.在双向链表中,每个结点含有两个指针域,一个指向其 1 结点,另一个指向 2 结点。 (分数:2.00)16.N个顶点的连通图,至少
5、有 1 条边。 (分数:2.00)17.设有一元多项式 A(x)=7+3x+10x 30 -4X 100 +13x 101 ,用单链表给出 A(x)的存储表示为 1。 (分数:2.00)18.一组字符(a,b,c,d)在文中出现的次数分别为(7,6,3,5),字符“d“的哈夫曼编码的长度为 1。 (分数:2.00)三、解答题(总题数:2,分数:15.00)(1)画出对表长为 13的有序顺序表进行二分查找的判定树; (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99),写出在该序列中二分查找 37时所需进行的比较次数。(分数:10.00)_19.
6、图的邻接表的类型定义如下所示: #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作,可将邻接表的表头向量定义为链式结构,两种定义的存储表示
7、实例如下图所示,请写出重新定义的类型说明。 (分数:5.00)_四、算法阅读题(总题数:2,分数:10.00)阅读下列算法,并回答问题: void f32(int r, int n) Int i, j; for(i=2; in; i+) r0=ri; j=i-1; while(r0rj) rj+1=rj; j=j-1; rj+1=r0; (分数:5.00)(1).这是哪一种插入排序算法?该算法是否稳定?(分数:2.50)_(2).设置 r0的作用是什么?(分数:2.50)_20.求下面算法中变量 count的值:(假设 n为 2的乘幂,并且 n2) int Time int n count=0
8、;x=2; while(xn/2) x * =2;count+; return(count) (分数:5.00)_五、算法设计题(总题数:1,分数:10.00)21.设计一个双向起泡排序算法,即在排序过程中交替改变扫描方向。 (分数:10.00)_数据结构自考题分类模拟 1答案解析(总分:71.00,做题时间:90 分钟)一、单项选择题(总题数:10,分数:20.00)1.内部排序的方法有许多种, _ 方法是从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上。(分数:2.00)A.归并排序B.插入排序 C.快速排序D.选择排序解析:2.对长度为 n的关键字序
9、列进行堆排序的空间复杂度为 _(分数:2.00)A.O(log2n)B.O(1) C.O(n)D.O(n*log2n)解析:解析 由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地排序,辅助空间为 0(1),但它是不稳定的。3.在一棵完全二叉树的顺序存储方式中,若编号为 t的结点有右孩子,则此结点右孩子的编号为 _(分数:2.00)A.2tB.2t-1C.2t+1 D.t/2解析:4.排序的重要目的是为了以后对已排序的数据元素进行 _(分数:2.00)A.打印输出B.分类C.查找 D.合并解析:5.设有一个无向图 G=(V,E)和 G“=(V“,E“),如果 G“
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学历 职业资格 数据结构 考题 分类 模拟 答案 解析 DOC
