数据结构测试题1

一、选择题:
1．若长度为n的钱性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动(         )个数据元素。(  C  )
A .n-i   B.n+i     C.n-i-1     D.n-i+1
2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行__。(  B  )
A. q->next=p; s->next=p
B. s->next=p;q->next=s;
C. p->next=s; s->next=q
D. s->next=q; q->next=p;
3.某堆栈的输入序列为a,b,c,d,下面的四个序列中，_____不可能是它的输出序列。(  C  )
A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a
4．在一棵树中，（   C   ）没有前驱结点。
A.分支结点   B.叶结点    C.树根结点    D.空结点
5.一棵深度为8(根的层次号为1）的满二叉树共有_个结点。(   B  )
A. 256    B.255    c. 128      D.127
6.下面二叉树的中序遍历序列为__(   A  )

A.ACBDFHEMG      B. FCADBEHGM
C,ABDCHMGEF      D. ABCDEFGHM

7.队列通常采用两种存储结构是(   A  )
A.顺序存储结构和链表存储结构      B.散列方式和索引方式
C.链表存储结构和数组        D.线性存储结构和非线性存储结构
8.算法分析的目的是(  C  )
A.找出数据结构的合理性     B.研究算法中的输入/输出关系
C.分析算法的以求改进      D.分析算法的易读性
9.在需要经常查找结点的前驱与后继的场合中，使用(  B  )比较合适.
A.单链表     B.双链表
C.顺序表     D.循环链表
10、带头结点的单链表head为空的判断条件是(  B   )
A.head=NULL          B.head->next == NULL
C.head->next==head      D.head != NULL
11、对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是(  C  ) 
A、O(1)     B、O(n)      C、O(n2)       D、O(nlog2n)
12、使用双链表存储线性表，其优点是可以(  C  ) 
A、节约存储空间         B、提高检索速度
C、更方便数据的插入和删除       D、很快回收存储空间
13、设线性表有n个元素，以下操作中，( )在顺序表上实现比在链表上
实现的效率更高。
A、输出第i(1≤i≤n)个元素值        B、交换第1个和第2个元素的值
C、顺序输出所有n个元素             D、查找与给定值x相等的元素在线性表中的序号
14、讨论树、森林和二叉树的关系，目的是为了(  B  ) 
A、借助二叉树上的运算方法去实现对树的一些运算
B、将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题
C、将树、森林转换成二叉树
D、体现一种技巧，没有什么实际意义
15、在链表中，若要删除第i个元素，以下操作正确的（  B  ）
A.直接删除第i个节点
B.将第i个节点的前一个节点的next指针指向第i个节点的后一个节点
C.将第i个节点的后一个节点的前一个节点的next指针指向第i个节点
D.将第i个节点的数据清零
16．在数据结构中，线性表是一种常见的数据结构，以下哪项不是线性表的特征 （  C  ）
A．有且只有一个头节点     
B．每个节点最多有一个直接前驱和一个直接后继
C.每个节点最多有一个直接前驱和多个直接后继
D.表中元素呈线性排列
17．在二叉树中，若度为О的节点个数为n0，度为2的节点个数为n2，则n0 与n2的关系为（  A  ） 
A. n0 = n2+ 1
B. n0 = n2 - 1
C. n0 = n2 + 2
D. n0 = n2 - 2
18、在排序算法中，以下哪种排序算法的平均时间复杂度最低（  D ）
A.冒泡排序一个
B.选择排序
C.插入排序
D.快速排序
二．程序题
1、已知数据序列为（24，10，18，40，12，62，48），对该数据序列排序，写出插入排序，简单选择排序，冒泡泡排序的算法程序。(8分)