模拟题答案(13页).doc

《模拟题答案(13页).doc》由会员分享，可在线阅读，更多相关《模拟题答案(13页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-一、二、三、四、 模拟题答案-第 12 页五、 选择题1. 以下数据结构中哪一个是线性结构？( B ) A. 有向图 B. 队列 C. 线索二叉树 D. B树2. 在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( D )语句序列。A. p=q; p-next=q; B. p-next=q; q-next=p;C. p-next=q-next; p=q; D. q-next=p-next; p-next=q;3. 以下哪一个不是队列的基本运算？（ A ） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读

2、取队头元素的值4. 由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( B )。A 11 B.35 C. 19 D. 535. 该二叉树结点的前序遍历的序列为( C )。A. E、G、F、A、C、D、B B. E、A、G、C、F、B、DC. E、A、C、B、D、G、F D. E、G、A、C、D、F、B6. 下面关于图的存储的叙述中正确的是( B )。 A用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D用邻接矩阵法

3、存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关7. 设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果? ( B )A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z8. 一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。 A. HL=p; p-next=HL; B. p-next=HL-next; HL-next=p; C. p-next=HL; p=HL; D. p-next=

4、HL; HL=p; 9. 顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素.A. n B.n-1C. n+1 D.不确定10. 下述哪一条是顺序存储方式的优点？（ A ） A存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快11. 下列关于二叉树遍历的叙述中，正确的是( A ) 。A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序

5、最后一个结点D若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点12. k层二叉树(K=1)的结点总数最多为( A ).A2k-1 B.2K+1 C.2K-1 D. 2k-1 13. 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（ D ）个。 A1 B2 C3 D414. 对一个算法的评价，不包括如下（ B ）方面的内容。 A健壮性和可读性 B并行性 C正确性 D时空复杂度15. 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进

6、行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变16. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2 D. 1 2 317. 快速排序在最坏情况下的时间复杂度为（ D ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)18. 从二叉排序树中查找一个元素时，其时间复杂度大致为( C )。A. O(n) B. O(1) C. O(log2n) D. O(n2)19. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( C )存储方式最节省时

7、间。A.单链表 B.双链表C.带头结点的双循环链表D.单循环链表20. 下面的二叉树中，( C )不是完全二叉树。21. 栈和队列的共同特点是( A )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 22. 用链接方式存储的队列，在进行插入运算时( D )。A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改23. 树最适合用来表示( C )。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据24. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分

8、查找，则查找A3的比较序列的下标依次为( D )。A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，325. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个，A1 B2 C3 D426. 设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。A.5 B.6 C.7 D.827. 某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为（ C ）。A:O(n)B:O(nlog2n)C:O(n2)D:O(1)28. 从一个长度为n的顺序表

9、中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的平均比较次数为（ C ）。A:nB:n/2C:(n+1)/2D:(n-1)/229. 在一个长度为n的顺序表中删除第i个元素（0in-1）时，需要从前向后依次前移（ C ）个元素。A:n-iB:n-i+1C:n-i-1D:I30. 树中所有结点的度之和等于所有结点数加( C )。A:0B:1C:1D:231. 一棵具有35个结点的完全二叉树的高度为( A ), 假定空树的高度为-1。A:5B:6C:7D:832. 对于具有e条边的无向图，它的邻接表中有( D )个边结点。A:e-1B:eC:2(e-1)D:2e33. 图的深度优先搜索

10、类似于树的（A ）次序遍历。A:先序B:中序C:后序D:层次34. 设单链表中结点的结构为（data, next）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ B ）。A: s-next=p-next; p-next=s; B: q-next=s; s-next=p; C: p-next=s-next; s-next=p; D: p-next=s; s-next=q; 35. 递归调用时系统需要利用一个（ D ）来实现数据的传递和控制的转移。A: 队列 B: 优先级队列 C: 双端队列 D: 栈 36. 对待排序的元素序列进行划分，将其分为

