《川大《数据结构2264》18春在线作业2辅导资料》由会员分享，可在线阅读，更多相关《川大《数据结构2264》18春在线作业2辅导资料（7页珍藏版）》请在金锄头文库上搜索。
1、川大数据结构 226418 春在线作业 2 辅导资料1、C 2、D 3、B 4、D 5、D 一、单选题共 25 题，50 分1、若某二叉树结点的中序遍历的序列为 A、B、C、D、E、F、G，后序遍历的序列为 B、D、C、A、F、G、E。 则该二叉树结点的前序遍历的序列为（ ）。AE、G、F、A、C、D、B BE、A、G、C、F、B、D CE、A、C、B、D、G、F DE、G、A、C、D、F、B 正确答案是：C2、AOV 网是一种（ ）。 A 有向图 B 无向图 C 无向无环图 D 有向无环图正确答案是：D3、队列的特点是（ ）。 A 先进后出 B 先进先出 C 任意位置进出D 前面都不正确 正
2、确答案是：B4、设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右子树上的结点个数为 n， 森林 F 中第一棵树的结点个数是（ ）。Am-n-1 Bn+1 Cm-n+1 Dm-n 正确答案是：D5、从 L=（ ）,（ ）)中，取出 banana 元素的表达式为（ ）。Ahead(tail(L) Bhead(head(tail(L) Ctail(head(tail(L) Dhead(tail(head(tail(L) 正确答案是：D6、带有头结点的单循环链表的头指针为 head，则该链表为空的判定条件是（ ）。Ahead= =NUL Bhead-next= =NULLCh
3、ead!=NULL Dhead-next= =head 正确答案是：D7、以下数据结构中哪一个是非线性结构？（ ） A 队列 B 栈C 线性表 D 二叉树正确答案是：D8、在数据结构中，数据元素可由（ ）。 A 实体B 域 C 数据项D 字段 正确答案是：C9、在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素， 则在进行第 i 趟排序之前，无序区中元素的个数为（ ）。Ai Bi+1 Cn-i Dn-i+1 正确答案是：C10、已知一个图的顶点集 V=1,2,3,4,5,6,7；边集 E=（ ）3, （ ）5, （ ）8, （ ）10, （ ）6, （ ）15,
4、（ ）12, （ ）9, （ ）4, （ ）20, （ ）18, （ ）25，用克鲁斯卡尔算法得到最小生成树，则在最小 生成树中依次得到的各条边为（ ）。A(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 B(1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9 C(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 D(1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20 正确答案是：A11、在二叉树结点的先序序列、中序序
5、列和后序序列中，所有叶子结点的先后顺序（ ）A 都不相同 B 完全相同 C 先序和中序相同，而与后序不同 D 中序和后序相同，而与先序不同 正确答案是：B12、k 层（ ）二叉树的结点总数最多为（ ）。A2k-1B2K+1 C2K-1 D2k-1 正确答案是：A13、设有一个二维数组 Amn （ ），假设 A00存放位置在 600，A33存放位置在 678， 每个元素占一个空间，则 A23的存放位置是（ ）。A658 B648 C633 D653 正确答案是：C14、设有 6 个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。A5 B6 C7 D8 正确答案是：A15、采用开放定址法
6、处理散列表的冲突时，其平均查找长度（ ）。 A 低于链接法处理冲突 B 高于链接法处理冲突 C 与链接法处理冲突相同 D 高于二分查找正确答案是：B16、假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关键字存入散列表中，至少要 进行（ ）次探测。AK-1 次 BK 次 CKl 次 DK(K+1)/2 次 正确答案是：D17、若有 18 个元素的有序表存放在一维数组 A19中，第一个元素放 A1中，现进行二分查 找，则查找 A3的比较序列的下标依次为（ ）。A1，2，3 B9，5，2，3 C9，5，3 D9，4，2，3 正确答案是：D18、对线性表，在下列哪种情况下应当采用链表表示？
7、（ ）A 经常需要随机地存取元素 B 经常需要进行插入和删除操作 C 表中元素需要占据一片连续的存储空间 D 表中元素的个数不变正确答案是：B19、树最适合用来表示（ ）。A 有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据正确答案是：C20、如表 r 有 100000 个元素，前 99999 个元素递增有序，则采用（ ）方法比较次数较少。A 直接插入排序 B 快速排序 C 归并排序 D 选择排序正确答案是：A21、一散列表长度 m 为 100，采用除留余数法构造散列函数，即 H（ ）=K%P （ ）,，为使散列 函数具有较好的性能，P 的选择应是（
8、 ）。A99 B100 C97 D93 正确答案是：C22、从一个长度为 n 的顺序表中删除第 i 个元素（ ）时，需向前移动的元素个数是（ ）。An-i Bn-i+1 Cn-i-1 Di 正确答案是：A23、在一个单链表 HL 中，若要在当前由指针 p 指向的结点后面插入一个由 q 指向的结点， 则执行如下（ ）语句序列。Ap=q; p-next=q; Bp-next=q; q-next=p; Cp-next=q-next; p=q; Dq-next=p-next; p-next=q; 正确答案是：D24、对一棵有 100 个结点的完全二叉树按层编号，根结点编号为 1，则编号为 49 的结点
9、的父结点的编号为（ ）。A24 B5 C98 D99 正确答案是：A25、从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。AO(n) BO(1) CO(log2n) DO(n2) 正确答案是：C二、多选题共 4 题，20 分1、以下哪些是队列的基本运算？（ ） A 在队列第 i 个元素之后插入一个元素 B 从队头删除一个元素 C 判断一个队列是否为空 D 读取队头元素的值 E 将队列中的元素排序正确答案是：BCD2、以下数据结构中哪一个是线性结构？（ ） A 有向图 B 队列 C 线索二叉树 D 线性表 E 栈正确答案是：BDE3、若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以
10、穿插进行，则不可能出现的出栈序列为（ ）。 A3，2，6，1，4，5 B3，4，2，1，6，5 C1，2，5，3，4，6 D5，6，4，2，3，1 E6，5，4，3，2，1 正确答案是：ACD4、对一个算法的评价，主要包括如下（ ）方面的内容。 A 健壮性和可读性B 并行性C 正确性 D 时空复杂度E 界面友好性 正确答案是：ACD三、判断题共 15 题，30 分1、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 A 错误B 正确 正确答案是：B2、为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。 A 错误B 正确 正确答案是：B3、线性表若采用链式存储表
11、示, 在删除时不需要移动元素。 A 错误B 正确 正确答案是：B4、一个广义表的表头总是一个广义表。 A 错误B 正确 正确答案是：A5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 A 错误B 正确 正确答案是：A6、若一棵二叉树的任一非叶子结点的度为 2，则该二叉树为满二叉树。 A 错误B 正确 正确答案是：A7、快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 A 错误B 正确 正确答案是：B8、图 G 的某一最小生成树的代价一定小于其他生成树的代价。 A 错误B 正确 正确答案是：A9、进行折半搜索的表必须是顺序存储的有序表。 A 错误B 正确 正确答案是：B10、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 A 错误B 正确 正确答案是：B11、线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 A 错误B 正确 正确答案是：B12、线性表的长度是线性表所占用的存储空间的大小。 A 错误B 正确 正确答案是：A13、在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。 A 错误B 正确 正确答案是：A14、顺序表用一维数组作为存储结构，因此顺序表是一维数组。 A 错误B 正确 正确答案是：A15、有回路的有向图不能完成拓扑排序。 A 错误B 正确 正确答案是：B
