《《数据结构》模拟自测题2.docx》由会员分享，可在线阅读，更多相关《《数据结构》模拟自测题2.docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构模拟自测题2一、单项选择题 （每题2分，共30分）1 .从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构.在n个结点的顺序表中，算法的时间复杂度是0 （1）的操作是：（）A.访问第i个结点（IWiWn）和求第i个结点的直接前驱（2WiWn）B.在第i个结点后插入一个新结点（IWiWn）C.删除第i个结点（IWiWn）D.将n个结点从小到大排序3 .链接存储的存储结构所占存储空间：（）A分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针B只有一局部，存放结点值C只有一局部，存储表示结点间关系的
2、指针D分两局部，一局部存放结点值，另一局部存放结点所占单元数s-next=p-next;p-next=s; p-next=s-next;p-next=s;s-next=p-next;p-next=s; p-next=s-next;p-next=s;4 .在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A. p-next=s;s-next=p-next; B.C. p-next=s;p-next=s-next; D.5 .设栈的输入序列是1, 2, 3, 4,那么()不可能是其出栈序列。A.1,2, 4,3,B.2, 1, 3, 4,C. 1, 4, 3, 2,D.4,3, 1
3、,2,E.3, 2, 1, 4,)o)o6 .循环队列存储在数组A0.ni中，那么入队时的操作为（A. rear=rear+lC. rear=(rear+1) mod mA. rear=rear+lD. rear=(rear+1) mod mB. rear=(rear+l) mod (m-1)E. rear=(rear+1) mod (m+1)8.串 ababaaababaa,A.C.的next的函数值为（B.D. 5)o.假设一个栈的入栈序列是1, 2, 3,，n,其输出序列为pl, p2, p3,，pn,假设pl=n,那么pi为()D.不确定D.不确定A. i B. n=i C. n-i+
4、1.假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是（）A. 9 B. 11 C. 15 D.不确定.高度为k的二叉树最大的结点数为（ ）oA. 2kB. 2k-1C. 2-1D. 2k-1-l.遥远山区的N个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以 归结为什么问题()A最短路径 B关键路径 C拓扑排序 D最小生成树.当一个有n个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是()。tjnnnE之 AIM之 A 亿力川A. /=IB. J=1C.D. i= J=19 .设广义表L=(a,b,c),那么L的长度和深度分别为( )oA. 1 和 2
5、B. 1 和 3A. 1 和 2B. 1 和 3C. 1 和 1D. 2 和 3.折半查找法查找一个长为10的，排好序的线性表，当查找不成功时，最多需要比拟多少 次()A 5 B 2 C 4 D 1. 一组记录的关键码为(46, 79, 56, 38, 40, 84),那么利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为()oA. (40, 38, 46, 56, 79, 84)B. (40, 38, 46, 79, 56, 84)C. (38, 40, 46, 56, 79, 84)D. (40, 38, 46, 84, 56, 79)二、填空(每空1分，共16分)1 .对于给定
6、的n个元素，可以构造出的逻辑结构有,四种。2 .顺序存储结构是通过 表示元素之间的关系的;链式存储结构是通过表示元素之间的关系的。3 .具有n个结点的二叉树，采用二叉链表存储，共有 个空指针域。4 .完全二叉树中，结点个数为n,那么编号最大的非终端结点的编号为。5 .对于一个具有n个顶点e条边的无向图的邻接表的表示，那么表头向量大小为,邻 接表的边结点个数为 o.设一棵完全二叉树具有1000个结点，那么此完全二叉树有一个叶子结点，有 个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。6 .在堆排序和快速排序中，假设初始记录接近正序或反序，那么选用；假设初始记录基本无序，那么最好选
7、用 O三、判断题：对打；错打“义”，并说明理由。(每题1分，共10分).顺序存储结构的主要缺点是不利于插入或删除操作。（）1 .线性表的长度是线性表所占用的存储空间的大小。（）.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）2 .完全二叉树中，假设一个结点没有左孩子，那么它必是树叶。（）.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）3 .折半查找与二叉排序树的时间性能有时不相同。（）十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。（）8 .在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列，那么需要
8、 采用“大根堆”。（）.图G的拓扑序列唯一，那么其弧数必为nT （其中n为顶点数）。（）9 .散列表的装填因子a越小，发生冲突的可能性就越小。（）四、算法设计题：（共20分）Q是一个非空队列，S是一个空栈。仅用如下给定的队列和栈的ADT函数和尽量少 的工作变量，使用C或C+语言编写一个算法，将队列Q中的所有元素逆置。 栈的ADT函数有：void MakeEmpty （Stack &S） 置空栈bool Push （Stack &S, DataType e）新元素e进栈，入栈成功返回TRUE,否那么返回FALSEDataType Pop （Stack &S ）出栈，返回栈顶值，否那么返回空值bo
9、olisSEmpty （Stack S） 判栈空否，假设空返回TRUE,否那么返回FALSE 队列的ADT函数有：bool EnQueue （Queue &Q, DataType e）元素e进队，入队成功返回TRUE,否那么返回FALSE DataType DeQueue （Queue &Q）出队列，假设队列非空返回队头值，否那么返回空值bool isQEmpty （ Queue Q ）.判队列空否。假设空返回TRUE,否那么返回五、设散列表的长度m=13；散列函数为H （Key）=Key MOD m,给定的关键码序列为19, 14, 23, 01, 68, 20, 84, 27, 55, 1
10、1,试画出用线性探查法（Hi=（H（Key）+di）MOD m, i=l,2,k（kinT）解决冲突时所构造的散列表。并求出在等概率的情况下，这种方 法的搜索成功时的平均搜索长度。（构造出散列表15分，求出其搜索成功时的平均搜索长度15分，共计30分）以下是本试卷的参考答案：一、单项选择题（每题2分，共30分）1.C2. A3. A4. B5.D6.D7.C8.D9.B10. C11.B12. B13. A14. A15. A二、填空题（每空1分，共16分）1. 线性结构，树型结构，图状结构，集合2. 物理位置上相邻，结点的指针3. n+14. Ln/2j5. n, 2e6. 500, 499
11、, 1, 07. .堆排序快速排序三、判断题（每题1分，共10分）1. J2. X3. X-1. V5. V6. V7. X8. V9. X10. V四、算法设计题：（共20分）参考算法：void Invert ( Queue &Q) MakeEmpty (S) ; / II while( ! isQEmpty( Q ) e= DeQueue(Q);Push (S, e); / MakeEmpty (S) ; / II while( ! isQEmpty( Q ) e= DeQueue(Q);Push (S, e); /while( ! isSEmpty( S )II e= Pop( S );
12、IIEnQueue (Q, e);II /return ;五、23,01, 68,20, 84, 27, 55, 11,那么有11(19)H(01)H(84)H(27)11(55)06,1,6,1,3,114成功; 冲突, 冲突,11(14)二L成功;冲突，二冲突，二2012,7,2,4,368成功;冲突,冲突，二冲突，二4278,3,5,5H（68）成功;冲突,H(23)3,成功；4,成功;成功；h(ll)= 11,67855192084二10,成功;H(20)7,成功;成功。91011122311（构造出散列表15分，求出其搜索成功时的平均搜索长度15分，共计30分）设散列表的长度m设散列表的长度m13；散列函数为H （K）=K mod m,给定的关键码序列为19, 14,(1) (1)(1)(2)(1)(4)(3)(1)(1)在等概率的情况下，搜索成功时的平均搜索长度ASLsucc =（1+2 + 1+ 4 + 3 + 1 + 1+ 3 + 1 + 1）/10=18 / 10=1. 8