国家工信部网站备案实名:湖北自考网 为考生提供湖北自考信息服务,仅供学习交流使用,官方信息以湖北教育考试院为准。

湖北自考网

网站首页 自考专业 自考培训 考场查询 成绩查询 网上报名 考生平台
专题:
自考报名时间 考试时间 自考单科网课 模拟考试 教材大纲 免考办理 转考办理 实践考核 毕业申请 学位英语培训 学位申请 专升本 成人高考 中专
湖北自考在线 湖北学位英语培训班 湖北成人高考报名 湖北自考视频免费领取
当前位置:湖北自考网 > 2013年1月数据结构导论自考试题

2013年1月数据结构导论自考试题

湖北自考网 来源: 时间:2013-03-14 10:22:28

全国2013年1月数据结构导论自考试题

 

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1.数据的基本单位是
A.数据元素 B.数据项
C.字段 D.域
2.算法的空间复杂度是指
A.算法中输入数据所占用的存储空间的大小
B.算法本身所占用的存储空间的大小
C.算法中所占用的所有存储空间的大小
D.算法中需要的辅助变量所占用存储空间的大小
3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为
A.29 B.30
C.70 D.71
4.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是
A.单链表 B.双链表
C.单循环链表 D.顺序表
5.判断链栈LS是否为空的条件是
A.LS->next= =LS B.LS->next= =NULL
C.LS! =NULL D.LS= =NULL
6.关于链队列的运算说法正确的是
A.入队列需要判断队列是否满 B.出队列需要判断队列是否空
C.入队列需要判断队列是否空 D.出队列需要判断队列是否满
7.元素的进栈次序为A,B,C,D,E,则出栈中不可能的序列是
A.A,B,C,D,E B.B,C,D,E,A
C.E,A,B,C,D D.E,D,C,B,A
8.具有63个结点的完全二叉树是
A.满二叉树 B.二叉排序树
C.哈夫曼树 D.空树
9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是
A.左孩子编号为79,右孩子编号为80
B.左孩子不存在,右孩子编号为80
C.左孩子编号为80,右孩子不存在
D.左孩子不存在,右孩子不存在
10.将题10图所示的一棵树转换为二叉树,结点D是
A.A的右孩子
B.B的右孩子
C.C的右孩子
D.E的右孩子
11.无向图的邻接矩阵是                                      
A.对称矩阵 B.稀疏矩阵
C.对角矩阵 D.上三角矩阵
12.图的广度优先搜索遍历的过程类似于树的
A.前序遍历 B.中序遍历
C.后序遍历 D.按层次遍历
13.要解决散列引起的冲突问题,最常用的方法是
A.数字分析法、除留余数法、平方取中法 B.除留余数法、线性探测法、平方取中法
C.线性探测法、二次探测法、链地址法 D.除留余数法、线性探测法、二次探测法
14.下列表述中,正确的是
A.序列(102,81,55,62,50,40,58,35,20)是堆
B.序列(102,81,55,62,50,40,35,58,20)是堆
C.序列(102,81,55,58,50,40,35,62,20)是堆
D.序列(102,71,55,40,50,62,35,58,20)是堆
15.下列算法中,不稳定的排序算法是
A.冒泡排序 B.快速排序
C.直接插入排序 D.二路归并排序

非选择题部分

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

二、填空题(本大题共13小题,每小题2分,共26分)
16.下面算法程序段的时间复杂度为__________。
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{x=a[i][j];
a[i][j]=a[j][i];
a[j][i]=x;}
17.设p指向单链表的最后一个结点,要在最后一个结点之后插入q所指的结点,需执行的语句序列是①p->next=q;②__________;③p->next=NULL。
18.向一个长度为100的顺序表中第50个元素之前插入一个元素时,需向后移动的元素个数为__________。
19.一个带头结点的链栈LS,现将一个新结点入栈,指向该结点的指针为p,入栈操作为p->next=LS->next和__________。
20.队列操作的原则是__________。
21.含有n个顶点的连通图中的任意一条简单路径,其最大长度为__________。
22.在一棵度为3的树中,度为3的结点数为1个,度为2的结点数为2个,度为1的结点数为3个,则度为0的结点数为__________个。
23.某二叉树的中序遍历序列为BACDEFGH,后序遍历序列为BCAEDGHF,则根结点F的左子树上共有__________个结点。
24.设有向图G的邻接矩阵为A,如果<Vi,Vj>是图中的一条弧,则A[i][j]的值为_______。
25.一个有序表A含有15个数据元素,且第一个元素的下标为1,按二分查找算法查找元素A[14],所比较的元素下标依次是__________。
26.用n个值构造一棵二叉排序树,它的最大深度为__________。
27.设记录数为n,则冒泡排序算法在最好情况下所作的比较次数为__________。
28.二路归并排序算法的时间复杂度为__________。

