算法与数据结构复习重点全

一、单项选择题（50个）

1. 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，而（ B ）是数据不分割的最小单位。

A． 数据元素 B．数据项 C．数据对象 D．数据结构

2.以下数据结构中，（ A）是非线性数据结构

A.树 B.字符串 C.队 D.栈

3．在定义ADT时，除数据对象和数据关系外，还需说明（ c ）。

A． 数据元素 B．算法 C．基本 D．数据项

4．算法分析的两个方面是（ C ）。

A. 正确性和简明性 B. 可读性和文档性

C. 空间复杂性和时间复杂性 D. 数据复杂性和程序复杂性

5．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）。

A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等

6．以下说法正确的是（D）。

A．数据元素是数据的最小单位

B．数据项是数据的基本单位

C．数据结构是带有结构的各个数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

7. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A ）。A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B. 在第i个结点后插入一个新结点（1≤i≤n）

C. 删除第i个结点（1≤i≤n）

D. 将n个结点从小到大排序

8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。

B

A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;

9．线性表L=(a1,a2, ……an)，下列陈述正确的是 （D）。

A．每个元素都有一个直接前驱和一个直接后续

B．线性表中至少有一个元素

C．表中诸元素的排列必须是由小到大或由大到小

D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继

10．若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，则采用（D ）存储方式节省时间。

单链表只有一个指针域，是指向直接后继的。没有指向直接前驱。

循环链表也是只指向直接后继。

只有双向链表有两个指针域，分别指向直接前驱和后继。要存取值得修改两个指针

顺序表是在计算机内存中以数组的形式保存的线性表。它是数组，不用考虑修改指针，只用修改下标

A．单链表 B．双链表 C．单循环链表 D．顺序表

11． 在一个不设头结点的单链表L中，若要向表头处插入一个由指针p指向的结点，则执行（ D ）你要明白，p是指针，L也是指针。如题意，不需要考虑表头的情况。开始时，链表的first节点是L，而我们需要将p插入到L之前。所以我们需要将p链接到L所指的内存上，p->link = L。然后，因为我们要保持链表L不变，也就说L指针是在表首的，所以说要把 这时链表的（表首指针）P的值赋给L指针。

A. L = p;p->next = L; B. p->next = L->next; L->next = p;

C. p->next =L;p = L; D. p->next =L; L = p;

12．双向链表中插入一个结点需要修改( D )个指针。

4，2

在双向链表的结点A和B之间插入结点P需要修改：

P的前驱，P的后继，A的后继，B的前驱

在单向链表的结点A和B之间插入结点P需要修改：

P的后继，A的后继

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

13.在长度为n的顺序存储的线性表中，删除第i个元素(0 <= i <= n-1)时，需要从前向后依次前移（ A ）个元素。

删除第i个元素时,后面的元素ai+1~an都要向上移动一个位置,共移动了n-i个元素

A．n-i B. n-i+1 C. n-i-1 D. i

14．对于一个头指针为L的带头结点的单链表，判定该表为空表的条件是（B ）。

A．L==NULL B．L→next==NULL C．L→next==L D．L!=NULL

15. 若编号为1，2，3，4，5，6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到（ D ）

A．143562 B．456321 C．145326 D．426531

16.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ C ）。

A．iB．n=iC．n-i+1D．不确定

17.判定一个队列QU（最多元素为m0）为满队列的条件是（ A ）。

队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1，所以不必再减1了，应当选A。当然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0

A．QU->rear － QU->front = = m0

B．QU->rear － QU->front －1= = m0

C．QU->front = = QU->rear

D．QU->front = = QU->rear+1

18. 假设一个循环顺序队列的队首和队尾指针分别为front和rear，存储空间大小为n，则判断队空的条件是（ B ）

A．( front + 1 ) % n = = rear B．front = = rear

C．( rear + 1 ) % n = = front D．front = = 0

19．栈和队列都是（ c ）

A．顺序存储的线性结构 B. 链式存储的非线性结构

C. 限制存取点的线性结构 D. 限制存取点的非线性结构

20．设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g,则栈的容量至少是（ 3 ）

首先明确几个概念：栈是先进后出，队列是先进先出；题目中指定了进栈顺序，但没说要连续进栈。(下面箭头图中右代表栈底，左代表栈顶，队列同样)

假如栈的容量是1，则第一个出栈的肯定是a，不符合；

假如栈的容量是2，则a、b进去，b出栈，c进栈，只能c先出栈，d不可能出队顺序在c前

假如栈的容量是3，分析过程如下：

①S：b→a，b出栈，Q：b，S：a

