数据结构考研试题.doc

[ 注] ：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注

释一、回答下列问题： [20 分 ]

1、算法的定义和性质

2、为什么说数组与广义表是线性表的推广？

3、什么是结构化程序设计？

4、哈希方法的基本思想

5、给出一不稳定排序方法名称与实例

二、构造结果：[24分]

（1）确定 x:=x+1 语句在下面程序段中的频率，要求写出分析过程。

for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2）画出对长度为 8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均

查找长度。

（3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4）假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为{2 ， 3， 5，7， 11， 4， 13， 15} ，试为这 8 个字母设计哈夫曼编码．

（ 5）在地址空间为0~15 的散列区中，对以下关键字序列构G 造哈希表，关键字序列为（ Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec ）， H(x)=[i/2]，其中i 为关键字中第一

字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找

成功的平均查找长度。

（6）构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。

三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。

[15 分 ]

[15 分 ]

四、编写一非递归算法，对一棵二叉排序树实现中序遍历。

五、编写程序，完成下列功能：[15 分 ]

1．读入整数序列，以整数0 作为序列的结束标志（0 不作为序列元素），建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，

可使用临时工作单元。

例：输入序列为：1， 8， 4，3， 0

六、给出有向图 G 的邻接表表示。找出其一棵最小生成树。[11 分]

[ 注] ：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注

释一、回答下列问题： [20 分 ]

1、算法的定义和性质

2、为什么说数组与广义表是线性表的推广？

3、什么是结构化程序设计？

4、哈希方法的基本思想

5、给出一不稳定排序方法名称与实例

二、构造结果：[24分]

（1）确定 x:=x+1 语句在下面程序段中的频率，要求写出分析过程。

for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2）画出对长度为 8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均

查找长度。

（3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4）假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为{2 ， 3， 5，7， 11， 4， 13， 15} ，试为这 8 个字母设计哈夫曼编码．

（ 5）在地址空间为0~15 的散列区中，对以下关键字序列构G 造哈希表，关键字序列为（ Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec ）， H(x)=[i/2]，其中i 为关键字中第一

字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找

成功的平均查找长度。

（6）构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。

三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。

[15 分 ]

[15 分 ]

四、编写一非递归算法，对一棵二叉排序树实现中序遍历。

五、编写程序，完成下列功能：[15 分 ]

1．读入整数序列，以整数0 作为序列的结束标志（0 不作为序列元素），建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，

可使用临时工作单元。

例：输入序列为：1， 8， 4，3， 0

六、给出有向图 G 的邻接表表示。找出其一棵最小生成树。[11 分]

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，应加上必要的注释

所有答案均要求写在答题纸上

一、回答问题[15 分]

1．结构化程序设计

2．面向对象开发方法与面向过程开发方法的不同之处

3．数据类型含义与作用

4．稳定排序与不稳定排序

二、简述方法与原因[20 分]

1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原

因。

2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方

法，若不能，请简述原因。

3.有 n 个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。

4．说明在图的遍历中，设置访问标志数组的作用。

5.在一个连通无向图上，欲求从一点 V I到另一点 V J（V I≠V J）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。

三、构造结果[25 分]

1.二叉树按二叉链表方式存放，其中的data 域为 char 类型，已

有按前序方式构造二叉树的算法，若输入序列为AB□CD□□ ED□G□□□，请给出构造的相应二叉树。

2.已知 Ackerman函数定义如下：

n+1 当m=0时

akm(m,n) = akm(m-1,1)当m≠0,n=0时

akm(m-1, akm(m,n-1))当m≠0,n≠0时

写出 akm(2,1) 时调用时变化过程与执行结果。

3.对于正整数 A、B，说明下面程序段定义了什么函数功能，要求重写程序段，

使之完成原函数功能，且执行时间仅可能短。

Unsigned int f(a,b)

int a,b;

