2022数据结构答案.pdf
1.（判断题）在有n 个叶子结点的哈夫曼树中,其结点总数2n+lo（）（本题2.0 分）r A、正确仃B、登吴学生答案：B标准答案：B解 析：得 分：22.（判断题）链表由头指针唯一确定。（）（本题2.0 分）行A、正确r B、错误学生答案：A标准答案：A解 析：得 分：23.（判断题）完全二叉树的叶子结点只能出现在最后一层上。（）（本题 2.0 分）r A、正确 B、错误学生答案：B标准答案：B解 析：得 分：24.（判断题）由树转化来的二叉树一定没有右子树。（）（本题2.0分）A、正确C B、错误学生答案：A标准答案：A解 析：得 分：25.（判断题）折半查找要求数据必须有序,且采用顺序存储结构。（）（本题2.0 分）仃A、正确r B、错误学生答案：A标准答案：A解 析：得 分：26.（判断题）有回路的图不能进行拓朴排序。（）（本题2.0 分）A、正确B、错误学生答案：A标准答案：A解 析：得 分：27 .（判断题）在顺序存储的线性表中,逻辑上相邻的两个数据元素在物理位置上并不一定紧邻。（）（本题2.0 分）r A、正确行B、错误学生答案：B标准答案：B解 析：得 分：28 .（判断题）链式存储的线性表可以随机存取。（）（本题2.0 分）r A、正确B、错误学生答案：B标准答案：B解 析：得 分：29 .（判断题）散列表的查找效率主要取决于建表时所选取的散列函数和处理冲突的方法。（）（本题2.0 分）“A、正确r B、错误学生答案：A标准答案：A解 析：得 分：21 0 .（判断题）对于同一组记录,生成的二叉排序树的形态与记录的输入次序无关。（）（本题2.0 分）r A、正确B、错误学生答案：B标准答案：B解 析：得 分：21 1 .（单选题）设有一个二维数组A 1 0 1 5 ,数组按行存放,假设A 0 0 存放位置在6 4 4,每个元素占一个空间,则A 4 5 在（）位置。（本题2.0 分）r A、672r B、626 C、709D、724学生答案：C标准答案：C解 析：得 分：212.（单选题）顺序查找方法适用于存储结构为（）的线性表。（本题2.0 分）r A、压缩存储 B、散列存储 C、顺序存储C D、以上都不是学生答案：C标准答案：C解 析：得 分：213.（单选题）下面程序段的时间复杂度是（）0f o r （i=0;i n;i+）f o r（j=0;j next=NULLr B、p=NULLC、p-next=headD、p=head学生答案：C标 准 答 案：C解 析：得 分：22 0 .（单选题）若线性表最常用的操作是存取第i个元素及其前趋的值,则采用（）存储方式节省时间。（本题2.0 分）r A、单链表r B、双链表r C、单循环链表行D、顺序表学 生 答 案：D标 准 答 案：D解 析：得 分：22 1 .（填空题）有一个不含头结点的单链表,头指针为h e ad,则判断其 是 否 为 空 的 条 件 为（本题2.0 分）我 的 答 案：head.next=head标 准 答 案：Head=NULL解 析：得 分：点 评：22.（填空题）在顺序表（即顺序存储的线性表）中删除一个元素，需要平均移动 的元素。（本题2.0 分）我 的 答 案：1标 准 答 案：n/2或一半解 析：得 分：点 评：2 3 .（填空题）一组记录的关键字为（4 6,7 9,5 6,3 8,4 0,8 4）,利用选择排序的方法，第 一 趟 排 序 结 果 为（本题2.0 分）我 的 答 案：4 0,3 8,4 6,5 6 ,79,84标 准 答 案：38,79,56,46,40,84解 析：得 分：点 评：2 4 .（填空题）对于关键字序列（1 2,1 3,1 1,1 8,6 0,1 5,7,1 8,2 5 ,1 0 0）,用筛选法建堆，必须从键值为 的结点开始。（本题2.0 分）我 的 答 案：6 0标 准 答 案：6 0解 析：得 分：点 评：25.（填空题）我们学过的构造散列函数的方法有数字分析法、分段叠加法、伪随机数法。（本题4.0分）我 的 答 案：Q）平方取中法直接定址法标 准 答 案：（1）平方取中法除留余数法解 析：得 分：点 评：2 6 .（填空题）在使用K ru sk al 算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 上,才会被加入到生成树中。（本题2.0 分）我的答案：连通分量标准答案：同一个连通分量或同一个集合解 析：得 分：点 评：2 7 .（填空题）栈和队列是运算 的线性表。（本题2.0 分）我的答案：受限标准答案：受限的解 析：得 分：点 评：2 8 .（填空题）设有向图的邻接矩阵为A,如果图中不存在弧,则的值为（本题2.0 分）我的答案：1标准答案：0解 析：得 分：点 评：29.（填空题）n 个顶点的连通无向图的生成树含有一条边。（本题2.0 分）我的答案：n-1标准答案：解 析：得 分：点 评：30.（简答题）给定关键字序列3 2,1 3,4 9,5 5,2 2,3 8,2 1,散列函数为 H（k）=k%7,散列表的地址从0到 6,用线性探测法解决冲突,建立散列表 ht。（本题2 0.0 分）我的答案：k：3 21 34 95 52 23 82 1k%7：4606130标准答案:1地址：02 6关 键 字：4 91 2 3 4 55 5 2 2 3 8 3 2 2 1 1 34 9 5 5 2 2 3 8 3 22 11 3解 析：得 分：点 评：31.（简答题）给定叶子结点权值：（3,3 5,1 3,1 5,2 0,5,9）,构造哈夫曼树，并计算其带权路径长度。（本题2 0.0 分）我 的 答 案：树带权路径长度2 5 4得 分：点 评：
