浙江工商大学数据结构期末复习题2

数 据 结 构 习 题 集

一、选择题

１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动 B 个元素。

A. n-1 B. n-i+1 C. n-i-1 D. i ２.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。

A. top不变 Ｂ. top＝ -n C. top＝top-1 D. top=top+1 ３.向顺序栈中压入元素时，是 A 。

A. 先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素 ４.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。

A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 ５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 ６.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 C 。

A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0

７.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是 D 。

A. rear % n= =front B. (rear-1) % n= =front

C. (rear-1) % n= =rear D. (rear+1) % n= =front

８.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2 ９.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 C 。

A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q;

10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs->next=s; B. s->next=hs->next; hs->next=s; C. s->next=hs；hs=s; D. s->next=hs; hs=hs->next;

11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 B 。

A. front->next=s; front=s; B. rear->next=s; rear=s; C. front=front->next; D. front=rear->next;

12.线性表是 A 。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空

1

C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 C 个元素。

A. n+1 B. n-1 C. (n-1)/2 D. n 14.线性表采用链式存储时，其地址 D 。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以

15.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 B 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link; C. p->link=f->link; D. f=nil;

16.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. ((p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink; B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; C. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p; D. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;

17.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针 A 。

A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p; 18.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 B 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表 19.在数据结构中，与所使用的计算机无关的数据叫 C 结构。

A. 存储 B. 物理 C. 逻辑 D. 物理和存储 20.二分法查找 A 存储结构。

A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式

21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 B 。 A. 一定相邻 B. 不一定相邻 C. 有时相邻

23.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉树的结点数为18个，则它的最小高度 B 。 性质2 A. 4 B. 5 C. 6 D. 18 25.在一棵二叉树中第五层上的结点数最多为 C 。 性质1 A. 8 B. 15 C. 16 D. 32 26.在一棵具有五层的满二叉树中，结点总数为 A 。 性质3 A. 31 B. 32 C. 33 D. 16

27.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 B 。 不理解？ A. 1 B. 2 C. 3 D. 4

28.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 为什么不是46？

2

29.在树中除根结点外，其余结点分成m (m≥0)个 A 的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 30.下面答案 D 是查找二叉树（又称二叉排序树）。

A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于１ B. 二叉树中的每个结点的两棵子树的高度差等于１ C. 二叉树中的每个结点的两棵子树是有序的 D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。

31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 B 。 A. 3 B. 4 C. 5 D. 1

32.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是 B 。

A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0

33.在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点 D ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4

36.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有n个顶点的无向完全图，边的总数为 D 条。

A. n-1 B. n C. n+1 D. n*(n-1)/2

38.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e>=n,故可推得深度优先搜索的时间复杂度为 A 。

A. O(e) B. O(n) C. O(ne) D. O(n+e) 39.最小代价生成树 D 。

A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关 40.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于 C 。 A. i+j B. i-j C. 1 D. 0

41.图的深度优先或广度优先遍历的空间复杂性均为 A 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e)

42.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， B 次比较后查找成功；当二分查找值为47的元素时， D 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4

43.散列函数有一个共同性质，即函数值应当以 D 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率

44.设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)＝k % p。为了减少发生冲突的频率，一般取p为 D 。

3

A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数

45.目前以比较为基础的内部排序时间复杂度T(n)的范围是 A ③ ；其比较次数与待 排序的记录的初始排列状态无关的是 B ② 。

A. ①O(log2 n)～O(n) ②O(lon2 n)～O(n2 )

③O(nlog2 n)～O(n2 ) ④O(n)～O(n2 ) ⑤O(n)～O(nlog2 n) B. ①插入排序 ②先用二分法查找，找到后插入排序 ③快速排序 ④冒泡排序

46.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 A 。 A. 6 B. 7 C. 8 D. 20 47.在归并排序过程中，需归并的趟数为 C 。

A. n B. √n C. log2 n向上取整 D. log2 n向下取整

48.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 B 。

A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38)

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

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)

50.在平均情况下快速排序的时间复杂性为 C ，空间复杂性为 B ；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为 D ，空间复杂性为 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 选择题参考答案：

１.B ２.C ３.A ４.A ５.C ６.C ７.D ８.D ９.C 10.C 11.B 12.A 13.C 14.D 15.B 16.B 17.A 18.B 19.C 20.A 21.B 22.D 23.B 24.B 25.C 26.A 27.B 28.C 29.A 30.D 31.B 32.B 33.D 34.B 35.B 36.A 37.D 38.A 39.D 40.C 41.A 42.B,D 43.D 44.D 45.A:③ B:②

46.A 采用选择排序对给定的关键字序列进行排序，只需６次。 47.C 48.B 49.C 50.C B D A 二、填空题

1.在线性结构中第一结点 [1] 无 前驱结点，其余每个结点有且只有 [2] 一 个前驱结点；最后一个结点 [3] 无 后继结点，其余每个结点有且只有 [4] 一 个后继结点。 2.在树型结构中，树根结点没有 [1] 前趋 结点，其余每个结点有且仅有 [2] 一 个前驱结点；树叶结点没有 [3] 后继 结点，其余每个结点的 [4] 后继 结点数不受限制。

3.一个数据结构用二元组表示时，它包括 [1] 数据元素 的集合K和K上 [2]二元关系 的集合R。

4.对于一个二维数组A[1..m,1..n]，若按行序为主序存储，则任一元素A[i,j]的相对地址（即偏移地址）为 [1] (i-1)*n+j-1 。

4

5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 [1] 一半 的元素。

6.对于长度为n的顺序表，插入或删除元素的时间复杂性为 [1] O(n) ；对于顺序栈或队列，插入或删除元素的时间复杂性为 [2] O(1) 。

7.在具有n个单元、顺序存储的循环队列中，队满时共有 [1] n-1 个元素。

8.从顺序表中删除第i个元素时，首先把第i个元素赋给 [1] 变参或函数名 带回，接着从 [2] 链接指针 开始向后的所有元素均 [3] 前移 一个位置，最后使线性表的长度 [4] 减1 。

9.在线性表的顺序存储中，元素之间的逻辑关系是通过 [1] 相邻位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 [2] 链接指针 决定的。 10.一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;

(2)p->data=p->next->data;

(3)p->next= [1] q->next或p->next->next ; (4)free(q);

11.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s->next= [1] p->next ; (2)p->next=s; (3)t=p->data;

(4)p->data= [2] s->data ; (5)s->data= [3] t ;

12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的 [1] 浪费 ，若分配太少又容易在算法中造成 [2] 溢出 ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 [3] 预先分配 存储空间，存储器中的整个 [4] 动态存储区 都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 [5] 溢出 的发生，因此适应数据量变化较大的情况。

13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 [1] O(1) 。 ┏0 0 2 0┓

**14.一个稀疏矩阵为 ┃3 0 0 0┃，则对应的三元组线性表为

┃0 0 -1 5┃ ((1,3,2),(2,1,3),(3,3,-1),(3,4,5))。 ┗0 0 0 0┛

15.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n-1 。

16.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则： n0 = n2 +1 。

17.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 [1] 2 ， 若它存在左孩子，则左孩子结点的下标为 [2] 10 ，若它存在右孩子，则右孩子结点的下标为 [3] 11 。