{if (a*b==0)

return (a+b)

else return(f(b-(b/a)*a,a);( 注： b/a 相当整除)

}

4.写出在中序线索树 BT 中找结点 X 的后继结点的函数过程。

5. 对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7 的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。

四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲

得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。 [10 分]

1．一棵树采用孩子 - 兄弟方式存放，结点结构为

fc da ns le

h ta ib ve

l

其中 fch 表示指向第一个孩子， nisib 表示指向下一个兄弟, level 表示结点层次。设根结点层次为 1，其它以此类推，编写一算法，将树中所有结点层

次值置入相应 level域。[10分]

六、以顺序存储结构表示串 , 设计算法 , 求串 S中出现的第一个最长重

复子串及其位置并分析算法的时间复杂度.[10 分]

七、编写程序，要求完成：

建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。

在此链表上实现对二进制数加1的运算，并输出运算结果。[10 分]

[ 注] ：编写程序可用 PASCAL 或 C 语言；算法描述可采用类语言，加上必要注释；

一、解释和简答下列问题：（20分）

1）算法的定义和特性

2）抽象数据类型

3）广义表与字符串属于线性表的理由

4）封装

5）排序算法的稳定性

6）结构化程序设计

二、写出要求结果：（ 30分）

1．已知一二叉树中序序列为DBGEAFC ，后序序列为DGEBFCA ，给出其对应的二叉树。

2．给定权值 {8 ，12，4， 5， 26， 16， 9} ，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。

1．有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数

实现，你认为应采用什么方法？

4．只想得到 N 个元素序列中第 K 个最大元素之前的部分递减有序序列（ K<

5 ．在地址空间为 0~12 的散列区中，对以下关键字序列建哈希表：

（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct ）。用线性探测法处理冲突，求出在等概率的情

况下查找成功与不成功的平均查找长度。

6．下面给出求N 价 hanoi 塔的过程：

PROCEDURE hanoi(n： integer；x,y,z： char)；

begin

if n=1 then move(x,1,z)

else [hanoi(n-1,x,z,y) ；

move(x,n,z) ；

hanoi(n-1,y,x,z)]

end

请写出执行hanoi(3,a,b,c) 时递归过程的实在参量变化过程及move 的搬动过程。

三、数学归纳法证明非空满K 叉树的叶子结点数目为(K-1)N+1 ，其中 N 为分支结点数目。

（ 10分）

四、编写程序，判断一带头结点的双向链表是否对称，对称是指表中各元素满足a i=a n-i+1 结点结构为如下：(10分 )

next

dada

prior

五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对

这一书目单按字典排序，将结果以文件方式存储。编程实现之。（ 10分）

六、二叉树按链表方式存放，且树中结点的关键字均不同。写一个判别给定二叉树是否

为二叉排序树的非递归算法。（ 10分）

写一个算法，确定一个 N 个顶点的无向图是否包含回路，此算法的时间代价应为O（ N）（ 10 分）

[ 注] ：编写程序可选用盘Pascal 或 C 语言，算法描述可选用类语言，必要时加上注释

一、简答下列问题：

1．结构化程序设计

2．参数传递的常用方式及含义

3．数据类型

4．几种基本数据结构的名称及特征

5．算法定义与性质

6．

二、写出要求结果

1． PROGRAM PF(OUTPUT);

VER T,M:INTEGER;

FUNCTION F(N:INTEGER):INTEGER;

BEGIN

M:=N+M;F:=M

END

BEGIN

M:=10;T:=(M+1)*F(10);WRITELN(T);

M:=10;T:=F(10)*(M+1); WRITELN(T);

M:=10;T:=M*F(10)+F(10); WRITELN(T);

END.

写出程序输出结果，说明为什么T 的树出结果不同。

2．有过程定义如下：

PROCEDURE PRIT(N:INTEGER);

BEGIN

VAR N1:INTEGER;

N1:=TRUNC(N/10);{TRUNC(x)表示取x的整数部分}

S:=S*10+(N MOD 10);

IF N1<>0 THEN PRIT(N1);

WRITELN(N MOD 10)

END;

问：置 S 初值为 0，用 PRIT （ 12345）调用此过程，写出打印结果；当执行完此次调用

后， S 值是多少？

3．给定一组权值（7，18，3，32，5， 26，12，8），构造一棵哈夫曼树，并计算带权路径长度。

4．将树转换成二叉树

5．对给定以下关键字序列（Jan,Feb,Mar,Apr,May,

Jun,Jul,Aug ），哈希函数H（ Key ） Key 的第一字母

表中序号 MOD 7，采用性探再散列方法理冲突，

要求：①构造一个装填因子0.8的哈希表

②求出等概率情况下找成功与找不成功的平均找度

6．在 m 行 n 列的稀疏矩中，有七个非零元素，若用十字

表表示，共需要多少个点？

三、写一程序，要求打印以下的三角形（n 可 10） [10分]

1

1 1

1 2 1

n 行 1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

2 1 6 15 20 15 1

:

四、一个数中元素正数或数，写一程序，完成在O[n] 内原地重排数，不要

求整个排序，只要求数排在正数之前。[10分]

五、二叉按二叉表方式存放：

① 写任一二叉中非端点数目的非算法[10 分 ]

② 写求一二叉高度的算法。[5分 ]

六、有向以接表方式存，利用列技写一个判中是否存在由点V i到点V

j 路径的算法。（其中i≠j）[12分]

七、已知有如下表（ a1,a2,?? ,an）,n 偶数。

要求写出一个复度O[n] ，助空O(1) 的算法，将上述表成：

即（ an,an-2,?? a2,a1,a3,?? an-1）

[ 注] ：编写程序可选用任一种高级语言（ C 或 PASCAL 等）一、简答问题：[15 分]

1.结构化程序设计；

2.简述面向对象开发方法的特点；

3.何谓程序中的千年虫问题，简述一种解决问题的方法；

4.给出抽象数据类型和特征，并举例说明；

5.简述广义表属于线性结构的理由。

二、写出要求结果[45分 ]

1.有函数定义如下：

FUNCTION GC(M,N:INTEGER);INTEGER

BEGIN

IF N=0 THEN GC:=M

ELSE GC:=GC(N ， M MOD N)

END

写出此函数功能，并改写它，使其执行速度仅可能地短。

2.设 T 、 M 为全程量，有函数定义如下：

FUNCTION FA(N:INTEGER) ： INTEGER

BEGIN

M:=N+M;FA:=M;

END

在主程序段中，有如下语句：

M:=10;T:=(M+2)*FA(10);WRITELN(T);

M:=10;T:=FA(10)*(M+2);WRITELN(T);

写出程序输出结果，说明为什么3. 对以下关键字序列建立哈希表：T 的输出结果不同的原因。

（ SUN,MON,TUE,WED,THU,FRI,SAT ） ,哈希函数为

H(K)=（关键字中第一个字母在字母表中的序号） MOD 7。用线性探测法处理冲突，要求构造一个装填因子为 0.7的哈希表，并分别计算出在等概率情况下查找成功与

不成功的平均查找长度。

4. 在数轴上有 N 个彼此相邻不交的区间，每个区间的下界和上界都是整数。N 个区间

顺序为 1~N 。要查找给定的 X 落入的区间号，你认为应怎样组织数据结构，选择什

么方法最快，并简述原因

5. 对 N 个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N 个元素

的初始排列，对 N=7 ，给出快速排序的一个最好情况的初始排列实例（7 个元素可取自集合 {1 ， 2， 3，4， 5， 6，7} ）。

6.在前序线索树上，要找出结点P 的直接后继结点，请写出相关语句。

ltag lc data rtag rc

7. 给出循环队列中元素个数的计算式（设队列的最大长度为N ，队首指针FRONT ，队

尾指针为 REAR ）。

8.有向图的拓扑排序能否用图的深度搜索模式来查找？若能，请简述方法，若不能，

请简述原因。

9.写出三个形如 A:=B 的语句，完成将单链表 LA 整表释放的功能，可利用链栈指针 AV

（即将 LA 表归还到可利用栈）。

三、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串

中的合法字符为A~Z 这26个字母和 0~9这 10个数字） [10分 ]

四、已知两个线性表 A 、B，均以带头结点的单链表作存储结构，且表中元素按值递增有序

排列。设计算法，求出 A 与 B 的交集 C，要求 C 另开辟存储空间，要求 C 同样以元素值的递增有序的单链表形式存贮。[8分 ]

五、要求二叉树按二叉链表形式存储。

（1）写一个建立二叉树的算法。

答案请答在答题纸上，答在本试题上的答案一律无效

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上

一、简答问题： [30 分]

1．结构化程序设计

2．面向对象程序设计与面向过程程序设计各自的特点与区别

3．简述队列与广义表属于线性表的理由

4．简述不稳定排序含义、并给出证明某一种排序方法是不稳定的排序方法

5．函数的副作用

二、选择题：[20 分]

1．下面方法可以判断出一个有向图中是否有环（回路）

A．深度优先遍历 B. 拓扑排序 C.最短路径 D.关键路径

2.已知一算术表达式的中缀形式为 A＋B *C-D/E，后缀形式为 ABC*+DE/- ，其前缀形式为。

A. –A+B*C/DE

B. –A+B*CD/E

C. -+*ABC/DE

D.-+A*BC/DE

3.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，

利用遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

4.排序趟数与序列的原始状态有关的排序方法是排序法。

5.下面给出的四种排序法中排序法是不稳定性排序法。

A．插入 B．冒泡 C．二路归并 D．堆

6.若需在 O（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，

则可选择的排序方法是 :

A．快速排序 B. 堆排序 C.归并排序 D.直接插入排序

7.下述二叉树中，满足性质：从任一结点出发到根的路径上所经过的结点序列

按其关键字有序

A. 二叉排序树

B. 哈夫曼树

C. AVL树

D.堆

8．下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反

而最多。

A、堆排序

B、冒泡排序

C、快速排序

D、SHELL 排序

9．设循环队列中数组的下标范围是1~n，其头尾指针分别为 f ，r ，若队列中元素个数为。

A、r-f B 、r-f+1C、（r-f+1 ）mod n D、（r-f+n ）mod n

10.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有

序序列

A、存在

B、不存在

三、写出要求结果： [50 分]

1．下列C与PASCAL函数的功能相同

有如下 C 函数定义：有如下 PASCAL 过程定义：

void bin(int b[ ], int n) PROCEDURE bin （ VAR b： array， n： integer）

{ BEGIN

if (n==1) {b[1]=1; b[2]=1;} if (n==1) {b[1]=1;b[2]=1;}

else { bin(b, n-1); else { bin(b, n-1);

b[n+1]=1; b[n+1]=1;

For (i=n; i>=2; i--) For i=n downto 2 do

b[i]= b[i]+ b[i-1] b[i]= b[i]+ b[i-1]

}

} END

若调用 bin(A, 5), 给出 A 数组中第 1个至第 6个数组元素的输出结果。

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,y)；

move(x,n,z) ；

hanoi(n-1,y,x,z)

}

}

