数据结构李春葆习题与解析

1、数据结构C语言篇一习题与解析修订版清华大学出版社一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科.1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为K,R,其中 K 是的有限集,R 是 K上的有限集.1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3 .在数据结构中,从逻辑上可以把数据结构分成.A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构4 .线性结构的顺序存储结构是一种

2、A 的存储结构,线性表的链式存储结构是一种 B 的存储结构.A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5 算法分析的目的是 C,算法分析的两个主要方面是 AB1A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改良 D.分析算法的易懂性和文档性2A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性 D.数据复杂性和程序复杂性6.计算机算法指的是 C,它必须具备输入、输出和 B 等 5 个特性.1A.计算方法 B.排序方法 C.解决问题的有限运算序列D.调度方法2A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性

3、和稳定性 D.易读性、稳定性和平安性7.线性表的逻辑顺序与存储顺序总是一致的,这种说法 B.A.正确 B.不正确8 线性表假设采用链式存储结构时,要求内存中可用存储单元的地址D.A.必须连续的B.局部地址必须连续的C.一定是不续的D连续不连续都可以9 .以下的表达中,正确的选项是 B.A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表先进先出10 .每种数据结构都具备三个根本运算：插入、删除和查找,这种说法 B.A.正确 B.不正确填空题1.数据逻辑结构包括三种类型线性结构、树形结构和图形结构,树形结构和图形结构合称为非线性结卞勾o2 .在线性结构中,第一个结点没有

