2016年数据结构与算法分析习题及参考答案.pdf

《2016年数据结构与算法分析习题及参考答案.pdf》由会员分享，可在线阅读，更多相关《2016年数据结构与算法分析习题及参考答案.pdf（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、四川大学计算机学院 数据结构与算法分析课程模拟试卷及参考答案模拟试卷一一、单 选 题（每 题 2分，共 2 0 分）1 .以下数据结构中哪一个是线性结构？（）A.有向图 B.队列 C.线索二叉树 D.B树2 .在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。A.p=q;p-n ex t=q;B.p-n ex t=q;q-n ex t=p;C.p-n ex t=q-n ex t;p=q;D.q-n ex t=p-n ex t;p-n ex t=q;3.以下哪一个不是队列的基本运算？（）A.在队列第i 个元素之后插入一个元素 B.从队头删除一个元

2、素C.判断一个队列是否为空 D.读取队头元素的值4 .字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串？A.1 4 B.5 C.6 D.85 .山权值分别为3,8,6,2 的叶子生成一棵哈夫曼树，它的带权路径长度为（）。A.1 1 B.35 C.1 9以下6-8 题基于图l o6 .该二叉树结点的前序遍历的序列为（）。A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C D、F、B7.该二叉树结点的中序遍历的序列为（）。A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E A、C

3、、B D、G、FE.D、C、A、F、G、E图 18 .该二叉树的按层遍历的序列为（）。A.E、G、F、A、C D、BC.E、A、G、C、F、B、DB.E、A、C、B D G FD.E、G、A、C、I）、F、B9 .下面关于图的存储的叙述中正确的是()oA.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关1 0 .设有关键码序列(q,g,m,z,a,n,p,x,h),

4、下面哪一个序列是从上述序列出发建堆的结果?()A.a,g,h,m,n,p,q,x,z B.a,g,m,h,q,n,p,x,zC.g,m,q,a,n,p,x,h,z D.h,g,m,p,a,n,q,x,z二、填 空 题(每 空1分，共26分)1 .数据的物理结构被分为_ _、_ _、_ _和 四种。2 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为,在 表 尾 插 入 元 素 的 时 间 复 杂 度 为。3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是;删除一个结点时，需要执行的操作是(假设栈不空而且无需回收被删除结点)。4 .对于一棵具有n个结点的二叉树，一

5、个结点的编号为i(l i W n),若它有左孩子则左孩子 结 点 的 编 号 为,若它有右孩子，则 右 孩 子 结 点 的 编 号 为,若它有双亲，则双亲结点的编号为 o5 .当向一个大根堆插入一个具有最大值的元素时，需要逐层 调整，直到被调整到_位置为止。6 .以二分查找方法从长度为10的有序表中查找一个元素时，平 均 查 找 长 度 为。7 .表 示 图 的 三 种 常 用 的 存 储 结 构 为、和8.对于线 性 表(7 0,3 4,5 5,2 3,65,4 1,2 0)进行散列存储时，若选用H (K)=K%7作为散列函数，则散列地址为0 的元素有 个，散列地址为6的有 个。9.在归并排

6、序中，进 行 每 趟 归 并 的 时 间 复 杂 度 为,整个排序过程的时间复杂度为,空间复杂度为。10.在一棵m阶B/对匕每个非树根结点的关键字数目最少为 个,最多为个，其 子 树 数 目 最 少 为,最多为三、运 算 题(每 题6分，共24分)I .写出下列中缀表达式的后缀形式：(1)3 X/(Y-2)+l(2)2+X*(Y+3)2 .试对图2中的二叉树画出其：(1)顺序存储表示的示意图；(2)二叉链表存储表示的示意图。3 .判断以下序列是否是小根堆？如果不是，将它调整为小根堆。(1)12,7 0,3 3,6 5,2 4,5 6,4 8,92,86,3 3 (2)05,2 3,2 0,2

