山大网络教育《数据结构》( C 卷)

数据结构模拟卷一、单独选择问题1 .数据结构为()a .数据类型b .数据的存储结构c .性质相同的数据元素的集合d .相互之间存在一个或多个特定关系的数据元素的集合2 .算法分析的目的是(b )。a .判别数据结构的合理性b .评估算法的效率c .研究算法中输入和输出的关系d .认证算法的可读性3 .线性表的下一个运算中，不改变数据要素间的结构关系的运算是(d )。a .插入b .删除c .排序d .定位4 .如果输入堆栈序列为1、2、3、4、5、6且输入堆栈可交替，则可出现的输出堆栈序列为(b )。a.3、2、6、1、4、5 b.3、4、2、1、6、5c.1、2、5、3、4、6 d.5、6、4、2、3、15 .如果串sl=“数据串withjava”，s2=it”，则子串的定位函数index(s1，s2)的值变为(d )。A.15B.16C.17D.186 .以行优先顺序存储二维阵列A89，当阵列元素A23的存储地址为1087、A47的存储地址为1153时，阵列元素A67的存储地址为(a )。A.1207B.1209C.1211D.12137 .在分级扫描二叉树的算法中，需要帮助的辅助数据结构是(a )。a .队列b .堆栈c .线性表d .秩序表8 .任意一棵二叉树的前序和后序，各叶间的相对顺序关系(b )。a .不一定是一样的b .是一样的c .全部不同的d .相互逆序9 .如果把孩子的兄弟链表作为树的记忆结构，树的后列扫描应该采用二叉树(c )。a .分层扫描算法b .初级扫描算法c .中顺遍历算法d .后顺遍历算法10 .用相邻矩阵表示有向图时，各列中包含的“1”的个数为(a )。a .图中各顶点的入度b .图中的各顶点的出度c .图中弧的根数d .图中的连通成分的数量11 .图中的相邻矩阵显示方法应用于显示(c )。a .无向图b .有向图c .稠密图d .稀疏图12 .在直接选择和排序n个关键字的过程中，如果每次从无序区中选择最小的关键字要素，则在进行第I次排序之前，无序区的关键字要素的数量为(d )。PS PS PS K 1C.n-iD.n-i 1二、填补问题1 .堆栈是_操作限制_的线性表，其运算遵循_后出_的原则。2._堆栈_是一个线性表，用于限制只在表的末尾插入或删除操作。3 .一个堆栈的输入序列为1、2、3不能的堆栈输出序列为_3 1 2 _。4 .二叉树由_(1)根节点_、_(2)左子树_、_(3)右子树_三个基本单位组成。5 .在二叉树中，指针p所指的节点是叶节点的条件是_ _ p-lchild=nullp-rcild=null _ _。6 .具有256个节点的完全二叉树的深度为_ _9_ _ _ _。7 .如果已知1根度为3的树有2个度为1的节点、3个度为2的节点、4个度为3的节点，则该树有_ _ _ _ _ _ _ _ _个叶节点。8 .如果不考虑基数排序，排序过程中主要执行的两个基本操作是关键字的_比较_和记录的_移动_。9 .分别采用堆积排序、快速排序、泡沫排序和合并排序，对于初始状态有序的表，最节省时间的是_鼓泡算法，最花费时间的是_快速算法。10 .不受排序的第一个序列的影响，时间上复杂的O(N2)的排序算法可以_简单地选择排序_ _ _，且直到排序算法的最后一个为止，所有元素都不在最终位置的排序算法可以_直接插入排序_ _ _ .三、解答问题1 .某广义表的页眉和页脚用(a )、(b、c )描绘该广义表的图形表示。2 .已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。(1)画这个二叉树描绘与在(2)(1)中求出的二叉树对应的森林。3 .已知带权利图的邻接表如下： 其中，边表节点的结构如下根据该邻接表从顶点c开始进行深度优先遍历。(1)描绘由此得到的深度优秀的老师变成了树(2)写出从扫描中得到的顶点c到其他各顶点的加权路径及其长度。参考回答：1.2.(1)(2)3.(1)(2)从顶点c到顶点a的加权路径是(c、d、b、a )，其长度为8 20 11=39从顶点c到顶点b的加权路径是(c、d、b )，其长度为8 20=28从顶点c到顶点d的加权路径是(c，d )，长度是8从顶点c到顶点e的加权路径为(c、d、b、f、e )，其长度为8 20 9 14=51从顶点c到顶点f的加权路径为(c、d、b、f )，其长度为8 20 9=37 .四、算法设计问题1 .中序线索已知的二叉树t右边的子树不空。 设计算法将s指向的节点转换为t的右子树的插入一个叶节点，成为TT的右侧子树的第一个节点(同时修改)。适当的线索关系)。2 .在中序线索二叉树中查找指定节点位于下位的前驱节点的算法。参考回答：1 .回答： 问题分析如果将新插入的叶节点s作为t右侧子树顺序的第一个节点，则插入t右侧子树的最左侧的节点(假设为p )，将s作为节点p的左侧子。 s的前体是t，后续是pvoid thrtreeinsert (位树t，s )/中序线索在二叉树t的右子树中插入节点s，使s在t右子树的中序遍历第一个节点p=T-rchild； /t的右子树的最左边的节点用p指向while(p-ltag=0) p=p-lchild；S-ltag=1； S-rtag=1； /S是叶，其左右的标记都是1S-lchild=T； S-rchild=p； /S的前驱是根节点t，后续是节点pp-lchild=S； p-ltag=0； /p左边的孩子朝向s，左边的标志变更为0结束/thrtreeinsert2 .回答： 问题分析在后的顺序中，如果节点p上有右孩子，右孩子是其前驱，如果没有右孩子，左孩子是其前驱。 如果没有节点p左右的孩子，则假设其中指的是有顺序的左侧的线索的祖先节点f (p是f的右侧的子树中顺序的第一个节点)，如果f有左侧的孩子，则假设其左侧的孩子在节点p之后的顺序之前，如果f中没有左侧的孩子另一方面，如果p是中顺扫描的第一个节点，则节点p不以中顺和后顺两者向前驱动。位树输入(位树t，p )/在中序线索二叉树t中，求指定节点p的后序下的前驱节点q .位树q；PS (p-rtag=0) q=p -线路； /p中有右孩子时，右孩子是其后顺序的前驱else if (p-ltag=0) q=p-lchild； /p上没有右边的孩子，有左边的孩子，左边的孩子是后面顺序的先驱。else if(p-lchild=null) q=null； /p是中序序列的第一节点，没有后序前驱者沿着else /左边的线索找p的祖先，如果存在的话，就找祖先