数据结构2009统考真题

北京师范大学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，

目 录

第一章．概述 ................................................................................................................................................ 1

1．1 本章重点 ...................................................................................................................................... 1 1．2 本章难点 ...................................................................................................................................... 1 1．3 本章习题 ...................................................................

第一章 概述 真题

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.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

第一章 概述 真题

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.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

第 5 章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。【燕山大学 2001 一、2 （2分）】

A. 13 B. 33 C. 18 D. 40

2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 23

06数据结构（50分）

一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共10分）

1.数据的基本单位是（ ）

A.数据项 B.数据类型 C.数据对象 D.数据元素

2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。（ ） A.顺序 B.链式 C.散列 D.任意

3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（ ） A.7，5，3，9 B.9，7，5，3 C.7，5，9，3 D.9，5，7，3 4.下面的说法中，正确的是（ ）

A.字符串的长度指串中包含的字母的个数 B.字符串的长度指串中包含的不同字符的个数 C.一个字符串不能说是其自身的一个子串 D.若T包含在S中，则T一定是S的一个子串 5.广义表（（a，b），（c，d））的表尾是（ ）

A.d B.c，d C.（c，d）

第一章 概述 真题

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.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。

第1章绪论

一、选择题

1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】

A．效率 B. 复杂性 C. 现实性 D. 难度

2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】

A．问题的规模 B. 待处理数据的初态 C. A和B

3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D.易读性、稳定性、安全性

【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】

4．一个算法应该是（）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.

5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】

A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令