7、8,4 0,3 8,2 9,6 1,3 5,7 6,4 7,100 4 .已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7);E=(1,2)3,(1,3)5,(1,4)8,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)2 0,(5,6)18,(6,7)2 5 ;按照普里姆算法从顶点1 出发得到最小生成树，试写出在最小生成树中依次得到的各条边。四、阅读算法(每题7 分，共 14分)1.void AE(Stack&S)I n i tSta c k(S);P ush(S,3);P ush(S,4);i n t x二 P o p(S)+

8、2*P o p(S);P ush(S,x);i n t i,a 5 =l,5,8,12,15);f o r(i=0;i left,cl,c2);c l+;if(BT-left=NULL&BT-right=NULL)c2+;ABC(BT-right,c l,c2);/if)该函数执行的功能是什么？五、算法 填 空(共 8 分)向单链表的末尾添加一个元素的算法。V o i d I n se rtR e a r(L N o d e*&H L,c o n st E l e m T y p e&i te m)(L N o d e*n e wp tr;n e wp tr=n e w L N o d e;I

9、 f ()(c e rr，zM e m o ry a l l o c a ti o n f a i l a re!e n d l;e xi t(1);)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _=i te m;n e wp tr-n e xt=N U L L;i f (H L 二 二 N U L L)HL=;e l se L N o d e*P=H L;W hi l e (P-n e xt!=N U L L)p-n e xt=n e wp tr;)六、编写算法(共 8 分)编写从类型为L i st的线性表L中将第i 个元素删除的算法，(假

10、定不需要对i 的值进行有效性检查,也不用判别L 是否为空表。)vo i d De l e te(L i st&L,i n t i)模拟试卷一 参考答案单选题(每题2 分，共 2 0 分)l.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B二、填 空 题(每 空 1 分，共 2 6 分)1 .顺 序 链 表 索 引 散 列2.0(n)0(1)3.p-n e xt=H S;H S=p H S=H S-n e xt4.2 i 2 i+l L i/2(或 i/2)5.向上根6.2.97.邻 接 矩 阵 邻 接 表 边 集 数 组8.1 49.0(n)0(nlog2n)0(n

11、)10.m/2 L l m-1 1m/2 1 m三、运算题(每题6 分，共 2 4 分)1.(1)3 X *Y 2 -/I +(2)2 X Y 3 +*+图 39 10 11 12 13 14 15 162.(1)012345678123456789(2)见图3 所示：3 .不是小根堆。调 整 为:12,6 5,3 3,7 0,2 4,5 6,4 8,9 2,8 6,3 3(2)是小根堆。4 .普里姆算法从顶点I 出发得到最小生成树为：(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)2 0四、阅读算法(每题7 分，共 1 4 分)1.3 0 2 4 16 10

