数据结构习题（无答案）

试卷一

一、简答题：（每小题3分，共15分）

1. 什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找

性能最差？

2. 比较顺序表与单链表的优缺点。

3. 请写出栈的链式存储结构的类型定义。

4. 在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反

的方向移动，试举例说明之。

5. 简述参数传递的主要方式及其特点。

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。

( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。 ( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。 ( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。 ( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。

三、单项选择题：(每小题1分，共5分)

1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的单循环链表 C) 用尾指针表示的单循环链表 D) 单链表 2．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：

A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X)

C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y, R, X)

3．下面是三个关于有向图运算的叙述：

（1）求有向图结点的拓扑序列，其结果必定是唯一的

（2）求两个指向结点间的最短路径，其结果必定是唯一的 （3）求AOE网的关键路径，其结果必定是唯一的 其中哪个（些）是正确的？

A) 只有（1） B) （1）和（2） C) 都正确 D) 都不正确 4．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为:

A) 4 B) 5 C) 6 D) 7 5. 以下关于广义表的叙述中,正确的是：

A) 广义表是由0个或多个单元素或子表构成的有限序列 B) 广义表至少有一个元素是子表

C) 广义表不能递归定义 D) 广义表不能为空表

四、填空题：(每小题2分,共 20分)

1． 一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对1≤k≤101, 若A[k]是非叶结点, 则k的最小值是: ，k的

最大值是: 。

2. 设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5);

StrCat(sub1,sub2); 则最后sub1的值为： 。 3. 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为________________ 。

4．广义表((((a),b),c),d)的表头是 ，表尾是 。

5． 已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是： 将 累加。

6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作： 和 。

7. 用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是 。

8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2

个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是 9．在表示二叉树的二叉链表中,共有 个空链域。

10． n个顶点的连通无向图至少有 条边，至多有 条边。

五、构造题：（每小题6分，共30分）

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

2．已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全

为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。

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

4．图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。

图2

5．对关键字序列 (72，87，61，23，94，16，05，58) 进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和一趟排序后的序列状态。

六、算法设计题：（共25分）

1． 设有一个由正整数组成的单链表L（含头结点），编写完成下列功能的算法： 找出最小值结点P， 若最小值是奇数，则删除结点P。[15分]

2． 已知树用孩子兄弟链表存储，root 指向根结点。编写算法，逐层遍历这棵树。 [10分]

《数据结构》试卷参考答案与评分标准

（2000级）

一 、简答问题：（每小题4分，共16分）

1． 集合结构、线性结构、树形结构、网状结构

2． 线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。

3． 解决特定问题的有限指令序列。有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。

4． 堆排序。因为一趟堆排序排定一个元素，只需进行前10趟堆排序就可以了。其它排序方法均需进行完全排序。

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

1.（?） 2.（√） 3.（√） 4.（?） 5.（√） 三、单项选择题：(每小题1分，共4分)

1．C) 2．A) 3. A) 4. D)

四、填空题：(每小题2分,共 20分)

1． 97 2. n+1 3. 链域数目不同

4. 哈希查找法 5. 26 – 1 6. 1168

7. p->next 、 s 8.(a,b) 、 (c,d) 9. P->next==LA 10. 直接插入

五、构造题：（每小题5分，共25分）

1．

2．

0 K 1 TA 2 BA 3 M 4 D 5 CI 6 X 7 8 9 TN 10 I ASL=20/9 0 1 2 3 4 5 6 7 8 9 10

ASL=15/9 3．

{36，17，22，50，96，85，52，55} 4．

WPL=11×2+6×2+9×2 +5×3 +2×4+3

×4 =87

[注]：哈夫曼树的左右子树可以互换。 5．

[注]：如果求中点时采用向上取整，则二叉树的形态为左子树偏长。

六、算法设计题：（每小题15分，共30分） （仅要求给出子程序）

1．[解答]：

int judge(DLinkList L){ p=L->next; q=L->prior; while(p!=q)

{ if(p->data!=q->data) return 0;

if(p->next==q) return 1; p=p->next; q=q->prior; }

return 1; }

[注]：可以不用返回值，而用打印信息。 2． [解答]： （1）

void print_1(BiTree T){ if(T!=NULL)

{ print_1(T->RChild); printf(“%c”, T->data); print_1(T->LChild); } }

（2）

void Print_2（BiTree T） { InitStack (&S); p=T;

while(p!=NULL || ! IsEmpty(S))

{ while (p!=NULL) { Push(&S, p);

p=p->RChild; }

if ( ! IsEmpty(S) ) { Pop(&S, &p);

printf (“%c”, p -> data ); p = p -> LChild;

}

} }

试卷二

一 、简答问题：（每小题4分，共16分）

6. 四类基本数据结构的含义和特点。 7. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？ 8. 举例说明什么是抽象数据类型。 9. 算法的定义和特性。

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

( )（1）由树的中序表示和前序表示可以导出树的后序表示。 ( )（2）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。

( )（3）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

( )（4）在Huffman树中，权值较大的叶子结点离根较远。

( )（5）用一维数组存储二叉树时，是以先根遍历的次序存储结点。

三、单项选择题：(每小题1分，共4分)

1．对线性表，在下列哪种情况下应当采用链表表示？

A）经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变

2．在待排序文件已基本有序的前提下,下述排序方法中效率最高的是：

A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序

3．设有关键码序列(Q,G,M,Z,A,N,P,X,H),下面哪一个序列是从上述

序列出发建堆的结果?

A)A,G,H,M,N,P,Q,X,Z B)A,G,M,H,Q,N,P,X,Z C)G,M,Q,A,N,P,X,H,Z D)H,G,M,P,A,N,Q,X,Z 4．以下哪一个术语与数据的存储结构无关？

A)栈 B)散列表 C)穿线树 D)双链表

四、填空题：(每小题2分,共 20分)