请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程。

3．已知一个循环单链表 la,av 是可利用栈的头指针，请用 3个赋值语句，完成将整个循环单链表释放的功能（即将 la 表整个归还到可用空间栈）。

4.在地址空间为 0-12 的散列区中，对以下关键字序列：

（ Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）建哈希表，设哈希函数为 H（X ）=i/2，其中 i 为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法

或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。

5．在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借

助于一棵折半判定树来模拟，树中结点的值为记录在文件中的位置序号。

①若文件中有 l7个记录，请画出这棵折半判定树；

②当文件中有 n 个记录时，给出该判定树的深度。

6．设某城市有N个车站，并有M条公交线路连接这些车站，设这些公交车都是单向的，这 N 个车站顺序编号为 0至 N-1，要求输入该城市的公交线路数、车站个数以及各公交线路上各站编号，要求从站 0出发乘公交车至站 N-1的最少换车次数，简述应如何设置数据结构、应当采用的基本处理方法。

7．下图是带权的有向图 G的邻接表表示法。给出从结点V1到结点 V8的最短路径。

8．在后序线索树中，要找出X 结点的前趋结点，请写出相关语句Ltag Lc Data Rtag Rc

四．编写程序，实现在链式存储方式下的模式匹配。

设主串 s 和子串 t 分别以单链表存储， t 和 s 中每个字符均用一结点表示：data Next

