四川自考网 > 历年真题 > 2017年4月四川自考02331《数据结构》真题
2017年4月四川自考02331《数据结构》真题
一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下列叙述中,不正确的是( )
A.算法解决的只能是数值计算问题
B.同一问题可以有多种不同算法
C.算法的每一步操作都必须明确无歧义
D.算法必须在执行有限步后结束
2.下列关于栈中逻辑上相邻的两个数据元素的叙述中,正确的是( )
A.顺序存储时不一定相邻,链式存储时一定相邻
B.顺序存储时不一定相邻,链式存储时也不一定相邻
C.顺序存储时一定相邻,链式存储时也一定相邻
D.顺序存储时一定相邻,链式存储时不一定相邻
3.对带头结点的单循环链表从头结点开始遍历(head为头指针,p=head->next)。若指 针p指向当前被遍历结点,则判定遍历过程结束的条件是( )
A.p==NULL
B.head==NULL
C.p==head
D.head !=p
4.设栈的入栈序列为1,2,3,4,5,经过入、出栈操作后,可能得到的出栈序列是( )
A.2,3,5,1,4
B.4,2,1,3,5
C.3,4,1,2,5
D.3,4,2,1,5
5.数组A[2][3]按行优先顺序存放,A的首地址为10。若A中每个元素占用一个存储单元,则元素A[1][2]的存储地址是( )
A.10
B.12
C.14
D.15
6.广义表((a,b),(c,d))的表尾是( )
A.b
B.d
C.( c, d)
D.((c,d))
7.若完全二叉树T包含20个终端结点,则T的结点数最多是( )
A.38
B.39
C.40
D.41
8.对下面的二叉树进行中序线索化后,结点f的右指针指向的结点是( )
A.a
B.b
C.c
D.e
9.若图G是一个含有n个顶点的强连通有向图,则G的边数至少是( )
A.n-1
B.n
C.n*(n+1)/2
D.n*(n+1)
10.若从顶点a开始对下图进行广度优先遍历,则不可能得到的遍历序列是( )
A.a,b,c,e,f,d
B.a,c,b,e,f,d
C.a,c,e,b,d,f
D.a,e,b,c,f,d
11.下列排序算法中,稳定的是( )
A.堆排序
B.直接选择排序
C.冒泡排序
D.希尔排序
12.下列排序算法中,比较操作的次数与待排序序列初始排列状态无关的是( )
A.快速排序
B.直接选择排序
C.冒泡排序
D.直接插入排序
13.若对二叉排序树进行遍历,则下列遍历方式中,其遍历结果为递增有序的是( )
A.前序遍历
B.中序遍历
C.后序遍历
D.按层遍历
14.设一组记录的关键字为{12,22,10,20,88,27,54,11},散列函数为H(key)=key%11,用拉链法解决冲突,则散列地址为0的链中结点数是( )
A.1
B.2
C.3
D.4
15.在下面3阶B树中插入关键字65后,其根结点内的关键字是( )
A.53 90
B.53
C.90
D.65
二、填空题(本大题共10小题,每小题2分,共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。
11.散列方法的基本思想是根据元素的关键字直接计算出该元素的________。
12.一个需要频繁增删的线性表宜选择________存储结构。
13.若中缀表达式为9+(6-2)*8,则相应的后缀表达式是________。
14.对任何一棵二叉树T,若其叶子结点数为n0, 度数为2的结点数为
, 则等于________。15.若某二叉树T的前序遍历序列是A,B,C,D,中序遍历序列是B,A,D,C,则T的后序遍历序列是________。
16.在给定n个叶子结点权值且不含度数为1的结点的所有二叉树中,其________最小的二叉树称为哈夫曼树。
17.用邻接表存储含n个顶点e条边的有向无环图G,对G进行拓扑排序,算法的时间复杂度为________。
18.连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的________树。
19.二分查找的速度快效率高,但是它要求表按关键字有序并且________。
110.除了问题的规模和分量个数之外,还有________是影响基数排序时间复杂度的主要因素。
三、解答题(本大题共4小题,每小题5分,共20分)
21.对题26图所示的带权无向图G,试回答以下问题。
(1)画出G的最小生成树;(2)若用克鲁斯卡尔( Kruskal)算法求最小生成树,请按被选中的次序写出最小生成树上各条边的顶点和权值。22.已知散列表的长度为11,散列函数为H(key)=key%11,散列表的当前状态如下:
现要插入关键字38,回答下列问题(1)若用线性探查法解决冲突,则38所在位置的下标是什么?(2)若用二次探查法解决冲突,则38所在位置的下标是什么?(3)以上两种方法中,各需要多少次擦查次数?23.试回答下列关于拓扑排序算法的问题。(1)算法中利用一个栈保存入度为0的顶点,其目的是什么?(2)若在算法中将队列改为栈,相应地将入、出栈及判栈空操作改为入、出队列和判队列空操作,其他部分不变,是否依然能够得到拓扑排序的正确结果?
24.考虑用快速排序、堆排序和归并排序3种排序方法对数据序列进行排序,针对下列不同情况,宜分别选择哪种排序方法?(1)使用尽量少的存储空间;(2)要求排序结果是稳定的;(3)快速找出数据序列中关键字值较大的若干项。
四、算法阅读题(本大题共4小题,每小题5分,共20分)
31.设链表中结点类型定义如下,阅读程序,回答下列问题。typedef int DataType;typedef struct node{ DataType data; struct node *next;} RecType, LinkList; int f30( LinkList *head) { if( head ==NULL ) return 0; else return max(head-> data,f30(head->next); //max(ab)返回ab中的较大者}(1)若链表L={2,12,16,88,5,10},写出调用f30(L)的输出结果;(2)函数f30的功能是什么?
32.函数f31的功能是逆序输出链表中所有结点的数据域值。请在空白处填充适当的内容,使其完成指定功能。void f31 LinkList *head){ if( head==NULL ) ___(1)___; else { f31(head->next); printf("%d",___(2)___); }}
33.函数f32的功能是统计N个顶点的有向图中边的数量,有向图用邻接矩阵A表示。阅读程序,并在空白处填入适当内容,使其完成指定功能。int f32(intAIN) { int i, j; int sum=0; for(i=0; i<N; (3) ) for( ___(2)___ ; j <N;j++) if( ___(3)___ ) sum++; return sun;}
34.已知二叉树的二叉链表类型定义如下:typedef struct node{ char data; struct node * lchild, *rchild; } BiTNode; typedef BiNode BiTree;以下程序为求二叉树深度的递归算法,请填空完普之。int depth( Bitree *bt) /*bt为指向根结点的指针*/ { int h1=0, hr =0; if(___(1)___) return (0); h1=depth( bt-> lchild); hr= depth (bt->rchild); if(___(2)___) return (h1+1); else ___(3)___;}
五、算法设计题(本大题共1小题,共10分)
41.已知二叉树的结点类型定义如下:typedef struct node{ int data; struct node *lchild, *rchild;}BinTNode;typedef BinTNode BinTree;请编写函数 SearchXNum,计算任意二叉树T中其数据域的值大于或等于x的结点的个数并返回该值。函数原型如下: int SearchXNum( Bintree *T, int x);//返回二叉树T中数据域的值大于或等于x的结点的个数
如果大家想要获得更多的四川自考本科、四川自考专科的历年真题和复习资料,请关注四川自考网。
猜你喜欢
- 2022-01-11 2021年10月四川自考04729《大学语文》真题
- 2022-01-11 2021年10月四川自考03708《中国近现代史纲要》真题及答案
- 2022-01-11 2021年10月四川自考03706《思想道德修养与法律基础》真题及答案
- 2022-01-11 2021年10月四川自考03709《马克思主义基本原理概论》真题级答案
- 2022-01-11 2021年10月四川自考00015《英语(二)》真题答案及评分参考
- 2022-01-11 2021年10月四川自考00015《英语(二)》真题
自考微信公众号
扫一扫上方二维码