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

    【学历类职业资格】数据结构真题2013年1月及答案解析.doc

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

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

    【学历类职业资格】数据结构真题2013年1月及答案解析.doc

    1、数据结构真题 2013 年 1 月及答案解析(总分:85.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.数据的逻辑结构可以分为_ A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性结构 D.简单结构和构造结构(分数:2.00)A.B.C.D.2.线性表是一个有限序列,组成线性表的基本单位是_ A.数据项 B.数据元素 C.数据域 D.字符(分数:2.00)A.B.C.D.3.栈中有 a、b 和 c 三个元素,a 是栈底元素,c 是栈顶元素,元素 d 等待进栈,则不可能的出栈序列是_ A.dcba B.cbda C.cadb D.cdba

    2、(分数:2.00)A.B.C.D.4.稀疏矩阵的三元组表是_ A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列表存储结构(分数:2.00)A.B.C.D.5.已知广义表 G,head(G)与 tail(G)的深度均为 6,则 G 的深度是_ A.5 B.6 C.7 D.8(分数:2.00)A.B.C.D.6.下列编码集合中,属于前缀编码的一组是_ A.11,10,001,101,0001 B.00,010,0110,1000 C.11,01,001,0101,0001 D.0,10,110,1011(分数:2.00)A.B.C.D.7.如下图所示二叉树的中序序列为_(分数:2.0

    3、0)A.B.C.D.8.有向图中所有顶点入度之和与所有顶点出度之和的比是 A.1/2 B.1 C.2 D.4(分数:2.00)A.B.C.D.9.含有 n 个顶点和 e 条边的有向图的邻接矩阵中,零元素的个数是_ A.e B.2e C.n2-2e D.n2-e(分数:2.00)A.B.C.D.10.n 个顶点的无向连通图,其生成树的边数为_ A.n-1 B.n C.n+1 D.nlog2n(分数:2.00)A.B.C.D.11.用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序,第一趟排序需进行交换的次数为_ A.2 B.3 C.4 D.5(分数:2.00)A.B.

    4、C.D.12.对序列(8,13,26,55,29,44)从小到大进行基数排序,第一趟排序的结果是_ A.(13,44,55,26,8,29) B.(13,26,55,44,8,29) C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)(分数:2.00)A.B.C.D.13.采用分块查找时,要求数据_ A.块内有序 B.分块有序 C.分块无序 D.每块中数据个数必须相同(分数:2.00)A.B.C.D.14.下列关于散列函数的说法正确的是_ A.散列函数越复杂越好 B.散列函数越简单越好 C.用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下,散列函数越简

    5、单越好(分数:2.00)A.B.C.D.15.下列关于 m 阶 B 树的叙述中,错误的是_ A.每个结点至多有 m 棵子树 B.每个结点至多有 m-1 个关键字 C.所有的叶结点均在同一层上 D.根结点至少有 m/2 棵子树(分数:2.00)A.B.C.D.二、B填空题/B(总题数:10,分数:20.00)16.算法的时间复杂度与实现时采用的程序设计语言_。(分数:2.00)填空项 1:_17.在长度为 n 的顺序表的第 i(1in)个元素之后插入一个元素时,需向后移动_个元素。(分数:2.00)填空项 1:_18.设循环队列存放在向量 data0m-1中,在出队操作后,队头指针 front

    6、变化为_。(分数:2.00)填空项 1:_19.树的前序遍历序列等同于该树对应二叉树的_遍历序列。(分数:2.00)填空项 1:_20.一个 10090 的整型稀疏矩阵有 10 个非零元素,设每个整型数占 2 个字节,则用三元组表存储该矩阵时,所需的字节数是_。(分数:2.00)填空项 1:_21.当用二叉链表作为 n 个结点的二叉树的存储结构时,空指针域的个数是_。(分数:2.00)填空项 1:_22.采用邻接表表示 n 个顶点的有向图时,若表结点的个数为 m,则该有向图的边数为_。(分数:2.00)填空项 1:_23.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的

    7、算法是_。(分数:2.00)填空项 1:_24.在 16 个记录的有序顺序表中进行二分查找,最大比较次数是_。(分数:2.00)填空项 1:_25.在排序算法中,若排序前后具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是_的。(分数:2.00)填空项 1:_三、B解答题/B(总题数:1,分数:5.00)判别以下序列是否为堆,若不是,将其调整为大根堆,并画出大根堆。(分数:5.00)(1).(1,5,7,20,18,8,10,40)(分数:2.50)_(2).(18,9,5,8,4,17,21,6)(分数:2.50)_四、B算法阅读题/B(总题数:2,分数:20.00)单链表类型定

    8、义如下:typedef struet nodeDataType data; struct node *next; ListNode; typedef ListNode *LinkList; 阅读下列算法,并回答问题:void f30(LinklList head, DataType x) /head 是带头结点的非空单链表的头指针ListNode *p, *q; p=head; while(p-next-next)p=p-next; q=(ListNode*)malloc(sizeof(ListNode); q-data=x; q-next=p-next; p-next=q; (分数:5.00

    9、)(1).该算法的功能是什么?(分数:2.50)_(2).若单链表的长度为 n,算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?(分数:2.50)_阅读下列算法(假设栈的操作函数都已定义),并回答问题:void f31_ SeqStaek S; char x, y; x=c; y=k; Push( Push( Push( x=Pop( Push( Push( X=Pop( Push( while(!StackEmpty( putchar(y);putchar(x);(分数:15.00)(1).自底向上写出执行 while 语句之前栈 S 中的元素序列。(分数:3.75)_(2).写

    10、出该函数的最后输出结果。(分数:3.75)_(3).下列算法的功能是在中序线索树中查找结点*p 的前趋,填上适当内容使算法完整。 typedef enum Link, Thread PointerTag; /枚举值 Link 和 Thread 分别为 0 和 1 typedef struct node DataType data; PointerTag ltag, rtag; Struct node *lchild, *rchild; BinThrNode; BinThrNode*f32(BinThrNode *p) /在中序线索树中找结点*p 的中序前趋,设 p 非空 BinThrNode

    11、*q; if(p-ltag=Thread)_; else q=p-lchild; while(q-rtag=Link)_; return q; (分数:3.75)_(4).分析下列排序算法中语句 1 和语句 2 的频度以及此算法的时间复杂度,并指出该算法是属于哪一种排序方法。 void f33(int a, int n) int i, j, k, t; for(i=0; in; i+) /语句 1 j=i; for (k=j+1; k=n; k+) if(akaj)j=k; /语句 2 t=ai; ai=aj; aj=t; (分数:3.75)_五、B算法设计题/B(总题数:1,分数:10.00

    12、)26.二叉排序树的类型定义如下: typedef struct node int data; struct node *lehild, *rchild; *BSTree; 编写递归算法从小到大输出二叉排序树 T 中所有 data 域值大于 m 且小于 n 的数据。 函数原型为 void f34(BSTree T, int m, int n)(分数:10.00)_数据结构真题 2013 年 1 月答案解析(总分:85.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.数据的逻辑结构可以分为_ A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线

    13、性结构 D.简单结构和构造结构(分数:2.00)A.B.C. D.解析:考点 数据的逻辑结构包含的内容 解析 数据的逻辑结构可以分为线性结构和非线性结构。2.线性表是一个有限序列,组成线性表的基本单位是_ A.数据项 B.数据元素 C.数据域 D.字符(分数:2.00)A.B. C.D.解析:考点 本题考查的数据表的基本单位 解析 线性表是一个有限序列,组成线性表的基本单位是数据元素。3.栈中有 a、b 和 c 三个元素,a 是栈底元素,c 是栈顶元素,元素 d 等待进栈,则不可能的出栈序列是_ A.dcba B.cbda C.cadb D.cdba(分数:2.00)A.B.C. D.解析:考

    14、点 栈的操作 解析 根据栈的操作原则,不可能的出栈序列是 cadb。4.稀疏矩阵的三元组表是_ A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列表存储结构(分数:2.00)A. B.C.D.解析:考点 稀疏矩阵的三元组表的存储结构 解析 稀疏矩阵的三元组表是顺序存储结构。5.已知广义表 G,head(G)与 tail(G)的深度均为 6,则 G 的深度是_ A.5 B.6 C.7 D.8(分数:2.00)A.B.C. D.解析:考点 广义表深度的计算 解析 当表头、表尾的深度相等时,广义表的深度为表头深度加 1。6.下列编码集合中,属于前缀编码的一组是_ A.11,10,001,

    15、101,0001 B.00,010,0110,1000 C.11,01,001,0101,0001 D.0,10,110,1011(分数:2.00)A.B. C.D.解析:考点 前缀编码的判断 解析 根据前缀编码的概念,选项 B 可判断为前缀编码。7.如下图所示二叉树的中序序列为_(分数:2.00)A. B.C.D.解析:考点 二叉树的中序遍历 解析 根据二叉树中序遍历的方法,可得到所给二叉树的中序遍历为ACDB。8.有向图中所有顶点入度之和与所有顶点出度之和的比是 A.1/2 B.1 C.2 D.4(分数:2.00)A.B. C.D.解析:考点 有向图的入度与出度 解析 在有向图中,顶点总的

    16、入度和出度是相同的,所以其比例为1。9.含有 n 个顶点和 e 条边的有向图的邻接矩阵中,零元素的个数是_ A.e B.2e C.n2-2e D.n2-e(分数:2.00)A.B.C.D. 解析:考点 图的邻接矩阵中零元素的个数解析 含有 n 个顶点和 e 条边的有向图的邻接矩阵中,零元素的个数是 n2-e。10.n 个顶点的无向连通图,其生成树的边数为_ A.n-1 B.n C.n+1 D.nlog2n(分数:2.00)A. B.C.D.解析:考点 无向图的边数的问题 解析 n 个顶点的无向连通图,其生成树的边数为 n-1。11.用自底向上的冒泡排序方法对序列(8,13,26,55,29,4

    17、4)从大到小排序,第一趟排序需进行交换的次数为_ A.2 B.3 C.4 D.5(分数:2.00)A. B.C.D.解析:考点 冒泡排序算法中交换的次数 解析 根据冒泡排序的方法,可知给定序列第一趟排序的交换次数为 2。12.对序列(8,13,26,55,29,44)从小到大进行基数排序,第一趟排序的结果是_ A.(13,44,55,26,8,29) B.(13,26,55,44,8,29) C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)(分数:2.00)A. B.C.D.解析:考点 基数排序 解析 根据基数排序的方法,第一趟先按个位数排序,得到排序结果为(

    18、13,44,55,26,8,29)。13.采用分块查找时,要求数据_ A.块内有序 B.分块有序 C.分块无序 D.每块中数据个数必须相同(分数:2.00)A.B. C.D.解析:考点 分块排序的基本要求 解析 采用分块查找时,要求数据分块有序。14.下列关于散列函数的说法正确的是_ A.散列函数越复杂越好 B.散列函数越简单越好 C.用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下,散列函数越简单越好(分数:2.00)A.B.C.D. 解析:考点 散列函数的性质的判断 解析 在冲突尽可能少的情况下,散列函数越简单越好。15.下列关于 m 阶 B 树的叙述中,错误的是_ A.每个结点

    19、至多有 m 棵子树 B.每个结点至多有 m-1 个关键字 C.所有的叶结点均在同一层上 D.根结点至少有 m/2 棵子树(分数:2.00)A.B.C.D. 解析:考点 B 树的特征的判断 解析 根结点(若不为叶子结点)至少有 2 棵子树,除根结点之外的所有非终端结点至少有 m/2 棵子树。二、B填空题/B(总题数:10,分数:20.00)16.算法的时间复杂度与实现时采用的程序设计语言_。(分数:2.00)填空项 1:_ (正确答案:无关)解析:考点 算法的时间复杂度与采用的设计语言的关系 解析 算法的时间复杂度与实现时采用的程序设计语言无关。17.在长度为 n 的顺序表的第 i(1in)个元

    20、素之后插入一个元素时,需向后移动_个元素。(分数:2.00)填空项 1:_ (正确答案:n-i)解析:考点 顺序表中元素的插入问题 解析 在长度为 n 的顺序表的第 i(1in)个元素之后插入一个元素时,需向后移动 n-i 个元素。18.设循环队列存放在向量 data0m-1中,在出队操作后,队头指针 front 变化为_。(分数:2.00)填空项 1:_ (正确答案:加 1)解析:考点 循环队列的操作 解析 当队列执行出队操作时,其队头指针将加 1。19.树的前序遍历序列等同于该树对应二叉树的_遍历序列。(分数:2.00)填空项 1:_ (正确答案:前序)解析:考点 树的前序遍历与其对应的二

    21、叉树的遍历的关系 解析 树的前序遍历序列等同于该树对应二叉树的前序遍历序列。20.一个 10090 的整型稀疏矩阵有 10 个非零元素,设每个整型数占 2 个字节,则用三元组表存储该矩阵时,所需的字节数是_。(分数:2.00)填空项 1:_ (正确答案:60)解析:考点 三元组表的存储问题 解析 稀疏矩阵共有 10 个非零元素,每个整型变量需要 2 个存储单元,共需 1032=60 个存储单元。21.当用二叉链表作为 n 个结点的二叉树的存储结构时,空指针域的个数是_。(分数:2.00)填空项 1:_ (正确答案:n+1)解析:考点 二叉链表的空链域的个数 解析 当用二叉链表作为 n 个结点的

    22、二叉树的存储结构时,空指针域的个数是 n+1。22.采用邻接表表示 n 个顶点的有向图时,若表结点的个数为 m,则该有向图的边数为_。(分数:2.00)填空项 1:_ (正确答案:m)解析:考点 图的邻接表与图的对应关系 解析 有向图的邻接表中,表结点的个数等于有向图的边数。23.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是_。(分数:2.00)填空项 1:_ (正确答案:冒泡排序)解析:考点 排序方法的选择 解析 当待排序记录关键字基本有序时,宜采用直接插入排序或冒泡排序。24.在 16 个记录的有序顺序表中进行二分查找,最大比较次数是_。(分数:2.00)

    23、填空项 1:_ (正确答案:33)解析:考点 二分查找的查找次数的计算 解析 在 n 个记录的有序顺序表中进行二分查找,最大比较次数是 2n+1。25.在排序算法中,若排序前后具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是_的。(分数:2.00)填空项 1:_ (正确答案:稳定)解析:考点 排序算法稳定性的概念 解析 在排序算法中,若排序前后具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的。三、B解答题/B(总题数:1,分数:5.00)判别以下序列是否为堆,若不是,将其调整为大根堆,并画出大根堆。(分数:5.00)(1).(1,5,7,20,18,8,10,

    24、40)(分数:2.50)_正确答案:(不是大根堆,调整后的根堆为:(40,20,10,5,18,8,7,1)解析:(2).(18,9,5,8,4,17,21,6)(分数:2.50)_正确答案:(不是大根堆,调整后的大根堆为:(21,9,18,8,4,17,5,6)解析:考点 大堆的判定以及调整四、B算法阅读题/B(总题数:2,分数:20.00)单链表类型定义如下:typedef struet nodeDataType data; struct node *next; ListNode; typedef ListNode *LinkList; 阅读下列算法,并回答问题:void f30(Link

    25、lList head, DataType x) /head 是带头结点的非空单链表的头指针ListNode *p, *q; p=head; while(p-next-next)p=p-next; q=(ListNode*)malloc(sizeof(ListNode); q-data=x; q-next=p-next; p-next=q; (分数:5.00)(1).该算法的功能是什么?(分数:2.50)_正确答案:(在单链表的表尾处插入结点 x)解析:(2).若单链表的长度为 n,算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?(分数:2.50)_正确答案:(算法的时间复杂度为 O

    26、(n),该时间复杂度与链表的初始状态无关)解析:考点 单链表的插入操作 解析 根据算法可知其为在单链表的表尾处插入结点 x 的算法,其时间复杂度为 O(n),该时间复杂度与链表的初始状态无关。阅读下列算法(假设栈的操作函数都已定义),并回答问题:void f31_ SeqStaek S; char x, y; x=c; y=k; Push( Push( Push( x=Pop( Push( Push( X=Pop( Push( while(!StackEmpty( putchar(y);putchar(x);(分数:15.00)(1).自底向上写出执行 while 语句之前栈 S 中的元素序列

    27、。(分数:3.75)_正确答案:(执行 while 语句之前栈 S 中的元素序列为 c,a,t,s)解析:(2).写出该函数的最后输出结果。(分数:3.75)_正确答案:(该函数的最后输出结果为 stack。)解析:考点 栈的操作的应用 解析 通过阅读程序可知执行 while 语句之前栈 s 中的元素序列为c,a,t,s;该函数的最后输出结果为 stack。(3).下列算法的功能是在中序线索树中查找结点*p 的前趋,填上适当内容使算法完整。 typedef enum Link, Thread PointerTag; /枚举值 Link 和 Thread 分别为 0 和 1 typedef st

    28、ruct node DataType data; PointerTag ltag, rtag; Struct node *lchild, *rchild; BinThrNode; BinThrNode*f32(BinThrNode *p) /在中序线索树中找结点*p 的中序前趋,设 p 非空 BinThrNode *q; if(p-ltag=Thread)_; else q=p-lchild; while(q-rtag=Link)_; return q; (分数:3.75)_正确答案:(return p-lchild q=q-rchild)解析:考点 以中序线索二叉链表作为存储结构,查找某结点

    29、的中序前驱结点的算法 解析 根据题干中所给的算法的功能:在中序线索树中查找结点*p 的前驱,可填出空白语句。(4).分析下列排序算法中语句 1 和语句 2 的频度以及此算法的时间复杂度,并指出该算法是属于哪一种排序方法。 void f33(int a, int n) int i, j, k, t; for(i=0; in; i+) /语句 1 j=i; for (k=j+1; k=n; k+) if(akaj)j=k; /语句 2 t=ai; ai=aj; aj=t; (分数:3.75)_正确答案:(语句 1 频度是 n语句 2 频度 n(n+1)/2该算法为直接选择排序,其时间复杂度为 O(

    30、n2)。)解析:考点 直接选择排序的算法解析 根据算法,可判断出其为直接选择排序的算法,其时间复杂度为 O(n2)。五、B算法设计题/B(总题数:1,分数:10.00)26.二叉排序树的类型定义如下: typedef struct node int data; struct node *lehild, *rchild; *BSTree; 编写递归算法从小到大输出二叉排序树 T 中所有 data 域值大于 m 且小于 n 的数据。 函数原型为 void f34(BSTree T, int m, int n)(分数:10.00)_正确答案:(void f34(BSTree T, int m, int n) BSTNode *p; /定义指向树结点的指针 p=T; if (T=NULL) exit(0); if(mp-data) f34(p-lchild, m, n); f34(p-rchild, m, n) )解析:考点 输出二叉排序树中所有 data 域值大于 m 且小于 n 的数据的算法


    注意事项

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




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

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

    收起
    展开