《数据结构》

1．下面关于线性表的叙述中，错误的是哪一个？（ B   ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（  C  ）的有限序列（n>0）。 

A．表元素      B．字符      C．数据元素     D．数据项         E．信息项

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A   ）存储方式最节省时间。

A．顺序表      B．双链表        C．带头结点的双循环链表     D．单循环链表

3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D   ）存储方式最节省运算时间。

A．单链表     B．仅有头指针的单循环链表     C．双链表       D．仅有尾指针的单循环链表

4. 静态链表中指针表示的是（  C  ）. 

A． 内存地址       B．数组下标     C．下一元素地址      D．左、右孩子地址

5. 链表不具有的特点是（  B  ） 

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

 C．不必事先估计存储空间  D．所需空间与线性长度成正比

1. 对于栈操作数据的原则是（ B  ）。

A. 先进先出    B. 后进先出    C. 后进后出     D. 不分顺序

2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ A   ）

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 

3. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。

A. 1，2，4，3，        B. 2，1，3，4，        C. 1，4，3，2， 

D. 4，3，1，2，        E. 3，2，1，4，

1. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，求A[6，8]的地址。1340

2. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，求A[5，9]的地址。1196

1．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）

A．9            B．11         C．15       D．不确定 

2．具有10个叶结点的二叉树中有（ B ）个度为2的结点， 

A．8           B．9             C．10          D．ll

3. 设给定权值总数有n 个，其哈夫曼树的结点总数为(  D ) 

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

4．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（A ）。

A．n-1      B．n/m-1       C．(n-1)/(m-1)     D． n/(m-1)-1   E．(n+1)/(m+1)-1

5. 有关二叉树下列说法正确的是（  B  ）

A．二叉树的度为2                   B．一棵二叉树的度可以小于2                                                                                 

C．二叉树中至少有一个结点的度为2   D．二叉树中任何一个结点的度都为2

1．图中有关路径的定义是（ A   ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列      B．由不同顶点所形成的序列

C．由不同边所形成的序列                          D．上述定义都不是

2．设无向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1        B．n(n-1)/2       C． n(n+1)/2        D．0       E．n2

3．一个n个顶点的连通无向图，其边的个数至少为（ A   ）。

A．n-1           B．n            C．n+1             D．nlogn；

4．要连通具有n个顶点的有向图，至少需要（  B  ）条边。

A．n-l           B．n            C．n+l             D．2n

5．n个结点的完全有向图含有边的数目（　D　　）。【中山大学 1998 二、9 （2分）】

A．n*n        Ｂ．n（n＋１）     C．n／2            D．n*（n－l）

6．一个有n个结点的图，最少有（ B   ）个连通分量，最多有（  D  ）个连通分量。

A．0                B．1                 C．n-1             D．n

7．在一个无向图中，所有顶点的度数之和等于所有边数（  B  ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C   ）倍。

A．1/2          B．2             C．1               D．4

8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A )。

A．5          B．6               C．8               D．9     

9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。

A．逆拓扑有序         B．拓扑有序            C．无序的      

10．下列哪一种图的邻接矩阵是对称矩阵？（ B   ）

A．有向图            B．无向图           C．AOV网          D．AOE网

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(C  )。【北京航空航天大学 2000 一、8 （2分）】                      

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

2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A  ) 

A．（N+1）/2      B. N/2      C. N      D. [（1+N）*N ]/2

3. 下面关于二分查找的叙述正确的是  ( D  ) 

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储  

B. 表必须有序且表中数据必须是整型，实型或字符型       

C. 表必须有序，而且只能从小到大排列

D. 表必须有序，且表只能以顺序方式存储

4. 对线性表进行二分查找时，要求线性表必须（  B ）

A.以顺序方式存储      B.以顺序方式存储,且数据元素有序 

C.以链接方式存储      D.以链接方式存储,且数据元素有序

5．适用于折半查找的表的存储方式及元素排列要求为( D  )

    A．链接方式存储，元素无序     B．链接方式存储，元素有序

C．顺序方式存储，元素无序     D．顺序方式存储，元素有序

6. 用二分（对半）查找表的元素的速度比用顺序法( D  )

