数据结构（本科）期末综合练习一（单选题）

1、数据结构本科期末综合练习一单项选择题单项选择题 1. 一个数组元素ai 与( )的表示等价。 A. *(a+i) B. a+i C. *a+i D. &a+i 2. 假设需要利用形参直接访问实参，那么应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值 3. 下面程序段的时间复杂度为( )。 for(int i=0; i<m; i+) for(int j=0; j<n; j+) aij = i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1

2、; i<=n; i+) for(int j=1; j<=i; j+) S; A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 5. 下面算法的时间复杂度为( )。 int f(unsigned int n) if(n=0 | n=1) return 1; else return n*f (n-1); A. O(1) B. O(n) C. O(n2) D. O(n!) 6. 一种抽象数据类型包括数据和( )两个局部。 A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明 7. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以

3、节省参数值的传输时间和存储参数的空间。 A. 根本类型 B. 引用型 C. 指针型 D. 常值引用型 8. 当需要进行标准I/O操作时，那么应在程序文件中包含头文件，当需要进行文件I/O操作时，那么应在程序文件中包含( )头文件。 A B C D 9. 一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。 A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值 10. 输出一个二维数组bmn中所有元素值的时间复杂度为( )。 A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

4、 11. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为( )。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 12. 某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为 。 A. O(n) B. O(nlog2n) C. O(n2) D. O(1) 13. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为3，那么该算法的时间复杂度为 。 A. O(n) B. O(n2) C. O(n3) D. O(1) 14. 以下说法错误的选项是 。 A. 抽

5、象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。 C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现别离。 15. 在二维数组中，每个数组元素同时处于 个向量中。 A. 0个 B. 1个 C. 2个D. n个 16. 多维数组实际上是由嵌套的 实现的。 A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 17. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比拟次数为 。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 18. 在一个长度为n的顺序表中

6、向第i个元素0in-1位置插入一个新元素时，需要从后向前依次后移 个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 19. 在一个长度为n的顺序表中删除第i个元素0in-1时，需要从前向后依次前移 个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 20. 在一个长度为n的顺序表中删除一个值为x的元素时，需要比拟元素和移动元素的总次数为 。 A. (n+1)/2 B. n/2 C. n D. n+1 21. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为 。 A. O(n) B. O(1) C. O(n2) D. O(log2n) 22. 在

7、一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为 。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 23. 在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为 。 A. O(1) B. O() C. O(log2n) D. O(n) 24. 在二维数组A810中，每一个数组元素Aij 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，那么存放该数组至少需要的存储空间是 。 A. 80 B. 100 C. 240 D. 270 25. 设有一个n´n的对称矩阵A，将其下三角局部按行存放在一个一维数组B中，A

8、00存放于B0中，那么第i行的对角元素Aii存放于B中 处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 26. 设有一个n´n的对称矩阵A，将其上三角局部按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中 处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 27. 设有两个串t和p，求p在t中首次出现的位置的运算叫做 。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 28. 不带头结点的单链表fi

9、rst为空的判定条件是 。A. first = NULL; B. first->link = NULL;C. first->link = first; D. first != NULL; 29. 带头结点的单链表first为空的判定条件是 。A. first=NULL; B. first->link=NULL;C. first->link=first; D. first!=NULL; 30. 设单链表中结点的结构为data, link。指针q所指结点是指针p所指结点的直接前驱，假设在*q与*p之间插入结点*s，那么应执行的操作是 。 A. s->link=p-&g

10、t;link; p->link=s; B. q->link=s; s->link=p; C. p->link=s->link; s->link=p; D. p->link=s; s->link=q; 31. 设单链表中结点的结构为data, link。指针p所指结点不是尾结点，假设在*p之后插入结点*s，那么应执行的操作是 。 A.s->link=p; p->link=s; B. p->link=s; s->link=p; C.s->link=p->link; p=s; D. s->link=p->

