烟台大学数据结构试题2009~2010年度

《烟台大学数据结构试题2009~2010年度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生姓名__________学号_________________院系___________班级___________-------------------------------密------------------------------封----------------------------线---------------------------------烟台大学2009～2010学年第二学期数据结构试卷A（考试时间为120分钟）题号一二三四总分得分阅卷人合分人（注：第三大题答案请写在后面的空白答题纸上）一、选择题(每小题2分，共20分)1.

2、以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是()A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条"锁链"C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接2.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()A、n-i+1B、n-iC、iD、i-

3、14.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表ABCDEF图15.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A、edcbaB、decbaC、dceabD、abcde6.已知图1如右所示，若从顶点A出发按深度优先搜索进行遍历，则可能得到的顶点序列为（）A、A，B，E，C，D，FB、A，C，F，E，B，DC、A，E，B，C，F，DD、A，E，D，F，C，B7.n个顶点的有向图中含有向边的数目最多为()A、n-1B、nC、n(n-1)

4、/2D、n(n-1)8.若一个栈的输入顺序是1，2，…，n，输出序列的第一个元素是n，则第i（1≤i≤n）个输出元素是（）12345图2A、n-iB、n-i-1C、i+1D、n-i+19.已给图2，（）是该图的正确的拓扑排序序列A、1，2，3，4，5B、1，3，2，4，5C、1，2，4，3，5D、1，2，3，5，410.为查找某一特定单词在文本中出现的位置，可应用的串运算是()A、插入B、删除C、串联接D、子串定位二、填空题(每小题2分，共30分)1.存储结构是逻辑结构的__________实现。2.若一个算法中的语句频度之和为T(n)=n+4nlog

5、n，则算法的时间复杂度为________。3.数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是。4.在无向图的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于________。5.对带有头结点的链队列lq，判定队列中只有一个数据元素的条件是___________。5.设数组data[0..m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为。6.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e

6、4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4,e6,e2,e1,则栈S的容量至少应该是。7.设有顺序栈s[0..m-1]，若栈底设在下标最大的一端，则栈满的条件是（设栈顶指针为top，指向栈顶元素的位置）。8.有一个10阶对称矩阵A，采用压缩存储方式，以行序为主序存储，A[1,1]为第一元素，其存储地址为1，每个元素占一个地址空间，则A[7,5]的地址为。9.在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找，查找元素11，需进行次元素之间的比较。10.深度为h的完全二叉树

7、至少有_________个结点。11.在对一组记录（18，6，27，12，52，15，47，29）进行直接插入排序时，当把第6个记录15插入到有序表时，为寻找插入位置需比较次。12.在直接插入排序和快速排序中，若初始数据基本有序，则选用_________；在冒泡排序和堆排序中，若要求数据的稳定性，则选用_________。13.广义表运算式TAIL(((a,b)，(c,d)))的运算结果为。14.一组记录的关键字为(42,59,36,28,10,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。三．应用题（每小题5分，共35分）11

8、．设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均