1．字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 个不同的字符串。 2．设仅包含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为 。

3．在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码值12，所需的关键码比较次数为： 。

4．快速排序的最坏情况，其待排序的初始排列是 . 5. 二叉树的先序遍历序列为：EFHIGJK，中序遍历序列为：HFIEJKG，则该二叉树根的右子树的根是： 。

6． 顺序表（即顺序存储结构的线性表）中插入一个元素，

平均需要移动 个元素.

7．二维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元,并且A[0][0]的存储地址是1016, 则A[9][8]的存储地址是

8．循环单链表La中，指针P所指结点为表尾结点的条件是 9．N个结点的二叉树,采用二叉链表存放,空链域的个数为 .

10．要在一个单链表中p所指结点之后插入s所指结点时, 应执行 和 的操作.

五、构造题：（每小题5分，共25分）

1．对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,

哈希函数为H(K)=（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。 2．已知一棵树如图所示,请将该树转化为二叉树。

A

B C D

E ，4，5，F G ，构造一棵带权路径长度最H 3．给定权值{8，1226，16，9}短的二叉树，并计算基带权路径长度。 4. 已知关键码序列为{2，8，31，20，19，18，53，27}，试画出逐

I J K 个插入这8个关键码后的二叉排序树。 5．设有关键码序列(Q,G,M,Z,A,N,P,X,H),将其筛选为一个堆序列。

六、算法设计题：（每小题15分，共30分）

（仅要求给出子程序） 3． 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。（15分） 4． 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前。要求：采取顺序存储结构，至多使用一个记录的辅助存储空间，算法的时间复杂度为O(n)。（15分）

试卷三

一、简答题：（每小题3分，共15分）

10. 什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找

性能最差？

11. 比较顺序表与单链表的优缺点。

12. 请写出栈的链式存储结构的类型定义。

13. 在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反

的方向移动，试举例说明之。

14. 简述参数传递的主要方式及其特点。

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。

( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。 ( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。 ( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。 ( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。

三、单项选择题：(每小题1分，共5分)

1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的单循环链表 C) 用尾指针表示的单循环链表 D) 单链表 2．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：

A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X)

C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y, R, X)

3．下面是三个关于有向图运算的叙述：

（1）求有向图结点的拓扑序列，其结果必定是唯一的

（2）求两个指向结点间的最短路径，其结果必定是唯一的 （3）求AOE网的关键路径，其结果必定是唯一的 其中哪个（些）是正确的？

A) 只有（1） B) （1）和（2） C) 都正确 D) 都不正确 4．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为:

A) 4 B) 5 C) 6 D) 7 5. 以下关于广义表的叙述中,正确的是：

A) 广义表是由0个或多个单元素或子表构成的有限序列 B) 广义表至少有一个元素是子表

C) 广义表不能递归定义 D) 广义表不能为空表

四、填空题：(每小题2分,共 20分)

1． 一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对1≤k≤101, 若A[k]是非叶结点, 则k的最小值是: ，k的最大值是: 。

2. 设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5);

StrCat(sub1,sub2); 则最后sub1的值为： 。 3. 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为________________ 。

4．广义表((((a),b),c),d)的表头是 ，表尾是 。

5． 已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是： 将 累加。

6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作： 和 。

7. 用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是 。

8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2

个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是 9．在表示二叉树的二叉链表中,共有 个空链域。

10． n个顶点的连通无向图至少有 条边，至多有 条边。

五、构造题：（每小题6分，共30分）

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

2．已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。

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

4．图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。

图2

5．对关键字序列 (72，87，61，23，94，16，05，58) 进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和一趟排序后的序列状态。

六、算法设计题：（共25分）

5． 设有一个由正整数组成的单链表L（含头结点），编写完成下列功能的算法： 找出最小值结点P， 若最小值是奇数，则删除结点P。[15分]

6． 已知树用孩子兄弟链表存储，root 指向根结点。编写算法，逐层遍历这棵树。 [10分]

《数据结构》试卷参考答案与评分标准

（2001级）

一、简答题：（每小题3分，共15分）

15. 前驱与后继之间通常为一对多或多对多的关系。

16. 顺序表优点：随机查找，存储密度大

顺序表缺点：插入、删除不便，静态分配，表长固定 单链表优点：插入、删除方便，动态分配，表长灵活 单链表缺点：查找不便，存储密度小

17. 关键字相同的两个记录，排序前后其先后顺序不变。 18. typedef struct node{

ElemType data; struct node * next; } *LinkStack;

19.当二叉排序树接近平衡二叉树或完全二叉树时查找性能较好，当二叉排

序树为单边单枝二叉树时查找性能最差。

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

(?)（1） (?)（2） (√)（3） (?)（4） (?)（5）

三、单项选择题：(每小题1分，共5分)

1．C) 2．C) 3．D) 4．B) 5. A)

四、填空题：(每小题2分,共 20分)

1． 1 2. ’YOU ARE RIGHT’

3. O(nlogn) 4． (((a),b),c) ， (d)

5． i列元素 6． t->next=p->next ， p->next=s 7. rear->next==rear 8． 1300 9． n+1 10． n-1

五、构造题：（每小题6分，共30分）

1．

2．

3．

或：

WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2 =207

[注]：哈夫曼树的左右子树可以互换。

4． [解1]：

[解2]：

[注]：边上的权值可以省略。

5．

初始堆：

05，23，16，58，94，72，61，87

一趟排序后的序列状态：

87，23，16，58，94，72，61，05

筛成堆后为：

16，23，61，58，94，72，87，05

[注]：如果采用大根堆，应适当减分。

六、算法设计题：（共25分）

7．

[15分]