11、左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( C )。A: 直接选择排序 B: 直接插入排序 C: 快速排序 D: 起泡排序 37. 设无向图的顶点个数为n，则该图最多有（ B ）条边。A: n-1 B: n(n-1)/2 C: n(n+1)/2 D: n(n-1) 38. 设循环队列的结构是 const int MaxSize=100; typedef int DataType; struct Queue DataType dataMaxSize; int front, rear; 若有一个Queue类型的队列Q，试问判断队列满的条

12、件应为( D )。A: Q.front=Q.rear; B: Q.front-Q.rear=MaxSize; C: Q.front+Q.rear=MaxSize; D: Q.front=(Q.rear+1) % MaxSize; 39. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。A: front=rear B: front!=NULL C: rear!=NULL D: front=NULL 40. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( A )。A: 求一个顶点的度 B: 求一个顶点的邻接点 C: 进行图的深度优先遍历 D: 进行图的广

13、度优先遍历 41. 与邻接矩阵相比，邻接表更适合于存储 ( C )。A无向图 B连通图 C稀疏图 D稠密图 42. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B） A3，2，6，1，4，5 B3，4，2，1，6，5 C1，2，5，3，4，6 D5，6，4，2，3，1 43. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A） A队列 B栈 C线性表 D有序表 44. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（ A ） A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目45. 在对n个关键字进行直接

14、选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i（i=1）趟排序之前，无序区中关键字元素的个数为（D ） Ai Bi+1 Cn-i Dn-i+1 46. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（A） Af,c,b Bf,d,b Cg,c,bDg,d,b 47. 在下面的程序段中，对x的赋值语句的频度为（ C ） For( i = 1 ; i = n ; i+ ) For( j = 1; j next=h B. p-next=NULL C. p-next-next=h D. p-data= -

15、155. 完成在双循环链表结点p之后插入s的操作是（ D ）；A p-next=s ; s-prior=p; p-next-prior=s ; s-next=p-next;B p-next-prior:=s; p-next=s; s-prior=p; s-next:=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s ;D s-prior=p; s-next=p-next; p-next-prior=s ; p-next=s;56. 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，

16、q指向一待插入结点，现要求在p前插入q，则正确的插入为（ D ）A. p-llink=q; q-rlink:=p; p-llink-rlink:=q; q-llink:=p-llink;B. q-llink=p-llink; p-llink-rlink=q; q-rlink=p; p-llink:=q-rlink; C. q-rlink=p; p-rlink=q; p-llink-rlink=q; q-rlink=p;D. p-llink-rlink=q; q-rlink=p; q-llink=p-llink; p-llink=q;57. 对于一个头指针为head的带头结点的单链表，判定该表为

17、空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL58. 在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。A (p-prior)-next = p-next (p-next)-prior = p-prior;B p-prior=(p-prior)-prior (p-prior)-next = p;C (p-next)-prior = p p-next=(p-next)-nextD p-next=(p-prior)-prior p-prior=(p-next)-next;59. 输入序列为ABC，可以变为C

18、BA时，经过的栈操作为（ B ）A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop60. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈61. 用链接方式存储的队列，在进行删除运算时（ D ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改62. 假设以数组A

19、0.m存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m63. 循环队列存储在数组A0.m中，则入队时的操作为（ D ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 64. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个

20、元素后，rear和front的值分别为多少？( B )A. 1和 5 B. 2和4 C. 4和2 D. 5和1 65. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ B ）。 A. (rear+1) % n = front B. rear=front Crear+1 = front D. (rear-l) % n = front66. 栈和队列都是（ C ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构67. 用单链表表示的链式队列的队头在链表的（ A ）位置。A链头 B链尾 C链中68. 若一棵二叉树

21、具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A9 B11 C15 D不确定 69. 具有10个叶结点的二叉树中有（ B ）个度为2的结点A8 B9 C10 Dll70. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A不确定 B2n C2n+1 D2n-171. 对于有n 个结点的二叉树, 其高度为（ D ）Anlog2n Blog2n Clog2n|+1 D不确定72. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( D )次序的遍历实现编号。A先序 B.

22、中序 C. 后序 D. 从根开始按层次遍历73. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是( G )A、 E B、 F C、 G D、 H 74. 在完全二叉树中，若一个结点是叶结点，则它没（ C ）。A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点75. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点76. 引入二叉线索树的目的是（ A ）A加快查找结点的前驱或后继的

23、速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一77. n个结点的线索二叉树上含有的线索数为（ C ）A2n Bnl Cnl Dn 78. 由3 个结点可以构造出多少种不同的二叉树？（ D ）A2 B3 C4 D5 79. 设无向图的顶点个数为n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En280. 一个n个顶点的连通无向图，其边的个数至少为（ A ）。An-1 Bn Cn+1 Dnlogn；81. n个结点的完全有向图含有边的数目（A）。An*n n（n） Cn2 Dn*（nl）82. 在一个无向图中，

24、所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。A1/2 B2 C1 D483. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)84. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储85. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结