②S：d→c→a，d、c依次出栈，Q：c→d→b，S：a

③S：f→e→a，f、e、a依次出栈，Q：a→e→f→c→d→b，S：null

④S：g，g出栈，Q：g→a→e→f→c→d→b，S：null

Q中元素依次出队，即b→d→c→f→e→a→g

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

21． 在目标串T[0…n-1]=‘acaabab’中，对模式串p[0…m-1]=‘ab’进行子串

定位操作的结果（ A ）

A.3 B.4 C.5 D.6

22．设有两个串 p 和 q ，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ c ）。

A．求子串 B．联接 C．匹配 D．求串长

23．设有串t='I am a good student '，那么SubString(t,6,6)=（ D ）。

A. student B. a good s C. good D. a good

24. 如下陈述中正确的是（ A ）

A. 串是一种特殊的线性表 B. 串的长度必须大于零

C. 串中元素只能是字母 D. 空串就是空白串

25. 二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为（ c ）

A.470 B.471 C.472 D.473

26. 设有一8×8对称矩阵A[5][5]，采用按行压缩存储的方式存放在一维数组B[ ]中，则数组B[ ]的容量至少需要( B )个元素空间。

A.25 B.26 C.16 D.15

27. 已知广义表的表头为A，表尾为(B,C)，则此广义表为（ b ）

A.（A,(B,C)） B.（A,B,C） C.(A,B,C) D.(( A,B,C))

28．已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

GetTail(GetHead(GetTail (C))) =( D )。

A.(a) B. A C. a D. (A)

29.下列关于二叉树的说法中正确的是( C )

A．二叉树是度为2的树。 B．有n个结点的二叉树高度为log2n

C.有10个叶子结点的二叉树中有9个度为2的结点。

D. 二叉树中至少有一个度为2的结点

30．设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ a ）。

根据二叉树与森林的对应关系，将森林F转换成对应二叉树B的规则如下：1、若森林F为空，则二叉树B为空。2、若森林F非空，则F中的第一棵树的根为二叉树B的根；第一棵树的左子树所构成的森林按规则转换成一个二叉树成为B的左子树，森林F的其他树所构成的森林按本规则转换成一个二叉树成为B的右子树。依此规则可知：二叉树B结点的个数减去其右子树的结点的个数就是森林F的第1棵树的结点的个数。

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

31．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为

2的结点有( A)个。

33个，

二叉树性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

由n0=n2+1, n0+n2=67,得

n2 = 33

A． 33 B．34 C． 32 D． 30

32．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于(B )

A．1.0 B．2.9 C．3.4 D．5.5

33．给定权值集合{ 2, 3, 5, 6, 8 }，则构造的Huffman树的带权路径长度为（ D ）。

A． 48 B．55 C．54 D． 53

34．5个字符有如下4种编码方案，是前缀编码的是C ）。

A． 01,0000,0001,001,1 B．011,000,001,010,1

C． 000,001,010,011,100 D．0,100,110,1110,1100

35. 利用二叉链表存储树，则根结点的右指针是（ C ）。【青岛大学 2001 五、5 （2

分）】

A．指向最左孩子 B．指向最右孩子 C．空 D．非空

36.一个有n个顶点和n条边的无向图一定是（ D ）。

A. 连通的 B. 不连通的 C. 无环的 D. 有环的

37．已知有向图G = ( V, E )，其中V = {V1, V2, V3, V4, V5, V6, V7 }，E = { ,

, , , , , , , }，G的拓扑序列是（ A ）。

A．V1V3V4V6V2V5V7 B．V1V3V2V6V4V5V7C．V1V3V4V5V2V6V7

D．V1V2V5V3V4V6V7

38．如下图所示由7个结点组成的无向图，对它进行深度优先遍历，不可能得到的顶点序列是（ B ）。

A. 1427653 B. 1245367 C. 1342765 D. 1534267

1354276 39. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

无向的邻接矩阵一定是对称阵。当vi与vj中间有一条边相连接时，则a(ij)=1,否则为0.e条边对应了n个顶点的度的和为2e.所以零元素的个数为n^2-2e

A．e B．2e C．n2－e D．n2－2e

40. 在含n个顶点和e条边的连通图中,其生成树顶点数和边数分别为( C )

A．n,e B．n,e-1 C．n,n-1 D．n-1,e-1

41.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。

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

42．折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素（ D ）进行比较。

A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37

43．适合二分查找的表的存储方式和元素排列要求是（ C ）

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

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

44．适于对动态查找表进行高效率查找的组织结构是（ C ）

