计算机专业数据结构模拟卷

计算机专业数据构造模拟试题 07月14日 22:00 一、判断题 (每题1分，共15分) 1.非空线性表中任意一种数据元素均有且仅有一种直接前驱元素。( ) 2.数组是一种没有插入与删除*作的线性构造。( ) 3.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组措施进行压缩存储。( ) 4.空串与由空格构成的串没有区别。( ) 5.将T在S中初次浮现的位置作为T在S中的位置的*作称为串的模式匹配。( ) 6.深度为h的非空二叉树的第i层最多有2h-1 个结点。( ) 7.完全二叉树就是满二叉树。( ) 8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ) 9.非空二叉排序树的任意一棵子树也是二叉排序树。( ) 10.有向图是一种非线性构造。( ) 11.带权连通图的最小生成树的权值之和一定不不小于它的其他生成树的权值之和。( ) 12.AOE 网是一种带权的无环连通图。( ) 13.折半查找措施合用于按值有序的线性链表的查找。( ) 14.哈希表的查找效率重要取决于所选择的哈希函数与解决冲突的措施。( ) 15.选择排序过程中元素之间的比较次数与原始序列的状态无关。( ) 二、单选题 (每题2分，共20分) 1.若长度为n的线性表采用顺序存储构造，删除它的第i数据元素之前，需要先依次向前移动_个数据元素。( ) A.n-i B.n+i C.n-i-1 D.n-i+1 2.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行_。( ) A.link(s)link(p)，link(p)s B.link(q)s，link(s)p C.link(p)link(s)，link(s)p D.link(p)s，link(s)q 3.在非空双向循环链表中由q所指的那个链结点前面插入一种由p指的链结点的动作相应的语句依次为:rlink(p)q,llink(p)llink(q),llinkp,_。（空白处为一条赋值语句）( ) A.rlink(q)p B.rlink(llink(q)p C.rlink(llink(p)p D.rlink(rlink(p)p 4.为了节省存储空间，将n阶对称矩阵A中涉及主对角线元素在内的下三角部分的所有元素按照行序为主序方式寄存在一维数组B1:n(n-1)/2中，对任意下三角部分的元素aij(ij)在B的下标k是 ( ) A.i(i-1)/2+j B.(i(i-1)/2+j C.i(i+1)/2+j B.(i(i+1)/2+j 5.某堆栈的输入序列为a,b,c,d,下面的四个序列中，_不也许是它的输出序列。( ) A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a 6.若非空队列采用链式存储构造，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一种元素的*作时依次执行pfront，_ ，call RET(P)。( ) A.frontlink(rear) B.rearlink(p) C.rearlink(front) D.frontlink(p) 7.中缀体现式A-(B+C)*D/E的后缀形式是_。( ) A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/- 8.广大义表A=(),(a),(b,(c,d)的长度为 ( ) A.2 B.3 C.4 D.5 9.在初始为空的杂凑表中依次插入核心字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂凑函数为H(k)=i MOD 7，其中，i为核心字k的第一种字母在英文字母表中的序号，地址值域为0:6，采用线性再散列法解决冲突。插入后的杂凑表应当如_所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 10.从未排序序列中选择一种元素，该元素将未排序序列提成前后两个部分，前一部分中所有元素都不不小于等于所选元素。后一部分中所有元素都不小于等于所选元素，而所选元素处在排序的最后位置。这种排序措施称为_排序法。( ) A.插入 B.谢尔 C.迅速 D.堆积 三、填空题 (每题2分，共20分) 1.已知具有n个元素的一维数组采用顺序存储构造，每个元素占k个存储单元，第一种元素的地址为LOC(a1)，那么，LOC(ai)=_。 2.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_。 3.具有n个结点的非空二叉排序树的最小深度为_。 4.深度为h且有_个结点的二叉树称为满二叉树。(设根结点处在第1层)。 5.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G?珼，H，其后序遍历序列为_。 6.已知序列(34，76，45，18，26，54，92，65，)，按照逐点插入法建立一棵二叉排序列树，该树的深度是_。 7.一种不带有权的有向图采用邻接矩阵存储措施，其邻接矩阵是一种_。8.带权连通图G=，其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：顶点偶对右下角的数据为边上的权值)，G的最小生成树的权值之和为_ 。 9.在线性表中采用折半查找法（二分查找法）查找一种数据元素，线性表中元素应当按值有序，并且采用_存储措施。 10.若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序列的状态是_。 四、问题求解题 (每题10分，共20分) 1.已知AOE网为G=(V,E)，其中, V =v1,v2,v3,v4,v5,v6,v7, E = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10, a1:(v1,v2)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4)3, a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7)6； (注：顶点偶对的右括号下方的数据表达该边上的权值)。e与l分别表达活动a1的最早开始时间与最晚开始时间，请分别求出e与l(1i10),填入下面的方格中。 e1:10 l1:10 2.若对序列(76，38，65，13，97，27，50，49)采用堆积排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟的成果： 原始序列 76 38 65 13 97 27 50 49 第1趟成果 第2趟成果 第3趟成果 第4趟成果 第5趟成果 第6趟成果 第7趟成果 第8趟成果 五、算法题 (共25分) 1.已知长度为n的线性表A采用顺序存储构造，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相似的元素。请在算法的空白处填入合适内容，使之可以正常工作。(10分) procedure DEL (A,n) i1 while _ do if (AAi+1 then ii+1 else / 查找满足条件的元素 / for _ do Aj-1Aj end / 删除第i+1个元素 (满足条件的元素) / _ / 修改线性表的长度 / end end 2.已知非空线性链表的链结点的构造为 date | link，第一种链结点的指针为list，下面的算法删除链表的第i个结点（设i0）。请在算法的空白处填入合适内容，使之可以正常工作。(15分) procedure DEL (list,i,item) _ / 给变量q赋初值 / if (i=1) then listlink(q) / 删除第一种链结点 / else for j1 to _ do rq qlink (q) if _ then call ERROR (i 超过链表的长度！) return end / r与q分别指向第i-1个与第i个链结点 / _ / 删除第i个链结点 / call RET(q) / 删除被删除链结点的空间 /