2022年2007~2008学年《数据结构》B

1、华侨高校数据结构试卷（B）系别：班级：学号：姓名：考试日期：年月日题号一二三四五总分得分一，选择填空题（每题1.5 分,共 15 分）1， 在一个长度为 n 的次序线性表中次序查找值为平均比较次数,假定查找每个元素的概率都相等）为（x 的元素时,查找成功时的平均查找长度（即）.x 与元素的AnBn/2Cn+1/2Dn-1/22，已知单链表 A 长度为 m,单链表 B 长度为 n,如将 B 联接在 A 的末尾,其时间复杂度应为（）.AO1BOmCOnDOm+n3， 如进栈序列为 a,b,c,就通过入出栈操作可能得到的a,b,c 的不同排列个数为（）.A4B5C6D74， 由权值分别为11, 8,

2、 6,2, 5 的叶子结点生成一棵赫夫曼树,它的带权路径长度WPL 为（）.A24B71C48D535，已知函数 Subs,i,j 的功能是返回串 s 中从第 i 个字符起长度为 j 的子串,函数 Scopys,t的功能为复制串t到 s.如字符串 S=SCIENCESTUDY,就调用函数ScopyP,SubS,1,7后得到（）.A P= SCIENCEBP= STUDYCS= SCIENCEDS= STUDY6，二维数组 A47 按列优先储备方法储备在内存中,如每个元素占2 个储备单元,且数组中第一个元素的储备地址为 120,就元素 A34 的储备地址为（）.A139B145C158D1627

3、，以下陈述中正确选项 .A 二叉树是度为 2 的有序树B 二叉树中结点只有一个孩子时无左右之分C 二叉树中必有度为2 的结点D 二叉树中最多只有两棵子树,并且有左右之分8，n 个顶点的无向完全图中含有向边的数目最多为.An-1BnCnn-1/2Dnn-19，假定一个链式队列的队头和队尾指针分别为front和rear,就判定队空的条件为.Afront = =rearBfront .=NULLCrear .= NULLDfront NULL10，以下排序方法中,哪一种方法的比较次数与纪录的初始排列状态无关？A直接插入排序B冒泡排序C快速排序D简洁选择排序二，填空题（每空 1 分,共 10 分）1，

4、如一个算法中的语句频度之和为Tn=3720n+4nlogn ,就算法的时间复杂度为.2，数据结构的储备结构包括次序，索引和散列等四种.可编辑资料 - - - 欢迎下载3 ，假设一个10 阶的下三角矩阵A ,按行优先次序压缩储备在一维数组C 中,就 C 数组的大小应为 .4，一棵高度为 4 的二叉树中最少含有个结点,最多含有个结点. 一棵高度为 4 的完全二叉树中,最少含有个结点,最多含有个结点.5，在对长度为n 的关键字序列进行堆排序的过程中,对堆顶元素进行堆调整的选择运算的时间复杂度为,整个堆排序过程的时间复杂度为.6 ，如对序列 49 , 38, 65, 97, 76, 13, 27, 5

5、0 接受冒泡排序法排序,就其次趟终止后序列的状态是.三，解答题（每题 5 分,共 30 分）1，指出下面算法中,带下划线的语句的语句频度,并估量该算法的时间复杂度.int funint ns=0;t=0;fori=1;i<n;i+ s+=2;forj=n;j>=i;j-t+;return s+t;2，设循环队列的总长度为5,入队的序列为 A1 ,A2 ,A3 ,A4 ,然后 A1 , A2 出队,最终 A5 , A6 入队, 请画出最终的循环队列,并写出在循环队列中判定队空和队满的条件.3，某二叉树bt 中序遍历序列为：ABCEFGHD ,后序遍历序列为： ABFHGEDC ,请构

6、造该二叉树（画出树形）,并画出对应的先序线索（不带头结点）.4，试画出如下图的无向图G 的邻接表表示,要求邻接表中的各顶点的邻接链表中的表结点按顶点序号从小到大排列. 依据你所给出的邻接表, 给出从 A 动身的深度优先搜寻序列, 并给出其深度优先搜寻dfs 生成树.ABCDE无向图 G可编辑资料 - - - 欢迎下载5，设有一个关键字输入序列31 ,55, 11,37,46,73, 7 ,试从空树开头构造平稳二叉排序树,画出每加入一个结点时二叉树的外形,如发生不平稳,请指出平稳调整的类型和调整结果.最终,运算在等概率情形下,查找成功的平均查找长度ASL .6，判别序列 12 ,2, 16, 3

7、0, 8, 28, 4, 10, 20, 6, 18 是否为大顶堆,假如不是,就写出将其调整为大顶堆的过程（用树形表示） .四，算法阅读题（每题 5 分,共 15 分）1， head 为不带头结点的单链表头指针,链表中结点的域有数据域data 和指针域 next,阅读下面算法,指出该算法的功能.voidfun1 Linklist &head p=head;while p.= NULL q=p; r= p->next; while r.=NULL ifr->data < q->data q=r; r= r->next;temp=q->data; q-&

8、gt;data=p->data; p->data=temp; p= p->next ;2，阅读下面算法,指出该算法的功能.voidfun2char str Stack T;int i=0;InitStackT;/初始化栈 T whilestri .=0 PushT, stri; i+;i = 0;while.StackEmptyT /判定栈 T 是否为空栈PopT, stri; i+;3，设二叉树 t 接受二叉链表储备结构,阅读下面算法,指出该算法的功能.intfun3BiTreetift=NULLreturn 0;else ift->lchild=NULL&&

