数据结构__河北工业大学__内部汇总

1、第一二章一 填空1. 衡量算法效率的两个重要指标称为算法的_时间复杂度 _和 空间复杂度 2. 一个算法应具有 _有穷性，确定性，可行性，输入和输出 _这五个特性。3. 线性表的长度是指 _线性表中元素的个数 _。4. 在线性表的顺序存储中，元素之间的逻辑关系是通过_元素的存储(物理)地址 _决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 _指向下一个元素的指针 _ 决定的。5 在双向链表中，每个结点包含两个指针域，一个指向 前驱 结点，另一个指向 _后继 _结点。二、判断题1线性表的逻辑顺序与存储顺序总是一致的。(FALSE)2顺序存储的线性表可以按序号随机存取。(TRUE)3在线性

2、表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。( FALSE)4在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。( TRUE)5在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。( TRUE)6线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。( TRUE)三、单选题 ( 请从下列 A， B，C，D选项中选择一项 ) 1线性表是 ( ) 。(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 答：An，在任何位置上插入或删除操作都是等

3、概率的。插入一个元素时平2对顺序存储的线性表，设其长度为 均要移动表中的( )个元素。1)/2(D) n(A) n/2 (B)( n+1)/2(C) (n答：A3线性表采用链式存储时，其地址( )(A) 必须是连续的； (B) 部分地址必须是连续的；(C) 一定是不连续的； (D) 连续与否均可以。 答：D4用链表表示线性表的优点是( )。(A) 便于随机存取(B) 花费的存储空间较顺序存储少(C) 便于插入和删除(D) 数据元素的物理顺序与逻辑顺序相同答：C5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素， 则采用 ( ) 存储方 式最节省运算时间。(A) 单链表

4、(B) 双链表(C) 单循环链表(D) 带头结点的双循环链表答：D6. 循环链表的主要优点是 ( ) 。(A) 不再需要头指针了(B) 已知某个结点的位置后，能够容易找到他的直接前趋(C) 在进行插入、删除运算时，能更好的保证链表不断开(D) 从表中的任意结点出发都能扫描到整个链表 答：D7. 单链表中，增加一个头结点的目的是为了( )。(A) 使单链表至少有一个结点 (B) 标识表结点中首结点的位置(C)方便运算的实现(D) 说明单链表是线性表的链式存储答：C8. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用( )存储方式最节省 运算时间( )。(A) 单链

5、表 (B) 顺序表 (C) 双链表 (D) 单循环链表 答：B 四、简答题1 何时选用顺序表、何时选用链表作为线性表的存储结构为宜 ? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以 下几方面的考虑：1. 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜 采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2. 基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构 为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链

6、表做存储结构。并且，若链 表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素 ?答：在等概率情况下，顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均移动 (n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n以及需插入或删除的位置 i 。i 越接近 n则所需移动的结点 数越少。3 为什么在单循环链表中设置尾指针比设置头指针更好 ? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很 方便，设一带头结点的单循环链表，其尾指针为

7、 rear ，则开始结点和终 端结点的位置分别 是 rear->next->next 和 rear, 查找时间都是 O(1) 。若用头指针来表示该链表，则查找终端结点的时间为O(n) 。五、分别设计算法，实现线性表的顺序存储结构和链式存储结构的原地置逆。第三章一 单项选择题1. 栈中元素的进出原则是 ( B )先进先出后进先出栈空则进栈满则出2. 若已知一个栈的入栈序列是 1，2，3， n ，其输出序列为 p1，p2，p3， pn，若 p1=n，则 pi 为 ( C) i n=i n-i+1不确定解释：当 p1=n，即 n 是最先出栈的，根据栈的原理， n 必定是最后入栈的(事实上

8、题目已经表明了) ，那 么输入顺序必定是 1，2，3， n，则出栈的序列是 n， 3，2，1。(若不要求顺序出栈，则输出序列不确定)3. 判定一个栈 ST(最多元素为 m0)为空的条件是 ( B ) ST->top<>0 ST->top= =0 ST->top<>m0 ST->top= =m04. 在作进栈运算时 ,应先判别栈是否 （ B ）, 在作退栈运算时应先判别栈是否 （ A ） 。当栈中元素为 n 个 , 作进栈运算时发生上溢 , 则说明该栈的最大容量为 （ B ） 。为了增加内存空间的利用率和减少溢出的可能性 , 由两个栈共享一片连续的

9、内存空间时 , 应将两栈的（ D ）分别设在这片内存空间的两端, 这样 , 当 （ C ）时，才产生上溢。, :A.空 B.满 C.上溢D.下溢:A.n-1 B. nC. n+1D. n/2:A.长度 B.深度 C. 栈顶D.栈底: A. 两个栈的栈顶同时到达栈空间的中心点 .B. 其中一个栈的栈顶到达栈空间的中心点 .C. 两个栈的栈顶在栈空间的某一位置相遇 .D. 两个栈均不空 , 且一个栈的栈顶到达另一个栈的栈底5. 某堆栈的输入序列为 a, b ，c ，d, 下面的四个序列中，不可能是它的输出序列的是（D ）。A. a ，c，b， dB. b, c，d，a C. c, d ， b, a

10、 D. d, c，a， b6. 若栈采用顺序存储方式存储，现两栈共享空间V1.m ，topi 代表第 i 个栈（ i =1,2） 栈顶，栈 1 的底在 v1 ，栈 2 的底在 Vm ，则栈满的条件是（ B ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top27. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A线性表的顺序存储结构B. 队列 C. 线性表的链式存储结构 D. 栈8. 用不带头结点的单链表存储队列时 , 其队头指针指向队头结点 , 其队尾指针指向队尾结点， 则在进行删除 操作时

11、 （ A ） 。A仅修改队头指针B. 仅修改队尾指针C. 队头、队尾指针都要修改 D. 队头, 队尾指针都可能要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。A队列B 多维数组 C 栈 D. 线性表10. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除 一个元素，再加入两个元素后， rear 和 front 的值分别为多少？ （ B ）A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1二 填空题1. 线性表、 栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和

12、删除元素； 对于栈 只能在 栈顶 插入和删除元素； 对于队列只能在 队尾 插入元素， 在 队头 删除元素。2. 栈是一种特殊的线性表， 允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一 端称为 栈底 。3. 一个栈的输入序列是： 1， 2 ， 3 则不可能的栈输出序列是 _3 1 2 。4. 循环队列的引入，目的是为了克服 _队列的假溢出 。5用下标 0 开始的 N元数组实现循环队列时，为实现下标变量M加 1 后在数组有效下标范围内循环， 可采用的表达式是： M=_（M+1）%N；_6. 队列的特点是 _先进先出 。7表达式求值是 _栈应用的一个典型例子。第四五章、填充题1、一个

13、串中任意个的字符组成的子序列称为该串的子串。连续2、串的静态存储结构中的两种不同的存储方式分别是格式和 格式。定长 堆3、两个串的相等，是指两个两串的相等， 相同。长度 对应位置的字符4、已知二维数组 A 有 m行 n 列，采用行优先方式存储，每个数据元素占k 个存储单元，并且第一个元素的存储地址是 LOC(A1,1) ，则数据元素 Ai,j 的地址是 。 LOC(A1,1)+(n*(i-1)+(j-1)*k5、有一个 10 阶的对称矩阵，采用以行优先的压缩存储方式，已知元素A1,1 的地址为 1，则元素A8,5 的地址是 ，元素 A5,8 的地址是 。33 336、广义表 (a,(a,b),

14、d,e,(i,j),k)的长度是 ，深度是 。5 3二、单选题、给出字符串 A='abcd'，它的子串个数是、10、9回串、11、14给出两个串 A=' ABCD'E，、B串大于 A 串、B串小于 A 串B=' ABCdE'，它们的关系是、B 串等于 A串、B 串是 A 串的子串、设有两个串 A 和 B，求 B在 A中首次出现的位置的操作称作A 、连接 B 、求串长 C 、模式匹配 D 、求子串、设串 S1='ABCDEF'G，串 S2='PQRST'，函数 con(x,y) 返回 x 和 y 串的连接串， 函数

15、subs(s,i,j) 返 s 的从序号 i 的字符开始的 j 个字符组成的子串，而函数 len(s) 则返回串 s 的长度。那么，表达式 的结果串是 。con(subs(S1,2,len(S2),subs(S1,len(S2),2)、BCDEF、 BCDEFG、BCPQRST、 BCDEFEF、数组通常具有的两种基本操作是A 、建立与删除C 、查找与修改、索引与修改、查找与索引1到、在数组 A 中，每个数据元素10，从首地址 SA 开始连续存放在存储器中，若该数组按行优先存放时，数据元素Ai,j 的长度为3个字节，数组 A的行下标 i 从 1到 8，而列下标 j 从A8,5 的起始地址、SA

16、+141、 SA+144C、SA+225D、 SA+222D SA+(10*(8-1)+(5-1)*37. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为()A. 13B. 33C. 18D. 40B =i*(i-1)/2+j (i>=j)8. 若对 n阶对称矩阵 A以行序为主序方式将其下三角形的元素 (包括主对角线上所有元素 ) 依次存放于一维 数组 B1.(n(n+1)/2 中，则在 B 中确定 aij (i<j )的位置 k 的关系为 ( ) 。A. i*(i-1)/2+j

17、 B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+IB9. 对稀疏矩阵进行压缩存储目的是( )。A便于进行矩阵运算 B 便于输入和输出 C 节省存储空间 D 降低运算的时间复杂度C11. 已知广义表 LS (a,b,c),(d,e,f),运用 head 和 tail 函数取 出 LS 中原子 e 的运算是 ( ) 。A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)C12. 广义表( a,(b,c),d,e )的表头为( )。A. aB

18、. a,(b,c)C. (a,(b,c)D. (a)第六章一、 填空题1. 不相交的树的聚集称之为 森林 。2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树 可 采 用 孩 子 -兄弟链表(二叉链表)做存储结构，目的是利用二叉树的已有算法解决树的有关问题。3. 深 度 为 k 的 完 全 二 叉 树 至 少 有 2 k-1 个 结 点 。 至 多 有 2 k-1 个 结 点 ， 若 按 自 上 而 下 ， 从 左到 右 次序 给结 点编 号( 从 1 开始)， 则编 号最 小的 叶子 结点 的编 号是 2 k-2 +1。4. 在 一 棵 二 叉 树 中 ， 度

19、 为 零 的 结 点 的 个 数 为 n 0 ， 度 为 2 的 结 点 的 个 数 为 n 2 ， 则 有 n 0 = n 2+1 。5. 一棵 二叉 树的第 i ( i 1)层最 多有 2 i-1 个结 点； 一棵有 n(n>0 )个结 点的 满二叉 树共 有 (n+1)/2 个 叶子 和 ( n-1) /2 个 非终 端结点 。6. 现 有 按 中 序 遍 历 二 叉 树 的 结 果 为 abc ，问 有 5 种 不 同 形 态 的 二 叉 树 可 以 得 到 这 一 遍 历 结果。7. 哈夫曼树 是带权路径最小的二叉树。8. 前缀编码是指任一个字符的编码都 不是 另一个字符编码的

20、前缀的一种编码方法，是设计不等长 编码的前提。9. 以给定的数据集合 4 ，5，6，7， 10， 12，18 为结点权值构造的 Huffman 树的加权路径长度是165 。10. 树被定义为连通而不具有 回路 的(无向)图。11. 若一棵根树的每个结点最多只有 两个 孩子，且孩子又有 左、右 之分，次序不能颠倒， 则称此根树为 二叉树 。12. 高度为 k ，且有个结点的二叉树称为 二叉树。2 k -1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为 树。Huffman14. 在一棵根树中，树根是 为零的结点，而 为零的结点是 结点。入度 出度 树叶15. Huffman 树中，

21、结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。结点 树根16. 满二叉树是指高度为 k ，且有个结点的二叉树。二叉树的每一层i 上，最多有个结点。2 k -1 2二、单选题1. 具有 10 个叶结点的二叉树中有 (B) 个度为 2 的结点。(A)8 (B)9 (C)10 (D)112 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左 右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_( 3)次序的遍历实现编号。( 1)先序( 2)中序( 3)后序( 4)从根开始按层遍历3. 由 2、3、4、7 作为结点权值构造的树的加权路径长度B 。

22、A、33B、30C、36D、404. 高度为6 的满二叉树，总共有的结点数是B。A、15B、63C、20D、255. 下面描述根树转换成二叉树的特性中，正确的是 C 。A 、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子B 、根树转换成的二叉树是不唯一的，二叉树的根结点只有左孩子C 、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。D 、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子6. 如图所示的4 棵二叉树中，不是顺序二叉树的是。A 、B、 C 、D、C7. 某二叉树先序遍历的结点序列是abdgcefh ，中序遍历的结点序列是dgbaechf ，则其后序遍历的结点序

23、列是 D。A 、bdgcefhaB、 gdbecfhaC 、bdgaechfD、 gdbehfca8. 已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJ，K 按后序遍历所得到的结点序列为DCEGBFHKJI，A 按先序遍历所得到的结点序列为ABCDGEIHFJK 。9. 设 n，m为一棵二叉树上的两个结点，在中序遍历时，n在 m前的条件是 CA、 n 在 m右方B、 n 是 m祖先C、 n 在 m左方D、 n 是 m子孙10. 二叉树第 i 层结点的结点个数最多是(设根的层数为1) ：A16A ) 2i-1)2i -1C) 2iD ) 2i-111.12.树的后根遍历序列等同于该树对

24、应的二叉树的： ）先序序列 B ）中序序列 树最适合用来表示 _C）后序序列13.14.15.A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据由于二叉树中每个结点的度最大为 2，A.正确假定在一棵二叉树中， 双分支结点数为15B 16D. 元素之间无联系的数据所以二叉树是一种特殊的树，这种说法 _BB. 错误15，单分支结点数为30 个，则叶子结点数为B 个。C17D47按照二叉树的定义，具有3 个结点的不同形状的二叉树有C_种。A. 3B. 4C. 5D. 616. 深度为 5 的二叉树至多有C_个结点。A. 16B. 32C. 31D. 1017. 对一个满二叉树，

25、 m个树叶， n 个结点，深度为h，则 _DA. n=h+mB. h+m=2nC. m=h-1D. n=2 h-118.19.C. 不能确定 如果某二叉树的前根次序遍历结果为 stuwv ，中序遍历为 uwtvs ，A. 不发生改变B. 发生改变D.以上都不对那么该二叉树的后序为 _CA. uwvtsB. vwutsC. wuvtsD. wutsv任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序20.A.B. 错误21.正确在一非空二叉树的中序遍历序列中，根结点的右边A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点22

26、.已知某二叉树的后序遍历序列是dabec ，中序遍历序列是 debac，它的前序遍历序列是 _DA. acbedB. decabC. deabcD. cedba二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法23. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_C_存储结构。A. 二 叉 链 表 B. 广 义 表 存 储 结 构 C. 三 叉 链 表 D. 顺 序 存 储 结 构24. 在线索化二叉树中， t 所指结点没有左子树的充要条件是 _B_。A. t > left=NULLB. t > ltag=1C. t > ltag

27、=1 且 t> left=NULLD. 以上都不对25. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B_。 A. 正确 B. 错误26. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和 后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_A_是正确的。A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对第七章第 7 章 图一、选择题1对于一个具有 n 个顶点和 e 条

28、边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为( )A) O(n)B ) O(n+e) C ) O(n*n) D ) O(n*n*n)【答案】 B2设无向图的顶点个数为 n，则该图最多有()条边。A) n-1 B) n(n-1)/2C ) n(n+1)/2D )n2【答案】 B3连通分量指的是()A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图【答案】 B4n 个结点的完全有向图含有边的数目()A) n*nB )n(n+1)C) n/2D)n*(n-1 )答案】 D5关键路径是()A) AOE网中从源点到汇点的最长路径

