​数据结构自考2017年10月真题

数据结构自考2017年10月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列选项中,与数据存储结构直接相关的是(　　)

A.线性表
B.双向链表
C.二叉树
D.有向图

2.将12个数据元素保存在顺序表中,若第一个元素的存储地址是100,第二个元素的存储地址是105,则该顺序表最后一个元素的存储地址是(　　)

A.111
B.144
C.155
D.156

3.设栈的初始状态为空，元素1,2,3,4,5,6依次入栈，栈的容量是3，能够得到的出栈序列 是(　　)

A.1,2,6,4,3,5
B.2,4,3,6,5,1
C.3,1,2,5,4,6
D.3,2,6,5,1,4

4.设指针变量head指向非空单循环链表的头结点,指针变量p指向终端结点,next是结点的指针域,则下列逻辑表达式中,值为真的是(　　)

A.p->next->next==head
B.p->next==head
C.p->next->next==NULL
D.p->next==NULL

5.已知广义表LS=(((ab)),((c,(d)),(e,(f))),(g,h)),LS的深度是(　　)

A.2
B.3
C.4
D.5

6.已知一棵高度为4的完全二叉树T共有5个叶结点,则T中结点个数最少是(　　)

A.9
B.10
C.11
D.12

7.在一棵非空二叉树的中序遍历序列中,所有列在根结点前面的是(　　)

A.左子树中的部分结点
B.左子树中的全部结点
C.右子树中的部分结点
D.右子树中的全部结点

8.用邻接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵中零元素的个数是(　　)

A.n(n+1)/2-e
B.n(n+1)/2-2e
C.n×n-e
D.n×n-2e

9.无向图G中所有顶点的度数之和是20,则G中的边数是(　　)

A.10
B.20
C.30
D.40

10.设有向图G含有n个顶点、e条边,使用邻接表存储。对G进行广度优先遍历的算法的时间复杂度是(　　)

A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)

11.对数据序列(25,15,7,18,10,0,4)采用直接插入排序进行升序排序，两趟排序后，得到的排序结果为(　　)

A.0,4,7,18,10,25,15
B.0,4,25,15,7,18,10
C.7,15,10,0,4,18,25
D.7,15,25,18,10,0,4

12.下列排序方法中,稳定的排序方法是(　　)

A.希尔排序
B.归并排序
C.堆排序
D.快速排序

13.一组记录的关键码为(45,68,57,13,24,89)，利用堆排序算法进行升序排序，建立的初始堆为(　　)

A.68,45,57,13,24,89
B.89,68,57,13,24,45
C.89,68,57,45,24,13
D.89,57,68,24,45,13

14.一棵二叉排序树中,关键字n所在结点是关键字m所在结点的祖先,则(　　)

A.n一定大于m
B.n一定小于m
C.n一定等于m
D.n与m的大小关系不确定

15.设散列表长m=14,散列函数H(key)=key%11，表中已保存4个关键字：addr(15)=4，addr(38)=5，adr(61)=6，addr(84)=7，其余地址均为空。保存关键字49时存在冲突，采用线性探查法来处理。则查找关键字49时的探查次数是(　　)

A.1
B.2
C.4
D.8

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

11.数据的逻辑结构是从逻辑关系上描述数据,它与数据元素的存储结构_________。

12.指针p和指针q分别指向单链表L中的两个相邻结点,即q> nextp,且p所指结点不是终端结点。若要删除p所指结点,则执行的语句是_________。

13.一个直接或间接调用自己的函数称为_________。

14.广义表(a,(b,c,d),e,f,(g,h))的表尾是_________。

15.二叉树的前序遍历序列和后序遍历序列中,叶结点之间的相对次序_________。

16.如果图G存在拓扑排序序列,则G必为_________。

17.将一棵树T转换为一棵二叉树T1,在T1中结点A是结点B的父结点,则在T中,A可能是B的父结点或_________。

18.对含n个元素的数据序列采用快速排序算法进行排序,在最坏情况下的时间复杂度是_________。

19.散列方法中,表示散列表装满程度的指标a称为_________。

110.假设顺序存储的有序表R含有12个关键字,进行二分查找时,平均查找长度为_________。

三、解答题(本大题共4小题，每小题5分，共20分)

21.设电文字符集是{e1,e2,e3,e4,e5},它们出现的次数分别为:{50,10,16,8,12}。现要为该字符集设计哈夫曼编码。请回答下列问题。(1)画出得到的哈夫曼树。(2)给出各符号的哈夫曼编码。

