《2007~2008学年《数据结构》B》由会员分享，可在线阅读，更多相关《2007~2008学年《数据结构》B（13页珍藏版）》请在金锄头文库上搜索。
1、名师归纳总结 精品word资料 - - - - - - - - - - - - - - -华侨高校数据结构试卷（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，就通过入出栈操作可能得到
2、的a,b,c 的不同排列个数为（）；A4B5C6D74、 由权值分别为11， 8， 6，2， 5 的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL 为（）；A24B71C48D535、已知函数Subs,i,j 的功能是返回串s 中从第 i 个字符起长度为j 的子串，函数Scopys,t的功能为复制串t到 s；如字符串S=SCIENCESTUDY，就调用函数ScopyP,SubS,1,7后得到（）；AP= SCIENCEBP= STUDYCS= SCIENCEDS= STUDY6、二维数组A47 按列优先储备方法储备在内存中，如每个元素占2 个储备单元，且数组中第一个元素的储备地址为120，就
3、元素 A34 的储备地址为（）；A139B145C158D1627、以下陈述中正确选项 ；A 二叉树是度为2 的有序树B 二叉树中结点只有一个孩子时无左右之分C 二叉树中必有度为2 的结点D 二叉树中最多只有两棵子树，并且有左右之分8、n 个顶点的无向完全图中含有向边的数目最多为；An-1BnCnn-1/2Dnn-19、假定一个链式队列的队头和队尾指针分别为front和rear，就判定队空的条件为；Afront = =rearBfront .=NULLCrear .= NULLDfront NULL10、以下排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？A直接插入排序B冒泡排序C快
4、速排序D简洁挑选排序二、填空题（每空1 分，共 10 分）1、如一个算法中的语句频度之和为Tn=3720n+4nlogn ，就算法的时间复杂度为；2、数据结构的储备结构包括次序、索引和散列等四种；1 第 1 页，共 10 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -3 、假设一个10阶的下三角矩阵A ，按行优先次序压缩储备在一维数组C 中，就C数组的大小应为 ；4、一棵高度为4 的二叉树中最少含有个结点，最多含有个结点； 一棵高度为 4 的完全二叉树中，最少含有个结点，最多含有个结点；5、在对长度为n 的关键字
5、序列进行堆排序的过程中，对堆顶元素进行堆调整的挑选运算的时间复杂度为，整个堆排序过程的时间复杂度为；6 、如对序列49 ， 38， 65， 97， 76， 13， 27， 50 采纳冒泡排序法排序，就其次趟终止后序列的状态是；三、解答题（每题5 分，共 30 分）1、指出下面算法中，带下划线的语句的语句频度，并估量该算法的时间复杂度；int funint ns=0;t=0;fori=1;i=i;j-t+;return s+t;2、设循环队列的总长度为5，入队的序列为A1 ，A2 ，A3 ，A4 ，然后 A1 ， A2 出队，最终A5 ， A6 入队，请画出最终的循环队列，并写出在循环队列中判定
6、队空和队满的条件；3、某二叉树bt 中序遍历序列为：ABCEFGHD ，后序遍历序列为：ABFHGEDC ，请构造该二叉树（画出树形），并画出对应的先序线索（不带头结点）；4、试画出如下图的无向图G 的邻接表表示，要求邻接表中的各顶点的邻接链表中的表结点按顶点序号从小到大排列； 依据你所给出的邻接表，给出从 A 动身的深度优先搜寻序列，并给出其深度优先搜寻dfs 生成树；ABCDE无向图 G2 第 2 页，共 10 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -5、设有一个关键字输入序列31 ，55， 11，37
7、，46，73， 7 ，试从空树开头构造平稳二叉排序树，画出每加入一个结点时二叉树的形状，如发生不平稳，请指出平稳调整的类型和调整结果；最终，运算在等概率情形下，查找胜利的平均查找长度ASL ；6、判别序列 12 ，2， 16， 30， 8， 28， 4， 10， 20， 6， 18 是否为大顶堆，假如不是，就写出将其调整为大顶堆的过程（用树形表示）；四、算法阅读题（每题5 分，共 15 分）1、 head 为不带头结点的单链表头指针，链表中结点的域有数据域data 和指针域next，阅读下面算法，指 出该算法的功能；voidfun1 Linklist &head p=head;while p.
8、= NULL q=p; r= p-next; while r.=NULL ifr-data data q=r; r= r-next;temp=q-data; q-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 采纳二叉链表储备结构，阅读下面算法，指出该算法的
9、功能；intfun3BiTreetift=NULLreturn 0;else ift-lchild=NULL&t-rchild=NULLreturn 1; elsereturn （ fun3t-lchild+algo3t-rchild） ;3 第 3 页，共 10 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -五、算法设计题（共30 分）（说明：你所设运算法中如需调用基本操作，需给出实现该基本操作的算法）1、L 为带头结点的单链表头指针且链表长度大于2，试设运算法删除链表L 的尾结点，并将该结点插入到链表 L 的
10、首结点之前（即头结点之后）；（10 分）2、设二叉排序树bt 以二叉链表为储备结构，试设运算法删除二叉排序树bt 中值最小的结点； （ 8 分）3、试设运算法Create_dgalgraph &g1 ，Mgraphg2，将邻接表表示的有向图g1，转换成数组表示的有向图g2；（ 12 分）#defineINFINITYINT_MAX#defineMAX_NUM20/ 图的数组（邻接矩阵）储备表示： typedef structArcCellVRTypeadj; InfoType*info; ArcCell; typedefstructVertexTypevexsMAX_NUM ; ArcCell
11、arcsMAX_NUM MAX_NUM; intvexnum , arcnum;MGraph;/图的邻接表储备表示： typedef structArcNodeintadjvex;struct ArcNode*nextarc;ArcNode;typedefstructVNode VertexTypedata; ArcNode*firstarc;VNode;typedefstructVNodeverticesMAX_NUM; intvexnum , arcnum;ALGraph;4 第 4 页，共 10 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - -
12、 - - - - - - - - -B 卷 参考答案一、挑选题（共15 分，每道题 1.5 分）题号12345答案题号678910答案二、填空题（共10 分，每道题 1 分）1.2.3.4.5.6.三、解答题（共30 分，每道题 5 分）1. s+=2;的语句频度是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 第 5 页，共 10 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - -
