数据结构（宁夏大学）智慧树知到答案章节测试2023年

第一章测试在数据结构中，从逻辑上可以把数据结构分成（

）。

A:内部结构和外部结构

B:动态结构和静态结构

C:紧凑结构和非紧凑结构

D:线性结构和非线性结构

答案:D算法分析的两个主要方面是（

）。

A:数据复杂性和程序复杂性

B:正确性和简单性

C:时间复杂度和空间复杂度

D:可读性和文档性

答案:C计算机算法必须具备输入、输出和（

）等5个特性。

A:可行性、确定性和有穷性

B:确定性、有穷性和稳定性

C:可行性、可移植性和可扩充性

D:易读性、稳定性和安全性

答案:A数据结构是研究数据的（

）以及它们之间的相互关系。

A:抽象结构，逻辑结构

B:理想结构，物理结构

C:理想结构，抽象结构

D:物理结构，逻辑结构

答案:D数据结构中，与所使用的计算机无关的是数据的（

）结构。

A:物理

B:存储

C:逻辑

D:物理和存储

答案:C组成数据的基本单位是（

）。

A:数据类型

B:数据元素

C:数据项

D:数据变量

答案:B设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（

）。

A:线性结构

B:集合

C:树型结构

D:图型结构

答案:D下面程序的时间复杂为（

）for（i=1，s=0；

i<=n；

i++）

{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}

A:O(n)

B:O(n4)

C:O(n3)

D:O(n2)

答案:D程序段s=i=0；do{i=i+1；

s=s+i；}while(i<=n)；的时间复杂度为（

）。

A:O(n)

B:O(nlog2n)

C:

O(n2)

D:O(n3/2)

答案:A算法指的是（

）

A:解决问题的计算方法

B:排序算法

C:解决问题的有限运算序列

D:计算机程序

答案:C算法就是程序。

A:对

B:错

答案:B在C语言中，inti,

*p

=

&i；是不正确的变量声明。

A:错

B:对

答案:A第二章测试在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（

）。

A:s->next=p;p->next=s

B:p->next=s;s->next=p

C:s->next=p->next;p->next=s

D:s->next=p->next;p=s

答案:C线性表是具有n个（

）的有限序列（n≠0）。

A:表元素

B:数据元素

C:字符

D:数据项

答案:B在一个单链表中，若删除p所指结点的后续结点，则执行（

）。

A:p=p->next->next;

B:p=p->next;p->next=p->next->next

C:p->next=p->next->next

D:p->next=p->next

答案:C线性表采用链式存储时，结点的存储地址（

）。

A:必须是连续的

B:必须是不连续的

C:和头结点的存储地址相连续

D:连续与否均可

答案:D在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q所指结点和p所指结点之间插入s结点，则执行（

）。

A:q->link=s;s->link=p

B:s->link=p->link;p->link=s

C:p->link=s;s->link=q

D:p->link=s->link;s->link=p

答案:A顺序存储的线性表（a0,a1,…,an-1）,在任一结点前插入一个新结点时所需移动结点的平均次数为（

）。

A:n/2

B:(n+1)/2

C:n

D:n+1

答案:A若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（

）存储方式节省时间。

A:单循环链表

B:顺序表

C:单链表

D:双链表

答案:B若某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，则采用（

）存储方式最节省时间。

A:双链表

B:单链表

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

D:单循环链表

答案:D下面关于线性表的叙述错误的是（

）。

A:线性表采用链式存储不必占用一片连续的存储空间

B:线性表采用顺序存储便于插入和删除操作的实现

C:线性表采用顺序存储必须占用一片连续的存储空间

D:线性表采用链式存储便于插入和删除操作的实现

答案:B设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（

）。

A:O(n2)

B:O(1)

C:O(n)

D:O(nlog2n)

答案:B顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（

）。

A:O(n1/2)

B:O(n2)

C:O(n)

D:O(1og2n)

答案:C设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（

）。

A:head->next==head

B:head==NULL

C:head!=

NULL

D:head->next==

NULL

答案:A线性表的唯一存储形式是链表。

A:对

B:错

答案:B已知指针P指向键表L中的某结点，执行语句P=P->next不会删除该链表中的结点。

A:对

B:错

答案:A对链表进行插入和删除操作时不必移动链表中结点。

A:错

B:对

答案:B第三章测试栈结构通常采用的两种存储结构是（

）。

A:链表存储结构和数组

B:散列方式和索引方式

C:线性存储结构和非线性存储结构

D:线性存储结构和链表存储结构

答案:A设循环队列Q[N]的头尾指针为F、R，头指针F总是指在队列中的第一个元素的前一位置，则队列中元素计数为（