18.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F))，则该树的深度为 [1]4 ， 度为0的结点数为 [2]3 ，度为1的结点数为 [3] 2 ，度为2的结点数为 [4]2 ；C结点是A 结点的 [5] 右 孩子，E结点是C结点的 [6] 左 孩子。

19.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个有序序列。 20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为

5

55 。

┏━━┳━━┳━━━┓

21.假定在二叉树的链接存储中，每个结点的结构为┃left┃data┃right ┃，其中 ┗━━┻━━┻━━━┛

data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序遍历算法 中画有横线的地方填写合适的语句。

void inorder(bt); { if bt!=nil {

(1) [1] inorder(bt->left) ； (2) [2] printf(bt->data) ；

(3) [3] inorder(bt->right) ；} }

22.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 [1] 度数 ，对于有向图来说等于该顶点的 [2] 出度数 。

23.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 [1] O(n2 ) ， 采用邻接表表示的空间复杂性为 [2] O(n+e) 。

24.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 [1] ABCDFE ，按广度优先搜索遍历得到的顶点序列为 [2] ABCEFD 。 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E ┗0 1 0 1 1 0┛F

25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 20 。 10

① ② 15 5 2 8 ⑤ 12

③ 3 ④

26.假定在有序表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 [1]1 ， 比较两次查找成功的结点数为 [2]2 ，比较三次查找成功的结点数为 [3]4 ，比较四次查找成功结点数为 [4]8 ，比较五次查找成功的结点数为 [5]5 ，平均查找长度为 [6]3.7 。

27.在索引查找或分块查找中，首先查找 [1] 索引表 ，然后再查找相应的 [2] 子表或块 ，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 [3] 和 。

28.在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就 [1] 越大，

6

当α的值越小，存取元素时发生冲突的可能性就 [2] 越小 。

29.给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函数，则元素18的同义词元素共有 [1]2 个，元素25的同义词元素共有 [2]0 个，元素50的同义词元素共有 [3]1 个。

30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 (54,72,60,96,83) 。

31.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为 [1]7 ，在整个冒泡排序过程中共需进行 [2]5 趟后才能完成。

32.在归并排序中，若待排序记录的个数为20，则共需要进行 [1]5 趟归并，在第三趟归并中，是把长度为 [2]4 的有序表归并为长度为 [3]8 的有序表。

33.在直接插入和直接选择排序中，若初始数据基本正序，则选用 [1] 直接插入排序 ，若初始数据基本反序，则选用 [2] 直接选择排序 。

34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 [1] 堆排序 方法，其次选取 [2] 快速排序 方法，最后选取 [3] 归并排序 方法；若只从排序结果的稳定性考虑，则应选取 [4] 归并排序 ；若只从平均情况下排序最快考虑，则应选取 [5] 快速排序 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 [6] 堆排序 方法。

填空题参考答案

1. [1]无 [2]一 [3]无 [4]一 2. [1]前趋 [2]一 [3]后继 [4]后继 3. [1]数据元素 [2]二元关系 4. [1](i-1)*n+j-1 5. [1]一半

6. [1]O(n) [2]O(1) 7. [1]n-1 预先

8. [1]变参或函数名 [2]第i+1个元素 [3]前移 [4]减1 9. [1]相邻位置 [2]链接指针 10.[1]q->next或p->next->next

11.[1]p->next [2]s->data [3]t

12.[1]浪费 [2]溢出 [3] 预先分配 [4]动态存储区 [5]溢出 13.[1]O(1)

