数据结构各章作业题目

1、第一一、1.2.3.4.5.6.7.8.9.10.章作业 选择题被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的 这种关系称为 ( ) 。A. 规则B. 结构C. 集合D. 运算在 Data_Structure=(D,S) 中，D是()的有限集合。A. 数据元素B. 算法C. 数据操作D.数据对象计算机所处理的数据一般具有某种关系，这是指( ) 之间存在的某种关系。A. 数据与数据B.数据元素与数据元素C. 元素内数据项与数据项D.数据文件内记录与记录顺序存储表示中数据元素之间的逻辑关系是由表示的。A. 指针B. 逻辑顺序C.存储位置D. 问题上下文链接存储

2、表示中数据元素之间的逻辑关系是由表示的。A. 指针B.逻辑顺序C.存储位置D. 问题上下文A. 顺序表B. 散列表C.有序表D. 单链表1从逻辑上可将数据结构分为A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 内部结构和外部结构D.线性结构和非线性结构以下选项属于线性结构的是A. 广义表B.二叉树C.D. 稀疏数组以下选项属于非线性结构的是A. 广义表B. 队列C.优先队列D. 栈以下属于逻辑结构的是 ( )一个完整的算法应该具有 ( ) 等特性。A. 可执行性、可修改性和可维护性B.可行性、确定性和有穷性11.12.13.二、(1)int1.2.3.4.5.C. 确定性、有穷性和可靠