实现在链式存储方式下的模式匹配，即求子串t 在主串 s 中第一次出现的位置指

针。 [12分]

五、编写算法：

已知二叉树采用二叉链表方式存放，其中要求对二叉树从1开始进行连续编号，要求每个结点 v 的编号等于其左子树上最小编号加 1，结点 v 的编号等于其右子树结点中最大编号加 1，请回答采用什么次序的遍历方式实现编号？并给出在二

叉树中结点的数据域部分填写实现如上要求编号的非递归算法。[13 分]

六、编写算法：

h

已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT〔1：2－1〕中，请写一算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为

根结点所在链结点的指针由BT 给出。 [13 分]

七、编写程序：

已知全省有 m个学生参加计算机等级考试，其成绩值均为界于 0～100之间的整数值，且成绩中有许多值重复出现多次，请按下列方法进行排序：另设数组

num[0:100] ，且令 num[i] 计算统计整数 i 在成绩数组中重复出现的次数，之后

按 num重排成绩数组，以达成绩数组递增有序。编写程序实现上述要求。

[12

分] （2）写一个判别给定的二叉树是否是完全二叉树的算法。

完全二叉树定义为：深度为 K 、具有 N 个结点的二叉树的每一个结点都与深度为 K 的满二叉树中编号从 1至 N 的结点一一对应（此题以此定义为准）。 [12分 ]

六、给定一公园的导游图，自给适当的数据结构，编写算法实现下列要求：

游客从大门进入，选择一条最佳路线，使游客可以不重复的游览各景点，最后回到大

门。 [10分 ]

答案请答在答题纸上，答在本试题上的答案一律无效

[注] 编写程序可选用PASCAL 或 C 语言

算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上

一、简答问题： [30 分]

1．结构化程序设计（目的、构成与方法）

2．简述栈、队列、串、数组的共同点和不同点，它们属于线性表原因

3．简述面向对象方法的特点

4．线性结构与非线性结构的差别

5．算法特性与算法时间复杂度

二、选择题：[20 分]

1．已知一算术表达式的中缀形式为 A＋B*C-D/E，后缀形式为 ABC*+DE/- ，其前缀形式为( ) 。

A. –A+B*C/DE

B. –A+B*CD/E

C.-+*ABC/DE

D.-+A*BC/DE

2．利用逐点插入法建立序列 (50 ，72，43，85，75，20，35，45，65，30) 对应的二叉排序树以后，查找元素 35要进行（）元素间的比较。

A．4次 B．5次 C. 7次 D．10次

3．在有 n 个叶子结点的哈夫曼树中，其结点总数为( ) 。

A、不确定

B、2n

C、2n+1

D、2n-1

4．若需在 O（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则

可选择的排序方法是:

A．快速排序 B. 堆排序 C.归并排序 D.直接插入排序

5．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑

有序序列( )

A. 存在

B. 不存在

6．将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是( )

A. n

B. 2n－1

C. 2n

D. n-1

7．下述二叉树中，哪一种满足性质：从任一节点出发到根的路径上所经过的

