数据结构(宁夏大学)智慧树知到课后章节答案2023年下宁夏大学

数据结构〔宁夏大学〕智慧树知到课后章节答案2023年下宁夏大学宁夏大学第一章测试在数据结构中，从逻辑上可以把数据结构分成〔

〕。A:动态结构和静态结构B:紧凑结构和非紧凑结构C:线性结构和非线性结构D:内部结构和外部结构答案:线性结构和非线性结构算法分析的两个主要方面是〔

〕。A:时间复杂度和空间复杂度B:数据复杂性和程序复杂性C:可读性和文档性D:正确性和简单性答案:时间复杂度和空间复杂度计算机算法必须具备输入、输出和〔

〕等5个特性。A:易读性、稳定性和平安性B:确定性、有穷性和稳定性C:可行性、确定性和有穷性D:可行性、可移植性和可扩充性答案:可行性、确定性和有穷性数据结构是研究数据的〔

〕以及它们之间的相互关系。A:物理结构，逻辑结构B:理想结构，物理结构C:抽象结构，逻辑结构D:理想结构，抽象结构答案:物理结构，逻辑结构数据结构中，与所使用的计算机无关的是数据的〔

〕结构。A:逻辑B:物理C:物理和存储D:存储答案:逻辑组成数据的根本单位是〔

〕。

A:数据项B:数据变量C:数据元素D:数据类型答案:数据元素设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，那么数据结构A是〔

