数据结构自考2016年10月真题及答案解析
本试卷为单选题型,填空题,算法阅读,算法设计等题型。
一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下列选项中,不属于线性结构特征的是( )
A.数据元素之间存在线性关系
B.结构中只有一个开始结点
C.结构中只有一个终端结点
D.每个结点都仅有一个直接前驱
2.设17个元素的顺序表中,若将第i(1≤i
A.j-i-1
B.j-i
C.j-i-+1
D.i-j
3.若用一个大小为7的数组作为循环队列的存储结构,且当前rear和front的值分别为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素,请问这3个操作之前rear和front的值分别是( )
A.0和1
B.0和3
C.3和6
D.4和5
4.已知广义表LS=(((a)),((b,(c)),(d,(e,f))),0),LS的长度是( )
A.2
B.3
C.4
D.5
5.一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。树中包含的结点数是( )
A.k
B.2k-1
C.
D.
6.如果某二叉树的前序遍历序列为abced,中序遍历序列为cebda,则该二叉树的后序遍历序列是( )
A.cedba
B.decba
C.ecdba
D.ecbad
7.一个森林有m棵树,顶点总数为n,则森林中含有的总边数是( )
A.m
B.n-1
C.n-m
D.n+m
8.设图的邻接矩阵A如下所示。各顶点的度依次是( )
A.1,2,1,2
B.2,2,1,1
C.3,4,2,3
D.4,4,2,2
9.若对下列无向图进行深度优先遍历,得到的正确遍历序列是( )
A.h,c,a,b,d,e,g,f
B.e,a,f,g,b,h,c,d
C.d,b,c,a,h,e,f,g
D.a,b,c,d,h,e,f,g
10.己知有向图G如下所示,G的拓扑序列是( )
A.a,b,e,c,d,f,g
B.a,c,b,f,d,e,g
C.a,C,d,e,b,f,g
D.a,c,d,f,b,e,g
11.下列排序算法中,在每一趟都能选出一个元素放到其最终位置上的是( )
A.插入排序
B.希尔排序
C.归并排序
D.直接选择排序
12.对一组数据(2,12,16,88,5,10)进行排序,若前3趟排序结果如下:第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88则采用的排序方法是( )
A.冒泡排序
B.希尔排序
C.归并排序
D.基数排序
13.设有序表为{9,12,21,32,41,45,52},当二分查找值为52的结点时,元素之间的比较次数是( )
A.1
B.2
C.3
D.4
14.下列选项中,既能在顺序存储结构也能在链式存储结构上进行查找的方法是( )
A.散列查找
B.顺序查找
C.二分查找
D.以上选项均不能
15.在一棵5阶B树中,每个非根结点中所含关键字的个数最少是( )
A.1
B.2
C.3
D.4
二、填空题(本大题共10小题,每小题2分,共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。
11.两个栈S1和S2共用含100个元素的数组S[0一99],为充分利用存储空间,若S2的栈底元素保存在S[99]中,则S1的栈底元素保存在_______中。
12.在一个单链表中,已知指针变量q所指结点不是表尾结点,若在q所指结点之后插入指针变量S所指结点,则正确的执行语句是_______。
13.设顺序表第1个元素的存储地址是1000,每个数据元素占6个地址单元,则第11个元素的存储地址是_______。
14.二叉树采用顺序存储方式保存,结点Z保存在数组A[7]中,若X有右孩子结点L则Y保存在_______中。
15.一棵二叉树中,度数为l的结点个数为n1,度数为2的结点个数为n2,则叶结点的个数为_______。
16.已知广义表LS=((a,b),c,d),head(LS)是_______。
17.在无向图G的邻接矩阵A中,若A[i,j]=1,则A[j,i]=_______。
18. 已知大根堆中的所有关键字均不相同,最大元素在难项,第2大元素可能存在的位置有2个,第3大元素可能存在的位置有_______个。
19.在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等,则查找成功时平均查找长度是_______。
110.线性探查法和拉链法解决的是散列存储中的_______问题。
三、解答题(本大题共4小题,每小题5分,共20分)
21.对题26图中所给的二叉排序树T回答下列问题。(1)给出能生成r的2种关键字插入序列;(2)给出r的前序遍历序列。
22.对题27图所示的无向带权图G,回答下列问题。(1)给出图G的邻接矩阵;(2)给出图G的一棵最小生成树。
23.现有5个权值分别是20、31、16、7和15的叶结点,用它们构造一棵哈夫曼树,画出该树。
24.对于给定的一组关键字序列{26,18,60,65,45,13,32},写出使用直接选择排序方法将其排成升序序列的过程。
四、算法阅读题(本大题共4小题,每小题5分,共20分)
31.设非空双向循环链表L的头指针为head,表结点类型为DLNode,定义如下。typedef int DataType;typedef struct dlode{ DataType data; //data是数据域 struct dlnode * prior, *next; // prior指向前趋结点,next指向后继结点 }DLNode; typedef DLNode * DLinkList;初始时,L中所有结点的prior域均为空(NULL),next域和data域中已经正确赋值。如题30图a所示。函数f30完成的功能是:将L中各结点的prior域正确赋值,使L成为双向循环链表。如题30图b所示。将空白处应填写的内容答在答题卡上。void f30( DLinkList head) { DLNode *p; p=head; while(p->next!=____(1)____) { ____(2)____=p; p=p->next; } ____(3)____=p;}
32.已知二叉树的二叉链表类型定义如下,阅读程序,并回答问题。typedef char DataType;typedef struct node{ DataType data; //data是数据域 struct node *lchild, *rchild; //分别指向左、右孩子结点 }BinTNode; typedef BinTNode * BinTree; void f31( BinTree bt){ if (bt!=NULL) { printf("%c", bt->data ); f31(bt->lchild; printf("%c", bt->data ); }}若二叉树如下所示,写出调用f31(T)的输出结果。
33.阅读下列程序,写出f32的输出结果。void f32(){ SeqStack *S; char x, y; Initstack(S); x= 'h'; y= 't'; Push(S, x); Push(S, 'c'): x= Pop(S); Push(S, x); Push(S, y); Push(S, 'a'); Push( S, x ) while( !StackEmpty(S)) { y= Pop(S); printf(”%c”,y);} printf ("%c "'!');}
34.阅读程序,回答下列问题。int f33( NodeType R[], KeyType k, int n){ int i=n-1, count=1; R[0]. key =k; while(R[i]. key !=k) { i--; count++;} if(i-==0) return-1; else return count;}(1)变量 count的含义是什么?(2)f33的功能是什么?
五、算法设计题(本大题共1小题,共10分)
41.已知单链表类型定义如下:typedef struct node { int data; struct node *next;}ListNode;typedef ListNode * List_pt;单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的前n项。如果是,则函数返回1,否则返回0。函数原型如下:int IsF(List_ptr head); //判定是否是斐波拉契序列注:斐波拉契序列的定义为:f0=0,f1=,,fn=fn-1+fn-2 (n≥2)