29、B) AOE网中从源点到汇点的最短路径 C) AOV网中从源点到汇点的最长路径 D) AOV网中从源点到汇点的最短路径 【答案】 A 6有向图中一个顶点的度是该顶点的()A)入度 B ) 出度 C ) 入度与出度之和 D ) (入度 +出度) /2 【答案】 C7有 e 条边的无向图，若用邻接表存储，表中有()边结点。A ) e B ) 2e C ) e-1 D ) 2(e-1) 【答案】 B8实现图的广度优先搜索算法需使用的辅助数据结构为()A ) 栈 B ) 队列 C ) 二叉树 D ) 树 【答案】 B9实现图的非递归深度优先搜索算法需使用的辅助数据结构为()A ) 栈 B ) 队列 C

30、 ) 二叉树 D ) 树 【答案】 A10存储无向图的邻接矩阵一定是一个()A ) 上三角矩阵 B )稀疏矩阵 C ) 对称矩阵 D ) 对角矩阵 【答案】 C11在一个有向图中所有顶点的入度之和等于出度之和的()倍A ) 1/2B)1C) 2D) 4【答案】 B12在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()A) O(n)B ) O(n+e) C )O(n 2)D )O(n 3)【答案】 B13下列关于 AOE网的叙述中，不正确的是()A)关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整