〕。A:图型结构B:线性结构C:树型结构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(n2)B:O(n3)C:O(n4)D:O(n)答案:O(n2)程序段s=i=0；do{i=i+1；

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

〕。A:

O(n2)B:O(n)C:O(n3/2)D:O(nlog2n)答案:O(n)算法指的是〔

〕A:计算机程序B:排序算法C:解决问题的有限运算序列D:解决问题的计算方法答案:解决问题的有限运算序列算法就是程序。A:对B:错答案:错在C语言中，inti,

*p

=

&i；是不正确的变量声明。A:对B:错答案:错第二章测试在一个单链表中，假设p所指结点不是最后结点，在p之后插入s所指结点，那么执行〔

〕。A:s->next=p;p->next=sB:s->next=p->next;p->next=sC:p->next=s;s->next=pD:s->next=p->next;p=s答案:s->next=p->next;p->next=s线性表是具有n个〔

〕的有限序列〔n≠0〕。A:数据元素B:数据项C:表元素D:字符答案:数据元素在一个单链表中，假设删除p所指结点的后续结点，那么执行〔

〕。A:p->next=p->nextB:p=p->next;p->next=p->next->nextC:p->next=p->next->nextD:p=p->next->next;答案:p->next=p->next->next线性表采用链式存储时，结点的存储地址〔

〕。A:连续与否均可

B:和头结点的存储地址相连续C:必须是连续的

D:必须是不连续的答案:连续与否均可

在一个单链表中，q所指结点是p所指结点的前驱结点，假设在q所指结点和p所指结点之间插入s结点，那么执行〔

〕。A:s->link=p->link;p->link=sB:p->link=s;s->link=qC:q->link=s;s->link=pD:p->link=s->link;s->link=p答案:q->link=s;s->link=p顺序存储的线性表〔a0,a1,…,an-1〕,在任一结点前插入一个新结点时所需移动结点的平均次数为〔

〕。A:(n+1)/2B:nC:n+1D:n/2答案:n/2假设线性表最常用的操作是存取第i个元素及其前趋的值，那么采用〔

〕存储方式节省时间。A:顺序表B:单链表C:单循环链表D:双链表

答案:顺序表假设某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，那么采用〔

〕存储方式最节省时间。A:单链表B:单循环链表C:双链表D:带头结点的双循环链表答案:单循环链表下面关于线性表的表达错误的选项是〔

〕。A:线性表采用链式存储便于插入和删除操作的实现B:线性表采用顺序存储必须占用一片连续的存储空间C:线性表采用链式存储不必占用一片连续的存储空间D:线性表采用顺序存储便于插入和删除操作的实现答案:线性表采用顺序存储便于插入和删除操作的实现设一维数组中有n个数组元素，那么读取第i个数组元素的平均时间复杂度为〔

〕。A:O(1)B:O(n)C:O(n2)D:O(nlog2n)答案:O(1)顺序查找不管在顺序线性表中还是在链式线性表中的时间复杂度为〔

〕。A:O(1og2n)B:O(n)C:O(n2)D:O(n1/2)答案:O(n)设带有头结点的单向循环链表的头指针变量为head，那么其判空条件是〔

〕。A:head!=

NULLB:head->next==

NULLC:head->next==headD:head==NULL答案:head->next==head线性表的唯一存储形式是链表。A:错B:对答案:错指针P指向键表L中的某结点，执行语句P=P->next不会删除该链表中的结点。A:对B:错答案:对对链表进行插入和删除操作时不必移动链表中结点。A:对B:错答案:对第三章测试栈结构通常采用的两种存储结构是〔

〕。A:链表存储结构和数组B:线性存储结构和链表存储结构C:散列方式和索引方式D:线性存储结构和非线性存储结构答案:链表存储结构和数组设循环队列Q[N]的头尾指针为F、R，头指针F总是指在队列中的第一个元素的前一位置，那么队列中元素计数为〔

〕。A:R-FB:N-(R-F)C:(F-R+N)%ND:(R-F+N)%N

答案:(R-F+N)%N

队列操作的原那么是〔

〕。A:先进先出B:只能进行删除C:只能进行插入D:后进先出答案:先进先出一个栈的输入序列为12345，那么以下序列中不可能是栈的输出序列的是〔

〕。A:54132B:15432C:23145D:23415答案:54132设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，假设6个元素出列的顺序为E2、E4、E3、E6、E5和E1，那么栈S的容量至少应该是〔

〕。A:2B:6C:3D:4答案:3设用链表作为栈的存储结构那么退栈操作〔

〕。A:判别栈元素的类型B:对栈不作任何判别C:必须判别栈是否为空D:必须判别栈是否为满答案:必须判别栈是否为空设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，那么该操作的时间复杂度为〔

〕。A:O(n2)B:O(1)C:O(log2n)D:O(n)答案:O(n)设指针变量top指向当前链式栈的栈顶，那么删除栈顶元素的操作序列为〔

〕。A:top=top-1;B:top=top+1;C:top=top->next;D:top->next=top;答案:top=top->next;以下属于队列的根本运算的是〔

〕。A:对队列中的元素排序B:删除队头元素C:取出最近进队元素D:在队列中某元素之后插入元素答案:删除队头元素以下各种不带头结点的链表中最不适合用作链队的〔

〕。A:只带队首指针的循环双链表B:只带队首指针的非循环双链表C:只带队尾指针的非循环双链表D:只带队尾指针的循环双链表答案:只带队首指针的非循环双链表在链队列中，即使不设置尾指针也能进行入队操作。A:对B:错答案:对非空的双向循环链表中任何结点的前驱指针均不为空。A:错B:对答案:对走迷宫问题只能用队列来求解。A:错B:对答案:错第四章测试下面关于串的表达中，哪一个是不正确的？〔

〕。A:串是字符的有限序列B:空串是由空格构成的串C:串既可以采用顺序存储，也可以采用链式存储D:模式匹配是串的一种重要运算答案:空串是由空格构成的串字符串采用结点大小为1的链表作为其存储结构，是指〔

〕。A:链表的每个链结点的数据域中不只存放了一个字符B:链表的长度为1C:链表只存放1个字符D:链表的每个链结点的数据域中只存放了一个字符答案:链表的每个链结点的数据域中只存放了一个字符设串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:CDPQRSTB:CDEFGFGC:CDEFGD:CDEFGG答案:CDEFGFG模式串S=’aaab’，其Next数组值分别为〔

〕。A:-1，0，1，2B:0，0，1，2C:0，1，0，0D:-1，1，2，0答案:-1，0，1，2两个串相等必有串长度相等且〔

〕。A:串中各对应位置字符均相等B:两个串含有相同的字符C:两个串所含字符任意D:串的各位置字符任意答案:串中各对应位置字符均相等假设有以下定义和语句:char*s1="12345",*s2="1234";printf("%d\n",strlen(strcpy(s1,s2)));那么输出结果是〔

〕。A:4B:9C:5D:10答案:4printf函数中用到格式符%5s,其中数字5表示输出的字符串占用5列。如果字符串长度小于5,那么输出按方式〔

〕。A:按原字符长从左向右全部输出B:从左起输出该字串,右补空格C:右对齐输出该字串,左补空格D:输出错误信息答案:右对齐输出该字串,左补空格对于一个链串s，查找第i个元素的复杂度为〔

〕。A:都不对B:O(n)C:O(1)D:O(n2)答案:O(n2)C语言中，char

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

c[4]=d[4]=”abc”;A:错B:对答案:错C语言中，语句static

char

c[]=“after”;执行后，数组c的长度为5。A:错B:对答案:对第五章测试设有一个二维数组A[10][15]，数组按行存放，假设A[0][0]存放位置在644，每个元素占1个空间，那么A[4][5]在〔

〕位置。A:724B:672C:709D:626答案:709设有一个n行n列的对称矩阵A将其下三角局部按行存放在一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中〔

〕处。A:(i+1)*i/2B:(2n-i+1)*i/2

C:(i+3)*i/2D:(2n-i-1)*i/2答案:(i+3)*i/2设一个稀疏矩阵的三元组如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),那么其转置矩阵的三元组表中第3个三元组为〔

〕。A:(3,1,5)B:(2,3,-1)C:(2,1,3)D:(3,2,-1)

答案:(2,1,3)广义表L=((a,b,c))，那么L的长度和深度分别为〔

〕。A:1和1B:2和3C:1和3D:1和2答案:1和2广义表运算，Tail(Head(((a,b,c,d,e))))=〔