void min(LinkList L){

if(L->next==NULL) return; q=L; r=L->next; m=r->data; while(r->next!=NULL) { if(r->next->data

{ m= r->next->data; q=r; } r=r->next; }

p=q->next;

if(m%2==1) {q->next=p->next; free(p); } }

8． [10分]

void layer(CSTree root){

InitQueue(&Q); EnterQueue(&Q, root); while(!Empty(Q))

{ DelQueue(&Q, &p); visit(p); p=p->FirstChild; while(p!=NULL)

{ EnterQueue(&Q, p); p=p->NextSibling; } } }

试卷四

一、简答题：（每小题3分，共15分）

20. 在哈希查找法中，为什么平均查找长度与关键字个数无关？

21. 对于无向图，如何用遍历算法判断图中是否存在回路？ 22. Huffman树是否唯一？请举例说明。 23. 栈和队列各有哪些基本操作？

24. 在一个与堆序列对应的完全二叉树中，从根结点到任一个叶结点的路径

上的关键字序列有何特点？为什么？

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

（ ）1. 折半搜索只适用于有序表，包括有序顺序表和有序单链表。 （ ）2．由树的中序表示和前序表示可以导出树的后序表示。 （ ）3. 查找n个关键字的散列表时，平均查找长度与n无关。 （ ）4. 希尔排序是一种不稳定的排序方法。

（ ）5. 给定一个关键字集合，将得到唯一的一棵二叉排序树，与关键字的插入顺序无关。

三、单项选择题：(每小题1分，共5分)

1. 某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则该二叉树根的右子是：

A）E B）F C）D D）G

2．在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的移动次数为：

A) n-i+1 B) n-i C) i D) i-1 3．下面关于图的存储的叙述中正确的是

A）邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关； B）邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关； C）邻接表占用的存储空间只与图中结点个数有关，而与边数无关； D）邻接表占用的存储空间只与图中边数有关，而与结点个数无关。 4. 在待排序记录已基本有序的前提下，下述排序方法中效率最高的是：

A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序 5．栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？

A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、 E、 A

四、填空题：(每小题2分,共 20分)

1. 向一个有n个元素的有序表中插入一个新元素并保持原来顺序不

变，平均要移动 个元素。

2. 设广义表L=( ( ), ( ) )，则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 。

3． 在双向循环单链表中，删除指针P所指结点的操作是 ； 。

4. 设根结点的层数为1，则高度为k的二叉树具有的结点数目，最少为 ，最多为 。

5． 10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________________。 6.有3个结点的、不同结构的二叉树共有 棵。 7．将10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为________。

8. 在n个结点的线索二叉链表中，有________个线索指针。

9．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的存储地址是

。

10．字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 个不同的字符串。

五、构造题：（每小题6分，共30分）

1． 已知关键字序列：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为：H(K)=（K中最后一个字母在字母表中的序号）MOD 7 用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。 2． 一个二叉树按顺序方式存储在一个一维数组中，如图1所示（空元素对应虚结点）。（1）画出二叉树， （2）给出后序遍历序列。

图1

3．假设字符a, b, c, d, e, f的使用频度分别是0.07, 0.09, 0.12, 0.22, 0.23, 0.27，画出哈夫曼树，并给出a, b, c, d, e, f的哈夫曼编码。 4. 已知无向图如图2所示， （1）给出图的邻接表。

（2）从C开始，给出深度优先遍历序列和深度优先搜索树。 5．将下列关键字序列筛成一个大根堆： （A, C, D, G, H, M, P, Q, R, X），要求给出建堆过程图示。

A

B D

C E 图2

F

六、算法设计题：（共25分）

9． 编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。[15分]

10． 二叉树按照二叉链表方式存储，编写非递归算法计算二叉树中结点数目。[10分]

试卷五

一、简答题（15分，每小题3分）

25. 简要说明算法与程序的区别。

26. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 27. 说明在图的遍历中，设置访问标志数组的作用。

28. 说明以下三个概念的关系：头指针，头结点，首元素结点。 29. 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？

二、判断题（10分，每小题1分）

正确在括号内打√，错误打×

( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。

( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面 ：p->next = s; s->next = p->next;

( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。

( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。

( )（10）长度为1的串等价于一个字符型常量。

三、单项选择题（10分, 每小题1分）

1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2． 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A. head->priro==NULL B. head->next==NULL

C. head->next==head D. head->next-> priro==NULL 4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为：

A) 2 B) 3 C) 4 D) 5 5. 以下哪一个不是队列的基本运算？

A）从队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值

6. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：

A) n – i + 1 B) n – i C) i D) i – 1 7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表 D) 单链表

8．对包含n个元素的哈希表进行查找，平均查找长度为：

A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n

9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点

进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A、48 B、49 C、50 D、51

10．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：

A）3 B）2 C）4 D）5

四、填空题（10分，每空1分）

1．填空完成下面一趟快速排序算法：

int QKPass ( RecordType r [ ], int low， int high) { x = r [ low ]； while ( low < high ) {

while ( low < high && r [ ]. key >= x.key )

high - -；

if ( low < high )

{ r [ ] = r [ high ]； low++; }

while ( low < high && r [ ]. key < x. key ) low++;

if ( low < high )

{ r [ ] = r [ low ]； high--; }

}

r [ low ] = x； return low ; }

2. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句： ； ；R=S；

3．通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣。

4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是： 5．高度为h的完全二叉树最少有 个结点。

五、构造题（20 分）

1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。

DS = (D, R)

D = { a, b, c, d, e, f, g } R = { T }

T = { , , , , , ,

, , , , , }

2．（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为H(K) =（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下查找成功的平均查找长度。

3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53， 87）调整为大根堆。 4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。

六、算法分析题（10分）

阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。

（1） 简要说明程序功能。（5分）

（2） n个结点的满二叉树的深度h是多少？（3分）

（3） 假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。

（2分）

