号_______________ 姓名_______________ 专业_______________ 班级_______________
………………………………装…………………………订…………………………线………………………………………………………………答………………题………………不………………要………………过………………此……………………………试卷(A 卷)
2010– 2011学年度第 一 期
考试班级 09级计应 完卷时间 100分钟 考试科目 《数据结构》 命 题 人 杨 华 使用教材 教研室主任签字
系教学副主任签字_____ _____
《数据结构》期末考试试卷(A 卷)
第I卷 选择题(共30分)
一、选择题(本大题共15小题,每小题2分,共30分。在每小题给出的四个选项中,只有一个是正确的,选对得2分,选错或不选得0分)。
1、在数据结构中,与所使用的计算机无关的是数据的( )结构。
A 、 逻辑
B 、 存贮
C 、 逻辑与存贮
D 、 物理 2、下列算法的时间复杂度的量级为( )。
for( int i=0; i A 、 O (m 3) B 、 O (n 2) C 、 O (m*n ) D 、 O (m+n ) 3、线性表是( )。 A 、一个有限序列,可以为空; B 、一个有限序列,不能为空; C 、一个无限序列,可以为空; D 、一个无限序列,不能为空; 4、上溢现象通常出现在( ) A 、顺序栈的入栈操作过程中 B 、顺序栈的出栈操作过程中 C 、链栈的入栈操作过程中 D 、链栈的出栈操作过程中 5、队和栈的主要区别是( ) A 、逻辑结构不同 B 、存储结构不同 C 、所包含的运算个数不同 D 、限定插入和删除的位置不同 6、一个栈的入栈序列是a ,b ,c ,d ,e ,则不可能的出栈序列是( )。 A 、 edcba B 、dceab C 、 decba D 、 abcde 号_______________ 姓名_______________ 专业_______________ 班级_______________ ………………………………装…………………………订…………………………线………………………………………………………………答………………题………………不………………要………………过………………此……………………………7、设有两个串P 和Q ,求P 在Q 中首次出现的位置的运算称为( )。 A 、 连接运算 B 、 模式匹配运算 C 、 求子串 D 、 求串长 8、王先生有一对双胞胎儿女,他和他双胞胎儿女的关系属于( )。 A 、 集合结构 B 、线形结构 C 、树型结构 D 、图形结构 9、下面关于算法说法错误的是( )。 A 、算法最终必须由计算机程序实现 B 、为解决某问题的算法同为该问题编写的程序含义是相同的 C 、 算法的可行性是指指令不能有二义性 D 、以上几个都是错误的 10、在一个单链表中,若q 所指结点是p 所指结点的前驱结点,若在q 与p 之间插入一个s 所指结点,则执行( )。 A 、 s →next=p →next ;p →next=s ; B 、p →next=s ;s →next=q ; C 、p →next= s →next ;s →next=p ; D 、q →next=s ;s →next=p ; 11、下列表述中,( )不是算法的基本特征。 A 、正确性 B 、长度有限 C 、在规定的时间完成 D 、确定性 12、在初始为空的栈S 中依次插入元素fedcba 后,连续进行了三次POP (S )操作,此时求top (S )=( )。 A 、 c B 、d C 、b D 、e 13、串是一种特殊的线性表,其特殊性体现在( )。 A 、唯一可以顺序存贮 B 、数据元素是一个字符 C 、可以链接存贮 D 、数据元素可以是多个字符 14、循环队列S 为满的条件是( )。 A 、S → rear== S →front B 、(S → rear+1)%maxsize== S →front C 、S → rear==0 D 、S →front==0 15、设单链表中指针p 所指结点a ,若要删除p 之后的结点(若存在),则需要进行的操作为( )。 A 、p → next= p → next →next B 、p= p → next C 、p= p → next →next D 、next =p 号_______________ 姓名_______________ 专业_______________ 班级_______________ ………………………………装…………………………订…………………………线………………………………………………………………答………………题………………不………………要………………过………………此…………………………… 南充职业技术学院2010-2011第一期期末考试 数 据 结 构 答 题 卷 (考试时间100分钟,满分100分) 第I卷 选择题(共30分) 一、选择题(本大题共15小题,每小题2分,共30分。在每小题给出的四个选项中,只有一个是正确的,选对得2分,选错或不选得0分)。 第Ⅱ卷 非选择题(共70分) 注意事项: 1.考生要将第II 卷的答案用钢笔或圆珠笔答在答题卷指定的位置上。 2.答题前应将答卷上密封线内的项目填写清楚。 二、简答题(共5小题,每题8分,共40分) 16、什么叫算法,它有哪些特征。 答:算法是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。 17、在链表的设计中,为什么通常采用带头结点的链表结构? 答:头指针是链表的一个标识,它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点,它的作用是使对第一个结点的操作和其它结点一致,表空与非空时处理一致,不需要特殊处理,简化了操作。 18、在顺序队列中,什么叫溢出?什么叫假溢出?如何避免假溢出产生? 答:当front 0,rear=M 时,再有元素入队发生溢出,称之为 “假溢出”,存储空间还有剩余。为了改进这种状况,可以将顺序队列想象为一个首尾相接的环状空间,称之为循环队列。 19、字符串连接运算concat (S1,S2)一般不满足交换律运算,但当S1,S2满足一定条 件的时候,concat (S1,S2)= concat (S2,S1)可以成立;请写出使得concat (S1,S2)= concat (S2,S1)成立的条件,并举例说明。 1、s1和s2为空串; 2、s1和s2之一为空串; 3、s1和s2为相同的串; 4、若两串长度不等,则长串s1由整数个s2短串组成 号_______________ 姓名_______________ 专业_______________ 班级_______________ ………………………………装…………………………订…………………………线………………………………………………………………答………………题………………不………………要………………过………………此……………………………20、在如图1所示的链表中,若在指针p 所指的结点之后插入数据域值相继为a 和b 的两 个结点,请写出实现该操作的语句。 P →next=s s →next=p →next →next 三、计算、程序分析和画图题(3小题,每题10分,共30分) 21、设有一个顺序栈S ,元素s1, s2, s3, s4, s5, s6依次进栈,如果6个元素的出 栈顺序为s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为多大?(要求写出栈的状态变化过程) 容量为3 22、算法分析(10分) void conversion( ) { setnull( s ); scanf (“%d”, n); while(n) { push(s , n%8); n=n / 8; } while(! empty(s)) { pop(s , e); printf(“%d”, e); } } 分析上面的算法,当我们输入n=100时,其结果是___144__________。 23、请画出下列二元组表示的数据结构对应的逻辑结构图,并指出它属于何种结构。 三元组:A=(K ,R ),其中: K={a ,b ,c ,d ,e ,f ,g ,h};R={ r } r={,, 它是一种线性结构 图1 一、判断题: 1、力矩分配法中的分配系数、传递系数与外来因素(荷载、温度变化等)有关。( ) 2、若图示各杆件线刚度i 相同,则各杆A 端的转动刚度S 分别为:4 i , 3 i , i 。(√ ) A A A 3、图示结构EI =常数,用力矩分配法计算时分配系数4 A μ= 4 / 11。( ) 1 2 3 4 A l l l l 4、图示结构用力矩分配法计算时分配系数μAB =12/,μAD =18/。(√ ) B C A D E =1i =1 i =1i =1 i 5、用力矩分配法计算图示结构,各杆l 相同,EI =常数。其分配系数μBA =0.8,μBC =0.2, μBD =0。(√ ) A B C D 6、单元刚度矩阵反映了该单元杆端位移与杆端力之间的关系。(√ ) 7、单元刚度矩阵均具有对称性和奇异性。( X ) 8、局部坐标系与整体坐标系之间的坐标变换矩阵T 是正交矩阵。(√ ) 9、结构刚度方程矩阵形式为:[]{}{}K P ?=,它是整个结构所应满足的变形条件。( X ) 10、矩阵位移法中,等效结点荷载的“等效原则”是指与非结点荷载的结点位移相等。(√ ) 二.选择题 (1)欲使图2-1所示体系的自振频率增大,在下述办法中可采用:( D ) A.增大质量 m; B.将质量 m 移至梁的跨中位置;C.减小梁的 EI; D.将铰支座改为固定支座。 图2-1 (2)平面杆件结构一般情况下的单元刚度矩阵[]66? k,就其性质而言,是:( B ) A.非对称、奇异矩阵; B.对称、奇异矩阵; C.对称、非奇异矩阵; D.非对称、非奇异矩阵。 (3)已知图2-3所示刚架各杆 EI = 常数,当只考虑弯曲变形,且各杆单元类型相同时,采用先处理法进行结点位移编号,其正确编号是:(A ) 图2-3 一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度()。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的()。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为()。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。 一、判断题(共223小题) 1。结构的类型若按几何特征可分为平面结构和空间结构。(A) 2、狭义结构力学的研究对象是板、壳结构(B)。 3 单铰相当于两个约束。(A) 4、单刚节点相当于三个约束。(A) 5、静定结构可由静力平衡方程确定全部约束力和内力。A 6、超静定结构可由静力平衡方程确定全部约束力和内力B。 7 无多余约束的几何不变体系是静定结构。A 8 三刚片规则中三铰共线为可变体系。B 9 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为静定结构。A 10 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为超静定结构B。 11链杆相当于两个约束。B 12 平面上的自由点的自由度为2 A 13 平面上的自由刚体的自由度为3 A 14 铰结点的特征是所联结各杆可以绕结点中心自由转动。A 15 有多余约束的几何不变体系是超静定结构。A 16 无多余约束的几何可变体系是超静定结构。B 17、无多余约束的几何可变体系是静定结构。B 18刚结点的特征是当结构发生变形时汇交于该点的各杆端间相对转角为零。A 19 三刚片规则中三铰共线为瞬变体系。A 20三个本身无多余约束的刚片用三个不共线的单铰两两相连,则组成的体系为静定结构。A 21 一个刚结点相当于3个约束。 22 一个连接3个刚片的复铰相当于2个单铰。A 23 一个铰结三角形可以作为一个刚片。A 24 一个铰结平行四边形可以作为一个刚片。B 25 一根曲杆可以作为一个刚片。A 26 一个连接4个刚片的复铰相当于2个单铰.B 27 任意体系加上或减去二元体,改变体系原有几何组成性质。B 28 平面几何不变体系的计算自由度一定等于零。B 29 平面几何可变体系的计算自由度一定等于零。B 30 三刚片体系中若有1对平行链杆,其他2铰的连线与该对链杆不平行,则该体系为几何不变体系。A 31 三刚片体系中,若有三对平行链杆,那么该体系仍有可能是几何不变的。B 32 三刚片体系中,若有2对平行链杆,那么该体系仍有可能是几何不变的。A 33 一个单铰相当于一个约束。B 34 进行体系的几何组成分析时,若体系通过三根支座链杆与基础相连,可以只分析体系内部。B 35 三刚片体系中,若有两个虚铰在无穷远处,则该体系一定为几何可变。B 36 有多余约束的体系为静定结构。B 37 静定结构一定几何不变。A 38 超静定结构一定几何不变.A 39 几何不变体系一定是静定结构。B 40几何不变体系一定是超静定结构。B 41力是物体间相互的机械作用。A 42 力的合成遵循平行四边形法则。A 43 力的合成遵循三角形法则。A 44 力偶没有合力。A 45 力偶只能用力偶来平衡。A 46 力偶可以和一个力平衡。B 47 力偶对物体既有转动效应,又有移动效应。B 48 固定铰支座使结构在支承处不能移动也不能转动。B 49 可动铰支座使结构在支承处能够转动,但不能沿链杆方向移动。A 50 结点法求解桁架内力应按照结构几何组成相反顺序来求解。A 51 将一个已知力分解为两个力可得到无数解答。A 52 作用力和反作用力是作用在同一物体上的两个力。B 53 作用力和反作用力是作用在不同物体上的两个力。A 54 两个力在同一轴上的投影相等,此两力必相等 B 55 力偶对平面内任一点的矩等于力偶矩A 56 力偶在坐标轴上的投影的代数和等于零A 57 一个固定铰支座相当于两个约束。A 58三个本身无多余约束的刚片用三个不共线的单铰两两相连,则组成的体系为超静定结构B 59 桁架是“只受结点荷载作用的直杆、铰结体系”。A 60桁架结构的内力有轴力。A 61 拱的合理拱轴线均为二次抛物线。B 62无铰拱属于超静定结构。A 63 三铰刚架和三铰拱都属于推力结构。A 64 简支刚架属于推力结构。B 65 三铰拱属于静定结构。A 66 相同竖向载荷作用下,同跨度拱的弯矩比代梁的弯矩大得多。B 67 桁架结构中,杆的内力有轴力和剪力。B 68 竖向载荷作用下,简支梁不会产生水平支反力.A 69 竖向载荷作用下,拱不会产生水平支反力。B 70 竖向载荷作用下,拱的水平推力与拱高成正比。B 2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 1 ?在数据结构中,从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时,一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 第1题第2题2.图示外伸梁,跨中截面C的弯矩为( ? m D.17kN m 题7图图(a)图(b)图(c)图(d)位移法典型方程中系数k ij=k ji反映了() A.位移互等定理 B.反力互等定理 第9题第10题 10.FP=1在图示梁AE上移动,K截面弯矩影响线上竖标等于零的部分为().DE、AB段B.、DE段C.AB、BC段D.BC、CD段 二、填空题:(共10题,每题2分,共20分) 两刚片用一个铰和_________________相联,组成无多余约束的几何不变体系。 所示三铰拱的水平推力 第3题机动法作静定结构内力影响线依据的是_____________。 .静定结构在荷截作用下,当杆件截面增大时,其内力____________。 D处的纵标值y D为_________。 第6题第7题 7.图示结构,各杆EI=常数,用位移法计算,基本未知量最少是_________个。 8.图示结构用力法计算时,不能选作基本结构的是______。 3.用力法计算图示刚架,并绘其M 图,EI D 4m N/m EI 10kN/m A B C D 2EI EI 4m 2m 4m G F EI 10k N /m C F l ql 12 2 G A 一、选择题:(共10题,每小题2分,共20分) 1.A 2.D 3. A 4.D 5.A 6.C 7.D 8.B 9.C 10.C 二、填空题(共10空,每空2分,共20分) 1.不通过此铰的链杆 2. FP/2(→) 3.l θ(↓) 4. 刚体体系虚功原理 5.不变 6.-1/2 7.6 8.(c ) 9.反对称 10.无侧移的超静定结构 三、问答题:(共2题,每小题5分,共10分) 1.图乘法的应用条件是什么?求变截面梁和拱的位移时可否用图乘法? 答.图乘法的应用条件:1)杆轴线为直线,2)杆端的EI 为常数3)MP 和M 图中至少有一个为直线图形。否。(7分) 2.超静定结构的内力只与各杆件的刚度相对值有关,而与它们的刚度绝对值无关,对吗?为什么? 答:不对。仅受荷载作用的超静定结构,其内力分布与该结构中的各杆刚度相对值有关;而受非荷载因素作用的超静定结构,其内力则与各杆刚度的绝对值有关。(7分) 四、计算题. (1、2题8分,3题10分,4、5题12分,4题共计50分) 1.图示桁架,求1、2杆的轴力。 解:F N1=75KN ,F N2=2 13 5 KN 2.图示刚架,求支座反力,并绘弯矩图。 解:F Ay =22KN (↓)F Ax =48KN (←)F By =42KN (↑) 最终的弯矩图为: 3.用力法计算图示刚架,并绘其M 图,EI 为常数。 数据结构试题? 一、?单选题(每题 2 分,共20分) 1.1.???? 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2.???? 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时,其平均查找长度( B )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7.???? 若需要利用形参直接访问实参时,应将形参变量说明为( D )参数。 A.值 B.函数 C.指针 D.引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有 相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N(M: N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题(n)大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度:随着n的增加时增长函数的一般性质,这一特性基于该表达式的主项,即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次,算法的阶次是忽略该算法的增长函数中的常量和其他次要项,只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度:增长函数的界限,由增长函数的主项确定的。渐进复杂度类似的函数,归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法:与问题大小无关、执行时间恒定的增长函数称为具有O(1)的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法,从运行效率的角度来说都是等价的。 9.如果算法的运行效率低,从长远来说,使用更快的处理器也无济于事。 10.要分析循环运行,首先要确定该循环体的阶次n,然后用该循环要运行的次数乘以它。(n 表示的是问题的大小) 11.分析嵌套循环的复杂度时,必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析: 如:public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O(n),计算调用该方法的初始循环的时间复杂度,只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O(n2)。 13指数函数增长> 幂函数增长> 对数函数增长 2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) A.(100,80,90,60,120,110,130) B.(100, 120, 110,130,80, 60,90) C.(100,60,80,90,120,110,130) D.(100,80, 60,90, 120, 130,110) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 第 1 章绪论 课后习题讲解 1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为()、()、()和()。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。 二、判断改错题。 1. 位移法仅适用于超静定结构,不能用于分析静定结构。( × ) 2位移法未知量的数目与结构的超静定次数有关。( × ) .3 位移法的基本结构为超静定结构。( × ) 4. 位移法中角位移未知量的数目恒等于刚结点数。(×) 提示:与刚度无穷大的杆件相连的结点不取为角位移未知量。 1. 瞬变体系的计算自由度一定等零。 2. 有多余约束的体系一定是几何不变体系。 1、三刚片用三个铰两两相联不一定成为几何不变体系。(×) 2、对静定结构,支座移动或温度改变不会产生内力。(×) 3、力法的基本体系不一定是静定的。(×) 4、任何三铰拱的合理拱轴不一定是二次抛物线。(×) 5、图乘法不可以用来计算曲杆。(×) 6、静定结构的影响线全部都由直线段组成。(√) 7、多跨静定梁若附属部分受力,则只有附属部分产生内力。(×) 8、功的互等定理成立的条件是小变形和线弹性。(√) 9、力法方程中,主系数恒为正,副系数可为正、负或零。(√) 10.三个刚片用不在同一条直线上的三个虚铰两两相连,则组成的体系是无多余约束的几何不变体系。( √) 三、选择题。 1. 体系的计算自由度W≤0是保证体系为几何不变的 A 条件。 A.必要 B.充分 C.非必要 D. 必要和充分 1、图示结构中当改变B点链杆方向(不能通过A铰)时,对该梁的影响是( d ) A、全部内力没有变化 B、弯矩有变化 C、剪力有变化 D、轴力有变化 2、图示桁架中的零杆为( b ) A 、DC, EC, DE, DF, EF B 、DE, DF, EF C 、AF, BF, DE, DF, EF D 、DC, EC, AF, BF 4、右图所示桁架中的零杆为( b A 、CH BI DG ,, B 、DG DE ,, C 、AJ BI BG ,, D 、BI BG CF ,, 5、静定结构因支座移动,( b ) A 、会产生内力,但无位移 B 、会产生位移,但无内力 C 、内力和位移均不会产生 D 、内力和位移均会产生 7、下图所示平面杆件体系为( b ) A 、几何不变,无多余联系 B 、几何不变,有多余联系 C 、瞬变体系 D 、常变体系 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列,在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构? ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io ), A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放A[1]中, 现进行二分查找,则查找 A [3]的比较序列的下标依次为( A. 1 , 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 8. 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O (1) B. O (n ) C. O ( 1 og 2n ) D. O (n2) 9. 对于线性表( 7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选 用 H (K )=K %9 作为散列函数,则散列地址为 1 的元素有( )个, 位置在 676(10),每个元素占一个空间, 表示用 10 进制表示。 问 A[3][3] (10)存放在什么位置?脚注 (10) 5. A .688 B .678 C . 692 D . 696 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 ( ). A .2-1 B.2K+1 C.2K-1 D. 2k-1 7. 广东创新科技职业学院期末考试试题(标明A 卷、B 或C 卷) 2018 —2019 学年第二学期考试科目:《数据结构》 (闭(开)卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题(每小题 2 分,共 40 分) 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. 下述程序段①中各语句执行频度的和是()。 s=0; ① for(i=1;i<=i;j++) s+=j; A .n-1 B .n C .2n-1 D .2n 7. 下面程序段的时间复杂度为()。 for(i=0;i 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为()。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为()。 for(i=n-1;i>=0;i--) for(j=0;jnext; p->next= Q.rear->next; (D)、p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于() (A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和 (C)、各叶子结点的带权路径长度之和(D)、根结点的值 10.线索二叉链表是利用()域存储后继结点的地址。 (A)、lchild (B)、data (C)、rchild (D)、root 二、填空题 第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i 2005年-2006学年第二学期“数据结构”考试试题(A) 姓名学号(序号)_ 答案隐藏班号 要求:所有的题目的解答均写在答题纸上(每张答题纸上要写清楚姓名、班号和学号),需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题(每小题2分,共20分) 1.数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答:A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答:参见本节要点3。本题答案为:A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答:C。 4.以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答:C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答:D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答:B。 8. 用直接插入排序对下面四个序列进行递增排序,元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答:C。 9. 以下序列不是堆(大根或小根)的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三) (四) (五) (六) (七 )(八 ) (九 ) (十 ) 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三 ) (四 ) (五 ) (六) (七) (八) (九) (十 ) 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列,在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分,共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n],假设 个空间,问 676(10),每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置?脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ) 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中,第一个元素放 A[1]中,现进行二 分查找,则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选用 H (K ) =K %9作为散列函数,则散列地址为 1的元素有(D )个, A . 1 B . 2 C . 3 10. 设有6个结点的无向图,该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分,共26分) 1.通常从四个方面评价算法的质量: _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个,树的深度为 ____________ ,树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 第一章 1.在数据结构中,从逻辑上可以把数据结构分为(C ) A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O(mn)_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是(A) A 可以随机访问任一结点(顺序) B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为(A ),带头结点的单链表head为空的判定条件为(B ) A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中,读取元素花费时间最少的是(D) A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表,宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点,并保持链表元素仍然有序, 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上,设有头和尾两个指针,执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比,双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针,则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续,这句话正确吗? (不正确) 11. 某线性表采用顺序存储结构,元素长度为4,首地址为100,则下标为12的(第13个)元素的存储地址为148。V 100+4*12=148 11.在顺序表的(最后一个结点之后)插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除,则该线性表宜采用(顺序)存储结构,若频繁地对线性表进行插入和删除操作,则该线性表宜采用( 链 )存储结构。结构力学2期末考试复习题
数据结构试题及答案(免费)
结构力学期末考试题库
2017年数据结构期末考试题及答案A
结构力学期末考试试题及答案
数据结构试题及答案
数据结构复习资料,java数据结构期末考试
《数据结构》期末考试题及答案
数据结构习题与答案
结构力学期末复习题及答案
2017数据结构期末考试试题及答案
《数据结构》期末考试试卷
数据结构期末考试试题及答案
数据结构试题及答案
数据结构期末考试试题含答案
十套数据结构试题与答案
数据结构习题及答案