一单项选择题 ( 在每小题的四个备选答案中选出一个正确答案并将正确答案的序号填在题干的括号内每小题 分共 分 )
某二叉树的先序序列和后序序列正好相同则该二叉树一定是 ( ) 的二叉树
A 空或只有一个结点 B 高度等于其结点数
C 任一结点无左孩子 D 任一结点无右孩子
下列排序算法中时间复杂度不受数据初始状态影响恆为 O(log n) 的是 ( )
A 堆排序 B 冒泡排序
C 直接选择排序 D 快速排序
下列排序算法中 ( ) 算法可能会出现下面情况初始数据有序时花费的时间反而最多
A 堆排序 B 冒泡排序
C 快速排序 DSHELL 排序
一个栈的输入序列为 则下列序列中不可能是栈的输出序列的是 ( )
A B
C D
设循环队列中数组的下标范围是 ～ n 其头尾指针分别为 f 和 r 则其元素个数为 ( )
A rf B rf+
C (rf) mod n+ D (rf+n) mod n
若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点则采用 ( ) 存储方式最节省时间
A 单链表 B 双链表
C 带头结点的双循环链表 D 单循环链表
在有 n 个结点的二叉链表中值为非空的链域的个数为 ( )
A n B n
C n+ D n+
一棵左右子树均不空的二叉树在先序线索化后其空指针域数为 ( )
A B
C D 不确定
数组 A [][]的每个元素占 个单元将其按行优先次序存储在起始地址为 的连续的内存单元中则元素 A []的地址为 ( )
A B
C D
求最短路径的 DIJKSTRA 算法的时间复杂度为 ( )
A O(n) B O(n+e)
C O(n ) D O(n × e)
对有 个元素的有序表作二分查找则查找 A [ ]的比较序列的下标依次为 ( )
A B
C D
快速排序算法在最好情况下的时间复杂度为 ( )
A O(n) B O(nlog n)
C O(n ) D O(log n)
下列排序算法中某一趟结束后未必能选出一个元素放在其最终位置上的是 ( )
A 堆排序 B 冒泡排序
C 快速排序 D 直接插入排序
二叉树在线索化后仍不能有效求解的问题是 ( )
A 先序线索二叉树中求先序后继
B 中序线索二叉树中求中序后继
C 中序线索二叉树中求中序前趋
D 后序线索二叉树中求后序后继
DFS 算法的时间复杂度为 ( )
A O(n) B O(n )
C O(n ) D O(n+e)
队列操作的原则是 ( )
A 先进先出 B 后进先出
C 只能进行插入 D 只能进行删除
有 个结点的完全二叉树的深度为 ( )( 根的层次为 )
A B
C D
在平衡二叉树中插入一个结点后造成了不平衡设最低的不平衡结点为 A 并已知 A 的左孩子的平衡因子为 右孩子的平衡因子为 则应作 ( ) 型调整以使其平衡
A LL B LR
C RL D RR
数据表 A 中有 个元素如果仅要求求出其中最大的 个元素则采用 ( ) 排序算法最节省时间
A 堆排序 B 希尔排序
C 快速排序 D 直接选择排序
二判断题 ( 判断下列各题正确的在题后括号内打 √ 错的打 × 每小题 分共 分 )
给出不同的输入序列建造二叉排序树一定得到不同的二叉排序树 ( )
由于希尔排序的最后一趟与直接插入排序过程相同因此前者一定比后者花费的时间多 ( )
在对链队列作出队操作时不会改变 front 指针的值 ( )
若一个栈的输入序列为 … n 其输出序列的第一个元素为 n 则其输出序列的每个元素 a i 一定满足 a i =ni+(i=n)( )
二叉树中的叶子结点就是二叉树中没有左右子树的结点 ( )
一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数 ( )
有向图用邻接矩阵表示后顶点 i 的人度等于邻接矩阵中第 i 列的元素个数 ( )
有向图的邻接表和逆邻接表中的结点数一定相同 ( )
删除二叉排序树中一个结点再重新插入上去一定能得到原来的二叉排序树 ( )
图 G 的拓扑序列唯一则其弧数必为 n( 其中 n 为 G 的顶点数 ) ( )
三填空题 ( 每空 分共 分 )
在有 n 个叶子结点的哈夫曼树中总结点数是 _______
一棵树 T 采用二叉链表存储如果树 T 中某结点为叶子结点则在二叉链表 BT 中所对应的结点一定 _______
已知数组 A [][]为对称矩阵其中每个元素占 个单元现将其下三角部分按行优先次序存储在起始地址为 的连续的内存单元中则元素 A []对应的地址是 _______
在有 n 个结点的无向图中其边数最多为 _______
取出广义表 A=(x(abcd)) 中原子 x 的函数是 _______
对矩阵采用压缩存储是为了 _______
带头结点的双循环链表 L 为空表的条件是 _______
在双链表中在指针 P 所指结点前面插入一个结点 S ∧时的语句序列是
S>next=P;S>prior=P>prior;P>prior=S;
_______ ;
对广义表 A=(x((ab)cd)) 的运算 head (head (tail (A))) 的结果是 ______
判断线索二叉树中某结点指针 P 所指结点有左孩子的条件是 _______
四简答题 ( 每小题 分共 分 )
&#;
求出下图的一棵最小生成树
将下面顺序表建成一个小头堆
( )
已知一棵二叉树的先序序列是 ABCDEFGHIJK 中序序列是 CDBGFEAHJIK 请构造出该二叉树
五综合应用题 ( 共 分 )
已知一树的双亲表示法如下其中各兄弟结点是依次出现的画出该树及对应的二叉树 ( 满分 分 )
data A B C D E F G H I J K L M N O
parent
计算二叉树的深度的算法 ( 分 )
浙江省 年 月高等教育自学考试
数据结构试题参考答案
课程代码
一单项选择题 ( 每小题 分共 分 )
A B C B D
C A B A C
D B D D C
A B A C
二判断题 ( 每小题 分共 分 )
√ × √ √ ×
× √ × × ×
三填空题 ( 每空 分共 分 )
n
左右子树空
n(n)/
head(A)
节省空间
L>next=L>prior 或 L>next=L
S>prior>next=S
(a)
P>ltag=
四简答题 ( 每小题 分共 分 )
&#; 最小生成树
小头堆
二叉树
五综合应用题 ( 共 分 )
&#;
从森林转换为二叉树 ( 分 )
计算二叉树的深度的算法 ( 分 )
int depth(tree *T)
{
if(!T)
return ;
else
return +max(depth(T>Lchild)depth(>Rchild));
}