12、 2 102.该函数的功能是：统计出B T所指向的二叉树的结点总数和叶子总数五、算法 填 空(共 8 分，每一空2 分)ne w ptr=N U L L ne w ptr-=d a ta ne w ptr p=p-ne x t六、编写 算 法(8 分)voi d D e le te(L i st&L,i nt i)(f or(i nt j=i-l;j ne x t=H L;B.p-ne x t=H L-ne x t;H L-ne x t=p;C.p-ne x t=H L;p=H L;D.p-ne x t=H L;H L=p;2 .若顺序存储的循环队列的Q ue ue M a x S i ze=

13、n,则该队列最多可存储（）个元素.A.n B.n-1C.n+1 D.不确定3 .下述哪一条是顺序存储方式的优点？（）A.存储密度大 B.插入和删除运算方便C.获取符合某种条件的元素方便 D.查找运算速度快4 .设有一个二维数组Amn,假 设 A 存放位 置 在 6 00（助,4 3 3 存放位置在6 7 8（助，每个元素占一个空间，问*2 3（助存放在什么位置？（脚注（表示用10进制表示,m 3）A.6 5 8 B.6 4 8 C.6 3 3 D.6 5 35 .下列关于二叉树遍历的叙述中，正确的是（）。A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B

14、.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6 .k 层二叉树的结点总数最多为（）.A.2-1 B.2 K+1 C.2 K-1 D.7 .对线性表进行二分法查找，其前提条件是（）.A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对 n

15、个记录进行堆排序，所需要的辅助存储空间为A.0（l o g2n）B.0（n）C.0（1）D.0（n 2）9.对于线性表（7,34,7 7,2 5,64,49,2 0,14）进行散列存储时，若 选 用 H（K）=K%7 作为散列函数，则散列地址为0 的元素有（）个，A.1 B.2C.3D.410.下列关于数据结构的叙述中，正确的是（）.A.数组是不同类型值的集合B,递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填 空 题（每 空 1 分，共 26分）1.数 据 的 逻 辑 结 构 被 分 为、和 四种。2 .一个算法的时间复

16、杂度为(37+2 000”l o g 2+90)/2,其 数 量 级 表 示 为。3.对于一个长度为n的单链存储的队列，在 表 头 插 入 元 素 的 时 间 复 杂 度 为,在表 尾 插 入 元 素 的 时 间 复 杂 度 为。4.假定一棵树的广义表表示为A(D(E,G),H(L J),则树中所含的结点数为个，树的深度为，树的度为。5.后缀算式7 9 2 30+-4 2 /*的值为。中缀算式(3+X*Y)-2 Y/3对应的后缀算式为 o6.在一棵高度为5 的理想平衡树中，最少含有 个结点，最多含有 个结点。7 .在树中，一个结 点 的 直 接 后 继 结 点 称 为 该 结 点 的。一个结点

17、的直接前趋结点称为该结点的。8.在一个具有10个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。9.假定一个线性表为(12,17,7 4,5,63,49,82,36),若按Ke y%4 条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为、和O10.对一棵B _ 树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度。11.在堆排序的过程中，对 任 一 分 支 结 点 进 行 筛 运 算 的 时 间 复 杂 度 为,整个堆排序过 程 的 时 间 复 杂 度 为。12.在线性表的散列存储中，装填因子a 又称为装填系数，若用

18、m表示散列表的长度，n 表示待散列存储的元素的个数，则a 等于。三、运 算 题(每 题 6 分，共 24分)1.在如下数组A 中链接存储了一个线性表，表头指针存放在A 0.n e x t,试写出该线性表。A 0 1 2 3 4 5 6 760507 890344040527132 .已知棵二叉树的前序遍历的结果是AB KC D F G HIJ,中序遍历的结果是KB C D AF HIG J,试画出这棵二叉树。3.已知一个图的顶点集V为：V=1,2,3 4 5,6,7;其共有1 0 条边。该图用如下边集数组存储:122552261364547677751122233457试用克鲁斯卡尔算法依次求

19、出该图的最小生成树中所得到的各条边及权值。4 .画出向小根堆中加入数据4,2,5,8,3,6,1 0,1 时，每加入一个数据后堆的变化。四、阅读算法(每题7 分，共 14分)1 .在下面的每个程序段中，假定线性表L a 的类型为L is t,元素类型E lemTyp e为 int,并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表L a。(1)I nit L is t(L a);I nt a =1 0 0,2 6,5 7,3 4,7 9;F or (i=0;i5;i+)I ns er t(L a,a i);Tr a v er s eL is t(L a);(2)Delet eF

20、 r ont(L a);I ns er t R ea r(L a,Delet eF r ont(L a);Tr a v er s eL is t(L a);(3)C lea r L is t(L a);F or (i=0;idata,ABC(BT-left);ABC(BT-right);五、算法填空(共8 分)二分查找的递归算法。I nt B ins ch(E lemTyp e A ,int low,int hig h,K eyTyp e K)(ifint mid=(low+hig h)/2;if ()r et u r n mid;查找成功，返回元素的下标els e if (K A mid.k

21、ey)r et u r n B ins ch(A,low,mid-1,K);在左子表上继续查找els e return；/在右子表上继续查找)els e；查找失败，返回T)六、编写 算 法(共 8 分)H L为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。bool Find(LNode*HL,ElemType&item)模拟试卷二参考答案一、单选题(每题2 分，共 20分)l.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D二、填 空 题(每 空 1 分，共 26分)1.集 合 结 构 线 性 结 构 树 结 构 图 结 构2.0(n)3.0

22、(1)0(1)4.7 2 25.9 4 3 XY*+2Y*3/-6.1 6 3 17.孩子(或子)结点 双亲(或父)结点8.4 5 n(n-1)9.(1 2,3 6)(1 7,5,4 9)(7 4,8 2)(6 3)1 0.减 少1 (或减少)1 1.0(log2n)0(nlog2n)1 2.n/m三、运算题(每题6 分，共 24分)1 .线性表为：(9 0,4 0,7 8,5 0,3 4,6 0)2 .当前序序列为A B K C D F G H I J,中序序列为K B C D A F H I G J时，逐步形成二叉树的过程(1,6)1,(2,4)1,(2,5)2,(5,7)2,(2,6)3

23、,(3,5)74 .见图5 o图5四、阅读算法(每题7 分，共 14分)1 .(l)L a=(2 6,3 4,5 7,7 9,1 0 0)L a=(5 7,7 9,1 0 0,3 4)(3)L a=(7 9,3 4,5 7,2 6,1 0 0)2 .前序遍历链式存储的二叉树。五、算法填空(每空2 分，共 8 分)(low da t a=it em)r et u r n t r u e;els e p=p-next;r et u r n f a ls e;模拟试卷三一、单 选 题（每 题 2 分，共 20分）1 .对一个算法的评价，不包括如下（）方面的内容。A.健壮性和可读性 B.并行性 C.正

24、确性 D.忖空复杂度2 .在带有头结点的单链表HL中，要向表头插入一个由指针p 指向的结点，则执行（）。A.p-next=H L-next;H L-next=p;B.p-next=H L;H L=p;C.p-next=H L;p=H L;D.H L=p;p-next=H L;3 .对线性表，在下列哪种情况下应当采用链表表示？（）A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4 .一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是（）A.23 1 B.3 2 1C.3 1 2 D.1 235 .AOV网是

25、一 种（）A.有向图 B.无向图 C.无向无环图 D.有向无环图6 .采用开放定址法处理散列表的冲突时，其平均查找长度（）。A.低于链接法处理冲突 B.高于链接法处理冲突C.与链接法处理冲突相同 D.高于二分查找7 .若需要利用形参直接访问实参时，应将形参变量说明为（）参数。A.值 B.函数 C.指针 D.引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。A.行号 B.列号 C.元素值 D.非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。A.0（l o g2n）B.O（n l o g2n）C.0（n）D.0（n2）1 0 .从二叉搜索树中查找一个元素时、

26、其时间复杂度大致为（）。A.O（n）B.0（1）C.0（l o g2n）D.0（n2）二、运 算 题（每 题 6 分，共 24分）1 .数 据 结 构 是 指 数 据 及 其 相 互 之 间 的。当结点之间存在M 对 N （M：N）的联系时，称这种结构为。2.队列的插入操作是在队列的 进行，删除操作是在队列的 进行。3 .当用长度为N的数组顺序存储一个栈时，假定用t o p=N 表示栈空，则表示栈满的条件是。4 .对于一个长度为n的单链存储的线性表，在 表 头 插 入 元 素 的 时 间 复 杂 度 为,在 表 尾 插 入 元 素 的 时 间 复 杂 度 为。5 .设 W 为一个二维数组，其每

27、个数据元素占用4个字节，行下标i 从 0到 7 ,列下标j从 0到 3 ,则二维数组W 的数据元素共占用 个字节。W 中第6行的元素和第 4列的元素共占用 个字节。若按行顺序存放二维数组W,其起始地址为1 0 0,则二维数组元素W 6,3 的起始地址为。6 .广义表A=（a,（a,b）,（a,b）,c）,则它的深度为,它的长度为。7 .二叉树是指度为2 的 树。棵结点数为N的二叉树，其所有结点的度的总和是8.对-棵二叉搜索树进行中序遍历时，得到的结点序列是一个。对一棵由算 术 表 达 式 组 成 的 二 叉 语 法 树 进 行 后 序 遍 历 得 到 的 结 点 序 列 是 该 算 术 表 达

28、 式 的9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 个,其中 个用于指向孩子，个指针是空闲的。10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A 中。其余类推，则A i 元 素 的 左 孩 子 元 素 为,右孩子元素为,双亲元素为 o11.在 线 性 表 的 散 列 存 储 中，处 理 冲 突 的 常 用 方 法 有 和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 两种。12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时,

29、宜采用排 序；当 待 排 序 的 记 录 数 较 大，存 储 空 间 允 许 且 要 求 排 序 是 稳 定 时，宜采用_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 排序。三、运 算 题(每 题6分，共24分)1.已知一个6x5稀疏矩阵如右所示，试：(1)写出它的三元组线性表；(2)给出三元组线性表的顺序存储表示。2.设有一个输入数据的序列是 46,25,78,62,12,80，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。3.对 于 图6所示的有向图若存储它采用邻接表，并且每个顶点邻00001000000-10000000250

30、00000700接表中的边结点都是按照终点序号从小到大的次序链接的，试写出:(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；4.已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=,6,5 ;若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。四、阅 读 算 法(每 题7分，共14分)int Prime(int n)(int i=l;int x=(int)sqrt(n);while(+ix)return 1;el

31、se return 0;(1)指出该算法的功能；(2)该算法的时间复杂度是多少？2.写出下述算法的功能：v o i d A J(a d j l i s t G L,i n t i,i n t n)(Q u e u e Q;I n i t Q u e u e(Q);c o u t i，;v i s i t e d i =t r u e;Q I n s e r t (Q,i);w h i l e(!Q u e u e E m pt y(Q)i n t k=Q D e l e t e(Q);e d g e n o d e*p=G L k ;w h i l e(p!=N U L L)(i n t j=

32、p-a d j v e x;i f (!v i s i t e d j )(c o u t j，;v i s i t e d j =t r u e;Q I n s e r t(Q,j);)p=p-n e x t;)五、算法 填 空(共8分)如下为二分查找的非递归算法，试将其填写完整。I n t B i n s c h(E l e m T y pe A ,i n t n,K e y T y pe K)(i n t l o w=0;i n t h i g h=n-l;w h i l e (l o w =h i g h)(i n t mid=；i f (K=A m i d .k e y)r e t

33、u r n m i d;查找成功，返回元素的下标e l s e i f (K next;ElemType temp=p-data;delete p;return temp;)模拟试卷四一、单 选 题（每 题 2分，共 2 0 分）I .以下数据结构中哪一个是线性结构？（）A.有向图 B.栈 C.二叉树 D.B树2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。A.单链表C.带头结点的双循环链表3 .以下哪一个不是队列的基本运算？（）A.在队列第i个元素之后插入一个元素C.判断一个队列是否为空B.双链表D.单循环链表B.从队头删除一个元素D

34、.读取队头元素的值4 .字 符 A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串？A.15 B.14 C.16 D.215.由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。A.11 B.37 C.19 D.53以下6-8 题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G,后序遍历的序列为B、D、C、A、F、G、E。6.则该二叉树结点的前序遍历的序列为（）.A.E、G、F、A、C、D、BC.E、A、C、B、D、G、F7.该二叉树有（）个叶子。A.3 B.2 C.58.该二叉树的按层遍历的序列为（）

35、A.E、G、F、A C、D BC.E、A、G、C、F、B、D9.下面的二叉树中，（）不是完全二叉树。B.E、A、G、C、F、B、DD.E、G、A、C D、F、BD.4B.E、A C、B D、G FD.E、G、A、C、D、F、BA B.C.D.10.设有关键码序列（q,g,m,z,a）,下面哪一个序列是从上述序列出发建的小根堆的结果?()A.a,g ,m q,z B.a,g m,z,qC.g ,m,q,a,z D.g,m,a,q,z二、填 空 题(每空1 分，共 2 6 分)1 .数 据 结 构 是 指 数 据 及 其 相 互 之 间 的。当结点之间存在1 对 N (1：N)的联系时，称这种结构

36、为。2 .一个广义表中的元素分为 元素和 元素两类。3 .对于一个长度为n的顺序存储的线性表，在 表 头 插 入 元 素 的 时 间 复 杂 度 为,在表尾插入元素的时间复杂度为 04 .向一个由H S 指向的链栈中插入一个结点时p 时，需要执行的操作是:删除一个结点时，需要执行的操作是(假设栈不空而且无需回收被删除结点)。5 .栈又称为 表，队列又称为 表。6 .在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、为辅序的次序排列。7 .若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K,则左、右 子 树 皆 非 空 的 结 点 个 数 是。8 .以折半(或二分)

37、查找方法从长度为8的有序表中查找一个元素时，平均查找长度为9 .表 示 图 的 三 种 常 用 的 存 储 结 构 为、和。10 .对于线 性 表(7 8,4,5 6,3 0,6 5)进行散列存储时，若选用H (K)=K%5作为散列函数，则散列地址为0的元素有 个，散列地址为4的有 个。11.在归并排序中，进 行 每 趟 归 并 的 时 间 复 杂 度 为，整个排序过程的时间复杂度为,空间复杂度为 o1 2 .在 n 个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为 W P L 称为 o1 3 .在索引表中，若一个索引项对应主表的一个记录，则此索引为 索 引，若对应主表的若干条

38、记录，则称此索引为 索引。三、运 算 题(每 题 6分，共 2 4 分)1.写出下列中缀表达式的后缀形式：(1)3 X/(Y-2 H)+1(2)2+X*(Y+3)2.假定一棵二叉树广义表表示为a(b(c),d(e,f)，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：3.已知一个无向图的顶点集为 a,b,c,d,e ，其邻接矩阵如下所示01 0 011 0 01 000 01 101 1 011 01 1 0(1)画出该图的图形；(2)根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。4.已知一个图的顶点集V和边集E 分别为：V=0,1,2

39、,3,4,5,6,7 ;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)2 5,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)2 0);按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。四、阅读算法(每题7分，共14分)1.v o i d A E(S t ac k&S)I n i t S t ac k(S);P u s h (S,3);P u s h (S,4);i n t x=P o p(S)+2*P o p(S);P u s h(S,x);i n t i,a 5 =2,5,8,2 2,15 ;f o r(i=0;i

40、 5;i+)P u s h(S,a i );w h i l e (!S t ac k Em p t y (S)c o u t d at a;查找成功r e t u r n t r u e;e l s e i f(i t e m d at a)BS T=BS T-;e l s e BS T=BS T-;/w h i l er e t u r n ;查找失败)六、编写算法(共8 分)用递归的算法编写出对存入在a n+l 数组中的n 个有序元素进行二分(又称折半)查找(假定a 0 单元不用)的程序。int halfsearch(SSTable*a,KeyType k,int low,int high

41、)模拟试卷四参考答案一、单选题(每题2 分，共 2 0 分)l.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 1 0.B二、填 空 题(每 空 1 分，共 2 6 分)1 .联 系 树(或 树 结 构)2 .单 (子)表3 .0(n)0(1)4 ,p-nex t=HS;HS=p HS=HS-nex t5 .先 进 后 出 先 进 先 出6.行 歹 I J7.k-18.2.62 59.邻 接 矩 阵 邻 接 表 边 集 数 组1 0 .2 11 1 .0 (n)0(nlog2 n)0(n)1 2 .哈夫曼树 带权路径长度1 3 .稠密 稀疏三、运算题(每题6 分，共 2 4

42、 分)I.(1)3 X *Y 2 H*-/I +(2)2 X Y 3 +*+2 .先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按层：a,b,d,c,e,f3 .(1)该图的图形如图9 示：(2)深度优先遍历序列为：a b d c e广度优先遍历序列为：a b od e图 94 .普里姆：(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)1 0,(6,4)4,(5,7)2 0四、阅读算法(每题7 分，共 1 4 分)3 .1 5 2 2 8 5 2 1 04 .该函数的功能是:n+求.aknifjn,n)=d a t a left r ig

43、ht fa ls e六、编写算法(8 分)递 归 算 法：int ha lfs ea r c h(SSTa b le*a,K ey Ty p e k,int low,int high)if(low high)r et u r n 0;els e int mid=(low+high)/2if E Q(k,a mid ,key)r et u r n mid;els e if L T(k,a mid ,key)r et u r n ha lfs ea r c h(a,k,low,mid-1);els e r et u r n ha lfs ea r c h(a,k,mid+1,high);)模拟试卷

44、五单 选 题（每 题 2 分，共 20分）1 .栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2 .用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针 B.头、尾指针都要修改C.仅修改尾指针 D.头、尾指针可能都要修改3 .以下数据结构中哪一个是非线性结构？（）A.队列 B.栈 C.线性表 D.二叉树4 .设有一个二维数组Amn,假 设A 0 0 存放位置在64 4,|0），A 2 存放位置在676的，每个元素占一个空间，问4 3 3卜0）存放在什么位置？脚注（表示用1。进制表示。A.688B.678C.692 D.6965

45、.树最适合用来表示（）。A.有序数据元素C.元素之间具有分支层次关系的数据6.二叉树的第k层的结点数最多为（）.A.2-1 B.2 K+1 C.2 K-1B.无序数据元素D.元素之间无联系的数据D.2卜,7.若 有1 8个元素的有序表存放在一维数组A 1 9中，第一个元素放A中，现进行二分查找，则查找A 3 的比较序列的下标依次为（）A.1,2,3 B.9,5,2,3C.9,5,3 D.9,4,2,38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A,0（1）B.0（n）C.0（l o g2n）D.0（n 2）9.对于线性表（7,3 4,5 5,2 5,6 4,4 6,2 0,1

46、0）进行散列存储时，若 选 用I I （K）=K%9作为散列函数，则散列地址为1的元素有（）个，A.1 B.2 C.3 D.410.设有6 个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5 B.6 C.7 D.8二、填 空 题(每空1 分，共 26分)1.通常从四个方面评价算法的质量：、和。2.一个算法的时间复杂度为(3+g2”+14”)/”2,其 数 量 级 表 示 为。3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J),则树中所含的结点数为 个，树的深度为，树的度为 o4.后缀算式92 3+-10 2/-的值为。中缀 算 式(3+4X)-2Y/3对应的后缀算

47、式为。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 个指针域，其中有 个指针域是存放了地址，有 个指针是空指针。6.对于一个具有n 个顶点和e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有 个和 个。7.AOV网是一种 的图。8.在一个具有n 个顶点的无向完全图中，包含有 条边，在一个具有n 个顶点的有向完全图中，包含有 条边。9.假定一个线性表为(12,23,74,55,63,40),若按Key%4 条件进行划分，使得同一余数的元素 成 为 一 个 子 表，则得到的四个子表分别为、和O10.向 棵

48、B-树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度11.在堆排序的过程中，对 任 一 分 支 结 点 进 行 筛 运 算 的 时 间 复 杂 度 为，整个堆排序过 程 的 时 间 复 杂 度 为。12.在快速排序、堆排序、归并排序中，排序是稳定的。三、运 算 题(每 题 6 分，共 24分)1.在如下数组A 中链接存储了一个线性表，表头指针为A 0.next,试写出该线性表。datanextA 0 1 2 3 4 5 6 760507890344035720412.3.请画出图10的邻接矩阵和邻接表。已知一个图的顶点集V 和边集E 分别为：V=1,2,3,4,5,6,7;E=

49、(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树 图 10中依次得到的各条边。4.画出向小根堆中加入数据4,2,5,8,3 时，每加入一个数据后堆的变化。四、阅读算法(每题7 分，共 14分)1.LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L；L=L-next；p=L；SI：S2：while(p-next)p=p-next；pnext=q；qne

50、xt=NULL；)return L；请回答下列问题：(1)说明语句s i 的功能；(2)说明语句组S 2的功能：(3)设链表表示的线性表为61赳，,a)，写出算法执行后的返回值所表示的线性表。2.void ABC(BTNode*BT)(if BTABC(BT-left);ABC(BT-right);coutBT-data该算法的功能是：五、算法填空(共8 分)二叉搜索树的查找一递归算法：bool Find(BTreeNode*BST,ElemType&item)(if(BST=NULL)return false;查找失败else if(item=BST-data)i tem=BST-data;