A．有序表 B．分块有序表 C．二叉排序树 D．线性链表

45．已知含8个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( A )

A．21/8 B．11/4 C．25/8 D．4.5

46. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( c ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR

47. 将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。

A. 一定会 B. 一定不会 C. 仍可能会

48．对一组数据(12，2，16，58，5，10)进行排序，若前三趟排序结果如下：

第一趟：2，12，16，5，10，58

第二趟：2，12，5，10，16，58

第三趟：2，5，10，12，16，58

则采用的排序方法可能是( A)

A．冒泡排序法 B．希尔排序法 C．归并排序法 D．基数排序法

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

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

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

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

二、填空（35个）

1. 《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和_数据的运算___。

1.线性结构中元素之间存在一对一关系，树型结构中元素之间存在 一对多 关系，图型结构中元素之间存在 多对多 关系。

2. 在长度为n的顺序存储的线性表中，删除第i个元素(0 <= i <= n-1)时，需要从前向后依次前移 n-i 个元素。

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

4.对于双向链表,在两个结点之间插入一个新结点需修改的指针共 4 个。

5.带头结点的双循环链表L中只有一个元素结点的条件是：L→next→next==L &&

L→next != L

。

6. 设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为 (tail+1)modm==front 。

7．带头结点的双循环链表L为空表的条件是_ L->next==L ___。

8. 已知循环队列的存储空间为数组data[31]，且头指针和尾指针分别为18和13，则该队列的当前长度 __26_ ____。

9 经过下列栈的运算后栈顶的值是 s 。InitStack(s);Push(s,a), Push(s,b);Pop(s);

10. 广义表L=(a, (b,c,d) ,e,((i,j),k))的长度是 5 。

11.链接存储的特点是利用 指针 _来表示数据元素之间的逻辑关系。

12. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第（i1<=i<=n）个元素是_n-i+1__ ____。

13．设S=“A;/document/Mary.doc”，则strlength(s)= 20

14. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是 (x,y,z) 。

15.设有一个8阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a[1][1]

为第一个元素，其存储地址为1，每个元素占1个地址空间，则a[3][7]的

地址为__ 10___。

16. 一棵有30个结点的完全二叉树中有 16 个度为1的结点 。

17. 一棵高度为10的二叉树中最少含有 512 个结点，最多含有 1023 个结点。

18. 一颗深度为6的满二叉树共有 31 个非终端结点。

满二叉树有（2的六次方）-1个节点啦 叶子的个数就是2的（6-1）次方个

俩者相减 即分支节点个数了

19. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 99 。

20.完全二叉树中，结点个数为n，则编号最大的分支结点的编号为 2的平方-1 。

21. 用二叉链表存储包含n个结点的二叉树，结点的2n个指针域中有 n+1 个为空指针。

首先

二叉树的节点都有2个指针。每个节点有0个、1个或2个空指针。对应的有2个、1个、0个非空指针。非空指针的总数就是二叉树的边的个数。

设一个二叉树x个节点含有0个空指针，y个节点有1个空指针，z个节点有2个空指针 有如下等式

1、 x+y+z=N 节点总数为N，题目叙述

2、 y+2*z=N+1空指针个数为N+1，题目叙述

3、 2*x+y= N-1 二叉树的边数。树的边数=树的节点数-1 解以上方程组就可得出树的几种类型的节点数了。你就可以构造这个二叉树了。如果方程组有解

一般可以构造的二叉树是很多的。

22.树的双亲表示法便于实现涉及到____双亲__的操作，孩子表示法便于实现涉及到_孩子_____的操作。(双亲/孩子)

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

24. 一个连通无向图有10个顶点16条边，则其生成树将要去掉 7 条边。

25. 在用于表示有向图的邻接矩阵中， 对第i行的元素进行累加， 可得到第i 个顶点的 出 _ 度， 而对第j列的元素进行累加，可得到第j个顶点的 入___度。

26.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n _次；当使用监视哨时，若查找失败，则比较关键字的次数为 n +1 27. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 。

28.若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用______中序_____遍历法。

29. 在哈希函数H（key）=key%p中，p值最好取_质数__ _。

30.希尔排序的组内排序采用的_ 插入 排序。

31．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较______和记录的 移动 。

32.每次直接或通过“枢轴”元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_____快速_______排序。

33. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是_ 4 ___。

34. 从平均时间性能而言， 快速 排序最佳。

35.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，___冒泡_____最省时间，___堆______最费时间。

三、判断题（35个）

（ × ）1. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上亦相邻。

（ × ）2．在顺序存储结构中，有时也存储数据结构中元素之间的关系。。

（ √ ）3. 抽象数据类型与计算机内部表示和实现无关。

（ × ）4.算法和程序没有区别，所以在数据结构中二者是通用的。

（ × ）5. 取线性表的第i个元素的时间同i的大小有关。

（ × ）6．若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

（ √）7. 一个栈的输入序列是12345，则栈的输出序列不可能是45231。

（ × ）8. 在链队列中执行出队操作是在队头进行的，故不可能改变尾指针的值。

（ × ）9. 设串S的长度为n，则S的子串个数最多为n(n+1)/2。

s的长度为n，故它含有n个字符，它的子串应包括：1个字符的子串，2个字符的子串，…，n个字符的子串；这些子串的个数分别为

123nCn?Cn?Cn?Cn?(1?1)n?1?2n?1

（ √ ）10. 两个字符串相等的充要条件是长度相等且对应字符相等。

（ × ）11. 如果一个串中的所有字符均在另一串中出现，则说前者一定是后者的子串。

（ × ）12. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

（ × ）13. 一个稀疏矩阵Am*n采用三元组顺序表形式表示，若把三元组顺序表中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。

（ × ）14. 顺序存储方式只能用于存储线性结构。

（ √ ）15. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。

（ √ ）16. 已知一棵二叉树的先序序列和中序序列，一定能构造出该二叉树。

（ √ ）17. 哈夫曼树的结点个数不能是偶数。

（ × ）18. 已知一棵树的先序序列和后序序列，一定能构造出该树。

（ × ）19. Prim算法适用于求一个稀疏图的最小生成树。

（ √ ）20. 设有一个无向图G=（V，E）和G1=（V1，E1），如果G1是G的生成树，则G1是G的连通分量。

（ × ）21. 拓扑排序是一种内部排序方法。。

（ × ）22. 任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。

（ × ）23. 对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

（ × ）24. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（ × ）25. 带权的无向连通图的最小生成树是唯一的。

（ √ ）26. 一个网（带权图）都有唯一的最小生成树。

（√ ）27. 一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，

以尽可能减少冲突。

（ √ ）28. 顺序查找并不要求关键字一定有序。

（ × ）29. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。

（× ）30.平衡二叉树上所有结点的平衡因子，只可能是0或1。

（ √ ）31.一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。

（ × ）32. 堆是满二叉树。

（ √ ）33. 希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。

（ × ）34. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

（× ）35. 归并排序在任何情况下都比所有简单排序速度快。

四、综合题 （16个）

1. 对于下图所示的树转换成二叉树, 对转换后的二叉树分别求出它的先序序列、中序序列和后序序列

ABEFCGDH 2.已知二叉树的前序遍历序列为A, B, D, G，C, E, H, F, 中序遍历序列为B, G, D, A, E, H, C, F,试画出该二叉树，并写出其后序序列。

(1)还原该二叉树；

(2)写出该二叉树的后序遍历序列。

3. 在一份电文中共使用八种字符，即a, b, c, d, e, f, g, h，它们出现的频率依次为0.07, 0.19, 0.02,0.06, 0.32, 0.03, 0.21, 0.10，试画出对应的赫夫曼树，并为这8个字母设计哈夫曼编码。

4．已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤构造一棵哈夫曼树，并计算出它的带权路径长度WPL

5．设一个有向图为G=(V,E),其中V={v1,v2,v3,v4}，

E={,,,, },画出该有向图，画出相应的邻接矩阵。

6. 设无向图G有7个结点，顶点集为V(G)={1,2,3,4,5,6,7}，边集为E(G)={(1,2), (1,3), (2,3), (2,4),(2,5)，（4,6）, (5,7) }

（1）画出无向图G。

（2）画出G的邻接表

7. 设某带权无向图如下图，画出用Prim算法和Kruskal算法，从顶点A开始生成最小生成树的每一步结果。并求出最小生成树的带权路径长度。

4138E5F9D5AB27C6

8．下面的邻接表表示一个给定的无向图

（1）画出其邻接矩阵存储；

（2）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；

（3）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。

0123456 1 2 3 4 5 6 7 1 1 0 0 1 1 34 2 2 1 5 6 3 4 9.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

① 画出描述折半查找过程的判定树；

② 若查找元素54，需依次与哪些元素比较？

③ 若查找元素90，需依次与哪些元素比较？

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

（1） 折半查找判定树为

（2） 查找元素54，需依次与30，63，42，54比较 （3） 查找元素90，需依次与30，63，87，95比较 （4） ASL=1/12*（1+2*2+4*3+5*4）=3

10．给定一组整数26，9，34，62，30，23，请构造一棵二叉排序树。，并计算查找成功时的ASL。

11.试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，为每一次

的平衡处理指明旋转类型，并计算出在等概率情况下查找成功时的平均查找长度。

12.设散列表长13，散列函数为H(key) = key % 13，对关键字序列93, 63, 81, 78, 17, 8, 85, 7, 30, 22造表，用线性探测再散列法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。

13. 设散列表长13，散列函数为H(key) = key % 13，对关键字序列19，14，23，1，68，20，84，27，55，11，10，79造表，用拉链法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。

14．已知一组元素的关键码为 ( 77, 16, 48, 21, 19, 51, 62, 37, 60, 22, 99, 66 )， 利用Shell排序使之按关键字递增次序排序，设排序间隔分别是5、3、1，依次写出各趟排序后的结果。

15. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出冒泡排序各趟的排序结果。

五、算法设计（6个）

1. 简述以下算法的功能

Status A(LinkedList L) {

if (L&&L->next){

Q=L;L=L->next;P=L;

While(P-> next) P=P-> next;

P-> next= Q; Q-> next=NULL;

}

return OK ;

}

2.写出下列程序段的输出结果（栈的元素类型SElem Type为char）。

void main( ){

Stack S;

Char x,y;

InitStack(S);

X=’c’;y=’k’;

Push(S,x); Push(S,’a’); Push(S,y);

Pop(S,x); Push(S,’t’); Push(S,x);

Pop(S,x); Push(S,’s’);

while(!StackEmpty(S)){ Pop(S,y);printf(y); };

Printf(x);

}

输出为“stack”。

Pop()函数是出栈并且将出栈的元素存放在第二个行参里，所以在这里x的值不再是c了，而是出栈的元素。。

过程：

首先是三个压栈操作，之后栈里的元素为：cak，左边的为栈底，右边是栈顶。

然后一个出栈，此时栈里的元素为：ca，x中存的是k；

之后两次压栈，此时栈里的元素为：catk；

之后一个出栈，此时栈里的元素为：cat，x中存的是k；

最后一次压栈，此时栈里的元素为：cats，x中存的是k；

之后while(!StackEmpty(S)){ Pop(S,y);printf(y); };

结果是stac，

Printf(x);

结果是k，

3．简述以下算法的功能（栈和队列的元素类型均为int）。

void nizhi(Queue &Q){

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue (Q,d); Push(S,d);};

while(!StackEmpty(S)){

Pop(S,d); EnQueue (Q,d); }}

