《数据结构与算法》模拟题 4一、 判断题（共 5 题,共 10 分）1. 数据元素是数据的最小单位( )。2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算( ) 。3. 二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面( )。4. 一个有 10 个顶点,6 条边的无向图,该图不连通( )。5. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点( )。二、单选题 数据结构可形式地定义为，其中  是  上的有限集。操作 存储映像 关系 数据元素数据的最小单位是。 数据结构 数据元素 数据项 文件下列数据结构中是线性数据结构。二叉树 无向图 赫夫曼树 队列采用链式存储结构存储线性表的优点是。便于随机存取 花费的存储空间比顺序存储少便于插入和删除操作 数据元素的物理顺序与逻辑顺序相同不是队列的基本运算。判断一个队列是否为空 从队头删除一个元素在队列第  个元素之后插入一个元素 读取队头元素的值一个队列的入列序列是 ，则队列的输出序列是。广义表的表尾是。若无向图中有  个结点， 条边，则它的邻接表需要个表结点。在哈希函数  中，一般来说， 应取。奇数 偶数 充分大的数 素数 赫夫曼树的带权路径长度是。   所有叶结点带权路径长度之和 所有结点权值之和带权结点的值 除根以外所有结点权值之和设一个有序表为｛，，，，，，，，，，，，｝，当采用折半查找值为 的结点时，次比较后查找结束。 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是。直接插入排序 快速排序冒泡排序 简单选择排序三、填空题 在线性表中，一个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为!!!!!!!!!!!!。在图形结构中，每个结点的前驱结点和后继结点可以有!!!!!!!。从逻辑结构来看，线性结构的特点是!!!!!!!!!!!!。 栈又称为!!!!!!!!!!!!!!!!的线性表。设有一个顺序栈 ，元素 "#$ 依次入栈，如果  个元素的出栈顺序为 "#$，则顺序栈的容量至少为!!!!。 在队列中，可进行删除操作的一端称为!!!!!!!!。对于稀疏矩阵的压缩存储只需存储!!!!!!!!!!!!!!!!!。邻接表是图的!!!!!!!!!!!存储结构。在一棵度为  的树中，度为  的结点个数为 ，度为  的结点个数为 ，则度为  的结点为!!!!!!个。有  个结点的树有!!!!!!!!条边。对二叉排序树进行!!!!!!!!遍历，可以得到该二叉树所有结点构成的有序序列。 起泡排序、快速排序和插入排序中，不稳定的是!!!!!!!!。四、解答题  选择排序算法是否稳定？为什么？  ABEFCGD设有多项式 %&%&%，试用线性链表表示。设有一个二维数组 '('(，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为 十进制，求元素 '('(的存放位置。将如下树转换成二叉树。设哈希表表长为 ，哈希函数（用除留余数法）)#，解决冲突的方法为开放定址法&#)#，对下列关键字序列*，，，，，，+，给出计算过程并构造哈希表。五、算法题  下列程序判断字符串 ,是否对称，对称则返回 ，否则返回 ；如 $--返回，$--返回 。请填空完成该程序。   / .$!!!!!!!!/ *.01/ 234,'0(!!!!!!!!1/ $)506617088,'(,'0(1&&0661/ 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、 （<&）<&、)#)#)#)#冲突 &#)#&)#)#)# 冲突 &#)#&)# 冲突 &#)#&)#)#                五、 下列程序判断字符串 ,是否对称，对称则返回 ，否则返回 ；如 $--返回 ，（）"35,'(/（）0&&（）=0阅读如下算法，给出该算法的功能。程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在 64 个以内。 