您好、欢迎来到现金彩票网!
当前位置:老k棋牌 > 栈向量 >

全部习题_百度文库

发布时间:2019-07-22 04:50 来源:未知 编辑:admin

  第一章绪论 求时间复杂度练习题 (1) i←1 ; j←0 while i+j=n do if ij then j←j+1 else i←i+1 endif endwhile (2) for i←1 to n do for j←1 to n do for k←1 to j do x←x+1 endfor endfor endfor (3) for i←1 to n do for j←1 to i do for k←1 to j do x←x+1 endfor endfor endfor (4)一个算法的执行时间为 1000n,另一个算法约为 2^n(2 的 n 次方)。这两个算法的时间复杂度分别是多少?哪个高?当问题的规模 n≤13 时, 选用哪个算法合适? (5)已知有实现同一功能的两个算法,其时间复杂度分别为 O(2^n)和 O(n^10),假设现实计算机可连续运行的时间约 100 天,又每秒可执行基本 操作为 10^5 次。试问在此条件下,这两个算法可解决问题的规模(即 n 的范围)各为多少?哪个算法更合适?试说明理由。 (6)给出费氏数列(fibonacci 数列)前 n 项的递归与非递归的算法,试分析它们的算法复杂度(注:费氏数列指 fibonacci 数列);试用 time 或 clock 函数实际测试 n=100 时,机器的实际运行时间,并分析结果。 第六章 6-1. 6-2. 6-3. 6-4. 线性表习题 一个向量的第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是 。 在一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动的元素个数是 。 在线性表的顺序存储结构中,逻辑上相邻的元素在物理位置上 。 对顺序存储的线性表,设其长度为 n,在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的 个元素,删除 一个元素时大约要移动表中的 个元素。 6-5. 线性表顺序存储的特点是 。 6-6. 若线性表中元素的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么若采用顺序存储结构是否合适? 为什么? 6-7. 根据线性表的链式存储结构中每个结点所含指针的个数,链表可分为 和 ;而根据指针的连接方式,链表又可分为 和 。 6-8. 试描述头指针、头结点及开始结点的区别,并说明头指针和头结点的作用。 6-9. 有哪些链表可由一个尾指针来唯一确定?(即从尾指针出发能访问到链表上任何一个结点) 6-10. 什么情况下用顺序表比链表好? 6-11. 不带头结点的单链表 head 为空的判定条件是 。 (1) head=NULL (2) head→next=NULL (3) head→next=head (4) head!=NULL 6-12. 在一个单链表中,若指针 p 所指结点不是最后结点,在 p 之后插入指针 s 所指结点,则执行 (1) s→next=p;p→next=s; (2) s→next=p→next;p→next=s; (3) s→next=p→next; p=s; (4) p→next=s;s→next=p; 6-13. 在循环双链表的指针 p 所指结之后插入指针 s 所指结点的操作是 (1) p→next=s;s→prior=p;p→next→prior=s;s→next=p→next; (2) p→next=s; p→next→prior=s;s→prior=p;s→next=p→next; (3) s→prior=p;s→next=p→next;p→next=s; p→next→prior=s; (4) s→prior=p;s→next=p→next;p→next→prior=s;p→next=s; 。 。 6-14. 从一个具有 n 个结点的单链表中查找其值等于 x 的结点时,在查找成功的情况下,需平均比较的结点个数是 (1) n (2)n/2 (3)(n-1)/2 (4)(n+1)/2 6-15. 给定有 n 个元素的向量,建立一个有序单链表的时间复杂度是 。 (1) O(1) (2)O(n) (3)O(n2) (4)O(nlog2n) 6-16. 线性表采用链表存储时,其地址 。 (1)必须是连续的 (2)部分地址必须是连续的 。 (3)一定是不连续的 (4)连续不连续都可以 6-17. 试用顺序存储结构设计一个算法,仅用一个辅助结点,实现将线性表中的结点循环右移 k 位的运算,并分析算法的时间复杂度。 6-18. 已知一顺序表递增有序,试设计一算法,将 x 插入到表中的适当位置,以保持顺序表的有序性。 6-19. 设有两个顺序表 A 和 B,元素的个数分别是 m 和 n,若表中的数据都是由小到大顺序排列的,且这(m+n)个数据中没有相同的。试设计算法 将 A 和 B 合并成一个线性表 C,并存储到另一个向量中。 6-20. 设有一个顺序表中,写出在其值为 x 的元素之后插入 m 个元素的算法(假设顺序表的长度足以容纳 m 个元素) 。 6-21. 设有一线,en),试设计一个算法,将线性表逆置,即使元素排列次序颠倒过来,成为逆线性表 E? ={en,en-1,…,e2,e1), 要求逆线性表占用原线性表空间,并且用顺序和单链表两种方法表示,写出不同的处理过程。 6-22. 已知带头结点的动态单链表 L 中的结点是按整数值递增排列的,试写一算法将值为 x 的结点插入表 L 中,使 L 仍然有序。 6-23. 试编写在带头结点的动态单链表上实现线性表操作 LENGTH(L)的算法,并将长度写入头结点的数据域中。 6-24. 已知一个带头结点的单链表,设计算法将该单链表复制一个拷贝。 6-25. 设指针 la 和 lb 分别指向两个无头结点单链表的首元结点,试设计从表 la 中删除自第 i 个元素起共 len 个元素后,将它们插入到表 lb 中第 i 个元素之前的算法。 6-26. 设计算法将一个带头结点的单链表 A 分解为两个链表 A、B,使得 A 表中含有原表中的序数为奇数的结点,而 B 表中含有序数为偶数的结 点,且保持结点间原有的相对顺序。 6-27. 假设有两个按元素值递增有序排列的线性表 A 和 B,均以单链表作存储结构,试编写算法将 A 表和 B 表归并成一个按元素值递减有序(即 非递增有序,允许值相同)排列的线性表 C,并要求利用原表(即 A 表和 B 表)的结点空间存放表 C。 6-28. 设线性表 A、B 和 C 递增有序,试在 A 表中删除既在 B 中出现又在 C 中出现的那些元素, 且 A、 B 和 C 分别以两种存储结构 (顺序和链式) 存储。 6-29. 假设在长度大于 1 的单循环链表中,既无头结点也无头指针。s 为指向链表中某个结点的指针,试编写算法删除结点*s 的直接前趋结点。 6-30. 设有一个双向链表,每个结点中除有 prior,data 和 next 三个域外,还有一个访问频度域 freq,在链表被启用之前,其值均初始化为零。每 当在链表中进行一次 LOCATE(L,x)运算时,令元素值为 x 的结点中 freq 域的值增 1,并使此链表中结点保持按访问频度递减的顺序排列,以便使 频繁访问的结点总是靠近表头,试编写符合上述要求的 LOCATE 运算的算法。 已知,由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符,数字字符和其它字符) ,试编写算法构造三个以循环链表表示的线 性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。 第八章 栈和队列 8-1. 一个栈的入栈序列是 a,b,c,d,e,则栈不可能的输出序列是 。 (1)edcba (2)decba (3)dceab (4)abcde 8-2. 若已知一个栈的入栈序列是 1,2,3,…,n,其输出序列为 p1,p2,p3,…,pn,若 p1=n,则 pi 为 (1) i (2) n=i (3) n-i+1 (4) 不确定 8-3. 循环队列用数组 A[0,m-1]存放其元素值,已知其头尾指针分别是 front 和 rear,则当前队列中的元素个数是 (1) (rear-front+m)%m (2) rear-front+1 (3) rear-front-1 (4) rear-front 。 。 8-4. 栈和队列的共同点是 。 (1) 都是先进先出 (2) 都是先进后出 (3) 只允许在端点处插入和删除元素 (4) 没有共同点 8-5. 为增加内存空间的利用率和减少发生上溢的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 分别设在这片内存空间的两 端,这样,只有当 时,才产生上溢。 8-6. 向量、 栈和队列都是 结构, 可以在向量的 位置插入和删除元素; 对于栈只能在 插入和删除元素; 对于队列只能在 插 入元素和 删除元素。 8-7. 设有编号为 1,2,3,4 的四辆列车,顺序进入一个栈式结构的站台。具体写出这四辆列车开出车站的所有可能的顺序。 8-8. 试证明:若借助栈由输入序列 12…n 得到输出序列为 p1p2...pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着 ijk 使 pjpkpi。 8-9. 对于循环向量中的循环队列,写出求队列长度的公式。 8-10. 用单链表实现队列如图 8-17 所示,并令 front=rear=NULL 表示队列为空,编写实现队列的如下五种运算的函数。 SETNULLQ:将队列置成空队列 FRONTQ:取队头结点数据 ENQUEUEQ:将元素 x 插入到队列的尾端 DEQUEUEQ:删除队列的第一个元素 EMPTYQ:判定队列是否为空 图 8-17 用单链表实现队列 8-11. 设单链表中存放着 n 个字符,试编写算法,判断该字符串是否有中心对称关系,例如 xyzzyx、xyzyx 都算是中心对称的字符串。要求用尽 可能少的时间完成判断。(提示:将一半字符先依次进栈。) 8-12. 设计算法判断一个算术表达式的圆括号是否正确配对。(提示:对表达式进行扫描,凡遇(就进栈,遇)就退掉栈顶的(,表达式被扫描完毕, 栈应为空。) 8-13. 两个栈共享向量空间 V[m],它们的栈底分别设在向量的两端, 每个元素占一个分量, 试写出两个栈公用的栈操作算法: push(i,x),pop(i)和 top(i), 其中 i 为 0 或 1,用以指示栈号。 8-14. 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的置空队、入队列和出队列的算 法。 8-15. 试设计算法判断字符串是否中心对称,要求利用栈作存储结构。 8-16. 假设以数组 sequ[m]存放循环队列的元素,同时设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判别 此循环队列的队满条件,并写出相应的入队列和出队列的算法(在出队的算法中要返回队头元素)。 第七章 数组和串 7-1. 串是一种特殊的线性表,其特殊性体现在 。 (1)可以顺序存储 (2)数据元素是一个字符 (3)可以连接存储 (4)数据元素可以是多个字符 7-2. 设有两个串 p,q,求 q 在 p 中首次出现的位置的运算称作 (1)连接 (2)模式匹配 (3)求子串 (4)求串长 7-3. 串的两种最基本的存储方式是 7-4. 两个串相等的充分必要条件是 7-5. 空串是 ,其长度为 和 。 。 。 。 。 。 7-6. 设 S=“I am a teacher.”,其长度为 。 7-7. 子串定位函数的时间复杂度在最坏情况下为 7-8. 快速匹配算法的最大特点是 7-9. 令 s=“aaab”,t=“abcabaa”,试分别求出它们的 next 函数值。 7-10. 若 S=“(XYZ)+*”,T=“(X+Z)*Y”,试利用连接、求子串和置换等基本运算将 S 转化为 T。 7-11. 二维数组 M 的成员是 6 个字符(每个字符占一个存储单元)组成的串,行下标 i 的范围从 0 到 8,列下标 j 的范围从 1 到 10,则存放 M 至 少需要 个字节;M 的第 8 列和第 5 行共占 个字节;若 M 按行优先方式存储,元素 M[8][5]的起始地址与当 M 按列优先方式存储时 的 元素的起始地址一致。 7-12. 数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1 到 10,从首地址 SA 开始连续存放在存储器内,存放该数组至少 需要的单元数是 。若数组按行存放时,元素 A[8][5]的起始地址为 。 7-13. 稀疏矩阵一般的压缩存储方法有两种,即 和 。 7-14. 二维数组 A[m][n]采用行序为主存储,每个元素占 k 个存储单元,并且 A[0][0]的存储地址是 200,则 A[6][12]的地址是 。 7-15. 已知三维数组 M[2…3,-4…2,-1…4],且每个元素占用 2 个存储单元,起始地址为 100,按行下标优先顺序存储,求: (1)M 所含的数据元素个数; (2)M[2,2,2],M[3,-3,3]的存储地址。 7-16. 设三对角矩阵 An× n 按行优先顺序,压缩存储在数组 B[3*n-2]之中,求: (1)用 i,j 表示 k 的下标变换公式; (2)用 k 表示 i,j 的下标变换公式。 7-17. 设 A 是一个上三角矩阵,重复元素 c 可共享一个存储空间,其余元素压缩存储到 A[n*(n+1)/2+1]中,重复元素存放在最后一个分量中。试 求:数据元素 A[k]与 aij 对应关系。 7-18. 若 x 和 y 是两个采用顺序结构存储的串,编写一个比较两个串是否相等的函数。 7-19. 若 s 一个采用顺序结构存储的串,编写一个函数,要求从 s 中删除从第 i 个字符开始的,长度为 j 的一个子串。 7-20. 若 x 是采用单链表存储的串,编写一个函数将其中的所有字符 c 替换成 s 字符。 7-21. 采用顺序存储结构串,遍写一个实现串通配符匹配的函数 pattern_index(),其中的统配符只有′? ′,它可以和任一字符匹配成功。 7-22. 采用顺序结构存储串,编写一个函数计算一个子串在一个字符串中出现的次数,如果该子串不出现则为 0。 7-23. 若 s 和 t 是两个单链表存储的串,编写一个函数找出 s 中第一个不在 t 中出现的字符。 7-24. 设对于二维数组 A[m][n],其中 m≤80,n≤80,读入数组的全部元素,对如下三种情况分别编写相应函数: (1)求数组 A 靠边元素之和; (2)求从 A[0][0]开始的互不相邻的个元素之和; (3)当 m=n 时,分别求两条对角线上的元素之和,否则打印出 m≠n 的信息。 7-25. 若在矩阵 Am× n 中存在一个元素 A[i-1][j-1]满足:A[i-1][j-1]是第 i 行元素中最小值,且又是第 j 列元素中最大值,则称此元素为该矩阵的一 个马鞍点。假设以二维数组存储矩阵 Am? n,试设计求出矩阵中所有马鞍点的算法,并分析所设计算法在最坏情况下的时间复杂度。 7-26. 已知稀疏矩阵用三元组表示,编写 C=A*B 的算法。 7-27. 已知 A 和 B 为两个 n× n 阶的对称矩阵,输入时,对称阵只输入下三角元素,存入一维数组,如图 7-15 所示。编写一个计算对称矩阵 A 和 B 的乘积的函数。 图 7-15 矩阵的存储转换形式 第九章树 9-1. 树最适合用来表示 (1)有序数据元素 。 (2)无序数据元素 (3)元素数据之间具有分支层次关系的数据 (4)元素之间无联系的数据 9-2. 对一棵满二叉树,m 个树叶,n 个结点,深度为 h,则 。 (1) n=h+m (2) h+m=2n (3) m=h-1 (4) n=2h-1 9-3. 在如图 10.32 的 4 棵二叉树中, 不是完全二叉树。 (2) (3) (4) 图 9-32 4 棵二叉树 9-4. 已知一棵树边的集合为{ (i, m), (i, n), (e, i), (b,e), (b,d), (a,b), (g,j), (g,k), (c,g), (c,f), (h,l), (c,h), (a,c) }。画出该树,并回答下列问题: (1) 根结点是 。 (2) 叶子结点有 。 (3) g 的双亲结点是 。 (4) g 的祖先结点有 。 (5) g 的孩子结点有 。 (6) b 的子孙结点有 。 (7) f 的兄弟结点是 。 (8) 树的深度是 ,b 为根的子树的深度是 。 (9) 结点 c 的度是 ,树的度是 。 9-5. 指出树和二叉树的三个主要差别。 9-6. 一棵度为 2 的树与一棵二叉树的区别是 。 9-7. 一个深度为 L 的满 k 叉树有如下性质:第 L 层上的结点均为叶子,其余各层上每个结点均有 k 棵非空子树。如果按层次顺序从 1 开始对全 部结点编号,问:(1) 各层的结点数目是多少? (2) 编号为 n 的结点的双亲结点(若存在)的编号是多少? (3) 编号为 n 的结点的第 i 个孩子结点(若存在)的编号是多少? (4) 编号为 n 的结点有右兄弟的条件是什么?右兄弟的编号是多少? 9-8. 已知一棵度为 m 的树中有 n1 个度为 1 的结点,n2 个度为 2 的结点,…,nm 个度为 m 的结点,问该树中有多少个叶子结点 ? (1) 9-9. 写出图 9-33 所示二叉树的先序、中序和后序遍历序列。 9-10. 试找出分别满足下面条件的所有二叉树: (a) 先序序列和中序序列相同; (b) 中序序列和后序序列相同; (c) 先序序列和后序序列相同。 9-11. 已知先序遍历二叉树的结果为 ABC,试问有几种不同的二叉树可得到这一遍历结果? 9-12. 设二叉树的存储结构如下图所示: 其中 t 为根结点指针,left、right 分别为结点的左右孩子指针域,data 为的数据域。请完成下列各题: (1) 画出二叉树的逻辑结构 (2) 画出二叉树的后序线. 已知一棵二叉树的中序序列和后序序列分别为 D, G, B, A, E, C, H, F 和 G, D, B, E, H, F, C, A,画出这棵二叉树。 9-14. 假设用于通信的电文由十种不同的符号来组成,这些符号在电文中出现的频率为 8, 21, 37, 24, 6, 18, 23, 41, 56, 14,试为这十个符号设计相 应的哈夫曼编码。 9-15. 试对结点序列{21, 18, 37, 42, 65, 24, 19, 26, 45, 25} 画出相应的二叉排序树,并且画出删除了结点 37 后的二叉排序树。 9-16. 一棵 n 个结点的完全二叉树以向量作为存储结构,试编写非递归算法实现对该树进行先序遍历。 9-17. 以二叉链表作存储结构,试编写非递归的先序遍历算法。 9-18. 已知二叉树的先序序列与中序序列分别存放在 preod[n]和 inod[n]数组中,并且各结点的数据值均不相同。请写出构造该二叉链表结构的非 递归算法。 9-19. 在二叉树中查找值为 x 的结点,试编写算法打印值为 x 的结点的所有祖先。假设值为 x 的结点不多于 1 个。提示:利用后序遍历非递归算 法,当找到值为 x 的结点时打印栈中有关内容。 9-20. 已知二叉树采用二叉链表存储结构,指向根结点存储地址的指针为 t。试编写一算法,判断该二叉树是否为完全二叉树。 9-21. 已知二叉树采用二叉链表存储结构,试编写一算法交换二叉树所有左、右子树的位置,即结点的左子树变成结点的右子树,右子树变为左 子树。 已知二叉树采用二叉链表存储结构,根结点存储地址为 T。试编写一算法删除该二叉树中数据值为 x 的结点及其子树。 第十章 图 10-1. 在一个无向图中,所有顶点的度数之和等于所有边数的 倍。 10-2. n 个顶点的连通图至少有 条边。 10-3. 对于一个具有 n 个顶点和 e 条边的无向图, 若采用邻接表表示, 则表头向量的大小为 10-4. 已知一个图的邻接矩阵表示,计算第 i 个结点的入度的方法是 10-5. 已知一个图的邻接矩阵表示,删除所有从第 i 个结点出发的边的方法是 10-6. 判定一个有向图是否存在回路除了可以利用拓扑排序的方法外,还可以利用 (1) 求关键路径的方法 (2) 求最短路径的方法 。 , 所有邻接表中的结点总数是 。 。 。 (3) 广度优先遍历算法 (4) 深度优先遍历算法 10-7. 对 n 个顶点的无向图 G,采用邻接矩阵表示,如何判别下列有关问题: (1) 图中有多少条边? (2) 任意两个顶点 vi 和 vj 是否有边相连? (3) 任一顶点的度是多少? 10-8. 给定有向图如图 10-26 示,试回答以下问题: (1) 每个顶点的入度与出度; (2) 相应的邻接矩阵与邻接表; (3) 强连通分量。 10-9. 给定一无向图如图 10-27 示,画出它的邻接表,写出用深度优先搜索和广度优先搜索算法遍历该图时,从顶点 v1 出发所经过的顶点和边序 列。 图 10-26 图 10-27 10-10. 对图 10-28 所示的连通网络,请分别用 Prim 算法 Kruskal 算法构造该网络的最小生成树。 10-11. 对图 10-29 所示的有向图,试利用 Dijkstra 算法求从顶点 v1 到其它各顶点的最短路径,并写出执行算法过程中每次循环的状态。 图 10-28 图 10-29 10-12. 对图 10-29 所示的有向图,试利用 Floyd 算法求出各对顶点之间的最短路径,并写出执行过程中路径长度矩阵和路径矩阵的变化过程。 10-13. 对图 10-30 所示的 AOV 网,列出全部可能的拓扑序列,并给出使用 TOPOSORTB 算法求拓扑排序时的入度域的变化过程和得到的拓扑排 序序列。 10-14. 对 10-31 所示的 AOE 网求出: (1) 各活动的最早开始时间与最迟开始时间; (2) 所有的关键路径; (3) 该工程完成的最短时间是多少? (4) 是否可通过提高某些活动的速度来加快工程的进度? 图 10-30 图 10-31 10-15. 编写一个函数根据用户输入的偶对(以输入 0 表示结束)建立其有向图的邻接表。 10-16. 利用图的深度优先搜索和广度优先搜索各写一个算法,判别以邻接表方式表示的有向图中是否存在由顶点 vi 到顶点 vj 的路径(i≠j) 。 10-17. 已知一个以邻接表方式存储的网络及网络中两个顶点。试设计一个算法: (1) 求出这两个顶点之间的路径数目; (2) 求出这两个顶点之间的某个已知长度的路径数目。 10-18. 利用深度优先搜索遍历,编写一个对 AOV 网进行拓扑排序的算法。 编写一个函数,求出无向图中连通分量的个数。 第十一章 索引和散列 11-1. 索引结构的检索分两步完成,第一步是 11-2. 稠密索引是指 11-3. 分块查找的基本思想是 ,第二步是 ,稀疏索引是指 ,其查找效率由 。 决定的。 。 11-4. 倒排表的内容是 ,倒排表检索速度快,但修改维护较难。 (1) 一个关键字值和关键字的记录地址 (2) 一个属性值和该属性的一个记录地址 (3) 一个属性值和该属性的全部记录地址 (4) 多个关键字值和它们相对应的某个记录的地址 11-5. 散列存储的基本思想是根据 来决定 。 11-6. 冲突指的是 ,装填因子 α 越 ,发生冲突的可能性越大。处理冲突的两类主要方法是 和 。 11-7. 采用分块查找时, 若线 个元素,查找每个元素的概率相同, 假设采用顺序查找来确定结点所在的块时,每块应分 个 结点最佳。 (1) 10 (2) 25 (3) 6 (4) 625 11-8. 在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是 11-9. 散列函数有一个共同性质,即函数值应当以 取其值域的每个值。 (1) 最大概率 (2) 最小概率 (3) 平均概率 (4) 同等概率 。 11-10. 设散列地址空间为 0~m-1,k 为关键字,用 p 去除 k,将所得的余数作为 k 的散列地址,即 H(k)=k MOD p。为了减少发生的冲突的频率, 一般取 p 为 。 (1) 小于 m 的最大偶数 (2) m (3) 大于 m 的最小素数 (4) 小于 m 的最大素数 11-11. 设有一组职工数据,每个记录有如下格式: 职工号、姓名、职称、性别、工资 其中“职工号”为主关键字,其它为次关键字,如表 11-5 所示。试用下列结构组织这组数据: (1)索引无序表; (2)倒排表。 表 11-5 职工数据表 记录 1 2 3 4 5 6 7 8 职工号 29 05 02 38 31 43 17 46 姓名 陈军 王强 李玫 张兵 付强 董威 赵红 李芳 职称 教授 副教授 副教授 讲师 助教 教授 助教 讲师 性别 男 男 女 男 男 男 女 女 工资 1560 1200 1260 990 850 1600 850 1050 11-12. 设散列表的长度为 15,散列函数为 H(k)=k%13,给定的关键字序列为:19,14,23,01,68,20,84,27,55,11,10,79。试画出分别用拉链法和线性探 查法解决冲突时所构造的散列表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。 11-13. 设有一组关键字序列(72,35,124,153,84,57) ,需插入到表长为 12 的散列表中。 (1) 请设计一个适当的散列函数; (2) 用设计的散列函数将上述关键字插入散列表。请画出建好的散列表结构(假定用线性探查法解决冲突) ; (3) 指出该散列表的装填因子是多少。 11-14. 设给定的散列表存储空间为 H(1~m) ,每个单元可存放一个记录,H[i](1≤i≤m)的初值为 NULL,选取的散列函数为 H(R.key),其中 R.key 为记录 R 的关键字,解决冲突方法为线性探测法,编写一个函数将某记录 R 填入到散列表 H 中。 编写对一组关键字,利用链地址法解决冲突,散列函数为 H (k),写出在此散列表中插入、删除元素的算法。 特别提请注意:作业要按要求完成和提交! **********编程作业要求*********** 1、给出测试样例及预期结果表 2、函数结构设计:功能/输入/输出 3、数据结构描述 4、算法伪代码描述 5、给出测试结果 6、给出测试的完整程序(带 main 函数) 7、重要的语句加上注释 8、算法复杂度分析 9、邮件提交,邮件题目格式: 测试作业:学号姓名——线性表测试程序 编程作业:学号姓名——线性表编程作业 (各章名称:线性表、栈与队列、数组和串、树、图、索引与散列) 10、提交文件要求: (1)源程序都放在一个 cpp 文件中。 注意: (a)无论用什么方式几个源程序文件测试,但提交要求只能是一个源文件,这样老师验证的效率高些 (b)不要提交可自动生成的文件,如 exe 等。 (c)附件中不要带文件夹。 (d) cpp 文件后缀改为 txt 后提交,不然有时打开有问题。 (2)样例测试结果不要拷屏,拷成文本格式,在控制台窗口程序运行结果复制操作命令:右键—全选—回车 ================================

http://drpetermitoff.com/zhanxiangliang/87.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有