吉林大学网络教育数据结构练习题C期末考试复习题
- 格式:doc
- 大小:39.50 KB
- 文档页数:2
数据结构练习题C
一、单项选择题
1.线性链表中各结点之间的地址()。
A. 必须连续
B. 一定不连续
C. 部分地址必须连续
D. 连续与否无所谓
2.在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加()。
A. 2
B. 1
C. 0
D. –1
3.某二叉树的前序和后序序列正好相同,则该二叉树一定是( )的二叉树。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
4.设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是()。
A. 5 1 2 3 4
B.4 5 1 3 2
C.4 3 1 2 5
D. 3 2 1 5 4
5.稀疏矩阵一般采用( )方法压缩存储。
A.三维数组
B.单链表
C.三元组表
D.散列表
6.设有50行60列的二维数组A[50][60],其元素长度为4字节,按行优先顺序存储,基地址为200,则元素A[18][25]的存储地址为()。
A.3700 B.4376 C.3900 D.4620
7.在含n个顶点e条边的无向图的邻接矩阵中,零元素的个数为()。
A.e B.2e C.n2-e D.n2-2e
8.邻接表的存储结构下图的深度优先遍历类似于二叉树的( )。
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
9.串是()。
A.一些符号构成的序列
B.一些字母构成的序列
C.一个以上字符构成的序列
D.任意有限个字符构成的序列
10.若在线性表中采用折半查找法查找元素,该线性表必须满足()。
A. 元素按值有序
B. 采用顺序存储结构
C. 元素按值有序,且采用顺序存储结构
D. 元素按值有序,且采用链式存储结构
11. 深度为n的二叉树中所含叶子结点的个数最多为()个。
A.2n
B.n
C.2n
D.2n-1
12. 设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用( )法。
A.冒泡排序
B.快速排序
C.堆排序
D.基数排序
13.下列四个关键字序列中,( )不是堆。
A. {05,23,16,68,94,72,71,73}
B. {05,16,23,68,94,72,71,73}
C. {05,23,16,73,94,72,71,68}
D. {05,23,16,68,73,71,72,94}
14.任何一个无向连通图的最小生成树( )。
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
15.在一个具有n个顶点的无向图中,要连通全部顶点至少需要( )边。
A. n
B. n+1
C. n-1
D. n/2
二、填空题
1.在n个结点的顺序表中插入一个结点需平均移动_ __个结点,具体移动次数取决于_ _。
2.在双链表中每个结点有两个指针域,一个指向________,另一个指向 __________。3.数据结构的三个方面:数据的、、。
4.算法分析的两个主要方面是____________和____________。
5.深度为8的(根的层次号为1)满二叉树有个叶子结点。
6.设根结点的层数为0,定义树的高度为树中层数最大的结点的层数加1。
则高度为k的二叉树具有的结点数目,最少为___
7.队列中允许进行插入的一端称为_________。
8.若连通网络上各边的权值均不相同,则该图的最小生成树有_______棵。
9.二叉树的遍历方式有三种:先根遍历、中序遍历、___________ 。
10.由一棵二叉树的后序序列和_ ___唯一确定这棵二叉树。
11若一棵二叉树有10个叶结点,则该二叉树中度为2的结点个数为
_________。
12.一个具有n个顶点的图采用邻接矩阵表示,则该矩阵的大小为。
三、应用题
1.将表达式((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。
2.给定表(45,36,56,6,64,32,8,41),按数据元素在表中的次序构造一棵二叉查找树。
3.已知一棵二叉树的中序和前序序列如下,求该二叉树的后序序列。
中序序列:c,b,d,e,a,g,i,h,j,f
前序序列:a,b,c,d,e,f,g,h,i,j
4.用普里姆算法(Prim)算法求出下图的最小支撑树。
5.应用直接插入排序算法,对键值序列49,38,65,97,76,13,27,45从小到大进行排序,写出每趟排序的结果。
四、算法设计题
1.假设线性表用带表头结点的单向链表head表示,试写出删除表中所有data域值为零的元素的算法。
2.设一棵二叉树以二叉链表为存储结构,试写一算法求该二叉树上1度结点的个数。