超星​数据结构（4期）答案

超星尔雅数据结构（4期）尔雅课答案 主讲教师：秦锋 教授 /安徽工业大学

1.8单元测试

1、【单选题】根据数据元素之间关系的不同特性,以下解释错误的是( )

A、集合中任何两个结点之间都有逻辑关系但组织形式松散

B、线性结构中结点形成1对1的关系

C、树形结构具有分支、层次特性,其形态有点像自然界中的树

D、图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接

答案：A

2、【单选题】关于逻辑结构,以下说法错误的是( )。

A、逻辑结构是独立于计算机的

B、运算的定义与逻辑结构无关

C、同一逻辑结构可以采用不同的存储结构

D、一些表面上很不相同的数据可以有相同的逻辑结构

E、逻辑结构是数据组织的某种"本质性"的东西

答案：B

3、【单选题】下面关于算法说法正确的是( )。

A、计算机程序一定是算法

B、算法只能用计算机高级语言来描述

C、算法的可行性是指指令不能有二义性

D、以上几个都是错误的

答案：D

4、【单选题】程序段 for(i=n-1;i>=0;i--) for(j=1;j<=n;j++) if A[j]>A[j+1] A[j]与A[j+1]对换; 其中n为正整数,则最后一行的语句频度在最坏情况下是( )。

A、O(n)

B、O(n2)

C、O(n3)

D、O(nlog2n)

答案：B

5、【单选题】下面关于算法的说法正确的是( )。

A、算法的时间效率取决于算法所花费的CPU时间

B、B. 在算法设计中不能用牺牲空间代价来换取好的时间效率

C、C. 算法必须具有有穷性、确定性等五个特性

D、D. 通常用时空效率来衡量算法的优劣

答案：C

6、【判断题】数据的逻辑结构是指数据的各数据项之间的逻辑关系。

答案：×

7、【判断题】数据元素是数据的最小单位。

答案：×

8、【判断题】程序一定是算法。

答案：×

9、【判断题】数据的物理结构是指数据在计算机内的实际存储形式。

答案：对

10、【判断题】数据结构的抽象操作的定义与具体实现有关。

答案：×

2.7单元测试

1、【单选题】1.线性表是( )。

A、一个有限序列,可以为空

B、一个有限序列,不能为空

C、一个无限序列,可以为空

D、一个无序序列,不能为空

答案：A

2、【单选题】2. 从一个具有n个结点的单链表中查找值为x的结点,在查找成功情况下,需平均比较( )个结点。

A、n

B、n/2

C、(n-1)/2

D、(n+1)/2

答案：D

3、【单选题】3.线性表采用链式存储时,其各元素存储地址( )。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续与否均可以

答案：D

4、【单选题】4.用链表表示线性表的优点是( )。

A、便于随机存取

B、花费的存储空间较顺序存储少

C、便于插入和删除

D、数据元素的物理顺序与逻辑顺序相同

答案：C

5、【单选题】删除速度快,但不能随机存取。

A、链接表

B、顺序表

C、顺序有序表

D、上述三项无法比较

答案：A

6、【单选题】6.若希望从链表中快速确定一个结点的前驱,则链表最好采用( )方式。

A、单链表

B、循环单链表

C、双向链表

D、任意

答案：C

7、【单选题】7.下面关于线性表的叙述错误的是( )。

A、线性表采用顺序存储,必须占用一片地址连续的单元

B、线性表采用顺序存储,便于进行插入和删除操作

C、线性表采用链式存储,不必占用一片地址连续的单元

D、线性表采用链式存储,便于进行插入和删除操作

答案：B

8、【单选题】10.在循环双链表的p所指结点之后插入s所指结点的操作是( )。

A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;

C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

D、s->prior=p; s->next=p->next; p->next->prior=s; p->next =s;

答案：D

9、【单选题】9.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。

A、单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

答案：D

10、【单选题】8.带头结点的单链表head为空的判定条件是( )。

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head!=NULL

答案：B

11、【判断题】1.链表中的头结点仅起到标识的作用。

答案：×

12、【判断题】2.顺序存储的线性表可以按序号随机存取。

答案：对

13、【判断题】3.线性表采用链表存储时,存储空间可以是不连续的。

答案：对

14、【判断题】4.静态链表中地址相邻的元素具有前驱后继关系。

答案：×

15、【判断题】5.对任何数据结构,链式存储结构一定优于顺序存储结构。

答案：×

16、【判断题】7.循环链表可以在尾部设置头指针。

答案：对

17、【判断题】6.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。

答案：×

18、【判断题】8.为了方便插入和删除,可以使用双向链表存放数据。

答案：对

19、【判断题】10.取线性表的第i个元素的时间同i的大小有关。

答案：×

20、【判断题】9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。

答案：×

3.7单元测试

1、【单选题】1. 栈和队列的共同点是( )。

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

答案：C

2、【单选题】2. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是( )。

A、n-i-1

B、n-i

C、n-i+1

D、不确定

答案：C

3、【单选题】3. 设abcdef以所给的次序进栈,若在进栈操作时,允许出栈操作,则下面得不到的序列为( )。

A、fedcba

B、bcafed

C、dcefba

D、cabdef

答案：D

4、【单选题】4. 递归过程或函数调用时,处理参数及返回地址,要用一种称为( )的数据结构。

A、队列

B、多维数组

C、栈

D、线性表

答案：C

5、【单选题】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

答案：C

6、【单选题】6. 用链式存储的队列,在进行删除运算时( )。

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

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

答案：D

7、【单选题】7. 栈应用在( )。

A、递归调用

B、子程序调用

C、表达式求值

D、A,B,C

答案：D

8、【单选题】8.一个递归算法必须包括( )。

A、递归部分

B、终止条件和递归部分

