《(满分100)南开21春南开21春学期(1709---2103)《数据结构》在线作业888888(4)》由会员分享，可在线阅读，更多相关《(满分100)南开21春南开21春学期(1709---2103)《数据结构》在线作业888888(4)（4页珍藏版）》请在金锄头文库上搜索。
1、南开21春学期(2103)数据结构在线作业 (482).doc10111 / 101.已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（ ） A.0 2 4 3 1 5 6 B.0 1 3 5 6 4 2 C.0 4 2 3 1 6 5 D.0 1 3 4 2 5 6 【参考答案】: D 2.设有两个串p和q，求q在p中首次出现的位置的运算称作（） A.连接 B.模式匹配 C.求子串 D.求串长 【参考答案】: B 3.折半搜索与二叉搜索树的时间性能() A.相同 B.完全不同 C.有时不相同 D.数量级都是O（log2n） 【参考答案】: C 4.在n个结点的顺序表中，
2、算法的时间复杂度是O（1）的操作是（） A.访问第i个结点（1in）和求第i个结点的直接前驱（2in） B.在第i个结点后插入一个新结点（1in） C.删除第i个结点（1in） D.将n个结点从小到大排序 【参考答案】: A 5.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（） 在线1对1辅导，中小学1对1辅导黄磊选择-掌门1对1 A.0 2 4 3 6 5 1 B.0 1 3 6 4 2 5 C.0 4 2 3 1 5 6 D.0 1 3 4 2 5 6 【参考答案】: B 6.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A.1/2 B.1
3、C.2 D.4 【参考答案】: B 7.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的 A.栈 B.队列 C.树 D.图 【参考答案】: B 8.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（） A.i B.n=i C.n-i1 D.不确定 【参考答案】: C 9.快速排序在下列哪种情况下最易发挥其长处() A.被排序的数据中含有多个相同排序码 B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中的最大值和最小值相差悬殊 【参考答案】: C 10.堆的形状是一棵() A.二叉排序树 B.满二叉树 C.完全二叉
4、树 D.平衡二叉树 【参考答案】: C 11.判定一个队列QU（最多元素为m0）为满队列的条件是（） A.QU-rear QU-front = = m0 B.QU-rear QU-front 1= = m0 C.QU-front = = QU-rear D.QU-front = = QU-rear1 【参考答案】: A 12.一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A. B. C. D. 【参考答案】: A 13.堆是一种()排序。 A.插入 B.选择 C.交换 D.归并 【参考答案】: B 14.有8个结点的无向连通图最少有（）条边 A.5 B.6 C.7 D.8 【参考答案
5、】: C 15.链表是一种采用 存储结构存储的线性表 A.顺序 B.链式 C.星式 D.网状 【参考答案】: B 16.不含任何结点的空树（） A.是一棵树 B.是一棵二叉树 C.是一棵树也是一棵二叉树 D.既不是树也不是二叉树 【参考答案】: C 17.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为() A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 【参考答案】: C 18. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ） A.0 2 4 3 1 5 6 B.0 1 3 6 5 4 2 C.0 4 2 3 1 6 5
6、D.0 3 6 1 5 4 2 【参考答案】: C 19.下列关键字序列中，()是堆 A.16,72,31,23,94,53 B.94,23,31,72,16,53 C.16,53,23,94，31,72 D.16,23,53,31,94,72 【参考答案】: D 20.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为() A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 【参考答案】: C 21.在表长为的链表中进行线性查找，它的平均查找长度为（ ） A. B.（） C. D. 【参考答案】: B 22. 设a
7、1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（） A.循环链表 B.单链表 C.双向循环链表 D.双向链表 【参考答案】: B 23.将5个不同的数据进行排序，至多需要比较()次 A.8 B.9 C.10 D.25 【参考答案】: C 24.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为() A.79,46,56,38,40,84 B.84,79,56,38,40,46 C.84,79,56,46,40,38 D.84,56,79,40,46,38 【参考答案】: B 25.任何一个无向连通图的最小生成树(
8、) A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在 【参考答案】: A 26.单链表的存储密度（） A.大于1 B.等于1 C.小于1 D.不能确定 【参考答案】: C 27.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （） A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3 【参考答案】: D 28.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为() A.CBEFDA B.FEDCBA C.CBEDFA D.不定 【参考答案】: A 29.判定一个栈ST（最多元素为m0）为空
9、的条件是（） A.ST-top0 B.ST-top=0 C.ST-topm0 D.ST-top=m0 【参考答案】: B 30.把一棵树转换为二叉树后，这棵二叉树的形态是（） A.唯一的 B.有多种 C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子 【参考答案】: A 31.二叉树中每个结点的两棵子树的高度差等于1。 A.错误 B.正确 【参考答案】: A 32.链表的每个结点中都恰好包含一个指针。 A.错误 B.正确 【参考答案】: A 33.栈和链表是两种不同的数据结构。 A.错误 B.正确 【参考答案】: A 34.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位
10、置次序上相邻。 A.错误 B.正确 【参考答案】: A 35.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表 A.错误 B.正确 【参考答案】: B 36.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 A.错误 B.正确 【参考答案】: A 37.在表结构中最常用的是线性表，栈和队列不太常用。 A.错误 B.正确 【参考答案】: A 38.一个栈的输入序列是12345，则栈的输出序列不可能是12345。 A.错误 B.正确 【参考答案】: A 39.二叉树中每个结点的两棵子树是有序的。 A.错误 B.正确 【参考答案】: B 40.栈和队列是一种非线性数据结构
11、。 A.错误 B.正确 【参考答案】: A 41.链表的物理存储结构具有同链表一样的顺序。 A.错误 B.正确 【参考答案】: A 42.具有12个结点的完全二叉树有5个度为2的结点。 A.错误 B.正确 【参考答案】: B 43.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 A.错误 B.正确 【参考答案】: B 44.栈和队列的存储方式既可是顺序方式，也可是链接方式。 A.错误 B.正确 【参考答案】: B 45.线性表的逻辑顺序与存储顺序总是一致的。 A.错误 B.正确 【参考答案】: A 46.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 A.错误 B.正确 【参考答案】: A 47.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 A.错误 B.正确 【参考答案】: B 48.顺序存储方式只能用于存储线性结构。 A.错误 B.正确 【参考答案】: A 49.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 A.错误 B.正确 【参考答案】: A 50.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 A.错误 B.正确 【参考答案】: A
