数据结构期末考试试卷（A卷）.pdf

《数据结构期末考试试卷（A卷）.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试试卷（A卷）.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末考试试卷（A 卷）第一学期开课单位：软件学院，考试形式：闭、开卷，允许带 入场科目：数据结构 班 级:软件工程 姓名:学号：题序二三四五六七八九总 分得分评卷人I.基本概念部分（共6 0分）1下图所示是单链表结点的插入过程，在f e n ce结点后面插入一个值为1 0的I t m p结点，已知f e n ce-n e xt是指向f e n ce的后继结点，请把这一插入过程用代码表示出来：（6分）这一过程的代码:l t m p-n e xt =f e n ce-n e xt;f e n ce-n e xt =I t m p;2下图所示是双链表结点的删除过程，在f e n ce结点后面

2、删除一个值为23的结点，已 知f e n ce-n e xt是 指 向f e n ce的后继结点，f e n ce-pre v是指向f e n ce的前驱结点，I t m p是一个值为N UL L的链表结点指针，请把这一删除过程用代码表示出来：（8分）fence(a)fence(b)这一过程的代码:I tmp=fence-next;fence-next=ltmp-next;ltmp-next-prev=fence;3画出下图中的B ST加上值5以后的形状。（6分）4画出下图所示图的相邻矩阵表示（假设下面的表格是一个二维数组,请在表格中填入正确的数值）。（8分）12345611 020221 0

3、35331 542 051 11 051 51 135给出下图从顶点1 开始的DFS树。（8 分）621 03深度优先搜索（DFS）：从底到高，从小到大广度优先搜索（B FS）：直接在下面的顶点中画出来即可:6给出下图从顶点3开始使用P ri m （普里姆）算法时的最小支撑树（最小生成树）。（8 分）直接在下面的顶点中画出来即可:7起泡排序函数的算法如下：(8分)voi d bu bs ort(i n t A ,i n t n)i n t t m p;f or(i n t i =0;i n;i+)(f or(i n t j =i +1;j A j)t m p=A i;A i =A j;A j

4、=t m p;)外层循环,打印一下中间结果f or(i n t k =0;k n;k+)pri n t f C%d，/,A k);pri n t f(rT);)对数组i n t A =9,1 2,3,7,9 0,1 5）;应用上面的排序算法进行排序的部分中间打印结果如下，请补充使之完整:第0次外层循环的中间结果：31 2979 01 5第1 次外层循环的中间结果:371299015第2次外层循环的中间结果:379129015第3次外层循环的中间结果:379129015第4次外层循环的中间结果:379121590第5次外层循环的中间结果：379121 59 08给出从下图的最大值堆中删除最大元素

5、后得到的堆。（8分）或6 5 3 4 2 1I I.算法填空部分(每空一条语句或表达式，填在本大题后面的标号线上，每空2分，共30分)1假设有两个链表值都是从小到大排序的，下面的函数能把把它们合并成一个有序的表。合并两个有序的单链表为一个新的有序的单链表，传入参数为两个有序的单链表，返回合并后的有序表。t e m p l a t e L is t*m e r g e(L is t*1 1,L is t E l e m*1 2)H-s e t St a r t ();1 2-s e t St a r t ();L is t *1 =n e w L L is t 0;E l e m e l,e 2

