安阳工学院软件工程专业2015-2016学年数据结构检测题

1、安阳工学院软件工程专业2015-2016学年数据结构检测题1.树型结构是数据元素之间存在一种： （） 单选题A、一对多关系(正确答案)B、多对多关系C、多对一关系D、一对一关系2.数据结构被形式化定义为( K,R)，其中K是数据元素的有限集合，R是K上的（）有限集合。 单选题A、 操作B、映像C、存储D、关系(正确答案)3.数据在计算机存储内表示时，物理地址与逻辑地址不相同，称之为（） 单选题A、 存储结构B、逻辑结构C、链式存储结构(正确答案)D、顺序存储结构4.数据结构中，与所使用的计算机无关的是数据（）的结构； 单选题A、 存储B、物理C、逻辑(正确答案)D、物理和存储5.计算机算法指的

2、是（） 单选题A、 计算方法B、调度方法C、解决问题的有穷指令序列(正确答案)D、处理问题的任何程序6.算法分析的目的是： ( ) 单选题A、 找出数据结构的合理性B、 研究算法中的输入和输出的关系C、分析算法的效率以求改进(正确答案)D、分析算法的易懂性和文档性7.算法分析的两个主要方面是： （） 单选题A、 空间复杂性和时间复杂性(正确答案)B、 正确性和简明性C、 可读性和文档性D、数据复杂性和程序复杂性8.下面关于线性表的叙述错误的是（）。 单选题A、 线性表采用顺序存储必须占用一片连续的存储空间B、 线性表采用链式存储不必占用一片连续的存储空间C、 线性表采用链式存储便于插入和删除操

3、作的实现D、 线性表采用顺序存储便于插入和删除操作的实现(正确答案)9.数据在计算机内有顺序和链式存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（） 单选题A、 低B、高(正确答案)C、相同D、不好说10.下面程序的时间复杂度为( )int i=1 1while(i=n) n+1i=i*2 log2n+？ 单选题O(n)O(logn)(正确答案)O(n)O(n)11.下面程序的时间复杂度为( )for（i=1，s=0； i=n； i+）t=1；for(j=1；jnext；p-data=r-data；p-next=r-next；free(r)；B、r=p-next；r-data=p-d

4、ata；p-next=r-next；free(r)；C、r=p-next；p-next=r-next；free(r)；(正确答案)D、r=p-next；p-data=r-data；free(r)；19.在一个单链表中，已知指针s指向待插入的其值为x的新结点A，若将结点A插入到单链表指针变量p之后，则需要修改的操作序列为() )。 单选题A、s=p-next；p-data=s-data；p-next=s-next；free(s)；B、s=p-next；s-data=p-data；p-next=r-next；C、s-data=x；s-next=p-next；p-next=s；(正确答案)D、p-n

5、ext=s；s-next=p-next； s-data=x;20.单链表中，增加一个头结点的目的是为了（） 单选题A、 使单链表至少有一个结点B、标示表结点中首结点位置C、 方便运算实现(正确答案)D、 说明单链表是线性表的链式存储21.数据的最小单位是（）。 单选题A、 数据项(正确答案)B、 数据类型C、 数据元素D、 数据变量22.设一条单链表的头指针变量为head且有头结点，则其判空条件是（）。 单选题A、 head= NULLB、 head-next= NULL(正确答案)C、 head-next=headD、 head!= NULL23.非空循环链表head的尾结点(由p指针所指)

6、满足（）。 单选题A、p-next= NULLB、 p= NULLC、p-next=head(正确答案)D、 p=head24.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 单选题A、 front-next=s；front=s；B、 s-next=rear；rear=s；C、 rear-next=s；rear=s；(正确答案)D、 s-next=front；front=s；25.设指针变量top指向当前顺序栈的栈顶，则删除栈顶元素的操作序列为（）。 单选题A、 top=top+1;B、 top=

