第二章线性表 西南交通大学,数据机构,课件
第二章线性表
一、单选题
1.链表不具备的特点是【】。
A.可随机访问任一结点
B.插入删除不需要移动元素
C.不必事先估算存储空间
D.所需空间与其长度成正比
2.设线性表有n个元素，以下操作中，【】在顺序表上实现比在链表上实现效率更高。
A.输出第i（1≤i≤n）个元素的值
B.顺序输出这n个元素
C.交换第1个与第2个元素的值
D.输出与给定值x相等的元素在线性表中的序号
3.如果最常用的操作是取第i个结点及其前驱，则采用【】存储方法最节省时间。
A.单链表
B.双链表
C.线性链表
D.顺序表
4.线性表是具有n个【】的有限序列（n≥0）。
A.表元素
B.字符
C.数据元素
D.数据项
5.下面关于线性表的叙述中，错误的是【】。
A.线性表采用顺序存储，则必须占用一片连续的存储单元
B.线性表采用顺序存储，则便于插入和删除操作
C.线性表采用链式存储，则不必占用一片连续的存储单元
D.线性表采用链式存储，则便于插入和删除操作
6. 线性表的顺序存储结构是一种【】。
A.随机存取的存储结构
B.顺序存取的存储结构
C.索引存取的存储结构
D.Hash存取的存储结构
7.单链表中增加一个头结点的目的是为了【】。
A.使单链表至少有一个结点
B.标识表首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储
8.不带头结点的单链表（头指针为h）为空的条件是【】。
A.h==NULL
B.h->next==NULL
C.h->next==h
D.h!=NULL
9. 带头结点的单链表（头指针为h）为空的条件是【】。
A.h==NULL
B.h->next==NULL
C.h->next==h
D.h!=NULL
10.带头结点的循环双向链表（头指针为L）为空的条件是【】。
A.L==NULL
B.L->next->prior==NULL
C.L->prior==NULL
D.L->next==L
11.非空的循环单链表（头指针为head）的尾结点（由p指向）满足【】。
A.p->next==NULL
B.p==NULL
C.p->next==head
D.p==head
12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【】最节省时间。
A.带头结点的双循环链表
B.单循环链表
C.带尾指针的单循环链表
D.单链表
13.若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【】的存储方式最节省时间。
A.顺序表
B.双链表
C.带头结点的双循环链表
D.单循环链表
14.在n个结点的线性表的顺序实现中，算法的时间复杂度为O(1)的操作是【】。
A.访问第i个结点和求第i个结点的直接前驱
B.在第i个结点后插入一个新结点
C.删除第i个结点
D.以上都不对
15.若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂度为【】。
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
16.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【】。
A.O(n)O(n)
B.O(n)O(1)
C.O(1)O(n)
D.O(1)O(1)
17. 线性表以链式方式存储，访问第i个结点的时间复杂度为【】。
A.O(i)
B.O(1)
C.O(n)
D.O(i-1)
18.循环链表H尾结点p的特点是【】。
A.p->next==H
B.p->next==H->next
C.p==H
D.p==H->next
二、判断题
【】1.取线性表的第i个元素的时间同i的大小有关。
【】2.线性表中每个元素都有一个直接前驱和一个直接后继。
【】3.顺序存储方式只能用于存储线性结构。
【】4.线性表采用链式存储时，结点和结点内部的存储空间可以不连续。
【】5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。
三、填空题
1.在一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动个元素。
2.在一个长度为n的顺序表中删除第i个元素时，需要向前移动个元素。
3.在单链表中设置头结点的作用是。
4.在单链中要删除某一指定结点，必须找到该结点的结点。
5.访问单链表中的结点，必须沿着依次进行。
6.在双链表中，每个结点有两个指针域，一个指向，一个指向。
7.在链表中，删除最后一个结点的算法时间复杂度为O(1)。
8.访问一个线性表中具有给定值的时间复杂度的数量级是。
9.由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为。
10. 在链表中，可以用表尾指针代替表头指针。
11.根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是，最坏的情况是。
12.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是和。
13.在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？。
14.在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？。
四、简答题
1.阐述顺序表和链表存储方式的特点。在什么情况下使用顺序表比链表好？
2.若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？
3.在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。
4.对链表设置头结点的作用是什么？
数据结构试题及答案
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 本次作业是本门课程本学期的第1次作业，注释如下：大学英语IV 第1单元作业题 一、单项选择题(只有一个选项正确，共40道小题) 1. – David, I got an A in Accounting! –_________________________ (A) I was surprised to hear the news. (B) Are you kidding? (C) That’s a pity. (D) Congratulations! 你选择的答案：[前面作业中已经做正确] [正确] 正确答案：D 解答参考：[第一单元]D 当得知他人在考试中取得好成绩时，首先应向对方表示祝贺，故D项为正确答案。A，B，C三个选项都不符合礼貌习惯。 2. – How do you think of this test? –_________________________ (A) I got 85. (B) Good luck. (C) It’s a piece of cake. (D) Don’t worry about it. 你选择的答案：[前面作业中已经做正确] [正确] 正确答案：C 解答参考：[第一单元]C 该题题干是询问对方对于考试的看法，“a piece of cake”表示“容易的事，小菜一碟”，说明回答者认为此次考试很容易，因此只有选项C符合上下文语境。 3. –Do you like Professor Zhang’s classes? –_________________________ (A) I never miss her class. (B) Chemistry is difficult to study. (C) I take a course in Chemistry. (D) Professor Zhang is a strict teacher. 你选择的答案：[前面作业中已经做正确] [正确] 正确答案：A 解答参考：[第一单元]A 说话者询问对方是否喜欢上张教授的课，选项A的言外之意是回答者十分喜欢教授的课因而从不缺席，故选A，其它三个选项不合题意。 4. – What school subject do you like best? –_________________________ (A) I hate Physics. 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第一章概论 一、选择题 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 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 浅析建筑施工安全管理问题及对策研究 大学本科毕业论文浅析建筑施工安全管理问题及对策研究 姓名：龙浩 学号： 专业：土木工程 导师： 学校代码： 毕业论文声明 本人郑重声明： 1. 此毕业论文是本人在指导老师下独立研究取得的成果，除了特别加以标注和致谢的 地方外，本文不包含其他人或其它机构已经发表或撰写过的研究成果。对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。本人完全意识到本声明的法律结果由本人承担。 2. 本人完全了解学校、学院有关保留、使用学位论文的规定，同意学校与学院保留并 向国家有关部门或机构送交此外的复印件及电子版，允许此文被查阅和借阅。本人授权西南交通大学网络教育学院可以将此文的全部或部分内容编入数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本文。 3. 若在西南交通大学网络教育学院毕业论文审查小组复审中，发现本文有抄袭，一切 后果均由本人承担（包括接受毕业论文成绩不合格、缴纳毕业论文重新学习费、不能按时获得毕业证书等），与毕业论文指导老师无关。 作者签名：龙浩日期：2014年9月20日 网络教育学院 毕业设计(论文) 任务书 Ⅰ、毕业设计（论文）题目： 浅析建筑施工安全管理问题及对策研究 Ⅱ、毕业设计（论文）使用的原始资料（数据）及设计技术要求： 1、查阅相关案例资料，熟悉我国施工现场管理安全现状。 2、查阅相关标准、熟知规范变化情况，了解施工现场安全管理中存在的遗留和漏洞。 3、掌握施工现场安全管理切入点、方法及控制要点。 Ⅲ、毕业设计（论文）工作内容： 1、查阅相应规范、标准，及时了解其更新情况。 2、通过施工现场安全管理的实践活动，熟悉施工现场可能存在安全隐患、施工现场安全控制过程中容易疏漏的工作，从此点入手进行剖析。 3、结合实习施工现场，通过典型以往安全事故进行分析，总结事故原因(技术、管理)，然后进行和项目部人员安全分享；提高项目部安全管理水平。 4、完成毕业设计事件工作，完成毕业论文编写。 Ⅳ、主要参考资料： [1]叶刚.浅谈建筑工程的施工安全管理问题及对策[J].科技创新导报,2009, [2]全裕利.房屋建筑施工质量管理[J].湖南经济管理干部学院学报,2005. [3]党宏斌.浅论建筑施工安全管理的现状及努力方向[J].建筑安全,2007, 西南交通大学学院（系）土木工程专业类1103本科班学生龙浩 毕业设计（论文）时间：年月日至年月日答辩时间：年月日 成绩： 指导教师： 兼职教师或答疑教师（并指出所负责部分）： 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 西南交通大学网络教育 专升本交通运输专业教学计划（2012年秋季入学适用） 培养目标：本专业旨在培养适应经济全球化、信息化及交通运输行业发展需要，掌握信息技术、外语、管理学、经济学和交通运输专业的相关理论知识和专业技能，具有交通运输组织管理、规划设计和指挥决策能力，能在各级铁路运输管理部门及相关单位从事运输组织指挥和生产技术管理的高级应用型人才。 基本要求：具有一定的自然科学与社会科学基础知识，掌握运输组织与优化理论与方法、交通运输规划理论与设计方法、现代信息技术及其应用、经济与管理等知识，适应社会主义市场经济体制下交通运输行业发展的需求，具备交通运输组织管理、规划设计和指挥决策能力。 专业特色：本专业以“基础扎实、技术过硬、工作上手快、适应能力强”为特点，在学生综合素质培养的基础上，注重学生管理学、经济学、信息技术和外语应用能力的培养，尤其重视培养和训练学生扎实的交通运输专业基础和实践技能。 主干课程：管理运筹学A、交通运输系统分析、运输市场营销、交通运输设备、交通工程学、运输组织学。 学期课程名称课程代 码 学 分 考核形 式 课程性 质 是否为申 请 学位所需 课程 是否为核 心课程 第1学期大学英语III 000300 4 考试 公共基 础课 是计算机应用基础001300 4 考试 公共基 础课 是交通运输经济157800 4 考试专业课是毛泽东思想和中国特色 社会主义理论体系 001800 4 考查 公共基 础课 学习导航002000 2 考查 公共基 础课 专业概论（交通运输类）003000 1 考查 公共基 础课 小计19 第2学期大学英语IV 000400 4 考试 公共基 础课 是管理运筹学A 136401 5 考试 专业基 础课 是是交通运输系统分析158100 5 考试专业课是是运输市场营销204400 5 考试 专业基 础课 是是小计19 第3学期大学英语V 000500 4 考试 公共基 础课 是交通运输管理信息系统157600 4 考试 专业基 础课 是交通运输设备158000 5 考试 专业基 础课 是现代物流学A 197601 5 考试专业课 小计18 第4学期交通工程学156700 5 考试专业课 科技论文写作A 001400 2 考查 公共基 础课 运输商务204300 3 考试专业课是运输组织学204900 5 考试专业课是小计15 第5学期毕业设计（论文）103000 12 专业课毕业实习250900 1 专业课小计13 总计84 总课程数（门）20 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 第二次大作业 一、使用《中图分类法》中查找你所在专业的分类号，并使用图书馆的书目查询系统查找该分类下的一本图书，写出该书的书名、作者、出版社、出版年、索书号、馆藏复本数、馆藏地等信息。 《中图法》的标记符号采用汉语拼音字母与阿拉伯数字相结合的混合号码。即用一个字母表示一个大类，以字母的顺序反映大类的序列。字母后用数字表示大类以下类目的划分。数字的编号使用小数制。现将五个基本部类及下设的二十二个大类列表如下： 我所在的机械设计专业按中图分类法是：TH机械、仪表工业 ANSYS 10.0机械设计高级应用实例 王庆五;左昉;胡仁喜 北京:机械工业出版社,2006.1 书目号：484948 索书号：TH122 Z452-2 馆藏副本数：7 馆藏地犀浦馆基本藏书阅览室(501室),九里馆中文书库(202室),犀浦馆中文图书借阅室(301室) 二、用超星数字图书馆检索并打开与你所学专业相关的图书，并分别以图像和 文本两种形式采集该书的一段文字。 第一章推土机 第一节概述 一、用途 推土机是一种在履带式拖拉机或轮胎式牵引车的前面安装推土装置及操纵机构的自行式施工机械，主要用来开挖路堑、构筑路堤、回填基坑、铲除障碍、清除积雪、平整场地等，也可完成短距离松散物料的铲运和堆积作业。推土机配备松土器，可翻松级以上硬土、软石或凿裂层岩，以便铲运机和推土机进、行铲掘作业，也可利用推土机的铲刀直接顶推铲运机以增加铲运机的铲土能力（即所谓推土机助铲），还可协助平地机或铲运机完成施工作业，以提高这些机械的作业效率。推土机用途十分广泛，是铲土运输机械中最常用的作业机械之一，在土方施工中占有重要地位。但由于铲刀没有翼板，容量有限，在运土过程中会造成两侧的泄漏，故运距不宜太长，大型推土机的运否则会降低生产效率。通常中小型推土机的运距为距一般不应超，推土机过的经济运距为 三、使用CNKI期刊导航，查找你所在专业的2种核心期刊，写出刊名、主办 单位、ISSN号和CN号。 一、填空题（红色为2013-2014-2学期考试题） 1.计算机网络是现代通信技术和计算机技术密切结合的产物。 2.计算机网络的定义为一个互连的自主的计算机集合。 3.计算机网络按规模分为局域网，城域网，广域网。 按带宽分为窄带网和宽带网。 4.局域网的英文缩写为LAN，城域网的英文缩写为MAN，广域网的英文缩写为 WAN。 5.NAT将地址转换为全球唯一的IP，以便进入因特网。 6.在某层上进行通信所使用的规则的集合称为该层的协议。网络各层协议按层次顺序排列而 成的协议称为网络的协议栈。 7.对一个网络进行层次结构的划分时应做到：各层功能明确、相互独立；层间接口清晰、 穿越接口的信息量尽可能少。 8.两个最重要的网络参考模型是__OSI/RM（汉语解释）______模型和_TCP/IP_______。 9.OSI参考模型分为__7___层，从低到高依次是物理层、数据链路层、网络层、传输层、会话层、 表示层和应用层。 10.ISO的全称是___国际标准化组织______，在1984年正式颁布了一个称为__开放系统互联参 考模型___。该模型包含七个层次。 11.计算机网络采用___分层结构__。每层完成一定的___功能__，每层都向它的上层提供一定的 ____服务____，而将如何实现服务的细节对上层屏蔽，即低层协议对高层而言是透明的。相邻两层之间为___层间接口__。对等层用户通话时所必须遵守的规则称为___对等层协议____。 12.协议由_语义，语法，时序等三部分组成。 13.TCP/IP协议分为___4__层，从低到高依次是___网络接口层_______，___网间网层__ __， __传输层________，___应用层________________。 14.数据通信的几个主要指标有___信号传输速率、数据传输速率、信道容量、误码率。 15.RS-232C机械特性规定了使用一个__25_____芯或__9_____芯接头。 16.RS-232C机械特性规定了使用一个__25_____芯标准连接器，电气特性规定逻辑“1”的电平为 ___-15____至__5_____，即采用正负15V的__负_____逻辑电平。其中正负5V之间为__过渡区_____。不作任何定义。 17.数字信号模拟传输时，数字信号变成音频信号的过程称为____调制___。音频信号变成数字信 号的过程称为___解调____。 18.多路复用技术的几种形式：__TDMA_____、_FDMA______、__WDMA_____、_CDMA______。 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是 2014-2015学年第一学期《数据库原理》 课程实验报告 学号：20122617 学生姓名：徐玉松 班级：软件工程2012 教师：陶宏才 辅导老师：王泽洲赵红芳 2014年12月 实验一：表及约束的创建 1.1 实验目的与内容 目的：创建数据表、添加和删除列、实现所创建表的完整性约束。 内容：11-2、11-26~33。 注：实验内容编号均取自《数据库原理及设计（第2版）》第11章的实验！即：实验内容以第2版教材为准！ 报告：以11-31作为实验一的报告。 1.2 实验代码及结果 1.2.1 实验代码 create table person20122617 --创建新表 ( P_no char(6)primary key, P_name varchar(10)not null, Sex char(2)not null, Birthdate datetime null, Date_hired datetime not null, Deptname varchar(10)not null DEFAULT'培训部', P_boss char(6)null, constraint birth_hire_check --为约束创建一个名称 check(Birthdate Cust_name varchar(10)not null, Sex char(2)not null, BirthDate datetime null, City varchar(10)null, Discount Dec(4,2)not null, constraint Discount_check --检查约束的名称 check(Discount>=0.5 and Discount<=1 )--检查约束 ) --create rule d as @state between 0 and 1 --创建规则 --sp_bindrule d,'customer20122617.Discount' --这种方法也可以给Discount约束绑定规则create table orderdetail20122617 ( Order_no char(6)primary key, constraint Order_no_constraint CHeck(Order_no LIKE'[A-Z][A-Z][0-9][0-9][0-9][0-9]'), Cust_no char(6)not null, P_no char(6)not null, Order_total int not null, Order_date datetime not null, constraint person20122617_contr FOREIGN KEY(P_no)--定义外键为P_no REFERENCES person20122617(P_no)--外键参照主表person20122617中的P_no on delete NO Action --参照定义为不许删除数据结构线性表2答案
数据结构线性表实验报告
西南交通大学网络教育学院《大学英语IV》第1次网络作业
数据结构课后习题及答案
数据结构_实验1_线性表的基本操作
数据结构试题答案
西南交通大学本科毕业论文
数据结构实验一题目一线性表实验报告
西南交通大学网络教育-西南交通大学远程与继续教育学院
数据结构习题与答案
《数据结构》实验一 线性表及其应用
数据结构作业及答案
信息检索第二次大作业(西南交大,高凡图书馆长)
西南交通大学计算机网络考试复习(3学分)汇总
数据结构线性表答案
西南交通大学数据库原理实验课程设计报告书
- 数据结构课后习题答案第二章 线性表
- 数据结构第2章 线性表 教案
- 《数据结构及其应用》笔记含答案 第二章_线性表
- 数据结构第二章课后答案
- 数据结构第2章线性表习题及答案
- 数据结构练习题 第二章 线性表 习题及答案
- 数据结构第二章线性表
- 数据结构习题及答案与实验指导(线性表)2
- 《数据结构》第二章线性表习题与解答
- 数据结构线性表
- 第二章线性表
- 最新《数据结构》 第二章 线性表习题
- 数据结构练习第二章-线性表概述
- 第二章-线性表-自测题-自测题答案
- 数据结构第二章线性表习题
- 数据结构第二章线性表
- 数据结构第二章 线性表答案
- 数据结构第二章线性表.ppt
- 数据结构第二章线性表1答案
- 数据结构第二章线性表