欢迎您访问贵州自考网!网站为考生提供贵州自考信息服务,供学习交流使用,非政府官方网站,官方信息以贵州省招生考试院(http://zsksy.guizhou.gov.cn/)为准 登录  网站导航

贵州自考网

自考热线:400-0929-629

全国2009年1月高等教育自学考试数据结构导论试题

编辑整理:  贵州自考网 发表时间:  2018-05-24   【   点击数:

全国2009年1月高等教育自学考试数据结构导论试题
课程代码:02142

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.

1.数据的不可分割的最小标识单位是(  )
A.数据项
B.数据记录
C.数据元素
D.数据变量

2.for(i=0;ifor(j=0;jc[i][j]=0;
for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];
上列程序的时间复杂度为(  )
A.O(m+n×t)
B.O(m+n+t)
C.O(m×n×t)
D.O(m×t+n)

3.若线性表最常用的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储方式是(  )
A.单链表
B.双链表
C.单循环链表
D.顺序表

4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为(  )
A.p—>next=p—>next—>next
B.p=p—>next
C.p=p—>next—>next
D.p—>next=p

5.向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为(  )
A.hs—>next=s;
B.s—>next=hs;hs=s;
C.s—>next=hs—>next;hs—>next=s;
D.s—>next=hs;hs=hs—>next;

6.设循环队列的元素存放在一维数组Q[0‥30]中,队列非空时,front指示队头元素的前一个位置,rear指示队尾元素.如果队列中元素的个数为11,front的值为25,则rear应指向的元素是(  )
A.Q[4]
B.Q[5]
C.Q[14]
D.Q[15]

7.定义二维数组A[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为(  )
A.LOC+28L
B.LOC+36L
C.LOC+50L
D.LOC+52L

8.具有n个结点的二叉树,拥有指向孩子结点的分支数目是(  )
A.n-1
B.n
C.n+1
D.2n

9.对一棵有100个结点的完全二叉树按层序编号,则编号为49的结点,它的左孩子的编号为(  )
A.99
B.98
C.97
D.50

10.有m个叶子结点的哈夫曼树,其结点总数是(  )
A.2m-1
B.2m
C.2m+1
D.2(m+1)

11.有n个结点的无向图的边数最多为(  )
A.n+1
B.n(n-1)/2
C.n(n+1)
D.2n(n+1)

12.设图的邻接矩阵为,则该图为(  )
A.有向图
B.无向图
C.强连通图
D.完全图

13.二分查找算法的时间复杂度是(  )
A.O(n2)
B.O(nlog2n)
C.O(n)
D.O(log2n)

14.已知8个元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树,则该树的深度为(  )
A.4
B.5
C.6
D.7

15.采用排序算法对n个元素进行排序,其排序趟数肯定为n-1趟的排序方法是(  )
A.插入和快速
B.冒泡和快速
C.选择和插入
D.选择和冒泡

二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案.错填、不填均无分.

16.在数据结构中,数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种.
17.作为一个算法输入的数据所含数据元素的数目,或与此数目有关的其他参数,称为_________.
18.在双链表中,存储一个结点有三个域,一个是数据域,另两个是指针域,分别指向_________和_________.
19.在有n个元素的链队列中,入队和出队操作的时间复杂度分别为_________和_________.
20.在栈结构中,允许插入的一端称为_________;在队列结构中,允许插入的一端称为_________.
21.在循环队列中,存储空间为0~n-1.设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为_________.
22.深度为k的二叉树至多有_________个结点,最少有_________个结点.
23.设有一稠密图G,则G采用_________存储结构较省空间.设有一稀疏图G,则G采用_________存储结构较省空间.
24.在一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较_________个元素结点.
25.假定对线性表R[0…59]进行分块检索,共分为10块,每块长度等于6.若检索索引表和块均用顺序检索的方法,则检索每一个元素的平均检索长度为_________.
26.文件在外存储器上的组织结构主要有三种:顺序文件、散列文件和索引文件,其中_________特别适应磁带存储器,也适应磁盘存储器.
27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是_________.
28.冒泡排序最好的时间复杂度为_________,平均时间复杂度为_________,是一种稳定的排序算法.

三、应用题(本大题共5小题,每小题6分,共30分)
29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF.请构造出该二叉树,并给出该二叉树的后序序列.
30.将题30图所示的由三棵树组成的森林转化为一棵二叉树.
 
题30图
31.已知某图的邻接表存储结构如题31图所示:
 
题31图
(1)画出该图.
(2)根据该邻接表从顶点A出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列.
32.假定采用H(k)=kmod7计算散列地址,引用线性探测的开放定址法解决冲突,试在0~6的散列地址空间中,对关键字序列(38,25,74,63,52,48)构造散列表,并求出等概率情况下查找成功的平均查找长度.
33.用快速排序法对数据序列(49,38,65,97,16,53,134,27,39)进行排序,写出其第一趟排序的全过程.

四、算法设计题(本大题共2小题,每小题7分,共14分)
34.完善下列折半插入排序算法.
Voidbinasort(structnoder[MAXSIZE],int n)
  {for(i=2;i<=n;i++){
    r[0]=r[i];low=1;high=i-1;
    while(low<=high){
      mid=(1)_________;
      if(r[0].key        high=(2)_________;
      elselow=(3)_________;
    }
    for(j=i-1;j>=low;j--)
    (4)_________;
    r[low]=r[0];
  }
}
35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次.请完善该算法.
Voidlevel(BSTreeroot,p) 
  {intlevel=0;
    if(!root)
      (1)_________;
    else{
      level++;
      while(root—>key!=p—>key){
        if(root—>keykey)
          (2)_________;
        else
          (3)_________;
        level++;
      }
      (4)_________;
    }
  }


本文标签:贵州自考 历年真题 全国2009年1月高等教育自学考试数据结构导论试题

转载请注明:文章转载自(http://www.crzkw.cn/

本文地址:http://www.crzkw.cn/lnzt/12962.html


小编提示:添加【贵州自考网】招生老师微信,即可了解2024年贵州自考政策资讯自考报名入口准考证打印入口成绩查询时间以及领取历年真题资料个人专属备考方案等相关信息!

贵州自考网招生老师微信
(添加“贵州自考网”招生老师微信,在线咨询报名报考等相关问题)


贵州自考网微信公众号

贵州自考网课程中心

贵州自考网声明:

1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。

2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。

贵州自考便捷服务

  • 微信交流群
  • 微信公众号


微信扫一扫加入考生微信群
①学习交流、②考试提醒、③自考解答
④自考资料、⑤新闻通知、⑥备考指导

  • 视频课程
  • 真题下载
概率论与数理统计

概率论与数理统计

马克思主义基本原理概论

马原概论

中国近现代史纲要

中国近现代史纲要

思想道德修养与法律基础

思修03706

内科护理学(一)

内科护理学(一)

文学概论(一)

文学概论(一)