没有合适的资源?快使用搜索试试~ 我知道了~
为软件工程打下良好的基础,非常适合专业工作者或者在校大学生学习参考的一本书籍
资源详情
资源评论
资源推荐
数据结构试卷(一)
一、单选题(每题 2 分,共 20 分)
栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素 B.都是先进后出
C.都是先进先出 没有共同点
用链接方式存储的队列,在进行插入运算时
仅修改头指针 头、尾指针都要修改
仅修改尾指针 头、尾指针可能都要修改
以下数据结构中哪一个是非线性结构?
A. 队列 B. 栈 C. 线性表 D. 二叉树
设有一个二维数组 A[m ][n],假设 A[0][0]存放位置在 644
(10)
,A[2][2]存放位置在
676
(10)
,每个元素占一个空间,问 A[3][3]
(10)
存放在什么位置?脚注
(10)
表示用 10 进制
表示。
A.688 B.678 C.692 D.696
树最适合用来表示( )。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
二叉树的第 层的结点数最多为
.
若有 18 个元素的有序表存放在一维数组 A[19]中,第一个元素放 A[1]中,现进行二
分查找,则查找 A[3]的比较序列的下标依次为( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
对 个记录的文件进行快速排序,所需要的辅助存储空间大致为
() () (
) ()
对于线性表(,,,,,,,)进行散列存储时,若选用
() 作为散列函数,则散列地址为 的元素有( )个,
....
设有 6 个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
二、填空题(每空 1 分,共 26 分)
通常从四个方面评价算法的质量:_________、_________、_________和_________。
一个算法的时间复杂度为(n
3
+n
2
log
2
n+14n)/n
2
,其数量级表示为________。
假定一棵树的广义表表示为 A(C,D(E,F,G),H(I,J)),则树中所含的结点
数为__________个,树的深度为___________,树的度为_________。
后缀算式 9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3 对应的后缀算式为
_______________________________。
若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指
针。在这种存储结构中,n 个结点的二叉树共有________个指针域,其中有________
个指针域是存放了地址,有________________个指针是空指针。
对于一个具有 n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中,所含边结点
分别有_______个和________个。
7. AOV 网是一种___________________的图。
在一个具有 n 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点的有
向完全图中,包含有________条边。
假定一个线性表为(12,23,74,55,63,40),若按 Key % 4 条件进行划分,使得同一余数的元
素成为一个子表,则得到的四个子表分别为____________________________、_______
____________、_______________________和__________________________。
向一棵 B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度__
_________。
在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为 ________,整个堆排
序过程的时间复杂度为________。
在快速排序、堆排序、归并排序中,_________排序是稳定的。
三、计算题(每题 6 分,共 24 分)
在如下数组 A 中链接存储了一个线性表,表头指针为 A [0].next,试写出该线性表。
!"
请画出下图的邻接矩阵和邻接表。
已知一个图的顶点集 V 和边集 E 分别为:#$%%%%%%&'
($%%%%%%%%%%%%
%%%%%%%%%%%&'
用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。
画出向小根堆中加入数据 4, 2, 5, 8, 3 时,每加入一个数据后堆的变化。
四、阅读算法(每题 7 分,共 14 分)
1. 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;
}
请回答下列问题:
(1)说明语句 S1 的功能;
(2)说明语句组 S2 的功能;
(3)设链表表示的线性表为(a
1
,a
2
, ),a
n
),写出算法执行后的返回值所表示的线性表。
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<<BT->data<<' ';
}
}
该算法的功能是:
五、算法填空(共 8 分)
二叉搜索树的查找——递归算法*
+,-./0!!1!23/%(,!4/56!7. !4
$
.83/19::
0! ;08,<!'==查找失败
!,<!$
.8. !43/> $
. !43/> '==查找成功
0! ;0???????????'&
!,<!.8. !4@3/>
0! ;0-.??????????????%. !4'
!,<!0! ;0-.???????????????%. !4'
&==.8
&
六、编写算法(共 8 分)
统计出单链表 HL 中结点的值等于给定值 X 的结点数。
. ; A:1!2:%(,!4/56!"
数据结构试卷(二)
一、选择题(24 分)
.下面关于线性表的叙述错误的是( )。
线性表采用顺序存储必须占用一片连续的存储空间
线性表采用链式存储不必占用一片连续的存储空间
线性表采用链式存储便于插入和删除操作的实现
线性表采用顺序存储便于插入和删除操作的实现
.设哈夫曼树中的叶子结点总数为 4,若用二叉链表作为存储结构,则该哈夫曼树中总
共有( )个空指针域。
4 4 4 4
.设顺序循环队列 BC:DE的头指针和尾指针分别为 - 和 F,头指针 - 总是指向队头
元素的前一位置,尾指针 F 总是指向队尾元素的当前位置,则该循环队列中的元素个数为
( )。
F- -F F-D%D -FD%D
.设某棵二叉树的中序遍历序列为 ABCD,前序遍历序列为 CABD,则后序遍历该二叉
树得到序列为( )。
.设某完全无向图中有 个顶点,则该完全无向图中有( )条边。
=
.设某棵二叉树中有 个结点,则该二叉树的最小高度为( )。
.设某有向图中有 个顶点,则该有向图对应的邻接表中有( )个表头结点。
.设一组初始记录关键字序列,,,,,以第一个记录关键字 为基准进行一
趟快速排序的结果为( )。
,,,, ,,,,
,,,, ,,,,
二、填空题(24 分)
为了能有效地应用 3 查找技术,必须解决的两个问题是????????????????????和??
????????????????????????。
下面程序段的功能实现数据 " 进栈,要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x)
{
if (stack.top==m-1) printf(“overflow”);
else {____________________;_________________;}
}
中序遍历二叉排序树所得到的序列是???????????序列(填有序或无序)。
快速排序的最坏时间复杂度为???????????,平均时间复杂度为??????????。
设某棵二叉树中度数为 的结点数为 1
,度数为 的结点数为 1
,则该二叉树中度数
为 的结点数为?????????;若采用二叉链表作为该二叉树的存储结构,则该二叉树中
共有???????个空指针域。
设某无向图中顶点数和边数分别为 和 !,所有顶点的度数之和为 ,则 !???????。
设一组初始记录关键字序列为,,,,,,,,则利用筛选法
建立的初始堆为???????????????????????????。
. 已知一有向图的邻接表存储结构如下:从顶点 1 出发,DFS 遍历的输出序列是
,BFS 遍历的输出序列是
三、应用题(36 分)
. 设一组初始记录关键字序列为,,,,,,则分别给出第 趟简单
选择排序和第 趟直接插入排序后的结果。
. 设指针变量 6 指向双向链表中结点 ,指针变量 G 指向被插入结点 ,要求给出在结
点 的后面插入结点 的操作序列(设双向链表中结点的两个指针域分别为 ,,. 和
0,.)。
. 设一组有序的记录关键字序列为,,,,,,,,,查找
方法用二分查找,要求计算出查找关键字 时的比较次数并计算出查找成功时的平均
查找长度。
. 设一棵树 / 中边的集合为$(,B),(,C),(,D),(,E),(,F),(,G)&,要
求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉
树。
. 设有无向图 H,要求给出用普里姆算法构造最小生成树所走过的边的集合。
. 设有一组初始记录关键字为,,,,,,要求构造一棵二叉排序树
并给出构造过程。
四、算法设计题(16 分)
. 设有一组初始记录关键字序列(
,
,…,
),要求设计一个算法能够在 的
时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于
.
,右半部
分的每个关键字均大于等于
.
。
剩余21页未读,继续阅读
herundongheliantao
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0