节点序列按其关键字有序 ( )

A. 二叉排序树

B. 哈夫曼树

C. AVL树

D. 堆

8．已知待排序的n 个元素可分为n/k 个组，每个组包含k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )

A. O（nlog2n ）

B. O(nlog2k)

C. O(klog2n)

D. O(klog2k)

9．数组A[1..5,1..6]的每个元素占 5 个将单其元按，行优先次序存储在起始地址

为1000的连续内存单元中，则A[5，5] 的地址是( ) 。

A、1140

B、1145

C、1120

D、1125

10.在有n个叶子结点的哈夫曼树中，其结点总数为() 。

A、不确定

B、2n

C、2n+1

D、2n-1

三、写出要求结果： [50 分]

1．下列C与PASCAL函数的功能相同

有 C 函数定义如下：有PASCAL过程定义如下：

int gc(:int m, n) FUNCTION GC(M,N:INTEGER);INTEGER

{ BEGIN

if (n==0 ) return(m); I F N=0 THEN GC:=M

else retun (n， m /n); ELSE GC:=GC(N ， M MOD N)

} END

写出此函数功能，并改写它，使其执行速度仅可能的短。

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,y) ；

move(x,n,z) ；

hanoi(n-1,y,x,z)；

}

}

请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程。

3．在前序线索树中，要找出X 结点的后继结点，请写出相关语句

Ltag Lc Data Rtag Rc

4．一棵非空的二叉树其前序序列与后序序列正好相反，给出满足条件的二叉树。

5．在数轴上有 n 个彼此不交的相邻区间，每个区间下、上界都是整数，按区间

位置从左到右依次编号为1~N。试问：要查找某个给定值x 所在区间，你认为应

选择什么方法查找最快，简述原因。

6．已知关键字序列为：（75, 33,52, 41, 12, 88, 66, 27 ）哈希表长为10 ，哈

希函数为： H(K)=K MOD7, 解决冲突用线性探测再散列法，要求构造哈希表，并

求出等概率下查找成功与不成功的平均查找长度。

，K<

（列出 3种速度快的方法名称与原因。

8．已知二叉排序树，现要求得到结点的递减有序的排列，请说明实现此要求应

采用的方法思路。

四、编写程序，求字符串中的字符平台。

一个字符串中的任意一个子序列，若子序列中各字符均相同则称为字符平台。编程

要求；输入任意一字符串 S 时，输出 S 中长度最大的所有字符平台的起始位置及所

含字符，注意字符平台有可能不止一个。 [10 分]

五、编写算法，要求完成：

已知二叉树采用二叉链表方式存放，要求对二叉树从 1开始进行连续编号，要求每

个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的

编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。[13 分]

六、编写算法：

（1）要求二叉树按二叉链表形式存储，写一个建立二叉树的算法。

（2）编写计算二叉树最大宽度的算法。

二叉树最大宽度指：二叉树所有层中结点个树的最大值[15 分]

七、编写算法：

树采用孩子 - 兄弟方式存放，结点结构为

fch da ns lev

ta ib el

其中 fch 表示指向第一个孩子， nisib 表示指向下一个兄弟, level 表示结点层次。设根结点层次为 1，其它以此类推，

编写一算法，将树中所有结点层次值置入相应 level 域，并要求由根开始逐层输出树中的各条边，边输出格式为（ Ki,Kj ）。 [12 分]

例： A

B C D 输出为：AB,AC,AD,BE,BF,CG

E F G

2019年考研《计算机数据结构》考试试题

