计算机应用基础数据结构部分试题及答案.doc
《计算机应用基础数据结构部分试题及答案.doc》由会员分享,可在线阅读,更多相关《计算机应用基础数据结构部分试题及答案.doc(12页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机应用基础数据结构部分试题及答案计算机应用基础数据结构部分试题及答案1选择题:选择题:1.下面程序段的时间复杂度的量级为()for(i=1;inext= p-next-next B. p=p-next C. p=p-next-next D. next=p 27设单链表中指针 p 指向结点 ai,指针 f 指向将要插入的新结点 x,则当 x 插 在链表中两个数据元素 ai和 ai+1之间时,只要先修改( )后修改()即可。 A. p-next= f B. p-next= p-next-next C. p-next=f-next D. f-next= p-next E. f-next=null
2、 F. f-next=p28设单链表中指针 p 指向结点 ai,指针 f 指向将要插入的新结点 x,则在链表 中最后一个结点 an之后插入时,只要先修改()后修改()即可。 A. f-next= p B. f-next= p-next C. p-next=f D. p-next= f-next E. f =null 29在一个单链表中,若要在 p 所指向的结点之后插入一个新结点,则需要相 继修改()个指针域的值。 A. 1 B. 2 C. 3 D.4 30在一个单链表中,若要在 p 所指向的结点之前插入一个新结点,则此算法 的时间复杂性的量级为() A. O(n) B.O(n/2) C. O(
3、1) D.O(n1/2)21-25 D B A C B 26-30 A (D.A) (B.C) B A31不带头结点的单链表 L 为空的判定条件是() 。 A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL 32带头结点的单链表 L 为空的判定条件是() 。 A. L= = NULL B. L-next = = NULL C. L-next = = L D. L! = NULL 33在一个带有头结点的双向循环链表中,若要在 p 所指向的结点之前插入一 个新结点,则需要相继修改()个指针域的值。 A. 2 B. 3 C. 4
4、D.6 34在一个带有头结点的双向循环链表中,若要在 p 所指向的结点之后插入一 个 q 指针所指向的结点,则需要对 q-next 赋值为() A. p-prior B. p-next C. p-next-next D. p-prior -prior 35对一个具有 n 个元素的线性表,建立其单链表的时间复杂度为() A. O(n) B.O(1) C. O(n2) D.O(logn) 36线性表采用链式存储时,其地址() A. 必须是连续的 B. 一定是不连续的 C. 部分地址必须是连续的 D. 连续与否均可以 37假定利用数组 aN顺序存储一个栈,用 top 表示栈顶指针,top= =-1
5、表示栈 空,并已知栈未满,当元素 x 进栈时所执行的操作为() A. a-top=x B. atop-=x C. a+top=x D .atop+=x 38若已知一个栈的入栈序列是 1,2,3,.n,其输出序列为 p1, p2, p3,. pn,若 p1=n,则 pi 为() A. i B.n-i C. n-i+1 D.不确定 39判定一个栈 S(最多元素为 m0)为空的条件是() A. S. top!=0 B. S. top= =0 C. S. top!=m0 D .S. top= =m0 40判定一个栈 S(最多元素为 m0)为满的条件是() A .S. top!=0 B. S. top=
6、 =0 C. S. top!=m0-1 D .S. top= =m0-131-35 A B C B A 36-40 D C C B D41一个队列的入队序列是 1,2,3,4,则队列的输出序列是() A.4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D .3,2,4,1 42从一个顺序循环队列中删除元素时,首先需要() A. 前移队首指针 B. 后移队首指针 C. 取出队首指针所指位置上的元素 D . 取出队尾指针所指位置上的元素 43假定一个顺序循环队列的队首和队尾指针分别用 front 和 rear 表示,则判断 队列空的条件为() A.front+1= =rear B.re
7、ar+1= =front C. front= =0 D . front= =rear 44假定一个顺序循环队列存储于数组 aN中,其队首和队尾指针分别用 front 和 rear 表示,则判断队列满的条件为() A. (rear-1)%N= =front B. (rear+1)%N= =front C. (front-1)%N= =rear D . (front+1)%N= =rear 45树中所有结点的度等于所有结点数加() A.0 B.1 C.-1 D.2 46在一棵树中,每个结点最多有()个前驱结点。 A.0 B.1 C.2 D.任意多个 47在一棵度为 3 的树中,度为 3 的结点数为
8、 2 个,度为 2 的结点数为 1 个, 度为 1 的结点点数为 2 个,则度为 0 的结点数为()个。 A.3 B.4 C.5 D.6 48在一棵二叉树上第 5 层的结点数最多为() A.16 B.15 C.8 D.32 49在一棵具有 n 个结点的二叉树的第 i 层上,最多具有()个结点。 A.2i B. 2i+1 C. 2i-1 D. 2n 50一颗具有 35 个结点的完全二叉树的深度为() A.6 B.7 C.5 D.841-45 B B D B C 46-50 B D A C A51在一棵完全二叉树中,若编号为 i 的结点存在右孩子,则右孩子结点的编 号为() A.2i B.2i-1
9、 C.2i+1 D.2i+2 52设高度为 h 的二叉树上只有度为 0 和度为 2 的结点,则此类二叉树中所包 含的结点数至少为() A.2h B.2h-1 C.2h+1 D.h+1 53按照二叉树的定义,具有 3 个结点的二叉树有()种状态。 A.5 B.4 C.3 D.30 54若查找每个元素的概率相等,则在长度为 n 的顺序表上查找任意元素的平 均查找长度为() A.n B.n+1 C.(n-1)/2 D.(n+1)/2 55顺序查找法适合于存储结构为()的线性表。 A.散列存储 B.顺序存储或链接存储 C.压缩存储 D.索引存储 56对于顺序存储的有序表(5,12,20,26,37,4
10、2,46,50,64) ,若采用 折半查找,则查找元素 26 的查找长度() A.2 B.3 C.4 D.557对线性表进行折半查找时,要求线性表必须() A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储,且结点按关键字有序排序 D.以链接方式存储,且结点按关键字有序排序 58采用折半查找方法查找长度为 n 的线性表时,每个元素的平均查找长度为 () A. O(n2) B. O(nlogn) C. O(n) D. O(logn) 59在对 n 个元素进行直接插入排序的过程中,共需要进行()趟。 A .n B.n+1 C.n-1 D.2n 60对 n 个元素进行直接插入排序时间复杂度为
11、() A. O(1) B. O(n2) C. O(n) D. O(nlog2n)51-55 C B A D B 56-60 C C D C B61在对 n 个元素进行快速排序的过程中,最好情况下需要进行()趟。 A. n B. n/2 C. logn D. 2n 62在对 n 个元素进行冒泡排序的过程中,至少需要()趟完成。 A. 1 B. n C. n-1 D. n/2 63在对 n 个元素进行快速排序的过程中,平均情况下的时间复杂度为() A. O(1) B. O(logn) C. O(n2) D. O(nlogn) 64排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空) 中
12、的元素进行比较,将其放入已排序序列的正确位置上的方法,称为() A. 插入排序 B. 起泡排序 C. 希尔排序 D. 选择排序 65用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行 排序时,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,84 则采用的排序方法是() 。 A. 选择排序 B. 希尔排序 C. 插入排序 D. 快速排序 66对下列四个序列
13、进行快速排序,各以第一个元素为基准进行第一次划分, 则在该次划分过程中需要移动元素次数最多的序列为() 。 A. 1,3,5,7,9 B. 5,7,9,1,3 C. 5,3,1,7,9 D. 9,7,5,3,1 67若对 n 个元素进行简单选择排序,则进行任一趟排序的过程中,为寻找最 小值元素所需要的时间复杂度为() A. O(1) B. O(logn) C. O(n) D. O(n2) 68若对 n 个元素进行堆排序,则在由初始堆进行每趟排序的过程中,共需要 进行()次筛运算。 A. n+1 B. n/2 C. n D. n-1 69排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序
14、列(初 始时为空)的一段的方法,称为() 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序70一组记录的关键字为(45,80,55,40,42,85) ,则利用堆排序的方法建 立的初始堆为() 。 A. (80,45,55,40,42,85) B. (85,80,55,40,42,45) C. (85,80,55,45,42,40) D. (85,55,80,42,45,40)61-65 C A D A D 66-70 B C D D B71若对 n 个元素进行直接插入排序,则进行第 i 趟排序过程前,有序表中的 元素个数为() 。 A. 1 B.i-1 C.i D. i+1
15、 72在对 n 个元素进行冒泡排序的过程中,第一趟至多需要进行()次相邻元 素之间的比较。 A. n+1 B. n/2 C. n D. n-1 73若一个元素序列基本有序,则选用()排序较快。 A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序 74快速排序方法在()情况下最不利于发挥其长处。 A.要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 75排序方法中,将整个无序序列分割成若干个小的子序列并分别进行插入排 序的方法,称为() 。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 应用 利用 运用 基础 数据结构 部分 部份 试题 答案 谜底
限制150内