大数据结构期末考试题集Word下载.docx
《大数据结构期末考试题集Word下载.docx》由会员分享，可在线阅读，更多相关《大数据结构期末考试题集Word下载.docx（37页珍藏版）》请在冰点文库上搜索。
C．可以通过计算得到第i个结点的存储地址
D．插入和删除操作方便，不必移动结点
（13）可以用（）、数据关系和基本操作定义一个完整的抽象数据类型。
A．数据元素B．数据对象C．原子类型D．存储结构
应用题
（14）设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}。
试画出其逻辑结构图并指出属于何种结构。
（15）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
（16）说明数据的逻辑结构和存储结构之间的关系。
（17）抽象数据类型的主要特点是什么？
数据类型和抽象数据类型的关系如何？
使用抽象数据类型的主要好处是什么？
1
算法和算法分析
（1）算法指的是（）。
A．对特定问题求解步骤的一种描述，是指令的有限序列
B．计算机程序
C．解决问题的计算方法
D．数据处理
（2）下面（）不是算法所必须具备的特性。
A．有穷性B．确切性C．高效性D．可行性
（3）算法必须具备输入、输出和（）等特性。
A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性
C．确定性、稳定性和有穷性D．易读性、稳定性和健壮性
（4）算法应该具有确定性、可行性和有穷性，其中有穷性是指（）。
A．算法在有穷的时间终止B．输入是有穷的
C．输出是有穷的D．描述步骤是有穷的
（5）当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的（）。
A．可读性B．健壮性C．正确性D．有穷性
（6）算法分析的目的是（），算法分析的两个主要方面是（）。
A．找出数据结构的合理性B．研究算法中输入和输出的关系
C．分析算法的效率以求改进D．分析算法的易读性和文档性
E．空间性能和时间性能F．正确性和简明性
G．可读性和文档性H．数据复杂性和程序复杂性
（7）算法的时间复杂度与（）有关。
A．问题规模B．计算机硬件性能
C．编译程序的质量D．程序设计语言
（8）算法的时间复杂度与（）有关。
A．问题规模B．待处理数据的初态
C．算法的易读性D．A和B
（9）某算法的时间复杂度是○（n2），表明该算法（）。
A．问题规模是n2B．执行时间等于n2
C．执行时间与n2成正比D．问题规模与n2成正比
（10）下面说法错误的是（）。
①算法原地工作的含义是指示不需要如何额外的辅助空间
②在相同的规模n下，复杂度○（n）的算法在时间上总是优于复杂度○（2n）的算法
③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
④同一个算法，实现语言的级别越高，执行效率就越低
（11）算法
for（i=n-1;
i>
=1;
i--）
for（j=1;
j<
=i;
j++）
if（a[j]>
a[j+1]）a[j]与a[j+1]交换；
其中n为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（）。
A．○（n）B．○（nlog2n）C．○（n3）D．○（n2）
（12）算法的时间复杂度属于一种（）。
A．事前统计的方法B．事先分析估算的方法
C．事后统计的方法D．事后分析估算的方法
（13）设某算法完成对n个元素进行处理，所需的时间是T（n）=100nlog2n+200n+500，则该算法的时间复杂度是（）。
A．○
（1）B．○（n）C．○（nlog2n）D．○（nlog2n+n）
（14）假设时间复杂度为○（n2）的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（）ms。
A．3.1B．6.2C．12.4D．x（无法确定）
（15）下列程序段加下划线的语句执行（）次。
for（m=0,i=1;
i<
i++）
=2*i;
m=m+1；
A．n2B．3nC．n（n+1）D．n3
（16）将下列函数按它们的n→∞时的无穷大阶数，从小到大排列。
n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，（3/2）n，n!
，n2+log2n
（17）分析以下程序段，并用大○记号表示其执行时间。
1i=1;
k=0;
while（i<
n-1）
{
k=k+10*i;
i++;
}
2i=1;
j=0;
while（i+j<
=n）
if（i>
j）j++;
elsei++;
3for（i=1;
i<
=n;
i++）
for（j=1;
j<
j++）
for（k=1;
k<
=j;
k++）
x++;
4i=1;
do
}while（i<
5y=0;
while（（y+1）*（y+1）<
y=y+1
6for（i=0;
n;
for（j=0;
m;
a[i][j]=0;
（18）有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=○（2n），A2的时间复杂度为T2=○（n2），仅就时间复杂度而言，请具体分析这两个算法哪一个好。
综合应用题
（19）设n是偶数，且有程序段：
for（i=1;
if（2*i<
for（j=2*I;
y=y+i*j;
则语句y=y+i*j的执行次数是多少？
要求列出计算公式。
（20）斐波那契数列Fn定义如下：
F0=0，F1=1，…，Fn=Fn-1+Fn-2n=2，3，…
请就此斐波那契数列，回答下列问题。
①在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…，F1，F0精确计算多少次？
2用大○表示法给出递归计算时递归函数的时间复杂度是多少？
（21）运算是数据结构的一个重要方面。
举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。
（22）针对给定的实际问题建立数据结构时，应从哪些方面考虑。
2
线性表的逻辑结构
（1）线性表是具有n个（）的有限序列。
A．数据B．字符C．数据元素D．数据项
（2）线性表是（）。
A．一个有限序列，可以为空B．一个有限序列，不能为空
C．一个无限序列，可以为空D．一个无限序列，不能为空
（3）关于线性表，下列说法中正确的是（）。
A．线性表中每个元素都有一个直接前驱和一个直接后继
B．线性表中的数据元素可以具有不同的数据类型
C．线性表中数据元素的类型是确定的
D．线性表中任意一对相邻的数据元素之间存在序偶关系
（4）（）是一个线性表。
A．由n个实数组成的集合B．由所有实数组成的集合
C．由所有整数组成的序列D．由n个字符组成的序列
3
顺序线性表
（1）已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。
A．108B．180C．176D．112
（2）在长度为n的线性表中查找值为x的数据元素的时间复杂度为（）。
A．○（0）B．○
（1）C．○（n）D．○（n2）
（3）在一个长度为n的线性表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。
A．n-iB．n-i+1C．n-iD．n-i+1
（4）线性表的顺序存储结构是一种（）的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
（5）顺序存储结构的优点是（）。
A．存储密度大B．插入运算方便
C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
（6）n个结点的线性表采用数组实现，算法的时间复杂度是○
（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．以上都不对
（7）对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为（）。
A．○（n）、○（n）B．○（n）、○
（1）C．○
（1）、○（n）D．○
（1）、○
（1）
（8）顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配的存储空间。
A．m个B．m个连续的C．n+m个D．n+m个连续的
（9）设A是一个线性表（a1，a2，…，an），采用顺序存储结构，则在等概论的前提下，平均每插入一个元素需要移动的元素个数为多少？
若元素插在ai与ai+1之间（1≤i≤n）的概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动的元素个数是多少？
（10）设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小，D表示可以在数组中存储线性表的最大元素个数（D≥n），则使用顺序存储方式存储线性表需要多少存储空间？
（11）在什么情况下线性表使用顺序存储比较好？
算法设计题
（12）试以顺序表作存储结构，实现线性表就地逆置。
（13）设计算法判断给定字符串是否是回文。
所谓回文是正读和反读均相同的字符串，例如abcba或abba是回文，而abcda不是回文。
（14）设计一个时间复杂度为○（n）的算法，实现将数组A[n]中所有元素循环左移k个位置。
（15）已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为○（n）。
（16）假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。
（17）顺序存储的线性表A，其数据元素为整型，设计算法将A拆成B和C两个表，使A中值大于0的元素存入表B，值小于0的元素存入表C，要求B和C不另外设置存储空间而利用A的空间。
（18）已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。
（19）设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度为○
（1）。
（20）设计算法实现从顺序表L中删除所有值在x和y之间的所有元素，要求时间性能复杂度为○（n），空间性能为○
（1）。
（21）设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少并使剩余元素间的相对次序保持不变。
（22）给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[n+m]中，试写出这一算法（假设A、B和C均为升序序列）。
4
线性链表
（1）线性表的存储结构是一种（）的存储结构。
（2）线性表采用存储时，其（）。
A．地址必须是连续的B．部分地址必须是连续的
C．地址一定是不连续的D．地址连续与否均可以
（3）链表不具有的特点是（）。
A．可随机访问任一元素B．插入、删除不需要移动元素
C．不必事先估计存储空间D．所需空间与线性表长度成正比
（4）在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。
A．○
（1）B．○（n）C．○（n2）D．○（nlog2n1）
（5）对于n个元素组成的线性表，建立一个单链表的时间复杂度是（）。
（6）对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。
（7）在单链表中删除指针p所指结点的后续结点，则执行（）。
A．p->
next=p->
next->
nextB．p->
next
C．p=p->
nextD．p=p->
next;
p->
（8）在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。
A．s->
next=s;
B．q->
s->
next=p;
C．p->
next=s->
D．p->
next=q
（9）在一个长度为n（n>
1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（）操作与链表的长度有关。
A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表的最后一个元素后插入一个新元素
（10）在单链表中附加头结点的目的是为了（）。
A．保证单链表中至少有一个结点B．标识单链表中首结点的位置
C．方便运算的实现D．说明单链表是线性表的链式存储
（11）将长度为n个单链表在长度为m的单链表之后的算法，其时间复杂度是（）。
A．○
（1）B．○（n）C．○（m）D．○（n+m）
（12）循环单链表的主要优点是（）。
A．不再需要头指针了
B．从表中任一结点出发都能扫描到整个链表
C．已知某个结点的位置后，能够容易找到它的直接前驱
D．在进行插入、删除操作时，能更好地保证链表不断开
（13）将线性表（a1，a2，…，an）组织为一个带头结点的循环单链表，设H为链表的头指针，则链表中最后一个结点的指针域中存放的是（）。
A．变量H的地址B．变量H的值
C．元素a1的地址D．空指针
（14）非空的循环单链表L的尾结点p满足（）。
A．p=NULLB．p->
next=NULLC．p->
next=LD．p=L
（15）若要在○
（1）的时间实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向（）。
A．各自的头结点B．各自的尾结点
C．各自的第一个元素结点D．一个表的头结点，一个表的尾结点
（16）设线性表非空，（）可以在○
（1）的时间在表尾插入一个新结点。
A．带头结点的单链表，有一个链表指针指向头结点
B．带头结点的循环单链表，有一个链表指针指向头结点
C．不带头结点的单链表，有一个链表指针指向表的第一个结点
D．不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）
（17）设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元素结点，正确的操作是（）。
A．s=rear;
rear=rear->
B．rear=rear->
C．rear=rear->
D．s=rear->
rear->
（18）设有两个长度为n个单链表，以h1为头指针的链表是非循环的，以h2为尾指针的链表是循环的，则（）。
A．在两个链表上删除第一个结点的操作，其时间复杂度均为○
（1）
B．在两个链表的表尾插入一个结点的操作，其时间复杂度均为○（n）
C．循环链表要比非循环链表占用更多的存储空间
D．循环链表要比非循环链表占用更少的存储空间
（19）使用双链表存储线性表，其优点是可以（）。
A．提高查找速度B．更方便数据的插入和删除
C．节约存储空间D．很快回收存储空间
（20）与单链表相比，双链表的优点之一是（）。
A．插入和删除操作更简单B．可以进行随机访问
C．可以省略表头指针或表尾指针D．访问其后相邻结点更灵活
（21）带头结点的循环双链表L为空表的条件是（）。
A．L->
prior=NULLB．L->
prior=L
C．L->
next=LD．B和C都对
（22）在循环双链表的p所指结点后插入s所指结点的操作是（）。
prior=p;
prior=s;
B．p->
C．s->
D．s->
（23）在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（）。
①pb->
next=pa->
②pb->
prior=pa;
③pa->
next=pb;
④pa->
prior=pb;
A．①②③④B．④③②①C．③④①②D．①④③②
（24）在一个双链表中，删除结点p的操作是（）。
prior->
prior=p->
prior;
D．p->
（25）单链表设置头结点的作用是什么？
（26）线性表的顺序存储结构具有三个弱点：
其一，插入或删除操作需要移动大量元素；
其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；
其三，表的容量难以扩充。
试问，线性表的存储结构是否能够克服上述三个弱点？
（27）若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？
（28）设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？
（29）设计算法依次打印单链表中每个结点的数据信息。
（30）求单链表的长度。
（31）设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，若找不到值为k的结点，则将x插入到链表的末尾。
（32）判断非空单链表是否递增有序。
（33）已知非空线性链表由list指出，结点结构为（data，link）。
请编写算法，将链表中数据域最小的结点移到链表的最前面。
要求：
不得额外申请新的结点。
（34）给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：
不允许使用数组作辅助空间）。
（35）已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。
（36）设计算法实现将单链表就地逆置。
（37）头插法建立单链表。
（38）尾插法建立单链表
（39）复制一个单链表。
（40）设计算法实现将单链表就地逆置。
（41）在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。
（42）设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。
（43）已知单链表中各结点的元素值为整型且递增有序，设计算法删除表于mink且小于maxk的所有元素，并释放被删结点的存储空间。
（44）有两个整数序列A=（a1，a2，…，am）和B=（b1，b2，…，bn）已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列。
（45）设线性表C=（a1，b1，a2，b2，…，an，bn）采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和B，使得A=（a1，a2，…，an），B=（b1，b2，…，bn）。
（46）有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序链表。
（47）有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。
（48）已知单链表A和B的数据（设为整型）递增有序，设计算法利用原有结点，将表A中与表B具有相同值的结点删
升级会员 