11、link; p->link=s; 32. 设单链表中结点的结构为data, link。假设想摘除p->link所指向的结点，那么应执行的操作是 。 A. p->link=p->link->link; B. p=p->link; p->link=p->link->link; C. p->link=p; D. p=p->link->link; 33. 非空的循环单链表first的尾结点由p所指向满足的条件是 。 A. p->link=NULL; B. p=NULL; C. p->link=first; D. p=f

12、irst; 34. 设单循环链表中结点的结构为data, link，且rear是指向非空的带表头结点的单循环链表的尾结点的指针。假设想删除链表第一个结点，那么应执行的操作是 。 A.s = rear; rear = rear->link; delete s; B.rear = rear->link; delete rear; C.rear = rear->link->link; delete rear; D.s = rear->link->link; rear->link->link = s->link; delete s;35. 从一个具

13、有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比拟的结点数是 。 A. n B. n/2 C. (n-1)/2 D. (n+1)/236. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n)37. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是 。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n)38.单链表A长度为m，单链表B长度为n，假设将B联接在A的末尾，其时间复杂度应为 。 A. O(1) B. O(m) C. O(n) D.

14、 O(m+n)39. 利用双向链表作线性表的存储结构的优点是 。 A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间40. 带表头的双向循环链表的空表满足 。 A. firstNULL; B. first->rLink=first C. first->lLink=NULL D. first->rLink=NULL41. L是一个不带表头的单链表, 在表首插入结点*p的操作是 。A. p = L; p->link = L; B. p->link = L; p = L; C. p->link = L

15、; L = p; D. L = p; p->link = L;42. L是带表头的单链表, 删除首元结点的语句是 。A. L = L->link; B. L->link = L->link->link; C. L = L; D. L->link = L;43. 栈的插入和删除操作在( )进行。 A. 栈顶 B. 栈底 C. 任意位置D. 指定位置44. 当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，那么向这个栈插入一个元素时，首先应执行( )语句修改top指针。 A. top+; B. top-; C. top = 0; D. top;45

16、. 假设让元素1,2,3依次进栈，那么出栈次序不可能出现( )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,246. 在一个顺序存储的循环队列中，队头指针指向队头元素的( )位置。 A. 前一个 B. 后一个 C. 当前 D. 后面47. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( )。 A. n-2 B. n-1 C. n D. n+148. 从一个顺序存储的循环队列中删除一个元素时，首先需要( )。 A. 队头指针加一B. 队头指针减一 C. 取出队头指针所指的元素D. 取出队尾指针所指的元素49. 假定一个顺序存储的循环队列的队头和队尾指

