一、单项选择题
1．在逻辑上可以把数据结构分为（ ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
2．线性表是具有n个（ ）的有限序列。
A．表元素 B．字符 C．数据元素 D．数据项
3．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是
（ ）
A．head==NULL B．head→next==NULL
C．head→next==head D．head!=NULL
4．有n个叶子节点的哈夫曼树的结点总数为（ ）
A．不确定 B．2n C．2n+1 D．2n-1
5．下列哪一条是顺序存储结构的优点（ ）。
A. 插入运算方便
B. 可方便的用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
6．以下数据结构中（ ）是非线性结构。
A. 队列 B. 栈 C. 线性表 D. 二叉树
7．栈的插入和删除操作在（ ）进行。
A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置
8．一个队列的入列序列是1,2,3,4,则队列的输出序列是（ ）。
A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2， D. 3,2,4,1
9.对于栈操作数据的原则是（ ）
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
10.设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈
排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX
11．有关二叉树下列说法正确的是（ ）
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中所有结点的度都为2
12．查找效率最高的二叉排序树是（ ）。
A．所有结点的左子树都为空的二叉排序树。
B．所有结点的右子树都为空的二叉排序树。
C．平衡二叉树。
D．没有左子树的二叉排序树。
13．一个5个顶点的无向完全图有（ ）条边。例如：☆
A. 7 B. 8 C. 9 D. 10
14. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．图的深度优先遍历不适用于有向图
C．图的遍历基本算法有两种：深度优先遍历和广度优先遍历
D．图的深度优先遍历是一个递归过程
15．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中
的变化为：
（1） 84 47 25 15 21 （2） 15 47 25 84 21
（3） 15 21 25 84 47 （4） 15 21 25 47 84
则采用的排序是 ( )。
A. 选择 B. 冒泡 C. 快速 D. 插入
16．以下数据结构中，（ ）是非线性数据结构。
A．栈 B．顺序表 C．队列 D．树
17．线性结构中数据元素之间的关系是（ ）。
A．一对一的关系 B．一对多的关系
C．多对多的关系 C．以上都不对
18.顺序表a=（1，2，3，4，5），在元素3的前面插入一个元素8，需往后移动
元素次数为（ ）。
A．3 B．2 C．0 D．1
19．已知入栈顺序是a、b、c，下列哪个是不能得到的出栈序列（ ）。
A．abc B．bac C．cba D．cab
20. 一棵二叉树中，结点的度不可能的取值是（ ）。
A．3 B．2 C．1 D．0
21．一棵树中结点A有4个孩子结点， 结点A的度为（ ）。
A．2， B．1 C．0 D．4
22．先序遍历的顺序是（ ）。
A．根结点，左子树，右子树 B．左子树，根结点，右子树
C．右子树，根结点，左子树 D．左子树，右子树，根结点
23．在一棵树中，（ ）没有后继结点。
A. 分支结点 B. 叶子结点 C. 树根结点 D. 空结点
24. 在有向图中每个顶点的度等于该顶点的（ ）。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
25．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2
C．n(n+1) C．0
26. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是
（ ）
A．head==NULL B．head→next==NULL
C．head→next==head D．head!=NULL
27．组成数据的基本单位是（ ）。
A. 数据项 B. 数据类型 C. 数据变量 D. 数据元素
28．以下结构中（ ）是非线性结构。
A. 队列 B. 栈 C. 线性表 D. 二叉树
29．一棵深度为3的满二叉树，结点个数有（ ）个。
A．5 B．6 C．7 D．4
30．树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
二、判断题
(×)1.顺序存储方式只能用于存储线性结构。
(×）2.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
(×) 3.完全二叉树一定存在度为1的结点。
(×) 4.用树的先序遍历和中序遍历可以导出树的后序遍历。
（×）5.有向图的邻接矩阵是对称的。 0
（√）6.链表进行插入、删除操作时，在链表中比在顺序表中效率高。
（√）7.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。
（×）8.在哈夫曼树中，权值最小的结点离根结点最近。
（×）9.对任何数据结构链式存储结构一定优于顺序存储结构。
（×）10.线性表中每个元素都有一个直接前驱和一个直接后继。
（√）11.线性表中元素的关系是一对一的关系。
（√）12.栈和队列都是特殊的线性表。
（√）13.入队顺序1、2、3，出队顺序一定是1、2、3。
（×）14.空串是空格串。
（√）15.哈夫曼树中不存在度为1的结点。
（×）16.树状结构中每个结点都有一个前驱结点和一个后继结点。
（√）17.完全二叉树一定是满二叉树。
（√）18.图G=（V，E），V是顶点集合，E是边的集合，其中V可以是空集。
（√）19.无向图的邻接矩阵一定是关于对角线对称的。
（×）20.图的深度优先遍历序列是不惟一的，但广度优先遍历序列是惟一的。
四、算法题
1．以下是一个冒泡排序算法，请阅读该算法，并回答以下问题：
void BubbleSort(int elements[], int number){
int i, j;
int temp;
for (i = 0; i < number; ++i){
for (j = number-1 ; j > i; –j){
if (elements[j – 1] > elements[j]){
temp = e[j-1] ;
e[j-1] = e[j] ;
e[j] = temp ;
}
}
}
}
（1）请写出上面横线上应该填上的适当语句，完成该算法。
（2）参数number的作用是什么？
1、第一个for循环的number控制冒泡排序的轮数
2、第二个for循环的number控制每轮比较的次数
2. LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next) {
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
- 说明语句组S1的功能；
遍历链表,查找最后一个元素
- 说明语句组S2的功能；
将链表中最后一个元素指向第一个元素,然后将第一个元素的指向置空,
设链表表示的线性表为（a1,a2,
…,an），写出算法执行后的返回值所表示的线性表。
返回的线性表为(a2，a3，…，an，a1)。
