数据结构模拟试卷(一)参考答案

《数据结构模拟试卷(一)参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构模拟试卷(一)参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用(A)方法最快。A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（　B　　）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　C　　）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可

2、以穿插进行，则可能出现的出栈序列为（　D　　）A．3，2，6，1，4，5B．5，6，4，2，3，1C．1，2，5，3，4，6D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（　A　　）A．15B．16C．17D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（　B　）。A.108　　　B.112　　　C.116　　D.1207．从一个具有

3、n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（　C　　）个结点。A.nB.n/2C.(n+1)/2D.(n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（　D　　）A．不一定相同B．互为逆序C．都不相同D．都相同9．高度为5的二叉树至多有结点数为（　A　　）A.63B.32C.24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　B　　）A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通

4、分量的数目11．图的邻接矩阵表示法适用于表示（　C　　）A．无向图B．有向图C．稠密图D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（　D　）。　　　A.s->next=p;p->next=sB.p-next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->next;p->next=s第5页共5页13．下列排序算法中，其时间复杂度和记录的初始排列无关的是（　A　　）A．直接选择排序B．插入排序C．快速排序

5、D．冒泡排序14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（　B　　）A．f,d,bB．f,c,bC．g,c,bD．g,d,b15．如下图所示的4棵二叉树中，（　C　　）不是完全二叉树。ABCD一．填空题（本大题共15小题，每小题2分，共30分）1.在数据结构中，数据的逻辑结构分线性结构和非线性结构。2.称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___f(n)____的数量级相同。3.在一个长度

6、为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_____O(n)____。4.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__10____。5.对于栈只能在___栈顶_____插入和删除元素。6.通常从正确性、____可使用性___、可读性、效率和健壮性等5个方面评价算法（包括程序）的质量。7.在具有n个单元的循环队列中，队满时共有　n-1　　　　个元素。8.若对关键字序列（43，02，80，48，26，57，15，73，21，

7、24，66）进行一趟增量为3的希尔排序，则得到的结果为(15,02,21,24,26,57,43,66,80,48,73)。9.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为稠密索引，若对应数据对象表中的若干个表项，则称此索引为稀疏索引。10.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为89　　　　。11.广义表A((a，b，c)，(d，e，f))的表尾为（(d，e，f)）。12.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果

8、6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为3。13.根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二叉搜索树)时，当插人到值为50的结点时需要进行旋转调整。14.n（n＞0）个顶点的无向图最多有n(n-1)／2条边。15.设无向图的邻接表如下图所示，则该图的边的数目是5。第5页共5页一．判断题(本大题共10小题，每小题1分，共10分)1.（×）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