数据结构试卷A

《数据结构试卷A》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东莞理工学院城市学院（本科）试卷（A卷）2013-2014学年第一学期开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场科目：数据结构班级：12软工班姓名：学号：题序一二三四五六总分得分评卷人一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写下表中。1234567891011121314151.在数据结构中，从逻辑上可以把数据结构分成（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2.一个向量首元素的

2、存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。A．110B．108C．100D．1203.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以5.将两个各有n个元素的有序表归并成一

3、个有序表，其最少的比较次数是（A）。A．nB．2n-1C．2nD．n-16.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（B）个元素。A．n-iB．n-i+1C．n-i-1D．i7.在双向链表存储结构中，删除p所指的结点时须修改指针（A）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;《数据结构》A卷第6页共6页C．p->prior->next=p;p->

4、prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;1.若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，12.对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（B）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)3.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，

5、这种排序方法称为（C）。A．归并排序B．冒泡排序C．插入排序D．选择排序4.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（C）。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.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。A．1/2B．1C．2D．46.在下列存储形式中，（B）不是树的存储形式？A．双亲表示法

6、B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法7.广义表((a,b,c,d))的表头是（C），表尾是（B）。A．aB．()C．(a,b,c,d)D．(b,c,d)8.假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（B）。A．808B．818C．1010D．1020一、填空题(每空1分，共15分)1.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为___9个，树的度为_3_。2.数据的物

7、理结构主要包括顺序结构和链式结构两种情况。3.为了能有效地应用HASH查找技术，必须解决的两个问题是构建HASH树和解决冲突问题。4.一个算法的效率可分为空间效率和时间效率。5.下面程序段的时间复杂度是n2。s=0;for(i=0;i

8、.top==m-1)printf(“overflow”);《数据结构》A卷第6页共6页else{___stack.top++;__stack.s[stack.top]=x;___}}1.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。type