《数据结构习题及参考答案》由会员分享，可在线阅读，更多相关《数据结构习题及参考答案（79页珍藏版）》请在金锄头文库上搜索。
1、习题一、单选题1 数据构造是指( )。A.数据元素的组织形式.数据类型.数据存储构造 D.数据定义.数据在计算机存储器内表达时,物理地址与逻辑地址不相似的，称之为( ）。A.存储构造B逻辑构造 C.链式存储构造D.顺序存储构造3. 树形构造是数据元素之间存在一种( )。A.一对一关系B多对多关系C.多对一关系.一对多关系4. 设语句x+的时间是单位时间,则如下语句的时间复杂度为( ）。for(i=1;i=；+）fr(j=i； j=;j+)x+；.O（1)B.O()CO()DO()5.算法分析的目的是(1）,算法分析的两个重要方面是（）。（1） A.找出数据构造的合理性 B.研究算法中的输入和输
2、出关系.分析算法的效率以求改善 D.分析算法的易懂性和文档性(） .空间复杂度和时间复杂度 B.对的性和简要性C可读性和文档性 D数据复杂性和程序复杂性6. 计算机算法指的是（1)，它具有输入,输出和（2）等五个特性。(1） A.计算措施 .排序措施C.解决问题的有限运算序列 D.调度措施（2） 可行性，可移植性和可扩大性 B可行性，拟定性和有穷性C拟定性,有穷性和稳定性 D易读性，稳定性和安全性7 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上,链式存储比顺序存储要（ ）。A.低 B.高.相似D.不好说8. 数据构造作为一门独立的课程浮现是在（ ）年。A.14B.93C.9
3、64D.19689 数据构造只是研究数据的逻辑构造和物理构造，这种观点（ )。A.对的.错误C前半句对，后半句错D前半句错，后半句对10. 计算机内部数据解决的基本单位是（ )。A数据 .数据元素C.数据项.数据库二、填空题 1.数据构造按逻辑构造可分为两大类，分别是_和_。. 数据的逻辑构造有四种基本形态,分别是_、_、_和_。3. 线性构造反映结点间的逻辑关系是_的,非线性构造反映结点间的逻辑关系是_的。4. 一种算法的效率可分为_效率和_效率。5. 在树型构造中，树根结点没有_结点，其他每个结点的有且只有_个前趋驱结点;叶子结点没有_结点；其他每个结点的后续结点可以_。6. 在图型构造中
4、,每个结点的前趋结点数和后续结点数可以_。7.线性构造中元素之间存在_关系；树型构造中元素之间存在_关系；图型构造中元素之间存在_关系。8. 下面程序段的时间复杂度是_。or(i=0；in；i+）for(j;j;j+)Aj;9 下面程序段的时间复杂度是_。=s=;whil(sn) i+; si;1 下面程序段的时间复杂度是_。s=0;fo（i=;n；i+)or(j=；jn；j+)s+=B;sum=;1. 下面程序段的时间复杂度是_。i=1;hile(n)=i*3；12. 衡量算法对的性的原则一般是_。13. 算法时间复杂度的分析一般有两种措施，即_和_的措施，一般我们对算法求时间复杂度时,采用
5、后一种措施。三、求下列程序段的时间复杂度。1. x0;fo(i=1;n;+)o(j=i+；n;)x+;. x=;f(i=1;i;i+)for(j=1;j=；j) x+;3. inti,j,k；fr(i=;in;i+)for（j=0;；j+) cij=0;for（k=0;kn;+) ci=ik*b4. =n1;hile(i0)Ai!=k）)j-;etur (i);5. t(n） if(n=)ren(）; s retrn(n*fact（-1);习题1参照答案一、单选题. A 2.C . D 4 . C、A 6.C、B B 8. D 9. B 10. B二、填空题1. 线性构造,非线性构造2. 集合
6、，线性，树,图3. 一对一,一对多或多对多4. 时间,空间. 前趋,一,后继，多6.有多种7. 一对一,一对多，多对多.(）9. O(）10 O（). O（logn）1 程序对于精心设计的典型合法数据输入能得出符合规定的成果。1 事后记录，事前估计三、算法设计题() 2. （) . O(n) 4.(n) 5. O(n)习题一、单选题 1.线性表是_。.一种有限序列,可觉得空一种有限序列,不可觉得空.一种无限序列,可觉得空.一种无限序列,不可觉得空2. 在一种长度为n的顺序表中删除第i个元素(0=inxt=; rior=p; p-next-pior=s; snep-nxt;B s-prio=;
7、s-next=pnex; pnext=s; -nxt-prior=s；C.-next=; p-xt-rio=; s-prior; s-next-next;Ds-priorp; s-next=p-ex; -etpor=s; -x=; . 设单链表中指针p指向结点m,若要删除之后的结点(若存在），则需修改指针的操作为_。A.pnet=p-next-ext;Bpp-next；.=pnxt-next； D.p-nex=p； 7. 在一种长度为n的顺序表中向第i个元素(0nxt=p-xt; p-next=B.-next=s; s-nex=pC.p-ne=s-nt;next=p.pnext=s; sxt=
8、q. 如下有关线性表的说法不对的的是_。 线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中涉及的数据元素个数不是任意的。线性表中的每个结点均有且只有一种直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。0. 线性表的顺序存储构造是一种_的存储构造。 随机存取顺序存取C.索引存取D散列存取1. 在顺序表中,只要懂得_，就可在相似时间内求出任一结点的存储地址。A.基地址结点大小 C.向量大小 基地址和结点大小1 在等概率状况下，顺序表的插入操作要移动_结点。 A.所有 B一半C三分之一 D四分之一13.在_运算中,使用顺序表比链表好。 A.插入 B.删除 C
9、根据序号查找 根据元素值查找1.在一种具有个结点的有序单链表中插入一种新结点并保持该表有序的时间复杂度是_。AO(1) B.O(n) CO(2) D.O(log2n)15. 设有一种栈,元素的进栈顺序为, B,， ,E，下列是不也许的出栈序列_。A.A, B, , D，E B， C, D， E，AC., ,B， C, D E,D,C, , 1. 在一种具有n个单元的顺序栈中，假定以地址低端（即0单元)作为栈底,以作为栈顶指针，当做出栈解决时,top变化为_。t不变 Bt=0 Ctop- D.tp+1. 向一种栈顶指针为h的链栈中插入一种s结点时，应执行_。A.hs-next=; Bs-nxt=hs; h=s；Cs-net=hext;-nexs; Ds-next=s; hs=s-net； 8.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为_。ea= rot (rontl)%n= = rarrea%n -1=frn D.(rear)
