西交15年考试《数据结构》作业考核试题最新Word文档下载推荐.docx
- 文档编号:6714594
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:9
- 大小:17.24KB
西交15年考试《数据结构》作业考核试题最新Word文档下载推荐.docx
《西交15年考试《数据结构》作业考核试题最新Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《西交15年考试《数据结构》作业考核试题最新Word文档下载推荐.docx(9页珍藏版)》请在冰点文库上搜索。
C.被排序的数据完全无序
D.被排序的数据中的最大值和最小值相差悬殊
满分:
2
分
2.
以下说法错误的是()。
A.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。
B.若一个二叉树的树叶是某子树中序遍历序列中的第一个结点,则它必是该子树后序遍历序列中的第一个结点
C.二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不能确定树的根结点
D.在前序遍历二叉树的结点序列中,任一结点其子树的结点都直接跟在该结点之后
3.
设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是()。
A.40,42,60,55,80,85
B.42,45,55,60,85,80
C.42,40,55,60,80,85
D.42,40,60,85,55,80
4.
()二叉排序树可以得到一个从小到大的有序序列。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
5.
下面( )算法适合构造一个稠密图G的最小生成树。
A.Prim算法
B.Kruskal算法
C.Floyd算法
D.Dijkstra算法
6.
设某棵二叉树的高度为10,则该二叉树上叶子结点最多有()。
A.20
B.256
C.512
D.1024
7.
程序段如下:
s=i=0;
do{i=i+1;
s=s+i;
}while(i<
=n);
其时间复杂度为()。
A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(n3/2)
8.
设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。
A.2n
B.n
C.n/2
D.n(n-1)
9.
对顺序表上的插入、删除算法的时间复杂性分析来说,通常以()为标准操作。
A.条件判断
B.结点移动
C.算术表达式
D.赋值语句
10.
设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为()。
A.1
B.2
C.3
D.4
11.
哈希表的平均查找长度是()的函数。
A.哈希表的长度
B.表中元素的多少
C.哈希函数
D.哈希表的装满程度
12.
设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为()。
A.top=top+1
B.top=top-1
C.top->
next=top
D.top=top->
next
13.
设无向图G中有n个顶点,则该无向图的最小生成树上有()条边。
A.n
B.n-1
C.2n
D.2n-1
14.
设带有头结点的单向循环链表的头指针变量为head,则其判空条件是()。
A.head==0
B.head->
next==0
C.head->
next==head
D.head!
=0
15.
设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为()。
A.2i+1
B.2i
C.i/2
D.2i-1
分
对不起,由于您的浏览器不能运行javascript,所以不能运行作业程序!
请您解除禁止javascript后,点击已经解除按钮或重新打开页面!
解决方法
三、判断题(共10道试题,共10分。
当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。
()
A.错误
B.正确
1
对连通图进行深度优先遍历可以访问到该图中的所有顶点。
设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(log2n)。
带权无向图的最小生成树是唯一的。
先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
线性表中的所有元素都有一个前驱元素和后继元素。
哈夫曼树中没有度数为1的结点。
完全二叉树中的叶子结点只可能在最后两层中出现。
由树转化成二叉树,该二叉树的右子树不一定为空。
不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。
四、简答题(共5道试题,共20分。
简答题
1下图所示的森林:
(1)求树(a)的先根序列和后根序列;
(2)求森林先序序列和中序序列;
(3)将此森林转换为相应的二叉树;
上传附件
文件操作
4
设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。
特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?
为什么?
3在图7.4(下图)所示的有向图中:
(1)该图是强连通的吗?
若不是,则给出其强连通分量。
(2)请给出所有的简单路径及有向环。
(3)请给出每个顶点的度,入度和出度。
(4)请给出其邻接表、邻接矩阵及逆邻接表。
为什么有序的单链表不能进行折半查找?
五、论述题(共2道试题,共20分。
论述题
2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
10
论述题1试设计在顺序存储结构上实现求子串的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 15 考试 作业 考核 试题 最新