2019年考研《计算机数据结构》考试试题 一、选择题(24分) 1.下列程序段的时间复杂度为( )。 i=0，s=0; while (s (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则 选用下列( )存储方式最节省运算时间。 (A) 单向链表(B) 单向循环链表 (C) 双向链表(D) 双向循环链表 3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。 (A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p; (C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q; 4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 5.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为( )。 (A) 10 (B) 19 (C) 28 (D) 55

6.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有( )个叶子结点。 (A) (B) (C) (D) 7. 二叉排序树中左子树上所有结点的值均( )根结点的值。 (A) < (B) > (C) = (D) != 8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度 为( )。 (A) 129 (B) 219 (C) 189 (D) 229 9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有( )个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y

计算机考研数据结构真题汇总

一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n)

计算机考研数据结构试卷一(练习题含答案)

数据结构试卷1 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放 位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚 注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中， 现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 n） D. O（n2） A. O（1） B. O（n） C. O（1og 2 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选 用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通 图。 A.5 B.6 C.7 D.8 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和 _________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含 的结点数为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应 的后缀算式为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩 子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针

计算机数据结构考研真题及其答案

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）; A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）; A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（），它必须具备（）这三个特性; (1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）; A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 5. 下面关于算法说法错误的是（）; A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）; (1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类; A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）; A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）; A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）; A．栈 B. 哈希表 C. 线索树 D. 双向链表

南京邮电大学2005年数据结构考研试卷

南 京 邮 电 学 院 2005年攻读硕士学位研究生入学考试 数 据 结 构 试 题 一、单选题（每题3分，共30分） 1. 设使用某算法对n 个元素进行处理，所需的时间是 T(n) = 100n log 2n + 200n + 2000 则该算法的渐进时间复杂度为 。 A. O(1) B. O(n) C. O(200n) D. O(nlog 2n) 2. 设顺序表的长度为n ，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是 。 A. (n －1)/2 B. n/2 C. n(n －1)/2 D. n(n ＋1)/2 3. 如果只保存一个n 阶对称矩阵a 的下三角元素（含对角线元素），并采用行主序存储在一维数组b 中，a[i][j]（或a[i, j]）存于b[k]，则对i

2018计算机考研：计算机数据结构测试题(九)

2018计算机考研：计算机数据结构测试题(九) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(九) 一、选择题(24分) 1.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )。 (A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M

4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为( )。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5.设某完全无向图中有n个顶点，则该完全无向图中有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 6.设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。 (A) 9 (B) 10 (C) 11 (D) 12 7.设某有向图中有n个顶点，则该有向图对应的邻接表中有( )个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为( )。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8 二、填空题(24分) 1. 1. 为了能有效地应用HASH查找技术，必须解决的两个问题是 ____________________和__________________________。 2. 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x)

大数据结构考研真题及其问题详解

一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【理工大学 1999 一、1（2分）【交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈

数据结构考研真题及其答案完整版

数据结构考研真题及其 答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈 9．以下数据结构中，哪一个是线性结构（ D ） 【北方交通大学 2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关（ A ）【北方交通大学 2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（C ）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO

数据结构考研试题精选及答案第1章绪论

绪论 一、选择题 1.算法的计算量的大小称为计算的( 复杂性 A.效率 B. 2. 算法的时间复杂度取决于 A.问题的规模 3. 计算机算法指的是( (1) A .计算方法 法 (2) A .可执行性、 B. 1), B. 4. 5. )。【北京邮电大学 2000二、3 (20/8 C. 现实性 D. 难度 、1 (2 分)] ( )【中科院计算所1998 待处理数据的初态 它必须具备( 排序方法 C. A 和 B 这三个特性。 C. 解决问题的步骤序列 D. 分) 】 调度方 可移植性、可扩充性 B. 可执行性、确定性、有穷性 易读性、稳定性、安全性 、1 ( 4 C.确定性、有穷性、稳定性 【南京理工大学 1999 一、1 (2分) 一个 算法应该是( )。【中山大学 A .程序 B .问题求解步骤的描述 下面关于算法说法错误的是( A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D.以上几个都是错误的 下面说法错误的是( )【南京理工大学 2000 一、2 (1.5分)] (1 ) (2) (3) (4) A . D. 【武汉交通科技大学 1996 1998 二、1 (2 分)】 C .要满足五个基本特性 D . A 和C. 分) 】 )【南京理工大学2000 一、1 (1.5分)】 )【南京理工大学 2000 算法原地工作的含义是指不需要任何额外的辅助空间 在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度 O(2n )的算法 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 同一个算法，实现语言的级别越高，执行效率就越低 (1) B.(1),(2) 7.从逻辑上可以把数据结构分为 A.动态结构、静态结构 C.线性结构、非线性结构 &以下与数据的存储结构无关的术语是 A.循环队列 B. 链表 9.以下数据结构中，哪一个是线性结构 A.广义表 B. 二叉树 10 .以下那一个术语与数据的存储结构无关？ A.栈 B. 11 .在下面的程序段中， 分)] 6. C.(1) ,(4) D.(3) ( )两大类。【武汉交通科技大学 1996 一、4 ( 2分)] B .顺序结构、链式结构 .初等结构、构造型结构 )。【北方交通大学 2000二、1 (2分)] 哈希表 D. 栈 )?【北方交通大学 2001 一、1 (2分)] 稀疏矩阵 ) 线索树 C. C. 哈希表 C. 对 x 的赋值语句的频度为( D.串 【北方交通大学2001 一、2 (2分)】 D. 双向链表 )【北京工商大学 2001 一、10 (3 FOR i:=1 FOR j:=1 x:=x+1; A. O(2 n) TO TO DO DO .0(n) 2 C . O(n) D .O(log 2n ) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO

天津大学数据结构和程序设计考研真题

天津大学数据结构和程序设计考研真题-考研资料-笔记讲义 许多学生在考研复习的时候，都会遇到重点不明确，不知道从何复习的情况。为此，天津考研网建议，考研复习中，专业的考研复习资料，是帮助考生能够快速掌握复习重点及方法必不可少的因素，然后就是真题和讲义，可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班，以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作，该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹，该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等，从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。 特别说明：此科目06年以前科目名称为数据结构；自06年到08年科目名称改为计算机基础（包含数据结构、程序设计、计算机原理）；自09年开始全国统考，科目名称为计算机学科专业基础综合；自2013年开始由学校自主命题，科目名称改为901数据结构与程序设计。 第一部分由天津考研网提供的核心复习资料： 天津大学数据结构和程序设计资料编者序言：本文的重点在于C++，数据结构的复习和复试基本情况介绍。C++、数据结构又分别从复习规划，复习用书，重点知识点结合历年考题这四个方面来展开的。复习规划大家务必看一下，然后根据自己的实际情况在制定自己的复习时间，因为内容很多，大多数同学都在考试之前复习不完，在心理因素上就落了一节。重点知识点一定要看了，这些知识点几乎每年都会有题了。另外我还给了历年试题的答案供大家参考。有的答案是自己做的答案，可能会有疏忽的地方。望大家提出宝贵的意见和建议。复试的东西现在了解一下即可，等到进复试了，还是有足够的时间看的。另外我还给了些自己复习心得。考完后感慨很多，回顾了这多半年来自己的成败得失。希望大家从一开始就沿着比较高效的方向前进，减少不必要时间的浪费。本资料格式为A4纸打印版，总量达到了130页共计50000余字，清晰易复习，已于编写者签订资料保真转让协议，各位研友可放心使用参考！特别提示：本站尽力保证资料的有用性，但由于个人复习态度进度不同，故请酌情参考本资料！ 天津大学数据结构和程序设计考研真题等资料目录 一、学院专业综述 二、近年来的录取情况及分数线 三、05、06年专业课试题的变化及其今后的趋势 四、复习策略和复习时间的统筹安排及所需要的辅助资料 五、C++和数据结构复习规划及复习侧重点(特别是05，06年的变化) 5七、复习经验与教训(学习生活心理诸方面) 八、关于数学和政治复习的小小的建议 九、计算机复试 十、附言

考研资料数据结构试题汇总

第一章绪论 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软 件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16. 任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件

计算机考研数据结构试卷十四(练习题含答案)

共25套适用于计算机考研数据结构系统练习 （PS：其他正在整理，敬请期待） 数据结构试卷14 一、填空题 1、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。 2、二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。 3、求下列广义表操作的结果： (1) GetTail[GetHead[((a,b),(c,d))]]; (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]] 4、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 5、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。 6、在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为____，共需递归调用的次数为____，其中第二次递归调用是对____一组记录进行快速排序。 7、在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____方法，其次选取____方法，最后选取____方法；若只从排序结果的稳定性考虑，则应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取____方法。 二、选择题 1、二分查找和二叉排序树的时间性能【】。 A. 相同 B. 不相同 2、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【】。 A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n) 3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是【】。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 4、下述几种排序方法中，要求内存量最大的是【】。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 5、设有两个串p和q，求q在p中首次出现的位置的运算称作【】。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 6、二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j 从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为【】。 A. SA+141 B. SA+180 C. SA+222 D. SA+225 7、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是【】。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