int Proc (BSTree *bst, KeyType K) { BSTree f, q, s;

s=(BSTree)malloc(sizeof(BSTNode));

s-> key = K; s-> lchild = NULL; s-> rchild = NULL; if ( *bst == NULL ) { *bst = s; return 1; } f = NULL; q = *bst; while( q != NULL )

{ if ( K < q -> key )

{ f = q; q = q -> lchild; } else

{ f = q; q = q -> rchild; }

}

if ( K < f -> key ) f -> lchild = s; else f -> rchild = s; return 1; }

七、算法设计题（25分）

11． 已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）

12． 无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分）

13． 编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）

2002级《数据结构》试卷参考答案与评分标准

一、简答题（15分，每小题3分）

30. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的

实现，与具体的计算机语言有关。

31. 主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突

的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。 32. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结

点。

33. 头指针指向头结点，头结点的后继域指向首元素结点。

34. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，

因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。

二、判断题（10分，每小题1分）

（1）(√) （2）(×) （3）(×) （4）(√) （5）(×) （6）(√) （7）(×) （8）(√) （9）(×) （10）(×)

三、单项选择题（10分, 每小题1分）

1． D） 2． B） 3． C） 4. C） 5. B） 6. A) 7． C) 8． D) 9． C） 10．C）

四、填空题（10分，每空1分）

1． high low low high 2. S->next=R->next ； R->next=S ；

3． 时间 空间 4． A[2, 3] 5． 2h-1

五、构造题（20 分）

1．（4分）

2．（6分）

0 1 2 3

SUN MON THU FRI

ASLsucc = ( 1×4 + 2×2 + 3 ) / 7 = 11 / 7

3.（6分）

4

WED

5

TUE

6 SAT

7

8

9

4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。

WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79

六、算法分析题（10分）

解：

（1） 在二叉排序树中插入关键字为K的结点

（2） h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括号表示向下取整） （3） O ( log2 ( n+1 ) ) 或 O ( log2 n )

七、算法设计题（25分）

（答案略）

试卷六

一、简答题（15分，每小题3分）

35. 用C语言写出静态顺序串类型定义。 36. 什么是算法的健壮性？

37. 用C语言实现一个抽象数据类型时，主要做哪两方面工作？ 38. 数据结构的形式化定义为：DS =（D，R），分别说明D和R的含义。 39. 在哈希查找法中，为什么平均查找长度与关键字个数无关？

二、判断题（10分，每小题1分）

正确在括号内打√，错误打×

( )（1）折半查找法只适用于有序表，包括有序顺序表和有序单链表。 ( )（2）将一个森林转换为二叉树后,该二叉树的根结点一定有右子树。

( )（3）一个抽象数据类型（ADT）定义了一个数据对象、数据对象中各元素间的结构关系、以及一组处理数据的操作（服务，公用界面）。

( )（4）一个栈的输入序列是：12345，则不可能得到出栈序列：43512。

( )（5）f(x)=O(g(x)) 表示随着x的增大，f(x)的增长率和g(x)的增长率相同。 ( )（6）逐层遍历一个堆对应的二叉树，将得到一个有序序列。

( )（7）当待排序记录序列已经有序时，快速排序的比较次数最少。

( )（8）在单链表中，给定任一结点的地址p，则可用下述语句将结点p的后继结点删除 ：p->next = NULL;

( )（9）对AOV网进行拓扑排序时，如果存在从Vi到Vj的路径，则在拓朴序列中，结点Vi一定排在结点Vj的前面。

( )（10）哈夫曼树根结点的权值等于所有叶结点的权值之和。

三、单项选择题（10分, 每小题1分）

1．第i趟排序时，顺序扫描待排序记录序列，从中选出当前最小（或最大）元素，并与第i个元素交换位置。这是哪种排序方法的基本思想？ A）堆排序 B）冒泡排序 C）快速排序 D）简单选择排序 2． 已知一个无向图的邻接矩阵A[n][n]，要增加一条边 ( i, k )，应该： A）将A[i][k]置为1 B）将A[i][i]和A[k][k]同时置为1 C）将A[k][i]置为1 D）将A[i][k]和A[k][i]同时置为1 3．广义表( a, ( b ), ( ( c ) ) ) 的表尾是: A) ( ( c ) ) B) ( ( ( c ) ) )

C) ( c ) D) ( ( b ), ( ( c ) ) ) 4．下面关于串的叙述中，哪一个是不正确的？

A) 串是字符的有限序列 B) 空串是由空格构成的串

C) 模式匹配是串的重要运算 D) 串既可顺序存储，也可采用链式存储 5． 6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列？

A) E、D、F、C、A、B B) B、C、E、F、A、D C) C、B、E、D、F、A D) A、D、F、E、B、C 6. 将长度为n的顺序表的第i个元素删除（1≤ i ≤n），元素的移动次数为： A) i B) i – 1 C) n – i + 1 D) n – i

7．已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为：

A) R->next B) *( R->next->next ) C) &( R->next->next ) D) R->next->next

8. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的左子树上的结点个数是

A）M1 B）M1+M2 C）M1+1 D）M1-1 9．下述哪一条是顺序存储方式的优点？ A)存储密度大 B)插入运算方便

C)删除运算方便 D)可方便地用于各种逻辑结构的存储表示 10．AVL树是一种平衡的二叉排序树，树中任一结点的:

A) 左、右子树的高度均相同 B) 左、右子树高度差的绝对值不超过1

C) 左子树的高度均大于右子树的高度 D) 左子树的高度均小于右子树的高度

四、填空题（15分，每空1.5分）

1．填空完成下面哈希表查找算法：

假设hash(x)为哈希函数，解决冲突用线性探测再散列法。 typedef RecordType HashTable[ m ] ;

int HashSearch( HashTable ht, KeyType K)

{

p0 = _______________;

if ( ht[ p0 ]. key == NULLKEY ) return ( - 1 ); else if ( ht[ p0 ]. key == K ) return ( p0 ); else

{

for (i=1; i<= ________; i++) {

pi = ( p0 + _____ ) % m;

if ( ht[ pi ]. key == NULLKEY ) return ( - 1 ); else if ( ht[ pi ]. key == _____ ) return ( pi ); }

return ( - 1 ); } }