A. 必然快      B. 必然慢      C. 相等      D. 不能确定

7．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C   )                      

A．必定快     B.不一定     C. 在大部分情况下要快    D. 取决于表递增还是递减

8. 具有12个关键字的有序表，折半查找的平均查找长度（ A  ）

  A. 3.1            B. 4            C. 2.5            D. 5

9. 折半查找的时间复杂性为（ D  ）

A. O（n2）     B. O（n）     C. O（nlogn）     D.  O（logn）

10．当采用分快查找时，数据的组织方式为  (   B ) 

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

11．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A   )查找法。

A. 分快查找       B. 顺序查找       C. 折半查找       D. 基于属性

12. 既希望较快的查找又便于线性表动态变化的查找方法是 (  C )  

A．顺序查找   B. 折半查找   C. 索引顺序查找    D. 哈希法查找

13．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(  C  ) 

A．（100，80， 90， 60， 120，110，130）  B.（100，120，110，130，80， 60， 90）

C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)

1．某内排序方法的稳定性是指( D   )。 

A．该排序算法不允许有相同的关键字记录    B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法     D．以上都不对 

2．下面给出的四种排序法中( D   )排序法是不稳定性排序法。   

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

3．下列排序算法中，其中（ D   ）是稳定的。 【福州大学 1998 一、3 (2分)】

A. 堆排序，冒泡排序              B. 快速排序，堆排序   

  C. 直接选择排序，归并排序        D. 归并排序，冒泡排序

4．稳定的排序方法是（ B   ）   

A．直接插入排序和快速排序       B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序   D．树形选择排序和shell排序

5．下列排序方法中，哪一个是稳定的排序方法？（ B 　）  

A．直接选择排序      B．二分法插入排序      C．希尔排序        D．快速排序

6．若要求尽可能快地对序列进行稳定的排序，则应选    B

（A．快速排序  B．归并排序  C．冒泡排序）。

7．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（  A  ）排序为宜。

A．直接插入  B．直接选择  C．堆  D．快速  E．基数   

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

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

9．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(  A  )

A．选择排序法      B. 插入排序法       C. 快速排序法        D. 堆积排序法

10．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( D   )。

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

11．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。

A． 直接插入排序   B.  气泡排序     C.  快速排序     D.  直接选择排序

12．比较次数与排序的初始状态无关的排序方法是( D    )。

A．直接插入排序       B．起泡排序      C．快速排序       D．简单选择排序

13．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(  C  )的两趟排序后的结果。

A．选择排序        B.冒泡排序         C.插入排序         D.堆排序

14．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(  A  )的两趟排序后的结果。

A. 快速排序         B. 冒泡排序          C. 选择排序         D. 插入排序

15．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为

A. 84 47 25 15 21  B. 15 47 25 84 21   C. 15 21 25 84 47  D. 15 21 25 47 84 

则采用的排序是 ( A    )。   

A. 选择            B. 冒泡           C. 快速            D. 插入

16．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（  C  ）排序。

A. 选择           B. 快速           C. 希尔            D. 冒泡

二、填空题

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用__顺序 _____存储结构。

2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2  ______。【北方交通大学 2001 二、9】

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______；py->next=px->next; px->next=py ______;

4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ n-i+1_______个元素。

5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_ O(1)，  _______,在给定值为x的结点后插入一个新结点的时间复杂度为__ O(n)______

7． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;

_______、_______、________。

8. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：

s^ .next:=p； s^ .prior:= _ p^.prior     

_______；p^ .prior:=s；__ s^.prior^.next______:=s；

9．链接存储的特点是利用__指针   ______来表示数据元素之间的逻辑关系。

10.顺序存储结构是通过__物理上相邻   _____表示元素之间的关系的;链式存储结构是通过__指针_______表示元素之间的关系的。

11. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 __4__个，单链表为____2___个。

12. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素。_______。13. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ u=p->next; 

p->next=u->next; free(u); _______

14. 带头结点的双循环链表L中只有一个元素结点的条件是：__ L->next->next==L  ______

15. 在单链表L中，指针p所指结点有后继结点的条件是：_ p->next!=null_   

16.带头结点的双循环链表L为空表的条件是：____ L->next==L && L->prior==L ____。

