淮阴工学院数据结构期末试卷A

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

1、淮阴工学院课程考试试卷班级姓名学号----------------------------装--------------------------订----------------------线-----------------------------专业：通信工程课程名称：数据结构学分：3.5试卷编号（A）课程编号：1311050考试方式：闭卷考试时间：100分钟拟卷人(签字)：拟卷日期：2006,12,25审核人(签字)：得分统计表：题号一二三四五六七八九十总分得分得分阅卷人一、填空题：（每空1分

2、，共10分）1.数据的存储结构种类包括　①。2.分析以下部分代码的时间复杂度用大O表示法为②。inti=1;s=0;while(i<=n){s+=i;i=i*2;}3.栈是一种③的特殊的线性表。4.线性表的顺序存储结构是一种④存取方式。5.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度⑤的次序来得到最短路径的。6.设一棵完全二叉树有100个结点，则共有⑥50个叶子结点。7.将一个长度为50的顺序表的第30个元素删除时，需前移⑦20个元素。8.设数组a[0…8,0…9]的起始地址

3、为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[4,6]的存储地址为　　　⑧　1000+8*2*5+6*2=1092　　。9.排序方法的稳定性是指⑨。10.对有序顺序表（3，8，10，25，29，45，55，77，85，99）采用折半查找，若查找表中元素10，它将依次与表中元素⑩比较大小。得分阅卷人二、选择题：（每题1分，共20分）1.数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的和运算的学科。A.关系B.算法C.运算D.数据2.算法分析的目的是。A.

4、找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性3.线性表的顺序存储结构是一种结构。A.随机存取B.顺序存取C.索引存取D.HASH存取4.顺序表和链表均适用于查找。A．随机B．二分法C．顺序，也能二分法D．顺序5.在一个有向图中，所有顶点的入度之和等于边的条数的倍。A．1／2B．lC．2D．46.一组记录的关键字为{18，1，3，8，9，29}，则利用堆排序的方法建立的初始堆(大顶堆)为。A．29，18，9，3，8，1B．29，9，18，8

5、，1，3C．29，9，18，8，3，1D．29，18，9，8，3，17.若在线性表中采用折半查找法查找元素，该线性表应该。A．元素按值有序B．元素按值有序，且采用链式存储结构C．采用顺序存储结构D．元素按值有序，且采用顺序存储结构8.二叉树是非线性数据结构，所以。A.它不能用顺序存储结构存储;B.顺序存储结构和链式存储结构都能存储;C.它不能用链式存储结构存储;D.顺序存储结构和链式存储结构都不能使用9.下述几种排序方法中，平均性能最差的是Ａ.希尔排序Ｂ.快速排序Ｃ.归并排序Ｄ.简单选择排序10.在

6、进行顺序栈入栈运算时，应先判别栈是否。A.空B.满C.上溢D.下溢11.一个队列的入队序列是a，b，c，d，则队列的输出序列是。A.d，c，b，aB.a，b，c，dC.a，d，c，bD.c，b，a，d12.一维数组的第一个元素的存储地址是1000，每个元素的长度为2，则第5个元素的地址是1000+2*4A.1010B.1008C.1000D.102013、快速排序是排序方法中的一种。Ａ.插入Ｂ.选择Ｃ.交换Ｄ.归并14、将递归算法转换成对应的非递归算法时，通常需要借助结构实现。A.树B.队列C.链表

7、D.栈15、图是一种的结构。A.一一对应关系B.一对多关系C.无序关系D.多对多关系16．把一棵树转换为二叉树后，这棵二叉树的形态是。第2页共2页淮阴工学院课程考试试卷班级姓名学号----------------------------装--------------------------订----------------------线-----------------------------A.有多种B.有多种，但根结点都没有左孩子C.唯一的D.有多种，但根结点都没有右孩子17．在完全二叉树中，若

8、一个结点没有，则它必定是叶结点。A．右孩子结点B．左孩子结点C．左子结点或者没有右子结点D．兄弟结点18．在单链表中，指针p指向链表某结点，现将指针s所指结点插到p所指结点之后，则其实现语句应为A．p->next=s；s->next=p->next；B．s→next=p→next；p→next=s；C．s→next=p→next；p→next=s→next；D．s->next=p+1；p->next=s；19．对于图1的有向图，以下是正确的拓扑排序序列。A．1，2，3