自考

各地资讯
当前位置:考试网 >> 自学考试 >> 自考真题 >> 工学类 >> 数据结构 >> 文章内容

排行热点

全国2014年4月自学考试《数据结构》试题

来源:考试网 [ 2015年1月16日 ] 【大 中 小】

全国2014年4月高等教育自学考试数据结构试题

课程代码:02331

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项:

1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

一、单项选择题(本大题共15小题,每小题2分,共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。

1.与数据存储结构无关的概念是

A.栈 B.链表

C.顺序表 D.二叉链表

2.顺序表中有10个数据元素,若第一个元素的存储地址是1000,则最后一个元素地址是1036,第5个元素的地址是

A.1010 B.1016

C.1018 D.1019

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

A.2 B.3

C.4 D..6

4.下列关于队列的叙述中,错误的是

A.队列是一种先进先出的线性表

B.队列是一种后进后出的线性表

C.循环队列中进行出队操作时要判断队列是否为空

D.在链队列中进行入队操作时要判断队列是否为满

5.对稀疏矩阵进行压缩存储的目的是

A.便于运算 B.节省存储空间

C.便于输入输出 D.降低时间复杂度

6.一棵二叉树的第7层上最多含有的结点数为

A.14 B.64

C.127 D.128

7.下列选项为完全二叉树的是

8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是

A. n×e B. e

C. 2e D. n+e

9.无向图中所有顶点的度数之和与所有边数之比是

A.1/2 B.1

C.2 D.4

10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为

A. O(n) B. O(n+e)

C. O(n2) D. O(n3)

11.对序列(15,9,7,8,20,-1,4)进行排序,若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是

A.归并排序 B.快速排序

C.直接选择排序 D.冒泡排序

12.比较次数与待排序列初始状态无关的排序方法是

A.快速排序 B.冒泡排序

C.直接插入排序 D.直接选择排序

13.查找较快,且插入和删除操作也比较方便的查找方法是

A.分块查找 B.二分查找

C.顺序查找 D.折半查找

14.下列关于m阶B树的叙述中,错误的是

A.根结点至多有m棵子树

B.所有叶子都在同一层次上

C.每个非根内部结点至少有[m/2]棵子树

D.结点内部的关键字可以是无序的

15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是

A.线性探查法 B.二次探查法

C.双重散列法 D.拉链法

非选择题部分

注意事项:

用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。

二、填空题(本大题共10小题,每小题2分,共20分)

16.数据结构研究的内容包括数据的逻辑结构、________和数据的运算。

17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是________。

18.普里姆(Prim)算法完成的功能是求图的________。

19.若三维数组a[4][5][6]的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是________。

20.二叉树的线索链表利用________存放遍历时得到的前趋或后继结点的指针。

21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为________。

22.若无向图中任意两个不同的顶点间都有路径,则称该图为________。

23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是________。

24.假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是________。

25.顺序查找算法的平均时间复杂度为________。

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

26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤。例如:将"ABC"改变为"BCA",则其操作步骤为XXSXSS。

27.假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4),为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。

28.设图以邻接表存储,如题28图所示。

(1)写出从顶点v1出发图的深度优先搜索遍历序列。

(2)写出从顶点v1出发图的广度优先搜索遍历序列。

29.(1)一个排序方法稳定的含义是什么?

(2)快速排序是稳定的吗?举例说明。

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

30.阅读下列算法,并回答问题:

void f30(SeqStack S)

{ int k=0;

CirQueue Q;

SeqStack T;

InitQueue(&Q); //初始化队列Q

InitStack(&T); //初始化栈T

while (!StackEmpty(&S))

{ k++;

if (k%2!=0) Push(&T, Pop(&S));

else EnQueue(&Q, Pop(&S));

} //第一个循环

while (!QueueEmpty(&Q)) //第二个循环

Push(&S, DeQueue(&Q));

while(!StackEmpty(&T)) //第三个循环

Push(&S,Pop(&T));

}

设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。调用函数f30(S)后,

(1)第一个循环结束后,栈T和队列Q中的内容各是什么?

(2)第三个循环语句结束后,栈S中的内容是什么?

31.二叉树的二叉链表类型定义如下:

typedef struct node {

DataType data;

struct node *lchild, *rchild;

} BinNode;

typedef BinNode *BinTree;

阅读下列算法,并回答问题:

void f31(BinTree BT)

{ BinNode *s;

if (BT)

{ s=BT->lchild;

BT->lchild=BT->rchild;

BT->rchild=s;

f31(BT->lchild);

f31(BT->rchild);

}

}

(1)该算法的功能是什么?

(2)以下算法功能是否等价于上面的算法?

void f3la(BinTree BT)

{ BinNode *s;

if(BT)

{ f31a(BT->lchild);

f31a(BT->rchild);

s=BT->lchild;

BT->lchild=BT->rchild;

BT->rchild=s;

}

}

32.单链表类型定义如下:

typedef struct node {

int data;

struct node *next;

} ListNode;

typedef ListNode *LinkList;

用不带头结点的单链表存储待排数据,链表头指针为head。下列直接选择排序算法对链表按升序进行排序,请在答题纸相应位置填写适当内容使算法完整。

void f32(LinkList head)

{ ListNode *p, *q, *r;

int tmp;

p=head;

while(p)

{ q=p;

r=->next;

while( (1) )

{ if( (2) ) q=r;

r=r->next;

}

tmp=q->data;

q->data=p->data;

p->data=tmp;

p= (3) ;

}

}

33.实现二分查找的递归章法如下,在答题纸相应位置填写适当的内容使算法完整。

typedef struct{

KeyType key;

InfoType otherinfo;

}NodeType;

typedef NodeType SeqList[n+l];

int f33(SeqList R, int low, int high, KeyType K)

{ int mid;

if(low>high)

return 0;

mid= (1) ;

if(R[mid].key==K)

return (2) ;

if(R[mid].key<K)

f33(R, mid+l, high, K);

else

(3) ;

}

五、算法设计题(本题10分)

34.单链表类型定义如下:

typedef struct node {

int data;

struct node *next;

} ListNode;

typedef ListNode *LinkList;

设计算法在带头结点的单链表L中删除数据值最小的结点(设链表中各结点数据值

均不相同)。函数的原型为:void f34(LinkList L)

责编:liujianting