农村信用社招聘-计算机专业-数据结构-综合练习题四

农村信用社招聘-计算机专业-数据结构-综合练习题四

［单选题］L算法的时间复杂度取决于Oo

A.问题的规模

B.待处理数据的初态

C.A和B

D.与A和B无关

有以下算法，其时间复杂度为()。

voidfun(inti)

(

inti=0；

while(i*i*i<=n)

i++;

［单选题］2.)

A.0(n)

B0(nlogzn)

QO(Vn)

D.0(Vn)

［单选题］3.在一个双链表中，在芈*P结点之前插入*。结点的操作是()。

p->prior=q；q—>next=p；p—>prior—>ncxt=q：q—>prior=p—>prior；

Bq->prior=p->prior：p—>prior—>next=q；q—>next=p：p—>prior=q—next；

Cq->next=p；p—>next=q；q—>prior—>next=q；q—>next=p；

Dq->ncxt=p；p->prior—>next=q；q->prior=p->prior；p->prior=q；

分析以下程序段时间复杂度()。

for(i=0：i<n：i++)〃①

(

y=y+l；〃②

for(j=0；j<=2*n；j++)/t@

x++；//©

［单选题］4.}

A.0(1)

B.0(logn)

C.0(n)

D.0(n2)

［单选题］5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行

插入和删除运算，则利用O存储方式最节省时间。

A.顺序表

B.双链表

C.带头结点的双循环链表

D.单循环链表

［单选题］6.已知一个线性表为(38,25,74,63,52,48),假定采用H(K)

二Kn:od7计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，

则在该散列表上进行查找的平均查找长度为();若利用链地址法处理冲突，

则在该散列上进行查找的平均查找长度为Oo

A.1.5,1

B.1.7,3/2

C.2,4/3

D.2.3,7/6

［单选题］7.以下说法正确的是()o

A.数据结构的逻辑结构是指数据的各数据项之间的逻辑关系。

B.数据元素是数据结构的最小单位。

C.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的

独立。

D.判断某个算法是否容易阅读是算法分析的任务之一。

［单选题］8.输入序列为ABC,可以变为CBA时。经过的栈操作为()o

A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,pop

C.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop

［单选题］9.非空的循环单链表head的尾结点P满足的条件是()o

A.F.link=head

B.p.link=NIL

C.p=NIL,

D.p=head

［单选题］10.使用双链表存储线性表，其优点是()。1.提高查找速度II.更方

便数据的插入和删除ni,节约存储空间N.很快回收存储空间

A.I、II

B.I、IV

C.仅II

D.II、HI、IV

［单选题］11.若用单链表来表示队列，则应该选用Oo

A.带尾指针的非循环链表

B.带尾指针的循环链表

C.带头指针的非循环链表

D.带头指针的循环链表

［单选题］12.在AOE网络中关键路径叙述正确的是()o

A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工

程所需的最短时间

B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工

程所需的最短时间

C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工

程所需的最长时间

D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工

程所需的最长时间

［单选题］13.若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于

该矩阵()o

A.第i行中值为1的元素个数

B.所有值为1的元素个数

C.第i行及第i列中值为1的元素总个数

D.第i列中值为1的元素个数

［单选

题］14.

用prim算法求下述邻接矩阵表示的连通带权图的最小生成树，在算法执行的某一时刻，

已选取的顶点集合为U二{1,2}。边的集合TF={(1,2)},要选取下一权值最小的边，应

当从()中选取。

8212108

2CO889

128863

10co687

oc9378

A.{(1,4),⑵3),(2,5))

B.{(3,5),(3,4),(4,5))

C.{(1,3),(3,4),(3,5))

D.{(2,3),(3,4),(2,5))

［单选题］15.对于一个长度为n的任惫表进行排序，至少需要进行的比较次数是

A.0(n)

B.O(n2)

C.0(logo)

D.0(nlogn)