6、;按顺序把两个表中的元素放入新表中w h il e (l l-g e t V a l u e(e l)&(1)/1 2-g e t V a l u e(e 2)if (e l a p p e n d(e l);l l-n e x t ();e l s e 1-a p p e n d(e 2);1 2-n e x t ();/e n d if-e l s e/e n d w h il e如果表1 1 不为空,则把剩余的元素都放入新表中w h il e (l l-g e t V a l u e(e l);/l-a p p e n d(e l)l l-n e x t ();如果表1 2 不为空,则把

7、剩余的元素都放入新表中w h il e (1 2-g e t V a l u e(e 2)1-a p p e n d(e 2);1 2-n e x t ();返回新生成的表r e t u r n 1;/L is t*l (f ji)2 回 文(p a l in d r o m e)是指一个字符串从前面读和从后面读都一样。仅使用若干栈和队列、栈 和 队 列 的 A D T 函 数 以 及 若 干 个 i n t 类型和c h a r 类型的变量，下面的算法能判断一个字符串是否为回文。算法的 返 回 结 果 为 t r u e 或 f a l s e。b o o l is P a l(c h a

8、r *b u f)声明一个空栈和一个空队列Qu e u e *q;St a c k*s;c h a r c q,c s;初始化栈和队列s =n e w ASt a c k(BU F L E N);q =n e w AQu e u e(BU F L E N);把字符串中的字符一个一个分别入栈和入队f o r(in t i =0;ip u s h(b u f i);(4);/q-e n q u e u e (b u f i )出栈出队，比较while(q-dequeue(cq)&)/s-pop(cs)if(cq!=cs)return false;)return(6);/true3下面是一个递归函数

9、search,传入参数为一棵二叉树和一个值K,如果值K出现在树中则返回true,否则返回falseotemplatebool search(BinNode*rt,int K);templatebool search(BinNode*rt,int K)if(rt 二 二 NUL L)return(7)；/falseelseif(KEComp:eq(K,rt-val0)return true;elsereturn(8)；/false(错)/search(rt-left(),K)|!search(rt-right(),K)4下面是一个递归函数smallcount,传入一棵二叉检索树和值K,返回值小于

10、或等于K的结点数目。templateint smallcount(BinNode*root,Key K);templateint smallcount(BinNode*root,Key K)if(root=NUL L)return(9)0;/falseelse i f(KEComp:11(K,root-val()return smallcount(root-left 0,K);)else r e t u r n(1 0);/smallcount(root-right(),K)(错)/I +smallcount(root-left(),K)+smalI count(root-right(),K)

11、注：返回值，如果是int型则返回0或1,如果是bool型则返回false或true5写一个算法以确定有n个顶点的无向图是否包含回路，代码已经给出，其中空位的地方需要你来补上。判断是否存在环的方法,检查所有可能的连通分量#define UNVI SI TED 0#define VI SI TED 1bool isExistRing(G raph*G)bool br=false;for(int v=0;00;v+)/vn()考虑图的所有顶点if(=UNVI SI TED)/G-getmark(v)br=br|L ookRing(G,0,-1);)return br;)/*从顶点pre开始,利用深度

12、优先搜索*在同一个连通分量类，如果找到了一个曾经被访问过的顶点*即说明此无向图存在环*/bool L ookRing(G raph*G,int v,int pre)bool br=false;(1 3)G-setmark(v,VI SI TED);设置该顶点被访问for(int w=G-f irst(v);w e();w=G-next(v,w)if(_胆_ _ _ _ _ _ _ _ =VI SI TED)/G-getmark(W)if(w!=pre)br=true;存在环 elsebr=br|I L ookRing(G,w,v);/对每一个可能边再找)return br;12-getValu

13、e(e2)l-append(el)(3)1(4)q-enqueue(buf Ei)(5)s-pop(cs)(6)true false(8)search(rt-left(),K)|search(rt-right(),K)(9)0 1+smallcount(root-left(),K)+smallcount(root-right(),K)(1 1)v n()G-getM ark(v)G-setM ark(v,VI SI TED)(1 4)G-e()G-getM ark(w)I I I.综合问题求解(共10分)1编写一个函数，以一棵树为输入，返回树的结点数目，函数原型如下：(1 0分)template int nodeCount(G TNode*rt);template int nodeCount(G TNode*rt)int n=1;if(rt=NUL L)return 0;else for(G TNode*tmp=root-leftmost_child();tmp!=NUL L;tmp=tmp-right_sibling()n+二 nodeCount(tmp);)return n;