山东师范大学成人高等教育计算机科学与技术专业 （专升本、高起本）《数据结构与算法》课程复习题A
参考答案在试卷后（7月无纸化考试）
一、 选择题（每小题2分，共30分）
1．数据结构在计算机内存中的表示是指 ( ) 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 2．在以下的叙述中，正确的是( )。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出
3．在循环双链表的p所指的结点之前插入s所指结点的操作是( ) 。 A．p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s 4．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：( )。
A．n-i+1 B．n-i C．i D．i-1 5．栈和队列的共同点是( )。
A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 6．串是一种特殊的线性表，其特殊性体现在( ) 。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符 7．对矩阵进行压缩存储是为了( )。
A．方便运算 B． 方便存储 C．提高运算速度 D．减少存储空间
8．稀疏矩阵一般的压缩存储方式有两种，即( ) 。 A．二维数组和三维数组 B． 三元组和散列 C．三元组和十字链表 D． 散列和十字链表
9．对一个满二叉树，m个叶子，n个结点，深度为h，则 ( )。 A．n = h+m B．h+m = 2n C．m = h-1 D．n = 2h-1 10．在下述论述中，正确的是( )。 ①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换； ④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④ 11．具有n 个结点的连通图至少有( )条边。
A．n-1 B．n C．n(n-1)/2 D．2n 88．广义表（（a），a）的表头是 C ，表尾是( )。
A．a B．（） C．（a） D．（（a））
12．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，( )次比较后查找成功。 A．11 B．5 C．4 D．8 13．查找效率最高的二叉排序树是( )。 A．所有结点的左子树都为空的二叉排序树 B．所有结点的右子树都为空的二叉排序树 C．平衡二叉树
D．没有左子树的二叉排序树
14．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( ) 。
A．希尔排序 B．冒泡排序 C．插入排序 D．选择排序 15设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是( )。 A．N0=N1+1
B．N0=Nl+N2
C．N0=N2+1
D．N0=2N1+l
二、 填空题（每空2分，共20分）
1．数据逻辑结构包括集合、__________、__________和图状结构四种类型。 2．算法的5个重要特性是有穷性、__________、__________、输入和输出。 3．广义表（（a），（（b），c），（（（d））））的长度是 __________，深度是__________。 数据的物理结构主要包括___________和__________两种情况。
4．设一棵完全二叉树中有500个结点，则该二叉树的深度为__________。 5．设输入序列为1、2、3，则经过栈的作用后可以得到__________种不同的输出序列。
三、 操作题（每小题10分，共30分）
1．对于下图所示的有向图采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点①出发进行深度优先搜索的遍历过程； (2) 从顶点②出发进行广度优先搜索的遍历过程。
2. 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。
3. 请画出与下列二叉树对应的森林。
四、 算法设计题（每小题2分，共20分）
1. 下列算法的功能是比较两个链串的大小，其返回值为：
成人教育数据结构与算法复习题及参考答案