31、个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】 B14具有 10 个顶点的无向图至少有多少条边才能保证连通（）A） 9B） 10C） 11D） 12【答案】 A15在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为（ ）22A） eB）2eC） n 2-eD）n2-2e【答案】 D16. 对于一个具有 n个顶点和 e条边的无向图， 如果采用邻接表来表示， 则其表头向量的大小为A、nB、 n+1C、n-1D、 n+e【答案】 A二、填空题1无向图中所有顶点的度数之和等于所有边数的 倍。【答案】 22具有 n 个顶点的无向完全图中包含有 条边，具有 n

32、个顶点的有向完全图中包含有条边。【答案】（ 1）n（n-1）/2 （2） n（n-1）3一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要 条边。【答案】 n-15对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为 ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为 。【答案】（ 1）O（n2） （ 2） O（n+e）6对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 和条。【答案】（ 1）e （2）2e7 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有 和结点。【答案】（ 1）出边 （2） 入边8 对于一个具有

33、n 个顶点和 e 条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的 时间复杂度依次为 和 。【答案】（ 1）O（n） （2） O（e）9对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为 和 【答案】（ 1）n （2） n-110 Prim 算法和 Kruscal 算法的时间复杂度分别为 和 。【答案】（ 1）O（n2） （ 2）O（eloge）11. 假设图 G中含有 n 个顶点， e 条边，且知每个顶点的度数为 di ，则它们三者之间满足的关系 为： 。【答案】 e=1/2 di12. 我们把图中所有顶点加上遍历时经过的所有边构成的子图称为。【答案

