计算机专业数据结构模拟试题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-iB.n+iC.n-i-1D.n-i+12.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由 s 指的结点，则需执行 ______ 。
( )A. link(s) J link(p) , link(p) J sB. link(q) Js, link(s) JpC. link(p) jlink(s) ， link(s) jpD. link(p) Js ， link(s) Jq3. 在非空双向循环链表中由 q 所指的那个链结点前面插入一个由 的动作对应的语句依次为 :rlink(p) Jq,llink(p)Jllink(q),llink J p, ___________________ 一条赋值语句)( )A. rlink(q) JpB. rl ink(llink(q) JpC. rlink(llink(p)) JpD. rlink(rlink(p) Jp4. 为了节省存储空间，将n 阶对称矩阵A 中包括主对角线元素在内的下三角部p 指的链结点 空白处为分的所有元素按 照行序为主序方式存放在一维数组 B[1:n(n-1)/2] 中， aij(i >j)在 B的下标 k 是 ( )A. i(i-1)/2+jB. (i(i-1))/2+jC. i(i+1)/2+jB. (i(i+1))/2+j5. 某堆栈的输入序列为 a,b,c,d, 下面的四个序列中，的输出序列。
()A. a,c,b,dB. b,c,d,aC. d,c,a,bD. c,d,b,a6. 若非空队列采用链式存储结构， front 和 rear 分别为队头元素与队列尾元 素的指针，删除此时队列的一个元素的*作时依次执行pjfront , ____________________ , call对任意下三角部分的元素__________ 不可能是它RET(P)。
()A.front jlink(rear)B.rear jlink(p)C.rear jlink(front)D.front jlink(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. 2B. 3C. 4D. 59.在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂凑函数为H(k)=i MOD,其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6] ,采用线性再散列法处理冲突。
插入后的杂凑表应该如 ____________________ 所示。
( )A.0 1 2 3 4 5 6THU TUE WED FRI SUN SAT MONB.0 1 2 3 4 5 6TUE THU WED FRI SUN SAT MONC.0 1 2 3 4 5 6TUE THU WED FRI SAT SUN MOND.0 1 2 3 4 5 6TUE THU WED SUN SAT FRI MON10.从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。
后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。
这种排序方法称为_______________ 排序法。
( )A. 插入B. 谢尔C.快速D.堆积三、填空题( 每小题2分，共20 分)1.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为L0C(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,其后序遍历序歹H为__________________ 。
6.已知序列(34 , 76, 45, 18, 26, 54, 92, 65, ) ,按照逐点插入法建立一棵二叉排序列树,该树的深度是____________________ 。
7.一个不带有权的有向图采用邻接矩阵存储方法,其邻接矩阵是一个8.带权连通图G=<V,E> 其中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与1(1 <i < 10),填入下面的方格中。
e[1:10]l[1: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）i — 1while ______________ doif （A 半 A[i+1] theni —i+1else满足条件的元素//[ for _________ doA[j- 1] —A[j]end除第i+1个元素（满足条件的元素）//使之能够正// 查找// 删_________________ ] // 修改线性表的长度//endend2. 已知非空线性链表的链结点的构造为date | link ，第一个链结点的指针为list ，下面的算法删除链表的第i 个结点(设i>0 )。
请在算法的空白处填入适当内容，使之能够正常工作。
(15 分)procedure DEL (list,i,item)________________ // 给变量q 赋初值//if (i=1) thenlist Jlink(q) //删除第一个链结点//else[ for j J1 to ____________________ doif __________ then[ call ERROR （i 超过链表的长度！' ）return ] end // r与q 分别指向第i-1 个与第i 个链结点//________________ ]// 删除第i 个链结点//// 删除被删除call RET(q)链结点的空间//。