数据结构精选考研试题

数据结构精选考研试题 [注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分] 1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？ 3、什么是结构化程序设计？ 4、哈希方法的基本思想 5、给出一不稳定排序方法名称与实例二、构造结果：[24分] 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．假设用于通讯的电文仅8个字母组成，字母在电文中出现的频率

分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为，H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分] 四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分] 五、编写程序，完成下列功能：[15分] 1．读入整数序列，以整数0作为序列的结束标志，建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0 六、

哈尔滨工程大学-考研数据结构真题-12_

哈尔滨工程大学-考研数据结构真题-12_ 哈尔滨工程大学试卷考试科目: 数据结构A 卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1、以下数据结构中，从逻辑结构看，（）和其他数据结构不同。 A．树B．字符串C．队列D．栈2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 3、有六个元素A，B，C，D，E，F的顺序进栈，（）不是合法的出栈序列。 A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA 4、字符串“ABCDEF”的子串有（）个。 A．19 B．20 C．21 D．22 5、顺序表中插入一个元素，需要平均移动的元素个数为（）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-1 6、非空的单循环链表head 的尾结点（由P所指向）满足（）。 A．p-next ==NULL B．p==NULL C．p-next==head D．p==head 7、若A是中序线索二叉树中的一个结点，且A不为根，则A的前驱为( )。 A．A的右子树中最右的结点B．A的左子树中最左的结点C．A 的右子树中最左的结点D．A的左子树中最右的结点8、如某二叉树有30个叶子结点，有20个结点仅有一个孩子，则该二叉树中有两个孩子的结点数为（）。 A．29 B．30 C．31 D．19 9、二维数组A的每个元素是由8个字符组成的串，其行下标i=0,1,…,9,列下标j=1,2,…,10。若A按行序为主序存储，元素A的起始地址与当A按列序为主序存储时的元素（）的起始地址相同（设每个字符占一个字节）。 A．A B．A C．A D．A 10、图的深度优先遍历算法类似于二叉树的（）。

