数据结构自考2016年10月真题

数据结构自考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)