17. 在单链表p结点之后插入s结点的操作是：_ s->next=p->next;p->next=s;______。

1．栈是_操作受限（或限定仅在表尾进行插入和删除操作） ______的线性表，其运算遵循__后进先出 _____的原则。

2．___栈____是限定仅在表尾进行插入或删除操作的线性表。

3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3 1 2 ______。

5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为__0 ，栈2空时 ，top[2]为___ n+1  

____，栈满时为__ top[1]+1=top[2]_____。

6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M：= M= _(M+1)% N；_______。

7．___队列_____又称作先进先出表。

8. 队列的特点是__先进先出 _____。

9．队列是插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是__先进先出 _____。

1. 数组的存储结构采用___顺序存储结构 ____存储方式。

2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）9572_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）1228_。 

3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）9174_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）8788  _。

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：__1100_____。

5. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为__232_____。 

6. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__ 1340 _____。

7. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：___1196____。

8. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_1_行，第_3_列的元素。

1．二叉树由_(1)根结点(2)左子树(3)右子树(1)__，__(2)_，_(3)__三个基本单元组成。

2．在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null _____。

3．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的__平衡因子__。

4．具有256个结点的完全二叉树的深度为__9 ____。

5．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。

6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是__ n ____。

7．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ N2+1____

8．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为__ N/2  ____。

9．高度为K的完全二叉树至少有__2k-2____个叶子结点。

10．高度为8的完全二叉树至少有______个叶子结点。

11．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_ 99 _____。

12．一个有2001个结点的完全二叉树的高度为__11 ____。

13．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。

14．具有N个结点的二叉树，采用二叉链表存储，共有__ N+1____个空链域。

15．二叉树的先序序列和中序序列相同的条件是_任何结点至多只有右子女的二叉树。

_____。

16．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是__ DGEBFCA __。

17．一个无序序列可以通过构造一棵___二叉排序树___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

18．利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。

19．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的___前序 ___序列中的最后一个结点。

20．哈夫曼树是_带权路径长度最小的二叉树，又称最优二叉树 _____。

21．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69____。

22．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_6 __，带权路径长度WPL为_261 __。

23. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__5, ________，带权路径长度WPL的值为___96_______。

1.判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图_____。

2．有向图G的强连通分量是指__有向图的极大强连通子图____。

3．一个连通图的__生成树____是一个极小连通子图。

4．具有10个顶点的无向图，边的总数最多为__45 ____。

5．若用n表示图中顶点数目，则有__ n(n-1)/2 _____条边的无向图成为完全图。

6．G是一个非连通无向图，共有2边，则该图至少有__9 ____个顶点。

7. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ n _____条弧。

8．在有n个顶点的有向图中，每个顶点的度最大可达__2(n-1) ____。

9．设G为具有N个顶点的无向连通图，则G中至少有_ N-1_____条边。

10．n个顶点的连通无向图，其边的条数至少为__ n-1____。

11．如果含n个顶点的图形形成一个环，则它有__ n ____棵生成树。

12．N个顶点的连通图的生成树含有__ N-1 ____条边。

13．构造n个结点的强连通图，至少有__ n ____条弧。    

14．有N个顶点的有向图，至少需要量__ N ____条弧

才能保证是连通的。

15．右图中的强连通分量的个数为（ 3   ）个。

16．N个顶点的连通图用邻接矩阵表示时,该矩阵

至少有___ 2（N-1）____个非零元素。

17．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度  ____；对于有向图来说等于该顶点的_出度_____。

18. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第I列非零元素个数 _____。

19．构造连通网最小生成树的两个典型算法是__普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法____。

20．求图的最小生成树有两种算法，__克鲁斯卡尔____算法适合于求稀疏图的最小生成树。

21. Prim（普里姆）算法适用于求__边稠密  ___的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_边稀疏______的网的最小生成树。

22. 有向图G可拓扑排序的判别条件是__不存在环____。