）。

A:R-F

B:(F-R+N)%N

C:(R-F+N)%N

D:N-(R-F)

答案:C队列操作的原则是（

）。

A:只能进行删除

B:先进先出

C:后进先出

D:只能进行插入

答案:B一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（

）。

A:23145

B:15432

C:54132

D:23415

答案:C设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（

）。

A:6

B:4

C:2

D:3

答案:D设用链表作为栈的存储结构则退栈操作（

）。

A:必须判别栈是否为满

B:判别栈元素的类型

C:必须判别栈是否为空

D:对栈不作任何判别

答案:C设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（

）。

A:O(n)

B:O(log2n)

C:O(n2)

D:O(1)

答案:A设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（

）。

A:top=top+1;

B:top->next=top;

C:top=top-1;

D:top=top->next;

答案:D以下属于队列的基本运算的是（

）。

A:删除队头元素

B:取出最近进队元素

C:在队列中某元素之后插入元素

D:对队列中的元素排序

答案:A以下各种不带头结点的链表中最不适合用作链队的（

）。

A:只带队尾指针的非循环双链表

B:只带队尾指针的循环双链表

C:只带队首指针的循环双链表

D:只带队首指针的非循环双链表

答案:D在链队列中，即使不设置尾指针也能进行入队操作。

A:对

B:错

答案:A非空的双向循环链表中任何结点的前驱指针均不为空。

A:错

B:对

答案:B走迷宫问题只能用队列来求解。

A:对

B:错

答案:B第四章测试下面关于串的叙述中，哪一个是不正确的？（

）。

A:模式匹配是串的一种重要运算

B:串既可以采用顺序存储，也可以采用链式存储

C:串是字符的有限序列

D:空串是由空格构成的串

答案:D字符串采用结点大小为1的链表作为其存储结构，是指（

）。

A:链表的长度为1

B:链表的每个链结点的数据域中只存放了一个字符

C:链表的每个链结点的数据域中不只存放了一个字符

D:链表只存放1个字符

答案:B设串s1=’ABCDEFG’，s2=’PQRST’，下标从0开始，函数con(x,y)返回x和y串的连接串，subs(s,

i,

j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,

2,

len(s2)),

subs(s1,

len(s2),

2))的结果串是（

）。

A:CDEFGG

B:CDEFGFG

C:CDPQRST

D:CDEFG

答案:B模式串S=’aaab’，其Next数组值分别为（

）。

A:0，1，0，0

B:-1，1，2，0

C:0，0，1，2

D:-1，0，1，2

答案:D两个串相等必有串长度相等且（

）。

A:串中各对应位置字符均相等

B:两个串所含字符任意

C:两个串含有相同的字符

D:串的各位置字符任意

答案:A若有以下定义和语句:chars1=“12345”,s2=“1234”;printf(“%d”,strlen(strcpy(s1,s2)));则输出结果是（

）。

A:4

B:10

C:9

D:5

答案:Aprintf函数中用到格式符%5s,其中数字5表示输出的字符串占用5列。如果字符串长度小于5,则输出按方式（

）。

A:右对齐输出该字串,左补空格

B:从左起输出该字串,右补空格

C:按原字符长从左向右全部输出

D:输出错误信息

答案:A对于一个链串s，查找第i个元素的复杂度为（

）。

A:O(1)

B:O(n)

C:O(n2)

D:都不对

答案:CC语言中，char

c[4]=”abc”,d[4]=”abc”;等价于char

c[4]=d[4]=”abc”;

A:对

B:错

答案:BC语言中，语句static

char

c[]=“after”;执行后，数组c的长度为5。

A:错

B:对

答案:B第五章测试设有一个二维数组A[10][15]，数组按行存放，假设A[0][0]存放位置在644，每个元素占1个空间，则A[4][5]在（

）位置。

A:724

B:626

C:672

D:709

答案:D设有一个n行n列的对称矩阵A将其下三角部分按行存放在一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（

）处。

A:(2n-i-1)i/2

B:(2n-i+1)i/2

C:(i+3)i/2

D:(i+1)i/2

答案:C设已知一个稀疏矩阵的三元组如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为（

）。

A:(2,3,-1)

B:(2,1,3)

C:(3,2,-1)

D:(3,1,5)

答案:B广义表L=((a,b,c))，则L的长度和深度分别为（

）。

A:2和3

B:1和3

C:1和2

D:1和1

答案:C广义表运算，Tail(Head(((a,b,c,d,e))))=（

）。

A:a

B:(b,c,d,e)

C:c,d

D:空表

