2020年春【中石油】数据结构第一次在线作业（100分）

skystar

【石油大学】数据结构-第一次在线作业
试卷总分:100    得分:100
第1题,1.（2.5分）程序段FORi:=n-1DOWNTO1DO FORj:=1TOiDO IFA[j]>A[j+1] THENA[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）
A、O（n）
B、O(nlogn)
C、O(n³)
D、O(n²)
正确答案:


第2题,2.（2.5分）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A、O(0)
B、O(1)
C、O(n)
D、O(n²)
正确答案:


第3题,3.（2.5分）算法的计算量的大小称为计算的
A、效率
B、复杂性
C、现实性
D、难度
正确答案:


第4题,4.（2.5分）算法的时间复杂度取决于
A、问题的规模
B、待处理数据的初态
C、A和B
正确答案:


第5题,5.（2.5分）下面关于算法说法错误的是
A、算法最终必须由计算机程序实现
B、为解决某问题的算法同为该问题编写的程序含义是相同的
C、算法的可行性是指指令不能有二义性
D、以上几个都是错误的
正确答案:


第6题,6.（2.5分）下面说法错误的是
A、算法原地工作的含义是指不需要任何额外的辅助空间
B、在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
C、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
D、同一个算法，实现语言的级别越高，执行效率就不定
正确答案:


第7题,7.（2.5分）从逻辑上可以把数据结构分为（）两大类
A、动态结构、静态结构
B、顺序结构、链式结构
C、线性结构、非线性结构
D、初等结构、构造型结构
正确答案:


第8题,8.（2.5分）以下数据结构中，哪一个是线性结构（）
A、广义表
B、二叉树
C、稀疏矩阵
D、串
正确答案:


第9题,9.（2.5分）以下那一个术语与数据的存储结构无关？
A、栈
B、哈希表
C、线索树
D、双向链表
正确答案:


第10题,10.（2.5分）在下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;
A、O(2n)
B、O(n)
C、O(n2)
D、O(log2n)
正确答案:


第11题,11.（2.5分）以下数据结构中，（）是非线性数据结构
A、树
B、字符串
C、队
D、栈
正确答案:


第12题,12.（2.5分）下列数据中，（）是非线性数据结构
A、栈
B、队列
C、完全二叉树
D、堆
正确答案:


第13题,13.（2.5分）下面关于线性表的叙述中，错误的是哪一个？（）
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
正确答案:


第14题,14.（2.5分）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A、顺序表
B、双链表
C、带头结点的双循环链表
D、单循环链表
正确答案:


第15题,15.（2.5分）某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A、单链表
B、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
正确答案:


第16题,16.（2.5分）设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。
A、单链表
B、.单循环链表
C、带尾指针的单循环链表
D、带头结点的双循环链表
正确答案:


第17题,17.（2.5分）若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。
A、单链表
B、双链表
C、单循环链表
D、带头结点的双循环链表
正确答案:


第18题,18.（2.5分）链表不具有的特点是（）
A、插入、删除不需要移动元素
B、可随机访问任一元素
C、不必事先估计存储空间
D、所需空间与线性长度成正比
正确答案:


第19题,19.（2.5分）线性表（a1,a2,...,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）
A、O（i）
B、O（1）
C、O（n）
D、O（i-1）
正确答案:


第20题,20.（2.5分）非空的循环单链表head的尾结点p↑满足（）
A、p↑.link=head
B、p↑.link=NIL
C、p=NIL
D、p= head
正确答案:


第21题,21.（2.5分）循环链表H的尾结点P的特点是（）
A、P^.NEXT:=H
B、P^.NEXT:= H^.NEXT
C、P:=H
D、P:=H^.NEXT
正确答案:


第22题,22.（2.5分）在一个以h为头的单循环链中，p指针指向链尾的条件是（）
A、p＾.next=h
B、p＾.next=NIL
C、p＾.next.＾next=h
D、p＾.data=-1
正确答案:


第23题,23.（2.5分）完成在双循环链表结点p之后插入s的操作是（）
A、p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next;
B、p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next;
C、s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ;
D、s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s;
正确答案:


第24题,24.（2.5分）在双向链表指针p的结点前插入一个指针q的结点操作是（）
A、p->  Llink=q;q->  Rlink=p;p->  Llink->  Rlink=q;q->  Llink=q；
B、p->  Llink=q;p->  Llink->  Rlink=q;q->  Rlink=p;q->  Llink=p->  Llink;
C、q->  Rlink=p;q->  Llink=p->  Llink;p->  Llink->  Rlink=q;p->  Llink=q;
D、q->  Llink=p->  Llink;q->  Rlink=q;p->  Llink=q;p->  Llink=q;
正确答案:


第25题,25.（2.5分）在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）
A、p->  next=s;s->  next=p->  next;
B、s->  next=p->  next;p->  next=s;
C、p->  next=s;p->  next=s->  next;
D、p->  next=s->  next;p->  next=s;
正确答案:


第26题,26.（2.5分）对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）
A、head==NULL
B、head→next==NULL
C、head→next==head
D、head!=NULL
正确答案:


第27题,27.（2.5分）对于栈操作数据的原则是（）。
A、先进先出
B、后进先出
C、后进后出
D、不分顺序
正确答案:


第28题,28.（2.5分）有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）
A、5 4 3 6 1 2
B、4 5 3 1 2 6
C、3 4 6 5 2 1
D、2 3 4 1 5 6
正确答案:


第29题,29.（2.5分）设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）
A、5 1 2 3 4
B、4 5 1 3 2
C、4 3 1 2 5
D、3 2 1 5 4
正确答案:


第30题,30.（2.5分）输入序列为ABC，可以变为CBA时，经过的栈操作为（）
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
正确答案:


第31题,31.（2.5分）若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是()。
A、top:=top+1; V [top]:=x
B、V [top]:=x; top:=top+1
C、top:=top-1; V [top]:=x
D、V [top]:=x; top:=top-1
正确答案:


第32题,32.（2.5分）若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A、|top[2]-top[1]|=0
B、top[1]+1=top[2]
C、top[1]+top[2]=m
D、top[1]=top[2]
正确答案:


第33题,33.（2.5分）栈在（）中应用。
A、递归调用
B、子程序调用
C、表达式求值
D、A，Ｂ，Ｃ
正确答案:


第34题,34.（2.5分）表达式a*(b+c)-d的后缀表达式是()
A、abcd*+-
B、abc+*d-
C、abc*+d-
D、-+*abcd
正确答案:


第35题,35.（2.5分）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
A、线性表的顺序存储结构
B、队列
C、线性表的链式存储结构
D、栈
正确答案:


第36题,36.（2.5分）用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。
A、仅修改队头指针
B、仅修改队尾指针
C、队头、队尾指针都要修改
D、队头,队尾指针都可能要修改
正确答案:


第37题,37.（2.5分）递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。
A、队列
B、多维数组
C、栈
D、线性表
正确答案:


第38题,38.（2.5分）假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
A、(rear-front+m)%m
B、rear-front+1
C、(front-rear+m)%m
D、(rear-front)%m
正确答案:


第39题,39.（2.5分）循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()。
A、(rear-front+m)%m
B、rear-front+1
C、rear-front-1
D、rear-front
正确答案:


第40题,40.（2.5分）循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A、rear=rear+1
B、rear=(rear+1) mod (m-1)
C、rear=(rear+1) mod m
D、rear=(rear+1)mod(m+1)
正确答案: