数据结构专升本模拟题及参考答案.doc

《数据结构专升本模拟题及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业题（一）一、单项选择题1.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1)B．O(n)C．O(n²)D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继

2、修改（）个指针域的值。A．2B．3C．4D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。A．98B．100C．102D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。A．s-〉top!=0B．s-〉top==0C．s-〉top!=m0D．s-〉top==m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front8

3、、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。A．连接B．求子串C．模式匹配D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF10、数组常用的两种基本操作是（）。A．建立与查找B．删除与查找C．插入与索引D．查找与修改二、填空题1.

4、所谓稀疏矩阵指的是________且分布没有规律。2.队列是________的线性表，其运算遵循________的原则。3.空格串是________________________________。4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为　　　，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为　　　，图的深度或广度优先搜索遍历时的空间复杂度均为　　　。6、一个图的　　　　表示法是唯一的，而　　　表示法是不唯一的。三、算法设二叉树采用

5、二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）20A39D4FCB81E65G23、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长

6、度与查找不成功的平均查找长度。（设等概率情况）4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？作业题（二）、单项选择题1.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341562.栈和队都是（）A．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构3、顺序查找法适合于存储结构为（）的线形表。A．散列存储B．顺序存储或链接存储C．压缩存储D．索引存储4、分别以下列序列构造二叉排序树，与用其

7、它三个序列所构造的结果不同的是()。A．（100，80，90，60，120，110，130）B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130）D．(100，80，60，90，120，130，110)5、折半查找的平均比较次数为（）。A．nB．n/2C．log2nD．log2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A．必定快B．不一定C．在大部分情况下要快D．取决于表递增还是递减7、