9、amp;t->rchild=NULLreturn 1; elsereturn （ fun3t->lchild+algo3t->rchild） ;可编辑资料 - - - 欢迎下载五，算法设计题（共 30 分）（说明：你所设运算法中如需调用基本操作,需给出实现该基本操作的算法）1，L 为带头结点的单链表头指针且链表长度大于2,试设运算法删除链表L 的尾结点,并将该结点插入到链表 L 的首结点之前（即头结点之后） .（10 分）2，设二叉排序树 bt 以二叉链表为储备结构,试设运算法删除二叉排序树bt 中值最小的结点. （ 8 分）3，试设运算法 Create_dgalgraph

10、&g1 ,Mgraphg2,将邻接表表示的有向图g1,转换成数组表示的有向图g2.（ 12 分）可编辑资料 - - - 欢迎下载#defineINFINITYINT_MAX #defineMAX_NUM20/ 图的数组（邻接矩阵）储备表示： typedef structArcCellVRTypeadj; InfoType*info; ArcCell; typedefstructVertexTypevexsMAX_NUM ; ArcCellarcsMAX_NUM MAX_NUM; intvexnum , arcnum;MGraph;/图的邻接表储备表示： typedef structAr

11、cNodeintadjvex;struct ArcNode*nextarc;ArcNode;typedefstructVNode VertexTypedata; ArcNode*firstarc;VNode;typedefstructVNodeverticesMAX_NUM; intvexnum , arcnum;ALGraph;可编辑资料 - - - 欢迎下载B 卷 参考答案一，选择题（共 15 分,每道题 1.5 分）题号12345答案题号678910答案二，填空题（共 10 分,每道题 1 分）.5.6.三，解答题（共 30 分,每道题 5 分）1. s+=2;的语句频度是

12、 n-1-（ 1 分）t+;的语句频度是 n-1n+2/2-2分2该算法的时间复杂度是On-1n+2/2=On-2分2. 最终的循环队列如下图所示： （ 2 分）Q.rearQ.frontA6A3A4A501234队空的条件（ 1.5 分）： Q.rear 等于 Q.front队满的条件（ 1.5 分）： Q.rear+1 mod 5 等于 Q.front3. 该二叉树先序序列为CBADEGFH分2 ,对应的中序线索二叉树（不带头结点）为：（ 3 分）CNULLDNULLBAE5G可编辑资料 - - - 欢迎下载4. 无向图 G的邻接表表示如下:2分从 A 动身的深度优先搜寻序列：A,D,E,

13、B,C （ 1.5 分）,相应的深度优先搜寻生成树为：（ 1.5 分）ADEBC深度优先搜寻树 dfs5. 构造过程如下： （ 3.5 分）0-131310550-13131000+1555511116可编辑资料 - - - 欢迎下载-131+2311155LR 型-1370110460003755-24603146011-10-146RR 型31550-10003755113773073+146+131-155+100113773007ASLsucc=1/71*1+2*2+3*3+4*1=18/71.5分可编辑资料 - - - 欢迎下载6. 依据层次遍历方法写成二叉树（1 分）：12/216

14、/ 308284/1020618序列一共有 11 个值应当从 11/2处开头交换,即第5 个值 8 处开头建堆操作将该子树调整为大根堆：（4 分）1，12/216/ 3018284/1020682 ，对 30 进行操作发觉该子树已是大根堆不用调整接着对16 进行操作12/228/ 3018164/102068可编辑资料 - - - 欢迎下载3 ，对 2 进行操作4 ，对根结点 12 进行操作12/3028/ 2018164/1026830/2028/ 1218164/10268可编辑资料 - - - 欢迎下载四，算法阅读题（共 15 分,每道题 5 分）1. 用链表表示的数据的简洁选择排序,结

15、点的域为数据域data ,指针域 next .链表首指针为head ,链表无头结点. p 指向无序区第一个记录,q 指向最小值结点,一趟排序终止,p 和 q 所指结点值交换,同时向后移 p 指针.2. 字符串倒序存放.3. 求二叉树 t 中的叶子结点个数五，算法设计题（共 30 分）1. void def_l_ins_fLinklist &l-1分/删除尾结点,插入在首结点之前q = l;p = l->next; while p->nexetq->next = NULL.q/= p;删除-2p = p->next;分/p-1指向尾结点分,q 相随 -4分p-&g

16、t;next = l->next;/插入-1分l->next = p;-1分/del_l_ins_f2. Status del_minBiTree &bt-1分/删除二叉排序树bt 中值最小的结点if .bt return ERROR;/ 空树p = bt;if bt->lchild = NULL /根无左子树-2分bt = bt->rchild;p->rlchild = NULL;/此语句可不要freep;elsewhilep->lchild .= NULL/p移至最左下结点q = p;p = p->lchild;ifp->rchild .= NULL/有右子树-5分q->lchild = p->rchild;elseq->lchild = NULL;/无右子树freep;/del_min3. Status Create_dgAlgraph g1,Mgraph &g2-1分/ 将邻接表表示的有向图g1 转换成数组表示的有向图g2g2.vexnum = g1.vexnum; g2.arcnum = g1.arcnum;-1分fori=0;i<g1.vexnum;+i/生成 g2 的顶点向量-2分g2.vexsi = g1.v