2. 在n个结点的线索二叉链表中，共有________个线索指针。

3. 已知L是不带头结点的单链表，则在表首插入新结点S的语句序列是： 、 。

4. N个结点的完全二叉树的深度是 . 5．已知一个m行、n列的二维数组（各维下标均从1开始），每个元素占size个存储单元，如果按“以行为主”的顺序存储，首元素a11的地址为Loc[1,1]，则任意元素aij的地址为：

Loc[ i , j ] = Loc[1,1] + ( n× + )×size

五、构造题（20 分）

1．（6分）已知一棵二叉树的先序序列为：ABCDE，中序序列为：BDCEA，请构造该二叉树。 2．（4分）画出长度为8的有序表的折半判定树。 3．（4分）已知关键字集合：（12，2，16，30，8，28，4，10，20，6，18），用快速排序从小到大排序（选第一个记录为划分记录），写出第一趟排序结束时的序列。 4．（6分）已知无向网如图所示，用普里姆算法给出最小生成树（从结点4开始）。

六、算法分析题（10分）

阅读下面程序，并回答有关问题。

其中BiTree为二叉链表类型，并假设二叉树root有n个结点。 （1） 简要说明程序功能。（5分）

（2） 总共执行了多少次出栈操作？（3分） （3） 给出算法的时间复杂度。（2分） void Proc（BiTree root） {

InitStack (&S); if ( ! root ) return; Push(&S, root); while(! IsEmpty(S)) {

Pop(&S, &p);

Visit(p->data);

if ( p->RChild != NULL) Push(&S, p->RChild); if ( p->LChild != NULL) Push(&S, p->LChild); } }

七、算法设计题（25分）

1．已知带头结点的单链表L，编写算法删除L中从k开始的n个元素。（9分）

2． 已知二叉排序树bst，采用二叉链表存储结构。编写算法实现按结点值的递减顺序输出树中结点。（8分）

3．无向图采用邻接表方式存储，要求编写图的广度优先搜索算法。（8分）

试卷七 数据结构

一 、简答问题：（16分） 1．四类数据结构

2．线性结构与非线性结构的差别 3．简述算法的定义与特性

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

二、判断正误，正确在（ ）内打√，否则打? （共5分）

1．（ ）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值 若它的右子树非空，则根结点的值大于其右孩子的值 2．（ ）索引顺序表的特点是块内可无序，块间要有序。 3．（ ）子串是主串中任意个连续字符组成的序列。

4．（ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（ ）快速排序的枢轴元素可以任意选定

三、单项选择题(4分, 每小题1分)

1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?

A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C

2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为 。 A、98 B、99 C、50 D、48

3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是

A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30}

4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是

A）M1 B）M1+M2 C）M3 D）M2+M3

四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P〈=M〉, 为使函数具有较好性能，P应选

2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是

4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有 个结点。

6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是

7．在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= 和

p->next= 的操作.

8．广义表((a,b),c,d)的表头是 ,表尾是

9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，你认为应使用 排序方法最好。

五、构造题：（25分）

1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

3．有一组关键字{50，52，85，22，96，17，36，55}，请用快速排序，写出第一趟结果。 4．已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。 5．构造8个结点的折半判定树。

六、设计题： （30分）

1．编写算法，判断带头结点的双循环链表L是否对称。（15分）

对称是指：设各元素值a1,a2,...,an, 则有ai=an-i+1 即指：a1= an，a2= an-1 。。。。。。 结点结构为

prior data next

2． 二叉排序树T用二叉链表表示，其中各元素均不相同。

（1） 写递归算法，按递减顺序打印各元素的值。（10分） （2） 写出完成上述要求的非递归算法。（5分） 试卷八

数据结构（B卷）

（不含图结构）

2002．6．24

一 、简答问题：（每小题4分，16分）

1. 四类基本数据结构的含义和特点。

2. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？ 3. 举例说明什么是抽象数据类型。 4. 算法的定义和特性。

二、判断正误，正确在（ ）内打√，否则打? （每小题1分，共5分） ( )（1）由树的中序表示和前序表示可以导出树的后序表示。

( )（2）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。

( )（3）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

( )（4）一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。 ( )（5）用一维数组存储二叉树时，是以先根遍历的次序存储结点。

三、单项选择题(4分, 每小题1分)

1．对线性表，在下列哪种情况下应当采用链表表示？

A）经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变 2．在待排序文件已基本有序的前提下,下述排序方法中效率最高的是

A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序

3．设有关键码序列(Q,G,M,Z,A,N,P,X,H),下面哪一个序列是从上述序列出发建堆的结果? A)A,G,H,M,N,P,Q,X,Z B)A,G,M,H,Q,N,P,X,Z C)G,M,Q,A,N,P,X,H,Z D)H,G,M,P,A,N,Q,X,Z 4．以下哪一个术语与数据的存储结构无关？ A)栈 B)散列表 C)穿线树 D)双链表

四、填空题：(每小题2分,共 20分)

1．字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 个不同的字符串。

2．设仅包含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为 。 3．在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码值12，所需的关键码比较次数为： 。

4．快速排序的最坏情况，其待排序的初始排列是 .

5. 二叉树的先序遍历序列为：EFHIGJK，中序遍历序列为：HFIEJKG，则该二叉树根的右子树的根是： 。

6． 顺序表（即顺序存储结构的线性表）中插入一个元素，平均需要移动 个元素. 7．已知二维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元,

并且A[0][0]的存储地址是1016, 则A[9][8]的存储地址是 8．循环单链表La中，指针P所指结点为表尾结点的条件是 9．N个结点的二叉树,采用二叉链表存放,空链域的个数为 . 10．要在一个单链表中p所指结点之后插入s所指结点时,

