欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > DOC文档下载
    分享到微信 分享到微博 分享到QQ空间

    【学历类职业资格】数据结构导论自考题模拟16及答案解析.doc

    • 资源ID:1375629       资源大小:76.50KB        全文页数:10页
    • 资源格式: DOC        下载积分:5000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要5000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    【学历类职业资格】数据结构导论自考题模拟16及答案解析.doc

    1、数据结构导论自考题模拟 16 及答案解析(总分:100.00,做题时间:90 分钟)一、单项选择题(总题数:15,分数:30.00)1.将现实生活中的数据转化为计算机所能表示的形式,其转化过程依次为_(分数:2.00)A.机外表示、存储结构、逻辑结构B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.逻辑结构、存储结构、机外表示2.下列关于线性表的基本操作中,属于加工型的操作是_(分数:2.00)A.初始化、插入、删除操作B.初始化、求表长度、插入操作C.求表长度、读元素、定位操作D.定位、插入、删除操作3.若在长度为 n 的顺序表中插入一个结点,则其结点的移动次数_(分数:2

    2、.00)A.最少为 1,最多为 nB.最少为 0,最多为 nC.最少为 0,最多为 n+1D.最少为 1,最多为 n+14.循环队列的队满条件为_(分数:2.00)A.(CQ.rear+1)%maxsize=CQ.frontB.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeD.CQ.rear=CQ.front5.顺序栈 S 中 top 为栈顶指针,指向栈顶元素所在的位置,elem 为存放栈的数组,则元素 e 进栈操作的主要语句为_(分数:2.00)A.elemtop=e;s.top=s.top+1

    3、;B.elemtop+1=e;s.top=s.top+1;C.top=s.top+1;s.elemtop+1=e;D.top=s.top+1;s.elemtop=e;6.设一个栈的输入序列是 a,b,c,d,则所得到的输出序列(输入过程中允许出栈)不可能出现的是_(分数:2.00)A.a,b,c,dB.c,d,a,bC.d,c,b,aD.a,b,d,c7.若二叉树(如下图所示)采用二叉链表存储结构,要交换其所有分支结点左右子树的位置,最合适的遍历方法是_ (分数:2.00)A.先序遍历B.中序遍历C.后序遍历D.按层次遍历8.除根结点外,树上每个结点_(分数:2.00)A.可有一个孩子、任意多

    4、个双亲B.可有任意多个孩子、任意多个双亲C.可有任意多个孩子、一个双亲D.只有一个孩子、一个双亲9.设有二维数组 (分数:2.00)A.B.C.D.10.从 V 1 出发,对下图按广度优先搜索遍历,则可能得到的一种顶点序列为_ (分数:2.00)A.V1V2V3V4V5V6B.V1V3V6V4V5V2C.V1V5V2V3V6V4D.V1V2V3V5V6V411.设有无向图 G=(V,E)和 G“=(V“,E“),如果 G“为 G 的生成树,则下面说法不正确的是_(分数:2.00)A.G“为 G 的连通分量B.G“为 G 的子图C.G“为 G 的极小连通子图且 V“=VD.G“是 G 的无环子图

    5、12.设图的邻接链表如下图所示,则该图的边的数目是_ (分数:2.00)A.4B.5C.10D.2013.采用二分查找法,若当前取得的中间位置 MID 的元素值小于被查找值,则表明待查元素可能在表的后半部分,下次查找的起始位置通常应_(分数:2.00)A.从 MID/2 位置开始B.从 MID 位置开始C.从 MID+1 位置开始D.从 MID-1 位置开始14.排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是_(分数:2.00)A.插入排序B.快速排序C.冒泡排序D.选择排序15.若对序列(25,91,23,53,1 6,34,69,39,22)进行一趟排序后所得到的结果为(2

    6、2,16,23,25,53,34,69,39,91),则该排序可能使用的方法是_(分数:2.00)A.插入排序B.冒泡排序C.快速排序D.选择排序二、填空题(总题数:13,分数:26.00)16.在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为 1。 (分数:2.00)17.设有指针 head 指向不带表头结点的单链表,用 next 表示结点的一个链域,指针 q 指向与链表中结点同类型的一个新结点。现要将指针 q 指向的结点插入表中,使之成为第一个结点,则所需的操作为“q-next=head;”和“ 1”。 (分数:2.00)18.对顺序表执行删除操作,其删除算法的平均

    7、时间复杂性为 1。 (分数:2.00)19.在具有 n 个单元且采用顺序存储的循环队列中,队满时共有 1 个元素。 (分数:2.00)20.在循环队列中,存储空间为 0(n-1),设队头指针 front 指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么队满标志为 front=(rear+1)%n,队空标志为 1。 (分数:2.00)21.设有二维数组 int M1020,每个元素(整数)占 2 个存储单元,数组的起始地址为 2000,元素 M610的存储位置为 1,M820的存储位置为 2。 (分数:2.00)22.若用后序遍历法遍历下图所示的二叉树,其输出序列为 1。 (分数:2.00

    8、)23.对于一棵具有 m 个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为 1 个,其中 2个用于链接孩子结点。 (分数:2.00)24.一个具有 20 个顶点的完全无向图中有 1 条边。 (分数:2.00)25.对于具有 n 个元素的数据序列,采用二叉排序树查找,其平均查找长度为 1。 (分数:2.00)26.采用折半查找方法进行查找的数据序列应为 1 且 2。 (分数:2.00)27.对 20 个元素进行冒泡排序时,第一趟排序的比较次数为 1。 (分数:2.00)28.冒泡排序最好的时间复杂度为 1,平均时间复杂度为 2,是一种 3 的排序算法。 (分数:2.00)三、应用题

    9、(总题数:5,分数:30.00)29.二叉树如下图所示,分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。 (分数:6.00)30.如下图所示,输入元素为 A,B,C,在栈的输出端得到一个输出序列 ABC,试写出在栈的输入端三个可能的输入序列。 (分数:6.00)31.已知连通网的邻接矩阵 (分数:6.00)32.已知一组键值序列(30,45,35,42,53,60,34,22),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 (分数:6.00)33.试写出下图的拓扑序列。 (分数:6.00)四、算法设计题(总题数:2,分数:14.00)34.现二叉树用二叉链表表示,试编写一算

    10、法求解一棵二叉树的叶子总数(可采用递归算法描述)。 (分数:7.00)_35.设某单链表中存在多个结点,其数据值均为 D,试编写一算法统计该类结点的个数。 (分数:7.00)_数据结构导论自考题模拟 16 答案解析(总分:100.00,做题时间:90 分钟)一、单项选择题(总题数:15,分数:30.00)1.将现实生活中的数据转化为计算机所能表示的形式,其转化过程依次为_(分数:2.00)A.机外表示、存储结构、逻辑结构B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构 D.逻辑结构、存储结构、机外表示解析:考点 实际数据转化到计算机所能表示的形式的过程 解析 实际数据转化到计算

    11、机所能表示的形式的转化过程为机外表示、逻辑结构、存储结构。2.下列关于线性表的基本操作中,属于加工型的操作是_(分数:2.00)A.初始化、插入、删除操作 B.初始化、求表长度、插入操作C.求表长度、读元素、定位操作D.定位、插入、删除操作解析:考点 线性表的基本操作 解析 线性表的基本操作中,属于加工型的操作是初始化、插入、删除操作。3.若在长度为 n 的顺序表中插入一个结点,则其结点的移动次数_(分数:2.00)A.最少为 1,最多为 nB.最少为 0,最多为 n C.最少为 0,最多为 n+1D.最少为 1,最多为 n+1解析:考点 顺序表的插入操作 解析 顺序表的插入需要移动原结点,在

    12、长度为 n 的顺序表中插入一个结点,最少时即插在尾部,无须移动结点;当需插入到最前面时,需要移动 n 个结点。4.循环队列的队满条件为_(分数:2.00)A.(CQ.rear+1)%maxsize=CQ.front B.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeD.CQ.rear=CQ.front解析:考点 循环队列队满的条件 解析 循环队列队满的条件(CQ.rear+1)%maxsize=CQ.front。5.顺序栈 S 中 top 为栈顶指针,指向栈顶元素所在的位置,elem 为存放栈的数

    13、组,则元素 e 进栈操作的主要语句为_(分数:2.00)A.elemtop=e;s.top=s.top+1;B.elemtop+1=e;s.top=s.top+1;C.top=s.top+1;s.elemtop+1=e;D.top=s.top+1;s.elemtop=e; 解析:考点 栈的存取时指针的修改 解析 栈的存取时指针的修改。6.设一个栈的输入序列是 a,b,c,d,则所得到的输出序列(输入过程中允许出栈)不可能出现的是_(分数:2.00)A.a,b,c,dB.c,d,a,b C.d,c,b,aD.a,b,d,c解析:考点 元素的进栈操作 解析 元素的进栈操作。7.若二叉树(如下图所示

    14、)采用二叉链表存储结构,要交换其所有分支结点左右子树的位置,最合适的遍历方法是_ (分数:2.00)A.先序遍历 B.中序遍历C.后序遍历D.按层次遍历解析:考点 二叉树的先、中、后序遍历算法 解析 二叉树的先序遍历用递归方法完成,第一步将根结点的左右子树交换,第二步在左子树中递归调用交换函数,第三步在右子树中递归调用交换函数。因此,采用先序遍历的方法最合适。8.除根结点外,树上每个结点_(分数:2.00)A.可有一个孩子、任意多个双亲B.可有任意多个孩子、任意多个双亲C.可有任意多个孩子、一个双亲 D.只有一个孩子、一个双亲解析:考点 本题主要考查的是树的结点间关系 解析 除根结点外,树上每

    15、个结点可有任意多个孩子、一个双亲。9.设有二维数组 (分数:2.00)A.B. C.D.解析:考点 总结根据矩阵存储数据的规律 解析 总结根据矩阵存储数据的规律,对角线上的元素第i,i个元素的元素值为(i+2)(i+1)/2。10.从 V 1 出发,对下图按广度优先搜索遍历,则可能得到的一种顶点序列为_ (分数:2.00)A.V1V2V3V4V5V6B.V1V3V6V4V5V2C.V1V5V2V3V6V4D.V1V2V3V5V6V4 解析:考点 图的广度优先遍历 解析 图的广度优先遍历算法。11.设有无向图 G=(V,E)和 G“=(V“,E“),如果 G“为 G 的生成树,则下面说法不正确的

    16、是_(分数:2.00)A.G“为 G 的连通分量 B.G“为 G 的子图C.G“为 G 的极小连通子图且 V“=VD.G“是 G 的无环子图解析:考点 无向图 解析 一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图,但不一定含有全部的边,也就是不满足连通分量的定义。因此不能说 G“为 G 的连通分量。12.设图的邻接链表如下图所示,则该图的边的数目是_ (分数:2.00)A.4B.5 C.10D.20解析:考点 图邻接表表示时,边数的求取 解析 图邻接表表示时边的条数=(邻接表结点个数)/2。13.采用二分查找法,若当前取得的中间位置 MID 的元素值小于被查找值,则表明待查元素

    17、可能在表的后半部分,下次查找的起始位置通常应_(分数:2.00)A.从 MID/2 位置开始B.从 MID 位置开始C.从 MID+1 位置开始 D.从 MID-1 位置开始解析:考点 二分查找算法 解析 二分查找算法,由题意可知,当判定在后半部分时,应该将 MID+1 作为起始位置,再进行二分查找。14.排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是_(分数:2.00)A.插入排序 B.快速排序C.冒泡排序D.选择排序解析:考点 插入排序算法 解析 插入排序算法,第一趟排序后,任一元素都不能确定其最终位置。15.若对序列(25,91,23,53,1 6,34,69,39,22

    18、)进行一趟排序后所得到的结果为(22,16,23,25,53,34,69,39,91),则该排序可能使用的方法是_(分数:2.00)A.插入排序B.冒泡排序C.快速排序 D.选择排序解析:考点 排序算法 解析 快速排序算法的步骤。二、填空题(总题数:13,分数:26.00)16.在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为 1。 (分数:2.00)解析:图形结构 考点 图形结构的定义 解析 在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为图形结构。17.设有指针 head 指向不带表头结点的单链表,用 next 表示结点的一个链域,指针 q

    19、指向与链表中结点同类型的一个新结点。现要将指针 q 指向的结点插入表中,使之成为第一个结点,则所需的操作为“q-next=head;”和“ 1”。 (分数:2.00)解析:head=p 考点 单链表元素插入操作的指针修改 解析 将指针 p 指向的结点插入表中,使之成为第一个结点,则所需的操作为“pNext=head;”和“head=p”。18.对顺序表执行删除操作,其删除算法的平均时间复杂性为 1。 (分数:2.00)解析:O(n-1)/2 考点 顺序表执行删除操作的时间复杂度 解析 对顺序表执行删除操作,其删除算法的平均时间复杂性为 O(n-1)/2。19.在具有 n 个单元且采用顺序存储的

    20、循环队列中,队满时共有 1 个元素。 (分数:2.00)解析:n-1 考点 循环队列的元素存储 解析 在具有 n 个单元且采用顺序存储的循环队列中,队满时共有 n-1 个元素。20.在循环队列中,存储空间为 0(n-1),设队头指针 front 指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么队满标志为 front=(rear+1)%n,队空标志为 1。 (分数:2.00)解析:rear=front 考点 循环队列的队空标志 解析 循环队列的队空标志为 rear=front。21.设有二维数组 int M1020,每个元素(整数)占 2 个存储单元,数组的起始地址为 2000,元素 M6

    21、10的存储位置为 1,M820的存储位置为 2。 (分数:2.00)解析:2260 2360 考点 二维数组存储位置的计算 解析 对于 m*n 的二维数组,根据存储地址计算公式 Loc(i,j)=Loc(0,0)+(n*i+j)*size;Loc(6,10)=2000+(206+10)2=2260;Loc(8,20)=2000+(208+20)2=2360。22.若用后序遍历法遍历下图所示的二叉树,其输出序列为 1。 (分数:2.00)解析:DBFHGECA 考点 后序遍历算法 解析 二叉树的后序遍历算法遍历顺序是:左子树、右子树、根结点。23.对于一棵具有 m 个结点的二叉树,当进行链接存储

    22、时,其二叉链表中的指针域的总数为 1 个,其中 2个用于链接孩子结点。 (分数:2.00)解析:2m m-1 考点 本题主要考查的二叉树的二叉链表存储 解析 二叉树中有 m 个结点,用二叉链表表示则有 2m 个指针域;由于只有一个根结点,所以相对于相应的父结点,有 m-1 个孩子结点,即有 m-1 个指针域用于链接孩子结点。24.一个具有 20 个顶点的完全无向图中有 1 条边。 (分数:2.00)解析:190 考点 无向完全图的定义 解析 个具有 n 个顶点的完全无向图中有有 n(n-1)/2 条边,所以对于 20 个顶点的无向完全图共有20(20-1)/2=190。25.对于具有 n 个元

    23、素的数据序列,采用二叉排序树查找,其平均查找长度为 1。 (分数:2.00)解析:1+log 2 n 考点 二叉排序树的平均查找长度 解析 采用二叉排序树查找,其平均查找长度 1+log 2 n。26.采用折半查找方法进行查找的数据序列应为 1 且 2。 (分数:2.00)解析:顺序存储 有序 考点 折半查找方法对数据序列的要求 解析 采用折半查找方法进行查找的数据序列应为顺序存储且有序。27.对 20 个元素进行冒泡排序时,第一趟排序的比较次数为 1。 (分数:2.00)解析:19 考点 冒泡排序算法 解析 对包含 20 个元素进行冒泡排序,第一趟排序的比较次数是 20-1=19。28.冒泡

    24、排序最好的时间复杂度为 1,平均时间复杂度为 2,是一种 3 的排序算法。 (分数:2.00)解析:O(n) O(n 2 ) 稳定 考点 冒泡排序最好情况下的比较次数 解析 冒泡排序最好的时间复杂度为 O(n 2 ),平均时间复杂度为 O(n 2 ),是一种稳定的排序算法。三、应用题(总题数:5,分数:30.00)29.二叉树如下图所示,分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。 (分数:6.00)解析:先序遍历:ABDEFC。 中序遍历:BEFDAC。 后序遍历:FEDBCA。 考点 二叉树的先序、中序、后序遍历算法30.如下图所示,输入元素为 A,B,C,在栈的输出端得到一个输

    25、出序列 ABC,试写出在栈的输入端三个可能的输入序列。 (分数:6.00)解析:ABC、ACB、BAC、CBA、CAB,写出任意 3 个序列即可。考点 栈的存取规则:先进后出31.已知连通网的邻接矩阵 (分数:6.00)解析:联通网和最小生成树分别见下图。 联通网32.已知一组键值序列(30,45,35,42,53,60,34,22),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 (分数:6.00)解析:初始 30 45 35 42 53 60 34 22 i=2 30 45 35 42 53 60 34 22 i=3 30 35 45 42 53 60 34 22 i=4 30

    26、 35 42 45 53 60 34 22 i=5 30 35 42 45 53 60 34 22 i=6 30 35 42 45 53 60 34 22 i=7 30 34 35 42 45 53 60 22 i=8 22 30 34 35 42 45 53 60 考点 直接插入排序算法33.试写出下图的拓扑序列。 (分数:6.00)解析:有以下 3 个拓扑序列: v 1 v 3 v 2 v 5 v 6 v 4 v 1 v 3 v 6 v 2 v 5 v 4 v 3 v 6 v 1 v 2 v 5 v 4 考点 拓扑排序的处理四、算法设计题(总题数:2,分数:14.00)34.现二叉树用二叉

    27、链表表示,试编写一算法求解一棵二叉树的叶子总数(可采用递归算法描述)。 (分数:7.00)_正确答案:()解析:void countleaf(bitreptr t,int * count) if(t!=NULL) if(t-lchild=NULL) countleaf(t-lchild,count); countleaf(t-rchild,count); 35.设某单链表中存在多个结点,其数据值均为 D,试编写一算法统计该类结点的个数。 (分数:7.00)_正确答案:()解析:int count_lklist(lklist head) p=head; j=0 while(p-next!=NULL) if p-data=D j+; /*j 增加 1*/ p=p-next; returu(j)


    注意事项

    本文(【学历类职业资格】数据结构导论自考题模拟16及答案解析.doc)为本站会员(bonesoil321)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开