《数据结构教学资料》期末复习卷(赵)

《《数据结构教学资料》期末复习卷(赵)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.是非题（正确的打“J”，错误的打“X”。）1.数据结构可用三元式表示（D,S,P）。其屮：D是数据对象，S是D上的关系，P是对D的基本操作集。2.线性表的链式存储结构具有可直接存取表中任一元素的优点。3.队列是数据对象特定的线性表。4.二叉树是一棵结点的度最大为二的树。5.邻接表可以用以表示无向图，也可用以表示有向图。6.可从任意有向图小得到关于所有顶点的拓扑次序。7.一棵无向连通图的生成树是其极大的连通子图。8.二叉排序树的查找长度至多为log2n。9.对于一棵m阶的B树，树中每个结点至多有m个

2、关键字。除根之外的所有非终端结点至少有「m/2]-1个关键字。10.对于目前所知的排序方法，快速排序具有最好的平均性能。11•顺序存储方式的优点是存储密度大，且插入、删除运算效率高。12.二维数组是其数据元素为线性表的线性表。13.连通图G的生成树是一个包含G的所有n个顶点和n・l条边的子图。14.折半查找不适用于有序链表的查找。15.完全二叉树必定是平衡二叉树。16.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。17.队列是与线性表完全不同的一种数据结构。18.平均查找长度与记录

3、的查找概率有关。19.广义表的表头和表尾都有可能是原子或广义表。20.算法的时间复杂性越好，可读性就越差；反Z,算法的可读性越好，则时间复杂性就越差。二.选择题1.若广义表LS满足Head(LS)==Tail(LS),则LS%()。A.()B.(())C.((),())D.((),(),())2.递归程序可借助于（）转化为非递归程序。a:线性表b:栈c:队列d:数组3.在下列数据结构中（）具有先进先出(FIFO)特性,）具有先进后出（FTLO）特性。a:线性表b:栈c:队列d:广义表4.假设用于通讯的

4、电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14o若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左32的字符编码是（）。a:00b:01c:10d:11e:Oilf:110g:1110h:llll5.对二叉排序树按（）可得到有序序列。a:层次遍历b:前序遍历c:中序遍历d:后序遍历6.已知某树的先根遍历次序为abcdefg,后根遍历次序为cdebgfao若将该树转换为二叉树，其后序遍历次序为（）oa:abcdefgb:cdebgfac:cdegbf

5、ad:edcgfba7.对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子，其编号是（）。编号为n的结点若存在双亲，其编号是（）。a:n/2b:2nc:2n-ld:2n+le:nf:2（n+l）8.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（）的路径。a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小9.哈希表的查找效率取决于（）0a:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是10.从逻辑上可以把数据结构分成（）。A.动态结构和静态结构B.顺

6、序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型11.在计算递归函数时，如不用递归过程，应借助于（）这种数据结构。A.线性表B.栈C.队列D.双向队列12.若己知某二叉树的中序和后序遍历序列分别BCAEFD和CBFEDA,则该二叉树的先序序列为（）。A.ABCDEFB.ABDCEFC.ABDCFED.ACBDEE13.当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中（）为佳。A.起泡排序B.快速排序C.直接插入排序D.简单选择排序14.若从二叉树的根结点到其它任一结点的

7、路径上所经过的结点序列按其关键字递增有序,则该二叉树是（）。A.二叉排序树B.赫夫曼树C.堆D.平衡二叉树15.下图所有可能的拓扑序列有（）种。D.516.下列排序算法中，（）算法可能会出现:初始数据为正序时,A.堆排序B.起泡排序花费的时间反而最多。D.快速排序17.右图为一棵3阶B■树。在该树上插入元素15后的B■树是（）。C•归并排序18.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为ml、m2和m3,则与森林F对应的二叉树根结点的右子树上的结点个数是A.mlB.ml+m2C.m3D.

8、m2+m319•根据插入次序（80,90,100,110,图（）是最终变化的结果。若仍以该插入次序建立平衡二叉树Oa:85,70,图（b:75,60,72）建立二叉排序树q是最终变化的结果。728075906070851001107210100io)o(3062)a:(19,20)(3845)(70,89)62)70(89)b:(45))e:3070)(19,20)(4562)(89)30(1920)d:(19)(70)(38))(62(89)/20)