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

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

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

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

1.一个算法的时间耗费的数量级称为该算法的(　　)

A.效率
B.难度
C.可实现性
D.时间复杂度

2.顺序表便于(　　)

A.插入结点
B.删除结点
C.按值查找结点
D.按序号查找结点

3.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是(　　)

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

4.设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为(　　)

A.(rear-front+m)%m
B.rear-front+1
C.(front-rear+m)%m
D.(rear-front)%m

5.下列关于顺序栈的叙述中，正确的是(　　)

A.入栈操作需要判断栈满，出栈操作需要判断栈空
B.入栈操作不需要判断栈满，出栈操作需要判断栈空
C.入栈操作需要判断栈满，出栈操作不需要判断栈空
D.入栈操作不需要判断栈满，出栈操作不需要判断栈空

6.A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素,0的存储地址为1，每个元素占一个存储单元，则的地址为(　　)

A.25
B.26
C.33
D.34

7.树的后序遍历等价于该树对应二叉树的(　　)

A.层次遍历
B.前序遍历
C.中序遍历
D.后序遍历

8.使用二叉线索树的目的是便于(　　)

A.二叉树中结点的插入与删除
B.在二叉树中查找双亲
C.确定二叉树的高度
D.查找一个结点的前趋和后继

9.设无向图的顶点个数为n，则该图边的数目最多为(　　)

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

D.

10.可进行拓扑排序的图只能是(　　)

A.有向图
B.无向图
C.有向无环图
D.无向连通图

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

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

12.下列序列不为堆的是(　　)

A.75,45,65,30,15,25
B.75,65,45,30,25,15
C.75,65,30,15,25,45
D.75,45,65,25,30,15

13.对线性表进行二分查找时，要求线性表必须是(　　)

A.顺序存储
B.链式存储
C.顺序存储且按关键字有序
D.链式存储且按关键字有序

14.分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是(　　)

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

15.下列关于m阶B树的叙述中，错误的是(　　)

A.每个结点至多有m个关键字
B.每个结点至多有m棵子树
C.插入关键字时，通过结点分裂使树高增加
D.删除关键字时通过结点合并使树高降低

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

11.数据元素之间的逻辑关系称为数据的______结构。

12.在线性表中，表的长度定义为______。

13.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为______。

14.在二叉树中，带权路径长度最短的树称为______。

15.已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是______。

16.一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符"d"的哈夫曼编码的长度为______。

17.在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。

18.直接选择排序算法的时间复杂度是______。

19.对于长度为81的表，若采用分块查找，每块的最佳长度为______。

110.用二叉链表保存有n个结点的二叉树，则结点中有______个空指针域。

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

21.假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一 个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0;写出依次执行 下列操作后头、尾指针的当前值。a,b,c,d,e,f入队，a,b,c,d出队; (1) Q.front=______;Q.rear=______。g,h,i,j,k,l入队，e,f,g,h出队; (2) Q.front=______;Q.rear=______。M,n,o,P入队，i,j,k,l,m出队; (3) Q.front=______;Q.rear=______。

22.已知一个无向图如题27图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。

23.用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问：(1)一共需要几趟归并可完成排序。(2)写出第一趟归并后数据的排列次序。

24.一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key%11将记录 散列到散列表HT[0..12]中去，用线性探测法解决冲突。 (1)画出存入所有记录后的散列表。 (2)求在等概率情况下，查找成功的平均查找长度。

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

31.顺序表类型定义如下：# define ListSize 100typedef struct {int data[ListSize];int length; }SeqList;阅读下列算法，并回答问题：(1)若L->data 中的数据为(22,4,63,0,15,29,34,42,3),则执行上述算法后L->data中的数据以及L->length的值各是什么?(2)该算法的功能是什么?

32.有向图的邻接矩阵类型定义如下：#define MVN 100 ∥ 最大顶点数typedef int EType; ∥ 边上权值类型typedef struct{EType edges[MVN][MVN]; ∥ 邻接矩阵，即边表int n; ∥ 图的顶点数｝MGraph; ∥ 图类型例如，一个有向图的邻接矩阵如下所示：阅读下列算法，并回答问题：(1)step1到step2之间的二重循环语句的功能是什么?(2)step2之后的二重循环语句的功能是什么?

33.阅读下列算法，并回答问题：(1)这是哪一种插入排序算法?该算法是否稳定?(2)设置r[0]的作用是什么?

34.顺序表类型定义如下：(1)给出该算法的功能;(2)给出该算法的时间复杂度。

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

41.二叉树的存储结构类型定义如下typedef struct node{int data;struct node *lchild， *rchild;} BinNode;typedef BinNode *BinTree;编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *sum) *count和*sum的初值为0。