2022年数据结构与算法试题.pdf

《2022年数据结构与算法试题.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构与算法试题.pdf（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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,

2、 则执行( 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

3、 从 1 到 10。所有数组元素相继存放于一个连续的存储空间中, 则存放该数精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 41 页 - - - - - - - - - - 数据结构与算法试题组至少需要的存储字数就是( C )。A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时, 通常需要使用 ( A )。A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为 ( C )。10、在循环队列中用数组A0 、 、m

4、 -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

5、;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、设

6、单链表中结点结构为 (data,link)、若想摘除结点 *p 的直接后继 , 则应执行下列哪一个操作 ( A ) A p-link=p-link-link; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 41 页 - - - - - - - - - - 数据结构与算法试题B p=p-link; p-link=p-link-link; C p-link=p-link; D p=p-link-link; 21、设单循环链表中结点的结构为(data,link),且 rear 就是指向非空的带表头

7、结点的 单循环链 表的尾结点 的指针。若 想删除链表第一个结点 , 则应执行下列哪一个操作 ( D ) A s=rear; rear=rear-link; delete s; B rear=rear-link; delete rear; C rear=rear-link-link; delete rear; D s=rear-link-link; rear-link-link=s-link; delete s;s 为第一个结点硫22、设单循环链表中结点的结构为(data,link),且 first为指向链表表头的指针,current为链表当前指针 , 在循环链表中 检测 current就是否达

8、到链表表尾的语句就是 ( 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 只允许在端点处插入与删

9、除 D 没有共同点26、假定一个顺序存储的循环队列的队头与队尾指针分别为f 与 r , 则判断队空的条件为 ( D )、A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为 n 的数组顺序存储一个队列时, 该队列的最大长度为 ( B ) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 41 页 - - - - - - - - - - 数据结构与算法试题A n-2 B n-1 C n D n+1 28、当利用大小为 n 的数组顺序存储一个栈时, 假定用 to

10、p= =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=10

11、0; typedef int Data Type; typedef struct Data Type dataMaxsize; Int front, rear; Queue; 若有一个 Queue类型的队列 Q,试问判断队列满的条件应就是下列哪一个语句( D ) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 41 页 - - - - - - - - - - 数据结构与算法试题A Q 、front= = Q、rear; B Q、front - Q、rear= = Maxsize; C Q、fr

12、ont + 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

13、 递归表 再入表 线性表 纯表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个存储单元 , 若第一个结

14、点的地址为 da1,则第 I 个结点的地址为 ( A ) 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 41 页 - - - - - - - - - - 数据结构与算法试题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 ) A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方

15、式存储且结点按关键码有序排列 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 求最短路径的 D

16、ijkstra方法C 深度优先遍历算法 D 广度优先遍历算法47、在 10阶 B-树中根结点所包含的关键码个数最多为(C ),最少为 ( A ) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 41 页 - - - - - - - - - - 数据结构与算法试题A 1 B 2 C 9 D 10 48、对包含 n 个元素的散列表进行搜索, 平均搜索长度为 ( C ) A O(log2n) B O(n) C 不直接依赖于 n D 上述都不对二、填空题 () 1、数据的逻辑结构被分为集合结构、线性结

17、构、 树形结构、图形结构四种2、数据的存储结构被分为顺序结构、 链接结构、索引结构、散列结构四种3、一种抽象数据类型包括 ( 数据 ) 与( 操作 ) 两个部分。4、设有两个串 p 与 q, 求 p 在 q 中首次出现的位置的运算称为( 模式匹配 ) 5、栈、队列逻辑上都就是 ( 线性存储 ) 结构。6、 线性结构反映结点间的逻辑关系就是( 一对一 )的, 图中的数据元素之间的关系就是 (多对多 ) 的, 树形结构中数据元素间的关系就是(一对多 ) 的。7、栈中存取数据的原则 ( 后进先出 ), 队列中存取数据的原则 ( 先进先出) 8、串就是由 ( 零个或多个 ) 字符组成的序列。( 长度为

18、零的串) 称为空串,( 由一个或多个空格组成的串) 称为空格串。9、设目标串 T=”abccdcdccbaa”, 模式 P=”cdcc”则第 (6) 次匹配成功。10、一维数组的逻辑结构就是( 线性结构 ), 存储结构就是 (顺序存储表示 ) 。对于二维数组 , 有( 行优先顺序 ) 与( 列优先顺序 ) 两种不同的存储方式, 对于一个二维数组Amn,若采用按行优先存放的方式, 则任一数组元素Aij相对于A00的地址为 ( n*i+j)。11、向一个顺序栈插入一个元素时, 首先使 ( 栈顶指针 ) 后移一个位置 , 然后把待插入元素 ( 写 ) 到这个位置上。 从一个顺序栈删除元素时, 需要前

19、移一位 ( 栈顶指针)。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),右子女结点为 (

20、 2*i+2 ),双亲结点 (i=1 )为(i-1)/2 ) 、16、 在一个最大堆中 , 堆顶结点的值就是所有结点中的(最大值 ), 在一个最小堆中 ,精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 41 页 - - - - - - - - - - 数据结构与算法试题堆顶结点的值就是所有结点中的(最小值 ) 。17、 已知具有 n 个元素的一维数组采用顺序存储结构, 每个元素占 k 个存储单元 ,第一个元素的地址为LOC(a1), 那么,LOC(ai)= LOC(a1)+(i-1)*k 。1