应执行 和 的操作. 五、构造题：（25分）

1． 对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H(K)=（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。

2．已知一棵树如图1所示,请将该树转化为二叉树。

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

4. 已知关键码序列为{2，8，31，20，19，18，53，27}，试画出逐个插入这8个关键码后的二叉排序树。

5．设有关键码序列(Q,G,M,Z,A,N,P,X,H),将其筛选为一个堆序列

六、设计题： （30分）

1． 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表

某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。

2． 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录

排在关键字为非负值的记录之前。要求：采取顺序存储结构，至多使用一个记录的辅助存储空间，算法的时间复杂度为O(n)；[8分]

试卷九

一、 简答题：（15分，每小题3分）

1. 什么是数据的逻辑结构？有哪四类逻辑结构？

2. 什么是数据的存储结构（物理结构）？有哪两种存储结构？ 3. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？ 4. 简述线性结构与非线性结构的差别。 5. 简述算法的定义和特性。

二、判断题：（10分，每小题2分） 正确在括号内打√，错误打×

( )（1）顺序存储结构只能用来存放线性结构，链式存储结构只能用来存放非线性结构。

( )（2）三元组表相当于一个由若干三元组构成的顺序表。

( )（3）广义表的表头是表中第一个元素，表尾是表中最后一个元素。

( )（4）将一棵树转换为二叉树表示后,该二叉树的根结点一定没有右子树。 ( )（5）哈夫曼树中没有度为1的结点。

三、单项选择题：(20分, 每小题2分)

1．对线性表，在下列哪种情况下应当采用链表表示？ A）经常需要随机地存取元素 B）经常需要进行插入和删除操作

C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变 2．以下哪一个术语与数据的具体存储结构无关？

A)栈 B)三元组表 C)线索二叉树 D)双向链表

3．有６个元素6,5,4,3,2,1的顺序进栈，问下列哪一个是不合法的出栈序列： A)5,4,3,6,1,2 B)4,5,3,1,2,6 C)3,4,6,5,2,1 D)2,3,4,1,5,6

4．下述哪一条是顺序存储方式的优点？ A)存储密度大 B)插入运算方便

C)删除运算方便 D)可方便地用于各种逻辑结构的存储表示 5．下面关于串的叙述中，哪一个是不正确的？

A)串是字符的有限序列 B)空串是由空格构成的串

C)模式匹配是串的一种重要运算 D)串既可以采用顺序存储，也可以采用链式存储

6．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为 。 A、98 B、99 C、50 D、48

7．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?

A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C

8．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：________________

A. head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 9．链表不具有的特点是 。

A、可随机访问任一个元素 B、插入删除不需要移动元素

C、不必事先估计存储空间 D、所需空间与线性表的长度成正比 10．在下列存储形式中，哪一个不是树的存储形式？

A）双亲表示法 B）孩子链表表示法 C）孩子兄弟表示法 D）顺序存储表示法

四、填空题：（15分）

1. 有一个含头结点的单链表，头指针为A, 另有一个不含头结点的单链表，头

指针为B。 则A为空的条件为：________________，B为空的条件为：________________。假设S指向一个新结点，则在A的表头插入S时，语句为：________________________________，在B的表头插入S时，语句为：________________________________。

2. 已知二维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存

储单元，

并且A[0][0]的存储地址是1016, 则A[9][8]的存储地址是 。 3. 循环单链表的头指针为CL，则指针P所指结点为表尾结点的条件

是 。

五、构造题：（20 分）

1．已知一棵树如图1所示。要求：

（1） 给出树的先根遍历序列和后根遍历序列； （2） 画出树的孩子-兄弟链表； （3） 将该树转化为二叉树。

2．给定权值：{8，12，4，5，26，16，9}，构造哈夫曼树，并计算其带权路径长度。

六、算法设计题(20分) 1． 二叉树按照二叉链表方式存储，编写非递归算法计算二叉树中叶子结点数目。[10分] 2． 已知两个带头结点的单链表A和B，编写算法从单链表A中删除自第i个元素起的共len个元素，然后将它们插入到单链表B的第 j个元素之前。[10分]

试卷十

一、简答题：（每小题3分，共15分）

1. 在哈希查找法中，为什么平均查找长度与关键字个数无关？ 2. 对于无向图，如何用遍历算法判断图中是否存在回路？ 3. Huffman树是否唯一？请举例说明。 4. 栈和队列各有哪些基本操作？

5. 在一个与堆序列对应的完全二叉树中，从根结点到任一个叶结点的路径

上的关键字序列有何特点？为什么？

二、判断正误：（每小题1分，共5分）

正确在（ ）内打√，否则打? 。

（ ）1. 折半搜索只适用于有序表，包括有序顺序表和有序单链表。 （ ）2．由树的中序表示和前序表示可以导出树的后序表示。 （ ）3. 查找n个关键字的散列表时，平均查找长度与n无关。 （ ）4. 希尔排序是一种不稳定的排序方法。

（ ）5. 给定一个关键字集合，将得到唯一的一棵二叉排序树，与关键字的插入顺序无关。

三、单项选择题：(每小题1分，共5分)

1. 某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则该二叉树根的右子是：

A）E B）F C）D D）G

2．在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的移动次数为：

A) n-i+1 B) n-i C) i D) i-1 3．下面关于图的存储的叙述中正确的是

A）邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关； B）邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关； C）邻接表占用的存储空间只与图中结点个数有关，而与边数无关； D）邻接表占用的存储空间只与图中边数有关，而与结点个数无关。 4. 在待排序记录已基本有序的前提下，下述排序方法中效率最高的是： A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序

5．栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？

A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、 E、 A

四、填空题：(每小题2分,共 20分)

1. 向一个有n个元素的有序表中插入一个新元素并保持原来顺序不

变，平均要移动 个元素。

2. 设广义表L=( ( ), ( ) )，则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 。