［单选题］16.将两个长度为N的有序表归并到一个长度为2N的有序表，最少需

要比较的次数是(),最多需要比较的次数是()o

A.N,2N-1

B.N-l,2N

C.N,2N

D.N-l,2N-1

［单选题］17.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向

图G有n介结点，其邻接矩阵为且压缩存储在B［l..k］,则k

的值至少为Oo

A.n(n+1)/2

B.J/2

C.(n-1)(n+1)/2

D.n(n-l)/2

［单选题］18.用链接方式存储的队列，在进行删除运算时()。

A.仅修改头指针

B.仅修改尾指针

C.头、尾指针都要修改

D.头、尾指针可能都要修改

［单选题］19.循环链表的主要优点是()。

A.不再需要头指针

B.已知某个结点的位置后，能很容易找到它的直接前驱结点

C.在进行删除操作后，能保证链表不断开

D.从表中任一结点出发都能遍历整个链表

［单选题］20.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存

储方式最节省时间的是O.

A.单链表

B.双链表

C.单循环链表

D.顺序表

［单选题］21.设线性表有n个元素，以下操作中，在顺序表上实现比在链表上实

现效率更高的是Oo

A.输出第i个元素值

B.交换第1个元素与第2个元素的值

C.顺序输出这n个元素的值

D.输出与给定值x相等的元素存线性表中的序号

［单选题］22.头指针为head的带头结点的循环链表为空的判定条件是()。

A.head=null

B.head——>next=null

C.head—>next=head

D.head—>null

［单选题］23.已知有一维数组A［O...mXnT］,若要对应为m行n列的矩阵，则

下面的对应关系()，可将元素A［k］(OWVkWVmXn)表示成矩阵的第i

行、第j列的元素(OWiWn,0匀<n)o

A.i=k/n,j=k%m

B.i=k/m,j=k%m

C.i=k/n,j=k%n

D.i=k/m,j=k%n

［单选题］24.栈在()中应用。

A.递归调用

B.子程序调用

C.表达式求值

D.A,B,C

［单选题］25.引入二叉线索树的目的是()。

A.加快查找结点的前驱或后继的速度

B.为了能在二叉树中方便地进行插入与删除

C.为了能方便地找到双亲

D.使二叉树的遍历结果唯一

［单选题］26.表达式a*(b+c)-d的后缀表达式是()o

A.abcd*+-

B.abc+*d-

C.abc*+d-

D.-+*abcd

［单选题］27.按照二叉树的定义，具有3个结点的二叉树有()种。

A.3

B.4

C.5

D.6

［单选

题］28.

下面说法错误的是()。

(1)算法原地工作的含义是指不需要任何额外的辅助空间。

(2)在相同的规模n下，复杂度O(n)的算法在时间上后、是优于复杂度O(29的算法V

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)

B.(1)、(2)

C.(1)、⑷

D.(3)

［单选题］29.将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度

为()。

A.0(n)

B.0(1)

C.0(m)

D.0(m+n)

［单选题］30.在一个氏度为n(n>l)的带头结点单链表h上，另设有尾指针r

(指向尾结点)。与链表的长度有关的操作是Oo

A.删除单链表中的第一个元素

B.删除单链表中的最后一个元素

C.在单链表第一个元素前插入一个新元素

D.在单链表最后一个元素后插入一个新元素

［单选题］31.若一个栈的输入序列为1,2,3…，n,输出序列的第一个元素是

i，则第j个输出元素是O。

A.i-j-1

B.i-j

C.j-i+1

D.不确定

［单选题］32.一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是

()O

A.5,4,3,2,1

B.4,5,3,2,1

C.4,3,5,1,2

D.1,2,3,4,5

［单选题］33.若G是一个具有36条边的非连通无向图(不含自回路和多重

边)，则图G至少有()个顶点。

A.11

B.10

C.9

D.8

［单选题］34.下面术语中，与数据的存储结构无关的是()。

A.循环队列