21、8、在霍夫曼编码中 , 若编码长度只允许小于等于4, 则除掉已对两个字符编码为0 与 10 外, 还可以最多对 ( 4 )个字符编码。19、设高度为 h 的空二叉树的高度为 -1, 只有一个结点的二叉树的高度为0, 若设二叉树只有度为2 上度为 0 的结点 , 则该二叉树中所含结点至少有( 2h+1 )个。20、由一棵二叉树的前序序列与(中序序列 ) 可唯一确定这棵二叉树。21、以折半搜索方法搜索一个线性表时, 此线性表必须就是 (顺序) 存储的 (有序)表。22、已知完全二叉树的第8 层有 8 个结点 , 则其叶子结点数就是 (68) 。若完全二叉树的第 7 有 10 个叶子结点 , 则整个

22、二叉树的结点数最多就是(235) 23、对于折半搜索所对应的判定树, 它既就是一棵 ( 二叉搜索树 ), 又就是一棵 ( 理想平衡树 ) 。24、假定对长度 n=50的有序表进行折半搜索 , 则对应的判定树高度为 ( ),判定树中前层的结点数为( ), 最后一层的结点数为 ( )。25、在一个无向图中 , 所有顶点的度数之与等于所有边数的()倍。在一个具有n 个顶点的无向完全图中 , 包含有 ( n(n-1)/2 )条边, 在一个具有 n 个顶点的有向完全图中 , 包含有 ( n(n-1) )条边。26、对于一个具有 n 个顶点与 e 条边的连通图 , 其生成树中的顶点数与边数分别为(n) 与

23、(n-1) 。27、设线性表中元素的类型就是实型, 其首地址为 1024,则线性表中第6 个元素精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 41 页 - - - - - - - - - - 数据结构与算法试题的存储位置就是 ( 1044) 。28、在插入与选择排序中 , 若初始数据基本正序 , 则选择 (插入排序 ), 若初始数据基本反序 , 则最好选择 (选择排序 )。29、 算法就是对特定问题的求解步驟的一种描述, 它就是 ( 指令) 的有限序列 , 每一条(指令)表示一个或多个操作

