《《数据结构》19秋期末考.doc》由会员分享，可在线阅读，更多相关《《数据结构》19秋期末考.doc（15页珍藏版）》请在三一文库上搜索。
1、 1 / 13 【奥鹏】-南开大学数据结构19秋期末考核 试卷总分:100得分:100 第1题,有8个结点的无向连通图最少有（）条边 A、5 B、6 C、7 D、8 正确答案:C 第2题,链表是一种采用存储结构存储的线性表 A、顺序 B、链式 C、星式 D、网状 正确答案:B 第3题,栈中元素的进出原则是（） A、先进先出 B、后进先出 C、栈空则进 D、栈满则出 正确答案:B 第4题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的 2 / 13 A、栈 B、队列 C、树 D、图 正确答案:A 第5题,链表适用于()查找 A、顺序 B、二分法 C、顺序，也能二分法 D、随机 正确
2、答案:A 第6题,把一棵树转换为二叉树后，这棵二叉树的形态是（） A、唯一的 B、有多种 C、有多种，但根结点都没有左孩子 D、有多种，但根结点都没有右孩子 正确答案:A 第7题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素 A、8 B、63.5 3 / 13 C、63 D、7 正确答案:B 第8题,引入二叉线索树的目的是（） A、加快查找结点的前驱或后继的速度 B、为了能在二叉树中方便的进行插入与删除 C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一 正确答案:A 第9题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（）A
3、、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 第10题,判定一个栈ST（最多元素为m0）为空的条件是（） A、ST-top0 B、ST-top=0 C、ST-topm0 D、ST-top=m0 正确答案:B 4 / 13 第11题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是() A、110 B、108 C、100 D、120 正确答案:B 第12题,广度优先遍历类似于二叉树的() A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 正确答案:D 第13题,已知图
4、的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）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 第14题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（） A、循环链表 5 / 13 B、单链表 C、双向循环链表 D、双向链表 正确答案:B 第15题,链接存储的存储结构所占存储空间（） A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B、只有一部分，存放结点值 C、只有一部分，存储表示结点间关系的指针 D、分两部分，一部分存放结
5、点值，另一部分存放结点所占单元数 正确答案:A 第16题,设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2, len(s2), subs(s1, len(s2), 2)的结果串是（） A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 正确答案:D 第17题,任何一个无向连通图的最小生成树() A、只有一棵 B、一棵或多棵 6 / 13 C、一定有多棵 D、可能不存在 正确答案:A 第18题,串是一种特殊的线性表，
6、其特殊性体现在（） A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 正确答案:B 第19题,判定一个队列QU（最多元素为m0）为满队列的条件是（） A、QU-rearQU-front = = m0 B、QU-rearQU-front1= = m0 C、QU-front = = QU-rear D、QU-front = = QU-rear+1 正确答案:A 第20题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（） A、0 1 3 2 B、0 2 3 1 C、0 3 2 1 D、0 1 2 3 7 / 13 正确答案:D 第2
7、1题,下列关键字序列中，()是堆 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 第22题,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。 A、20，70，30，50 B、30，88，70，50 C、20，50 D、30，88，50 正确答案:A 第23题,深度优先遍历类似于二叉树的() A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 正确答案:A 8 / 13 第2
8、4题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）A、0 2 4 3 1 6 5 B、0 1 3 5 6 4 2 C、0 1 2 3 4 6 5 D、0 1 2 3 4 5 6 正确答案:C 第25题,下述几种排序方法中，要求内存最大的是() A、插入排序 B、快速排序 C、归并排序 D、选择排序 正确答案:C 第26题,线性表在物理存储空间中也一定是连续的。 A、错误 B、正确 正确答案:A 第27题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 A、错误 B、正确 正确答案:A 9 / 13 第28题,线性表在顺序存储时，逻辑上相邻
9、的元素未必在存储的物理位置次序上相邻。 A、错误 B、正确 正确答案:A 第29题,栈和队列的存储方式既可是顺序方式，也可是链接方式。 A、错误 B、正确 正确答案:B 第30题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 A、错误 B、正确 正确答案:A 第31题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。 A、错误 B、正确 正确答案:A 第32题,栈和链表是两种不同的数据结构。 A、错误 10 / 13 B、正确 正确答案:A 第33题,顺序存储方式的优点是存储密度大
10、，且插入、删除运算效率高。 A、错误 B、正确 正确答案:A 第34题,具有12个结点的完全二叉树有5个度为2的结点。 A、错误 B、正确 正确答案:B 第35题,线性表的逻辑顺序与存储顺序总是一致的。 A、错误 B、正确 正确答案:A 第36题,链表的物理存储结构具有同链表一样的顺序。 A、错误 B、正确 正确答案:A 第37题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 A、错误 11 / 13 B、正确 正确答案:A 第38题,二叉树中每个结点的两棵子树是有序的。 A、错误 B、正确 正确答案:B 第39题,一个栈的输入序列是12345，则栈的输出序列不可能是12345
11、。 A、错误 B、正确 正确答案:A 第40题,顺序存储方式只能用于存储线性结构。 A、错误 B、正确 正确答案:A 第41题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。 A、错误 B、正确 正确答案:A 第42题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A、错误 B、正确 12 / 13 正确答案:A 第43题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表A、错误 B、正确 正确答案:B 第44题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 A、错误 B、正确 正确答案:B 第45题,两个
12、栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 A、错误 B、正确 正确答案:B 第46题,设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。 正确答案: (22，40，45，48，80，78)，(40，45，48，80，22，78) 第47题,设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。 正确答案: 13 / 13 01234567 线性探测：81025322768 h 0 h 18 h 2 h 310 h 42532 h 568 链地址法：h 627 第48题,设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 正确答案: 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。