数据结构期末试题及答案

计算机科学与技术、网络工程本科数据结构期末考试试卷一、选择题（单选题，每小题3分，共33分）1已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为 。 ABCDEAF BABDCEF CDBACEF DDABECF2在11个元素的有序表A111中进行折半查找（），查找元素A11时，被比较的元素的下标依次是 。 A6，8，10，11 B6，9，10，11 C6，7，9，11 D6，8，9，113由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为 。 A27 B38 C51 D754利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行 次元素间的比较。 A4 B5 C6 D75循环链表的主要优点是 。 A不再需要头指针了 B 已知某个结点的位置后，很容易找到它的直接前驱结点C在进行删除后，能保证链表不断开 D 从表中任一结点出发都能遍历整个链表6已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A06中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 。 A15 B17 C20 D237由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 。 A23 B37 C44 D468在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是 。 A基数排序 B快速排序 C堆排序 D归并排序9无向图G=(V，E)，其中V=a，b，c，d，e，f，E=(a，b)，（a，e），(a，c)，（b，e），（c，f），(f，d)，（e，d）。对该图进行深度优先遍历，下面不能得到的序列是 。 Aaebdcf Babedfc Caedfcb Dacfdeb10置换-选择排序的功能是 。 A产生初始归并段 B选出最大的元素 C产生有序文件 D置换某个记录 11ISAM和VSAM文件属于 。A索引顺序文件 B索引非顺序文件 C顺序文件 D散列文件二、填空题(18每空2分，912每空1分，共20分）1下面程序段的时间复杂度为 【1】 。Sum=1; For (i=0; sumn; i+) sum+=i;2稀疏矩阵快速转置算法(见第三题第1小题)的时间复杂度为 【2】 ，空间复杂度为 【3】 。3对广义表A=(a，(b，c，d)的运算head(rail(A)的结果是 【4】 。4将n个数据元素依次按a1，a2，an的顺序压入栈中，共有【5】 种出栈序列。5含有4个结点的不相似的二叉树有 【6】 棵。6设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，则A33(10)存放的位置为 【7】 。(脚注(10)表示用10进制表示)7 若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 【8】 。8给定一组关键字49，38，65，97，76，13，27，49，以下用了4种不同的排序方法分别得到了第一趟排序后的结果，请指出各自对应的排序方法。（每空1分） 第一趟排序后的结果排序方法27，38，13，49，76，97，65，49【9】38，49，65，97，13，76，27，49【10】49，76，65，49，38，13，27，97【11】13，65，76，97，27，38，49，49【12】三、算法填空题(每空3分,共18分）1 稀疏矩阵快速转置算法/稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 12500 /非零元个数最大为12500typedef struct int i,j; /行号,列号 ElemType e; /非零元Triple;typedef struct Triple dataMAXSIZE+1; /三元组表0号不用 int mu,nu,tu; /总行数,总列数,非零元总个数TSMatrix;#define MAXCOL 50status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)/采用三元组表存储表示,求稀疏矩阵M的转置矩阵T int numMAXCOL, cpotMAXCOL, col, t, p, q; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol=0; for (t=1; t=M.tu; +t) +num ; /求M中每一列含非零元个数 cpot1=1; /求第col列中第一个非零元在T.data中的序号 for (col=2; col=M.nu; +col) /后一列第一个非零元在Tdata中的序号等于cpotcol=cpotcol-1+ ; / 前一列的序号+前一列非零元个数 for (p=1; prchild=p) /右子树不存在或已被访问,访问之 ; /访问根结点Pop(S,p); /退栈 p=t; /p指向已被访问的结点else t=t-rchild; /t指向右子树tag=0; /设置未被访问的标记 while( ); return OK;四、解答题（共20分）1（6分）已知模式串p=cbcaacbcbc，求出p的next数组值和nextval数组值。j12345678910模式串pcbcaacbcbcNextjNextvalj2（6分）已知一组关键字为21，33，12，40，68，59，25，51，(1) 试依次插入关键字生成一棵3阶的B-树；(2) 在生成的3阶B-树中依次删除40和12，画出每一步执行后B-树的状态。3（8分）试对右图所示的AOE网络，解答下列问题。 (1) 求每个事件的最早开始时间Vei和最迟开始时间Vli。1 2 3 4 5 6 VeVl (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 e ll-e (3) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。(4) 这个工程最早可能在什么时间结束。五、算法设计题（9分）完成以下算法，对单链表实现就地逆置。void LinkList_reverse(Linklist &L)/链表的就地逆置;为简化算法,假设表长大于2 Linklist p,q,s; p=L-next; q=p-next; s=q-next; p-next=NULL;试题答案及评分标准一、选择题（单选题，每小题3分，共33分）1234567891011BBDBDCCDAAA二、填空题(18每空2分，912每空1分，共20分）【1】【2】【3】【4】【5】【6】O()O(tu+nu)O(nu)(b，c，d)14【7】【8】【9】【10】【11】【12】69269快速排序二路归并排序堆排序链式基数排序三、算法填空题(每空3分，共18分）1 M.datat.j numcol-1 +cpotcol2 t=t-lchild Visit(t-data) !StackEmpty(S)四、解答题（共20分）1 (6分)j12345678910模式串pcbcaacbcbcNextj0112112343Nextvalj01021010402(共6分) (1) (2分) 3阶B-树为：(2) （4分） 删除40后B-树的状态 删除12后B-树的状态3(8分) 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。(1) 每个事件的最早开始时间Vei和最迟开始时间Vli 2 3 4 5 6 Ve 0 15 19 29 38 43 Vl 0 15 19 37 38 43 (2) 每个活动的最早开始时间e( )和最迟开始时间l( ) e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0(3) 关键活动为：，；加速这些活动可使整个工程提前完成；由所有关键活动构成的图：（关键路径为：） 13265154195 (4) 此工程最早完成时间为43。五、算法设计题（9分） 试写一算法，对单链表实现就地逆置。void LinkList_reverse(Linklist &L)/链表的就地逆置;为简化算法,假设表长大于2 Linklist p,q,s;p=L-next; q=p-next; s=q-next; p-next=NULL;解：while (s-next) q-next=p; p=q; q=s; s=s-next; /把L的元素逐个插入新表表头 q-next=p; s-next=q; L-next=s;/LinkList_reverse分析：本算法的思想是,逐个地把L的当前元素q插入新的链表头部，p为新表表头。