三、应用题(本大题共5小题,每小题6分,共30分)
29.设有编号为A,B,C,D的四辆列车,顺序进入一个栈式结构的站台,试写出这四辆列车开出站台的所有可能的顺序。
30.已知一棵二叉树的先序遍历序列为ABCDEFGHK,中序遍历序列为CBEDFAGKH,试建立该二叉树并写出它的后序遍历序列。
31.利用克鲁斯卡尔(Kruskal)算法构造题31图的最小生成树,画出它的构造过程。
32.给定表(27,19,50,1,75,12,40,90,66,32,22),试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树。
33.对初始关键字序列48,39,68,95,88,12,27,48的记录进行冒泡排序(升序),给出排序过程。

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

34.试写出判断带头结点的单链表head中的元素值是否是递减的算法。
35.试写出在有序表T中用二分查找法查找键值为key的元素的算法。

 

结束
本文标签
特别声明:1.凡本网注明稿件来源为“湖北自考网”的,转载必须注明“稿件来源:湖北自考网(www.hbzkw.com)”,违者将依法追究责任;
2.部分稿件来源于网络,如有不实或侵权,请联系我们沟通解决。最新官方信息请以湖北省教育考试院及各教育官网为准!
限时,免费获取学历提升方案

已帮助10w万+意向学历提升用户成功上岸

  • 毛泽东思想概论

    毛泽东思想概论

    培训优势:课时考点精讲+刷题+冲刺,熟练应对考试题型。全程督促学习,安排好学习计划。 毛泽东思想概论...自考培训
  • 英语二

    英语二

    本课程既是一门语言实践课程,也是拓宽知识、了解世界文化的重要素质课程,它以培养学习者的综合语言应用能力为目标,使他们在学习、工作和社会交往中能够使用英语进行有效的交流。 英语二...自考培训
  • 马克思主义基本原理概论

    马克思主义基本原理概论

    本书包括两个部分:自学考试大纲和基本原理。主要内容有,马克思主义是关于工人阶级和人类解放的科学,物质世界及其发展规律,认识的本质及其规律,人类社会及其发展规律,资本主义的形成及其发展,资本主义发展的历史进程,社会主义社会及其进程,共产主义社会及其进程等。 马克思主义基本原理概论...自考培训
  • 思想道德修养与法律基础

    思想道德修养与法律基础

    《思想道德修养与法律基础》课具有鲜明的政治性、思想性、理论性、针对性、科学性、知识性以及实践性和修养性。它包罗政治、思想、道德、心理本质、学习成才和法律本质等内容,指导和回答大学生在人生、抱负、信念等方面遍及关心和迫切需要解决的问题。 思想道德修养与法律基础...自考培训
  • 中国近代史纲要

    中国近代史纲要

    “中国近现代史纲要”全国高等教育自学考试指定教材,依据中央审定的普通高等学校“中国近现代史纲要”编写大纲以及马克思主义理论研究和建设工程重点教材《中国近现代史纲要》,结合自学考试的特点设计了十章,集中讲述1840年鸦片战争爆发一直到2007年中国共产党第十七次全国代表大会召开的160多年的中国近现代历史。 中国近代史纲要...自考培训
微信公众号 考试交流群
湖北自考网微信公众号

扫一扫关注微信公众号

随时获取湖北省自考政策、通知、公告以及各类学习资料、学习方法、课程。