长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(C卷)
班级:___________学号:___________姓名:___________得分:___________
题目部分，(卷面共有32题,100分,各大题标有题量和总分)
一、应用题(2小题,共16分)
1．分析下列程序段的时间复杂度：
（1）for (i=1; i<=n; i=2*i)
++x;
（2）for (i=1; i<=n; ++i)
for (j=1; j<=i-1; ++j)
++x;
2．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
二、判断正误(5小题,共10分)
1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）
2．非空的双向循环链表中任何结点的前驱指针均不为空。（）
3．在循环队列中无溢出现象。（）
4．稀疏矩阵压缩存储后，必会失去随机存取功能。（）
5．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）
三、单项选择题(10小题,共20分)
1．递归算法一般需要利用（）实现。
2．已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。
A．B+(i-1)*m B．B+i*m C．B-i*m D．B+(i+1)*m
3．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（）。
A．已固定B．不固定C．可以改变D．动态变化
4．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。
A top=top+1;
B top=top-1;
C top->next=top;
D top=top->next;
5．若串S="SOFTWARE"，其子串的数目最多是：（）。
A．35 B．36 C．37 D．38
6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。
A h
B h+1
C h或h+1
D 任意
7．下列命题正确的是（）。
A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一
B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一
C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一
D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一
8．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。
A 99
B 97
C 91
D 93
9．堆的形状是一棵（）。
A二叉排序树 B满二叉树 C完全二叉树 D 判定树
10．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。
A F，H，C，D，P，A，M，Q，R，S，Y，X
B P，A，C，S，Q，D，F，X，R，H，M，Y
C A，D，C，R，F，Q，M，S，Y，P，H，X
D H，C，Q，P，A，M，S，R，D，F，X，Y
四、算法设计题(4小题,共32分)
1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C 用链式存储结构表示。
3．对给定的带头结点的单链表L，编写一个删除L中值为X的结点的直接前趋结点的算法。4．设计一个在链式存储结构上统计二叉树中结点个数的算法。
五、填空题(11小题,共22分)
1．已知顺序栈S，在对S进行进栈操作之前首先要判断（），在对S进行出栈操作之前首先要判断（）。
2．设循环队列存放在向量sq.data[0:M]中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。
3．广义表((a), (((b),c)),(d))的表头是（），表尾是（）。
4．在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。
5．一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。
6．希尔排序法属于（）
7．对n个待排序记录序列进行快速排序，所需要的最好时间复杂度是（），最坏时间复杂度是（）。
8．假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（）
9．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。
10．图形结构的元素之间存在（）的关系。
11．数据的存储结构是指（）
长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(C卷)答案部分，(卷面共有32题,100.0分,各大题标有题量和总分)
一、应用题(2小题,共22分)
1．O(log2n) （2）O(n2)
2．【解答】构造的哈夫曼树如图所示。
树的带权路径长度为：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2
=120
二、判断正误(5小题,共22分)
1．错
2．对
3．错
4．对
5．对
三、单项选择题(10小题,共22分)
1．栈
2．A
3．A
4．D
5．C
6．C
7．B
8．B
9．C
10．D
四、算法设计题(4小题,共22分)
1．typedef char datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)
{
lklist *p; ha=0,hb=0,hc=0;
for(p=head;p!=0;p=head)
{
head=p->next; p->next=0;
if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}
else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} }
}
2．typedef struct node {
int data;
struct node *next;
}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t; For(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next)
if (q->data==p->data) break;
if(q!=0){
t=(lklist *)malloc(sizeof(lklist));
t->data=p->data;
t->next=hc;
hc=t;}
}
}
3．解：
void delete(ListNode *L)
{ ListNode *p=L,*q;
if (L->next->data==X)
{ printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”);
return;
}
for (;p->next->data!=X; q=p; p=p->next); // 删除指针p所指向的结点q->next=p->next;
delete p;
}
4．void countnode(bitree *bt,int &count)
{
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} }
五、填空题(11小题,共22分)
1．栈是否满栈是否空
2．(sq.rear+1)%(M+1)==sq.front；
3．(a)，((((b),c)),(d))
4．n，n-1
5．2i-1，(n+1)/2，(n-1)/2
6．插入类排序
7．【解答】O(nlog2n)，O(n2)
8．n(n-1)/2
9．60
10．多对多
11．数据的逻辑结构在计算机中的表示
长沙理工大学考试试卷………………………………………………………………………………………………………………试卷编号 A 拟题教研室（或教师）签名教研室主任签名……………………………………………………………………………………………………………… 课程名称（含档次）汽车构造课程代号08020025 专业汽服、车辆层次（本、专）本考试方式（开、闭卷）闭卷 一、填空题（请在每小题的空格中填上正确答案。本题总分20分，每个空1分题） 1、活塞的基本构造可分为、、三个部分。沿轴线 方向成上下的锥形。 2、惯性锁环式同步器的锁止部件是，锁销式同步器的锁止部件是。 3、液力变矩器主要由、和三部分组成。 4、化油器由、、、、 等五大供油装置组成。 5、大货车的万向传动装置一般由、、组成。前置前驱轿车靠主 减速器处为球笼式万向节，靠车轮处为球笼式万向节。 二、选择题（请在每小题的备选答案中，选出一个正确答案。本题总分10分，每小题1分） 1、发动机用于平衡旋转惯性力及其力矩的平衡重一般设在（）。 A. 曲轴前端 B. 曲轴后端 C. 曲柄上 2、在排气上止点( )。 A. 进气门开启、排气门关闭 B. 排气门开启、进气门关闭 C. 排进气门同时开启 3、以发动机转速和进气量作为基本控制参数的汽油喷射系统为（）。 A. D型汽油喷射系统 B. L型汽油喷射系统 C. K型汽油喷射系统 4、当上行柱塞上的斜槽与柱塞套上的油孔相通时，柱塞式喷油泵（）。 A. 准备喷油 B. 开始喷油 C. 结束喷油 5、现代轿车水冷系一般使用（）节温器。 A．蜡式B．膨胀筒式 C．乙醚式 第1页（共 1 页）
一、选择(2’×15=30’) 1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时 间复杂度为( ) A.O(0) B.O(1) C.O(n) D.O(n2) 2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾 结点，则在进行删除操作时( ) A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都不修改 D.队头、队尾指针都可能要修改 3.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S，若每个元素出栈 后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( ) A.1 B.2 C.3 D.4 4.对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( ) A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D) 7.下面关于二分查找的叙述正确的是( ) A.表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序，且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列 D.表必须有序，且表只能以顺序方式存储 8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是( ) A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序 9.下列关于无向连通图特性的叙述中，正确的是( ) I.所有顶点的度之和为偶数 II.边数大于顶点个数减1
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、隧道：一种修建在地下，两端有出入口，供车辆、行人、水流及管线等通行的工程建筑物。 3、隧道建筑限界：为了保证隧道内各种交通正常运行与安全，而规定在一定宽度和高度范围内不得有任何障碍物的空间范围。 4、隧道净空：隧道衬砌内轮廓线所包围的空间，包括隧道建筑限界、通风、照明及其他所需面积。 5、复合式衬砌：由初期支护和二次衬砌及中间防水层组合而成的衬砌形式。 6、围岩压力：衬砌结构承受的压力，即围岩压力。 7、围岩：隧道周围一定范围内，对隧道稳定性能产生影响的岩土体。 8、坍落拱：隧道开挖后围岩力学形态经历“平衡-变形，破坏，坍塌，应力重分布-新的平衡”的过程，所得最终产物称为“坍落拱”。 9、松动压力：由于开挖而松动或坍塌的岩体以重力形式直接作用在支护结构上的压力称为松动压力。 10、形变压力：由于围岩变形受到与之密贴的支护如锚喷支护的抑制，而使围岩在与支护结构的共同变形过程中对支护结构施加接触压力。 11、岩石的流变性：岩石在力的作用下发生的与时间有关的变形性质，称为岩石的流变性。 12、洞门：隧道端部外露面，一般都修筑为保护洞口和排放流水的挡土墙式结构，称为“洞门”。 13、明洞：明挖后进行支护后覆土回填的洞口段。 14、岩体的初始应力状态：指在天然状态下存在于岩体内部的应力状态。 15、二次应力状态：隧道洞室开挖后，围岩的初始应力状态遭到破坏，围岩应力在洞室周围一定范围内重新调整。 16、弹性抗力：隧道衬砌两侧及底部衬砌则压入围岩，引起围岩对衬砌的约束，产生出相应的被动抵抗力。 17、新奥法：以控制爆炸为开挖方法，以喷锚为主要支护手段，通过监测控制围岩变形，动态修正设计参数和变动施工方法的一种隧道工程理念。18、马口开挖：指需要挖出土石方后进行衬砌的一种开挖方式。 19、新奥法的现场监控量测：在隧道的施工过程中，使用各种仪器设备和量测元件，对地表沉降、围岩与支护结构的变形，应力、应变进行量测，据此来判断隧道开挖对地表环境的影响范围和程度、围岩的稳定性和支护的工作状态。 20、岩爆：在坚硬稳定的岩层中开挖隧道时，有时会遇到小块岩石突然脱离岩体向隧道内弹出，人们称为“岩爆”。 21、风流中性点：指风速为零的点，它不会出现在纵向式通风中，而只会出现在半横向式和全横向式通风中。 22、收敛:隧道开挖后两边围岩向中间变形。 23、光面爆破：通过正确确定周边眼的各爆破参数，使爆破后的围岩断面轮廓整齐，最大限度地减轻爆破对围岩的振动和破坏，尽可能维持围岩原有的完整性和稳定性的爆破技术。 1、隧道按用途可以分为：交通、市政、水工、矿山四种类型。 2、交通隧道可以分为：铁路、公路、地下、水底、航运、人行六种。 3、市政隧道可以分为：给水,污水,管路、线路,人防四种类型。 4、水工隧道可以分为：引水、尾水、排沙、泄洪四种类型。 5、矿山隧道可以分为：运输巷道、给水、通风三种类型。 6、施工前三阶段勘查包括：可行性研究勘察、初步勘察、详细勘察。 7、隧道洞口位置选择时应贯彻早进晚出原则。 8、隧道纵坡分为单坡和人字坡两种形式。 9、隧道的轮廓线包括：衬砌内轮廓线、外轮廓线、实际开挖线三种。 10、隧道的主体结构包括洞门和明洞。 11、两座隧道根据其之间净距的大小分为：分离式隧道、连拱隧道和土质隧道。 12、围岩压力按作用力发生的形态，一般可分为松动压力和形变压力。 13、根据破坏时的应力类型，岩石的破坏有受拉、受压和受剪三种基本类型。 14、岩石的流变性包括蠕变、松弛和弹性后效。 15、岩石坚硬程度定量指标用R表达，而岩体完整程度的定量指标用Kv表达。 16、在对岩体基本质量指标BQ进行修正时，应考虑地下水、主要软土结构面产状和初始应力状态三个因素。 17、明洞结构类型可分为拱式明洞、箱形明洞和棚式明洞三类。 18、隧道的通风设计应分别按稀释CO浓度和稀释烟雾浓度来计算需风量。 19、按行车道空间的空气流动方式，公路隧道的机械通风方式分为射流式、风道式和集中排给式。 20、长隧道的照明可以分为洞口接近段、入口段、过渡段、中间段以及出口段五个区段。 21、公路隧道防排水应根据的总原则是防排、截堵结合、因地制宜、综合治理。 22、新奥法施工的基本原则有少扰动、早支护、勤量测、紧封闭。 23、锚杆的类型按照作用原理可划分为全长粘结型锚杆、端头锚固型、摩擦型、预应力锚杆和自钻锚杆。 24、在岩溶地段，隧道常用处理溶洞的方法，有引、堵、越、绕四种。 25、辅助施工措施的预加固措施有：预注浆加固地层、地表喷锚预加固。 26、监控量测项目可分为必测项目和选测项目。 27、喷射混凝土的喷射方式有：干喷、潮喷、湿喷。 28、锚杆的加固作用有悬吊效应、组合梁效应、加固效应。 29、隧道施工进度表达通常采用“进度图”(即施工进度图)的形式表示，施工进度图一般采用横道图法和网络图法等表示形式。 30、隧道营运管理包括交通管理、管理设施与安全设施等方面。
以下内容在任亚洲同学原稿上（）稍作修改，仅做参考，为了保证答案的正确性跟同志们的过科率，希望大家踊跃发现并改正其中的错误，如有修改请在修改完成后注明修改后的版本，谢谢合作！（本版本）。 温馨提示：X表示X— 1. 2812芯片：定点32位芯片。 2. 2000系列功能比较强。 3. 2812 I/O口供电电压，内核供电电压或。 4. 2812编译时.CMD是什么文件，.OUT是什么文件 答：CMD是链接命令文件，.OUT是最终可执行成文件。 5. 2812的3个CPU定时器是多少位 DSP采用段的概念，各个段的都有什么意思 答：○32位； ○已初始化的段：包含真实的指令跟数据，存放在程序储存空间。 未初始化的段：包含变量的地址空间，存放在数据存储空间。 6. 2812 时钟150M时，低速、高速外输时钟是多少 答：低速，高速75MHz 7. DSP总线结构是什么样子 答：先进型哈弗结构。 8. 2812 CPU的中断有可屏蔽中断和不可屏蔽中断，分别是哪些 答：○可屏蔽中断：INT1~INT14 14个通用中断；DLOGINT数据标志中断；RTOSINT实时操作系统中断。 ○不可屏蔽中断：软件中断（INTR指令和TRAP指令）；硬件中断NMI，非法指令陷阱； 硬件复位中断；用户自定义中断。 9. 2812实际寻址空间是多少 答：地址：00000~3FFFF（4M） 10. 2812一个事件管理器（EV）能够产生8路PWM波。（2路独立PWM波，3对6路互补PWM
波） 11.DSP有3组地址总线，3组数据总线，分别是什么 答：地址：程序地址总线、数据读地址总线、数据写地址总线。 数据：程序读数据总线、数据读数据总线、数据写数据总线。 12. ADC模块有多少路采样通道8*2=16路 13. SCI和SPI口哪一个需要设置波特率SCI 14. 把目标文件下载到实验板怎么操作 答：File----load program 15. CAN通讯的最大带宽是多少 1M 16. 加上看门狗，2812内部定时器一共有多少个 答：3个CPU定时器，4个事件管理通用定时器，1个看门狗定时器，总共8个。 17. 2812DSP流水线深度为8。 18. TI公司生产的最牛cpu是667x有8个核，320G mac /s。注：mac是乘法累加 19. 2812AD满量程转换时，转换寄存器的值是多少0xFFF0 20. 2812CPU最小系统：主芯片，电源模块，时钟电路，复位电路，JTAG电路 21. DSP生产厂家是TI公司，ADI公司，Freescale（飞思卡尔）公司。 22. TI公司的DSP芯片类型有C2000，C5000，C6000系列 23. DSP工程开发，需要编写4个文件：头文件，库文件，源文件，CMD文件。 24. 2812有2个事件管理器EVA、EVB，每一个事件管理器包含哪几个功能模块 答：通用定时器；全比较单元；捕获单元；正交编码电路。 25. 2812定时器计数周期怎么算T=(TDDRH:TDDR+1)*(PRDH:PRD+1) /150 s 26. 2812在什么情况下工作于微处理器模式MP/MC=0 27. 2812中断系统有一部分挂在PIE上面，这些都属于可屏蔽中断，那么能够响应中断的条件是什么 答： INTM置0响应总中断，其他的置1响应。（INTM=0，IFR=1，IER=1，PIEIFR=1，PIEIER=1，PIEACR=1） 28. 2812在进行引导时第一条程序在什么位置0x3FFFC0 注：就是程序运行的起始地址，
数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位
B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。
------------------------------------------------------------------------------------------------------------------------------ (单选题) 1: 若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。 A: 9 B: 11 C: 15 D: 不确定 正确答案: (单选题) 2: 具有10个叶结点的二叉树中有( )个度为2的结点。 A: 8 B: 9 C: 10 D: 11 正确答案: (单选题) 3: 设无向图的顶点个数为n,则该图最多有( )条边。 A: n-1 B: n(n-1)/2 C: n(n+1)/2 D: 0 正确答案: (单选题) 4: 一个n个顶点的连通无向图,其边的个数至少为( )。 A: n-1 B: n C: n+1 D: nlogn 正确答案: (单选题) 5: n个结点的完全有向图含有边的数目( )。 A: n*n B: n（n＋1) C: n／2 D: n*（n－l） 正确答案: (单选题) 6: 设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。 A: 求子串 B: 联接 C: 模式匹配 D: 求串长 正确答案: (单选题) 7: 串的长度是指( )。 A: 串中所含不同字母的个数 B: 串中所含字符的个数 C: 串中所含不同字符的个数 D: 串中所含非空格字符的个数
------------------------------------------------------------------------------------------------------------------------------ 正确答案: (单选题) 8: 树的后根遍历序列等同于该树对应的二叉树的( )。 A: 先序序列 B: 中序序列 C: 后序序列 D: 以上都不对 正确答案: (单选题) 9: 在下列存储形式中,哪一个不是树的存储形式?( ) A: 双亲表示法 B: 孩子链表表示法 C: 孩子兄弟表示法 D: 顺序存储表示法 正确答案: (单选题) 10: 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( )。 A: CBEFDA B: FEDCBA C: CBEDFA D: 不定 正确答案: (判断题) 1: 完全二叉树一定存在度为1的结点。 T: 对 F: 错 正确答案: (判断题) 2: 二叉树的遍历结果不是唯一的. T: 对 F: 错 正确答案: (判断题) 3: 一个树的叶结点,在前序遍历和后序遍历下,皆以相同的相对位置出现。 T: 对 F: 错 正确答案: (判断题) 4: 完全二叉树中,若一个结点没有左孩子,则它必是树叶。 T: 对 F: 错 正确答案: (判断题) 5: 在n个结点的无向图中,若边数大于n-1,则该图必是连通图。 T: 对 F: 错 正确答案: (判断题) 6: 强连通图的各顶点间均可达。 T: 对 F: 错
第二章算法分析 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指数函数增长> 幂函数增长> 对数函数增长
长沙理工大学高等数学试题及答案 一、单项选择题（本大题共5小题，每小题2分，共10分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．设f(x)=lnx ，且函数?(x)的反函数1?-2(x+1)(x)= x-1，则[]?=f (x)（ ） ....A B C D x-2x+22-x x+2 ln ln ln ln x+2x-2x+22-x 2．()002lim 1cos t t x x e e dt x -→+-=-?（ ） A ．0 B ．1 C ．-1 D ．∞ 3．设00()()y f x x f x ?=+?-且函数()f x 在0x x =处可导，则必有（ ） .lim 0.0.0.x A y B y C dy D y dy ?→?=?==?= 4．设函数,131,1 x x x ?≤?->?22x f(x)=，则f(x)在点x=1处（ ） A.不连续 B.连续但左、右导数不存在 C.连续但不可导 D. 可导 5．设C +?2 -x xf(x)dx=e ，则f(x)=（ ） 2222-x -x -x -x A.xe B.-xe C.2e D.-2e 二、填空题（本大题共10小题，每空3分，共30分） 请在每小题的空格中填上正确答案。错填、不填均无分。 6.设函数f(x)在区间[0，1]上有定义，则函数f(x+14)+f(x-14)的定义域是__________. 7．()()2lim 1_________n n a aq aq aq q →∞++++<= 8．arctan lim _________x x x →∞= 9.已知某产品产量为g 时，总成本是2 g C(g)=9+800 ，则生产100件产品时的边际成本100__g ==MC 10.函数3()2f x x x =+在区间[0，1]上满足拉格朗日中值定理的点ξ是_________. 11.函数3229129y x x x =-+-的单调减少区间是___________. 12.微分方程3'1xy y x -=+的通解是___________. 13. 设2ln 2,6 a a π==?则___________. 14.设2cos x z y =则dz= _______. 15.设{}2(,)01,01y D D x y x y xe dxdy -=≤≤≤≤=??，则_____________.
《数据结构与算法》（c语言版）期末考复习题 一、选择题。 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．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 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、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4 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.以顺序方式存储，且数据元素有序 长沙理工大学考试试卷 ……………………………………………………………………………………………………….. 试卷编号 B-1 拟题教研室（或教师）签名 喻林萍 教研室主任签名 …………………..………………………………………………………..……………………………………….. 课程名称（含档次） 物理化学B 课程代号 002210 专 业 食品科学、生物工程、无机材料 层次（本、专） 本 考试方式（开、闭卷） 闭 一、填空题（共24分每小题2分） 1．在300K ，100kPa 下，某理想气体的密度ρ=0.08275kg/m 3 。则该气体的摩尔质量M = 2.064*10-3kg/mol 。 2．1mol 理想气体A ，从始态B 经途径I 到达终态C 时，系统与环境交换了()15Q I kJ =-，kJ I W 10)(=。若该1mol 理想气体A 从同一始态B 出发经途径II 到达同一终态C 时，系统与环境交换了Q (II)=10-kJ ，则整个过程系统的热力学能变化=?U _____-5kJ ___ kJ 。 3．在T 1=750K 的高温热源与T 2=300K 的低温热源之间工作一卡诺可逆热机，当其从高温热源吸热Q 1=250KJ 时，该热机对环境所做的功W =___-150 __ kJ 。 4．1mol 单原子理想气体从体积V 1开始，经过绝热自由膨胀后变至10V 1，?S ＝ 19.14 J ·K -1 。 5．一定温度压力下，一切相变化必然朝着化学势降低的方向进行。 6．在高温热源1T 和低温热源2T 之间的卡诺循环，其热机效率=η。 7．在某一温度T 的抽空容器中，)(34s HCO NH 进行分解反应， )(34s HCO NH →NH 3(g)+CO 2(g)+H 2O(g) 达到平衡时所产生气体的总压力为60kPa 。则此热分解反应的标准平衡常数K !=（8.0×10-3 ）。 8．将过量)(3s NaHCO 放入一真空密封的容器中，在50℃下3NaHCO 按下式进行分解 2)()()()(22323g O H g CO s CO Na s NaHCO ++? 系统达到平衡后向系统中加入)(2g CO 时，系统重新达平衡，则系统组分的K ＝（ 3）；f =（ 1 ）。 9．原电池的阳极发生 氧化 反应，是原电池的负极。电解池的阴极发生还原反应，是电解池的负 极。 10．某电导池中充以0.10mol·dm -3 的醋酸水溶液，25℃时测得其电阻为703Ω，已知该电导池的电导常数 第 1 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; i 6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 广东创新科技职业学院期末考试试题（标明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 integer m,n,i,d1,d2 read*,m select case(m) case(2:9) d1=m;d2=0;d3=0 case(10:99) d1=mod (m,10);d2=m/10;d3=0 case(100:999) d1=mod (m,10);d2=mod(m/10,10);d3=m/100 endselect do m=3,999,2 n=sqrt(m) do i=2,n if(mod (d1+d2+d3),2)==1.and.mod (n,i)==0.and.n >i) print*,m enddo enddo end 考试时间为60分钟。选择题请考生点击题干，方能显示答题选项。看清试题，再选择认为正确的选项。（如要修改，请重复点击一次选择的选项，即取消所选答案。）答题完毕，请点击“提交”，系统即显示考生的考试成绩。每位考生只有一次考试机会。一、单选题(共20题，40分)。 1、 党的（D ）把毛泽东思想确立为党的指导思想。 A 、 二大 B 、 三大 C 、 五大 D 、 七大 2、 1920年11月，中国共产党上海发起组制定了（B ），以此作为接纳党员的标准。 A 、 《共产党宣言》 B 、 《中国共产党宣言》 C 、 《社会主义史》 3、 （ B ）是马克思主义的核心问题，是马克思主义哲学和政治经济学的合乎逻辑的必然结论和理论归宿。 A 、 科学社会主义 B 、 辩证唯物论 C 、 唯物史观 D 、 剩余价值论 4、 我们党的最大政治优势是 (A )。 A 、 密切联系群众 B 、 马克思列宁主义、毛泽东思想、邓小平理论和“三个代表”重要思想 C 、 工人阶级，同时又是中华民族的先锋队 D 、 掌握国家政权 5、 党员没有正当理由，连续（ C ）个月不交纳党费，被认定为自行脱党。 A 、 1 B 、 3 C 、 6 D 、 12 6、 党的最终奋斗目标是由工人阶级的（ C ）决定的。 A 、 先进性 B 、 历史使命 C 、 性质 D 、 革命彻底性 7、 加强党的先进性建设的根本目的是（ D ）。 A 、 提高人民生活水平 B 、 增强社会主义综合国力 C 、 提高党的执政能力、巩固执政地位 D 、 使我 8、 1918年7月李大钊公开发表了国内第一篇宣传十月革命的文章（C ）。 A 、 《我的马克思主义观》 B 、 《庶民的胜利》 C 、 《法俄革命之比较观》 D 、 《布尔什维主义的胜利》 9、 （ C ）是发展先进文化的重要内容和中心环节。 A 、 加强社会主义思想政治建设 B 、 加强社会主义理论建设 C 、 加强社会主义思想道德建设 D 、 加强社会主义道德素质建设 10、 党的先进性归根到底要看它（B ）。 A 、 究竟代表谁的根本利益 B 、 在推动历史前进中的作用 C 、 有没有一定的执政水平和为人民服务的本领 D 、 是促进生产力还是阻碍生产力发展 11、 坚持党的基本路线不动摇，关键是坚持（C ）不动摇。 A 、 马克思列宁主义 B 、 “三个代表” C 、 以经济建设 为中心 D 、 社会主义制度 12、 按照党的十六大要求，贯彻“三个代表”重要思想，核心在于保持（ B ）。 A 、 工人阶级的基础 B 、 党的先进性 C 、 党的生命力 D 、 解放思想，实事求是的基本路线 13、 （A ）是最活跃、最革命的因素，是社会发展的最终决定力量。 A 、 人 B 、 生产力 C 、 思想 14、 党章规定发展党员要有（ B ）名正式党员作介绍人。 A 、 1 B 、 2 C 、 3 D 、 4 15、 中国共产党的领导地位是（B ）。 A 、 经过全民选举产生的 B 、 经过长期斗争考验形成的 C 、 中国特殊国情决定的 D 、 党的性质和宗旨决定的 16、 2005年6月21日，被任命为中华人民共和国香港特别行政区第二任行政长官的是（ A ）。 A 、 董建华 B 、 何厚铧 C 、 曾荫权 D 、 梁锦松 17、 党从全面建设小康社会、开创中国特色社会主义事业新局面的全局出发提出的一项重大任务是（ C ）。 A 、 加强党的执政能力建设 B 、 大力开展反腐倡廉工作 C 、 构建社会主义和谐社会 D 、 增强社会主义综合国力 18、 （B ）这是靠拢党组织的重要形式和表现。 A 、 自觉主动向党组织汇报 B 、 积极参加党的活动 C 、 认真接受党组织的培训 D 、 积极学习党的理论知识 19、 加快建设节约型社会的动力是（A ）。 A 、 改革开放和科技进步 B 、 合理利用社会资源，避免资源浪费 C 、 节约使用资源和提高资源利用效率 D 、 节能、节水、节材、节地、资源综合利用和发展循环经济 20、 唱响社会主义文化的主旋律，坚持为人民服务，为社会主义服务，实行（ A ），是发展先进文化必须贯彻的重要方针。 A 、 百花齐放，百家争鸣 B 、 爱国主义，集体主义 C 、 古为今用，洋为中用 1、 加快建设节约型社会的动力是（A ）。 A 、 改革开放和科技进步 B 、 合理利用社会资源，避免资源浪费 C 、 节约使用资源和提高资源利用效率 D 、 节能、节水、节材、节地、资源综合利用和发展循环经济 2、 党的思想建设和作风建设的保证是 ( c )。大工数据结构课程考试模拟试卷a
《数据结构》期末考试题及答案
长沙理工大学考试试卷1
数据结构期末考试试题A卷(完成,不知对不对)
《数据结构》期末考试试卷
长沙理工大学最新党课考试题库
相关主题
文本预览