3． 在双向循环单链表中，删除指针P所指结点的操作是 ； 。

4. 设根结点的层数为1，则高度为k的二叉树具有的结点数目，最少为 ，最多为 。

5． 10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________________。 6.有3个结点的、不同结构的二叉树共有 棵。 7．将10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为________。

8. 在n个结点的线索二叉链表中，有________个线索指针。 9．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的存储地址是

。

10．字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 个不同的字符串。

五、构造题：（每小题6分，共30分）

1． 已知关键字序列：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为：H(K)=（K中最后一个字母在字母表中的序号）MOD 7 用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。 2． 一个二叉树按顺序方式存储在一个一维数组中，如图1所示（空元素对应虚结点）。（1）画出二叉树， （2）给出后序遍历序列。

图1

3．假设字符a, b, c, d, e, f的使用频度分别是0.07, 0.09, 0.12, 0.22, 0.23, 0.27，画出哈夫曼树，并给出a, b, c, d, e, f的哈夫曼编码。 4. 已知无向图如图2所示，

（1）给出图的邻接表。

（2）从C开始，给出深度优先遍历序列和深度优先搜索树。 5．将下列关键字序列筛成一个大根堆：

（A, C, D, G, H, M, P, Q, R, X），要求给出建堆过程图示。

六、算法设计题：（共25分）

1． 编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。[15分]

2． 二叉树按照二叉链表方式存储，编写非递归算法计算二叉树中结点数目。[10分]

试卷十一

数据结构

一 、简答问题：（16分） 1． 四类数据结构

2． 线性结构与非线性结构的差别 3． 简述算法的定义与特性 4． 设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？

二、判断正误：正确在（ ）内打√，否则打? （共5分）

1． （ ）二叉排序树或是一棵空树，或是有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值 若它的右子树非空，则根结点的值大于其右孩子的值

2． （ ）索引顺序表的特点是块内可无序，块间要有序。

3． （ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 4． （ ）快速排序的枢轴元素可以任意选定。

5． （ ）顺序存储方式的优点是存储密度大，且插入和删除运算效率高。

三、单项选择题(共10分, 每小题1分)

1． 下列哪一个关键码序列不符合堆的定义？

A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X 、G、Q、R C）A、D、P、R、C、Q、X 、M、H、G

D）A、D、C、M、P、G、H、X 、R、Q

2．在有n个叶子结点的哈夫曼树中，其结点总数为 ( ) 。 A、不确定 B、2n C、2n+1 D、2n-1

3．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:

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

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

A. n B. 2n－1 C. 2n D. n-1 5．一个有n个顶点的无向图最多有 条边。

A、n B、n（n-1） C、n（n-1）/2 D、2n 6．任何一个无向连通图的最小生成树 。 A、只有一棵 B、有一棵或多棵

C、一定有多棵 D、可能不存在

7．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：________________

A． head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 8．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列 序列是可能的出栈序列

A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C

9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为 。 A、98 B、99 C、50 D、48

10. 对下列关键字序列用快速排序法排序时，速度最快的是

A、{21、25、5、17、9、23、30} B、{25、23、30、17、21、5、9} C、{21、9、17、30、25、23、5} D、{5、9、17、21、23、25、30}

四、填空题：(每空2分,共 20分) 1． 设一哈希表表长M为26 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P〈=M〉, P应选 2． N个结点的二叉树用二叉链表存放，空链域个数为 3． 单链表与多重链表的区别是

4． 已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 5． 在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= 和p->next= 的操作.

6．广义表((a,b),c,d)的表头是 ,表尾是 7．循环单链表LA中，指针P所指结点为表尾结点的条件是

8．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，应使用 排序方法最好。

五、构造题：（20分）

1． 已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。

2． （SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H(K)=（关键字中第一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，计算出在等概率情况下查找成功的平均查找长度。 3． 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。 4． 构造8个结点的折半判定树。

六、设计题： （30分）

1．编写算法，判断带头结点的双循环链表L是否对称。（15分）

对称是指：设各元素值a1,a2,...,an, 则有ai=an-i+1 即指：a1= an，a2= an-1 。。。。。。 结点结构为

prior data next

2．二叉排序树T用二叉链表表示，其中各元素均不相同。

（1） 写递归算法，按递增顺序打印各元素的值。（10分） （2） 写出完成上述要求的非递归算法。（5分）

试卷十二

一 、简答问题：（15分） 1． 四类基本数据结构的含义 2． 线性结构与非线性结构的差别

3． 简述栈和队列的共同点和不同点。它们为什么属于线性表？

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

二、判断正误：正确在（ ）内打√，否则打×（共10分） （ ）1. 在单链表中，头结点是必不可少的。

（ ）2. 在一个大根堆中，最小元素不一定在最后。

（ ）3. 顺序存储结构只能存线性结构。链式存储结构只能存非线性结构。

（ ）4. 在有向图中，所有顶点的入度之和等于所有顶点的出度之和。

（ ）5. 内部排序是指排序过程在内存中进行的排序。

（ ）6. 拓扑排序是指结点的值是有序排列。

（ ）7. AOE网所示工程至少所需时间等于从源点到汇点最长路径长度。

（ ）8. 二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值 若它的右子树非空，则根结点的值大于其右孩子的值

（ ）9. 索引顺序表的特点是块内可无序，块间要有序。

（ ）10. 快速排序的枢轴元素可以任意选定。

三、单项选择题(共10分，每小题1分)

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

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

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

A、不确定 B、2n C、2n+1 D、2n-1

3． 若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

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

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

A. 存在 B. 不存在

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

A. n B. 2n－1 C. 2n D. n-1

6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是( ) 。 A、 A，B，C，D B、 D，C，B，A

C、 A，C，D，B D、 D，A，B，C

7．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为( )。 A、98 B、99 C、50 D、48

8. 一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84

D、40，38，46，84，56，79

