《数据结构期末综合练习一.docx》由会员分享，可在线阅读，更多相关《数据结构期末综合练习一.docx（24页珍藏版）》请在三一办公上搜索。
1、数据结构期末综合练习一数据结构期末综合练习一 单选题 1. 一个数组元素ai 与( A )的表示等价。 A. *(a+i) B. a+i C. *a+i D. &a+i 2. 若需要利用形参直接访问实参，则应把形参变量说明为( B )参数。 A. 指针 B. 引用 C. 传值 D. 常值 3. 下面程序段的时间复杂度为( C )。 for(int i=0; im; i+) for(int j=0; jn; j+) aij = i*j; 22 A. O(m) B. O(n) C. O(m*n) D. O(m+n) 4. 执行下面程序段时，执行S语句的次数为( D )。 for(int i=1;
2、i=n; i+) for(int j=1; jlink = 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. 设单链表中结点的结构为。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是。 A. s-link=p-link; p-link=s; B. q-link=s; s-link=p; C. p-lin
3、k=s-link; s-link=p; D. p-link=s; s-link=q; 31. 设单链表中结点的结构为。已知指针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. 设单链表中结点的结构为。若想摘除p-link所指向的结点，则应执行的操作是。 A. p-link=p-link-link; B. p=p-link; p-link=p-link-link; C. p-link
4、=p; D. p=p-link-link; 33. 非空的循环单链表first的尾结点满足的条件是。 A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first; 34. 设单循环链表中结点的结构为，且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-l
5、ink-link; rear-link-link = s-link; delete s; 35. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 36. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是。 A. O(1) B. O(n) C. O(n) D. O(nlog2n) 237. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是。 A. O(1) B. O(n) 2 C. O(n) D. O(nlog2n) 3 38.单链表A长度为m，单链
6、表B长度为n，若将B联接在A的末尾，其时间复杂度应为。 A. O(1) B. O(m) C. O(n) D. O(m+n) 39. 利用双向链表作线性表的存储结构的优点是。 A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间 40. 带表头的双向循环链表的空表满足。 A. firstNULL; B. first-rLink=first C. first-lLink=NULL D. first-rLink=NULL 41. 已知L是一个不带表头的单链表, 在表首插入结点*p的操作是。 A. p = L; p-link = L; B.
7、 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-link = L; 43. 栈的插入和删除操作在( A )进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 44. 当利用大小为n的数组顺序存储一个栈时，假定用top=n表示栈空，则向这个栈插入一个元素时，首先应执行( B )语句修改top指针。 A. top+; B. top-; C.
8、top = 0; D. top; 45. 若让元素1,2,3依次进栈，则出栈次序不可能出现( C )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2 46. 在一个顺序存储的循环队列中，队头指针指向队头元素的( A )位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 47. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( B )。 A. n-2 B. n-1 C. n D. n+1 48. 从一个顺序存储的循环队列中删除一个元素时，首先需要( A )。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指
9、针所指的元素 49. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。 A. front+1 = rear C. front = 0 B. rear+1 = front D. front = rear 50. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。 A. front = rear B. front != NULL C. rear != NULL D. front = NULL 51. 设链式栈中结点的结构为，且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行(
10、C )操作。 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; 4 52. 设链式栈中结点的结构为，且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。 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 stru
11、ct DataType dataMaxSize; int front, rear; Queue; 若有一个Queue类型的队列Q，试问判断队列满的条件应为( 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; 54. 设循环队列的结构是 const int MaxSize = 100; typedef int DataType; typedef struct DataType dataMaxSize; int front,
12、rear; Queue; 若有一个Queue类型的队列Q，则应用( A )表达式计算队列元素的个数。 A. (Q.rear-Q.front+MaxSize) % MaxSize; B.Q.rear-Q.front+1; C. Q.rear-Q.front-1; D. Q.rear-Qfront; 55. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( D )分别设在这块内存空间的两端。 A. 长度 B. 深度 C. 栈顶 D. 栈底 56. 递归是将一个较复杂的问题转化为一个稍为简单的与原问题的问题来解决，使之比原问题更靠近可直接求解的条件。 A.
13、 相关 B. 子类型相关 C. 同类型 D. 不相关 57. 递归调用时系统需要利用一个来实现数据的传递和控制的转移。 A. 队列 B. 优先级队列 C. 双端队列 D. 栈 58. 在系统实现递归调用时需利用递归工作记录保存，当递归调用程序执行结束时通过它将控制转到上层调用程序。 A. 调用地址 B. 递归入口 C. 返回地址 D. 递归出口 59. 在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为记录。 A. 活动 B. 当前 C. 日志 D. 标记 60. 将递归求解过程改变为非递归求解过程的目的是。 A. 提高速度 B. 改善可读性 C. 增强
14、健壮性 D. 提高可维护性 61. 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于，它很容易被改写为非递归过程。 A. 单向递归 B. 回溯递归 C. 间接递归 D. 尾递归 5 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-1 63. 设有一个递归算法如下 int X ( int n ) if ( n 0)的结点，其双亲结点的编号为( B
15、)。 A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2-1 79. 在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的( A )结点。 A. 兄弟 B. 父子 C. 祖先 D. 子孙 80. 在一棵树的静态双亲表示中，每个存储结点包含( B )个域。 A 1 B 2 C 3 D 4 81. 已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，则该二叉树的高度为( B )。假定树根结点的高度为0。 A. 3 B. 4 C. 5 D. 6 82. 已知一棵树的边集表示为, , , , , , , ，则该树的深度为( B )。假定树根结点的高度为0。
16、A. 2 B. 3 C. 4 D. 5 83. 利用n个值作为叶结点的权生成的霍夫曼树中共包含有( D )个结点。 A. n B. n+1 C. 2*n D. 2*n-1 84. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( A )。 A 55 B 29 C 58 D 38 85. 一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( C )。 A 1 B 2 C 3 D 4 86. 向具有n个结点的堆中插入一个新元素的时间复杂度为( C )。 A. O(1) B. O(n) C. O(log2n
17、) D. O(nlog2n) 87. 若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为( D )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 88. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为( C )。 A. 5.5 B. 5 C. 39/8 D. 19/4 89. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索任一元素的平均搜索长度为( A )。 A. 5/
18、3 B. 2 C. 7/3 D. 4/3 90. 对长度为n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为( B )。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 7 91. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( A )的值向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 92. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( B )的值的向下取整加1。 A. log2(n+1) B. log2n C. n/2
19、 D. (n+1)/2 93. 对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( C )除以9。 A. 20 B. 18 C. 25 D. 22 94. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为( B )。 A. 3 B. 4 C. 5 D. 6 95. 对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为( D )。 2 A. O(n) B. O(n) C. O(1) D. O(log2n) 96. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为( D )。 A. n B.
20、log2n C. (h+1)/2 D. h+1 97. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( C )。 2 A. O(n) B. O(1) C. O(log2n) D. O(n) 98. 向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为( B )。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n) 99. 在一棵AVL树中，每个结点的平衡因子的取值范围是( A )。 A. -11 B. -22 C. 12 D. 01 100. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分
21、为( C )种旋转类型。 A. 2 B. 3 C. 4 D. 5 101. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关( B )个指针域的值。 A. 2 B. 3 C. 4 D. 5 102. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( D )个指针域的值。 A. 2 B. 3 C. 4 D. 5 103. 设G1=和G2=为两个图，如果V1V2，E1E2，则称 ( A )。 AG1是G2的子图 BG2是G1的子图 CG1是G2的连通分量 DG2是G1的连通分量 104. 有向图的一个顶点的度数
22、等于该顶点的 ( C )。 A入度 B出度 C入度与出度之和 D 105. 一个连通图的生成树是包含图中所有顶点的一个 ( C )。 A极小子图 B连通子图 C极小连通子图 D无环子图 106. n个顶点的连通图中至少含有 ( A )。 An-1条边 Bn条边 Cn(n-1)/2条边 Dn(n-1)条边 8 107. n个顶点的强连通图中至少含有 ( B )。 An-1条有向边 Bn条有向边 Cn(n-1)/2条有向边 Dn(n-1)条有向边 108. 在一个带权连通图G中，权值最小的边一定包含在G的( A ) 中。 A最小生成树 B生成树 C广度优先生成树 D深度优先生成树 109. 对于具
23、有e条边的无向图，它的邻接表中有 ( D ) 个边结点。 Ae-1 Be C2(e-1) D2e 110. 具有n个顶点的有向无环图最多可包含 ( C ) 条有向边。 An-1 Bn Cn(n-1)/2 Dn(n-1) 111. 一个有n个顶点和n条边的无向图一定是 ( D )。 A连通的 B不连通的 C无环的 D有环的 112. 在n个顶点的有向无环图的邻接矩阵中至少有 ( C ) 个零元素。 An Bn(n-1)/2 Cn(n+1)/2 Dn(n-1) 113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( A )。 A查找一条边 B求一个顶点的邻接点 C进行图的深度优先遍历 D进行图
24、的广度优先遍历 114. 在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是 ( A )。 AO(1) BO(i) CO(j) DO(i+j) 115. 与邻接矩阵相比，邻接表更适合于存储 ( C )。 A无向图 B连通图 C稀疏图 D稠密图 116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度 所耗费的时间是 ( A )。 2 AO(n) BO(e) CO(n+e) DO(n) 117. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是 ( B )。 A栈 B队列 C二叉树 D树 118. 设无向图的顶点个数为n，则该图最多有条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( B ) 倍。 A. 3 B. 2 C. 1 D. 1/2 120. 若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个 ( D )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 121. 图的深度优先搜索类似于树的次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 122. 图的广度优先搜索类似于树的次序遍历。 A. 先根 B. 中根 C. 后根 D.