23．求最短路径的Dijkstra算法的时间复杂度为__ O(n2）____。

24. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为__ 75  ____。

25．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为__.O(n+e）____。

26．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为__关键路径 ____。

1．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__6,9,11,12 ________。

2. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5  ________

3. 在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__1,3,6,8,11,13,16,19________

4. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需___2,

_______次查找成功，47时_____4,____成功，查100时，需___3_______次才能确定不成功。

7. 对于长度为255的表，采用分块查找，每块的最佳长度为___16_______。

8. 在n个记录的有序顺序表中进行折半查找，最大比较次数是___．㏒2n」+1_______。

9．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__ k(k+1)/2  ________次探测。

10. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为___(n+1)/2 _______。 

11. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__(n+1)/n*log2(n+1)-1 ________。

12. 平衡因子的定义是__结点的左子树的高度减去结点的右子树的高度________

13. ___．直接定址法    _______法构造的哈希函数肯定不会发生冲突。

14. 在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为___ O(N)_____ 。

15. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做___ n(n+1)/2 ___次插入和探测操作。

16. 高度为8的平衡二叉树的结点数至少有___54_______个。

17. 高度为5（除叶子层之外）的三阶B-树至少有___31 W______个滓点。

18. 假定查找有序表A[1..12]中每个元素的概犇相等，则进行二分查找时瘄平均查找长度为___37/12 _______

19. 可以唯一的标识一个记录的关键字称为___丛关键字 ___[___。

20. 已知二叉排序树的左右子树均不为空，则____26 _____上所有结点的值均小于它的根结点倸，__  __________上所有结点的值均大于它的根结点的值。

2. 动态查找表和静态查找表的重要区别在于前者包含有____插入  ______和W___删除______运算，而后者不包含这两种运算。

2. 属于不稳定排序的有_希尔排序、简单选择排序、快速Β序、堆排序穉________]。

3．分别采用堆排庍，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡, _^__算法，最费时间的是__快速____算法。

4. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_(1)简单选择排序     

____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_(2)癴接插入排序（最小的儃素在最后时） ____。

6． 对n个记录的表r[1..n]进行简单选择排序，所錀进行的关键字间的比较次数为_ n(n-1)/2 ______。

7．从平均时间性能耈言，__快速 ________排序最佳。

8．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_(4,1,3,2,6,5,7)____。

9． 快速排序在_____的情况下最易发挥其长处。

10．在数据表有序时，快速排序算法的时间复杂度是_.O(n2) ___。

11．堆排序的算法时间复杂度为：__ O(nlog2n)  ___。

12．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆___ ④   _______。

①16，72，31，23，94，53      ②94，53，31，72，16，23    

③16，53，23，94，13，72       ④16，31，23，94，53，72     

 ⑤94，31，53，23，16，72

1. 对下面过程写出调用P(3)的运行结果。

PROCEDURE p（w：integer）;

   BEGIN

IF w>0 THEN

 BEGIN

                  p(w-1);

                  writeln(w);{输出W}

                  p(w-1）

END；

   END；

解：运行结果为：1  2  1  3  1  2  1（注：运行结果是每行一个数，为节省篇幅，放到一行。）

2.此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6> 

4．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小生成树的过程。

第29图

解：V（G）={1，2，3，4，5，6，7}    

E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）}

1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

解： 

以关键字27为例：H（27）=27%7=6（冲突）   H1=（6+1）%10=7（冲突） 

H2=（6+22）%10=0（冲突）   H3=（6+33）%10=5   所以比较了4次。

2. 设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。

解：

1．写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。

PROC   bbsort(VAR  r: sequence;  n: integer);

{r是一个数组}

  d:=1;  pos[-1]:=1; pos[1]:=n;  i:=1;  exchanged:= true;

  WHILE  exchanged  DO

    [ exchanged:= false;

WHILE i<>pos[d] DO

[IF (r[i]-r[i+d])*d>0 THEN [r[i]与r[i+d]交换; exchanged:=true;];

         i:=i+d;

        ]

    pos[d]:=pos[d]-d; i:=pos[d]; d:=-d;

]

 ENDP;  

 答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。               

 一趟：12,23,35,16,25,36,19,21,16,47

     二趟：12,16,23,35,16,25,36,19,21,47    

     三趟：12,16,23,16,25,35,19,21,36,47

       四趟：12,16,16,23,19,25,35,21,36,47   

     五趟：12,16,16,19,23,25,21,35,36,47

       六趟：12,16,16,19,21,23,25,35,36,47    

    七趟：12,16,16,19,21,23,25,35,36,47

2． 设待排序的关键码分别为28，13，72，85，39，41，6，20。按二分法插入排序算法已使前七个记录有序，中间结果如下:  

       6     13    28    39    41   72   85     20

             i=1                m=4             r=7

试在此基础上，沿用上述表达方式，给出继续采用二分法插入第八个记录的比较过程。

(1)  使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？

(2)  在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？

解：       6,  13,  28,  39,  41,  72,  85,  20

i=1↑          m=4↑          r=7↑

20<39  i=1↑m=2↑r=3↑

20>13 i=3 r=3 m=3

20<28 r=2 i=3

将r+1(即第3个)后的元素向后移动，并将20放入r+1处，结果为6,13,20,28,39,41,72,85。

（1）使用二分法插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不论待排序序列是否有序，已形成的部分子序列是有序的。二分法插入首先查找插入位置，插入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。

（2）一些特殊情况下，二分法插入排序要比直接插入排序要执行更多的比较。例如，在待排序序列已有序的情况下就是如此。

3．算法模拟

设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程求按递减顺序排序。

(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何？ 

解：. (1)直接插入排序

第一趟    (3)[8,3],2,5,9,1,6     第二趟    (2)[8,3,2],5,9,1,6   第三趟    (5)[8,5,3,2],9,1,6

第四趟    (9)[9,8,5,3,2],1,6     第五趟    (1)[9,8,5,3,2,1],6   第六趟    (6)[9,8,6,5,3,2,1]

(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）

第一趟    (9)[9],3,2,5,8,1,6     第二趟    (8)[9,8],2,5,3,1,6   第三趟    (6)[9,8,6],5,3,1,2

第四趟    (5)[9,8,6,5],3,1,2     第五趟    (3)[9,8,6,5,3],1,2   第六趟    (2)[9,8,6,5,3,2],1

 (3)直接插入排序是稳定排序，直接选择排序是不稳定排序。

4．在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？

解：这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例如 5,4,1,2,3在第一趟冒泡排序后得到4,1,2,3,5。其中4 向前移动，与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。

四、算法题

1. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域nexT），请给出这种队列的入队操作的实现过程。

解：void EnPueue (LinkedList rear, ElemType x)

// rear是带头结点的循环链队列犄尾指针，朤算法将元素x插入到队尾。

{ s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间

  s->data=x;  s->next=rear->next;         //将s结点链入队尾

  rear->next=s;  rear=s;                  //rear指向新队尾

}

2、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的出队操作的实现过程。

解：void DeQueue (LinkedList  rear)

     // rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。

     { if (rear->next==rear)  { printf(“队空\\n”); exit(0);}

       s=rear->next->next;             //s指向队头元素，

       rear->next->next=s->next;       //队头元素出队。

       printf (“出队元素是”，s->data);

       if (s==rear) rear=rear->next;   //空队列

      free(s);

     }

3．请编写直接插入排序算法。

    #define maxsize  100

typedef struct 

            { Elemtype data[maxsize];

              int last;

              }Sqlist;

解：

StraightInsertSort (SQLIST *v)

;n:integer);

   VAR i,j:integer;        

    BEGIN

      FOR i:=2 TO n DO               {假定第一个记录有序} 

BEGIN

v.data[0]:=v.data[i]; j:=i-1;        {将待排序记录放进监视哨} 

WHILE v.data[0]             BEGIN v.data[j+1]:=v.data[j]; j:=j-1; END;  

          v.data[j+1]*=v.data[0]           {将待排序记录放倰合适位置}

END {FOR}

END；

4．二叉树䫥下列二叉链表为存储结构，其头愇针为*Bitred,

编写将二叉树中每个结点的左右孩子交换的算法。

struct bitreptr

   {Elemtype  $ata;

    struct bitreptr *lchild,*Rchild;

    };

SWapBitree(BITREPTR *bt)

{ if(bt!=NULL){t=b4->lchild; bt->lchild= bt->rchild ;

bt->rchild=t;}

preptr(bt->lchild);

preptr(bt->rchild);}

   };