9．排序趟数与序列的原始状态有关的排序方法是( )排序法。

A. 插入 B．选择 C. 冒泡 D．快速 10．串是( )。

A、不少于一个字母的序列 B、任意个字母的序列 C、不少于一个字符的序列 D、有限个字符的序列

四、填空题：(每空2分,共 20分)

1． 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P〈=M〉，P最好应选 。

2． N个结点二叉树用二叉链表存放，共有 个空链域。

3． 单链表与多重链表的区别是 。

4． 已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[0][0]的存储地址是1000,则A[18][9]的存储地址是 。

5． 在一个单链表中p所指结点之后插入s所指结点时,应执行

s->next= 和p->next= 的操作.

6．广义表((a,b),c,d)表头是 ,表尾是 。

7．循环单链表LA中，指针P所指结点为表尾结点的条件是 。 8．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，应使用 排序方法最好。

五、构造题：（15分）

1． 已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 2． 设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

3． 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。

六、设计题： （30分）

1．二叉树T用二叉链表表示。

? 要求编写递归算法，计算二叉树中叶子结点数目。（10分） ? 要求编写非递归算法，计算二叉树中叶子结点数目。（5分）

2．无向图采用邻接表方式存储，要求编写按广度优先搜索策略实现对图的遍历算法。（15分）

试卷十三

西北大学 2007 ---- 2008 学年第 一 学期本科考试

数 据 结 构

注意：所有题目均要求在答题纸上解答。 一 、简答问题15分（每小题5分，共3小题） 1、 有哪四类基本数据结构？

2、 使用折半查找的两个前提条件是什么？

3、 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？

二、单项选择题10分（每小题1分，共10小题）

1． 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？

A）堆排序 B）直接插入排序 C）快速排序 D）冒泡排序

2． 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：

A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A）head->prior==NULL B）head->next==NULL C）head->next==head D）head->next-> prior==NULL

4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，

所需的关键码比较次数为： A) 2 B) 3 C) 4 D) 5

5. 以下哪一个不是队列的基本运算？

A）在队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值

6. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：

A) n – i + 1 B) n – i C) i D) i – 1

7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表 D) 单链表

8．对包含n个元素的哈希表进行查找，平均查找长度为： A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n

9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点

进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A）48 B）49 C）50 D）51

10．某二叉树结点的中序序列为：A、B、C、D、E、F、G， 后序序列为：B、D、C、A、F、G、E，则其左子树中结点数目为： A）3 B）2 C）4 D）5

三、填空题20分（每空2分，共5小题，10空）

1. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，

需执行下面语句： ； ； R=S；

2．通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣。 3．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元, 并且A[0][0]的存储地址是1024, 则A[6][18]的地址是 4．高度为h的完全二叉树最少有 个结点。 5．填空完成下面一趟快速排序算法：

int QKPass ( RecordType r [ ], int low， int high) {

x = r [ low ]； while ( low < high ) {

while ( low < high && r [ ]. key >= x.key ) high - -； if ( low < high )

{ r [ ] = r [ high ]； low++; }

while ( low < high && r [ ]. key < x. key ) low++;

if ( low < high )

{ r [ ] = r [ low ]； high--; } }

r [ low ] = x； return low ; }

四、构造题30分（共5小题）

注：构造题只要求手工构造相应结果，不需要编写实现程序。

1．（6分）已知关键字集合：{ 50，52，85，22，96，17，36，55 }，用冒泡排序从小到大排序，分别写出第一趟、第二趟、第三趟排序结束时的序列。

2．（7分）设哈希函数H（K）=（K的第一字母在字母表中的序号）% 11 ，哈希表长度为11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

3.（5分）画出8个结点的折半判定树。

4．（6分）已知叶结点权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。

5. （6分）已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素（包括主对角线元素）全为0，其他元素均为1。请画出该图，并给出其邻接表。

五、算法设计题25分（共2小题）

注：算法设计题只要求给出描述算法的子函数，不需要编写完整的实现程序。

1． 假设有一个长度大于1的循环单链表，表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法，在链表中删除指针s指向的结点。 【 15 分 】

2． 已知二叉排序树bst，采用二叉链表存储结构。

（1） 编写算法，逐层输出二叉排序树中的结点。 【 5 分 】 编写算法，按结点值的递减顺序输出二叉排序树中的结点。 【 5 分 】

《数据结构》试卷参考答案与评分标准

（2006级）

一 、简答问题15分（每小题5分，共3小题） 1.

集合结构、线性结构、树形结构、网状结构 。 2.

（1）采用顺序存储结构；（2）按关键字大小有序排列。 3.

当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。

解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。

二、单项选择题10分（每小题1分，共10小题） 1． D） 2． B） 3． C） 4. C） 5. B） 6. A) 7． C) 8． D) 9． C） 10．C）

三、填空题20分（每空2分，共5小题，10空） 1. S->next=R->next ； R->next=S ； 2． 时间 空间 3． 1300 4． 2h-1 5． high low low high

四、构造题30分（共5小题）

1．（6分）

{ 50，52，22，85，17，36，55，96 } { 50，22，52，17，36，55，85，96 } { 22，50，17，36，52，55，85，96 }

2．（7分）

0 1 2 3 4 5 6 7 8 9 10 K TA BA M D CI X TN I

ASLsucc = ( 1×4 + 2×2 + 3 + 4 + 5 ) / 9 = 20/9

4．（6分）

WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79

五、算法设计题25分（共2小题）

假设有一个长度大于1的循环单链表，表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法，在链表中删除指针s指向的结点。 【 15 分 】 【算法思路】

已知二叉排序树bst，采用二叉链表存储结构。 编写算法，逐层输出二叉排序树中的结点。 【 5 分 】

编写算法，按结点值的递减顺序输出二叉排序树中的结点。 【 5 分 】 【算法思路】

本文来源：https://www.bwwdw.com/article/6b65.html