25、果不同的是( C ) A(100，80， 90， 60， 120，110，130） B. (100，120，110，130，80， 60， 90）C. (100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)86. 设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用开散列表构造散列表，散列函数为H（key）=key % 13,散列地址为1的链中有（ D ）个记录。A1 B. 2 C. 3 D. 487. 闭散列表的地址区间为0-17,散列函数为H(K)=K % 17。采用线性重散列技

26、术处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中, 元素59存放在散列表中的地址是（ D ）。A 8 B. 9 C. 10 D. 1188. 在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ D ）。A 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序89. 119对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 , 则采用的排序是 ( A )。 A.

27、选择 B. 冒泡 C. 快速 D. 插入90. 对序列15，9，7，8，20，-1，4进行排序，经一趟排序后的排列为9，15，7，8，20，-1，4，则采用的是（ C ）排序。A选择 B. 堆 C. 直接插入 D. 冒泡 91. 下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A. 选择 B. 冒泡 C. 合并 D. 堆92. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B. (40,38,46,79,56,84)C(40,38,46,

28、56,79,84) D. (40,38,46,84,56,79)93. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆94. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。A94,32,40,90,80,46,21,69B32,40,21,46,69,94,90,80C21,32,46,40,80,69,90,94D90,69,80,46,21,32,94,4095. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进

29、行 （ C ）次比较。 A. 3 B. 10 C. 15 D. 25 96. 以下序列不是堆的是( D )。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100) D.(100,85,40,77,80,60,66,98,82,10,20)97. 归并排序中，归并的趟数是( B )。AO（n） BO(logn) CO(nlogn) DO(n*n) 六、 填空题1. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用

30、_顺序_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_链式_存储结构为宜。2. 栈和队列都是线性结构，对于栈只能在_栈顶_位置插入和删除元素；对于队列只能在_队列尾部_位置插入元素和在_队列首部_位置删除元素。3. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_2,3,_。4. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为_1_和_3_。5. 在一棵二叉搜索树上按_中序_遍历得到的结点序列是一个有序序列。6. n个结点的线索二

31、叉树上含有的线索数为_n+1_。7. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为_O(n)_和_O(e)_。8. 图的_深度_优先搜索遍历算法是一种递归算法，图的_广度_优先搜索遍历算法需要使用队列。9. 假定一个有向图的顶点集为a,b,c,d,e,f，边集为, , , , , ，则出度为0的顶点个数为_2_，入度为1的顶点个数为_4_。10. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。11. 若长度为n的线性表采用顺序存储结构，在其第i个位置(1=i=1）

32、的完全二叉树至少有_2k-1_个结点，至多有_2k-1_个结点。30. 具有N个结点的二叉树，采用二叉链表存储，共有_N+1_个空链域。31. 对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为_2e_。32. 下图中的强连通分量的个数为_3_个。33. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_深度优先_遍历方法。34. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_26, 15, 19, 25_。35. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_m-1_。36. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过_1_。37. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和