4、前驱结点,其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点,其余每个结点有且只有 1 个后续结点.3 .在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点,其余每个结点的后续可以任意多个.4 .在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个.5 .线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存队列的操作方式是 D.先进后出栈的操作方式是 C.在多对多关系.6 .算法的五个重要特性是有穷性、确定性、可行性、输入、输出7 .下面程序段的时间复杂度是 O(m*n)for(i=0;in;i+

5、)for(j=0;jm;j+)Aij=0;8 .下面程序段的时间复杂度是 O(n).i=s=0;while(sn)1+;/*i=i+1*/s+=i;/*s=s+i*/9 .下面程序段的时间复杂度是 O(n2).s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;10.下面程序段的时间复杂度是 O(log3n)i=1;while(itop!=0B.ST-top=0C.ST-top!=mD.ST-top=m6.判断一个栈 ST最多元素为 m为满栈的条件是 D.A.ST-top!=0B.ST-top=0C.ST-top!=m-1D.ST-top=m-17 栈的特

6、点是 B,队列的特点是 A.A.先进先出,后进后出 B.先进后出,后进先出8 .一个队列的入队序列是 1、2、3、4,那么队列输出序列是 BA.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、19 .判断一个队列 QU最多元素为 m为空的条件是 C.11 判断一个循环队列 QU最多元素为 m为空的条件是A.QU-rearQU-front=mC.QU-front=QU-rear110.判断一个队列 QU最多元素为A.A. QU-rearQU-front=mC.QU-front=QU-rear1B. QU-rearQU-front1=mD.QU-frontQU-rear+m为满队

7、列的条件是C. QU-rearQU-front1=mD.QU-frontQU-rear+A.QU-front=QU-rearB.QU-front!=QU-rearC. QU-front=(QU-rear+1)%mD.QU-front!=(QU-rear+1)%m12.判断一个循环队列 QU(最多元素为 m)为满队列的条件是.A.QU-front=QU-rearB.QU-front!=QU-rearD. QU-front!=(QU-rearC. QU-front=(QU-rear+1)%m+1)%m13 循环队列用数组 A0,m-1存放其元素值,其头尾指针分别是front 和 rear,那么当前

8、队列中的元素个数是.A.(rearfront+m)%mB.rearfront+1C.rearfront1D. rearfront14.栈和队列的共同点是.A.都是先进后出 B.都是先进先出C.只允许在端点处插入、删除元素 D.没有共同点填空题1.向量、栈和队列都是结构,可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入元素和删除元素.2在一个长度为 n的向量中的第 i个元素(1wVn)之前插入一个元素时,需向后移动个元素.3 .在一个长度为 n 的向量中的删除第 i 个元素(iwiwn)时,需要向前移动个元素.4 .向栈中压入元素的操作是.5 .对栈进行退栈时的操作

9、是.6 .在一个循环队列中,队首指针指向队首元素的.7 .从循环队列中删除一个元素时,其操作是.8 .在具有 n 个单元的循环队列中,队满时共有个,元素的.9 .一个栈的输入序列是 12345,那么栈的输出序列 43512 是.10 .一个栈的输入序列是 12345,那么栈的输出序列 12345 是.三、链表单项选择题1.不带头结点的单链表 head 为空的判定条件是.A.head=NULLB.head-nxt=NULLC.head-next=headD.head!=NULL2 .带头结点的单链表 head 为空的判定条件是.A.head=NULLB.head-nxt=NULLC.head-n

10、ext=headD.head!=NULL3 .非空的循环单链表 head 的尾结点由 p 所指向满足.A.p-next=NULLB.p=NULLC.p-next=headD.p=head4 .在循环双链表的 p 所指结点之后插入 s 所指结点的操作是.A. p-right=s;s-left=p;p-right-left=s;s-right=p-right;B. p-right=s;p-right-left=s;s-left=p;s-right=p-right;C. s-left=p;s-right=p-right;p-right=s;p-right-left=s;D. s-left=p;s-r

11、ight=p-right;p-right-left=s;p-right=s;所指结点的前驱结点,假设在 p 所指结点是 q 在一个单链表中,5.q 和 p 之间插入 s 结点,那么执行.A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;6.在一个单链表中,p 所指结点不是最后结点,在 p 之后插入 s 所指结点,那么执行.A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C. s-next=p-next;p=s;7.在一个单链

12、表中,假设删除 p 所指结点的后续结点,那么执行.A.p-next=p-next-next;p-next;=pB.p-next=p-next-next;D. p=p-next-next;C. p-next=p-next;结点时,在查找成 n 个结点的单链表中查找其值等于 x9.从一个具有个结点.功的情况下,需平均比拟D. (n+1)/2C.(n-1)/2B.n/2A.n个结点的有序单链表中插入一个新结点并仍然有序在一个具有 n10.的时间复杂度是2n)D.O(nlogC.O(nB.O(n)A.O(1)2个元素的向量,建立一个有序单链表的时间复杂度给定有 11.n 是.2)C.O(nD.O(nl

13、ogn)A.O(1)B.O(n)212.向一个栈顶指针为 HS 的链栈中插入 s 所指结点,那么执行.A.HS-next=s;B.s-next=HS-next;HS-next=s;C.s-next=HS;HS=s;D.s-next=HS;HS=HS-next;D.p-next=s;s-next=p;13.从一个栈顶指针为 HS 的链栈中删除一个结点,用 x 保存被删除结点的值,那么执行.A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;14 在一个链队中,假设 f 和 r 分别为队首和队尾指针

14、,插入 s 所指结点,那么执行.A.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;15.在一个链队中,假设 f 和 r 分别为队首和队尾指针,删除一个结点,那么执行.A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;填空题1.单链表是的链接存储表示.2 .可以使用表示树形结构.3 在双链表中,每个结点有两个指针域,一个指向,另一个指向4.在一个单链表中,p 所指结点之前插入 s 所指向结点,可执行如下操作：p-next=s;(3)t=p-data;(4)p-data=;(5)s-data

15、=;5 在一单链表中,删除 p 所指结点时,应执行以下操作：(1)q=p-next;p-data=p-next-data;(3)p-next=;(4)free(q);6.带头结点的单链表 head 为空的条件是.7 .在一个单链表中,p 所指结点之后插入 s 所指向结点,应执行 s-next=和p-next=的操作.8 .非空的循环单链表 head 的尾结点(由 p 所指向),满足.9 在栈顶指针为 HS 的链栈中,判定栈空的条件是.10.在栈顶指针为 HS 的链栈中,计算该链栈中结点个数的函数11 在 HQ 的链队中,判定只有一个结点的条件是12 在 HQ 的链队中,计算该栈链中结点个数的函

16、数是3.空串是,其长度等于四、串单项选择题1.空串与空格串是相同的,这种说法.A.正确 B.不正确2 .串是一种特殊的线性表,其特殊性表达在.A.可以顺序存储 B.数据元素是一个字符C.可以链接存储 D.数据元素可以是多个字符3 .设两个字符串 p 和 q,求 q 在 p 中首次出现的位置的运算称作.A.连接 B.模式匹配 C.求子串 D.求串长4 .设串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)

17、,subs(s1,len(s2),2)的结果串是.A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF填空题式方储存的本基最种两的串 1.2.两个串相等的充分必要条件是5 .设 s=IAMATEACHER,其长度是.6 .设 si=GOOD,s2=,s3=BYE!,那么 si、s2 和 s3 连接后的结果是.五、数组与稀疏矩阵单项选择题1.常对数组进行的两种根本操作是.A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引2 .二维数组 M 的成员是 6 个字符每个字符占一个存储单元组成的串,行下标 i 的范围从0 到 8,列下标 j 的范围从 1 到 10,那么存放 M

18、 至少需要 1 个字节；M 的第 8 列和第 5行共占 2 个字节；假设 M 按行优先方式存储,元素 M85的起始地址与当 M 按列优先方式存储时的 3 元素的起始地址一致.1A.90B.180C.240D.540D.603 .二维数组 M 的成员是 4 个字符每个字符占一个存储单元组成的4.空格串是,其长度等于C.54B.114A.10823A.M85B,M310C.M58D.M09串,行下标 i 的范围从0 到 4,列下标 j 的范围从 0 至 U5,M 按行存储时元素 M35的起始地址与 M 按列存储时元素的元素的起始地址一致.A.M24B,M34C,M35D,M444 .数组 A 中,

19、每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1 至10,从首地址 SA 开始连续存放在存储器内,存放该数组至少需要的单元素A.80B.120C.240D.2705 .数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1至10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A85的起始地址为.A.SA+141B.SA+144C.SA+222D.SA+2256 .数组 A 中,每个元素的长度为 3 个字节,行下标 i 从 1 到 8,列下标 j 从 1至10,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A

20、58的起始地址为.SA+2257 .稀疏矩阵一般的压缩存储方法有两种,即.A,二维数组和三维数组 B,三元组与散列C,三元组与十字链表 D,散列和十字链表8 .假设用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点.A.正确 B.不正确9 .设矩阵 A 是一个对称矩阵,为节省存储,将其下三角局部按行序存放在一信数组 B1,n(n-1)/2中,对下三角局部中任一元素 a(inj),j在一组数组 B 的下标位置 k 的值是.A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j填空题1 .二维数组

21、 Amn采用行序为主方式存储,每个元素占 k 个存储单元,并且第一个元素的存储地址是 LOC(A00),那么 Aij的地址是O2 .二维数组 A1020采用列序为主方式存储,每个元素占一个存储单元,并且 A00的存储地址是 200,那么 A610的地址是.3 .二维数组 A10.205.20采用行序为主方式存储,每个元素占 4 个A.SA+141B.SA+180C.SA+222D.的地址 A189,那么 1000 的存储地址是 A105存储单元,并且.4 .有一个 10 阶对称矩阵 A,采用压缩存储方式(以行为主存储,且LOC(A00)=1),那么A85的地址是.5 .设 n 行 n 列的下三

22、角矩阵 A 已压缩到一维数组 S1.n*(n+1)/2中,假设按行序为主存储,那么Aij对应的 S 中的存储位置是.6 .一个稀疏矩阵如下图,那么对应的三元数组表示为.0002030050010000八、树形结构单项选择题1.如下图的 4 棵二叉树中,不是完全二叉树.ABCD3 .在线索化二叉树中,t 所指结点没有左子树的充要条件是.A.t-left=NULLB.t-ltag=1C.t-ltag=1 且 t-left=NULLD.以上都不对4 .二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法.A.正确B.错误二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前 5.

23、面,这种说法.A.正确 B.错误6 .由于二叉树中每个结点的度最大为 2,所以二叉树是一种特殊的树,这种说法.A.正确 B.错误7 .设高度为h的二叉树上只有度为0和度为2的结点,那么此类二叉树中所包含的结点数至少为.A.2hB.2h-1C.2h+1D.h+18 .如下图二叉树的中序遍历序列是.A.abcdgefB.dfebagcC.dbaefcgD.defbagc9 .某二叉树的后序遍历序列是 dabec,中序遍历序列是 debac,前序遍历序歹!J 是.A.acbedB.decabC.deabcD.cedba10 .如果 T2 是由有序树 T 转换而来的二叉树,那么 T 中结点的前序就是

24、T2 中结点的.A.前序B.中序 C.后序D.层次序11 如果 T2 是由有序树 T 转换而来的二叉树,那么 T 中结点的后序就是 T2 中结点的.A.前序 B,中序 C,后序 D.层次序12 某二叉树的前序遍历结点访问顺序是 abdgcefh,中序遍历结点访问顺序是 dgbaechf,那么其后序遍历结点访问顺序是.A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca13 .二叉树为二叉排序树的充分必要条件是任一结点的值均大于其左孩子的值、小于其右孩子的值,这种说法.A.正确 B.错误14 .根据二叉树的定义,具有 3 个结点的二叉树有种.A.3B.4C.5D.61

25、5 .如下图二叉树的中序遍历序列是.16 .树的根本遍历策略可分为先根遍历和后根遍历；二叉树根本遍历策略可分为先序遍历、中序遍历和后序遍历.这时,我们把由树转化得到的二叉树叫做这棵树对应的二叉树.结论是正确的.A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefghA.树的先根遍历序列与二叉树的先序遍历序列相同树的后根遍历序列与二叉树的后序遍历序列相同 B.C.树的先根遍历序列与二叉树的中序遍历序列相同D,以上都不对17 .深度为 5 的二叉树至多有个结点.A.16B.32C.31D.1018 .在一非空二叉树的中序遍历序列中,根结点的右边.A,只有右子树上的所有结点

26、B,只有右子树上的局部结点C,只有左子树上的所有结点 D,只有左子树上的局部结点19 .树最适合用来表示.A.有序数据元素 B,无序数据元素C,元素之间具有分支层次关系的数据 D,元素之间无联系的数据20 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序.A.不发生改变 B.发生改变 C,不能确定D,以上都不对21 .实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最正确方案是二叉树采用存储结构D.顺序存储结构22 .对于一个满二叉树,m 个树叶,n 个结点,深度为 h,那么A.n=h+mB.h+m=2nC.m=h-1D.h-1n=223.如果某二叉树的前序为 stuwv,中序

27、为 uwtvs,那么该二叉树的后序.A.uwvtsB.vwutsC.wuvtsD.wutsv25 .如下图的 T2是由有序树 T1转换而来的二叉树,那么树 T1有个叶结点.A.4B.5C.6D.726 .设 n、m 为一棵二叉树上的两个结点,在中序遍历时,n 在 m 前的条件是.A.n 在 m 右方 B.n 是 m 祖先 C.n 在 m 左方D.n 是 m 子孙27.线索二叉树是一种结构.三叉链表 C.广义表存储结构 B.二叉链表 A.D.线性填空题有一棵树如下图,答复下面问题：1.;点是(1)这棵树的根结；是这(2)棵树的叶子结点;(3)结点 c 的度是I1;(4)这棵树的度是;(5)这棵树

28、的深度是;的子女是(6)结点 c.)结点 c 的父母结点是(7 差叉树的三要个主出 2.指树和二.、别从概念上讲,树与二叉树是二种不同的数据结构,将树转化为二叉3.树的根本目的是中,如图 T4.一棵二叉树的结点数据采用顺序存储结构,存储于数组.所示,那么该二叉树的链接表示形式为151314101112853467912202118191617eafdgcjihbA.逻辑B.逻辑和存储C.物理5 .深度为 k 的完全二叉树至少有个结点,至多有个结点,假设按自上而下、从左到右次序给结点编号(从 1 开始),那么编最小的叶子结点的编号是.6 .在一棵二叉树中,度为零的结点的个数为 n,度为 2 的结

29、点的个数.为 n,那么有 n=.0 02个结点的满 n 个结点；一棵有层最多有 k 一棵二叉树的第 7.二叉树共有个叶子和个非终端结点.8 .结点最少的树为,结点最少的二叉树为.9 .现有按中序遍历二叉树的结果是 abc,问有种不同形态的二叉树可以得到这一遍历结果,这些二叉树分别是10 .根据二叉树的定义,具有三个结点的有树叉二.种不同的形态,它们分别是由如下图的二叉树,答复以下问题：11.；(1)其中序遍历序列(2)其前序遍历序列3()其后序遍历序列；(4)该二叉树的中序线索二叉树为;(5)该二叉树的后序线索二叉树为(6)该二叉树对应的森林是12.一棵树如下图,其孩子兄弟表示为为结点权值所构

30、造的哈夫,1812,106,7,413.以数据集,5.曼树为,具带权路径长度为九、图 1.在一个图中,所有顶点的度数之和等于所有边数的倍D.4C.2A.1/2B.12.在一个有向图中,所有顶点的入度之和等于所有顶点的出度这和倍.A.1/2B.1C.2D.43 .一个有 n 个顶点的无向图最多有条边.A.nB.n(n-1)C.n(n-1)/2D.2n4 .具有 4 个顶点的无向完全图有条边.A. 6B. 12C. 16D. 205 .具有 6 个顶点的无向图至少应有条边才能保证是一个连1 通图.A.5B.6C.7D.86 .在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要条边.A.nB.

31、n+1C.n-1D.n/27 .对于一个具有 n 个顶点的无向图,假设采用邻接矩阵表示,那么该矩阵的大小是.22D.nC.n-1A.nB.(n-1)8.对于一个具有 n 个顶点和e 条边的无向图,假设采用邻接矩阵表示,那么表头向量的大小是 1;所有邻接矩阵中的结点总数是2.1A.nB.n+1C.n-1D.n+e2A.e/2B.eC.2eD.n+e出发按深度搜索法 a 一个图如下图,假设从顶点 9.;按宽度 1 进行遍历,那么可得到顶点序列为.搜索法进行遍历,那么可得到顶点序列为 2aedfcb1A.abecdfB.acfebdC.aebcfdD.一有向图的邻接表存储结构如图 10.所示从根据有

32、向图的深度优先遍历算法,1().1v1 顶点出发,所得到的顶点序列是顶点出发,所得到的顶 v1(2)根据有向图的宽度优先遍历算法,从.2 点序列是B.v1,v2,v3,v4,v5A.v1,v2,v3,v5,v41D.v1,v4,v3,v5,v2C.v1,v3,v4,v5,v2B. v1,v3,v2,v4,v52A.v1,v2,v3,v4,v5D.v1,v4,v3,v5,v2C. v1,v2,v3,v5,v4树叉二类似于度优先遍历算法存 11.采用邻接表储的图的深.的按层 D.后序遍历先序遍历 B.中序遍历 C.A.遍历树叉于二类先遍历算法似宽储邻 12.采用接表存的图的度优：的按层 D.后序遍

33、历中序遍历先序遍历 A.B.C.遍历.13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用2A.abcedfC.aebcfdD.B.abcefdacfdebA.求关键路径方法B.求最短路径的 Dijkstra 方法1.n 个顶点的连通图至少条边.2 在无权图 G 的邻接矩阵中,假设vi,vj或vi,vj属于图 G 的边集,那么对应元素 Aij等于,否那么等于.3 在无权图 G 的邻接矩阵中,假设 Aij等于 1,那么等于 Ajio4 .图 G 的邻接表如下图,其从 v1 顶点出发的深度优先搜索序列为,其从 v1 顶点出发的宽度优先搜索序列5 .一图的邻接矩阵表示,计算第 i

34、个结点的入度的方法6 .一图的邻接矩阵表示,删除所有从第 i 个结点出发的边的方法十、查找单项选择题.C.宽度优先遍历算法填空题D,深度优先遍历算法A,散列存储 B.顺序存储或链接存储C.压缩存储 D.索引存储2 .对线性表进行二分查找时,要求线性表必须.A,以顺序方式存储 B,以顺序方式存储,且结点按关键字有序排列C.以链接方式存储 D.以链接方式存储,且结点按关键字有序排列3 .采用顺序查找方法查找长度为 n 的线性表时,每个元素的平均查找长度为.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为 n 的线性表时,每个元素的平均查找长度为.2)B.O(nlo

35、gn)C.O(n)A.O(nD.O(logn)225.二分查找和二叉排序树的时间性能.A.相同 B.不相同6.有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为 82 的结点时,次比拟后查找1成功.A.1B.2C.4D.81 顺序查找法适合于存储结构为的线性表.7 .设哈希表长 m=14,哈希函数 H(key)=key.表中有 4 个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空如用二次探测再散列处理冲突,关键字为 49 的结点的地址是A.8B.3C.5D.98 .有一个长度为 12 的有序

36、表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比拟次数为.A.35/12B.37/12C.39/12D.43/129 .采用分块查找时,假设线性表中共有 625 个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分个结点最正确地.A.10B.25C.6D.62510 .如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用查找方法.A.分块 B.顺序 C.二分 D.散列填空题1.顺序查找法的平均查找长度为；二分查找法的平均查找长度为；分块查找法(以顺序查找确定块)的平均查找长度为；分块查找法(以二分查找确定块)的平均查找长度为哈

37、希表查找法采用链接法处理冲突时的平均；查找长度为.2 .在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法3 .二分查找的存储结构仅限于,且4 .在分块查找方法中,首先查找,然后再查找相应的.5 .长度为 255 的表,采用分块查找法,每块的最正确长度是.6 .在散列函数 H(key)=key%p 中,p 应取.7 .假设在有序线性表 A1.20上进行二分查找,那么比拟一次查找成功的结点数为,那么比拟二次查找成功的结点数为,那么比拟三次查找成功的结点数为,那么比拟四次查找成功的结点数为,那么比拟五次查找成功的结点数为,平均查找长度为.8 .对于长度为 n 的线性表,假设进行顺序查找,

38、那么时间复杂度为； 假设采用二分法查找,那么时间复杂度为；1/2),(假设总块数和每块长度均接近 n 那么时间复杂度假设采用分块查找为.9 .在散列存储中,装填因子口的值越大,那么；0c的值越小,那么.十一、内排序1.在所有排序方法中,关键字比拟的次数与记录的初始排列次序无关的是.A.希尔排序 B.起泡排序 C.插入排序 D.选择排序2 .设有 1000 个无序的元素,希望有最快的速度挑选出其中前 10 个最大的元素,最好采用排序法.A.起泡排序 B.快速排序 C.堆排序 D.基数排序3 .在待排序的元素序列根本有序的前提下,效率最高的排序方法A.插入排序 B.选择排序 C.快速排序 D.归并

39、排序4 .一组记录的排序码为(46,79,56,38,40,84),那么利用堆排序方法建立的初始堆为.A.79,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,385 .一组记录的排序码为(46,79,56,38,40,84),那么利用快速排序方法,以第一个记录为基准得到的一次划分结果为.84C.40,38,46,56,79,84D,40,38,46,84,56,796 .一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有 5 个长度为 2 的有序表,按归并排序的方

40、法对该序列进行一趟归并后的结果为.A.16253548234079823672B,16253548798223364072C.16254835798223364072D,162535487923364072827 .排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比拟,将其放入已排序序列的正确位置上的方法,称为.A.希尔排序 B,起泡排序 C,插入排序 D.选择排序8 .排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为.A.希尔排序 B,归并排序 C,插入排序 D.选择排序9 .用某种排序方法对线性表(25,84,21,4

41、7,15,27,68,35,20)进行排序时,元素序列的变化情况如下：20,35,68,27,15,47,21,84,25)1(.20,15,21,25,47,27,68,35,84,56,79,46,38,B.4084,79,56,46,40,A.38.(3)15,20,21,25,35,27,47,68,84(4)15,20,21,25,27,35,47,68,84那么采用的排序方法是.A.选择排序 B,希尔排序 C.归并排序 D.快速排序10 .以下几种排序方法中,平均查找长度最小的是.A.插入排序 B,选择排序 C.快速排序 D.归并排序11.以下几种排序方法中,要求内存量最大的是.A

42、.插入排序 B,选择排序 C.快速排序 D.归并排序12 .快速排序方法在情况下最不利于发挥其长处.A.要排序的数据量太大 B.要排序的数据中含有多个值C.要排序的数据已根本有序 D.要排序的数据个数为奇数填空题1.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第七个记录 60 插入到有序表时,为寻找插入位置需比拟次.2 .在利用快速排序方法对(54,38,96,23,15,72,60,45,83)进行快速排序时,递归调用而使用的栈的所能到达的最大深度为共需递归调用的次数为,其中第二次递归调用3 .在堆排序、快速排序和归并排序中,假设只从存储空间考

43、虑,那么应首先选取方法,其次选取方法,最后选取方法；假设只从排序结果的稳定性考虑,那么应选取方法；假设只从平均情况下排序最快考虑,那么应选取方法；假设从最坏情况下排序最快并且要节省内存考虑,贝 U 应选取方法.4 .在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有.I15.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比拟次数最少的排序是,需要内存量最多的是.6.在堆排序和快速排序中,假设原始记录接近正序或反序,那么选用,假设原始记录无序,那么选用.7.在插入排序和选择排序中,假设初始数据根本正序,那么选用假设初始数据根本反

44、序,那么选用,8.对 n 个元素的序列进行起泡排序时,最少的比拟次数是答案一、绪论选择题：1.A.B.2.B.Do3.Co4.A.B.5.C.A+B.6.C.Bo7.Bo8.D.9.Bo10.Bo是对一组记录进行快速排序.填空题：1.线性结构,树形结构,图形结构,非线性结构.2.没有,1,没有,1.3.前驱,1,后续,任意多个.4.任意多个.5.一对一,一对多,多对多.6. 有穷性,确定性,可行性,输入,输出.7.O(m*n).8.2).(n)n.9.OO(10.O(logn).3二、线性表选择题：1.Bo2.Co3.Co4.Ao5.B.6.D.7. B,A.8.BoC14.A13.C12.A11.A10.C9.填空题：1.线性,任何,栈顶,队尾,队首.2.n-i+1.3.n-io4.先栈顶指针,后存入元素.5.先取出元素,后移动栈顶指8. n-1.9.不可能的.10.可能的.三、链表选择题：1.A.2.B.3.Co4.Do5.C.6.B.7.A.9.Do10. B11.C12.C13.D14.B15.C填空题：1.线性表.2.双链表.3.前驱结点,后续结点11. p-next,s-data,t.5.p-next-next.6.head-next=NULL.7.p-next,s.8.