〕。A:(b,c,d,e)B:c,dC:空表D:a答案:(b,c,d,e)在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的〔

〕。A:元素值B:行号C:列号D:非零元素个数答案:行号C语言中，合法的数组定义是〔

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

s="string";

C:inta[5]={0,1,2,3,4,5};D:inta[]="string";答案:chara[]={0,1,2,3,4,5};假设有以下定义和语句:

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

〕。A:*pB:*a

C:a[p-a]D:a[10]答案:a[10]C语言中，设inta[][4]={1,2,3,4,5,6,7,8,9};那么数组a的第一维大小是5。A:对B:错答案:错C语言中，可以在赋值语句中通过赋值运算符”=”对字符数组整体赋值。A:对B:错答案:错第六章测试设二叉树根结点的层次为1，所有含有63个结点的二叉树中，最小高度是〔

〕。A:6B:4C:7D:5答案:6设结点x和结点y是二叉树T中的任意两个结点，假设在前序序列中x在y之前，而在后序序列中x在y之后，那么x和y的关系是〔

〕。A:x是y的右兄弟B:

y是x的孩子C:x是y的左兄弟D:y是x的祖先答案:

y是x的孩子A:DB:CC:AD:B答案:C深度为5的二叉树至多有〔

〕个结点。A:31B:32C:16D:10答案:31如下图二叉树的后序遍历序列是〔

〕。A:dgbafcheB:gdbehfcaC:abdgcefhD:gdbfheca答案:gdbfheca如下图二叉树的中序遍历序列是〔

〕。A:gdbehfcaB:abdgcefhC:dgbafcheD:abcdefgh答案:dgbafche在有n个结点的二叉链表中，值为非空的链域的个数为〔

〕。A:2n+1B:n+1C:n-1D:2n-1答案:n-1对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，那么可采用〔

〕遍历实现编号。A:后序B:无序C:中序D:从根开始的层次遍历答案:后序某二叉树的中序序列和后序序列正好相反，那么该二叉树一定是〔

〕的二叉树。A:高度等于其结点数B:任一结点无右孩子C:任一结点无左孩子D:空或只有一个结点答案:任一结点无左孩子一棵非空的二叉树的先序序列和后序序列正好相同，那么该二叉树一定满足〔

〕。A:是任意一棵二叉树B:其中任意一结点均无右孩子C:其中只有一个结点D:其中任意一结点均无左孩子答案:其中任意一结点均无右孩子一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为〔

〕。A:2B:1C:0D:不确定答案:1给定一棵二叉树的前序和后序遍历序列，可以唯一地确定出这棵二叉树形态。A:对B:错答案:错二叉树就是度为2的树。A:错B:对答案:错把一棵树转换成二叉树后，这棵二叉树形态是唯一的。A:对B:错答案:对哈夫曼编码是一种前缀码。A:错B:对答案:对第七章测试设某无向图中有n个顶点e条边，那么建立该图邻接表的时间复杂度为〔

〕。A:O(n+e)B:O(n2)C:O(ne)D:O(n3)答案:O(n+e)用邻接表存储图所用的空间大小〔

〕。A:与边数的平方有关B:只与图的顶点数与关C:只与图的边数有关D:与图的顶点和边数与关答案:与图的顶点和边数与关深度优先遍历类似于二叉树的〔

〕。A:先序遍历B:中序遍历C:后序遍历D:层次遍历答案:先序遍历用

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

〕。A:可能相同也可能不同

B:其余都不对C:是不同的D:是相同的答案:可能相同也可能不同

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

〕A:错B:对答案:错假设图G的最小生成树不唯一，那么G的边数一定多于n-1，并且权值最小的边有多条〔其中n为G的顶点数〕。A:错B:对答案:错邻接表比邻接矩阵更节省空间。A:对B:错答案:错任意一个AOV网都可以有拓扑排序。A:错B:对答案:错图的广度优先遍历算法中用到的辅助队列，每个顶点最多进队的次数不确定。A:错B:对答案:错具有n个顶点的无向完全图的边数为〔〕。A:n2B:n(n-1)C:n(n-1)/2D:n2-1答案:n(n-1)/2对含有n个顶点e条边的有向图，Floyd算法的时间复杂度为〔

〕A:O(n)B:O(ne)C:O(n3)D:

O(n2)答案:O(n3)如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，那么该图一定是〔

〕。A:有回路的图B:连通图C:一棵树D:完全图答案:连通图带权有向图G用邻接矩阵A存储，那么顶点i的入度等于A中〔

〕。A:第i列非∞且非0的元素个数B:第i行非∞的元素之和C:第i列非∞的元素之和D:第i行非∞且非0的元素个数答案:第i列非∞的元素之和以下对AOV网的描述中，错误的选项是〔

〕。A:在AOV网中可能存在多条关键路径。B:所有关键活动都提前完成，整个工程也将提前完成。C:任何一个关键活动提前完成，整个工程也将提前完成。D:关键活动不近期完成就会影响整个工程的完成时间。答案:任何一个关键活动提