14.[1]((1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 15.[1]n-1 16.[1]n2 +1

17.[1]2 [2]10 [3]11 18.[1]4 [2]3 [3]2 [4]2 [5]右 [6]左 19.[1]中序 20.[1]55

21.[1]inorder(bt->left) [2]printf(bt->data)

[3]inorder(bt->right)

7

22.[1]度数 [2]出度数

23.[1]O(n2 ) [2]O(n+e)

24.[1]ABCDFE [2]ABCEFD 25.[1]20

26.[1]1 [2]2 [3]4 [4]8 [5]5 [6]3.7

27.[1]索引表 [2]子表或块 [3]和 28.[1]越大 [2]越小

29.[1]2 [2]0 [3]1 30.[1](54,72,60,96,83) 31.[1]7 [2]5

32.[1]5 [2]4 [3]8 33.[1]直接插入排序 [2]直接选择排序

34.[1]堆排序 [2]快速排序 [3]归并排序 [4]归并排序 [5]快速排序 [6]堆排序 三、判断题

1．数据元素是数据的最小单位（× ）。 2．数据项是数据的基本单位（ × ）。

3．顺序存储的线性表可以随机存取（ √ ）。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象（ √ ）。

5．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（× ）。

6．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ × ）。

7．链表的每个结点中，都恰好包含一个指针（× ）。 **8．数组是同类型值的集合（× ）。 //不是集合// **9．使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（√ ）。

**10.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表（ √ ）。

11.由树转换成二叉树，其根结点的右子树总是空的（√ ）。

12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（ × ）。

13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点（× ）。

14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（√ ）。

15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（× ）。

16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（× ）。

17.有回路的图不能进行拓扑排序（√ ）。

18.连通分量是无向图中的极小连通子图（× ）。 //极大// 19.散列法存储的基本思想是由关键码的值决定数据的存储地址（ √ ）。 20.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（√ ）。

8

21.m阶B-树每一个结点的子树个数都小于或等于m（ √ ）。

22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（√ ）。

23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可（√ ）。

24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素（√ ）。

25.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ √ ）。 26.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)（√ ）。 27.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（ √）。 **28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件（ × ）。 **29.在索引顺序文件中插入新的记录时，必须复制整个文件（× ）。

**30.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上（× ）。 判断题参考答案

１.× ２.× ３.√ ４.√ ５.× ６.× ７.× ８.× ９.√ 10.√ 11.√ 12.× 13.× 14.√ 15.× 16.× 17.√ 18.× 19.√ 20.√ 21.√ 22.√ 23.√ 24.√ 25.√ 26.√ 27.√ 28.× 29.× 30.× 四、综合题

1. 线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?

(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?

(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么? 1. 解答:

(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。

(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。 (3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。

2. 用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?

2.解答: 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。

3. 在单链表和双向表中，能否从当前结点出发访问到任一结点?

3. 解答: 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4. 试述栈的基本性质?

9

4. 解答: 由栈的定义可知，这种结构的基本性质综述如下：

(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；

(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；

(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示； (4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)

其中，n为编号元素的个数，Cn 是可能的排列数目。

5. 何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。

5. 解答: 在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。

这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：

(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现假溢出时，可采用以下几种方法：

①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）；

②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置；

③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上 队尾在队首之前，但逻辑上队首依然在前，作插入和删除运算时仍按“先进先出”的原则。 6. 两个字符串相等的充要条件是什么?

6. 解答: 两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。

**7. 画出广义表(A(B(E，F(J))，C，D(G(K，L)，H，I)))对应的树型结构。

7. 解答: 根据广义表的结构可知，该树的根结点为A；而B、C、D为A的子树，B又有两棵子 树等等，该广义表对应的树型结构见下图。 A

B C D

E F G H I

J K L

**8. 对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。

8. 解答:其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。 9. 试证明：已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。 9. 证明

利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得 到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确

10

定整个二叉树。

假设BT为二叉树的根，P1 ，P2 ，?，Pn 为前序遍历序列，I1 ，I2 ，?，In 为中 序遍历序列。

由前序遍历序列可以得到BT＝P1 。

在中序遍历序列中查找等于P1 的结点，设该结点为Ii ，则有Ii ＝P1 。

根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中序遍历序列中有I1 ，I2 ，?，Ii－1 ，依此序列在前序遍历序列中可以得到其左子树为P2 ， P3 ，?，Pi ；

同理，对于右子树有 Ii＋1 ，Ii＋2 ，?，In Pi＋1 ，Pi＋2 ，?，Pn

对于这两棵子树而言，其左子树的根为P2 ，其右子树的根为Pi＋1 。 依此类推，用同样的方法就可以确定整个二叉树。 10.证明n个顶点的无向完全图的边数的n(n－1)/2。 10.证明 方法一： 用归纳法证明

当n＝1时，边数为0，结论成立。 当n＝2时，边数为1，结论成立。

当n＝1,2?,k时均成立，即当n＝k时，边数为k(k－1)/2。现证明当n＝k＋1时若仍然 成立，则结论正确。

由前面证得，对于有k个顶点时，其边数总和为 k(k－1)/2。 当再增加一个新顶点时，由于是无向完全图，故该顶点到原来各个顶点均有一条边， 这样就共有边数为

k(k－1)/2＋k＝k(k＋1)/2＝(k＋1)[(k＋1)－1]/2

可知当顶点数k＋1时，结论仍然成立，故具有n个顶点的无向完全图的这数为 n(n－1)/2 方法二：

在n个顶点的无向完全图中，每个顶点与其余各顶点均有一条边。第一个顶点到其余 各顶点的边数为n－1，第二个顶点到其余各顶点的边数为n－1，但它与第一个顶点之间的 边已在第一个顶点的边中，故第二个顶点到其它n－2个顶点的边为n－2,?，第n－1个到余下的第n个顶点为边数为1，所以总的边数为 (n－1)＋(n－2)＋(n－3)＋?＋2＋1＝n(n－1)/2 所以其结论成立。

11.证明一个有n个顶点，e条边的无向图G，必有 ∑dj ＝2e

其中dj 为顶点j的度。

11.证明

由度的定义可知，顶点j所联接的边数必为dj 条，另一方面，图G中的任一条边均关联 G中的两个顶点，即一条边均要分别计入两个不同的dj 和di 中，故∑dj 中的边数应为G中边数的两倍，即有

n ∑j ＝2e

11

i-1

12.证明：若无向图G的顶点度数的最小值大于或等于2，则G有一条回路。 12.证明 方法一：

设G＝(V，E)，任取一顶点v1 ∈V，因V1 的度大于或等于2,在v1 的邻接顶点中任取一个不同于v1 的顶点作为v2 。因v2 的度大于或等于2,在v2 的邻接顶点中任取一个不同于v2 的顶 点作为v3 。若v1 、v2 、v3 不构成回路，则在再v3 的邻接顶点中任取一个不同于v3 的的顶点 作为v4 ，??。因为图中顶点的集合V是有限的，当取得某个顶点vi 后，vi＋1 一定为v1 ， v2 ，?，vi-1 之一，因而构成回路。命题得证。

方法二：

设图G有n个顶点，整个图G的度数之和为N，则有 N≥2n

我们知道，图中每条边涉及二个顶点，也就是每条边含有2个度，这样一来，该图G至少有n条边。由于一个n个顶点的树图只有n－1条边，多于n－1条边时则树图就不存在，图中会出现回路。由前面推得，该图至少有n条边，故会出现回路。

13.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同?

(1)查找不成功，即表中没有关键字等于给定值k的记录； (2)查找成功，且表中只有一个关键字等于给定值k的记录；

(3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记 录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。

13.(1) 解答:不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束（假定顺序表是由小到大排列的，对于由大到小排列的情况类似），没有必要查找到表中最后一个关键字才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均长度为(n＋1)/2，而无序顺序表的平均查找长度为n。但从数量级上两者是相同的,即O(n)。 (2) 解答:相同的。其分析类似于(1)。两者在等概率下的平均长度为(n＋1)/2，数量级上为 O(n)。

(3) 解答:不相同。其分析完全与(1)相同，其结论也完全相同。

14.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字 存入到Hash地址空间中要做多少次探测?

14. 解答:由于线性探测的查找次数主要取决于装载因子α，即与Hash地址空间的占用情况 有关。假定初始时Hash地址空间为空，在此情况下连续装入n个具有相同的Hash函数值的 关键字所需的总探测次数为 1＋2＋?＋n＝n(n＋1)/2

15.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，问 (1)每块的理想长度是多少? (2)分成多少块最为理想? (3)平均查找长度是多少?

(4)若每块长度为20，平均查找长度是多少?

12

15.解答：

(1)在给定n的前提下，理想的块长d为√n＝√2000≈45

(2)因查找方法为等分区间顺序查找，长度为n的表被分成b＝[n/d]块，d为块长，故有

b＝[n/d]＝[2000/45]＝45 (3)平均查找长度为

ASL＝b＋d/2＋1＝(45＋45)/2＋1＝46

(4)因每块的长度为20，所以表被分成b块，其平均查找ASL长度为 b＝[n/d]＝[2000/20]＝100

ASL＝(b＋d)/2＋1＝(100＋20)/2＋1＝61

16.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗?为什么? 16. 解答:这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次 序经过排序后发生了变化，而题中未涉及到元素的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以此种说法不对。

17.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?

快速排序，堆排序，归并排序，基数排序的Shell排序。

17. 解答:上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。

**18.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。

18.证明

在排序过程中，每次时行元素的比较产生两种路径。如果排序过程至少需作t次比较， 则有2t 条路径。由于n个结点总共有n 种不同的排列,因而必须有n 种不同的比较路径。于是 2t ≥n!

即 t≥log2 n!

因为 log2 n!＝nlog2 n－n/ln2＋1/2log2 n＋O(1) 故有 log2 n!≈nlog2 n t≥nlog2 n

证毕。

19.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)； (2) (100，98，85，82，80，77，66，60，40，20，10) (3) (100，85，40，77，80，60，66，98，82，10，20)； (4) (10，20，40，60，66，77，80，82，85，98，100)；

19. 解答:根据堆的定义可知堆中元素满足下面中的某一个式子的关系， ┌≤k2i ┌≥k2i ① ki 或 ② ki └≤k2i＋1 └≥k2i＋1

13

因此(1)、(2)和(4)序列是堆。(3)不是堆。

(3) 调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。

**20.试列出文件的存储结构以及其相应文件类型，并简略回答其特点。 20. 解答:

(1)顺序结构，相应的文件为顺序文件。这种文件中的记录按存入文件的时间先后次序顺序存放。当记录的物理存取顺序与它们的关键码大小顺序一致时，则物理顺序和逻辑顺序是一致的。顺序文件适合顺序存取。

(2)计算寻址结构，相应的文件为散列文件。这种文件中的记录，在存放时，是根据它的关键码值经过散列函数计算来确定其地址的，散列函数把一个记录的关键码值经过计算转化为该记录所对应的地址。散列文件适合于随机存取。

(3)带索引的结构，相应的文件为带索引文件。这种文件带有一个索引表，索引表中的每一项内容包含一个关键码值和对应于该关键码值的相应地址。一般情况下，索引表本身是按关键码值的大小顺序排列的，而带索引文件本身内容的物理顺序与其逻辑顺序可以是一致的，也可以是不一致的。带索引文件是以索引表的物理顺序来体现文件的逻辑次序的，即索引表的物理顺序实现了文件的线性结构。

由以上三种文件可以派生出其它类型的文件。 21.编写下列算法

(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (1) 解答: status insert(SqList L,int i,ElemType x){

// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');

(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }

(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }

(2)从类型为list的线性表L中删除其值等于x的所有元素。 (2) 解答: status delete(L,x) {

// 从线性表L中删除其值等于x的所有元素 i＝1;

while (i<＝L.len ) if (L.vec[i]= =x ){

(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[j－1]＝L.vec[j]; (Ⅱ) L.len＝L.len－1;

}

else i＝i＋1; }

(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 (3)解答:status merge(A,B,C){

14

// 将两个有序表A和B合并成一个有序表C (1) if ( A.len＋B.len>m0 ) error('overflow'):

(2) i=1;j＝1;k＝1;

// i和j分别作为扫描数组A和B的指针，k指示存入数组C中元素的下标位置 (3) while (i<＝A.len) && (j<＝B.len) if (A.vec[i]<＝B.vec[j]) { C.vec[k]＝A.vec[i]; i＝i＋1;

k＝k＋1; }

else {C.vec[k]＝B.vec[j]; j＝j＋1; k＝k＋1; } }

(4) while (i<＝A.len){

C.vec[k]＝A.vec[i]; i＝i＋1; k＝k＋1; }

(5) while (j<＝B.len ){

C.vec[k]＝B.vec[j]; j＝j＋1; k＝K＋1; } }

22.编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 22. 解答:

(1)status contrary(HL){

// 使HL单链表中的所有结点按相反次序链接

p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){

(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }

(2)删除单链表中第i个（i≥1）结点。 (2) 解答:status delete(HL,i){

15

(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )

{ HL＝HL->next; return ; }

(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j个结点 while (jnext; }

// 寻找第i个结点的前驱结点 (4) if (p->next!= =nil)

p->next＝p->next->next; else error('out of range'); }

(3)删除单链表中由指针p所指向的结点。 (3) 解答:status delete(HL,P,X){

// 删除单链表HL中由指针p所指向的结点 if (p->next＝nil ) error ('not delete'); X＝p->data; q＝p->next; p->data＝p->next->data; p->next＝p->next->next; free(q); }

或者：

status delete(HL,P,X) { if ( HL＝p ) {

X＝HL->data ; HL＝HL->next; free(p);

} else{

(1) q＝HL;

(2) while (q->next!=nil) && (q->next!=p) q＝q->next; (3) if (q->next＝p){ X＝p->data;

q->next＝p->next;

free(p) }

else error('*p结点不存在');

}

}

(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (4) 解答:status delete(HL,x) {

16

(1) q＝HL; p＝HL->next;

(2) while (p!=HL) && (p->data!=x) { q＝p;

p＝p->next; }

(3) if (p= =HL) error('not found'); else {q->next＝p->next; free(p); } }

(5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (5) 解答:status insert(HL,p,x){ malloc(q);

q->data＝p->data; q->next＝p->next; p->next＝q; p->data＝x; }

(6)从循环单链表中查找出最小值。 (6) 解答: elemtype min(HL){

//从循环单链表HL中查找出最小值 if (HL= =nil ) {

printf('HL＝nil'); return; }

min＝HL->data; p＝HL->next; while (p!=HL) {

(1) if (p->datadata; (2) p＝p->next; } }

(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。

(7) 解答:status create(HL,A,n) {

(1) malloc(HL); q＝HL; // 产生附加表头结点

(2) for (i＝1 ;I<=n ;++i) { // 完成n个元素的依次链接 malloc(p);

p->data＝A(i); q->next＝p; q＝p; }

(3) q->next＝nil ; // 把最后一个结点的指针域置空 }

17

23.请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); {

if n>0 {

p(n-2);

printf(“%d”,n); } }

23. 解答:这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5；当n＝6时，其输出结果为2、4、6。 24.假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法：

(1)向循环链队插入一个元素为x的结点； (1) 解答:status insert(Rear,x){

// 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p);

p->data＝x; // 建立值为x的新结点p＾ (2) if( Rear＝nil){

Rear＝p; Rear->next＝p;

}

else {p->next＝Rear->next;

Rear->next＝p; Rear＝p; }

// 若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点 }

(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。 (2) 解答:status delete(Rear){

if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil; else Rear->next＝Rear->next->next;

} //Rear＾.next 所指向的结点为循环链队的队首结点

25.设A(k)有如下10个元素：2，4，6，8，10，12，14，16，18，20。若对A(k)分别查找x＝1，3，13，21，试跟踪下面过程的执行，并分析该程序段关于n的计算时间。 【程序段】 i=1;j=n; do {

k=(i+j)/2;

if A(k)<=x i=k+1

18

else j=k-1 }while !(i>j);

25.解答

(1)查找x＝1,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? X ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 1 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 1 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 > 1 ┃ 新j＝k－1＝0 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝1)>(j＝0)时，过程终止。未找到。 (2)查找x＝3,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 3 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 3 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 < 3 ┃ 新i＝k＋1＝2 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝2)>(j＝1)时，过程终止。未找到。 (3)查找x＝13,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <13 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 >13 ┃ 新j＝k－1＝7 ┃ ┃第3次┃6 ┃7 ┃6 ┃ 12 <13 ┃ 新i＝k＋1＝7 ┃ ┃第4次┃7 ┃7 ┃7 ┃ 14 >13 ┃ 新j＝k－1＝6 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝7)>(j＝6)时，过程终止。未找到。 (4)查找x＝21,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃ A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <21 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 <21 ┃ 新i＝k＋1＝9 ┃ ┃第3次┃9 ┃10┃9 ┃ 18 <21 ┃ 新i＝k＋1＝10┃ ┃第4次┃10┃10┃10┃ 20 <21 ┃ 新i＝k＋1＝11┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛

当(i＝11)>(j＝10)时，过程终止，未找到。该程序段的时间复杂型为O(log2 n)。

19

**26.分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。 26. 解答:中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{

(1) while (p!=nil ){ top＝top＋1; s[top]＝p;

p:＝p->left; //p指向左子树 }

(2) if (top>0 ){

p＝s[top]; top＝top－1; printf(p->data);

p＝p->right; // p指向右子树 }

}while !((top＝0) && (p＝nil)); }

解答: 先根遍历的非递归算法： status preorder(bt) { top＝0; p＝bt do{

(1) while( p!=nil ){

printf (p->data); if (p->right!=nil){ top＝top＋1;

s[top]＝p->right; }

//若右子树非空，则把链接指针保存起来， 待访问过左子树后再访问它 p＝p->left; //使p指向左子树 }

(2) if (top>0) { // 出栈，使p指向右子树 p＝s[top] top＝top－1; }

}while !((top＝0) && (p＝nil)); }

20

27.设有一个已排序的整数数组a[1..n]，和一个整数x，研究下面用类C所表示的折半查找的五个程序段，指出哪些是正确的。 第一个： i=1; j=n;

do{ k=(i+j)div 2;

if x>a[k] i=k+1; else j=k-1; }while !((a[k]=x) || (i>j)); 第二个: i=1; j=n;

while (i<=j) { k=(i+j) / 2;

switch{

case x>a[k]: i=k+1; case x= =a[k]: return; case x

第三个： i=1; j=n;

do{ k=(i+j) / 2;

if x>a[k] i=k; else j=k

}while !((a[k]= =x) || (i>=j)); 第四个： i＝1; j=n;

do{ k=(i+j) / 2;

if xa[k] i=k+1; }while !(i>=j); 第五个： i=1; j=n;

do{ k=(i+j) / 2; if x=j); 27. 解答:

第三个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝(1＋2) div 2，又因a[k]

第五个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝1,又因x

21

并不等于x，即求出的k是错误的。

第一、二、四个程序段是正确的折半查找算法的表示。

28.设a、b、c、d都是串名，a＝'THIS IS A BOOK'，b＝'ESE ARE'，C＝'S'。 求d＝CONCAT(SUB(a,1,2)，b，SUB(a,10,5),c)＝？ 28. 解答: d＝'THESE ARE BOOKS'

**29.数组b[1..10,-2..6,2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。试求元素b[5,0,7]的存储首址。

29. 解答:由三维数组中的数据元素存储位置的计算公式（以行为主存储）为 LOC(i,j,k)＝LOC(c1 ,c2 ,c3 )＋[(i－c1 )(d2 －c2 ＋1)(d3 －c3 ＋1)] ＋(j－c2 )(d3 －c3 ＋1)＋(k－c3 )]×l

＝100＋(4×9×7＋2×7＋5)×3＝913 **30.在n×n(n≥3)的稀疏矩阵A中，只有下标满足1

30.解答: 根据题意可知这个矩阵的第一行和第n行的元素均为零。对满足2≤i≤n－1的各 行，除ai,n-i ，ai,n-i+1 ，ai,n-i+2 三个元素外，其它元素均为零。其矩阵的形状为

┏ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┓ ┃ ０ ０ ０ ０ ? ? ０ a2,n-2 a2,n-1 a2,n ┃ ┃ ０ ０ ０ ０ a3,n-3 a3,n-2 a3,n-1 ０ ┃ Ａ＝ ┃ ┃ ┃an-1,1 an-1,2 an-1,3 ０ ? ? ０ ０ ０ ０ ┃

┗ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┛ 如果按行优先顺序存放这些非零元素，可得如下序列：

a2,n-2 a2,n-1 a2,n a3,n-3 a3,n-2 a3,n-1 ? an-1,1 an-1,2 an-1,3 把它 们顺序存放在以FIRST为首址的一个连续的存储空间中，前i-1行共中非零元素3*(i-2)个， 在非零的aij 前，本行还有非零元素的个数为j－(n－i)个，若第一个非零元素a2,n-2 的存储地址为LOC(a2,n-2 ),则非零元素aij 的地址可用下式求出 LOC(aij )＝LOC(a2,n-2 )＋3×(i-2)＋(i＋j－n) 其中 2≤i≤n－1,n≤i＋j≤n＋2

即 LOC(aij )＝FIRST＋3×(i－2)＋(i＋j－n)

**31.用三元组表示下面稀疏矩阵的转置矩阵。 ┏0 1 0 0 0┓ ┃2 0 0 0 3┃ M＝┃0 0 4 0 0┃ ┗0 0 0 5 0┛

31. 解答:矩阵的转置运算是一种简单的运算，其方法是：

(1)把矩阵的行列值相互交换，所以一个m×n的矩阵M，它的转置矩阵N是一种n×m的矩阵；

(2)将每个三元组中的i和j相互交换；

(3)按交换后的行号从小到大重排三元组中各元素的次序。

由以上三条可得转置矩阵的三元组为

22

i j data ━━┳━━━┳━━ 1 ┃ 2 ┃ 2 2 ┃ 1 ┃ 1 3 ┃ 3 ┃ 4 4 ┃ 4 ┃ 5 5 ┃ 2 ┃ 3 ━━┻━━━┻━━ **32.给出下列每个广义表的相关运算。 (1) A＝(a，b，c，d) head(A) tail(A) (2) C＝((a，b)，(c，d)) head(C) head(tail(C))

32. 解答: (1)head(A)＝a (2)tail(A)＝(b,c,d) tail(A)＝(b,c,d) head(tail(C))＝(c,d)

33.已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。

33. 解答:得到的二叉排序树如下图所示。 46

25 78

18 34 62

12 40 73 34.已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题： (1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？ (2)树的度是多少？各个结点的度是多少？

(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？ (4)对于结点Ｇ，它的双亲是哪个结点？它的祖先是哪些结点？它的孩子是哪些结点？ 它的子孙是哪些结点？它的兄弟和堂兄弟分别是哪些结点？ 34. 解答:

(1)树的根是A，而E、F、C、H、I、J、K、M、N是叶子结点，其它为非终端结点。 (2)树的度为4。deg(A)＝3,deg(B)＝2,deg(D)＝4,deg(G)＝3,deg(L)＝1，其它各叶子结点的度均为0。

(3)树的深度为5（设根结点的深度为1）。level(A)＝1,level(B)＝2,level(C)＝2, ?,level(G)＝3,?,level(K)＝4,?，level(N)＝5。

(4)D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、 J是G的兄弟；E、F是G的堂兄弟。

35.设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。

35. 解答:最大值(高度为h的满二叉树) 20 ＋21 ＋22 ＋?＋2h-1 ＝2h －1

23

最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值为2h-1个。 36.设二叉树BT的存储结构如下：

１ ２ ３ ４ ５ ６ ７ ８ ９ 10 ┏━┳━┳━┳━┳━┳━┳━┳━┳━┳━┓ Lchild ┃０┃０┃２┃３┃７┃５┃８┃０┃10┃１┃ ┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫ data ┃Ｊ┃Ｈ┃Ｆ┃Ｄ┃Ｂ┃Ａ┃Ｃ┃Ｅ┃Ｇ┃Ｉ┃ ┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫ Rchild ┃０┃０┃０┃９┃４┃０┃０┃０┃０┃０┃ ┗━┻━┻━┻━┻━┻━┻━┻━┻━┻━┛

(1) 画出图。

(2) 写出前序、中序、后序遍历次序。 (3) 画出后序线索二叉树.

36. 解答: (1)见下图。 A

B

C D

E F G

H I

J (2)前序遍历：ABCEDFHGIJ 中序遍历：ECBHFDJIGA 后序遍历：ECHFJIGDBA

(3)后序线索化树见下图：

A NIL

B

C D

NIL E F G

H I

J 37.已知一棵二叉树先序遍历结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，试 画出该二叉树。

37. 解答:由前序遍历结果可知该二叉树的根结点为Ａ。由此及中序遍历结果可

24

知，该二叉树在中序遍历下的左、右子树为 CBED和HGIJF

依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ

B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A

B F

C D G

E H I

J 38.设无向图G如下图：

B E

A D G

C F 试给出

(1)该图的邻接矩阵； (2)该图的邻接表；

(3)从A出发的“深度优先”遍历序列； (4)从A出发的“广度优先”遍历序列。

38. 解答: (1) 图G的邻接矩阵

┏０ １ １ ０ ０ ０ ０┓ ┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)邻接表如见：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│

25

├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ ５│Ｅ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ６│Ｆ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ７│Ｇ│ ┼→─┤Ｅ│ ┼→─┤Ｆ│＾│ └─┴─┘ └─┴─┘ └─┴─┘

(3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G 39.假定一个待散列存储的线性表为(32、75、63、48、94、25、36、18、70)散列地址空间为[0..10]，若采用除留余数法构造散列函数和线性探查法处理冲突，试给出它们对应的散列表，并求出在等概北情况下的平均查找长度。 39. 解答:

k 32 75 63 48 94 25 36 18 70 k 10 9 8 4 6 3 3 7 4

得到的散列表如下：

0 1 2 3 4 5 6 7 8 9 10 ┏━┯━┯━┯━┯━┯━┯━┯━┯━┯━┯━┓ ┃70│ │ │25│48│36│94│18│63│75│32┃ ┗━┷━┷━┷━┷━┷━┷━┷━┷━┷━┷━┛ 成功到位次数 8 1 1 3 1 1 1 1 1 不成功到位次数 2 1 1 10 9 8 7 6 5 4 3 查找成功的平均查找长度为 : (8+1+1+3+1+1+1+1+1)/9=2

查找不成功的平均查找长度为 : (2+1+1+10+9+8+7+6+5+4+3)/11=56/11 40.什么是内部排序？什么是排序方法的稳定性和不稳定性？

40. 解答:假设给定含有n个记录(R1 ，R2 ，?，Rn ）的文件，其相应的关键字为(K1 ，K2 ，?， Kn )，则排序是确定一个排列P(1)，P(2)，?，P(n)，使得KP(1) ≤KP(2) ，?，KP(n) ，

从而得到有序文件(RP(1) ，RP(2) ，?，RP(n) )。整个排序过程都在内存进行的排序称为 内部排序。

假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排 序法排序后，若这些相同关键字的记录的相对次序仍然保持不变，则这种排序方法是稳定 的，否则称这种排序方法是不稳定的。

26

综合题参考答案 1. 解:

(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。

(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。 (3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。

2. 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。

3. 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。

4. 由栈的定义可知，这种结构的基本性质综述如下：

(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；

(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；

(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示； (4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)

其中，n为编号元素的个数，Cn 是可能的排列数目。

5. 在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。

这里要特别注意的是：队列的虚溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：

(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现虚溢出时，可采用以下几种方法：

①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）；

②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置；

27

③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上 队尾在队首之前，但逻辑上队首依然在前，作插入和删除运算时仍按“先进先出”的原则。 6. 两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。 7. 根据广义表的结构可知，该树的根结点为A；而B、C、D为A的子树，B又有两棵子 树等等，该广义表对应的树型结构见下图。 A

B C D

E F G H I

J K L

8. 其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。 9. 证明

利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得 到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确定整个二叉树。

假设BT为二叉树的根，P1 ，P2 ，?，Pn 为前序遍历序列，I1 ，I2 ，?，In 为中 序遍历序列。

由前序遍历序列可以得到BT＝P1 。

在中序遍历序列中查找等于P1 的结点，设该结点为Ii ，则有Ii ＝P1 。

根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中序遍历序列中有I1 ，I2 ，?，Ii－1 ，依此序列在前序遍历序列中可以得到其左子树为P2 ， P3 ，?，Pi ；

同理，对于右子树有 Ii＋1 ，Ii＋2 ，?，In Pi＋1 ，Pi＋2 ，?，Pn

对于这两棵子树而言，其左子树的根为P2 ，其右子树的根为Pi＋1 。 依此类推，用同样的方法就可以确定整个二叉树。 10.证明 方法一： 用归纳法证明

当n＝1时，边数为0，结论成立。 当n＝2时，边数为1，结论成立。

当n＝1,2?,k时均成立，即当n＝k时，边数为k(k－1)/2。现证明当n＝k＋1时若仍然 成立，则结论正确。

由前面证得，对于有k个顶点时，其边数总和为 k(k－1)/2。 当再增加一个新顶点时，由于是无向完全图，故该顶点到原来各个顶点均有一条边， 这样就共有边数为

k(k－1)/2＋k＝k(k＋1)/2＝(k＋1)[(k＋1)－1]/2

可知当顶点数k＋1时，结论仍然成立，故具有n个顶点的无向完全图的这数为 n(n－1)/2 方法二：

28

在n个顶点的无向完全图中，每个顶点与其余各顶点均有一条边。第一个顶点到其余 各顶点的边数为n－1，第二个顶点到其余各顶点的边数为n－1，但它与第一个顶点之间的 边已在第一个顶点的边中，故第二个顶点到其它n－2个顶点的边为n－2,?，第n－1个到余下的第n个顶点为边数为1，所以总的边数为 (n－1)＋(n－2)＋(n－3)＋?＋2＋1＝n(n－1)/2 所以其结论成立。 11.证明

由度的定义可知，顶点j所联接的边数必为dj 条，另一方面，图G中的任一条边均关联 G中的两个顶点，即一条边均要分别计入两个不同的dj 和di 中，故∑dj 中的边数应为G中边数的两倍，即有

n ∑j ＝2e

i-1 12.证明 方法一：

设G＝(V，E)，任取一顶点v1 ∈V，因V1 的度大于或等于2,在v1 的邻接顶点中任取一个 不同于v1 的顶点作为v2 。因v2 的度大于或等于2,在v2 的邻接顶点中任取一个不同于v2 的顶 点作为v3 。若v1 、v2 、v3 不构成回路，则在再v3 的邻接顶点中任取一个不同于v3 的的顶点 作为v4 ，??。因为图中顶点的集合V是有限的，当取得某个顶点vi 后，vi＋1 一定为v1 ， v2 ，?，vi-1 之一，因而构成回路。命题得证。 方法二：

设图G有n个顶点，整个图G的度数之和为N，则有 N≥2n

我们知道，图中每条边涉及二个顶点，也就是每条边含有2个度，这样一来，该图G至 少有n条边。由于一个n个顶点的树图只有n－1条边，多于n－1条边时则树图就不存在，图 中会出现回路。由前面推得，该图至少有n条边，故会出现回路。

13.(1)不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束（假定顺序表是由小到大排列的，对于由大到小排列的情况类似），没有必要查找到表中最后一个关键字才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均长度为(n＋1)/2，而无序顺序表的平均查找长度为n。但从数量级上两者是相同的,即O(n)。

(2)相同的。其分析类似于(1)。两者在等概率下的平均长度为(n＋1)/2，数量级上为 O(n)。

(3)不相同。其分析完全与(1)相同，其结论也完全相同。

14.由于线性探测的查找次数主要取决于装载因子α，即与Hash地址空间的占用情况 有关。假定初始时Hash地址空间为空，在此情况下连续装入n个具有相同的Hash函数值的 关键字所需的总探测次数为

1＋2＋?＋n＝n(n＋1)/2 15.解答：

(1)在给定n的前提下，理想的块长d为√n＝√2000≈45

(2)因查找方法为等分区间顺序查找，长度为n的表被分成b＝[n/d]块，d为块长，故有

b＝[n/d]＝[2000/45]＝45

29

(3)平均查找长度为

ASL＝b＋d/2＋1＝(45＋45)/2＋1＝46

(4)因每块的长度为20，所以表被分成b块，其平均查找ASL长度为 b＝[n/d]＝[2000/20]＝100

ASL＝(b＋d)/2＋1＝(100＋20)/2＋1＝61

16.这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次 序经过排序后发生了变化，而题中未涉及到元素的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以此种说法不对。

17.上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。 18.证明

在排序过程中，每次时行元素的比较产生两种路径。如果排序过程至少需作t次比较， 则有2t 条路径。由于n个结点总共有n 种不同的排列,因而必须有n 种不同的比较路径。于是 2t ≥n!

即 t≥log2 n!

因为 log2 n!＝nlog2 n－n/ln2＋1/2log2 n＋O(1) 故有 log2 n!≈nlog2 n t≥nlog2 n

证毕。

19.根据堆的定义可知堆中元素满足下面中的某一个式子的关系， ┌≤k2i ┌≥k2i ① ki 或 ② ki

└≤k2i＋1 └≥k2i＋1 因此(1)、(2)和(4)序列是堆。(3)不是堆。

(3) 调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。 20.

(1)顺序结构，相应的文件为顺序文件。这种文件中的记录按存入文件的时间先后次序顺序存放。当记录的物理存取顺序与它们的关键码大小顺序一致时，则物理顺序和逻辑顺序是一致的。顺序文件适合顺序存取。

(2)计算寻址结构，相应的文件为散列文件。这种文件中的记录，在存放时，是根据它的关键码值经过散列函数计算来确定其地址的，散列函数把一个记录的关键码值经过计算转化为该记录所对应的地址。散列文件适合于随机存取。

(3)带索引的结构，相应的文件为带索引文件。这种文件带有一个索引表，索引表中的每一项内容包含一个关键码值和对应于该关键码值的相应地址。一般情况下，索引表本身是按关键码值的大小顺序排列的，而带索引文件本身内容的物理顺序与其逻辑顺序可以是一致的，也可以是不一致的。带索引文件是以索引表的物理顺序来体现文件的逻辑次序的，即索引表的物理顺序实现了文件的线性结构。

由以上三种文件可以派生出其它类型的文件。 21.编写算法

(1)status insert(SqList L,int i,ElemType x){

// 向线性表L中第i个元素之后插入值为x的新元素

30

(1) if (L.len = =m0) error('overflow'); (2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }

(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }

(2)status delete(L,x) {

// 从线性表L中删除其值等于x的所有元素 i＝1;

while (i<＝L.len ) if (L.vec[i]= =x ){

(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[j－1]＝L.vec[j]; (Ⅱ) L.len＝L.len－1;

}

else i＝i＋1; }

(3)status merge(A,B,C){

// 将两个有序表A和B合并成一个有序表C (1) if ( A.len＋B.len>m0 ) error('overflow'):

(2) i=1;j＝1;k＝1;

// i和j分别作为扫描数组A和B的指针，k指示存入数组C中元素的下标位置 (3) while (i<＝A.len) && (j<＝B.len) if (A.vec[i]<＝B.vec[j]) { C.vec[k]＝A.vec[i]; i＝i＋1;

k＝k＋1; }

else {C.vec[k]＝B.vec[j]; j＝j＋1; k＝k＋1; } }

(4) while (i<＝A.len){

C.vec[k]＝A.vec[i]; i＝i＋1; k＝k＋1; }

(5) while (j<＝B.len ){

C.vec[k]＝B.vec[j]; j＝j＋1; k＝K＋1;

31

} }

22.编写算法

(1)status contrary(HL){

// 使HL单链表中的所有结点按相反次序链接

p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){

(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }

(2)status delete(HL,i){

(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )

{ HL＝HL->next; return ; }

(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j个结点 while (jnext; }

// 寻找第i个结点的前驱结点 (4) if (p->next!= =nil)

p->next＝p->next->next; else error('out of range'); }

(3)status delete(HL,P,X){

// 删除单链表HL中由指针p所指向的结点 if (p->next＝nil ) error ('not delete'); X＝p->data; q＝p->next;

p->data＝p->next->data; p->next＝p->next->next; free(q); }

或者：

status delete(HL,P,X) { if ( HL＝p ) {

X＝HL->data ;

HL＝HL->next;

32

free(p); } else{

(1) q＝HL;

(2) while (q->next!=nil) && (q->next!=p) q＝q->next; (3) if (q->next＝p){ X＝p->data;

q->next＝p->next;

free(p) }

else error('*p结点不存在');

}

}

(4)status delete(HL,x) {

(1) q＝HL; p＝HL->next;

(2) while (p!=HL) && (p->data!=x) { q＝p;

p＝p->next; }

(3) if (p= =HL) error('not found'); else {q->next＝p->next; free(p); } }

(5)status insert(HL,p,x){ malloc(q);

q->data＝p->data; q->next＝p->next; p->next＝q; p->data＝x; }

(6) elemtype min(HL){

//从循环单链表HL中查找出最小值 if (HL= =nil ) {

printf('HL＝nil'); return; }

min＝HL->data; p＝HL->next; while (p!=HL) {

(1) if (p->datadata; (2) p＝p->next; }

33

}

(7)status create(HL,A,n) {

(1) malloc(HL); q＝HL; // 产生附加表头结点

(2) for (i＝1 ;I<=n ;++i) { // 完成n个元素的依次链接 malloc(p);

p->data＝A(i); q->next＝p; q＝p; }

(3) q->next＝nil ; // 把最后一个结点的指针域置空 }

23.这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5；当n＝6时，其输出结果为2、4、6。 24.循环链队的插入和删除操作 (1)status insert(Rear,x){

// 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p);

p->data＝x; // 建立值为x的新结点p＾ (2) if( Rear＝nil){

Rear＝p; Rear->next＝p;

}

else {p->next＝Rear->next;

Rear->next＝p; Rear＝p; }

// 若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点 }

(2)status delete(Rear){

if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil; else Rear->next＝Rear->next->next;

} //Rear＾.next 所指向的结点为循环链队的队首结点 25.解答

(1)查找x＝1,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? X ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 1 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 1 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 > 1 ┃ 新j＝k－1＝0 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝1)>(j＝0)时，过程终止。未找到。 (2)查找x＝3,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃

34

┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 3 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 3 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 < 3 ┃ 新i＝k＋1＝2 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝2)>(j＝1)时，过程终止。未找到。 (3)查找x＝13,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <13 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 >13 ┃ 新j＝k－1＝7 ┃ ┃第3次┃6 ┃7 ┃6 ┃ 12 <13 ┃ 新i＝k＋1＝7 ┃ ┃第4次┃7 ┃7 ┃7 ┃ 14 >13 ┃ 新j＝k－1＝6 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝7)>(j＝6)时，过程终止。未找到。 (4)查找x＝21,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃ A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <21 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 <21 ┃ 新i＝k＋1＝9 ┃ ┃第3次┃9 ┃10┃9 ┃ 18 <21 ┃ 新i＝k＋1＝10┃ ┃第4次┃10┃10┃10┃ 20 <21 ┃ 新i＝k＋1＝11┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛

当(i＝11)>(j＝10)时，过程终止，未找到。该程序段的时间复杂型为O(log2 n)。 26.中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{

(1) while (p!=nil ){ top＝top＋1; s[top]＝p;

p:＝p->left; //p指向左子树 }

(2) if (top>0 ){

p＝s[top]; top＝top－1; printf(p->data);

p＝p->right; // p指向右子树 }

}while !((top＝0) && (p＝nil)); }

先根遍历的非递归算法：

35

status preorder(bt) { top＝0; p＝bt do{

(1) while( p!=nil ){

printf (p->data); if (p->right!=nil){ top＝top＋1;

s[top]＝p->right; }

//若右子树非空，则把链接指针保存起来， 待访问过左子树后再访问它 p＝p->left; //使p指向左子树 }

(2) if (top>0) { // 出栈，使p指向右子树 p＝s[top] top＝top－1; }

}while !((top＝0) && (p＝nil)); } 27.答：

第三个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝(1＋2) div 2，又因a[k]

第五个程序段不正确。例如，令n＝2,a[1]＝5,a[2]＝6,x＝6,则开始时，i＝1,j＝2, k＝1,又因x

第一、二、四个程序段是正确的折半查找算法的表示。 28. d＝'THESE ARE BOOKS'

29. 由三维数组中的数据元素存储位置的计算公式（以行为主存储）为 LOC(i,j,k)＝LOC(c1 ,c2 ,c3 )＋[(i－c1 )(d2 －c2 ＋1)(d3 －c3 ＋1)] ＋(j－c2 )(d3 －c3 ＋1)＋(k－c3 )]×l

＝100＋(4×9×7＋2×7＋5)×3＝913

30. 根据题意可知这个矩阵的第一行和第n行的元素均为零。对满足2≤i≤n－1的各 行，除ai,n-i ，ai,n-i+1 ，ai,n-i+2 三个元素外，其它元素均为零。其矩阵的形状为

┏ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┓ ┃ ０ ０ ０ ０ ? ? ０ a2,n-2 a2,n-1 a2,n ┃ ┃ ０ ０ ０ ０ a3,n-3 a3,n-2 a3,n-1 ０ ┃ Ａ＝ ┃ ┃ ┃an-1,1 an-1,2 an-1,3 ０ ? ? ０ ０ ０ ０ ┃

┗ ０ ０ ０ ０ ? ? ０ ０ ０ ０ ┛ 如果按行优先顺序存放这些非零元素，可得如下序列：

a2,n-2 a2,n-1 a2,n a3,n-3 a3,n-2 a3,n-1 ? an-1,1 an-1,2 an-1,3 把它 们顺序存放在以FIRST为首址的一个连续的存储空间中，前i-1行共中非零元素3*(i-2)个， 在非零的aij 前，本行还有非零元素的个数为j－(n－i)个，若第一个非零元素a2,n-2 的存储地址为LOC(a2,n-2 ),则非零元素aij 的地址可用下式求出

36

LOC(aij )＝LOC(a2,n-2 )＋3×(i-2)＋(i＋j－n) 其中 2≤i≤n－1,n≤i＋j≤n＋2

即 LOC(aij )＝FIRST＋3×(i－2)＋(i＋j－n)

31.矩阵的转置运算是一种简单的运算，其方法是：

(1)把矩阵的行列值相互交换，所以一个m×n的矩阵M，它的转置矩阵N是一种n×m的矩阵；

(2)将每个三元组中的i和j相互交换；

(3)按交换后的行号从小到大重排三元组中各元素的次序。 由以上三条可得转置矩阵的三元组为 i j data ━━┳━━━┳━━ 1 ┃ 2 ┃ 2 2 ┃ 1 ┃ 1 3 ┃ 3 ┃ 4 4 ┃ 4 ┃ 5 5 ┃ 2 ┃ 3 ━━┻━━━┻━━

32.(1)head(A)＝a (2)tail(A)＝(b,c,d) tail(A)＝(b,c,d) head(tail(C))＝(c,d) 33.得到的二叉排序树如下图所示。 46

25 78

18 34 62

12 40 73

34.解：

(1)树的根是A，而E、F、C、H、I、J、K、M、N是叶子结点，其它为非终端结点。 (2)树的度为4。deg(A)＝3,deg(B)＝2,deg(D)＝4,deg(G)＝3,deg(L)＝1，其它各叶子结点的度均为0。

(3)树的深度为5（设根结点的深度为1）。level(A)＝1,level(B)＝2,level(C)＝2, ?,level(G)＝3,?,level(K)＝4,?，level(N)＝5。

(4)D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、 J是G的兄弟；E、F是G的堂兄弟。 35.最大值

20 ＋21 ＋22 ＋?＋2h-1 ＝2h －1

最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值为2h-1个。

36.(1)见下图。

A

37

B

C D

E F G

H I

J (2)前序遍历：ABCEDFHGIJ 中序遍历：ECBHFDJIGA 后序遍历：ECHFJIGDBA

(3)后序线索化树见下图：

A NIL

B

C D

NIL E F G

H I

J 37.由前序遍历结果可知该二叉树的根结点为Ａ。由此及中序遍历结果可知，该二叉树在中序遍历下的左、右子树为

CBED和HGIJF

依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ

B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A

B F

C D G

E H I

J

38. (1) 图G的邻接矩阵

┏０ １ １ ０ ０ ０ ０┓

38

┃１ ０ ０ １ ０ ０ ０┃ ┃１ ０ ０ １ ０ ０ ０┃ A＝┃０ １ １ ０ １ １ ０┃ ┃０ ０ ０ １ ０ ０ １┃ ┃０ ０ ０ １ ０ ０ １┃ ┗０ ０ ０ ０ １ １ ０┛ (2)邻接表如见：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐ １│Ａ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ２│Ｂ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ３│Ｃ│ ┼→─┤Ａ│ ┼→─┤Ｄ│＾│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ ┌─┬─┐ ４│Ｄ│ ┼→─┤Ｂ│ ┼→─┤Ｃ│ ┼→┤Ｅ│＾├→─┤Ｆ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ ５│Ｅ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ６│Ｆ│ ┼→─┤Ｄ│ ┼→─┤Ｇ│＾│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ７│Ｇ│ ┼→─┤Ｅ│ ┼→─┤Ｆ│＾│ └─┴─┘ └─┴─┘ └─┴─┘

(3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G

39.平均查找长度等于2，得到的散列表如下：

0 1 2 3 4 5 6 7 8 9 10 ┏━┯━┯━┯━┯━┯━┯━┯━┯━┯━┯━┓ ┃70│ │ │25│48│36│94│18│63│75│32┃ ┗━┷━┷━┷━┷━┷━┷━┷━┷━┷━┷━┛

40.假设给定含有n个记录(R1 ，R2 ，?，Rn ）的文件，其相应的关键字为(K1 ，K2 ，?， Kn )，则排序是确定一个排列P(1)，P(2)，?，P(n)，使得KP(1) ≤KP(2) ，?，KP(n)，从而得到有序文件(RP(1) ，RP(2) ，?，RP(n) )。整个排序过程都在内存进行的排序称为内部排序。

假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的记录的相对次序仍然保持不变，则这种排序方法是稳定的，否则称这种排序方法是不稳定的。

39

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