数据结构与算法模拟题4答案
发布时间:2024-05-09 01:05:43浏览次数:23《数据结构与算法》模拟题 4一、 判断题(共 5 题,共 10 分)1. 数据元素是数据的最小单位( )。2. 若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算( ) 。3. 二叉树的后序遍历序列中,任意一个结点均处在其孩子结点的前面( )。4. 一个有 10 个顶点,6 条边的无向图,该图不连通( )。5. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点( )。二、单选题 数据结构可形式地定义为,其中 是 上的有限集。操作 存储映像 关系 数据元素数据的最小单位是。 数据结构 数据元素 数据项 文件下列数据结构中是线性数据结构。二叉树 无向图 赫夫曼树 队列采用链式存储结构存储线性表的优点是。便于随机存取 花费的存储空间比顺序存储少便于插入和删除操作 数据元素的物理顺序与逻辑顺序相同不是队列的基本运算。判断一个队列是否为空 从队头删除一个元素在队列第 个元素之后插入一个元素 读取队头元素的值一个队列的入列序列是 ,则队列的输出序列是。广义表的表尾是。若无向图中有 个结点, 条边,则它的邻接表需要个表结点。在哈希函数 中,一般来说, 应取。奇数 偶数 充分大的数 素数 赫夫曼树的带权路径长度是。
所有叶结点带权路径长度之和 所有结点权值之和带权结点的值 除根以外所有结点权值之和设一个有序表为{,,,,,,,,,,,,},当采用折半查找值为 的结点时,次比较后查找结束。 在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是。直接插入排序 快速排序冒泡排序 简单选择排序三、填空题 在线性表中,一个数据元素可由若干数据项组成,在这种情况下,常将数据元素称为!!!!!!!!!!!!。在图形结构中,每个结点的前驱结点和后继结点可以有!!!!!!!。从逻辑结构来看,线性结构的特点是!!!!!!!!!!!!。 栈又称为!!!!!!!!!!!!!!!!的线性表。设有一个顺序栈 ,元素 "#$ 依次入栈,如果 个元素的出栈顺序为 "#$,则顺序栈的容量至少为!!!!。 在队列中,可进行删除操作的一端称为!!!!!!!!。对于稀疏矩阵的压缩存储只需存储!!!!!!!!!!!!!!!!!。邻接表是图的!!!!!!!!!!!存储结构。在一棵度为 的树中,度为 的结点个数为 ,度为 的结点个数为 ,则度为 的结点为!!!!!!个。有 个结点的树有!!!!!!!!条边。对二叉排序树进行!!!!!!!!遍历,可以得到该二叉树所有结点构成的有序序列。 起泡排序、快速排序和插入排序中,不稳定的是!!!!!!!!。四、解答题 选择排序算法是否稳定?为什么?
ABEFCGD设有多项式 %&%&%,试用线性链表表示。设有一个二维数组 '('(,采用以行序为主序的存储结构,每个元素占两个空间,第一个元素的存放位置为 十进制,求元素 '('(的存放位置。将如下树转换成二叉树。设哈希表表长为 ,哈希函数(用除留余数法))#,解决冲突的方法为开放定址法&#)#,对下列关键字序列*,,,,,,+,给出计算过程并构造哈希表。五、算法题 下列程序判断字符串 ,是否对称,对称则返回 ,否则返回 ;如 $--返回,$--返回 。请填空完成该程序。
/ .$!!!!!!!!/ *.01/ 234,'0(!!!!!!!!1/ $)506617088,'(,'0(1&&0661/ 5.95!!!!!!!/ +阅读如下算法,给出该算法的功能。void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); }一、判断题::;;二、三、、记录 、多个(任意) 3、是首无前驱,尾无后继,中间的元素有唯一的前驱和后继 (一对一)4、后进先出/先进后出 5、26、队首 (队头)7、非零元8、链式9、610、9911、中序12、快速排序四、、不稳定的。由于选择排序算法的原则是从记录中找到最小(或最大)者并与第一个记录交换,一旦被换到某个位置以后再也不动了,此种方法不能保证具有相同排序码的记录原来所具有的相对次序,即原来排在前面的经排序后有可能排在具有相同排序码记录的后面,所以此种排序算法是不稳定的、
-112起始下标0A11 032ABECF G D、 (<&)<&、)#)#)#)#冲突 &#)#&)#)#)# 冲突 &#)#&)# 冲突 &#)#&)#)# 五、 下列程序判断字符串 ,是否对称,对称则返回 ,否则返回 ;如 $--返回 ,()"35,'(/()0&&()=0阅读如下算法,给出该算法的功能。程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。此栈中元素个数限制在 64 个以内。