自考数据结构历年真题

北京师范大学08年考研程序设计与数据结构试题

考研_考试大 [ 2008/11/17 ] 来源：北京师范大学

一、简答题（20分）

1.数据类型和抽象数据类型的含义 2.算法的特性与算法的时间复杂度

3.快速排序方法最好和最坏的情况是什么？简要分析说明 4.栈、队列的共同点与不同点，说明其属于线形表的原因 二、方法选择（20分）

1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？

2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？

三、（40分，每题8分）

1.已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间） 2.给出求N阶hanoi塔的函数定义如下：Hanoi （ int n，char x，char y ，char z ）

{ if （ n= =1） move （ x ，1，z） Else{ hanoi（ n-1， x，z，

全国2001年10月高等教育自学考试

数据结构试题

课程代码：02331 第一部分 选择题(30分)

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只

有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．算法指的是（ ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的

D．和头结点的存储地址相连续

3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4．由两个栈共享一个向量空间的好处是：（ ） A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率

5．设数组data[m]作为循环队列SQ的存储

第一部分 选择题(30分)

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只

有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的

时间复杂度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3） 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表

0 2 3 3 5 对应的稀疏矩阵是（ ） ?0?8?70? A.?00???50??00?0?8?00? C.?02???50??0006??0?8?7000????00 B.??50??40??00?00?3??006?00??40?

?00?00??n3?0?8006??00000???0000? D.?7??40???50400????0306?0??0? ?0?0??12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有

弧的时间复杂度是( )

A．O(n) B．O(

第一部分 选择题(30分)

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只

有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的

时间复杂度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3） 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表

0 2 3 3 5 对应的稀疏矩阵是（ ） ?0?8?70? A.?00???50??00?0?8?00? C.?02???50??0006??0?8?7000????00 B.??50??40??00?00?3??006?00??40?

?00?00??n3?0?8006??00000???0000? D.?7??40???50400????0306?0??0? ?0?0??12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有

弧的时间复杂度是( )

A．O(n) B．O(

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

全国2004年10月高等教育自学考试

数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题干的括号内。错选、多选或未选均无分。

1．下列各式中，按增长率由小至大的顺序正确排列的是( ) A．n，n！，2，n C．2n，log n，nlogn，n3/2

n

3/2

B．n，2，n

3/2nlogn

，2

100

D．2100，logn, 2n, nn

2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) A．s->next=p->next; p->next=s; C．p->next=s->next; s->next=p;

B．p->next=s; s->next=p->next; D．s->next=p; p->next=s->next;

3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两

江西财经大学

学年 第 学期期末考试试卷

试卷代码：03265A卷 课时：96

课程名称：数据结构 适用对象：信息管理与信息系统 一、名词解释（每小题2分，共10分） 1、抽象数据类型 2、排序的稳定性 3、二叉排序树 4、冲突 5、哈希表

二、填空题（每空1分，共14分）

1、通常要表达一种数据结构，要说明 、 、 三方面。 2、带头结点的双向循环链表，空链表的条件是 。

3、已知一棵度为3的树有3个度为1的结点，3个度为2的结点，3个度为3的结点，则该数有 个叶子。

4、有一个长度为21的有序表采用二分查找方法进行查找，共有 个元素查找长度为5。 5、假设一完全二叉树共378个结点，则其中有 个叶子。

6、在内部排序中，需求附加内存容量最大的是 排序。

7、在长度为N的顺序表中的第i（1<=i<=N+1）个元素位置插入一个元素，元素的移动次数为 。

8、循环队列Q中，利用浪费一个空间的办法处理队列，则队空的条件是 ，队满的条件是 。

9、设深度为h的

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

2016年10月高等教育自学考试全国统一命题考试

数据结构 试卷

(课程代码02331)

本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项：

1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。

第一部分 选择题(共30分)

一、单项选择题(本大题共l5小题，每小题2分，共30分>

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列选项中，不属于线性结构特征的是

A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 2．设l7个元素的顺序表中，若将第

个元素e移动到第

个位置，

不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是

3．若用一个大小为

7的数组作为循环队列的存储结构，且当前rew和盘

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

第一章 概述 真题

16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++)

for(j=1；j<=n；j++)

for(k=1；k<=n；k++)

s=i+j+k；

17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

16.下列程序段的时间复杂度为________。

i=0；s=0；

while（i

17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。

1.数据的不可分割的最小标识单位是（ ）

A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)

16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。