数据结构期末复习单选

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; im; i+) for(int j=0; jn; j+) aij = i*j; a. o(m2) b. o(n2) c. o(m*n) d. o(m+n) 4. 执行下面程序段时，执行s语句的次数为( )。 for(int i=1; i=n; i+) for

2、(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. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。 a. s-link=p-link; p-link=s; b. q-link=s; s-link=p; c. p-

3、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, link）。若想摘除p-link所指向的结点，则应执行的操作是（ ）。 a. p-link=p-link-link; b. p=p-li

4、nk; p-link=p-link-link; c. p-link=p; d. p=p-link-link; 33. 非空的尾结点（由p所指向）满足的条件是（ ）。 a. p-lin循环单链表first的k=null; b. p=null; c. p-link=first; d. p=first; 34. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。 a.s = rear; rear = rear-link; delete s; b.rear = rear-link; delet

5、e 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个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。 a. o(1) b. o(n) c. o(n2) d. o(nlog2n)37. 给定有n个元素的向量，建立一个有序单链表的时间

6、复杂度是（ ）。 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. 利用双向链表作线性表的存储结构的优点是（ ）。 a. 便于单向进行插入和删除的操作 b. 便于双向进行插入和删除的操作 c. 节省空间 d. 便于销毁结构释放空间40. 带表头的双向循环链表的空表满足（ ）。 a. firstnull; b. first-rlink=first c. first-llink=null d. first-rli

7、nk=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-link = l;43. 栈的插入和删除操作在( )进行。 a. 栈顶 b. 栈底 c. 任意位置d. 指定位置44. 当利用大小为n的数组顺序存储一个栈时，假定用t

8、op=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. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( )。 a. n-2 b. n-1 c. n d. n+148. 从一个顺序存储的循环队列中删除一个元素时，首先

9、需要( )。 a. 队头指针加一b. 队头指针减一 c. 取出队头指针所指的元素d. 取出队尾指针所指的元素49. 假定一个顺序存储的循环队列的队头和队尾指针分别为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

10、, 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是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( )操作。 a. x=top-data; top=top-link; b. top=top-link; x=top-data; c. x=top; t

11、op=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. q.front=(q.rear+1) % maxsize;54. 设循环队列的结构是 const int maxsize = 100; typedef int datatype

12、; 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. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( )分别设在这块内存空间的两端。 a. 长度 b. 深度 c. 栈顶 d. 栈底56. 递归是将一个较复杂的

13、（规模较大的）问题转化为一个稍为简单的（规模较小的）与原问题（ ）的问题来解决，使之比原问题更靠近可直接求解的条件。 a. 相关b. 子类型相关c. 同类型d. 不相关57. 递归调用时系统需要利用一个（ ）来实现数据的传递和控制的转移。 a. 队列b. 优先级队列c. 双端队列d. 栈58. 在系统实现递归调用时需利用递归工作记录保存（ ），当递归调用程序执行结束时通过它将控制转到上层调用程序。 a. 调用地址b. 递归入口c. 返回地址d. 递归出口59. 在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为（ ）记录。 a. 活动b. 当前c. 日志

14、d. 标记60. 将递归求解过程改变为非递归求解过程的目的是（ ）。 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. 设有

15、一个递归算法如下int x ( int n ) if ( n 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. 6 82. 已知一棵树的边集表示

16、为, , , , , , , ，则该树的深度为( )。假定树根结点的高度为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. 一棵树的广义表表示为a(b,c(e,f(g),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。 a 1 b 2 c 3 d 4 86. 向具有n个结点的堆中插入一个新元素的时间复杂度

17、为( )。 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，则搜索任一元素的平均搜索长度为( )。 a. 5.5 b. 5 c. 39/8 d. 19/4 89. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6

18、，则搜索任一元素的平均搜索长度为( )。 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的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。 a. log2(n+1) b. log2n c. n/2 d. (n+1)/2 92. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值的向下取整加1。 a. log2(n+

19、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. 对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为( )。 a. o(n) b. o(n2) c. o(1) d. o(log2n) 96. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为( )。

20、 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 ) c. o(n) d. o(nlog2n) 99. 在一棵avl树中，每个结点的平衡因子的取值范围是( )。 a. -11 b. -22 c. 12 d. 01 100. 向一棵avl树插入元素时，可能引起对最小不平衡子树的调整过程，此调

21、整分为( )种旋转类型。 a. 2 b. 3 c. 4 d. 5 101. 向一棵avl树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关( )个指针域的值。 a. 2 b. 3 c. 4 d. 5 102. 向一棵avl树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( )个指针域的值。 a. 2 b. 3 c. 4 d. 5 103. 设g1=（v1，e1）和g2=（v2，e2）为两个图，如果v1v2，e1e2，则称 ( )。 ag1是g2的子图 bg2是g1的子图 cg1是g2的连通分量 dg2是g1的连通分量104. 有向图的

22、一个顶点的度数等于该顶点的 ( )。 a入度 b出度 c入度与出度之和 d（入度+出度）105. 一个连通图的生成树是包含图中所有顶点的一个 ( )。 a极小子图 b连通子图 c极小连通子图 d无环子图106. n个顶点的连通图中至少含有 ( )。 an-1条边 bn条边 cn(n-1)/2条边 dn(n-1)条边107. n个顶点的强连通图中至少含有 ( )。 an-1条有向边 bn条有向边 cn(n-1)/2条有向边 dn(n-1)条有向边108. 在一个带权连通图g中，权值最小的边一定包含在g的( ) 中。 a最小生成树 b生成树 c广度优先生成树 d深度优先生成树109. 对于具有e条

23、边的无向图，它的邻接表中有 ( ) 个边结点。 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个顶点的有向无环图的邻接矩阵中至少有 ( ) 个零元素。 an bn(n-1)/2 cn(n+1)/2 dn(n-1) 113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( )。 a查找一条边 b求一个顶点的邻接点 c进行图的深度优先遍历 d进行图的广度优先遍历114. 在一个

24、有向图的邻接矩阵表示中，删除一条边需要耗费的时间是 ( )。 ao(1) bo(i) co(j) do(i+j)115. 与邻接矩阵相比，邻接表更适合于存储 ( )。 a无向图 b连通图 c稀疏图 d稠密图116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度所耗费的时间是 ( )。 ao(n) 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(

25、n-1)119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。a. 3b. 2c. 1d. 1/2120. 若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个 ( )。a. 上三角矩阵b. 稀疏矩阵c. 对角矩阵d. 对称矩阵121. 图的深度优先搜索类似于树的（ ）次序遍历。a. 先根b. 中根c. 后根d. 层次122. 图的广度优先搜索类似于树的（ ）次序遍历。a. 先根b. 中根c. 后根d. 层次123. 在用kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。a. 位向量 b. 堆

26、 c. 并查集 d. 生成树顶点集合124. 采用dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）数。a. 非零b. 非整c. 非负d. 非正125. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。a. o(nlog2e)b. o(n+e)c. o(ne)d. o(n2) 126. 若待排序对象序列在排序前已基本按排序码递增顺序排列，则采用( )方法比较次数最少。 a. 直接插入排序 b. 快速排序 c. 归并排序d. 直接选择排序 127. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子

27、序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 a. 直接选择排序 b. 直接插入排序 c. 快速排序 d. 起泡排序 128. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较。 a. 8 b. 10 c. 15 d. 25 129. 下列排序算法中，( )算法是不稳定的。 a. 起泡排序 b. 直接插入排序 c. 基数排序 d. 快速排序 130. 假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是( )。 a. 3 b. 4 c. 5 d. 6 131. 在基于排序码比较的

28、排序算法中，( )算法在最坏情况下的时间复杂度不高于o(nlog2n)。 a. 起泡排序 b. 希尔排序 c. 堆排序 d. 快速排序 132. 在下列排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。 a. 锦标赛排序 b. 快速排序 c. 基数排序 d. 归并排序 133. 一个对象序列的排序码为46, 79, 56, 38, 40, 84，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为( )。a. 38, 46, 79, 56, 40, 84 b. 38, 79, 56, 46, 40, 84c. 40, 38, 46, 79, 56, 84 d.

29、38, 46, 56, 79, 40, 84 134. 如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。 a. 归并排序 b. 希尔排序 c. 快速排序 d. 基数排序 135. 设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（ ）。（注：平均探查次数的计算公式为snl=1+1/(1-)/2, 其中为装填因子） a. 400b. 526c. 624d. 676 136. 5阶b树中, 每个结点最多允许有（ ）个关键码。 a. 2b. 3c. 4d. 5

30、 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. h+1d. h+2 140. 当对一个线性表r60 进行索引顺序搜索（分块搜索）时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。 a. 7b. 8c.

31、 9d. 10 141. 当对一个线性表r60 进行索引顺序搜索（分块搜索）时，若共分成了8个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（ ）。 a. 7b. 8c. 9d. 10 142. 既希望较快的搜索又便于线性表动态变化的搜索方法是（ ）。 a. 顺序搜索b. 折半搜索 c. 散列搜索d. 索引顺序搜索 143. 散列函数应该有这样的性质，即函数值应当以（ ）概率取其值域范围内的每一个值。 a. 最大 b. 最小 c. 平均d. 同等 144. 设散列地址空间为0m-1，k为表项的关键码，散列函数采用除留余数法，即hash(k)=k

32、%p。为了减少发生冲突的频率，一般取p为（ ）。a. mb. 小于m的最大质数 c. 大于m的最小质数d. 小于m的最大合数 145. 在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（ ）值相同。a. 关键码 b. 非关键码 c. 散列函数 d. 某个域 146. 解决散列法中出现的冲突问题常采用的方法是（ ）。a. 数字分析法、除留余数法、平方取中法 b. 数字分析法、除留余数法、线性探查法 c. 数字分析法、线性探查法、双散列法 d. 线性探查法、双散列法、开散列法 147. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。a. 同义词之间发生冲突 b. 非同义词之间发生冲突 c. 同义词之间或非同义词之间发生冲突 d. 散列表“溢出”