数据结构模拟题1解析

1、数据结构试题1第5页数据结构试题1总共：15题，共100.0分一、单选（共8小题，24.0分）1. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素。（3分）A.8B.63.5C.63D.72. 设有一个二维数组Amn,假设A00存放位置在644（1。） ,A22 存放位置在676（1。）， 每个元素占一个空间，则 A45在（）位置，（10）表明用10进数表示。（3分）A.672（10）B.626（10）C.7O9（1o）D.724（10）3. 一个有序顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为 。（ 3分）A.128B.127C.126D.25

2、54. 含5个结点（元素值均不相同）的二叉顺序搜索法查表，平均搜索长度为 。 （ 3 分）A.54B.42C.36D.655. 在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为I i，那么搜索失败到达失败所做的数据比较次数是 。（3.0分）A.I i+1B.I i+2C.I i-1Di6. 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均控查次数不超过1.5，则歼列存储空间应容纳表项。（设搜索成功的平均搜索长度为sm=（1+1/（1- a ）/2，其中a为装填因子）A.400B.526C.624D.6767.

3、n个顶点的连通图至少有 边。（3.0分）A. n-1B.nC.n+1D.08. 一个二叉树按顺序方式存储在一个一维数组中，如图01234567891011121314A BC DEFGJ 1二、简答（共4小题，46.0分）1. 如右所示的连通图，请画出：（1）以顶点为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点2. 设有13个初始归并段，其长度分别为28,16,37,42, 5,9,13, 14,20,17,30,12,18。试画出4路归并时的最佳归并树，并计算它路径长度WPL( 12.0分)3. 设散列表HT0.12,，即表的大小为m=13采用双散列法解决冲突。散列函数和再散列

4、函数分别为：H)(Key)=Key%13注：是求余数运算(=mod)Hi =(Hi-1 +Rev(key+1)%11+1)%13i=1,2,3,m-1其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37) =37, REV=7等。若插入 的关键码序列为2,8,31,20,19,53,27，画出插入这8个关键码后的散列表。0123456789101112nnnnnnnnnnnnn时得到的结点序列4.已知一棵二叉树如左，请分别写出按前序、中序、后序和层次遍历三、计算(共1小题，10.0分)1.有一种简单的排序算法，叫做计数排序(count sorting )。这种排 序算法对一个待排序

5、的表(用数组表示)进行排序，并将排序结果放入一个新的表中。必须注意的是，表中所有待排序的关键码互不相同计数排序算法针对表中的第个记录，投其所好待排序的表一趟，统计表中多少个记录的关键码比该记录的关键小。假设针对某一个记录，统计出的计数值为C,那么，这个记录在新的有序表中的合适的存放位置即:(1) 给出适用于计数排序的数据表定义；(4分)(2) 使用C+语言编写实现计数排序的算法；(4分)(3) 对于有n个记录的表，关键码比较次数是多少？ (2分)四、其它(共2小题，20.0分)1.i nt unknown (Bin TreeNode * t) /指针t是二叉树的根指针if (t=NULL) r

6、eturn 0;elseif (t f leftChild)=NULL&&t rightChild =NULL) retur n 1;else retur n unknown (t leftChilk)+unknown(t rightChild);(10.0 分)2. 下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为X的结点不多于一个。此算法排序的非递归遍历形式。因退栈时需要区 分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志=0,进入左子树，=1,进入右子树栈ST保存结点指针ptr以及标志tag,top是栈顶指针。voi

7、d print (Bin TreeNode * t; Type &x)stack ST;i nt i,top;top=0;置空栈while (t!=NULL&&t data!=x|top!=0) /寻找值为 X 的结点while(t!=NULL&&t data!=x) ;STtop.ptr=t; / 进栈STtop.tag=0; ;if (t!=NULL&&t data=x) / 找到值为 X 的结点for (i=1;i+)cout<<STi.ptr data«e ndl;else while (top>0&a

8、mp;&STtop.tag=1) /未找到值为 X 的结点top-;if (top>0) STtop.tag=1; / 转向右子树;(1)请将缺失的语句补上(2)请给出对于右图所示的二叉树，使用上述算法搜索值为9的结点和值为10的结点的结果，以及在栈ST中的变化。(top是栈顶指针)数据结构试题1答案第4页厂77 数据结构试题1答案一单选 J f1. B 2.C 3.A 4.B 5.D 6.A 7.A 8.B二、简答1. (1)、该连通图从出做深度优先搜索，得到的深度优先生成树为：结果不唯一(6分)(2)、关节点为、(6分)2. 因为(13-1)% (4-1)=12%3=0,所以