C、迭代部分

D、终止条件和迭代部分

答案：B

9、【单选题】9.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( )。

A、(rear-front+m)%m

B、rear-front+1

C、(front-rear+m)%m

D、(rear-front)%m

答案：A

10、【单选题】10. 循环队列存储在数组A[0..m]中,则入队时队尾的操作为( )。

A、rear=rear+1

B、rear=(rear+1)%(m-1)

C、rear=(rear+1) % m

D、rear=(rear+1)%(m+1)

答案：D

11、【判断题】1. 消除递归一定需要使用栈。

答案：×

12、【判断题】2. 栈是实现过程和函数调用所必需的结构。

答案：对

13、【判断题】3. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。

答案：对

14、【判断题】4. 用递归方法设计的算法效率高。

答案：×

15、【判断题】5. 栈与队列是一种特殊的线性表。

答案：对

16、【判断题】6. 队列逻辑上是一端既能增加又能减少的线性表。

答案：×

17、【判断题】7. 循环队列通常浪费一个存储空间。

答案：对

18、【判断题】8. 循环队列也存在空间溢出问题。

答案：对

19、【判断题】9. 栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。

答案：对

20、【判断题】10. 任何一个递归过程都可以转换成非递归过程。

答案：对

4.4单元测试

1、【单选题】1.如下陈述中正确的是( )。

A、串是一种特殊的线性表

B、串的长度必须大于零

C、串中元素只能是字母

D、空串就是空白串

答案：A

2、【单选题】2.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。

A、求子串

B、联接

C、匹配

D、求串长

答案：C

3、【单选题】3.串"ababaaababaa"的next数组为( )。

A、012345678999

B、012121111212

C、011234223456

D、012301232234

答案：C

4、【单选题】4.串是( )。

A、不少于一个字母的序列

B、任意个字母的序列

C、不少于一个字符的序列

D、有限个字符的序列

答案：D

5、【单选题】串的长度是指( )。

A、串中所含不同字母的个数

B、串中所含字符的个数

C、串中所含不同字符的个数

D、串中所含非空格字符的个数

答案：B

6、【单选题】10.若串S="English",其子串的个数是( )。

A、9

B、16

C、36

D、28

答案：D

7、【单选题】9.设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为( )。

A、2n-1

B、n2

C、(n2/2)+(n/2)

D、(n2/2)+(n/2)-1

答案：D

8、【单选题】8.若串S1="ABCDEFG", S2="9898" ,S3="###",S4="012345",执行StrConcat(StrRep(S1,SubStr(S1,StrLength(S2),StrLength(S3)),S3),SubStr(S4,StrIndex(S2, "8"),StrLength(S2)))其结果为( )。

A、"ABC###G0123"

B、"ABCD###2345"

C、"ABC###G2345"

D、"ABC###G1234"

答案：D

9、【单选题】6.若s="1234ab567abcdab0",t="ab",r=""(空串),串替换StrRep(s,t,r)的结果是( )。

A、"1234ab567abcdab0"

B、"1234ab567abcd "

C、"1234567cd0"

D、"1234 567 cd 0"

答案：C

10、【单选题】7.从顺序串中删除一个字符的时间复杂度为( )。

A、O(1)

B、O(n)

C、O(1og2n)

D、O(nlog2n)

答案：B

11、【判断题】1.KMP算法的特点是在模式匹配时指示主串的指针不会变小。

答案：对

12、【判断题】2.只要串采用定长顺序存储,串的长度就可立即获得,不需要用函数求。

答案：×

13、【判断题】3.next函数值序列的产生仅与模式串有关。

答案：对

14、【判断题】4.空格串就是由零个字符组成的字符序列。

答案：×

15、【判断题】5.从串中取若干个字符组成的字符序列称为串的子串。

答案：×

16、【判断题】6.串名的存储映象就是按串名访问串值的一种方法。

答案：对

17、【判断题】7.两个串含有相等的字符,它们一定相等。

答案：×

18、【判断题】8.在插入和删除操作中,链式串一定比顺序串方便。

答案：对

19、【判断题】9.串的存储密度与结点大小无关。

答案：×

20、【判断题】10.用堆结构存储串必须建立索引表。

答案：对

5.5单元测试

1、【单选题】1.数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。

A、1175

B、1180

C、1205

D、1210

答案：A

2、【单选题】2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,a00存放于数组B[1]中,则在B中确定aij(i

A、i*(i+1)/2+j

B、j*(j+1)/2+i

C、i*(i+1)/2+j+1

D、j*(j+1)/2+i+1

答案：C

3、【单选题】8.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: GetTail (GetHead (GetTail (C))) =( )。

A、(a)

B、A

C、a

D、(b)

E、b

F、(A)

答案：F

4、【单选题】7.已知广义表LS=((a,b,c),(d,e,f)),运用GetHead和GetTail函数取出LS中原子e的运算是( )。

A、GetHead (GetTail (LS))

B、GetHead (GetTail (GetHead (GetTail (LS))))

C、GetTail (GetHead (LS))

D、GetHead (GetTail (GetTail (GetHead (LS))))

答案：B

5、【单选题】4.对矩阵压缩存储是为了( )。

A、方便压缩

B、节省空间

C、方便存储

D、提高运算速度

答案：B

6、【单选题】3.设二维数组A[1.. m,1.. n](即m行n列)按行存储在数组B[1.. m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为( )。

A、(i-1)*n+j

B、(i-1)*n+j-1

C、i*(j-1)

D、j*m+i-1

答案：A

7、【单选题】5.设广义表L=((a,b,c)),则L的长度和深度分别为( )。

A、1和1

B、1和3

C、1和2

D、2和3

答案：C

8、【单选题】6.有一个100*90的稀疏矩阵,非0元素有10个,设每个