34、】 生成树13、有 n 个顶点的无向图，其边数最大可达，像这样的有最大边数的无向图通常被称为。【答案】 n(n-1)/2 完全无向图14、树被定义为连通而不具有的(无向)图。【答案】 回路15、对于一个图 G 的遍历，通常有两种方法，它们分别是和 。【答案】 深度优先法 广度优先法16. AOV 网中，结点表示活动 ， 边表示活动的先后顺序， AOE 网中，结点表示事件， 边表示活动 .第九章一、填充题1、折半查找法适合于的数据序列。有序2、查找表的两种基本类型分别是和 。静态查找表 动态查找表3、Hash 表查找要研究的两个主要问题分别是和 。均匀性 冲突的解决4、在各种查找方法中，平均查找

35、长度与结点个数n 无关的查找方法是 。哈希表查找法5、折半查找的存储结构仅限于，而且是 。顺序存储结构 有序的6、在哈希函数 H( key) =key MOD p 中， p 应取 。素数7、假设我们在有 20 个数据元素的有序线性表上实施折半查找，则比较五次查找成功的结点数 为 ，平均查找长度为 。5 3.7( 可以画出折半查找判定树 )8、在哈希表存储中，装填因子的值越大，则，反之装填因子的值越小，则。存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小 二、单选题1、对个结点的线性表进行查找，用顺序查找法查找的时间复杂度为。A 、 O(n2)B、 O(nlog 2n)C 、O

