您好,欢迎来到尚车旅游网。
搜索
您的当前位置:首页2020年1月全国自学考试试题及答案解析数据结构导论试卷及答案解析

2020年1月全国自学考试试题及答案解析数据结构导论试卷及答案解析

来源:尚车旅游网
…………………………………………………………精品自学考试资料推荐………………………………………………

全国2018年1月高等教育自学考试

数据结构导论试题

课程代码:02142

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

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在数据结构中,数据的基本单位是( ) A. 数据项 C. 数据对象 2.k=1;

for(i=0;ifor(j=0;jA[i][j]=k++;

上述程序段的时间复杂度为( ) A.O(n2) C.O(2n)

B.O(n) D.O(1)

B. 数据元素 D. 数据文件

3.线性表采用链式存储结构时,要求内存中可用存储单元的地址( ) A. 必须是连续的 C. 一定是不连续的

B. 必须是部分连续的 D. 连续和不连续都可以

4.设h是指向非空带表头结点的循环链表的头指针,p是辅助指针。执行程序段

p=h;

while (p->next->next!=h) p=p->next;

p->next=h;

后(其中,p->next为p指向结点的指针域),则( ) A. p->next指针指向链尾结点 C. 删除链尾前面的结点

B. h指向链尾结点 D. 删除链尾结点

5.设顺序表有19个元素,第一个元素的地址为200,且每个元素占3个字节,则第14个元素的存储地址为( ) A.236

B.239 C.242

1

D.245

…………………………………………………………精品自学考试资料推荐………………………………………………

6.一个栈的入栈序列是a,b,c,d,e,则栈的输出序列不可能是( ) ...A. dceab C. edcba

B. decba D. abcde

7.元素大小为1个单元,容量为n个单元的非空顺序栈中,以地址高端为栈底,以top作为栈顶指针,则出栈处理后,top的值应修改为( ) A. top=top B. top=n-1

C. top=top-1

D. top=top+1

8.某二叉树的先根遍历序列和后根遍历序列正好相反,则该二叉树具有的特征是( A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子

D.空或只有一个结点

9.在完全二叉树中,若一个结点是叶结点,则它没有( ) A.左孩子结点 B.右孩子结点

C.左孩子结点和右孩子结点

D.左孩子结点,右孩子结点和兄弟结点 10.邻接矩阵为对称矩阵的图是( ) A. 有向图 B. 带权有向图

C. 有向图或无向图

D. 无向图

11.在一个具有n个顶点的无向图中,要连通全部顶点至少需要的边数为( ) A.n-1 B.n

C.n+1

D.n2 12.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不超过( )

A. n2 B. n

C.

n12 D. n+1

13.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的

C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的

2

) …………………………………………………………精品自学考试资料推荐………………………………………………

14.一个序列中有10000个元素,若只想得到其中前10个最小元素,最好采用的排序方法是

( )

A. 快速排序 C. 插入排序

B. 堆排序

D. 二路归并排序

15.在排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为( ) A.希尔排序 C.冒泡排序

B.插入排序

D.快速排序得分

二、填空题(本大题共13小题,每小题2分,共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。

17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,指针s指向双链表中的一个结点(该结点既非头结点,也非尾结点),则删除s指针所指向结点的操作为“s->tl->r1=s->r1;”和“____________”。

18.对稀疏矩阵进行压缩存储的目的是节省____________。

19.在一个具有n个结点的单链表中查找值为m的某结点,若查找成功,则需平均比较的结点数为____________。

20.深度为15的满二叉树上,第11层有____________个结点。

21.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的左孩子的编号为____________。

22.一个具有4个顶点的无向完全图有____________条边。

23.一个有向图G中若有孤,则在图G的拓扑序列中,顶点Vi,Vj和Vk的相对位置为____________。

24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。

25.实现二分查找的存储结构仅限于顺序存储结构,且其中元素排列必须是____________的。 26.文件的检索有三种方式,它们是顺序存取、直接存取和____________存取。 27.在插入排序和选择排序中,若原始记录已基本有序,则较适合选用____________。 28.对n个元素的序列进行冒泡排序时,最多需进行____________趟。

3

…………………………………………………………精品自学考试资料推荐………………………………………………

三、应用题(本大题共5小题,每小题6分,共30分)

29.写出利用直接选择排序方法对一组关键码为(,38,96,23,15,72,60)的记录进行排序时,每趟排序的结果。

30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA,试画出这棵二叉树。

31.设闭散列表容量为7(散列地址空间0..6),给定表(30,36,47,52,34),散列函数H(K)=K mod 6,采用线性探测法解决冲突,要求: (1)构造散列表;

(2)求查找数34需要比较的次数。

32.如题32图所示,在栈的输入端有6个元素,顺序为A,B,C,D,E,F。能否在栈的输出端得到序列DCFEBA及EDBFCA?若能,给出栈操作的过程,若不能,简述其理由。

题32图

33.已知无向图G的邻接表如题33图所示,请画出该无向图,并写出其按广度优先搜索时的访问序列。其中nil表示空。

题33图

四、算法设计题(本大题共2小题,每小题7分,共14分)

34.编写一个函数void insert(int *p,int size,int a),其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是:首先采用折半查找的方法,找出要插入数据的位置;然后按升序将数据插入该数组中。

4

…………………………………………………………精品自学考试资料推荐………………………………………………

35.某带头结点的单链表的结点结构说明如下:

typedef struct node1 {

int data;

struct node1 *next

}node;

试设计一个算法int copy(node *head1, node *head2),将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。

5

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- sceh.cn 版权所有 湘ICP备2023017654号-4

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务