24、。30、对于一个具有 n 个顶点肯 e 条边的无向图 , 进行拓朴排序时 , 总的进间为 (n)31、 构造哈希函数有三种方法 , 分别为 (平方取中 ) 法、( 除留余数 ) 法、( 折迭移位 )法。32、处理冲突的三种方法 , 分别为 ( 线性探测 ) 、( 随机探测 ) 、( 链地址法 )。33、对于含有 n 个顶点与 e 条边的无向连通图 , 利用普里姆算法产生的最小生成树, 其时间复杂度为 ( (n2) ) 、利用克鲁斯卡尔算法产生的最小生成树, 其时间复杂度为 ( (elog2e) )34、快速排序在平均情况下的时间复杂度为( (nlog2n), 在最坏情况下的时间复杂度为 ( (

25、n2); 快速排序在平均情况下的空间复杂度为( (log2n), 在最坏情况下的空间复杂度为 ( (n) 。35、假定一组记录的排序码为( , , , , , ), 对其进行归并排序的过程中 , 第二趟排序后的结果就是( )36、假定一组记录的排序码为( , , , , , ), 对其进行快速排序的第一次划分的结果就是( )。37、一个结点的子树的 ( 个数 ) 称为该结点的度。度为 ( 零 )的结点称为叶结点或终端结点。度不为( 零 )的结点称为分支结点或非终端结点。树中各结点度的 ( 最大值 )称为树的度。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载

26、 名师归纳 - - - - - - - - - -第 11 页，共 41 页 - - - - - - - - - - 数据结构与算法试题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

27、的满 k 叉树有如下性质 : 第 h 层上的结点都就是叶结点 , 其余各层上每个结点都有k 棵非空子树 , 如果按层次自顶向下 , 同一层自左向右 , 顺序从 1 开始对全部结点进行编号, 试问: (1) 各层的结点个数就是多少? (2) 编号为 i 的结点的父结点 (若存在 ) 的编号就是多少 ? (3) 编号为 i 的结点的第 m个孩子结点 ( 若存在) 的编号就是多少 ? (4) 编号为 i 的结点有右兄弟的条件就是什么? 其右兄弟结点的编号就是多少? (5) 若结点个数为 n, 则高度 h 就是 n 的什么函数关系 ? 精品资料 - - - 欢迎下载 - - - - - - - - -

28、 - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 41 页 - - - - - - - - - - 数据结构与算法试题答案: (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)

29、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 层; 它

30、有 1 个叶结点 ,n-1 个分支结点。16、 对于一个高度为h 的 AVL树, 其最少结点数就是多少？反之, 对于一个有 n个结点的 AVL树, 其最大高度就是多少 ? 最小高度就是多少 ? 答案: 设高度为 h(空树的高度为 -1) 的 AVL树的最少结点为 Nh, 则 Nh = Fh+3 -1 。A B F G E C D H J I精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 41 页 - - - - - - - - - - 数据结构与算法试题Fh 就是斐波那契数。又设 AVL树有

31、 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) 这个工程最早可能在什么时

32、间结束。(2) 求每个事件的最早开始时间Vei 与最迟开始时间 Vli。(3) 求每个活动的最早开始时间e( ) 与最迟开始时间 l ( ) 。(4) 确定哪些活动就是关键活动。画出由所有关键活动构成的图, 指出哪些活动加速可使整个工程提前完成。509 154 677 017 275 170 503 094 553 897 512 612 765 908 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 23 页，共 41 页 - - - - - - - - - - 数据结构与算法试题答案: 按拓朴有序的顺

33、序计算各个顶点的最早可能开始时间Ve与最迟允许开始时间 Vl, 然后再计算各个活动的最早可能开始时间e 与最迟允许开始时间l, 根据l-e就是否等于 0 来确定关键活动 , 从而确定关键路径。VeVl e 0 8 L 17 8 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) 第二次排序 :0

34、76,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

35、-) )/2)。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 24 页，共 41 页 - - - - - - - - - - 数据结构与算法试题答案 : 已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc 2, 则有:ASLsucc =1/2(1+1/(1-) 2 解得2/3 ,又有:=n/m=150/m 两式联立得 :150/m2/3, 解得:m225、所以散列表需要设计225 个单位。五、算法分析题1、给出下列递归过程的执行结果voidunknown ( int w ) if (

36、 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 ) );精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 25 页，共 41 页 -

