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

数据结构自考2016年4月真题及答案解析

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

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

1.下列选项中，属于非线性数据结构的是(　　)

A.队列
B.栈
C.二叉排序树
D.线性表

2.瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序。这里的数据结构指的是(　　)

A.数据的逻辑结构和存储结构
B.数据的线性结构和非线性结构.
C.数据的紧凑结构和非紧凑结构
D.数据的顺序结构和链式结构

3.线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址 (　　)

A.—定相邻
B.—定不相邻
C.不一定相邻
D.可能不相邻

4.数据元素1,2,3,4,5依次入栈，则不可能得到的出栈序列是(　　)

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

5.设顺序表首元素A[0]的存储地址是4000,每个数据元素占5个存储单元,则元素 A[20]的起始存储地址是(　　)

A.4005
B.4020
C.4100
D.4105

6.广义表A=(a,(b,c, (e,f)))，函数head(head(tail(A)))的运算结果是(　　)

A.a
B.b
C.c
D.e

7.设髙度为h的二叉树中， 只有度为0和2的结点， 则此类二叉树包含的结点数至少 是(　　)

A.2h
B.2h-1
C.2h+1
D.h+1

8.一棵非空二叉树T的前序遍历和后序遍历序列正好相反,则T—定满足(　　)

A.所有结点均无左孩子
B.所有结点均无右孩子
C.只有一个叶子结点
D.是一棵满二叉树

9.设图的邻接矩阵A如下所示。各顶点的度依次是(　　)

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

10.无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是(　　)

A.a, b, e, c, d, f
B.a, c, f,e,d, b
C.a,c,b, e,f,d
D.a, e,d, f,c,b

11.设带权连通图G中含有n(≥1)个顶点，下列关于g的最小生成树T的叙述中， 正确的是(　　)

A.T中可能含有回路
B.T中含有图g的所有边
C.T是唯一的，且含有n-1条边
D.T可能不唯一，但权一定相等

12.若要求对序列进行稳定的排序，则在下列选项中应选择(　　)

A.希尔排序
B.快速排序
C.直接插入排序
D.直接选择排序

13.下列排序算法中，空间复杂度最差的是(　　)

A.归并排序
B.希尔排序
C.冒泡排序
D.堆排序

14.下列排序算法中，初始数据有序时，花费的时间反而更多的算法是(　　)

A.插入排序
B.冒泡排序
C.快速排序
D.希东排序

15.对线性表L进行二分查找时,要求L必须满足(　　)

A.以顺序方式存储
B.以顺序方式存储，且数据元素有序
C.以链接方式存储
D.以链接方式存储，且数据元素有序

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

11.下面程序段的时间复杂度是________。i=1;while(i<n)i=i*2

12.在单链表的p结点之后插入s结点的操作是________。

13.只能在线性表的两端进行插入或删除操作的两种逻辑结构分别是________。

14.广义表A=(x,(y,z,(u,v,w)))的长度是________。

15.一棵树的后序遍历序列与其对应的二叉树的________序遍历序列相同

16.在有向图、无向图中,其邻接矩阵一定对称的是________。

17.要计算图中从某一顶点出发到其余各顶点的最短路径,可选用________算法。

18.设关键字序列为28,72,97,63,4,53,84,使用希尔排序法将其排成升序序列,若第一趟采用的间隔是3,则该趟排序的结果是________。

19. 对具有15个关键字的关键字序列进行顺序查找时,查找成功的平均查找长度为_______。

110.在二又排序树的查找过程中,若当前结点的关键字值大于待查找关键字,则应在该________结点的子树上继续查找。

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

21.设Q是有N个存储空间的循环队列,初始状态font=rear=0,约定指针rear指向的单元始终为空。定义如下：#define N 100typedef struct {        char data[N];         int front, rear;}CQ:CQ*Q:(1)写出清空队列的语句序列;(2)写出判断队列为满的表达式;(3)给出计算队列长度L的表达式。

22.已知4×5稀疏矩阵M按行优先顺序存储的三元组表如下：(1)写出矩阵M;(2)给出矩阵M的转置矩阵T按行优先顺序存储的三元组表。

23.给定一组权值数据{3,8,9,11,4},回答下列问题。(1)画出基于所给数据的一棵哈夫曼树;(2)计算所得哈夫曼树的带权路径长度WPL。

24.已知有向图G=(V,E)，其中={v1,v2,v3,v4,v5,v6,v7}，E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>}。(1)画出有向图G:(2)判断图G是否存在拓扑排序序列,若不存在请说明理由;若存在请给出一个拓扑排序序列。

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

31.阅读程序f0。int f30( int A[], int n){    int m;     if (n<=0) return=-1;      if(n==0 )retum=0      m=f30(A,n-1);"    if(A[m]>A[n-1]) return m;else return n-1;}已知线性表A={25,34,256,9,38,47,128,256,64}。(1)若主函数调用语句为f30(A,5),f30的返回值是多少?(2)若主函数调用语句为f30(A,9),f30的返回值是多少?(3)给出算法f30的功能。

32.已知栈的基本操作定义如下,请在空白处填写适当内容,完成相应的功能。  typedef struct { //栈定义       char data[ Stack Size];        int top;} SeqStack;SeqStack s;void InitStack( SeqStack *s)    //栈初始化  {         s->top=-1;}int StackEmpty( SeqStack *s)    //判栈是否为空{      retum ____(1)_____;}    int StackFull( SeqStack *s)   //栈是否为满{        retum s->top== StackSize-1; }  char push( SeqStack*s, char c)      //入栈操作{       if( Stack Full( s ))          return ‘’;           //操作失败        else ____(2)_____=c;         return c;         //操作成功  }    char pop( Seq Stack *s)      //出栈操作{         if( Stack Empty(s))       return 0; //操作失败     else return ____(3)_____; //操作成功}

33.设带头结点的单链表初始为空。将从键盘读入的每个字符作为一个结点加入该链表表尾,当读入回车符时结束并返回链表表头指针。请在空白处填写适当内容,完成其功能。typedef struct node{    char data;       struct node *next;}ListNode;typedef ListNode *LinkList;LinkList f32(){       LinkList head= NULL’       ListNode *p, *rear;       char ch;       head=( ListNode *)malloc( sizeof( ListNode ));      rear= head;       while(( ch=getchar())!=" ')             { ____(1)_____;                  p->data=ch;               ____(2)_____;              rear= p;                }           rear->next=NULL;          ____(3)_____;}

34.给出二叉链表定义如下。程序f33生成原二叉树的镜像树,即将二叉树中所有结点的左、右子树互换。请在空白处填写适当内容,完成其功能。typedef char DataType;typedef struct node {         DataType data;                             //data是数据域         struct node *lchild, *rchild;        //分别指向左右孩子  } BinTNode;; typedef BinTNode"BinTree;  BinTree f33( BinTree T)           {     Bin Tree NewT;                 if(____(1)_____   return NULL;                   ____(2)_____=( BinTree)malloc( sizeof( BinTNode));               NewT->data= T->data;               NewT->lchild=____(3)_____;               NewT->rchild=____(4)_____;                return ____(5)_____;}

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

41.实现f34,对含有n个整数的数组A进行选择排序。函数原型如下。void f34( int A[], int n); //对含有n个整数的数组A进行选择排序