B.栈

C.散列表

D.单链表

［单选题］35.在双向循环链表中，在p所指的结点之后插入指针f所指的新结

点，其操作步骤是OO

Ap->next=f；f->prior=p：p->next->prior=f；f->next=p->next

BP->next=f；p->nexl->prior=f；f->prior=p；f->next=P->next

Cf->prior=p；f->next=p->next；p->next=f；p—>next—>prior=f

D.f->prior=p；f->next=p->next；p—>next->prior=f；p->next=f

［单选题］36.在下列查找的方法中，平均查找长度与结点个数n无关的查找方法

是()。

A.顺序查找

B.二分法

C.利用二叉搜索树

D.利用哈希(hash)表

［单选题］37.表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概

率相等时，删除一个元素所需移动元素的平均个数为()。

A.n

B.n/2

C.(n-1)/2

D.(n+1)/2

［单选题］38.设线性表(顺序存储方式)的每个元素占8个存储单元。第一个单

元的存储地址为100,则第6个元素占用的最后一个存储单元的地址为()。

A.139

B.140

C.147

D.148

［单选题］39.在长度为n(H>1)的()上，删除第一个元素.其时间复杂度为

0(n)o

A.只有首结点指针的不带头结点的循环单链表

B.只有尾结点指针的不带头结点的循环单链表

C.只有尾结点指针的带头结点的循环单链表

D.只有头结点的循环单链表

［单选题］40.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈So

若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S

的容量至少是()o

A.1

B.2

C.3

D.4

［单选题］41.关于AVL(平衡二叉树)，下列说法错误的是()o

A.左子树与右子树高度差最多为1

B.插入操作的时间复杂度为0(logn)

C.平衡二叉树是二叉排序树中的一种

D.使用平衡二叉树的目的是为了节省空间

［单选题］42.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上,

并且其时间性能受数据初始特性影响的是()。

A.直接插入排序

B.快速排序

C.直接选择排序

D.堆排序

［单选题］43.求解Hanoi问题时，若初始有5个圆盘，则移动圆盘的次数是

()O

A.7

B.15

C.31

D.5

有以下算法，其时间复杂度为()。

voidfun(intn)

(

inti,j,x=0：

for(i=I；i<n；i++)

for(j=n：j>=i+1：j-)

x++；

［单选题］44.}

A.0(n)

B0(nlog2n)

2

c0(n)

D.0(n3)

［单选

在非空循环双链表中q所指的结点前插入一个由P所指结点的过程依次为：()

题］45P->next=q；p->prior=q—>prior；q—>prior=pa

A.q—>next=p；

Bq>prior—>next-p；

Qq—>prior—>ncxt=p；

Dq—>next—>prior=p；

［单选题］46.用链接方式存储的队列，在进行删除运算时，下面正确的是()。

A.仅修改头指针

B.仅修改尾指针

C.头、尾指针都要修改

D.头、尾指针可能都要修改

［单选题］47.以下与数据的存储结构无关的术语是()o

A.循环队列

B.链表

C.哈希表

D.栈

［单选题］48.数据的存储结构是指()o

A.数组类型

B.指针类型

C.数据之间的逻辑关系

D.数据之间的物理关系

［单选

题］49.一个算法的执行时间为二(3n2+2nlog2n+4n-7)/10n),其时间复杂度为()。

A.O(3n2)

B.O(2nlog2n)

C.O(3n2/10)

D.C(n)

［单选题］50.()的邻接矩阵是对称矩阵。

A.有向图

B.无向图

C.AOV网

D.AOF网

［单选

题］51.

在一个长度为n的顺序存储线性表中，删除第i个元素(l<i<n+1)时，需要从前向后依

次前移()•个元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

［单选题］52.(1)静态链表既有顺序存储的优点，乂有动态链表的优点。所

以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个

数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在

元素的插入、删除上类似，不需做元素的移动。以上错误的是Oo

A.(1),(2)

