1、1数据结构（本科）期末综合练习一（单选题）单选题1. 一个数组元素 ai 与( )的表示等价。A. *(a+i) B. a+i C. *a+i D. ilink = 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
2、，则应执行的操作是（ ） 。A. s-link=p-link; p-link=s; B. q-link=s; s-link=p;4C. 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-link; p-link=s;32. 设单链表中结点的结构为（data
3、, 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=first;34. 设单循环链表中结点的结构为（data, link） ，且 rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操
4、作是（ ） 。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. 从一个具有 n个结点的单链表中查找其值等于 x结点时，在查找成功的情况下，需要平均比较的结点数是（ ） 。A. n B. n/2 C. (n-1)/2 D. (n+1)/236. 在一个具有 n个结点的有序单链表中插入一个新结点并仍然保持有序的时间
5、复杂度是（ ） 。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. O(m+n)39. 利用双向链表作线性表的存储结构的优点是（ ） 。5A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作C. 节省空间 D. 便于销毁结构释放空间40. 带表头的双向循环
6、链表的空表满足（ ） 。A. firstNULL; B. first-rLink=firstC. 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; 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-li
7、nk = L;43. 栈的插入和删除操作在( )进行。A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置44. 当利用大小为 n的数组顺序存储一个栈时，假定用 top=n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改 top指针。A. top+; B. top-; C. top = 0; D. top;45. 若让元素 1,2,3依次进栈，则出栈次序不可能出现( )种情况。A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,246. 在一个顺序存储的循环队列中，队头指针指向队头元素的( )位置。A. 前一个 B. 后一个 C. 当前 D. 后面47. 当利用大
8、小为 n的数组顺序存储一个队列时，该队列的最大长度为( )。A. n-2 B. n-1 C. n D. n+148. 从一个顺序存储的循环队列中删除一个元素时，首先需要( )。A. 队头指针加一 B. 队头指针减一C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素49. 假定一个顺序存储的循环队列的队头和队尾指针分别为 front和 rear，则判断队空的条件为( )。A. front+1 = rear B. rear+1 = frontC. front = 0 D. front = rear50. 假定一个链式队列的队头和队尾指针分别为 front和 rear，则判断队空的条件为(
9、)。6A. front = rear B. front != NULLC. rear != NULL D. front = NULL51. 设链式栈中结点的结构为（data, link） ，且 top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针 s所指的结点，则应执行( )操作。A. top-link=s; B. s-link=top-link; top-link=s;C. s-link=top; top=s; D. s-link=top; top=top-link;52. 设链式栈中结点的结构为（data, link） ，且 top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除
10、结点的值保存到 x中，则应执行( )操作。A. x=top-data; top=top-link; B. top=top-link; x=top-data;C. x=top; top=top-link; D. x=top-data;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.
11、Q.front=(Q.rear+1) % MaxSize;54. 设循环队列的结构是const int MaxSize = 100;typedef int DataType;typedef struct DataType 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. 为增加内存空间的利用率和减少溢出的
12、可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( )分别设在这块内存空间的两端。 A. 长度 B. 深度 C. 栈顶 D. 栈底56. 递归是将一个较复杂的（规模较大的）问题转化为一个稍为简单的（规模较小的）与原问题（ ）的问题来解决，使之比原问题更靠近可直接求解的条件。A. 相关 B. 子类型相关 C. 同类型 D. 不相关57. 递归调用时系统需要利用一个（ ）来实现数据的传递和控制的转移。7A. 队列 B. 优先级队列 C. 双端队列 D. 栈58. 在系统实现递归调用时需利用递归工作记录保存（ ） ，当递归调用程序执行结束时通过它将控制转到上层调用程序。A. 调用地址 B.
13、递归入口 C. 返回地址 D. 递归出口59. 在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为（ ）记录。A. 活动 B. 当前 C. 日志 D. 标记60. 将递归求解过程改变为非递归求解过程的目的是（ ） 。A. 提高速度 B. 改善可读性 C. 增强健壮性 D. 提高可维护性61. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（ ） ，它很容易被改写为非递归过程。A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归62. 设有一个递归算法如下int fact ( int n ) /n大于等于 0if
14、( n 0)的结点，其双亲结点的编号为( )。9A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2-179. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的( )结点。A. 兄弟 B. 父子 C. 祖先 D. 子孙80. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。A 1 B 2 C 3 D 481. 已知一棵二叉树的广义表表示为 a(b(c),d(e(,g(h),f)，则该二叉树的高度为( )。假定树根结点的高度为 0。A. 3 B. 4 C. 5 D. 682. 已知一棵树的边集表示为, , , , , , , ，则该树的深度为( )。假定树根结
15、点的高度为 0。A. 2 B. 3 C. 4 D. 583. 利用 n个值作为叶结点的权生成的霍夫曼树中共包含有( )个结点。A. n B. n+1 C. 2*n D. 2*n-184. 利用 3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( )。A 55 B 29 C 58 D 3885. 一棵树的广义表表示为 a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。A 1 B 2 C 3 D 486. 向具有 n个结点的堆中插入一个新元素的时间复杂度为( )。A. O(1) B. O(n) C. O(log2n) D.
16、 O(nlog2n)87. 若搜索每个元素的概率相等，则在长度为 n的顺序表上搜索任一元素的平均搜索长度为( )。A. n B. n+1 C. (n-1)/2 D. (n+1)/288. 对长度为 10的顺序表进行搜索，若搜索前面 5个元素的概率相同，均为 1/8，搜索后面5个元素的概率相同，均为 3/40，则搜索任一元素的平均搜索长度为( )。A. 5.5 B. 5 C. 39/8 D. 19/489. 对长度为 3的顺序表进行搜索，若搜索第一个元素的概率为 1/2，搜索第二个元素的概率为 1/3，搜索第三个元素的概率为 1/6，则搜索任一元素的平均搜索长度为( )。A. 5/3 B. 2
17、C. 7/3 D. 4/31090. 对长度为 n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为( )。A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/491. 对于长度为 n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。A. log2(n+1) B. log2n C. n/2 D. (n+1)/292. 对于长度为 n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值的向下取整加 1。A. log2(n+1) B. log2n C. n/2 D. (n+1)/293.
18、对于长度为 9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )除以 9。A. 20 B. 18 C. 25 D. 2294. 对于长度为 18的顺序存储的有序表，若采用折半搜索，则搜索第 15个元素的搜索长度为( )。A. 3 B. 4 C. 5 D. 695. 对具有 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+197
19、. 从具有 n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( )。A. O(n) B. O(1) C. O(log2n) D. O(n2)98. 向具有 n个结点的二叉搜索树中插入一个元素的时间复杂度大致为( )。A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n)99. 在一棵 AVL树中，每个结点的平衡因子的取值范围是( )。A. -11 B. -22 C. 12 D. 01100. 向一棵 AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( )种旋转类型。A. 2 B. 3 C. 4 D. 5101. 向一棵 AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，