答案:B在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（

）。

A:列号

B:非零元素个数

C:行号

D:元素值

答案:CC语言中，合法的数组定义是（

）。

A:chara[]={0,1,2,3,4,5};

B:inta[5]={0,1,2,3,4,5};

C:inta[]=“string”;

D:string

s=“string”;

答案:A若有以下定义和语句:

inta[10]={1,2,3,4,5,6,7,8,9,10},p=a;不能表示a数组元素的表达式是（

）。

A:a[10]

B:p

C:*a

D:a[p-a]

答案:AC语言中，设inta[][4]={1,2,3,4,5,6,7,8,9};则数组a的第一维大小是5。

A:错

B:对

答案:AC语言中，可以在赋值语句中通过赋值运算符”=”对字符数组整体赋值。

A:对

B:错

答案:B第六章测试设二叉树根结点的层次为1，所有含有63个结点的二叉树中，最小高度是（

）。

A:7

B:6

C:5

D:4

答案:B设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在后序序列中x在y之后，则x和y的关系是（

）。

A:y是x的祖先

B:x是y的左兄弟

C:

y是x的孩子

D:x是y的右兄弟

答案:CA:D

B:B

C:A

D:C

答案:D深度为5的二叉树至多有（

）个结点。

A:10

B:32

C:31

D:16

答案:C如图所示二叉树的后序遍历序列是（

）。

A:gdbfheca

B:dgbafche

C:abdgcefh

D:gdbehfca

答案:A如图所示二叉树的中序遍历序列是（

）。

A:dgbafche

B:abdgcefh

C:abcdefgh

D:gdbehfca

答案:A在有n个结点的二叉链表中，值为非空的链域的个数为（

）。

A:n+1

B:2n+1

C:2n-1

D:n-1

答案:D对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（

）遍历实现编号。

A:中序

B:无序

C:后序

D:从根开始的层次遍历

答案:C某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（

）的二叉树。

A:任一结点无左孩子

B:空或只有一个结点

C:高度等于其结点数

D:任一结点无右孩子

答案:A一棵非空的二叉树的先序序列和后序序列正好相同，则该二叉树一定满足（

）。

A:其中任意一结点均无左孩子

B:是任意一棵二叉树

C:其中任意一结点均无右孩子

D:其中只有一个结点

答案:C一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（

）。

A:2

B:1

C:不确定

D:0

答案:B给定一棵二叉树的前序和后序遍历序列，可以唯一地确定出这棵二叉树形态。

A:错

B:对

答案:A二叉树就是度为2的树。

A:对

B:错

答案:B把一棵树转换成二叉树后，这棵二叉树形态是唯一的。

A:对

B:错

答案:A哈夫曼编码是一种前缀码。

A:错

B:对

答案:B第七章测试具有n个顶点的无向完全图的边数为（

）。

A:

n(n-1)

B:n2

C:n(n-1)/2

D:n2-1

答案:C对含有n个顶点e条边的有向图，Floyd算法的时间复杂度为（

）

A:O(n)

B:

O(n2)

C:O(ne)

D:O(n3)

答案:D如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是（

）。

A:一棵树

B:完全图

C:连通图

D:有回路的图

答案:C带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（

）。

A:第i行非∞且非0的元素个数

B:第i行非∞的元素之和

C:第i列非∞且非0的元素个数

D:第i列非∞的元素之和

答案:D以下对AOV网的描述中，错误的是（

）。

A:关键活动不近期完成就会影响整个工程的完成时间。

B:在AOV网中可能存在多条关键路径。

C:所有关键活动都提前完成，整个工程也将提前完成。

D:任何一个关键活动提前完成，整个工程也将提前完成。

答案:D设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（

）条有向边。

A:m

B:n-1

C:n

D:m-1

答案:A设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（

）。

A:O(n3)

B:O(ne)

C:O(n+e)

D:O(n2)

答案:C用邻接表存储图所用的空间大小（

）。

A:只与图的边数有关

B:与边数的平方有关

C:只与图的顶点数与关

D:与图的顶点和边数与关

答案:D深度优先遍历类似于二叉树的（

）。

A:层次遍历

B:后序遍历

C:先序遍历

D:中序遍历

答案:C用

Prim和Kruskal两种算法构造同一连通图的最小生成树，所得的最小生成树（

）。

A:可能相同也可能不同

B:是不同的

C:其余都不对

D:是相同的

答案:A任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（

）

A:错

B:对

答案:A若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。

A:对

B:错

答案:B邻接表比邻接矩阵更节省空间。

A:对

B:错

答案:B任意一个AOV网都可以有拓扑排序。

A