9、不需要添加空段。最佳归并树为WPL=(5+9+13+12+16+14+17+18+28+37+20+30)*2+42=480散列表HT0.12,散列函数与再散列函数为H0(key)=key mod 13;Hi =(Hi-1 +REV(key+1) mod 11+1) mod 13;插入关键码序列为2,8,31,20,19,18,53,27H0(2)=2,比较次数为1H0(8)=8,比较次数为1H0(31)=5,比较次数为1Hd(20)=7,比较次数为1H0(19)=6,比较次数为1H0(18)=5,冲突，Hi=9,比较次数为2H0(53)=1,比较次数为1H0(27)=1,冲突，Hi=7,冲突

10、，H2=0,比较次数为3插入8个关键码后的散列表0123456789101112275323119208184.各遍历次序如下：（10分）前序：A,B,D,G,C,E,F,H （2 分）中序：D,G,B,A,E,C,H,F （3 分）后序：G,D,B,E,H,F,C,A （2 分）层次：A,B,C,D,E,F,G,H （ 3 分）三、计算1. （1）、数据表定义const int DefaultSize=100;template <class Type> class datalist;/ 数据表的前视声明template <class Type> class Eleme

11、 nt /数据表元素类的定义private:Type key; / 关键码field otherdata; / 其它数据成员public:Type getKey （）return key; /取当前结点的关键码void setKey (const Type x ) key=x; /将当前结点的关键参政修改为 xtemplate <class Type> class datalist /用顺序表来存储待排序的元素， 这些元素的类型是Typepublic:datalist (int MaxSz=DefaultSize) :MaxSize(Maxsz),Curre ntSize (0)V

12、ector =new Eleme nt <Type> MaxSz;private:Eleme nt <Type> * Vector; /存储待排序的元素的向量int MaxSize,Curre ntSize; /最大元素个数与当前元素个数、计数排序的算法(4分)template <class Type>void coun tsort (datalist <Type> &in itList,datalist <Type> & resultList) int i,j,c: Type refer;for (i=0;i<

13、 in itList.Curre ntSize;i+)c=0;refer:=i ni tList.Vectori.getKey();for (j=0;j< in itList.Curre ntSize;j+)if (in itList.Vectorj.getKey()<refer) c+;resultList.Vector0=i nitList.Vectori;resultList.Curre ntSize=i nitList.Curre ntSize;解答2template <class Type>void coun tsort <datalist<Typ

14、e>&in itList.datalist<Type >&resultList)in t *c =n ew in ti nitList.Curre ntSize;for (int i=0;i<initList.CurrentSize;i+) ci=0;for (i=0;i<i nitList.Curre ntSize-1;i+)for (i nt j=i+1;j< in itList.Curre ntSize;j+)if (in itList.Vectorj.getKey()<i nitList.Vectori.getKey()ci+;

15、else cj+;for (i=0);i <in itList.Curre ntSize;i+)resultList.Vectorci=i nitList.Vectori;resultList.Curre ntSize=i nitList.Curre ntSize;(3) 、对于n个记录的表。(2 分)解答1关键码比较次数为解答2关键码比较次数n(n-1)/2四、其它1、答案：计算二叉树的叶结点的个数2、（ 1）、 top+ t=t leftChild i<=top t=STtop.ptr rightChild搜索值为10的结点000ptr tagn0101001001010011

16、00ptr tag10001ptr tag ptr tag ptr tag1101011ptr tag011ptr tagptr tagptr tag ptr tag ptr tag搜索值为9的结点000ptr tag0100ptr tag数据结构试题2第4页数据结构试题2一、单选题判断下列各小题叙述的正误。对，在题号前的括号内填入“V”；错，在题号前 的括号内填入“X”。(每小题 3分，共24分)()(1)有n个结点的不同的二叉树有n!棵。)(2)直接选择排序是一种不稳定的排序方法。()(3)在2048个互不相同的关键码中选择最小的 5个关键码，用堆排序比用锦标赛排 序更快。()(4)当3阶