3、性D. 正确性、可读性和有效性若一个问题既可以用迭代方法也可以用递归方法求解，则( ) 的方法具有更高的时空效率。A. 迭代B.递归C. 先递归后迭代D.先迭代后递归一个递归算法必须包括 (A. 递归部分B.终止条件和递归部分C. 迭代部分D.终止条件和迭代部算法的时间复杂度与有关。A. 问题规模B.源程序长度C. 计算机硬件运行速度D.编译后执行程序的3壬曰.质量 指出下列各算法的功能并求出其时间复杂度。Prime( int n)元素int i=2,x=( int )sqrt(n);D. 数据字段数据项B.数据记录 C. 数 据顺序表是线性表的( ) 存储表示。A. 有序B. 连续C. 数组

4、D.顺序存取若长度为n 的非空线性表采用顺序存储结构，在表中的第个位置插入一个数据元素， i 的合法值应该是A. 1 iB. 1 i n 1C. 0 i nD. 0 i n若设一个顺序表的长度为n那么，在表中顺序查找一个值为查找成功的数据平均比较次数为 ( )x 的元素时，在等概率的情况下，A. nB. n/ 2C. (n 1)/2D.(n 1)/2在长度为 n 的顺序表的表尾插入一个新的元素的时间复杂度为数据结构反映了数据元素之间的结构关系。单链表是一种A. 顺序存储线性表 B. 非顺序存储非线性表 C. 顺序存储非线性表D.非顺序存储线性表6. 单链表又称为线性链表，在单链表上实施插入和删

5、除操作A. 不需移动结点，不需改变结点指针B. 不需移动结点，只需改变结点指针C. 只需移动结点，不需改变结点指针D. 既需移动结点，又需改变结点指针7. 已知 L 是带头结点的单链表，则删除首元素结点的语句是 ( )A. L=L-next; B. L-next=L-next-next; C. L=L-next-next; D. L-next=L;8. 已知单链表A长度为m单链表B长度为n若将B链接在A的末尾，在没有链尾指针的情况下， 算法的时间复杂度应为 ( ) 。A. O(1)B. O(m)C. O(n)D. O(m n)9. 给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是()

6、A. O(1)B. O(n)C. O(n2)D. O(nlog2 n)二、算法设计1. 设计一个算法，从顺序表L中(SqList L)删除具有给定值x(ElemType x)的所有元素。2. 设计一个算法，从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。3. 设计一个算法，在非递减有序的带头结点的单链表中删除值相同的多余结点。第三章作业、选择题1.用 S 表示进栈操作，用 X 表示出栈操作，相应的S和X的操作序列为()若元素的进栈顺序是 1234，为了得到 1342 的出栈顺序，2.3.4.5.6.7.8.A. SXSXSSXXB. SSSXXSXXC. SXSSXXSXD.

7、 SXSSXSXX假设一个栈的输入序列是 1，2，A. 1,2,3,4B. 4,1,2,3已知一个栈的进栈序列为A. j iB.已知一个栈的进栈序列为A. iB.已知一个栈的进栈序列为A. 一定是 2B.已知一个栈的进栈序列为A. 一定是 21,2,3,ni1,2,3,ni1,2,3,*曰定是3，4，,n ，,n，,n，p1, p2,p3,B. 可能是 2已知一个栈的进栈序列为p1,p2,p3,已知一个栈的进栈序列为p1,p2,p3,则不可能得到的输出序列是C. 4,3,2,1其输出序列的第一个元素是C. ji1D. 1,3,4,2其输出序列是p1, p2,p3,i，, pn则第 j 个出栈元

8、素是 ( ) 。D.不确定C. ni1其输出序列是p1, p2,p3,C. 可能是 1,pn,pn,pn，其输出序列是C. 不可能是，其输出序列是，其输出序列是, pn1,2,3,1,2,3,1,2,3,。若 p1n ，则pi 的值是D.不确定。若 p13，则p2 的值是D.可能是 2,n 。若 p3 1，则D.*曰 O定是 3p1的值是,n 。若 p33，则宀曰 d定是 1,n 。若 pn 1，则p1的值是p1的值是A. 一定是 2B. 可能是 2C. 不可能是1D.5A. n i 1B. n iC. iD. 不确定199. 设栈S和队列Q的初始状态均为空， 元素1,2,3,4,5,6,7,

9、依次进入S。如果每个元素出栈后立即进入队列Q,且7个元素的出队顺序为2,4,3,6,5,1,7 ，则栈S的容量至少是()A. 1B. 2C. 3D. 410. 对中缀表达式 3 2*(4 2*2 6*3) 5求值， 在求值过程中扫描到 6时，操作数栈和操作符栈的内 容分别是 ( )A. 3,2,4,2,2 和+,*,(,+,*B. 3,2,4,4和+,*,(,+C. 3,2,8 和+,*,( D.3,2,8,6 和+,*,(,-二、算法设计题1. 详见数据结构题集 (C 语言版 ) 第 25 页。2. 详见数据结构题集(C语言版)第25页。第四章作业11. 串是一种特殊的线性表，其特殊性体现在

10、 （ ）A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个 字符12. 设有两个串T和P,求P在T中首次出现的位置的运算叫做（）。A. 求子串B. 模式匹配C. 串替换D. 串连接13. 下面关于串的叙述中，哪一个是不正确的（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储14. 串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数15. 两个串相等的充分必要条件是（）A.串中所含的字符相同B.串中所含字符的个数相同

11、，且对应位置上的字符也相同C.串中所含的字符个数相同D.串中对应位置上的字符相同6. 已知 p=” abcaabbabcabaacbacb ”，求出 next 函数值。第五章作业、选择题19.20.21.A. 80B. 100C. 240一个二维数组 A1020 按行存放于一个连续的存储空间中， 组元素占 1 个存储字，则 A62 的地址为 ( )A. 226B. 322C. 341一个二维数组 A1020 按列存放于一个连续的存储空间中， 组元素占 1 个存储字，则 A62 的地址为 (A. 226B. 322C. 341D. 270A00A00的存储地址是 200，每个数D. 342的存储

12、地址是 200，每个数D. 342在二维数组 这种情况下，A910 中，每个数组元素占用 元素 A85 的起始地址为 ( )3 个存储单元，从首地址SA开始按行连续存放，在A. SA+141B. SA+144C. SA+222D. SA+25522.将一个么第 i的对称矩阵A的下三角部分按存放在一个一维数组B中,行的对角元素 Ai i在B中的存放位置是()nnA00存放在B0 中，那23.A. (i3)i/2B. (i 1)i/2C. (2n i 1)i/2D.(2n i1)i/2将一个么第 in n 的对称矩阵 A 的上三角部分按存放在一个一维数组 B 中，行的对角元素 Ai i 在B中的存

13、放位置是()A00存放在B0 中，那A. (i3)i/2B. (i 1)i/2C. (2n i 1)i/2D.(2n i1)i/2A. 顺序存取B.直接存取C. 散列存取D.索引存取17. 多维数组实际上是由( )实现的。A. 一维数组B.多项式C. 三元组表D.简单变量18. 在二维数组 A810中，每一个数组元素Aij 占用 3 个存储空间，所有数组元素相继存放于16. 数组通常具有的操作是 ( )一个连续的存储空间中，则存放该数组至少需要的存储空间是o( )24. 设A是一个n n的对称矩阵，将 A的对角线及对角线上方的元素以列优先(以列为主序)的方式存放在一维数组Bn(n 1)/2中，

14、则矩阵中任一元素 aj(0 i, j n,i j)在B中的存放位置是()A. j(j 1)/2 iB. j( j 1)/2 i 1C. i(i 1)/2 jD. i(i 1)/2 j 125. 设n阶三对角矩阵A的三条对角线上的元素被按行压缩存储到一维数组若某矩阵元素在B中存放的位置在k,那么该元素在原始矩阵中的行号B中，A00存放于 B0。A. (k 1)/3B. k/3C. (k 1)/3D. (k 1)/3、简答题26. 设有一个 3 维数组 A10 2015 ，按行优先存放于一个连续的存储空间中， 每个数组元素占 4个 存储字，首元素 A000的存储地址是1000，则A789存放于什么

15、地方。27. 设有一个二维数组 Am n ，假设 A00 存放位置在 644(10)， A22 存放在 676(10) ，每个元 素占 1 个存储单元，问 A3 3 (10) 存放在什么位置脚注 (10)表示用十进制表示。28. 对于一个n n矩阵A的任一元素aij，按行存储和按列存储时的地址之差是多少(假设两种存储的开始存储地址 LOC (0,0)以及元素所占存储单元数d相同)29. 设有n阶三对角矩阵 A，将其 3条对角线上的元素逐行存储到数组B0:3n 3中，使得Bk Aij，且 B0A00，求(1) 用 i ， j 表示 k 的下标变换公式。(2) 用 k 表示 i ， j 的下表变换

16、公式。30. 设有一个n n的对称矩阵 A,将其下三角部分按行压缩存放于一个一维数组B中，A00存放于B0，试问：(1) 一维数组B有多少个元素(2) A中的任意一个元素 Aij应存于一维数组 B 的什么下标位置31. 设有一个n n的对称矩阵 A,将其上三角部分按列压缩存放于一个一维数组B中，A00存放于B0，试问：(1) 一维数组B有多少个元素(2) A中的任意一个元素 Aij应存于一维数组 B 的什么下标位置第六章作业、选择题32. 一颗有 n 个结点的树的所有结点的度数之和为 ( )A. n-1 B. n C. n 133. 设一颗高度为h的满二叉树有n个结点，其中有 m个叶结点，则(

17、)A. n h m B. h m 2n C. m h 134. 一颗有 124 个叶结点的完全二叉树最多有 ( ) 个结点。A. 247B. 248C. 24935. 一颗有 129 个叶结点的完全二叉树最少有 ( ) 个结点。A. 254B. 255C. 25736. 设完全二叉树的第 6层有 24 个叶结点，则此树最多有 ( ) 个结点。A. 55B. 79C. 8137. 具有 1000 个结点的完全二叉树的次底层的叶结点个数为 ( ) 。A. 11B. 12C. 24D. 2nD. n 2h 1D. 250D. 258D. 127D. 3638. 用顺序存储的方法将n个结点的完全二叉树

18、中所有结点按层逐个顺序存放在一维数组Rn中，当编号为0的根结点存放于 R0时，若结点Ri有左孩子，则左孩子是()。A. R2i 1B. R2iC. R2i 1D. R2i 239. 用顺序存储的方法将n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组Rn中，当编号为0的根结点存放于 R0时，若结点Ri有右孩子，则右孩子是()。A. R2i 1B. R2iC. R2i 1D. R2i 240. 二叉树的叶结点在前序、中序和后序遍历过程中的相对顺序 ( ) 。A. 发生改变B. 不发生变化C. 无法确定D. 以上均不对n在m前的条件是()41. 设n，m为一颗二叉树上的两个结点，在该二叉树的

19、中序遍历序列中A. n 在 m 右方B. n是m的祖先C. n 在 m 左方D. n是m的子孙42. 设一颗二叉树的前序序列为abdec,中序序列为dbeac,则该二叉树的后序遍历顺序是()43.44.45.46.47.48.二、49.50.51.52.A. abdecB. debacC. debcaD. abedc设一颗二叉树的中序序列为badce，后序序列为bdeca，则该二叉树的前序遍历顺序是()A. adbecB. decabC. debacD. abcde对二叉树的结点从 1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的 左、右孩子中，其左孩子编号小于其右孩子编

20、号，则可采用 ( ) 遍历实现二叉树的结点编号。A. 先序B. 中序C. 后序D. 层次序如果T2是由有序树T转换成的二叉树，那么 顺序。T 中结点的先根遍历顺序对应T2中结点的()遍历A. 前序B. 中序C. 后序D. 层次序如果T2是由有序树T转换成的二叉树，那么 顺序。T 中结点的后根遍历顺序对应T2中结点的()遍历A. 前序B. 中序C. 后序D. 层次序用 n 个权值构造出来的 Huffman 树共有 ( ) 个结点。A. 2n 1 B. 2nC. 2n 1D. n 1由权值为 8,4,5,7 的 4 个叶结点构造一颗Huffman 树，该树的带权路径长度为A. 24B. 36C.

21、48D. 72简答题 设二叉树根结点所在层次为 1，树的深度 d 为距离根最远的叶结点所在的层次，试回答以下问题：(1) 试精确给出深度为 d 的完全二叉树的不同二叉树的棵数； (2) 试精确给出深度为 d 的满二叉 树的不同二叉树棵数。如果一棵树有ni个度为1的结点，有门2个度为2的结点，有nm个度为m的结点，试问有 多少个度为 0 的结点 已知一棵二叉树的前序遍历序列为 ABECDFGH冲序遍历序列为 EBCDAFHIGJ(I)画出这棵二叉 树；(2) 给出这棵二叉树后序遍历序列； (3) 画出这棵二叉树转换成对应的树 (或森林)。假定用于通信的电文仅有 8 个字母 A,B,C,D,E,F

22、,G,H 组成，各字母在电文中出现的频率分别为 5,25,3,6,10,11,36,4 。试为这 8 个字母设计不等长 Huffman 编码，并给出该电文的总码数。算法设计53. 设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为1 的结点个数。54. 设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为2 的结点个数。55. 设树T以孩子-兄弟链表作为其存储表示，编写一个算法统计树T的叶结点个数。56. 设树T以孩子-兄弟链表作为其存储表示，编写一个算法计算树T的高度。1.2.3.4.5.6.7.8.9.10.11.第七章作业选择题具有 n 个顶点且每一对不同顶点间

23、都有一条边的无向图被称为A. 完全无向图B. 无向连通图C. 无向强连通图D. 无向树图一个有 n 个顶点的无向图中边数最多有 ( ) 条。A. nB. n(n 1)C. n(n 1)/2D. 2n对于具有 n(n 1) 个顶点的强连通图，其有向边条数至少是 ( )A. n 1B. nC. n 1D. n 2设G是一个非连通无向图，有 15条边，则该图的顶点数至少有个。A. 5B. 6C. 7D. 8在一个具有 n 个顶点的有向图中，若所有顶点的岀度之和为s，则所有顶点的入度之和为 ( ) 。A. sC. s+1D. n一个有 n 个顶点和 n 条边的无向图一定是A. 重连通图B. 不连通图C

24、. 无环的D. 有环的无向图的邻接矩阵是一个 ( ) 。A. 对称矩阵B. 零矩阵C. 上三角矩阵D. 对角矩阵有 n 个顶点和 e 条边的无向图采用邻接矩阵存储，零元素的个数为A. eB. 2eC. n2D. n2 2e带权有向图G用邻接矩阵A存储，则顶点i的入度等于A 中( ) 。A.第i行非R的元素之和B. 第 i列非g的元素之和C.第i行非g且非0 的元素个数D. 第 i列非g且非0 的元素个数设图有 n 个顶点和e 条边，采用邻接矩阵时，遍历图的顶点所需时间为A. O(n)B. O(n2 )C. O(e)D. O(ne)设图有 n 个顶点和e 条边，采用邻接表时，遍历图的顶点所需时间

25、为A. O(n e)B. O(n2)C. 0(e)D.0( ne)12.图的深度优先搜索类似于树的 （）次序遍历。A.先根B.中根C.后根D.层13.图的广度优先搜索类似于树的 （）次序遍历。A.先根B.中根C.后根D.层14.采用邻接表存储的图的深度优先搜索算法类似于二叉树的()。A.中序遍历B.前序遍历C.后序遍历D.层次遍历15.采用邻接表存储的图的广度优先搜索算法类似于二叉树的()。A.中序遍历B.前序遍历C.后序遍历D.层次遍历16.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）A.强连通图B.连通图C.有回路D.一棵树17.如果一个连通网络G中各边

26、权值互不相同，权重最小的边一定包含在G的（）生成树中。A.最小B.任何C.广度优先D.深度优先18.任何一个连通图的最小生成树（）。A.只有一棵B.有一棵或多棵C.定有多棵D.可能不存在19. 一个有n个顶点和e条边的连通图的生成树有（）条边。A. nB. eC. n 1D.n 120.设一个n个顶点的带权连通图有、n log 2n条边，则应该选通（）算法来求这个图的最小生成树从而使计算时间较少。A. PrimB. KruskalC. DFSD. BFS21.求最短路径的Dijkstra 算法的时间复杂度为()。A. O( n)B. O(n e)C.O(n2)D.O( ne)22.求最短路径的

27、Floyd算法的时间复杂度为（）。A. O( n)B. O(ne)C.O(n2)D.0(n3)23. 设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为（）。A. 0(n)B. 0(n e)C. 0(n2)D. 0(ne)24. 设有向图具有n个顶点和e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度为()。2A. 0(nge)B. 0(n e)C. 0(n)D. 0(ne)二、应用题25. 针对图1所示的有向图，画出该图的邻接矩阵、邻接表和逆邻接表。26. 对图2所示的无向图，从顶点a开始进行深度优先遍历，给出2个可得到的顶点访问序列；从顶点a开

28、始进行广度优先遍历，给出2个可得到的顶点访问序列。27. 已知一个带权连通图如图3所示，分别使用 Prim算法和Kruskal算法求其最小生成树。28. 已知一个带权有向图如图4所示，用Dijkstra算法求从顶点a到其余各顶点的最短路径及路径长度。29. 如图所示的 A0E网，求(1) 完成此工程最少要多少天(设弧上的权值为天数)；(2) 每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai)；(3)哪些是关键活动;(4)是否存在某些活动，当其提高速度后能使整个工程缩短工期图5第九章作业、选择题30.顺序查找算法适用于 ( ) 。A. 线性表B. 查找树C. 查找网D. 连通图31.顺

29、序查找法适用于线性表的 ( ) 。A. 散列存储B. 压缩存储C. 索引存储D. 顺序或链接存储32.A. nB. n/2C. (n 1)/2D. (n 1)/233.如果有 5 个关键吗 a,b,c,d,e 放在顺序表中， 他们的查找概率分别为 长度达到最小的存放方式是 ( ) 。,.015, ，可使平均查找A. d,a,b,c,eB. e,d,c,b,aC. a,b,c,d,eD. a,c,e,d,b采用顺序查找方式查找长度为 n 的顺序表时，平均查找长度为 ( )34.35.A. n/4B. n/2C. (n 1)/2D. (n 1)/2对线性表进行折半查找时，要求线性表必须A. 以顺序

30、方式存储B. 以链接方式存储C. 以顺序方式存储，且结点按关键吗有序排列D. 以链接方式存储，且结点按关键吗有序排列对于长度为 n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功 的平均查找长度为 ( )36.37.A. O(n)B. O(log 2 n)C. O(n2)D. O(nlogn)对于长度为 18 的有序顺序表，若采用折半查找，则查找第15 个元素的查找次数为 ( ) 。A. 3B. 4C. 5D. 638.已知有序顺序表 (13,18,24,35,47,50,62,83,90,115,134)时，查找成功的数据比较次数为，若采用折半查找法查找值为 18

31、的元素39.A. 1B. 2C. 3D. 4使用散列法时确定元素存储地址的依据是采用折半查找法查找长度为 n 的有序顺序表时，平均查找长度为 ( )A. 元素的序号B. 元素个数C. 关键吗D. 非码属性设一个散列表中有n 个元素，用散列法进行查找的平均查找长度是( ) 。A. O(1)B. O(n)C. O(log2n)D. O(n2)40.41.42.43.44.45.46.47.48.49.二、50.使用散列函数将元素的关键吗映射为散列地址时，常会发生冲突。此时的冲突是指 ( ) 。A. 两个元素具有相同的序号B. 两个元素的关键码不同，而非关键码相同C. 不同关键码对应到相同的存储地址

32、D. 装载因子过大，数据元素过多计算出的地址分布最均匀的散列函数是 ( ) 。A. 数值分析法B. 除留余数法C. 平方取中法D. 折叠法将 10 个元素散列到大小为 100000 个元素的散列表中， ( ) 产生冲突。A. 一定会B. 一定不会C. 仍可能会D. 以上都不对采用线性探测法解决冲突时计算出的一系列“下一个空位” ( ) 。A. 必须大于等于原散列地址B. 必须小于等于原散列地址C. 可以大于或小于但不等于原散列地址D. 对地址在何处没有限制包含有 4 个结点的元素值互不相同的二叉查找树有 ( ) 棵。A. 4B. 6C. 10 D. 14查找利用逐个数据插入的方法建立序列 35

33、,45,25,55,50,10,15,30,40,20 对应的二叉查找树后， 元素 20 需要进行 ( ) 次元素之间的比较。A. 4B. 5C. 7 D. 10一颗高度为A. 2h 1 1高度为7的AVL树最少有()A. 12B. 21高度为7的AVL树最多有()A. 63B. 64应用题h的AVL树，若其每个非叶子结点的平衡因子都是B. 2h1C.2h 1 1个结点。C.33个结点。C.650，则该树共有 ( ) 个结点。D. 2h 1D. 54D. 127设有一个关键码的输入序列55,31,11,37,46,73,63 ，从空树开始构造 AVL树，画出每加入一个1所示的AVL树中)。图1

34、新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。如果有平衡化旋转，注明相关结点平衡51. 分别画出在图1所示的AVL树中插入15、36后树的变化。因子的变化(注意，15和36是各自独立插入到图52. 已知含12个关键字的有序表及其相应的权值如下表，试按次优查找树的构造算法，画出由这12个关键字构造所得的次优查找树，并计算它的PH值。关键字ABCDEFGHIJKL权值82349326711453. 对于23题有序表及其相应的权值，试按次优查找树的构造算法并加适当调整，画出由这12个关键字构造所得的次优查找树，并计算它的PH值。通过适当调整后得到的次优查找树是否更优5

35、4. 设哈希表HT15，哈希函数为 H(key) key% 13。用开放地址法解决冲突，对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。采用线性探测法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。55. 设哈希表HT15，哈希函数为 H (key) key% 13。用开放地址法解决冲突，对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。采用再哈希法寻找下一个空位，再哈希函数为RH (key) (7key)%10 1，寻找下一个空位置的公式为H (H i !RH(key)%15，H。

36、 H (key)。画出相应的哈希表，并计算等概率下查找成功的平均查找长度。63.25第十章作业、选择题56. 排序算法的稳定性是指 ( ) 。A. 经过排序后，能使值相同的数据保持原顺序中的相对位置不变B. 经过排序后，能使值相同的数据保持原顺序中的绝对位置不变C. 经过排序后，数据序列的存放数组的结构保持不变D. 经过排序后，数据序列的存放数组的结构随之变化57. 若要求在最坏情况下也能尽快地对序列进行稳定的排序，则应选 ( ) 。A. 起泡排序 B. 快速排序 C. 归并排序 D. 堆排序58.每次从未排序的序列中取出一个元素与已排序的序列中的元素依次进行比较，然后把它插入到已排序序列中的适当位置，此种排序方法叫做 ( )A. 起泡排序B. 直接插入排序C. 简单选择排序D. 二路归并排序59.60.A. 8B. 10C. 15D. 25直接插入排序在最好情况下的时间复杂度是 ( )A. O (log 2 n)B. O(n)C. O(n log2 n)D.O(n2)对 5 个不同数据元素做直接插入排序，其数