7、top-1;(正确答案)C、 top-next=top;D、 top=top-next;26.栈中元素的进出原则是 （） 单选题A、先进先出B、后进先出(正确答案)C、栈空则进D、栈满则出27.若已知一个栈的入栈序列是1，2，3，n，再依次输出序列为p1，p2，p3，pn，而且中途没有入栈元素。若p1=n，则pi为 （） 单选题A、IB、n=iC、n-i+1(正确答案)D、不确定28. 根据二叉树定义，具有三个不同数据结点的不同的二叉树有（）种。 单选题A、3B、5(正确答案)C、4D、61.数据元素是数据的基本单位，_是数据表示中最小的单位。 填空题_(答案：数据项)2.数据结构是一门研究非

8、数值计算的程序设计问题中计算机的_以及它们之间的_和运算等的学科。 填空题_(答案：操作对象 关系)3.数据结构被形式地定义为(D, R)，其中D是_的有限集合，R是D上的 _有限集合。 填空题_(答案：数据元素 关系)4.数据结构包括数据的_、数据的_ 和数据的_这三个方面的内容。 填空题_(答案：逻辑结构 存储结构 运算)5.在线性结构中，第一个节点_前趋节点，其余每个节点有且只有1个前趋节点。 填空题_(答案：无)6.数据结构按逻辑结构可分为两大类，它们分别是_和 _。 填空题_(答案：线性结构 非线性结构)7.数据的存储结构可以用4种基本的存储方法表示，分别是_、_、_ 、_ 。 填空

9、题_(答案：顺序 链式 索引 散列)8.顺序存储结构是把逻辑上相邻的结点存储在物理上_的存储单元里，结点之间的逻辑关系由存储单元位置的相邻关系来体现。 填空题_(答案：连续)9.链式存储结构是把逻辑上相邻的结点存储在物理上 _的存储单元里，结点之间的逻辑关系由附加的指针域来体现。 填空题_(答案：任意)10.向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动_个元素。 填空题_(答案：n-i+1)11.在顺序表中访问任意一结点的时间复杂度均为_，因此，顺序表也称为随机存取的数据结构。 填空题_(答案：O(1)12.数据的物理结构主要包括_和_两种情况。 填空题_(答

10、案：顺序存储结构 链式存储结构)13.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_表。 填空题_(答案：FILO FIFO)14.向量(顺序表)、栈和队列都是_结构，可以在向量的任何位置插入和删除元素；对于栈只能在_ 插入和删除元素；对于队列只能在_插入和_删除元素。 填空题_(答案：线性 栈顶 队尾 队首)15.在具有n个单元的循环队列中，队满时共有_个元素。 填空题_(答案：n-1)16.深度为k的完全二叉树至少有_个节点，至多有_个节点。若按自上而下、从左到右的次序给

11、节点编号(从1开始)，则编号最小的叶子节点的编号是_。 填空题_(答案：2k-1 2k-1 2k-1)17.在一棵二叉树中，度为0的节点的个数为n0,度为2的节点个数为n2，则有n0=_ 填空题_(答案：n2+1)18.在一棵具有n个节点的完全二叉树中，如果按照自上而下、从左到右的次序给节点编号(从1开始)，对于任意非根节点i(1in)，可以推断出它的双亲节点是_，如果2in，则节点i无左孩子(节点i为叶子节点)，否则i的左孩子节点为_，如果2i+1n，则节点i无右孩子，否则i的右孩子节点为_。 填空题_(答案：i/2 2i 2i+1)1.链表的每个结点中都恰好包含一个指针。 判断题对错(正确

12、答案)2.链表的物理存储结构具有同链表一样的顺序。 判断题对错(正确答案)3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 判断题对错(正确答案)4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 判断题对错(正确答案)5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 判断题对错(正确答案)6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 判断题对错(正确答案)7.线性表在物理存储空间中也一定是连续的。 判断题对错(正确答案)8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 判

13、断题对错(正确答案)9.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 判断题对错(正确答案)10.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。 判断题对(正确答案)错11.顺序表查找指的是在顺序存储结构上进行查找。 判断题对错(正确答案)12.在表结构中最常用的是线性表，栈和队列不太常用。 判断题对错(正确答案)13.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 判断题对(正确答案)错14.栈和链表是两种不同的数据结构。 判断题对错(正确答案)15.栈和队列是一种非线性数据结构。 判断题对错(正确答案)16.对于不同的使用者，一个表结构既可以是栈，也可以是队列， 判断题对(正确答案)错