02331数据结构2014年4 月份历年真题附答案

全国2014年4月高等教育自学考试 数据结构试 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 课程代码：02331 本试卷满分100分，考试时间150分钟.  考生答题注意事项：    1.本卷所有试题必须在答题卡上作答。答在试卷上无效。试卷空白处和背面均可作草稿纸。    2.第一部分为选择题。必须对应试卷上的题号使用28铅笔将“答题卡”的相应代码涂黑。  3.第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。    4.合理安排答题空间。超出答题区域无效。        第一部分选择题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关的概念是 A.栈    B.链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf C.顺序表    D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址 是 A．1010    B.1016 C.1018    D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2    B.3 C.4    D..6 4.下列关于队列的叙述中,错误的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算    B.节省存储空间 C.便于输入输出    D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14    B.64 C.127    D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e    B. e C. 2e    D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2    B.1 C.2    D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n）    B. O（n+e） C. O（n2）    D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 是 A.归并排序    B.快速排序 C.直接选择排序    D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序    B.冒泡排序 C.直接插入排序    D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找    B.二分查找 C.顺序查找    D.折半查找 14.下列关于m阶B树的叙述中,错误的是 A.根结点至多有m棵子树 B.所有叶子都在同一层次上 C.每个非根内部结点至少有 棵子树 D.结点内部的关键字可以是无序的 15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是 A.线性探查法    B.二次探查法 C.双重散列法    D.拉链法 非选择题部分 注意事项： 用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。 二、填空题（本大题共10小题,每小题2分,共20分） 16.数据结构研究的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 包括数据的逻辑结构、________和数据的运算。 17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是________。 18.普里姆（Prim）算法完成的功能是求图的________。 19.若三维数组a［4］［5］［6］的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是________。 20.二叉树的线索链表利用________存放遍历时得到的前趋或后继结点的指针。 21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为________。 22.若无向图中任意两个不同的顶点间都有路径,则称该图为________。 23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是________。 24.假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是________。 25.顺序查找算法的平均时间复杂度为________。 三、解答题（本大题共4小题,每小题5分,共20分） 26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤。例如：将"ABC"改变为"BCA",则其操作步骤为XXSXSS。 27.假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。 28.设图以邻接表存储,如题28图所示。 （1）写出从顶点v1出发图的深度优先搜索遍历序列。 （2）写出从顶点v1出发图的广度优先搜索遍历序列。 29.（1）一个排序方法稳定的含义是什么？ （2）快速排序是稳定的吗？举例 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 。 四、算法阅读题（本大题共4小题,每小题5分,共20分） 30.阅读下列算法,并回答问题： void  f30（SeqStack  S） {  int  k=0； CirQueue  Q； SeqStack  T； InitQueue（&Q）；        //初始化队列Q InitStack（&T）；          //初始化栈T while  （!StackEmpty（&S）） {  k++; if  （k%2!=0）  Push（&T, Pop（&S））; else  EnQueue（&Q, Pop（&S））; }  //第一个循环 while  （!QueueEmpty（&Q））  //第二个循环 Push（&S, DeQueue（&Q））; while（!StackEmpty（&T））  //第三个循环 Push（&S,Pop（&T））； } 设栈S=（1,2,3,4,5,6,7）,其中7为栈顶元素。调用函数f30（S）后, （1）第一个循环结束后,栈T和队列Q中的内容各是什么？ （2）第三个循环语句结束后,栈S中的内容是什么？ 31.二叉树的二叉链表类型定义如下： typedef struct node { DataType data； struct  node  *lchild, *rchild; } BinNode; typedef  BinNode  *BinTree； 阅读下列算法,并回答问题： void  f31（BinTree  BT） {    BinNode  *s; if （BT） {  s=BT->lchild； BT->lchild=BT->rchild; BT->rchild=s； f31（BT->lchild）； f31（BT->rchild）； } } （1）该算法的功能是什么？ （2）以下算法功能是否等价于上面的算法？ void  f3la（BinTree  BT） {  BinNode  *s; if（BT） {  f31a（BT->lchild）； f31a（BT->rchild）； s=BT->lchild; BT->lchild=BT->rchild; BT->rchild=s； } } 32.单链表类型定义如下： typedef  struct  node { int  data; struct  node  *next; } ListNode; typedef  ListNode  *LinkList; 用不带头结点的单链表存储待排数据,链表头指针为head。下列直接选择排序算法对链表按升序进行排序,请在答题纸相应位置填写适当内容使算法完整。 void  f32（LinkList  head） {  ListNode  *p,  *q,  *r; int  tmp; p=head; while（p） {  q=p； r=->next; while（    (1)    ） {  if（    (2)    ） q=r； r=r->next; } tmp=q->data; q->data=p->data; p->data=tmp; p=    (3)    ； } } 33.实现二分查找的递归章法如下,在答题纸相应位置填写适当的内容使算法完整。 typedef  struct{ KeyType  key; InfoType  otherinfo; }NodeType; typedef  NodeType  SeqList［n+l］; int  f33（SeqList  R,  int  low,  int  high,  KeyType  K） {  int  mid; if（low>high） return  0； mid=    （1）    ； if（R［mid］.key==K） return    （2）    ； if（R［mid］.key