四川小自考 四川小自考课程购买入口

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

发布日期:2019-11-28 编辑整理:四川小自考 【字体: 【加入自考交流群】

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

  课程代码:02142

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

  选择题部分

  注意事项:

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

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

  一、单项选择题(本大题共15小题,每小题2分,共30分)

  在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。

  1.下列几种算法时间复杂度中,最小的是

  A.O(log2n) B.O(n)

  C.O(n2) D.O(1)

  2.数据的存储方式中除了顺序存储方式和链式存储方式之外,还有

  A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式

  C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式

  3.表长为n的顺序表中做删除运算的平均时间复杂度为

  A.O(1) B.O(log2n)

  C.O(n) D.O(n2)

  4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为

  A.O(1) B.O(log2n)

  C.O(n) D.O(n2)

  5.元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为

  A.D B.C

  C.B D.A

  6.带头结点的链队列中,队列头和队列尾指针分别为front和rear,则判断队列空的条件为

  A.front==rear B.front!=NULL

  C.rear!==NULL D.front==NULL

  7.深度为5的二叉树,结点个数最多为

  A.31个 B.32个

  C.63个 D.64个

  8.如果结点A有2个兄弟结点,结点B为A的双亲,则B的度为

  A.1 B.3

  C.4 D.5

  9.将题9图所示的一棵树转换为二叉树,结点C是

  A.A的左孩子

  B.A的右孩子

  C.B的右孩子

  D.E的右孩子

  10.n为图的顶点个数,e为图中弧的数目,则图的拓扑排序算法的时间复杂度为

  A.O(n) B.O(e)

  C.O(n-e) D.O(n+e)

  11.无向图的邻接矩阵是

  A.对角矩阵 B.稀疏矩阵

  C.上三角矩阵 D.对称矩阵

  12.在具有101个元素的顺序表中查找值为x的元素结点时,平均比较元素的次数为

  A.50 B.51

  C.100 D.101

  13.构造散列函数的方法很多,常用的构造方法有

  A.数字分析法、除留余数法、平方取中法

  B.线性探测法、二次探测法、除留余数法

  C.线性探测法、除留余数法、链地址法

  D.线性探测法、二次探测法、链地址法

  14.就平均时间性能而言,快速排序方法最佳,其时间复杂度为

  A.O(n) B.O(nlog2n)

  C.O(n2) D.O(1og2n)

  15.下述算法中,不稳定的排序算法是

  A.直接插入排序 B.冒泡排序

  C.堆排序 D.归并排序

  非选择题部分

  注意事项:

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

  二、填空题(本大题共13小题,每小题2分,共26分)

  16.数据的基本单位是_________。

  17.双向循环链表中,在p所指结点的后面插入一个新结点*t,需要修改四个指针,分别为

  t->prior=P;t->next=p->next;_________;p->next=t;。

  18.在带有头结点的循环链表中,尾指针为rear,判断指针P所指结点为首结点的条件是_________。

  19.若线性表中最常用的操作是求表长和读表元素,则顺序表和链表这两种存储方式中,较节省时间的是_________。

  20.不含任何数据元素的栈称为_________。

  21.稀疏矩阵一般采用的压缩存储方法是_________。

  22.100个结点的二叉树采用二叉链表存储时,用来指向左、右孩子结点的指针域有_________个。

  23.已知完全二叉树的第5层有5个结点,则整个完全二叉树有_________个结点。

  24.n个顶点的有向图G用邻接矩阵A[1..n,1..n]存储,其第i列的所有元素之和等于顶点

  Vi的_________。

  25.具有10个顶点的有向完全图的弧数为_________。

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

  27.在长度为n的带有岗哨的顺序表中进行顺序查找,查找不成功时,与关键字的比较次数为_________。

  28.归并排序算法的时间复杂度是_________。

  三、应用题(本大题共5小题,每小题6分,共30分)

  29.稀疏矩阵A如题29图所示,写出该稀疏矩阵A的三元组表示法。

  30.设二叉树的中序遍历序列为BDCEAFHG,后序遍历序列为DECBHGFA,试画出该二叉树。

  31.写出题31图所示无向图的邻接矩阵,并写出每个顶点的度。

  题31图

  32.已知散列表的地址空间为0至13,散列函数H(k)=kmod11,(mod为求余运算),待散列序列为(26,61,38,84,49),用二次探测法解决冲突,构造该序列的散列表,要求写出处理冲突的过程。

  33.将一组键值(80,50,65,13,86,35,96,57,39,79,59,15)应用二路归并排序算法从小到大排序,试写出各趟的结果。

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

  34.设单链表及链栈S的结构定义如下:

  typedef struct node

  { Data Type data;

  struct node*next;

  }linkstack;

  编写一个算法void ReverseList(1inkstack *head),借助于栈S将带头结点单链表head中序号为奇数的结点逆置,序号为偶数的结点保持不变。(例如:单链表的逻辑结构为(a1,a2,a3,a4,a5,a6),逆置后变为(a5,a2,a3,a4,a1,a6))。

  说明:栈的初始化运算用InitStack(S);进栈运算用Push(S,x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。

  35.以二叉链表作为存储结构,试编写递归算法实现求二叉树中叶子结点个数。

点击查看全部真题 >>

扫码登录


扫码关注“四川小自考”微信公众号

即可查看全部内容

二维码以过期,请重新刷新

本文标签:四川小自考 数据结构导论 2014年4月全国高等教育自学考试数据结构导论试题

转载请注明:文章转载自(http://www.scxzk.net

本文地址:http://www.scxzk.net/html/sjjgdl/28335.html

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

四川小自考指导老师微信
(添加“四川小自考”指导老师微信,在线咨询报名报考等相关问题)

《四川小自考网》免责声明:

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

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

相关《2014年4月全国高等教育自学考试数据结构导论试题》的文章

四川小自考-便捷服务