计算机科学与技术、网络工程本科《数据结构》期末考试试卷
一、选择题（单选题，每小题3分，共33分）
1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为 。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF
2．在11个元素的有序表A[1…11]中进行折半查找（?(low?high)/2?），查找元素A[11]时，被比较的元素的下标依次是 。 A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，11
3．由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为 。
A．27 B．38 C．51 D．75
4．利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行 次元素间的比较。
A．4 B．5 C．6 D．75．循环链表的主要优点是 。 A．不再需要头指针了 B． 已知某个结点的位置后，很容易找到它的直接前驱结点
C．在进行删除后，能保证链表不断开 D． 从表中任一结点出发都能遍历整个
链表
6．已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 。
A．1．5 B．1．7 C．2．0 D．2．3
7．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 。
A．23 B．37 C．44 D．46
8．在最好和最坏情况下的时间复杂度均为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）}。对该图进行深度优先遍历，下面不能得到的序列是 。
A．aebdcf B．abedfc C．aedfcb D．acfdeb10．置换-选择排序的功能是 。 A．产生初始归并段 B．选出最大的元素 C．产生有序文件 D．置换某个记录
11．ISAM和VSAM文件属于 。
A．索引顺序文件 B．索引非顺序文件 C．顺序文件 D．散列文
件
二、填空题(1~8每空2分，9~12每空1分，共20分）
1．下面程序段的时间复杂度为 【1】 。
Sum=1; For (i=0; sum 2．稀疏矩阵快速转置算法(见第三题第1小题)的时间复杂度为 【2】 ，空间复杂度为 【3】 。 3．对广义表A=(a，(b，c，d))的运算head(rail(A))的结果是 【4】 。4．将n个数据元素依次按a1，a2，…，an的顺序压入栈中，共有【5】 种出栈序列。 5．含有4个结点的不相似的二叉树有 【6】 棵。 6．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[3][3](10)存放的位置为 【7】 。(脚注(10)表示用10进制表示) 7． 若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 【8】 。 8．给定一组关键字{49，38，65，97，76，13，27，49’}，以下用了4种不同的排序方法分别得到了第一趟排序后的结果，请指出各自对应的排序方法。（每空1分） 第一趟排序后的结果 排序方法【9】【10】【11】【12】 {27，38，13，49，76，97，65，49’}{38，49，65，97，13，76，27，49’}{49’，76，65，49，38，13，27，97}{13，65，76，97，27，38，49，49’} 三、算法填空题(每空3分,共18分） 1． 稀疏矩阵快速转置算法 //稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 12500 //非零元个数最大为12500typedef struct {int i,j; //行号,列号 ElemType e; //非零元}Triple; typedef struct {Triple data[MAXSIZE+1]; //三元组表．0号不用 int mu,nu,tu; //总行数,总列数,非零元总个数}TSMatrix; #define MAXCOL 50 status FastTransposeSMatrix(TSMatrix M,TSMatrix &T){//采用三元组表存储表示,求稀疏矩阵M的转置矩阵T． int num[MAXCOL], cpot[MAXCOL], 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) num[col]=0; for (t=1; t<=M.tu; ++t) ++num[ ① cpot[1]=1; T.data中的序号 for (col=2; col<=M.nu; ++col) 中的序号等于 ]; //求M中每一列含非零元个数 //求第col列中第一个非零元在 //后一列第一个非零元在T．data cpot[col]=cpot[col-1]+ ② 个数 ; // 前一列的序号+前一列非零元 for (p=1; p<=M.tu; ++p) {col=M.data[p].j; //M中第p行的列号域值赋给col q=cpot[col]; //M中的第col列非零元在T.data中的恰当位置赋给q T.data[q].i=M.data[p].j; //M中的第p行复制到T中的第q行 T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ③ ; 中的位置应增1 } } return OK;} 2．后序遍历二叉树非递归算法 //M中第col列下一个非零元在T．data Status PostOrderTraverse1(BiTree t,Status (*Visit)(TElemType e)) {//后序遍历二叉树T非递归算法,对每个数据元素调用函数Visit一次且仅一次. BiTree p; SqStack S; int tag; InitStack(S); do {while (t) {Push(S,t); ④ ;} p=NULL; //p指向当前结点的前一个已访问的结点 tag=1; //设置t的访问标记为已访问过 while (!StackEmpty(S)&&tag) {t=GetTop(S); //取栈顶元素 if (t->rchild==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数组值。 j模式串pNext[j]Nextval[j] 2．（6分）已知一组关键字为{21，33，12，40，68，59，25，51}，(1) 试依次插入关键字生成一棵3阶的B-树； (2) 在生成的3阶B-树中依次删除40和12，画出每一步执行后B-树的状态。 1c 2b 3c 4a 5a 6c 7b 8c 9b 10c 3．（8分）试对右图所示的AOE网络，解答下列问题。 (1) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 1 ① VeVl (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 <1, 2> e l l-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; <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6> 2 ③ 3 ② 4 ④ 5 ⑤ 6 ⑥ 试题答案及评分标准 一、选择题（单选题，每小题3分，共33分） 1B 2B 3D 4B 5D 6C 7C 8D 9A 10A 11A 二、填空题(1~8每空2分，9~12每空1分，共20分） 【1】O(n) 【2】O(tu+nu) 【3】O(nu) 【4】(b，c，d) 【5】 【6】14 11(2n)!nC2或nn?1n?1(n!)2【11】堆排序 【12】 【7】 692 【8】69 【9】快速排序 【10】二路归并排序 链式基数排序 三、算法填空题(每空3分，共18分） 1． ① M.data[t].j ② num[col-1] ③ ++cpot[col]2． ④ t=t->lchild ⑤ Visit(t->data) ⑥ !StackEmpty(S)四、解答题（共20分） 6分) (1) (2分) 3阶B-树为： l e Vl Ve 0Nextval[j](2) （4分） 17 0 ① 0<1, 2>Next[j] 0 0 1500<1, 3> 2 ③ 15 11 15 15 19<3, 2> 3 ② 19 01 27 1922<2, 4> 37 1． (6分) 模式串p 1j 151c 32 b 4 (4) 此工程最早完成时间为43。 4 ④ 29 11 19 19<2, 5> 01 38 3c 24a 删除40后B-树的状态 删除12后B-树的状态 3．(8分) 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。 (1) 每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i] 五、算法设计题（9分） 试写一算法，对单链表实现就地逆置。 5a 6c (2) 每个活动的最早开始时间e( )和最迟开始时间l( ) 0 0 8 0 12 8 0l-e 17 (3) 关键活动为：<1, 3>，<3, 2>，<2, 5>，<5, 6>；加速这些活动可使整个工程提前完成； 由所有关键活动构成的图：（关键路径为：<1, 3><3, 2><2, 5><5, 6>） 19 5 ⑤ 38 27 15<3, 5> 43 6 ⑥ 43 37 29<4, 6> 38 38<5, 6> 57 b 1 2 58c 0 3 69 b c03 4 4 10 2．(共
相关推荐：
loading