数据结构平时作业.docx
《数据结构平时作业.docx》由会员分享，可在线阅读，更多相关《数据结构平时作业.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构平时作业
1.（判断题）数据元素是数据的最小单位。
（）参考答案：
×
2.（判断题）记录是数据处理的最小单位。
（）参考答案：
×
1.（单选题）非线性结构是数据元素之间存在一种：
（）
A）一对多关系B）多对多关系C）多对一关系D）一对一关系参考答案：
B
2.（单选题）数据结构中，与所使用的计算机无关的是数据的结构；（）
A）存储B）物理C）逻辑D）物理和存储参考答案：
C
3.（判断题）数据的逻辑结构是指数据的各数据项之间的逻辑关系。
（）参考答案：
×
4.（判断题）数据的物理结构是指数据在计算机内的实际存储形式。
（）参考答案：
√
5.（判断题）在顺序存储结构中，有时也存储数据结构中元素之间的关系。
（）参考答案：
×
1.（判断题）数据结构的抽象操作的定义与具体实现有关。
（）参考答案：
×
1.（单选题）算法分析的目的是：
（）
A）找出数据结构的合理性B）研究算法中的输入和输出的关系
C）分析算法的效率以求改进D）分析算法的易懂性和文档性参考答案：
C
2.（单选题）算法分析的两个主要方面是：
（）
A）空间复杂性和时间复杂性B）正确性和简明性
C）可读性和文档性D）数据复杂性和程序复杂性参考答案：
A
3.（单选题）计算机算法指的是：
（）
A）计算方法B）排序方法C）解决问题的有限运算序列D）调度方法参考答案：
C
4.（判断题）算法的优劣与算法描述语言无关，但与所用计算机有关。
（）参考答案：
×
5.（判断题）健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
（）参考答案：
√
6.（判断题）算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。
（）参考答案：
×
7.（判断题）程序一定是算法。
（）参考答案：
×
1.（单选题）下述哪一条是顺序存储结构的优点？
（）
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示参考答案：
A
2.（单选题）下面关于线性表的叙述中，错误的是哪一个？
（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
参考答案：
B
3.（单选题）线性表是具有n个（）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项E．信息项参考答案：
C
4.（单选题）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表参考答案：
A
5.（单选题）某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表参考答案：
D
6.（单选题）设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。
A．单链表B．单循环链表C．带尾指针的单循环链表D．带头结点的双循环链表参考答案：
D
7.（单选题）若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表参考答案：
D
8.（单选题）静态链表中指针表示的是（）
A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址参考答案：
C
9.（单选题）链表不具有的特点是（）
A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比参考答案：
B
10.（单选题）
（1）静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第i个元素的时间与i无关。
（2）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（）
A．
（1），
（2）B．
（1）C．
（1），
（2）,（3）D．
（2）参考答案：
B
11.（单选题）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1<=i<=n+1）。
A．O（0）B．O
（1）C．O（n）D．O（n2）参考答案：
C
12.（单选题）对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O（n）O（n）B．O（n）O
（1）C．O
（1）O（n）D．O
（1）O
（1）参考答案：
C
13.（单选题）线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）
A．O（i）B．O
（1）C．O（n）D．O（i-1）参考答案：
C
14.（单选题）非空的循环单链表head的尾结点p↑满足（）。
A．p↑．link=headB．p↑．link=NILC．p=NILD．p=head参考答案：
A
15.（多选题）下面的叙述不正确的是（）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B．线性表在链式存储时，查找第i个元素的时间同i的值无关
C．线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D．线性表在顺序存储时，查找第i个元素的时间同i的值无关参考答案：
BC
16.（判断题）链表中的头结点仅起到标识的作用。
（）参考答案：
×
17.（判断题）顺序存储结构的主要缺点是不利于插入或删除操作。
（）参考答案：
√
18.（判断题）线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
（）参考答案：
√
19.（判断题）顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
（）参考答案：
×
20.（判断题）对任何数据结构链式存储结构一定优于顺序存储结构。
（）参考答案：
×
21.（判断题）顺序存储方式只能用于存储线性结构。
（）参考答案：
×
22.（判断题）集合与线性表的区别在于是否按关键字排序。
（）参考答案：
×
23.（判断题）所谓静态链表就是一直不发生变化的链表。
（）参考答案：
×
24.（判断题）线性表的特点是每个元素都有一个前驱和一个后继。
（）参考答案：
×
25.（判断题）取线性表的第i个元素的时间同i的大小有关。
（）参考答案：
×
1.（单选题）栈中元素的进出原则是（）
Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出参考答案：
B
2.（单选题）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）Ａ．iＢ．n=iＣ．n-i+1Ｄ．不确定参考答案：
C
3.（单选题）判定一个栈ST（最多元素为m0）为空的条件是（）
Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0参考答案：
B
4.（单选题）判定一个队列QU（最多元素为m0）为满队列的条件是（）
Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0
Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1参考答案：
A
5.（单选题）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（）
（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n参考答案：
D
6.（判断题）消除递归不一定需要使用栈，此说法。
（）参考答案：
√
7.（判断题）栈是实现过程和函数等子程序所必需的结构。
（）参考答案：
√
8.（判断题）两个栈共用静态存储空间，对头使用也存在空间溢出问题。
（）参考答案：
√
9.（判断题）两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（）参考答案：
√
10.（判断题）即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。
（）参考答案：
×
11.（判断题）有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）]*（2n）!
/[（n!
）*（n!
）]。
参考答案：
√
12.（判断题）栈与队列是一种特殊操作的线性表。
（）参考答案：
√
13.（判断题）若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。
（）参考答案：
√
14.（判断题）栈和队列都是限制存取点的线性结构。
（）参考答案：
√
15.（判断题）若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。
参考答案：
×
16.（判断题）任何一个递归过程都可以转换成非递归过程。
（）参考答案：
√
17.（判断题）只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
（）参考答案：
×
18.（判断题）队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
参考答案：
×
19.（判断题）通常使用队列来处理函数或过程的调用。
（）参考答案：
×
20.（判断题）队列逻辑上是一个下端和上端既能增加又能减少的线性表。
（）参考答案：
√
1.（单选题）下面关于串的的叙述中，哪一个是不正确的？
（）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储参考答案：
B
2.（单选题）若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat（replace（S1,substr（S1,length（S2）,length（S3））,S3）,substr（S4,index（S2,‘8’）,length（S2）））其结果为（）。
A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345
E．ABC###G1234F．ABCD###1234G．ABC###01234参考答案：
E
3.（单选题）设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。
A．求子串B．联接C．匹配D．求串长参考答案：
C
4.（单选题）已知串S=‘aaab’,其Next数组值为（）。
A．0123B．1123C．1231D．1211参考答案：
A
5.（单选题）串‘ababaaababaa’的next数组为（）。
A．012345678999B．012121111212C．011234223456D．0123012322345参考答案：
C
6.（判断题）KMP算法的特点是在模式匹配时指示主串的指针不会变小。
（）参考答案：
√
7.（判断题）设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
（）参考答案：
√
8.（判断题）串是一种数据对象和操作都特殊的线性表。
（）参考答案：
√
1.（单选题）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C．18D．40参考答案：
B
2.（单选题）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225参考答案：
B
3.（单选题）假设以行序为主序存储二维数组A=array[1．．100，1．．100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A．808B．818C．1010D．1020参考答案：
B
4.（单选题）数组A[0．．5,0．．6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。
A．1175B．1180C．1205D．1210参考答案：
A
5.（单选题）将一个A[1．．100，1．．100]的三对角矩阵，按行优先存入一维数组B[1？
298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
供选择的答案：
A．198B．195C．197参考答案：
B
6.（单选题）二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。
若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。
设每个字符占一个字节。
A．A[8,5]B．A[3,10]C．A[5,8]D．A[0,9]参考答案：
B
7.（单选题）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B［1．．（n（n+1））/2］中，则在B中确定aij（iA．i*（i-1）/2+jB．j*（j-1）/2+iC．i*（i+1）/2+jD．j*（j+1）/2+i参考答案：
B
8.（单选题）设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1．．n（n+1）/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（）。
A．i（i-l）/2+jB．j（j-l）/2+iC．j（j-l）/2+i-1D．i（i-l）/2+j-1参考答案：
B
9.（单选题）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A．i（i-1）/2+jB．j（j-1）/2+iC．i（j-i）/2+1D．j（i-1）/2+1参考答案：
B
10.（单选题）设二维数组A[1．．m，1．．n]（即m行n列）按行存储在数组B[1．．m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（）。
A．（i-1）*n+jB．（i-1）*n+j-1C．i*（j-1）D．j*m+i-1参考答案：
A
11.（单选题）有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A．60B．66C．18000D．33参考答案：
B
12.（单选题）数组A[0．．4,-1．．-3,5．．7]中含有元素的个数（）。
A．55B．45C．36D．16参考答案：
B
13.（判断题）数组不适合作为任何二叉树的存储结构。
（）参考答案：
×
14.（判断题）从逻辑结构上看，n维数组的每个元素均属于n个向量。
（）参考答案：
√
15.（判断题）稀疏矩阵压缩存储后，必会失去随机存取功能。
（）参考答案：
√
16.（判断题）数组是同类型值的集合。
（）参考答案：
×
17.（判断题）数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作参考答案：
×
18.（判断题）一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
（）参考答案：
×
19.（判断题）二维以上的数组其实是一种特殊的广义表。
（）参考答案：
√
20.（判断题）广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
（）参考答案：
×
21.（判断题）若一个广义表的表头为空表，则此广义表亦为空表。
（）参考答案：
×
22.（判断题）广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
（）参考答案：
×
23.（单选题）有一个二维数组A[1:
6，0:
7]每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。
假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。
若按行存储，则A[2，4]的第一个字节的地址是（③）。
若按列存储，则A[5，7]的第一个字节的地址是（④）。
就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。
供选择的答案：
①-④:
A．12B．66C．72D．96E．114F．120G．156
H．234I．276J．282K．283L．288
⑤：
A．行与列的上界相同B．行与列的下界相同C．行与列的上、下界都相同D．行的元素个数与列的元素个数相同
因此本题选择（）A:
L;J;C;I;CB:
C;I;C;J;LC:
L;J;C;I;B参考答案：
A
24.（单选题）有一个二维数组A[0:
8,1:
5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（①）。
若按行存储，则A[3,5]和A[5,3]的第一个字节的地址是（②）和（③）。
若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。
①-⑤:
A．28B．44C．76D．92E．108F．116G．132H．176I．184J．188
因此本题选择（）
A:
H;C;E;A;FB:
H;C;B;A;FC:
F;C;E;A;B参考答案：
A
25.（单选题）二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。
从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。
（1）存放A至少需要（）个字节；
（2）A的第8列和第5行共占（）个字节；
（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。
供选择的答案：
（1）A．90B．180C．240D．270E．540
（2）A．108B．114C．54D．60E．150
（3）A．A[8,5]B．A[3,10]C．A[5,8]D．A[0,9]
因此本题选择A:
E;A;BB:
A;B;EC:
E;A;参考答案：
A
1.（单选题）不含任何结点的空树。
（Ａ）是一棵树;（Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树;（Ｄ）既不是树也不是二叉树参考答案：
C
2.（单选题）二叉树是非线性数据结构，所以。
（Ａ）它不能用顺序存储结构存储;（Ｂ）它不能用链式存储结构存储;
（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用
参考答案：
C
3.（单选题）具有n（n>0）个结点的完全二叉树的深度为。
（Ａ）élog2（n）ù（Ｂ）ëlog2（n）û（Ｃ）ëlog2（n）û+1（Ｄ）élog2（n）+1ù
参考答案：
C
4.（单选题）把一棵树转换为二叉树后，这棵二叉树的形态是参考答案：
A。
（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子
5.（判断题）二叉树是度为2的有序树。
（）参考答案：
×
6.（判断题）完全二叉树一定存在度为1的结点。
（）参考答案：
×
7.（判断题）对于有N个结点的二叉树，其高度为log2n。
（）参考答案：
×
8.（判断题）深度为K的二叉树中结点总数≤2k-1。
（）参考答案：
√
9.（判断题）二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立）。
（）参考答案：
√
10.（判断题）二叉树的遍历结果不是唯一的。
（）参考答案：
√
12.（判断题）树可用投影法进行中序遍历。
（）参考答案：
×
13.（判断题）一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
（）参考答案：
√
14.（判断题）二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。
（）参考答案：
×
15.（判断题）一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。
（）参考答案：
×
16.（判断题）对一棵二叉树进行层次遍历时，应借助于一个栈。
（）参考答案：
×
17.（判断题）用树的前序遍历和中序遍历可以导出树的后序遍历。
（）参考答案：
×
18.（判断题）采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的参考答案：
√
19.（判断题）用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
（）参考答案：
×
20.（单选题）树是结点的有限集合，它A根结点，记为T。
其余的结点分成为m（m≥0）个B
的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
一个结点的子结点个数为该结点的C。
供选择的答案
A：
①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上
B:
①互不相交②允许相交③允许叶结点相交④允许树枝结点相交
C：
①权②维数③次数（或度）④序
因此本题选择（）
A:
1，1，1B:
1，1，3C:
2，1，1参考答案：
B
1.（单选题）在一个图中，所有顶点的度数之和等于图的边数的倍。
A．1/2B.1C.2D.4参考答案：
C
2.（单选题）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A．1/2B.1C.2D.4参考答案：
B
3.（单选题）有8个结点的无向图最多有条边。
A．14B.28C.56D.112参考答案：
B
4.（单选
升级会员 