37、- - - - - - - - - 数据结构与算法试题 调用语句为 unknown ( 582 )。答案: 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 进制

38、表示。答案: 设数组元素 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; ;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 26 页，共 41 页 - - - - - - - - - - 数据

39、结构与算法试题下面的程序就是以单链表为存储结构, 实现二路归并排序的算法 , 要求链表不另外占用存储空间 , 排序过程中不移动结点中的元素, 只改各链结点中的指针 , 排序后 r 仍指示结果链表的第一个结点。在初始状态下 , 所有待排序记录链接在一个以 r 为头指针的单链表中。例如, 在算法实现时 , 利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时 , 各初始归并段为只有一个结点的有序链表。队列的数据类型为 Queue , 其可直接使用的相关操作有置空队列操作 : makeEmpty ( ); 将指针 x 加入到队列的队尾操作 : EnQueue ( ListNod

40、e * x ); 退出队头元素 , 其值由函数返回的操作 : ListNode *DlQueue ( ); 判队列空否的函数 , 空则返回 1, 不空则返回 0: int IsEmpty( ) 。解决方法提示 : ? 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。? 当队列不空时 , 从队列中退出两个有序子链表, 对它们进行二路归并 , 结果链表的表头指针存放到队列中。? 如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。在算法实现时有 6 处语句缺失 , 请阅读程序后补上。(1) 两路归并算法voidme

41、rge ( ListNode * ha, ListNode * hb,ListNode * & hc ) ListNode *pa, *pb, *pc; if ( hadata = hbdata ) hc = ha; pa = halink ; pb = hb;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 27 页，共 41 页 - - - - - - - - - - 数据结构与算法试题else hc = hb;pb = hb link ; pa = ha ; pc = hc ; while ( pa&

42、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 nex

43、t!=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) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 29 页，共 41 页 - -

44、 - - - - - - - - 数据结构与算法试题 a=t-getData(); linkedtosequent(t-getleftchild(),a,2*i+1); linkedtosequent(t-getrightchild(),a,2*i+2); 主程序调用方式 :linkedtosequent(t、root,a,0);答案 : 该程序的功能就是: 将用二叉链表表示的完全二叉树转换为二叉树的顺序( 数组 ) 表示。8、设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 3

45、1, 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,

46、H(78)=0,H(31)=5,H(15)=2,H(36)=10 利用线性探查法造表 : 0 11 12 78 1 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利用双散列法造表 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 30 页，共 41 页 - -

47、- - - - - - - - 数据结构与算法试题 Hi =(Hi-1+RH(key)%13, Hi =H(key) 0 11 12 78 1 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); 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

48、=1 ) if (p-data=q-data) p=p-rLink; 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转换为另一个基数

49、为B的 B进制数。12、阅读下面程序 , 指出其算法的功能template void BinaryTree:binsearchTree(BinTreeNode*t,int &bs) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 32 页，共 41 页 - - - - - - - - - - 数据结构与算法试题if(t!=Null) if(t-letfchild=Null|t-datat-leftchild-data)& (t-rightchild=Null|t-datarightchild-data)

50、bs=1; binsearchTree(t-leftchild,bs); if(bs) binsearchTree(t-rightchild,bs); else bs=0; 答案: 该算法就是判别给定的以二叉链表存储的二叉树就是否就是二叉搜索树。采用递归算法 , 对树中的所有结点检查就是否左子树上结点的关键码都小于它的关键码 , 右子树上结点的关键码都大于它的关键码。如满足上述条件 , 则就是二叉搜索树。六、综合算法题1、试设计一个实现下述要求的查找运算函数Locate 。设有一个带表头结点的双向链表 L, 每个结点有 4 个数据成员 : 指向前驱结点的指针llink、指向后继结点的指针 rl