西北大学《数据结构》试卷(2002)

西北大学《数据结构》A卷（2002）

一、简答题（15分，每小题3分） 1. 简要说明算法与程序的区别。

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

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

二、判断题（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分）

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

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

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

西北大学《数据结构》B卷（2002）

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

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

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

二、判断题（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.