B.(1)

C.(1),(2),(3)

D.(2)

［单选题］53.已知输入序列为abed,经过输出受限的双端队列后，能得到的输出

序列是()O

A.dacb

B.cadb

C.dbea

D.以上答案都不对

下面程序段中，执行S语句的次数为()。

for(inti=l；i<=n；i++)

for（intj=l；j<=i：j++）

［单选题］54.S；

A.n2

B.n2/2

C.n（n+1）

D.n(n+1)/2

［单选题］55.对于栈操作数据的原则是()o

A.先进先出

B.后进先出

C.后进后出

D.不分顺序

［单选题］56.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探

测多个位置，在查找成功的情况下，所探测的这些位置的键值Oo

A.一定都是同义词

B.一定都不是同义词

C.不一定都是同义词

D.都相同

［单选题］57.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少

的是（）。

A.94,32,40,90,80,46,21,69

B.32,40,21,46,69,94,90,80

C.21,32,46,40,80,69,90,94

D.90,69,80,46,21,32,94,40

［单选题］58.若一组记录的关键码为(46,79,56,38,40,84),则利用快速

排序的方法，以第一个记录为基准得到的一次划分结果为Oo

A.38,40,46,56,79,84

B.40,38,46,79,56,84

C.40,38,46,56,79,84

D.40,38,46,84,56,79

［单选题］59.线性表的静态链表存储结构与顺序存储结构相比优点是()o

A.所有的操作算法实现简单

B.便于随机存取

C.便于插入与删除

D.便于利用零散的存储器空间

［单选题］60.二叉树的先序遍历和中序遍历如下：先序遍历：EniTGJK；中序遍

历：HFIEJKG。该二叉树根的右子树的根是()o

A.E

B.F

C.G

D.H

［单选题］61.根据使用频率，构造的5个字符的哈夫曼编码不可能是()。

A.111,110,10,01,00

B.000,00b010,Oil,1

C.100,11,10,1,0

D.001,000,01,11,10

［单选题］62.设散列表表长m=14,散列函数H(k)=kMODll,表中已有15,38,

61,84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是()o

A.8

B.3

C.5

D.9

［单选题］63.将10个元素散列到100000个单元的哈希表中，()产生冲突？

A.一定会

B.一定不会

C.仍可能会

D.可能不会

［单选题］64.在一个双链表中，删除P结点之后的二个结点的操作是()o

Ap—>next=p—>next—>next；p—>next—>next—>prior=p；

Bp->next—>prior=p；p—>next=p->ncxt—>next：

Cp->next=p->next—>next；p->ncxt->prior=p：

D.p->next—>next=p"•>ncXt；p—>ncxt—>prior=p；

［单选题］65.下面关于Prim算法和KruskAl算法的时间复杂度正确的是()。

A.Frim算法的时间复杂度与网中的边数有关，适合于稀疏图

B.Frim算法的时间复杂度与网中的边数无关，适合于稠密图

C.KruskAl算法的时间复杂度与网中的边数有关，适合于稠密图

D.KruskAl算法的时间复杂度与网中的边数无关，适合于稀疏图

［单选题］66.在()存储结构中，数据结构中元素的存储地址与其关键字之间存

在某种映射关系。

A.树形存储结构

B.链式存储结构

C.索引存储结构

D.散列存储结构

［单选题］67.()不是算法的基本特性。

A.可行性

B.长度有限

C.在规定的时间内完成

D.确定性

［单选题］68.在具有n个结点的顺序表，算法的时间复杂度是0(1)的操作是

()O

A.访问第i个结点(145)和求第i个结点的直接前驱(2Sign)

B,在第i个结点后插入一个新结点

C,删除第i个结点(l<i<n)

D.将n个结点从小到大排序

［单选题］69.在一个单链表HL中，若要向表头插入一个由指针P指向的结点，

则执行()o

A.HL=P；P—>next=HL；

B.F—>next=HL