17、针分别为front和rear，那么判断队空的条件为( )。 A. front+1 = rearB. rear+1 = front C. front = 0D. front = rear50. 假定一个链式队列的队头和队尾指针分别为front和rear，那么判断队空的条件为( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL51. 设链式栈中结点的结构为data, link，且top是指向栈顶的指针。假设想在链式栈的栈顶插入一个由指针s所指的结点，那么应执行( )操作。 A. top->link=s;B.

18、s->link=top->link; top->link=s; C. s->link=top; top=s; D. s->link=top; top=top->link;52. 设链式栈中结点的结构为data, link，且top是指向栈顶的指针。假设想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，那么应执行( )操作。 A. x=top->data; top=top->link; B. top=top->link; x=top->data; C. x=top; top=top->link; D. x=top->da

19、ta;53. 设循环队列的结构是 typedef struct DataType dataMaxSize; int front, rear; Queue; 假设有一个Queue类型的队列Q，试问判断队列满的条件应为( ) 。 A. Q.front=Q.rear; B. Q.front-Q.rear=MaxSize; C. Q.front+Q.rear=MaxSize; D. Q.front=(Q.rear+1) % MaxSize;54. 设循环队列的结构是 const int MaxSize = 100; typedef int DataType; typedef struct DataTy

20、pe dataMaxSize; int front, rear; Queue; 假设有一个Queue类型的队列Q，那么应用( )表达式计算队列元素的个数。 A. (Q.rear-Q.front+MaxSize) % MaxSize; B.Q.rear-Q.front+1; C. Q.rear-Q.front-1; D. Q.rear-Qfront;55. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( )分别设在这块内存空间的两端。 A. 长度 B. 深度 C. 栈顶 D. 栈底56. 递归是将一个较复杂的规模较大的问题转化为一个稍为简单的规模较小

21、的与原问题 的问题来解决，使之比原问题更靠近可直接求解的条件。 A. 相关B. 子类型相关C. 同类型D. 不相关57. 递归调用时系统需要利用一个 来实现数据的传递和控制的转移。 A. 队列B. 优先级队列C. 双端队列D. 栈58. 在系统实现递归调用时需利用递归工作记录保存 ，当递归调用程序执行结束时通过它将控制转到上层调用程序。 A. 调用地址B. 递归入口C. 返回地址D. 递归出口59. 在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为 记录。 A. 活动B. 当前C. 日志D. 标记60. 将递归求解过程改变为非递归求解过程的目的是 。

22、A. 提高速度B. 改善可读性C. 增强健壮性D. 提高可维护性61. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，那么这种递归属于 ，它很容易被改写为非递归过程。 A. 单向递归B. 回溯递归C. 间接递归D. 尾递归62. 设有一个递归算法如下int fact ( int n ) /n大于等于0 if ( n <= 0 ) return 1; else return n * fact (n-1); 那么计算fact (n) 需要函数调用的次数为 次。 An Bn+1 Cn+2 Dn-163. 设有一个递归算法如下int X ( int n ) if ( n &l

23、t;= 3 ) return 1; else return X (n-2) + X (n-4) + 1; 试问计算X (X (5) ) 时需要调用 次X函数。 A2次B3次C4次D5次64. 设有一个广义表A (a)，其表尾为 。 AaB( ( ) )CD(a)65. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为 。 Ax B(a, b)C(x,(a,b)Dy66. 以下广义表中的线性表是 。 AE(a,(b,c)BE(a,E)CE(a,b)DE(a,L( )67. 对于一组广义表A( )

24、, B(a,b), C(c,(e,f,g), D(B,A,C), E (B, D)，其中的E是 。 A. 线性表B. 纯表C. 递归表D. 再入表68. 广义表A ( (a, b, c), (d, e, f ) )，从A中取出原子e的运算是 。 ATail (Head (A) )BHead (Tail (A) ) CHead (Tail(Head(Tail(A)DHead(Head(Tail(Tail (A)69. 树中所有结点的度之和等于所有结点数加( )。 A. 0 B. 1 C. 1 D. 2 70. 在一棵树中，( )没有前驱结点。 A. 树枝结点 B. 叶子结点 C. 树根结点 D.

25、 空结点 71. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。 A. 2 B. 1 C. 0 D. 1 72. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于( )。 A. n B. n-1 C. n+1 D. 2*n 73. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( )个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 74. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 75. 一棵具有35个

26、结点的完全二叉树的高度为( )。假定空树的高度为 -1。 A. 5 B. 6 C. 7 D. 8 76. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为( )。假定树根结点的编号为0。 A. ë(n-1)/2û B. ën/2û C. én/2ù D. ën/2û-1 77. 在一棵完全二叉树中，假设编号为i的结点存在左子女，那么左子女结点的编号为( )。假定树根结点的编号为0。 A 2i B 2i-1 C 2i+1 D 2i+2 78. 在一棵完全二叉树中，假定树根结点的编号为0，对于编号为i(i>

27、0)的结点，其双亲结点的编号为( )。 A. ë(i+1)/2û B. ë(i-1)/2û C. ëi/2û D. ëi/2û-1 79. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的( )结点。 A. 兄弟 B. 父子 C. 祖先 D. 子孙 80. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4 81. 一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，那么该二叉树的高度为( )。假定树根结点的高度为0。 A. 3 B. 4 C. 5 D.

28、6 82. 一棵树的边集表示为<A,B>, <A,C>, <B,D>, <C,E>, <C,F>, <C,G>, <F,H>, <F,I>，那么该树的深度为( )。假定树根结点的高度为0。 A. 2 B. 3 C. 4 D. 5 83. 利用n个值作为叶结点的权生成的霍夫曼树中共包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1 84. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( )。 A 55 B 29 C 58 D 38 85

29、. 一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。 A 1 B 2 C 3 D 4 86. 向具有n个结点的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n) 87. 假设搜索每个元素的概率相等，那么在长度为n的顺序表上搜索任一元素的平均搜索长度为( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 88. 对长度为10的顺序表进行搜索，假设搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，那么搜索任

30、一元素的平均搜索长度为( )。 A. 5.5 B. 5 C. 39/8 D. 19/4 89. 对长度为3的顺序表进行搜索，假设搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，那么搜索任一元素的平均搜索长度为( )。 A. 5/3 B. 2 C. 7/3 D. 4/3 90. 对长度为n的单链有序表，假设搜索每个元素的概率相等，那么搜索任一元素的搜索成功的平均搜索长度为( )。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 91. 对于长度为n的顺序存储的有序表，假设采用折半搜索，那么对所有元素的搜索长度中最大的为( )的值向

31、上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 92. 对于长度为n的顺序存储的有序表，假设采用折半搜索，那么对所有元素的搜索长度中最大的为( )的值的向下取整加1。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 93. 对于长度为9的顺序存储的有序表，假设采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )除以9。 A. 20 B. 18 C. 25 D. 22 94. 对于长度为18的顺序存储的有序表，假设采用折半搜索，那么搜索第15个元素的搜索长度为( )。 A. 3 B. 4 C. 5 D. 6 95.

32、对具有n个元素的有序表进行折半搜索，那么搜索任一元素的时间复杂度为( )。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 96. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为( )。 A. n B. log2n C. (h+1)/2 D. h+1 97. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 98. 向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为( )。 A. O(1) B. O(log2n )

33、 C. O(n) D. O(nlog2n) 99. 在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A. -11 B. -22 C. 12 D. 01 100. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( )种旋转类型。 A. 2 B. 3 C. 4 D. 5 101. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关( )个指针域的值。 A. 2 B. 3 C. 4 D. 5 102. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( )个指针域的值。 A. 2

34、B. 3 C. 4 D. 5 103. 设G1=V1，E1和G2=V2，E2为两个图，如果V1ÍV2，E1ÍE2，那么称 ( )。 AG1是G2的子图 BG2是G1的子图 CG1是G2的连通分量 DG2是G1的连通分量104. 有向图的一个顶点的度数等于该顶点的 ( )。 A入度 B出度 C入度与出度之和 D入度+出度105. 一个连通图的生成树是包含图中所有顶点的一个 ( )。 A极小子图 B连通子图 C极小连通子图 D无环子图106. n个顶点的连通图中至少含有 ( )。 An-1条边 Bn条边 Cn(n-1)/2条边 Dn(n-1)条边107. n个顶点的强连通图中至

35、少含有 ( )。 An-1条有向边 Bn条有向边 Cn(n-1)/2条有向边 Dn(n-1)条有向边108. 在一个带权连通图G中，权值最小的边一定包含在G的( ) 中。 A最小生成树 B生成树 C广度优先生成树 D深度优先生成树109. 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。 Ae-1 Be C2(e-1) D2e110. 具有n个顶点的有向无环图最多可包含 ( ) 条有向边。 An-1 Bn Cn(n-1)/2 Dn(n-1) 111. 一个有n个顶点和n条边的无向图一定是 ( )。 A连通的 B不连通的 C无环的 D有环的112. 在n个顶点的有向无环图的邻接矩阵中至

36、少有 ( ) 个零元素。 An Bn(n-1)/2 Cn(n+1)/2 Dn(n-1) 113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( )。 A查找一条边 B求一个顶点的邻接点 C进行图的深度优先遍历 D进行图的广度优先遍历114. 在一个有向图的邻接矩阵表示中，删除一条边<vi,vj>需要消耗的时间是 ( )。 AO(1) BO(i) CO(j) DO(i+j)115. 与邻接矩阵相比，邻接表更适合于存储 ( )。 A无向图 B连通图 C稀疏图 D稠密图116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度所消耗的时间是 ( )。 AO(n)

37、BO(e) CO(n+e) DO(n2)117. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是 ( )。 A栈 B队列 C二叉树 D树118. 设无向图的顶点个数为n，那么该图最多有 条边。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。A. 3B. 2C. 1D. 1/2120. 假设采用邻接矩阵存储具有n个顶点的无向图，那么该邻接矩阵是一个 ( )。A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵121. 图的深度优先搜索类似于树的 次序遍历。A. 先根B. 中根

38、C. 后根D. 层次122. 图的广度优先搜索类似于树的 次序遍历。A. 先根B. 中根C. 后根D. 层次123. 在用Kruskal算法求解带权连通图的最小代价生成树时，通常采用一个 辅助结构，判断一条边的两个端点是否在同一个连通分量上。A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合124. 采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 数。A. 非零B. 非整C. 非负D. 非正125. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为 。A. O(nlog2e)B. O(n+e)C. O(ne)

39、D. O(n2) 126. 假设待排序对象序列在排序前已根本按排序码递增顺序排列，那么采用( )方法比拟次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序D. 直接选择排序 127. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 128. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比拟。 A. 8 B. 10 C. 15 D. 25 129. 以下排序算法中，( )算法是不稳定的。 A. 起泡排

40、序 B. 直接插入排序 C. 基数排序 D. 快速排序 130. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，那么应取的归并路数至少是( )。 A. 3 B. 4 C. 5 D. 6 131. 在基于排序码比拟的排序算法中，( )算法在最坏情况下的时间复杂度不高于O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 堆排序 D. 快速排序 132. 在以下排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。 A. 锦标赛排序 B. 快速排序 C. 基数排序 D. 归并排序 133. 一个对象序列的排序码为46, 79, 5

41、6, 38, 40, 84，采用快速排序以位于最左位置的对象为基准所得到的第一次划分结果为( )。A. 38, 46, 79, 56, 40, 84 B. 38, 79, 56, 46, 40, 84C. 40, 38, 46, 79, 56, 84 D. 38, 46, 56, 79, 40, 84 134. 如果将所有中国人按照生日不考虑年份，只考虑月、日来排序，那么使用以下排序算法中( )算法最快。 A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序 135. 设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5

42、，那么散列表的长度应至少为 。注：平均探查次数的计算公式为Snl=1+1/(1-)/2, 其中为装填因子 A. 400B. 526C. 624D. 676 136. 5阶B树中, 每个结点最多允许有 个关键码。 A. 2B. 3C. 4D. 5 137. 在10阶B树中根结点所包含的关键码个数最少为 。 A. 0B. 1C. 3D. 4 138. 在一棵高度为h的B树中，叶结点处于第 层。注：树根结点为第0层，B树高度为失败结点所处层数。 A. h-1B. hC. h+1D. h+2 139. 在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取 个结点。 A. h-1B. hC.

43、 h+1D. h+2 140. 当对一个线性表R60 进行索引顺序搜索分块搜索时，假设共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，那么搜索每一个表项的平均搜索长度为 。 A. 7B. 8C. 9D. 10 141. 当对一个线性表R60 进行索引顺序搜索分块搜索时，假设共分成了8个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，那么搜索每一个表项的平均搜索长度为 。 A. 7B. 8C. 9D. 10 142. 既希望较快的搜索又便于线性表动态变化的搜索方法是 。 A. 顺序搜索B. 折半搜索 C. 散列搜索D. 索引顺序搜索 143. 散列函数应该有这样的性质，即函数值应当以 概率取其值域范围内的每一个值。 A. 最大 B. 最小 C. 平均D. 同等 144. 设散列地址空间