《数据结构与算法》复习题（专升本）
一、填空题
1、 数据结构被形式地定义为（ D, R），其中D 是 的有限集合， R 是D 上的 有限集合。
2、 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。
3、 写出带头结点的双向循环链表L 为空表的条件 。
4、 在具有n个元素的循环队列中，队满时具有 个元素。
5、 求子串在主串中首次出现的位置的运算称为 。
6、 由3个结点所构成的二叉树有 种形态。
7、 数据的逻辑结构是指 。
8、 数据结构按逻辑结构可分为两大类，它们分别是 和 。
9、 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。
10、 带头结点的单链表head 为空的条件是 。
11、 两个串相等的充分必要条件是两个串的长度相等且 。
12、 二维数组，可以按照 和 两种不同的存储方式。
13、 一棵具有257个结点的完全二叉树，它的深度为 。
14、 内部排序方法按排序采用的策略可划分为五类： 、 、 、 和基数排序。
二、完全二叉树算法选择题
1、若某线性表中最常用的操作是取第i 个元素和第i个元素的前驱，则采用（ ）存储方法最节省时间。
A.顺序表 B.单链表 C.双链表 D.单循环链表
2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子
3、计算机算法指的是：（ ）
A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法
4、栈和队列的主要区别在于（ ）。
A.它们的逻辑结构不一样 B.它们的存储结构不一样
C.所包含的运算不一样 D.插入删除运算的限定不一样
5、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（ ）。
A.000,001,010,011,1 B. 0000,0001,001,01,1
C.000,001,01,10,11 D.00,100,101,110,111
6、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。
A.逆拓扑有序 B.拓扑有序 C.无序 D.顶点编号次序
7、对如图所示的无向连通网图从顶点d开始用Prim算法构造最小生成树，在构造过程中加入最小生成树的前4条边依次是（ ）。
A. （d,f）4, (f,e) 2 , (f,b) 3 (b,a) 5
B. （f,e）2, (f,b) 3 , (a,c) 3 (f,d) 4
C. （d,f）4, (f,e) 2 , (a,c) 3 (b,a) 5
D. （d,f）4, (d,b) 5 , (f,e) 2 (b,a) 5
8、在采用线性探测法处理冲突所构成的闭散列表上进行查，可能要探测多个位置，在查成功的情况下，所探测的这些位置的键值（ ）。
A.一定都是同义词 B.一定都不是同义词 C.不一定都是同义词 D.都相同
9、二叉排序树中，最小值结点的（ ）。
A．左指针一定为空 B．右指针一定为空
C．左右指针均为空 D．左右指针均不为空
10、数据序列{8，9，10，4，5，6，20，1，2}只能是（ ）的两趟排序后的结果。
A.选择排序 B.冒泡排序 C.插入排序 D.堆排序
11、计算机算法必须具备输入、输出和（ ）等5 个特性。
A. 可行性、可移植性和可扩充性 B.可行性、确定性和有穷性
C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
12、串与普通的线性表相比较，它的特殊性体现在（ ）。
A. 顺序的存储结构 B. 链式存储结构
C. 数据元素是一个字符 D. 数据元素任意
13、以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
14、以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D.单链表
15、将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（ ）。
A. 98 B. 99 C. 50 D. 48
16、已知关键码序列{78，19，63，30，89，84，55，69，28，83}采用基数排序，第一趟排序后的关键码序列为（）
A. {19，28，30，55，63，69，78，83，84，89}
B. {28，78，19，69，89，63，83，30，84，55}
C. {30，63，83，84，55，78，28，19，89，69}
D. {30，63，83，84，55，28，78，19，69，89}
17、在一个长度为n 的顺序表中，在第i 个元素之前插入一个新元素时，需向后移动（ ）个元素。
A. n-i B. n-i+1 C. n-i-1 D. i
18、空串和空格串（ ）。
A. 相同 B. 不相同 C. 可能相同 D. 无法确定
19、常对数组进行两种基本操作是（ ）。
A. 建立和删除 B. 索引和修改 C. 查和修改 D. 查与索引
20、二叉树的深度为k ，则二叉树最多有（ ）个结点。
A. 2k B. 2 k-1 C. 2 k-1 D. 2k-1
三、判断题
1、线性表的逻辑顺序总是与其物理顺序一致。（ ）
2、当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（ ）
3、对稀疏矩阵进行压缩存储是为了节省存储空间。（ ）
4、边数很少的稀疏图，适宜用邻接矩阵表示。（ ）
5、二叉树是一棵无序树。( )
6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( )
7、当待排序序列初始有序时，快速排序的时间复杂性为O(n)。（ ）
8、顺序表的空间利用率高于链表。（ ）
9、哈希查法中解决冲突问题的常用方法是除留余数法。（ ）
10、顺序查法适用于存储结构为顺序或链接存储的线性表。（ ）
11、 线性表的顺序存储优于链式存储。（ ）
12、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 ( )
13、当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（ ）
14、采用不同的遍历方法，所得到的无向图的生成树是不同的。（ ）
15、有回路的有向图不能完成拓扑排序。( )
16、若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（ ）
17、在线性链表中删除中间的结点时，只需将被删结点释放。（ ）
18、线性表若采用链式存储表示, 在删除时不需要移动元素。（ ）
19、采用不同的遍历方法，所得到的无向图的生成树总是相同的。（ ）
20、递归的算法简单、易懂、容易编写，而且执行效率也高。（ ）
四、名词解释
3、数据：
4、存储结构分为：
5、算法的五个重要特性：
6、栈：
7、完全二叉树：
8、算法：
9、队列：
10、满二叉树：
11、连通图：
12、数据项：
五、简答题
1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问前序序列及后序序列是否也能唯一的建立二叉树，不能则举例说明理由。
2、关键码集合 {47, 7, 29, 11, 16, 92, 22, 8, 3}，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造开散列表，并求查成功时的平均查长度。
3. 已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出简单选择排序以及快速排序每趟的结果。
4、程序分析填空题
（1）函数GetElem 实现返回单链表的第i 个元素，请在空格处将算法补充完整。
int GetElem(LinkList L,int i,Elemtype *e){
LinkList p ;int j;
p=L->next;j=1;
while(p&&j<i){
(1) ;++j; }
if(!p||j>i) return ERROR;
*e= (2) ;
return OK;
}
（2）、函数实现单链表的插入算法，请在空格处将算法补充完整。
int ListInsert(LinkList L,int i,ElemType e){
LNode *p,*s; int j;
p=L;j=0;
while((p!=NULL)&&(j<i-1)){ p=p->next;j++;
}
if(p==NULL||j>i-1) return ERROR;
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
(1) ;
(2) ;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论