数据结构考研真题及其答案

一、选择题 1.算法的计算量的大小称为计算的（B）。【北京邮电大学2000二、3（20/8分）】 A．效率B.复杂性C.现实性D.难度 2.算法的时间复杂度取决于（C）【中科院计算所1998 二、1（2分）】 A．问题的规模B.待处理数据的初态和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（4分）】

4．一个算法应该是（B）。【中山大学1998二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 6.下面说法错误的是（C）【南京理工大学2000一、2（分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执

行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1)B.(1),(2)C.(1),(4)D.(3) 7．从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学1996一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（D）。【北方交通大学2000二、1（2分）】 A．循环队列B.链表C.哈希表D.栈 9．以下数据结构中，哪一个是线性结构（D）【北方交通大学2001一、1（2分）】 A．广义表B.二叉树C.稀疏矩阵D.串 10．以下那一个术语与数据的存储结构无关（A）【北方交通大学2001一、2（2分）】

10考研数据结构试题分析

一、总体分析 计算机科学与技术学科全国硕士研究生统一入学考试已经进行了两次。数据结构部分的考试范围要求掌握： 1，基本数据结构的知识 2，算法设计和编程的能力 3，综合应用算法和数据结构的技能 从考试的命题来看，2010年比2009年的题目难度要大一些。在这里，我对2009年考题与2010年考题的考试范围进行了简单的比较： A, 选择题部分，请参考表1

表1 2010年选择题还有一道题（11题）是对几种排序方法的考察。 由表1我们可以总结出，在选择题部分，各主要知识点分布如下，请参考表2： 表2 B ，综合应用题部分的试题范围如下：

总体上讲，2009年的试题较简单，2010年的试题比较复杂，且难度稍大，但平时教学中应当都教过，或练习都做过。 二、2010 年考试改卷的基本情况 2010年考试改卷的大概情况如下： 客观题是机改，数据结构部分总分22分，平均得分约为17分，失分较多的是 第2题（双端队列） 第5题（K叉树叶结点的计算） 第8题（拓扑排序的序列个数） 第10题（快速排序递归次数）； 主观题是人改，数据结构部分总分23分 第41题10分，平均得分5分，失分最多的是 计算散列表长度（2分），多数考生未得分。

将给定元素存储到散列表中（6分），平均得3分。如果第1问错了，不影响第2问得分；但可惜散列函数有不少同学选择不完全对。 计算平均查找长度（2分），平均得1分。 第42题是算法设计题13分，平均得6～8分，失分最多的是算法效率达不到要求。 许多考生成绩差的主要原因： 1，本科数据结构课程学习不够扎实； 2，考前复习不够充分； 3，考试时审题不仔细，急于给出答案，未严格推导。 三、2010年考试试卷分析 由于篇幅有限，在此只例举综合题两道大题进行分析。 二、综合应用题 41题：（10分）将关键字序列{ 7, 8, 30, 11, 18, 9, 14 } 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组散列，函数为： H(key) = (key′3) MOD 7 处理冲突采用线性探测再散列法，要求装载因子为 0.7 问题： (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下，查找成功和查找不成功的平均查找长度。

数据结构考研真题及其答案

数据结构考研真题及其 答案 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN

一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 2

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈 9．以下数据结构中，哪一个是线性结构（ D ） 【北方交通大学 2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关（ A ）【北方交通大学 2001 一、2（2分）】 3

2019年广东暨南大学数据结构考研真题

2019年广东暨南大学数据结构考研真题 一、单项选择题(每题2分，共30分) 1.在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。 A.不一定相同 B.互为逆序 C.都不相同 D.都相同 2.深度为4的二叉树至多有结点数为()。 A.18 B.14 C.15 D.16 3.在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和为()。 A.m B.m-1 C.m+1 D.2m 4.快速排序在()情况下最不利于发挥其长处。 A.被排序的数据量太大. B.被排序数据中含有多个相同的关键字 C.被排序的数据完全无序 D.被排序的数据已基本有序 5.一组记录的关键字为(45,80,55,40,42,85),则利用堆排序的方法建立的初始堆为()。 A.(80,45,55,40,42,85) B.(85,80,55,40,42,45) C.(85,80,55,45,42,40) D.(85,55,80,42,45,40) 6.对有18个元素的有序表(下标为1~18)作折半查找,则查找A[3]的比较序列的下标为()。 A.1,2,3 B.9,5,2,3 C.9,5,3 D.9,4,2,3 7.具有n个顶点的完全有向图的边数为()。 A.n(n-1)/2 B.n(n-1) C.n2 D.n2-1 8.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素35要进行()。 A.4次 B.5次 C.3次 D.2次 9.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用()。