功能：队列中的数据元素逆置

4．已知二叉树的结点数据类型如下：

typedef struct node

{ElemType data; //数据元素

struct node *lchild; //指向左孩子

struct node *rchild; //指向右孩子

}BTNode,*BiTree;

阅读下列二叉树算法,回答问题。

void exchange(BiTree bt)

{ if(bt) { BiTree s;

s=bt->lchild; bt->lchild= bt->rchild; bt->rchild=s;

exchange(bt->lchild);

exchange(bt->rchild);

}

}

该算法执行二叉树运算的什么功能？

将二叉树中所有结点的左，右子树相互交换

5．将下面算法填完整。

int Search_Bin(SSTable ST, KeyType key){

//在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素//在表中的位置，否则返回0

low=1;high= ;

while(low<=high){

mid=____________;

if(EQ(key, ST.elem[mid].key)) return ____________;

else if(LT(key, ST.elem[mid].key)) high=____________;

else low=____________;

}

return ____________;

int Search_Bin(SSTable ST,KeyType key)

//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为

//该元素在表中的位置，否则为0.

{

low = 1; high = ST.length;

while(low <= high)

{

mid = (low + high)/2;

if(EQ(key, ST.elem[mid].key))

return mid;

else if (LT(key,ST.elem[mid].key))

high = mid -1;

else low = mid + 1;

}

return 0;

}//Search.Bin

6.试写出改进的冒泡排序算法描述，当某一趟排序没有数据交换时结束排序过程

public static void bubbleSort_2(int[] list) {

int temp = 0; // 用来交换的临时数

boolean bChange = false; // 交换标志

// 要遍历的次数

for (int i = 0; i < list.length - 1; i++) {

bChange = false;

// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上

for (int j = list.length - 1; j > i; j--) {

// 比较相邻的元素，如果前面的数大于后面的数，则交换

if (list[j - 1] > list[j]) {

temp = list[j - 1];

list[j - 1] = list[j];

list[j] = temp;

bChange = true;

}

}

// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序

if (false == bChange)

break;

}

}