2022年数据结构习题全集和答案归纳 .pdf

数据结构习题与解析1 一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续3、采用顺序搜索方法查找长度为n 的顺序表时，搜索成功的平均搜索长度为（ D ） 。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q 结点是 p 结点的前驱结点，若在q 与 p 之间插入结点s，则执行（ D ） 。A slink = plink ;plink = s; B plink = s; slink = q;C plink = slink ;slink = p;D qlink = s;slink = p;5、如果想在 4092 个数据中只需要选择其中最小的5 个，采用（ C ）方法最好。 A 起泡排序 B 堆排序C 锦标赛排序 D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ） 。 A 求子串B 模式匹配 C 串替换 D 串连接7、在数组 A中，每一个数组元素Aij占用 3 个存储字，行下标i 从 1 到 8，列下标 j 从 1 到 10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 37 页 - - - - - - - - - 数据结构习题与解析2 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ） 。A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ） 。10、在循环队列中用数组A0. m -1 存放队列元素，其队头和队尾指针分别为front和 rear ，则当前队列中的元素个数是（ D ） 。A ( front - rear + 1) % m B ( rear - front + 1) % mC ( front - rear + m ) % m D ( rear - front + m ) % m 11、一个数组元素 ai与（ A ）的表示等价。A * （a+i ）B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。A 指针B 引用 C 值 D 变量13、下面程序段的时间复杂度为（ C ） for (int i=0;im;i+) for (int j=0;jlink=p;p-link=s; B s-link=p-link;p-link=s; C s-link=p-link;p=s; D p-link=s;s-link=p; 19、 设单链表中结点结构为 (data,link).已知指针 q 所指结点是指针 p 所指结点的直接前驱， 若在*q 与*p 之间插入结点 *s ，则应执行下列哪一个操作 （ B ）A s-link=p-link; p-link=s; B q-link=s; s-link=p C p-link=s-link; s-link=p; D p-link=s; s-link=q; 20、设单链表中结点结构为 (data,link).若想摘除结点 *p 的直接后继，则应执行下列哪一个操作（ A ）A p-link=p-link-link; B p=p-link; p-link=p-link-link; C p-link=p-link; D p=p-link-link; 21、设单循环链表中结点的结构为（data,link）, 且 rear 是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点， 则应执行下列哪一个操作（ D ）A s=rear; rear=rear-link; delete s; B rear=rear-link; delete rear; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 37 页 - - - - - - - - - 数据结构习题与解析4 C rear=rear-link-link; delete rear; D s=rear-link-link; rear-link-link=s-link; delete s; 22、设单循环链表中结点的结构为（data,link）, 且 first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是 ( D )。A current-link =null B first-link=current C first=current D current-link=first 23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。A c,b,a B b,a,c C c,a,b D a,c,b 24、栈的数组表示中， top 为栈顶指针，栈空的条件是( A )。A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是 ( C )。A 都是先进后出 B 都是先进先出C 只允许在端点处插入和删除 D 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f 和 r , 则判断队空的条件为 ( D ). A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）A n-2 B n-1 C n D n+1 28、当利用大小为 n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改 top 指针。A top+; B top-; C top=0; D top; 29、设链式栈中结点的结构为（data, link）, 且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x 中，则应执行下列（ A ）操作。A x=top-data; top=top-link; B top=top-link; x=top-data; C x=top; top=top-link; D x=top-data; 30、设循环队列的结构是： const int Maxsize=100; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 37 页 - - - - - - - - - 数据结构习题与解析5 typedef int Data Type; typedef struct Data Type dataMaxsize; Int front, rear; Queue; 若有一个 Queue类型的队列 Q ，试问判断队列满的条件应是下列哪一个语句（ D ）A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize; 31、设有一个递归算法如下：int fact (int n ) if (n=0) return 1; else return n*fact(n-1); 下面正确的叙述是（ B ）A 计算 fact(n) 需要执行 n 次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对32、设有一个递归算法如下int x (int n) if (n递归表 纯表线性表 B 递归表 线性表 再入表 纯表C 递归表 再入表 纯表线性表 D 递归表 再入表 线性表 纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B ）的二叉树。A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子 D 任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为 2 的结点为 n2., 则( A ) A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、 由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）A 24 B 73 C 48 D 53 40、已知一个顺序存储的线性表，设每个结点需占 m个存储单元， 若第一个结点的地址为 da1,则第 I 个结点的地址为（A ）。A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 41、34 具有 35 个结点的完全二叉树的深度为( A ) A 5 B 6 C 7 D 8 42、对线性表进行折半搜索时，要求线性表必须（ C ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 37 页 - - - - - - - - - 数据结构习题与解析7 A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储C 以数组方式存储且结点按关键码有序排列 D 以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。A 散列存储 B 顺序存储或链接存储C 压缩存储 D 索引存储44、 采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度为 （ C ）A O （n2）B O （n log2n） C O（log2n） D O （n）45、对于一个具有 n 个顶点和 e 条边的无向图，进行拓扑排序时，总的时间为( A ) A n B n+1 C n-1 D n+e 46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ） 。A 求关键路径的方法B 求最短路径的 Dijkstra方法C 深度优先遍历算法 D 广度优先遍历算法47、在 10 阶 B-树中根结点所包含的关键码个数最多为（C ） ，最少为 ( A ) A 1 B 2 C 9 D 10 48、对包含 n 个元素的散列表进行搜索，平均搜索长度为（ C ）A O （log2n） B O（n）C 不直接依赖于 n D 上述都不对二、填空题1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种3、一种抽象数据类型包括（数据）和（操作）两个部分。4、设有两个串 p 和 q，求 p 在 q 中首次出现的位置的运算称为（模式匹配）5、 栈、队列逻辑上都是（线性存储）结构。6、 线性结构反映结点间的逻辑关系是（一对一） 的，图中的数据元素之间的关名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 37 页 - - - - - - - - - 数据结构习题与解析8 系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、 栈中存取数据的原则 （后进先出）， 队列中存取数据的原则 （先进先出）8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串 T=”abccdcdccbaa”, 模式 P=”cdcc”则第（ 6）次匹配成功。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组 Amn,若采用按行优先存放的方式， 则任一数组元素 Aij相对于A00的地址为（ n*i+j）。11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列 Q中，判断队空的条件为（Q.front= =Q.rear ）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ）13、对于一棵具有 n 个结点的树，该树中所有结点的度数之和为（ n-1 ） 。14、一棵高度为 5 的满二叉树中的结点数为（ 63 ）个，一棵高度为3 满四叉树中的结点数为（ 85 ）个。15、若对一棵二叉树从0 开始进行结点编号， 并按此编号把它顺序存储到一维数组中，即编号为0 的结点存储到 a0 中，其余类推，则ai 元素的左子女结点为 （ 2*i+1） ， 右子女结点为（ 2*i+2 ） ， 双亲结点（i=1 ） 为 （ (i-1)/2 ） . 16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。17、 已知具有 n 个元素的一维数组采用顺序存储结构，每个元素占 k 个存储单元，第一个元素的地址为LOC(a1)，那么， LOC(ai)= LOC(a1)+(i-1)*k 。18、在霍夫曼编码中，若编码长度只允许小于等于4, 则除掉已对两个字符编码为 0 和 10 外，还可以最多对（ 4 ）个字符编码。19、设高度为 h 的空二叉树的高度为 -1 ，只有一个结点的二叉树的高度为0，若设二叉树只有度为2 上度为 0 的结点，则该二叉树中所含结点至少有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 37 页 - - - - - - - - - 数据结构习题与解析9 （2h+1 ）个。20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。21、以折半搜索方法搜索一个线性表时，此线性表必须是 （顺序）存储的（有序）表。22、已知完全二叉树的第8 层有 8 个结点，则其叶子结点数是（68） 。若完全二叉树的第 7 有 10 个叶子结点，则整个二叉树的结点数最多是（235）23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。24、假定对长度 n=50的有序表进行折半搜索，则对应的判定树高度为（5 ） ，判定树中前 5 层的结点数为（ 31） ，最后一层的结点数为（19） 。25、在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有 n 个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n 个顶点的有向完全图中，包含有（ n(n-1) ）条边。26、对于一个具有 n 个顶点和 e 条边的连通图， 其生成树中的顶点数和边数分别为（n）和（ n-1） 。27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6 个元素的存储位置是 ( 1044) 。28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序） 。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有 n 个顶点肯 e 条边的无向图，进行拓朴排序时，总的进间为（n）31、构造哈希函数有三种方法，分别为(平方取中 )法、( 除留余数 )法、( 折迭移名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 37 页 - - - - - - - - - 数据结构习题与解析10 位)法。32、处理冲突的三种方法，分别为( 线性探测 ) 、 （ 随机探测） 、 （ 链地址法）。33、对于含有 n 个顶点和 e 条边的无向连通图， 利用普里姆算法产生的最小生成树，其时间复杂度为（n2） ） 、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（ elog2e） ）34、快速排序在平均情况下的时间复杂度为（nlog2n），在最坏情况下的时间复杂度为（n2） ） ； 快速排序在平均情况下的空间复杂度为（ （log2n） ） ，在最坏情况下的空间复杂度为（n）。35、假定一组记录的排序码为（46，79，56，38，40，80） ，对其进行归并排序的过程中，第二趟排序后的结果是（ 38 46 56 79 40 80 ）36、假定一组记录的排序码为（46，79，56，38，40，80） ，对其进行快速排序的第一次划分的结果是（ 38 404656 79 80 ） 。37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或终端结点。 度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最大值）称为树的度。38、设 Ki=Kj (1=i=n, 1=j=n,ji)且在排序前的序列中Ri领先于 Rj (i1) 的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为 n 时，高度最小的树的高度为1，有 2 层；它有 n-1 个叶结点，1 个分支结点；高度最大的树的高度为n-1, 有 n 层；它有 1 个叶结点， n-1 个分支结点。6、 一棵高度为 h 的满 k 叉树有如下性质 : 第 h 层上的结点都是叶结点 , 其余各层上每个结点都有k 棵非空子树 , 如果按层次自顶向下 , 同一层自左向右 , 顺序从 1 开始对全部结点进行编号 , 试问: 429123456789101112131481171714C名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 37 页 - - - - - - - - - 数据结构习题与解析15 (1) 各层的结点个数是多少 ? (2) 编号为 i 的结点的父结点 ( 若存在 ) 的编号是多少 ? (3) 编号为 i 的结点的第 m个孩子结点 ( 若存在 )的编号是多少 ? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度 h 是 n 的什么函数关系 ? 答案：（1）各层的结点个数是ki (i=0,1,2,.,h) （2）编号为 i 的结点的父结点 ( 若存在 )的编号是 (i+k-2)/k（3）编号为 i 的结点的第 m个孩子结点 ( 若存在 ) 的编号是 (i-1)*k+m+1 （4）当(i-1)%k0 时有右兄弟，右兄弟的编号为 i+1 （5）若结点个数为 n ，则高度 h 和 n 的关系为： h=logk(n*(k-1)+1)-1 (n=0时 h=-1)7、 写出下列中缀表达式的后缀形式：(1) A* - B + C (2) (A + B) * D + E / (F + A * D) + C (3) A & B| ! (E F) 注：按 C+ 的优先级 ) (4) !(A & !( (B D) ) )|(C !| (4)ABC|!&!CE1) 的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为 n 时，高度最小的树的高度为1，有 2 层；它有 n-1 个叶结点，1 个分支结点；高度最大的树的高度为n-1, 有 n 层；它有 1 个叶结点， n-1 个分A B F G E C D H J I、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 37 页 - - - - - - - - - 数据结构习题与解析20 支结点。16、 对于一个高度为h 的 AVL树，其最少结点数是多少？反之，对于一个有n个结点的 AVL树, 其最大高度是多少 ? 最小高度是多少 ? 答案：设高度为 h(空树的高度为 -1) 的 AVL树的最少结点为 Nh，则 Nh = Fh+3 -1 。Fh 是斐波那契数。 又设 AVL树有 n 个结点，则其最大高度不超过3/2*log2(n+1), 最小高度为 log2(n+1) -1。17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。答案：折半搜索时的判定树为：ASLSUCC=1/14（1+2*2+3*4+4*7）=45/14 ASLUNSUCC=1/15（3*1+4*14）=59/15 18、试对下图所示的AOE 网络(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间Vei 和最迟开始时间 Vli。509 154 677 017 275 170 503 094 553 897 512 612 765 908 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 37 页 - - - - - - - - - 数据结构习题与解析21 (3) 求每个活动的最早开始时间e( ) 和最迟开始时间 l ( ) 。(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。答案： 按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间 Vl，然后再计算各个活动的最早可能开始时间e 和最迟允许开始时间l, 根据l-e 是否等于 0 来确定关键活动，从而确定关键路径。Ve0 19 15 29 38 43 Vl0 19 15 37 38 43 e 0 0 15 19 19 15 29 38 L 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为43，关键路径为 19、已知有五个待排序的记录， 其关键字分别为： 256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。答案：第一次排序：（ 076，129），256，（751，937，863，742，694，301，439）第二次排序： 076，129，256，（438，301，694，742），751，（863，937）第三次排序： 076，129，256，301，438，（694，742），751，（863，937）第四次排序： 076，129，256，301，438，694，742，751，（863，937）第五次排序： 076，129，256，301，438，694，742，751，863，937 20、设有 150 个记录要存储到散列表中, 并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2 次。试问散列表需要设计多大？ ( 设是散列表的装载因子，则有ASLsucc = ( 1+1/ (1-) )/2)。答案：已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc 2，则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 37 页 - - - - - - - - - 数据结构习题与解析22 有：ASLsucc =1/2（1+1/（1-） ）2 解得2/3 ，又有：=n/m=150/m 两式联立得： 150/m2/3, 解得： m 225. 所以散列表需要设计225 个单位。五、算法分析题1、给出下列递归过程的执行结果voidunknown ( int w ) if ( w ) unknown ( w-1 ) ; f or ( int i = 1 ; i = w; i+ ) cout w ;cout endl; 调用语句为unknown (4) 。答案：(1) 1 2 2 3 3 3 4 4 4 4 2、给出递归过程的执行结果voidunknown ( int n ) cout n % 10 ;if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); 调用语句为 unknown ( 582 )。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 37 页 - - - - - - - - - 数据结构习题与解析23 答案： 2853、给出递归过程的执行结果intunknown ( int m ) int value ; if ( ! m ) value = 3 ;elsevalue = unknown ( m -1 ) + 5;returnvalue ; 执行语句为cout unknown (3) 。答案： 18 4、 设有一个二维数组A m n ，假设 A00存放位置在 644（10），A22存放位置在 676（10），每个元素占一个空间，问A33（10）存放在什么位置？脚注（10）表示用 10 进制表示。答案：设数组元素Aij存放在起始地址为Loc(i,j)的存储单元中。因为： Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以： n=(676-2-644)/2=15 所以： Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692 5、设单链表结构为struct ListNode intdata ;ListNode * link; ;下面的程序是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间 , 排序过程中不移动结点中的元素, 只改各链结点中的指针 , 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 37 页 - - - - - - - - - 数据结构习题与解析24 排序后 r 仍指示结果链表的第一个结点。在初始状态下 , 所有待排序记录链接在一个以 r 为头指针的单链表中。例如, 在算法实现时，利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时 , 各初始归并段为只有一个结点的有序链表。队列的数据类型为 Queue , 其可直接使用的相关操作有置空队列操作： makeEmpty ( ); 将指针 x 加入到队列的队尾操作：EnQueue ( ListNode * x ); 退出队头元素 , 其值由函数返回的操作：ListNode *DlQueue ( ); 判队列空否的函数 , 空则返回 1, 不空则返回 0：int IsEmpty( ) 。解决方法提示：程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。当队列不空时 , 从队列中退出两个有序子链表, 对它们进行二路归并 , 结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。在算法实现时有 6 处语句缺失，请阅读程序后补上。(1) 两路归并算法voidmerge ( ListNode * ha, ListNode * hb,ListNode *& hc ) ListNode *pa, *pb, *pc; if ( hadata = hbdata ) hc = ha;pa = halink ;pb = hb;else hc = hb;pb = hb link ; pa = ha ; pc = hc ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 37 页 - - - - - - - - - 数据结构习题与解析25 while ( pa & pb ) if (padata = pbdata) pclink = pa; pc = pa;pa = palink; else pclink = pb; pc = pb; pb = pblink; if ( pa )pclink = pa; elsepclink = pb; ; (2) 归并排序主程序voidmergesort ( ListNode * r ) ListNode* s, t; Queue Q ;if ( !r ) return;s = r; Q.EnQueue ( r ) ;while ( s ) t = slink ;while ( t != 0 & sdata next!=p ) q=q-next; if (q) Error(“*p not in head”); q-next=p-next; free(p); 7、 已知一完全二叉树从根结点开始，自顶向下， 同一层自左向右连续编号， 根结点的编号为 0，阅读以下程序请回答该程序所实现的功能： template void linkedtosequent(Bintreenode *t,type a ,int i) if (t!=Null) a=t-getData(); linkedtosequent(t-getleftchild(),a,2*i+1); linkedtosequent(t-getrightchild(),a,2*i+2); 主程序调用方式： linkedtosequent(t.root,a,0);答案： 该程序的功能是：将用二叉链表表示的完全二叉树转换为二叉树的顺序（数组）表示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 37 页 - - - - - - - - - 数据结构习题与解析27 8、设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探查法寻找下一个空位, 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位, 再散列函数为 RH ( key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH ( key) % 13, H1 = H ( key) 。画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度。答案：使用散列函数H(key)=key mod 13 有：H（12）=12， H（23）=10，H （45）=6，H （57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10 利用线性探查法造表：0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 1 1 1 1 1 1 4 1 2 1 搜索成功的平均搜索长度为：ASLsucc =1/10（1+1+1+1+1+1+4+1+2+1 ）=14/10搜索不成功的平均搜索长度为：ASLunsucc =1/13（2+1+3+2+1+5+4+3+2+1+5+4+3 ）=36/13利用双散列法造表： Hi =（Hi-1+RH(key)）%13, Hi =H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 1 1 1 1 1 1 3 5 1 1 9、阅读下面程序，指出其算法的功能并求出其时间复杂度。（1） int Prime(int n) int i=2,x=(int)sqrt(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 37 页 - - - - - - - - - 数据结构习题与解析28 while(ix) return 1; else return 0; (2)int sum1(int n) int p=1,s=0; for(int i=1;irLink, q=DL-lLink; While(p!=q&p-lLink=q)& sym=1 ) if (p-data=q-data) p=p-rLink; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 37 页 - - - - - - - - - 数据结构习题与解析29 q=q-lLink; else sym=0; return sym; 11、阅读下面程序，指出其算法的功能 #include “stack.h ” int BaseTrans(int N,int B) int i,result=0;StackS; while(N!=0)i=N%B;N=N/B;S.Push(i); while(!S.IsEmpty()i=S.GetTop();S.Pop(); result=result*10+i; return result; 答案： 该算法是将一个非负的十进制整数N转换为另一个基数为B的 B进制数。12、阅读下面程序，指出其算法的功能template void BinaryTree:binsearchTree(BinTreeNode*t,int &bs) if(t!=Null) if(t-letfchild=Null|t-datat-leftchild-data)& (t-rightchild=Null|t-datarightchild-data) bs=1; binsearchTree(t-leftchild,bs); if(bs) binsearchTree(t-rightchild,bs); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 37 页 - - - - - - - - - 数据结构习题与解析30 else bs=0; 答案：该算法是判别给定的以二叉链表存储的二叉树是否是二叉搜索树。采用递归算法，对树中的所有结点检查是否左子树上结点的关键码都小于它的关键码，右子树上结点的关键码都大于它的关键码。如满足上述条件，则是二叉搜索树。六、综合算法题1、试设计一个实现下述要求的查找运算函数Locate 。设有一个带表头结点的双向链表 L， 每个结点有 4 个数据成员： 指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为 0。每当在链表上进行一次Locate (L, x) 操作时，令元素值为x 的结点的访问频度freq 加 1，并将该结点前移， 链接到与它的访问频度相等的结点后