17、BJ树中有255个关键码时，其最大高度(包括失败结点层)不超过 8.()(5) 棵3阶B_树是平衡是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3 阶B_树。()(6)在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列 函数时，要求计算出的值与表的大小 m互质。()(7)在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为K的 结点有nk个，则有n0=nk+1.()(8)折半搜索只适用于有序表，包括有序的顺序表和有序的链表。二、阅读理解题：说明下面递归过程的功能(10分)int unknown (Bi nTreNode * t) /指针t是二叉树的根指针。i

18、f (t=NULL) return-1;elseif (unknown (t leftChild)>=u nknown(t rightchild)return 1+u nknown(t leftChild);else retur n 1+unknown(t rightChild);三、简答题(每小题12分，共36分)1. 设已有12个不等长的初始归并段，各归并段的长度(包括记录数)分别为RUN1(25),RUN1(12), RUN1(04), RUN1(55), RUN1(30), RUN1(47), RUN1(19), RUN1(80),RUN1(76), RUN1(92), RUN1

19、(55), RUN1(89)若采用的是4路平衡归并排序，试画出 其最佳归并树，并计算每趟归并时的读记录数。(括号内即为该归并段包含的记录数)2. 设散列表的长度m=13;散列函数为H(K)=K mod m,给定的关键码序列为19, 14, 23, 01,68, 20, 84, 27, 55, 11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概 率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度。0123456789101112搜索成功时的平均搜索长度：ASLsucc=搜索不成功时的平均搜索长度：ASLsucc=3. 画出在一个初始为空的AVL树中依次插入3,

20、 1, 4, 6, 9, 8, 5, 7时每一步插入后AVL树 的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。四、(10分)已知一级元素为(46, 25, 78, 62, 12, 37, 70, 29),试画出按元素排列次序插入生成的 一棵二叉树。五、综合算法题(10分)设有一个表头指针为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点按逆序链接。六、程序填空题下面给出的算法是建立AOV网络并对其进行拓扑排序的算法，其中有多个语句缺失。Viod Graph:TopologicalSort()Edge * p,q;i n

21、t i,j,k;for(i=0;i< n;i+)NodeTablei.adj=NULL; ；cin>>j»k; 输入有向边<j,k>while(j&&k)p=new Edge(k);/建立边结点，dest域赋为kplink=NodeTablej.adj;链入顶点j的边链表的前端;countk+;顶点k入度加一cin> >j>>k;int top=-1;for(i=0;i< n;i+)建立入度为零顶点的链栈if (cou nti=0)coun ti=top; ;for(i=0;i< n;i+)if (to

22、p=-1)cout<<"Network has a cycle"<<e ndl;retur n;else j=top;cout<<NodeTablej.data<<e ndl;q=NodeTablej.adj;while (q) k=q dest;if(-cou ntk=O)coutk=top;top=k; ;请将缺失的语句补上：（5分） 请给出对于右面AOV网络，使用上述算法进行拓扑排 序的结果，以及在count数据中建立的链式栈的变化。（top 是栈顶指针）（5分）CDABEF初始数据结构试题2答案第5页19)036DO第

23、一趟读记录数据=(4+13+19)*仁36条第二趟读记录数=(04+13+19)*2+ (25+30+47 *1=174 条30X47第三趟读记录数=(04+13+19)*3+3M)5576X809276(25+30+47)*2+(0W13(55+55+76) *1=498 条(36>25)Ci0r第四趟读记录数=(04+13+19) *4+ (25+30+47) *3+ (55+55+76) *2+ (80+89+92) =1083 条SO892、H(19)=19 mod 13=613=2冲突H(14)=14 mod 13=113=3 冲突H(23)=23 mod 13=10Hi(2)=(1+1) modH(2)=(2+1) modH3(2)=(3+1) mod数据结构试题2答案、 xVVVxVxx二、求二叉树的高度三、1、构造4路归并树的过程m=4构造4佳归并树n=12:共有12个初始归并段(n-1)/(m-1)=(12-1)/(4-1)=3 所以有3个度为4的内结点 u=(12-1) mod (4