大数据结构期末考试题集.docx
- 文档编号:17332824
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:75
- 大小:61.84KB
大数据结构期末考试题集.docx
《大数据结构期末考试题集.docx》由会员分享,可在线阅读,更多相关《大数据结构期末考试题集.docx(75页珍藏版)》请在冰点文库上搜索。
大数据结构期末考试题集
标准
数据结构的基本概念
选择题
(1)顺序存储结构中数据元素之间的逻辑关系是由()表示的,存储结构中的
数据元素之间的逻辑关系是由()表示的。
A.线性结构B.非线性结构C.存储位置D.指针
子女可以继承父亲假设有如下遗产继承规则:
丈夫和妻子可以相互继承遗产,
(2)
则表示该遗产继承关系的最合适的数据结构或母亲的遗产;子女间不能相互继承,。
)应该是(
B.图A.树C.线性表.集合D
。
)(3)计算机所处理的数据一般具有某种在联系,这是指(
BA.数据和数据之间存在某种关系.元素和元素之间存在某种关系C.元素部具有某种结构.数据项和数据项之间存在某种关系D
在数据结构中,与所使用的计算机无关的是数据的()(4)。
.图B.线性表.树ACD.集合
)5()在存储数据时,通常不仅要存储各数据元素的值,还要存储(。
.数据的处理方法AB.数据元素的类型
.数据元素之间的关系C.数据的存储方法D文案.
标准
(6)在存储结构中,要求()。
A.每个结点占用一片连续的存储区域B.所有结点占用一片连续的存储区域
C.结点的最后一个域是指针类型D.每个结点有多少个后继就设多少个指针
)。
(7)下列说法不正确的是(
.数据项是数据中不可分割的最小单位BA.数据元素是数据的基本单位
.数据元素可由若干个数据项构成DC.数据可由若干个数据项构成
。
(8)以下与数据的存储结构无关的术语是()
BA.循环队列.散列表C.链表.栈D
(9)以下术语属于逻辑结构的是(。
)
.哈希表B.有序表A.顺序表C.单链表D
)定义一个完整的数据结构。
10()可以用(
AC.数据对象BD.数据元素.数据关系.抽象数据类型
)11(对于数据结构的描述,下列说法中不正确的是(。
)
A.相同的逻辑结构对应的存储结构也必相同B.数据结构由逻辑结构、存储结构和基本操作三方面组成.数据结构基本操作的实现与存储结构有关C文案.
标准
D.数据的存储结构是数据的逻辑结构的机实现
(12)以下关于存储结构的叙述中,()是不正确的。
A.结点除数据信息外还包括指针域,因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不一定相邻
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算法应该具有确定性、可行性和有穷性,其中有穷性是指(
.算法在有穷的时间终止AB.输入是有穷的DC.输出是有穷的.描述步骤是有穷的
而不会产生难以理解的算法会进行适当处理,“好”当输入非法错误时,)(5一个的输出结果,这称为算法的(。
)
文案.
标准
A.可读性B.健壮性C.正确性D.有穷性
(6)算法分析的目的是(),算法分析的两个主要方面是()。
A.找出数据结构的合理性B.研究算法中输入和输出的关系
D.分析算法的易读性和文档性C.分析算法的效率以求改进FE.空间性能和时间性能.正确性和简明性
H.数据复杂性和程序复杂性G.可读性和文档性
)有关。
(7)算法的时间复杂度与(
B.计算机硬件性能A.问题规模
C.编译程序的质量D.程序设计语言
(8)算法的时间复杂度与()有关。
A.问题规模B.待处理数据的初态
D.A和B
C.算法的易读性
(9)某算法的时间复杂度是○(n),表明该算法()。
2
A.问题规模是nB.执行时间等于n22D.问题规模与n成正比C.执行时间与n成正比22
(10)下面说法错误的是()。
①算法原地工作的含义是指示不需要如何额外的辅助空间
文案.
标准
②在相同的规模n下,复杂度○(n)的算法在时间上总是优于复杂度○
(2)的算法n③所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
④同一个算法,实现语言的级别越高,执行效率就越低
(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.○(nlogn)
C.○(n)D.○(n)
232
12()算法的时间复杂度属于一种(。
)
B.事前统计的方法.事先分析估算的方法AC.事后统计的方法D.事后分析估算的方法
T(n)=100
完设(13)某算法成对n的时是间所行素个元进处理,需,则该算法的时间复杂度是(n+200n+500nlog)。
2
n+n)
C(n)
(1)B.○Dn)
(nlog.○(nlog.○.○A22
,则(n200的算法在有)个元素的数组上运行需要3.1ms假设时间复杂度为○)14(2400在有个元素的数组上运行需要(ms)。
.A3.1.C6.2B..D12.4
(无法确定)x文案.
标准
(15)下列程序段加下划线的语句执行()次。
for(m=0,i=1;i<=1;i++)
for(j=1;j<=2*i;j++)
m=m+1;
B.3nC.n(n+1)D.nA.n23
应用题
(16)将下列函数按它们的n→∞时的无穷大阶数,从小到大排列。
n,n-n-7n,nlogn,2,n,logn,n+logn,(3/2),n!
,n+logn2n/2351/23n2222
(17)分析以下程序段,并用大○记号表示其执行时间。
①i=1;k=0;
③for(i=1;i<=n;i++)
for(j=1;j<=i;j++)while(i {for(k=1;k<=j;k++) k=k+10*i;x++; ④i++; i=1;k=0; do} {i=1;j=0; ②while(i+j<=n)k=k+10*i; i++; if(i>j)j++; }while(i<=n) elsei++; 文案. 标准 ⑤y=0; ⑥for(i=0;i for(j=0;j a[i][y=y+1 j]=0; (18)有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为T=○ (2),n1A2的时间复杂度为T=○(n),仅就时间复杂度而言,请具体分析这两个算法哪一22个好。 综合应用题 (19)设n是偶数,且有程序段: for(i=1;i<=n;i++) if(2*i<=n) for(j=2*I;j<=n;j++) y=y+i*j; 则语句y=y+i*j的执行次数是多少? 要求列出计算公式。 (20)斐波那契数列F定义如下: nF=0,F=1,…,F=F+Fn=2,3,…n-2n-110n请就此斐波那契数列,回答下列问题。 精确计算多少次? F,,…,F,的时候,需要对较小的F①在递归计算FF0n-21n-1n用大○表示法给出递归计算时递归函数的时间复杂度是多少? ② 文案. 标准 (21)运算是数据结构的一个重要方面。 举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而具有不同的特性,则这两个数据结构是不同的。 (22)针对给定的实际问题建立数据结构时,应从哪些方面考虑。 文案. 标准 2线性表的逻辑结构 选择题 (1)线性表是具有n个()的有限序列。 A.数据B.字符C.数据元素D.数据项 (2)线性表是()。 .一个有限序列,不能为空BA.一个有限序列,可以为空 .一个无限序列,不能为空DC.一个无限序列,可以为空 。 关于线性表,下列说法中正确的是())(3 A.线性表中每个元素都有一个直接前驱和一个直接后继.线性表中的数据元素可以具有不同的数据类型BC.线性表中数据元素的类型是确定的D.线性表中任意一对相邻的数据元素之间存在序偶关系 )是一个线性表。 ()(4 A.由B.由所有实数组成的集合n个实数组成的集合 C.由所有整数组成的序列.由Dn个字符组成的序列 文案. 标准 3顺序线性表 选择题 (1)已知一维数组A采用顺序存储结构,每个元素占用4个存储单元,第9个元素的地址为144,则第一个元素的地址是()。 A.108B.180C.176D.112 )。 的数据元素的时间复杂度为( (2)在长度为n的线性表中查找值为x ) B.○A.○(0)(n)C (1).○D(n.○2 需向n+1)个元素之前插入一个元素,≤的线性表的第)(3在一个长度为ni(1i≤)个元)个元素,删除第后移动(i (1)个元素时,需向前移动(n≤≤i 素。 n-i+1 .Bn-i+1 n-i.n-iA.CD. )的存储结构。 4()线性表的顺序存储结构是一种( .随机存取AB.顺序存取.索引存取C.散列存取D ()5顺序存储结构的优点是()。 .存储密度大AB.插入运算方便 .删除运算方便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) 个空间,若m顺序表的插入算法中,当n个空间已满时,可再申请增加分配)(8)可分配的存储空间。 申请失败,则说明系统没有( 个连续的.Dn+m个..Am个Bm个连续的C.n+m 应用题 (9)设A是一个线性表(a,a,…,a),采用顺序存储结构,则在等概论的前n12提下,平均每插入一个元素需要移动的元素个数为多少? 若元素插在a与a之i+1i间(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)线性表的存储结构是一种()的存储结构。 A.随机存取B.顺序存取C.索引存取D.散列存取 。 (2)线性表采用存储时,其() A.地址必须是连续的B.部分地址必须是连续的.地址连续与否均可以DC.地址一定是不连续的 )。 链表不具有的特点是((3) B.插入、删除不需要移动元素A.可随机访问任一元素C.不必事先估计存储空间.所需空间与线性表长度成正比D 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是)在具有n(4。 () n1) A.○ (1)C(n)B.○D)(n.○(nlog.○22 个元素组成的线性表,建立一个单链表的时间复杂度是(对于)5n。 )( n1) B.○.○A (1)(n.○C(n).○D)(nlog22 )。 个元素组成的线性表,建立一个有序单链表的时间复杂度是(对于)(6n n1) .○C(n).○B.○A (1)D)(nlog(n.○22文案. 标准 (7)在单链表中删除指针p所指结点的后续结点,则执行()。 A.p->next=p->next->nextB.p->next=p->next DC.p=p->next->next.p=p->next; p->next=p->next->next 之p所指结点是(8)在一个单链表中,已知qp所指结点的直接前驱,若在q和s间插入所指结点,则执行()操作。 q->next=s;s->next=p;s->next=p->next;p->next=s;.BA.p->next=s;s->next=q .p->next=s->next;s->next=p;.DC 指向尾结)(9在一个长度为n上,另设有尾指针hr)的带头结点的单链表(n>1)操作与链表的长度有关。 点,执行( A.删除单链表中的第一个元素B.删除单链表中的最后一个元素.在单链表第一个元素前插入一个新元素CD.在单链表的最后一个元素后插入一个新元素 。 在单链表中附加头结点的目的是为了()(10) B.保证单链表中至少有一个结点A.标识单链表中首结点的位置.方便运算的实现CD.说明单链表是线性表的链式存储 文案. 标准 (11)将长度为n个单链表在长度为m的单链表之后的算法,其时间复杂度是()。 A.○ (1)B.○(n)C.○(m)D.○(n+m) 。 )12()循环单链表的主要优点是( .不再需要头指针了A.从表中任一结点出发都能扫描到整个链表BC.已知某个结点的位置后,能够容易找到它的直接前驱D.在进行插入、删除操作时,能更好地保证链表不断开 为链表H,(13)将线性表(aa,…,a)组织为一个带头结点的循环单链表,设n21的头指针,则链表中最后一个结点的指针域中存放的是()。 的值HA.变量的地址.变量BH.空指针.元素Ca的地址D1 的尾结点非空的循环单链表)(14Lp满足()。 p=L p->next=NULL.B.Dp->next=LC.Ap=NULL. 则两个循环单链表应各设) (1)若要在○的时间实现两个循环单链表的首尾相接,15(一个指针,分别指向()。 .各自的头结点AB.各自的尾结点CD.各自的第一个元素结点.一个表的头结点,一个表的尾结点 文案. 标准 (16)设线性表非空,()可以在○ (1)的时间在表尾插入一个新结点。 A.带头结点的单链表,有一个链表指针指向头结点 B.带头结点的循环单链表,有一个链表指针指向头结点 C.不带头结点的单链表,有一个链表指针指向表的第一个结点 D.不带头结点的循环单链表,有一个链表指针指向表中某个结点(除第一个结点外) (17)设指针rear指向带头结点的循环单链表的尾指针,若要删除链表的第一个元素结点,正确的操作是()。 A.s=rear;rear=rear->next; B.rear=rear->next; C.rear=rear->next->next; D.s=rear->next->next;rear->next->next=s->next; (18)设有两个长度为n个单链表,以h1为头指针的链表是非循环的,以h2为尾指针的链表是循环的,则()。 A.在两个链表上删除第一个结点的操作,其时间复杂度均为○ (1) B.在两个链表的表尾插入一个结点的操作,其时间复杂度均为○(n) C.循环链表要比非循环链表占用更多的存储空间 D.循环链表要比非循环链表占用更少的存储空间 (19)使用双链表存储线性表,其优点是可以()。 文案. 标准 A.提高查找速度B.更方便数据的插入和删除 D.很快回收存储空间C.节约存储空间 (20)与单链表相比,双链表的优点之一是()。 A.插入和删除操作更简单B.可以进行随机访问 D.访问其后相邻结点更灵活C.可以省略表头指针或表尾指针 (21)带头结点的循环双链表L为空表的条件是()。 A.L->next->prior=NULLB.L->prior=L D.B和C都对C.L->next=L )。 所指结点的操作是(在循环双链表的(22)p所指结点后插入s p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;.Ap->next=s;p->next->prior=s;s->prior=p;s->next=p->next;B.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;.D 所指结点,执行的语句序列是在双链表中指针papb所指结点后面插入)(23)(。 pb->prior=pa; ②①pb->next=pa->next; ④pa->next=pb;③pa->next->prior=pb; C.③④①②.①②③④AD.①④③②B.④③②① 文案. 标准 (24)在一个双链表中,删除结点p的操作是()。 A.p->prior->next=p->next;p->next->prior=p->prior; B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next; D.p->next=p->prior->prior;p->prior=p->prior->prior; 应用题 (25)单链表设置头结点的作用是什么? (26)线性表的顺序存储结构具有三个弱点: 其一,插入或删除操作需要移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。 试问,线性表的存储结构是否能够克服上述三个弱点? (27)若频繁地对一个线性表进行插入和删除操作,该线性表采用什么存储结构比较好? (28)设n表示线性表中的元素个数,P表示指针所需的存储单元大小,E表示存储数据元素所需的存储单元大小,则使用单链表存储方式存储该线性表需要多少存储空间(不考虑头结点)? 文案. 标准 算法设计题 (29)设计算法依次打印单链表中每个结点的数据信息。 (30)求单链表的长度。 (31)设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前,若找不到值为k的结点,则将x插入到链表的末尾。 (32)判断非空单链表是否递增有序。 (33)已知非空线性链表由list指出,结点结构为(data,link)。 请编写算法,将链表中数据域最小的结点移到链表的最前面。 要求: 不得额外申请新的结点。 (34)给定一个带头结点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 考试题