36、(n)D、O(log 2 n)C2 、对 n 个结点的线性表进行查找，用折半查找法查找的时间复杂度为 。A 、O(log 2n)B、 O(n)C 、O(n2)D、 O(nlog 2n)A3、折半查找不成功时，指针 Low 和 High 的关系是 。A、 Low<HighB、 Low>HighC、Low与High 无关D、Low=HighB4、设 A是一个包含有 10 个数据元素的有序数组，如果我们利用折半查找法在A中查找任意的数据元素 X， 假定在确定目标元素是否等于、小于或大于 Ai 时仅需比较一次。则平均的查找成功时间是A、1.6B、4.2C、5.5D、2.9D5 、用 Has

37、h 函数 hash=key mod size 和线性探测再散列法来将关键字 37，38，72，48， 98，56，11 装入下标范围为 0 到 6 的 Hash 表中，则该表中各关键字的次序为。A 、72，11，37，38，56，98，48B、11，48， 37， 38， 72， 98， 56C 、98，11，37，38，72，56，48D、98，56， 37， 38， 72， 11， 48D6、对线性表进行折半查找时，要求线性表必须。A、以顺序方式存储，且结点按关键字有序B 、以顺序方式存储C、以链表方式存储，且结点按关键字有序D 、以链表方式存储A7 、有一个有序表为 1，3，9， 12，

38、32，41，45，62，75，77，82，95，100，当以折半法查找值为 82 的数据元素时，查找成功的比较次数是 。A、2B、4C、11D、3B第十章一、填充题1、按排序操作中所涉及的存储器的不同，可以把排序分成和 两大类内部排序 外部排序2、主关键字是可以地标识一个数据元素的关键字。唯一3、希尔排序是属于插入排序的一种类型，它又被称为排序。缩小增量4、次关键字是用以标识数据元素的关键字。多个5、按关键字与排序结果的关系，可以把排序方法分成和 两类。稳定排序 非稳定排序6、在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中，需要内存量最大 的是 。基数排序7、在堆排序和快速排序中，如果数据元素的原始序列接近正序或反序，则选用最好，如果数据元素的原始序列无序，则最好选用 。堆排序 快速排序8、对于由 n 个数据元素构成的序列实施冒泡排序时，最少的比较次数是 。冒泡排序的结 束条件是 。n-1 刚做完的一