22.已知图G采用邻接矩阵存储,邻接矩阵如题27图所示。(1)写出从顶点A开始图G的3个不同的深度优先搜索遍历序列。(2)写出从顶点A开始图G的2个不同的广度优先搜索遍历序列。

23.有以下数据序列(19,14,23,01,68,20,84,27,55,11,10,79,12),使用希尔排序方法将其排成升序序列。请回答下列问题(1)写出增量为4时对上述数据序列进行一趟希尔排序的结果。(2)给出一个可行的希尔排序增量序列。

24.设有二叉排序树如题29图所示。请回答下列问题。(1)假定二叉排序树初始为空,写出一个数据输入序列,按序插入时能得到题29图所示的二叉排序树。(2)能得到题29图所示的二叉排序树的不同的输入数据序列有几个?

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.顺序表类型定义如下#define ListSize 100typedef struct{      int data[ListSize];      int length;}SeqLiist;阅读下列算法,并回答问题。void change(SeqList *SL1, SeqList *SL2){        int minlength;         int k=0, temp;         if(SL1->length< SL2->length) return;        minlength= SL2->length;        while( k< minlength)    {           if (SL1->data[k]< SL2->data[k])      {          temp=SL1->data[k];                 SL1->data[k]=SL2->data[k];                SL2->data[k]=temp;      }           k++;       }         return;    }        void f30( SeqList *SL1, SeqList*SL2)  {   if( SL1->length> SL2->length) change( SL1, SL2 ); else change( SL2, SL1 ); return; } (1)若SL1->data中的数据为{25,4,256,9,-38,47,128,256,64},SL2->data中的数据为{22,4,-63,15,29,34,42,3},则执行算法f30(&SL1,&SL2)后SL1->data和SL2->data中的数据各是什么?(2)该算法的功能是什么?

32.二叉树的存储结构类型定义如下:typedef char Data Type;typedef struct node{       DataType data;       //data是数据域        struct node *lchild, * rchild;        //分别指向左右孩子}BinTNode;typedefBinTNode *BinTree;阅读下列算法,并回答问题。void A31( BinTree T){      if(T!= NULL)  { printf( "%c", T->data );      A31(T->rchild );      printf("%c",T->data);       A31(T->lchild );     }     return; }(1)设二叉树T如题31图所示,给出执行A31(T)的输出结果。(2)给出该算法的时间复杂度。

33.待排序记录的数据类型定义如下:#define maXsize 100typedef int KeyType;typedef struct {       KeyType key;} RecType;typedef RecType SeqList [MAXSIZE];下列算法实现自底向上、自顶向下交替进行的双向扫描冒泡排序,请在空白处填上适当内容使算法完整。void f32( SeqList R, int n){       int i=0;        RecType t;       int NoSwap=1;     while(NoSwap) {               NoSwap=0;           for(j=n-i-1; ____(1)____)             if(R[j].key t=R[j];              R[i]=R[j-1];              R[j-1]=t;                NoSwap=1;             }         for(____(2)____; j++)       if(Ri]. key>R[j+1].key){              t=R[i];               R[j]=R[j+1];              R[j+1]=t;            NoSwap=1;      }         ___(3)____;         }}

34.二叉树的存储结构类型定义如下:typedef int DataType;typedef struct node{ DataType key;       //data是数据域  Struct node *lchild, *rchild; //分别指向左右孩子  } BinTNode;typedef BinTNode *BinTree;阅读下列算法,并回答问题void A33(BinTree root, int k1, int k2, int end)  {      if (root==NULL) return;         A33(root->lchild, k1, k2, end);         if (end) return;        if (root->key>k2){           end=1;          return;         }      if (root->key >=k1) printf( "%d", root->key);        A33(root->rchild, k1, k2, end);}(1)设二叉排序树T如题33图所示,bt是指向根结点的指针。给出执行A33(bt,6,100,0)的输出结果。(2)给出该算法的功能。

五、算法设计题(本大题共1小题，共10分)

41.已知二叉树的存储结构类型定义如下:typedef struct node{      int data;      struct node *lchild, *rchild;  } BinNode;  typedef BinNode *BinTree;编写递归算法,对于给定的一棵二叉树T,将其修改为镜像二叉树。例如,题34图所示的两棵二叉树互为镜像二叉树。函数的原型为:vod f34( BinTree T);