《最新全国10月自考数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《最新全国10月自考数据结构试题及答案.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 全国 2012 年 10 月自考数据结构(02331)试题及答案 精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 全国 2012 年 10 月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分 注意事项：1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2.每小题选出答案后，用 2B 铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共 l5 小题，每小题 2 分，共 30分)
2、在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。1一个算法的时间耗费的数量级称为该算法的 A效率 B难度 C可实现性 D时间复杂度 2顺序表便于 A插入结点 B删除结点 C按值查找结点 D按序号查找结点 3设带头结点的单循环链表的头指针为 head，指针变量 P 指向尾结点的条件是 Ap-next-next=head Bp-next=head Cp-next-next=NULL Dp-next=NULL 4设以数组 A0.m-1存放循环队列，front 指向队头元素，rear 指向队尾元素的下一个位置，则当前队列中的元素个数
3、为 程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 A(rear-front+m)m Brear-front+1 C(front-rear+m)m D(rear-front)m 5下列关于顺序栈的叙述中，正确的是 A入栈操作需要判断栈满，出栈操作需要判断栈空 B入栈操作
4、不需要判断栈满，出栈操作需要判断栈空 C入栈操作需要判断栈满，出栈操作不需要判断栈空 D入栈操作不需要判断栈满，出栈操作不需要判断栈空 6A 是一个 10 10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为 1，每个元素占一个存储单元，则 a7,5的地址为 A25 B26 C33 D34 7树的后序遍历等价于该树对应二叉树的 A层次遍历 B前序遍历 C中序遍历 D后序遍历 8使用二叉线索树的目的是便于 A二叉树中结点的插入与删除 B在二叉树中查找双亲 C确定二叉树的高度 D查找一个结点的前趋和后继 9设无向图的顶点个数为 n，则该图边的数目最多为 An-l Bn(n-
5、1)2 Cn(n+1)2 Dn2 10可进行拓扑排序的图只能是 A有向图 B无向图 C有向无环图 D无向连通图 程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 11下列排序方法中稳定的是 A直接插入排序 B直接选择排序 C堆排序 D快速排序 12下列序列不为堆的是 A7
6、5,45,65,30,15,25 B75,65,45,30,25,15 C75,65,30,l5,25,45 D75,45,65,25,30,15 13对线性表进行二分查找时，要求线性表必须是 A顺序存储 B链式存储 C顺序存储且按关键字有序 D链式存储且按关键字有序 14分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 的序列是 A(4,1,2,3,5)B(4,2,3,l,5)C(4,5,2,1,3)D(4,2,1,5,3)15下列关于 m 阶 B 树的叙述中，错误的是 A每个结点至多有 m 个关键字 B每个结点至多有 m 棵子树 C插入关键字时，通过结点分裂使树高增
7、加 D删除关键字时通过结点合并使树高降低 非选择题部分 注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共 10 小题，每小题 2 分，共 20 分)16数据元素之间的逻辑关系称为数据的_结构。程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请
8、联系网站删除 17在线性表中，表的长度定义为_。18用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1、2、3、4，为了得到 1、3、4、2 的出栈顺序，相应的 S 和 X 的操作序列为_。19在二叉树中，带权路径长度最短的树称为_。20已知广义表 G，head(G)与 tail(G)的深度分别为 4 和 6，则 G 的深度是_。21一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符d的哈夫曼编码的长度为_。22在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要_条边。23直接选择排序算法的时间复杂度是_。24对于长度为 81 的表，若采用分块查找，每块
9、的最佳长度为_。25用二叉链表保存有 n 个结点的二叉树，则结点中有_个空指针域。三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26假设 Q 是一个具有 11 个元素存储空间的循环队列(队尾指针指向队尾元素的下一 个位置，队头指针指向队头元素)，初始状态 Q.front=Q.rear=0；写出依次执行 下列操作后头、尾指针的当前值。a,b,c,d,e,f 入队，a,b,c,d 出队；(1)Q.front=_；Q.rear=_。g,h,i,j,k,l 入队，e,f,g,h 出队；(2)Q.front=_；Q.rear=_。M,n,o,P 入队，i,j,k,l,m 出队；(3)Q.
10、front=_；Q.rear=_。27已知一个无向图如题 27 图所示，以为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 28用归并排序法对序列(98,36,-9,0,47,23,1,8)进行排序
11、，问：(1)一共需要几趟归并可完成排序。(2)写出第一趟归并后数据的排列次序。29一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数 H(key)=key 11 将记录 散列到散列表 HT0.12中去，用线性探测法解决冲突。(1)画出存入所有记录后的散列表。(2)求在等概率情况下，查找成功的平均查找长度。四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30顺序表类型定义如下：#define ListSize 100 typedef struct int dataListSize；int length；SeqList；阅读下列算法，并回答问题：v
12、oid f30(SeqList *L)int i,j；i=0；while(ilength)if(L-datai2!=0)for(j=i+1;jlength;j+L-dataj-1=L-dataj;L-length-;else i+（1）若 L-data 中的数据为（22,4,63,0,15,29,34,42,3）,则执行上述算法后 L-data中的数据以及 L-length 的值各是什么？程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结
13、点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除（2）该算法的功能是什么？31.有向图的邻接矩阵类型定义如下：#define MVN 100 最大顶点数 typedef int EType;边上权值类型 typedef struct EType edgesMVNMVN;邻接矩阵，即边表 int n;图的顶点数 MGraph;图类型 例如，一个有向图的邻接矩阵如下所示：0 1 0 0 01 0 0 0 10 1 0 1 01 0 0 0 00 0 0 1 1A 阅读下列算法，并
14、回答问题：Void f31(MGraph G)Int i,j,k=0;Step1:for (i=0;iG.n;i+)for (j=0;jG.n;j+)if (G.edgesij=1)k+;printf(“%d n”,k);step2:for (j=0;jG.n;j+)k=0;for (i=0;iG.n;j+)if (G.edgesij=1)k+;printf(“%d n”,k);程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找
15、结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除(1)stepl 到 step2 之间的二重循环语句的功能是什么?(2)step2 之后的二重循环语句的功能是什么?32阅读下列算法，并回答问题：void f32(int r，int n)Int i，j；for(i=2；in；i+)r0=ri；j=i-l；while (r0rj)rj+l=rj；j=j-1；rj+l=r0；(1)这是哪一种插入排序算法?该算法是否稳定?(2)设置 r0的作用是什么?33顺序表类型定义如下：typedef i
16、nt SeqList100；阅读下列算法，并回答问题：void f33(SeqList r，int n)int a,b，i；if (r0 程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 else a=r1；b=r0；for (i=2；in；i+)if (rib)b=ri
17、；printf(a=d，b=d。n，a，b)；(1)给出该算法的功能；(2)给出该算法的时间复杂度。五、算法设计题(本题 10 分)34二叉树的存储结构类型定义如下 typedef struct node int data；struct node *lchild，*rchild；BinNode；typedef BinNode *BinTree；编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。函数的原型为：void f34(BinTree T,int *count,int *sum)*count 和*sum 的初值为 0。程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答
18、题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 程名称姓名准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上每小题选出答案后用铅笔把答题纸上对应每小题分共分在每小题列出的四个备选项中只有一个是符合题目要求的请将其选出并将答题纸的相应代码涂黑错涂多除结点按值查找结点按序号查找结点设带头结点的单循环链表的头指针为指针变量指向尾结点的条件是设以数组存放