2021年10月自考数据结构导论试题及答案

　　【导读】华图自学考试频道同步华图教育发布：2021年10月自考数据结构导论试题及答案,详细信息请阅读下文!更多资讯请关注华图上学微信公众号(gh＿77568f84fe68)，欢迎大家电话咨询：17110152870 咨询自考报考问题。

★预留信息 学历提升报考问题免费咨询★

学历层次：

• 初中及以下
• 中专
• 高中
• 大专

考取层次：

• 大专
• 本科

提升原因：

• 考职称证书
• 积分落户
• 考公务员
• 求职晋升

      1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。

      2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

      选择题部分

      注意事项:每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

      一、单项选择题:本大题共15小题，每小题2分,共30分。在每小题列出的备选项中只有一项 是最符合题目要求的,请将其选出。

      1.程序段s=i=0;do {i=i+1;s=s+i;}while(i< = n)的时间复杂度为

      A. O(n)

      B. O( nlogzn)

      C. O(n2)

      D. 0(1)

      2.不属于数据组织三个层次的是

      A.数据

      B.数据元素

      C.数据类型

      D.数据项

      3.具有先进先出特征的数据结构是

      A.堆栈

      B.队列

      C.最小堆

      D.完全二叉树

      4.一个栈的输入序列为1234.则下列序列中可能是栈的输出序列的是

      A.231 4

      B.4123

      C.31 24

      D.34 1 2

      5.设指针变量front表示链队列的队头指针.指针变量rear表示链队列的队尾指针，指针变量s指向将要人队列的结点X.则入队列的操作序列为

      A. front->nexl=s; front=s;

      B. s->next= rear;rear=s;

      C. rear->next= s;rear= s;

      D. s->next = front; front=s;

      6.设一棵完全二叉树中有65个结点,则该完全二叉树的深度为.

      A.5

      B.6

      C.7

      D.8

      7.有n个叶结点的哈夫曼树的结点总数为

      A.2n-1

      B.2n

      C.2n+1

      D.2n2

      8.先序遍历与中序遍历结果相同的二叉树

      A.根结点无左孩子

      B.根结点无右孩子

      C.所有结点只有左子树

      D.所有结点只有右子树

      9.设有一个二维数组a[m][n].假设a[0]C0]存放位置为644.a[2][2]存放位置为676.每个元素占一个存储空间,则a[3][3]存放位置为

      A.678

      B.688

      C.692

      D.696

      10.线性表若采用链表存储结构.内存中可用存储单位的地址

      A.必须是连续的

      B.有一部分必须是连续的

      C.一定是不连续的

      D.连续不连续都可以

      11.一个具有n个顶点的无向完全图的边数为

      A.0

      B. n(n-1)/2

      C. n(n-1)

      D. n(n+1)

      12.对于线性表(7.34.55.25.64.46.20.10)进行散列存储时,若散列函数为H(K)=K %9.则散列地址为1的元素个数是

      A.1

      B.2

      C.3

      D.4

      13.对题13图中的树进行遍历后可以得到序列ABCD的遍历方式是

      A.先序遍历

      B.中序遍历

      C.后序遍历

      D.层次遍历

      14.设有序表中的元素为(13.18.24.35.47.50.62).则在其中利用二分法查找值为24的元素需要经过比较的次数是

      A.1

      B.2

      C.3

      D.4

      15.就平均时间性能而言,若需以O(nlog2n)的时间复杂度完成对数组的排序,则可选择的排序方法是

      A.快速排序

      B.冒泡排序

      C.直接选择排序

      D.直接插人排序

      非选择题部分

      注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。

      二、 填空题:本大题共13空,每空2分,共26分。

      16.根据图的定义,图中顶点的最少数目是 ▲ 。

      17.1976年瑞士计算机科学家Niklaus Wirth 曾提出一个著名公式:算法十数据结构 ▲ 。

      18.数据的存储结构有顺序存储链式存储、散列存储和 ▲ 存储。

      19.一个算法的时空性是指该算法的时间性能和空间性能.其中空间性能是算法需要的 ▲ 。

      20.用顺序存储实现的线性表称为顺序表，一般使用 ▲ 来表示。

      21.在单链表中,指针p所指的结点为最后一个结点的条件是 ▲ 。

      22.循环队列被定义为结构体类型,含有三个域:data. front和rear,则循环队列cQ为空的条 ▲

      23.假设m行n列的矩阵有t个非零元素.当t<<mwn时.则称矩阵为 ▲ 。

      24.顺序队列需要预先定义队列的容量.一般将数组的首尾相接,形成循环队列.这样可以解决 ▲ 问题。

      25.树上任一结点所拥有的子树的数目称为该结点的 ▲ 。

      26.一棵二叉树的最少结点个数为 ▲ 。

      27.含有n个顶点的连通图中任意一条简单路径.其长度最大为 ▲ 。

      28.要完全避免散列所产生的“堆积"现象,通常采用 ▲ 解 决冲突。

      三、应用题:本大题共5小题,每小题6分,共30分。

      29.设有编号为1.2,3,4的四辆列车,顺序进人一个栈式结构的站台,若列车2最先开出,则列

      车出站可能的顺序有几种?并写出这四辆列车所有可能的出站顺序。

      30.将题30图所示的森林转换成二叉树。

      31.写出题31图所示的有向带权图的邻接矩阵。

      32.已知题32图所示的二叉排序树中各结点的值分别为1~9.请写出图中结点A~I所对应的值。

      33.已知键值序列{11.2.13.26.5.18.4.9),设散列表表长为13.散列函数H(key)= key mod 13处理冲突的方法为线性探测法.请给出散列表。

      四、算法设计题:本大题共2小题,每小题7分,共14分。

      34.读入n=100个整数到一个数组中.写出实现将该组数进行逆置的算法.并分析算法的空间复杂度。

      35.试写出二分查找的递归算法。

↓↓↓↓2022年全国自学考试相关推荐↓↓↓↓
2022自考 报考指南	2022自考 备考资料	2022自考 公告解读	2022自考 咨询答疑

       相关内容推荐：
2022年10月全国自学考试报名公告汇总
2022年10月各省自考报名时间及入口汇总
2022年10月自考备考复习模拟题汇总
2022年全国自考考试时间及课程安排汇总
2022年10月全国自考准考证打印入口汇总

（编辑：admin）