下载文档原格式
《Visual FoxPro》2019年秋季学期在线作业（三）试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
在以下各种说法中,正确的是( )
A.ZAP和PACK的功能相同
B.DELETE 、ZAP和PACK的功能各不相同
C.DELETE ALL和PACK的功能相同
D.DELETE ALL、PACK和ZAP的功能相同
[提示：通过学习课本知识，完成本题作答]
参考答案:D
2.在关系模型中,对关系的要求不包括( )
A.在同一关系中字段必须按顺序排列
B.在同一关系中不允许出现完全相同的记录
C.在同一关系中不允许出现完全相同的字段
D.关系必须规范化
[提示：通过学习课本知识，完成本题作答]
参考答案:A
3.在Visual FoxPro中,内存变量的类型是( )
A.赋值时决定的
B.由数据输入语句决定的。
一、单选题（每题 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 1B. 3 2 1C. 3 1 2D. 1 2 35. 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(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
数据结构课后习题答案第1章绪论一、基础知识题1.1 简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。
【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。
每一种计算机程序设计语言都定义有自己的数据类型。
“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。
而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。
数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。
数据结构在计算机中的表示称为物理结构，又称存储结构。
是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。
逻辑结构与计算机无关。
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
其中每一条指令表示一个或多个操作。
一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。
1.2数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。
（也可以分为集合、线性结构、树形结构和图形即网状结构）。
逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。
（2）逻辑结构与数据元素的相对位置无关。
（3）逻辑结构与所含数据元素的个数无关。
数据结构习题参考答案第一章答案一、填空题1．数据元素，数据项2． O(1)，O(n)，O(log 2n)，O(n 2)3．线性结构，非线性结构，顺序结构，链式结构4．无，一，无，一5．前驱，一，无，任意6．任意7． O(n 1/2)8.O(1)<o(2n<="") 第二章答案一、填空题1． n/2，(n-1)/2分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。
因此在等概率情况下，插入操作中元素的平均移动次数为∑+==-++=112)1(11)(n i ni n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。
因此在等概率情况下，删除操作中元素的平均移动次数为∑=-=-= n i n i n n n f 121)(1)(。
2．向后3．向前4．指针域5．一定，不一定6． O(n)7． O(n)8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。
9．前驱，后继10．O(n)二、填空题1． (1)2． (1)3． (4)4． (2)5． (2)6． (4)7． (4)8． (1)9． (4)10．(1)11．(2)12．(3)第三章参考答案一、填空题1．线性，任何，栈顶，队尾，队头2．先进后出（FILO ），队尾，队头，先进先出（FIFO ）3． top==0，top==m4． 235415．前一个位置，所在位置，m-1分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。
6． (rear+1)%m==front ，rear==front7． O(1)8．返回地址，返回地址二、选择题1.(3) 2.(3) 3.(3) 4. (2)5. (2)6. (3)7. (1)8. (4)因为：顺序循环队列中的元素个数=??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。
数据构造试题一、单项选择题1、在数据构造的讨论中把数据构造从逻辑上分为〔〕A 部构造与外部构造B 静态构造与动态构造C 线性构造与非线性构造D 紧凑构造与非紧凑构造。
2、采用线性链表表示一个向量时，要求占用的存储空间地址〔〕A 必须是连续的B 局部地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为〔〕。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，假设q结点是p结点的前驱结点，假设在q与p之间插入结点s，那么执行〔〕。
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个，采用〔〕方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做〔〕。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，那么存放该数组至少需要的存储字数是〔〕。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用〔〕。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，那么出队列顺序为〔〕。
10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front 和rear，那么当前队列中的元素个数是〔〕。
A( front - rear + 1) %m B ( rear - front + 1) %mC (front - rear + m) %mD ( rear - front + m) %m11、一个数组元素a[i]与〔〕的表示等价。
数据结构作业题及答案第一章绪论1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
数据：指能够被计算机识别、存储和加工处理的信息载体。
数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。
数据元素有时可以由若干数据项组成。
数据结构：指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
逻辑结构：指各数据元素之间的逻辑关系。
存储结构：就是数据的逻辑结构用计算机语言的实现。
线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构。
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
3、求解下列算法的时间复杂度(1)i=1;k=0 while(i<n){k=k+10*i;i++;}T(n)=n-1∴T(n)=O(n)这个函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;} while(i<n);T(n)=n∴T(n)=O(n)这也是线性阶递增的(3)i=1;j=0;while(i+j<=n) {if(i<j)j++; else i++;}T(n)=n/2∴T(n)=O(n)虽然时间函数是n/2,但其数量级仍是按线性阶递增的。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（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）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（ㄨ）（3）数据元素是数据的最小单位。
（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（7）数据的存储结构是数据的逻辑结构的存储映像。
（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。
（ㄨ）（9）数据的逻辑结构是依赖于计算机的。
（√）（10）算法是对解题方法和步骤的描述。
二．填空题（1）数据有逻辑结构和存储结构两种结构。
（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。
（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
（4）树形结构和图形结构合称为非线性结构。
（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。
（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。
（7）数据的存储结构又叫物理结构。
（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。
（9）线性结构中的元素之间存在一对一的关系。
（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。
（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。
（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。
（14）算法是一个有穷指令的集合。
（15）算法效率的度量可以分为事先估算法和事后统计法。
（16）一个算法的时间复杂性是算法输入规模的函数。
（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。
(单选题)1: 作为数据库管理系统(DBMS)功能的一部分,( )被用来描述数据及其联系。
A: 数据定义语言
B: 自含语言
C: 数据操作语言
D: 过程化语言
正确答案: C
(单选题)2: ?表文件已经打开,当前记录中姓名字段的值是“王小平”。
执行以下命令序列??姓名="李敏"??? 姓名?屏幕显示的结果是( )
A: 王小平
B: 李敏
C: 王小平李敏
D: 李敏王小平
正确答案: A
(单选题)3: 设A=[5*8+9],B=6*8,C=“6*8”,在下列表示形式中,只有( )是合法表达式。
A: A+B
B: B+C
C: A+C
D: C－B
正确答案: C
(单选题)4: 由计算机、操作系统、数据库管理系统、数据库、应用程序及用户组成的一个整体叫( )
A: 软件系统
B: 数据库系统
C: 管理系统
D: 文件系统
正确答案: B
(单选题)5: ( )是( )的具体表现形式,( )是( )有意义的表现。
A: 信息、数据、数据、信息
B: 数据库、信息、信息、数据库
C: 数据、信息、信息、数据
D: 数据、信息、数据库、信息
正确答案: C
(单选题)6: 在VFP环境下,用LIST STRU命令显示表中每个记录的长度(总计)为60,用户实际可用字段的总宽度为( )
A: 60
B: 61
C: 59
D: 58
正确答案: C。
《程序设计（C语言）》2019年秋季学期在线作业（三）
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.结构化程序设计方法中有三种基本控制结构，以下不正确的是
A.顺序结构
B.选择结构
C.数组结构
D.循环结构
答案:C
2.以下语句中无限循环语句是
A.while(1,2,3)
B.while(‘\0’)
C.for(;2&5;)
D.for(;’\0’;)
答案:A
3.若有：int a[10],*p=&a[0];，关于数组名a的不正确的说法是（）。
A.数组名a表示数组的首地址
B.数组名a与a[0]等价
C.a是个数组指针
D.a和p都指向同一个存储单元
答案:C
4.执行下面程序（）。
main()
{
int x=1,y=1,z=1;
x=x++ +y++ +z++;
printf("%d, %d , %d",x,++y,z++);
}
输出的结果为
A.4,3,2
B.3,3,3
C.3,3,2
D.3,2,2
答案:A
5.已定义以下函数
fun(int *p)
{ return *p; }
该函数的返回值是（）。
A.形参p的地址值
B.形参p所指存储单元中的值。
《数据结构》2020年秋季学期在线作业（二）试卷总分:100 得分:100一、单选题(共20 道试题,共100 分)1.下列判断正确的是（）。
A.二叉树是树的特例。
B.具有n个结点的完全二叉树的深度为n/2。
C.Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
D.栈和队列都是限制存取点的线性结构。
答案:D2.题目和答案如下图所示：{图}A.AB.BC.CD.D答案:A3.题目和答案如下图所示：{图}A.AB.BC.CD.D答案:D4.下列说法不正确的是（）。
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.图的深度遍历不适用于有向图C.遍历的基本算法有两种：深度遍历和广度遍历D.图的深度遍历是一个递归过程答案:B5.单链表中，增加头结点的目的是为了（）。
A.使单链表至少有一个结点B.标示表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储实现答案:C6.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) = （）。
A.（a）B.AC.(b)D.(A)答案:D7.下列哪一个关键码序列不符合堆的定义？（）。
A.(102，87，100，79，82，62，84，42，22，12，68)B.(102，100，87，84，82，79，68，62，42，22，12)C.(12，22，42，62，68，79，82，84，87，100，102)D.(102，87，42，79，82，62，68，100，84，12，22)答案:D8.用堆栈求算术表达式a+b*(c-d)-e/f的后缀表达式为（）。
A.abcd-*+ef/-B.a+b*(c-d)-e/fC.abcdef-*+/-D.abc-d*ef/+-答案:B9.题目和答案如下图所示：{图}A.AB.BC.CD.D答案:B10.关于算法，下面描述正确的是（）。
《计算机操作系统》2019年秋学期在线作业（二）
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.虚拟存储器的最大容量（）。
A.由计算机的地址结构决定
B.由作业的地址空间决定
C.是任意的
D.为内外存容量之和
[提示：通过学习课本知识，完成本题作答]
参考答案:A
2.下面关于操作系统的叙述中正确的是（）。
A.由于采用了分时技术，用户可以独占计算机的资源。
B.批外理作业必须具有作业控制信息
C.分时系统不一定都具有人机交互功能。
D.从响应时间的角度看，实时系统与分时系统差不多
[提示：通过学习课本知识，完成本题作答]
参考答案:B
3.分区管理中采用“首次适应”分配算法时，宜把空闲区按（）次序登记在空闲区表中。
A.长度递增。
第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，士1，士2,…}，字母字符数据对象是集合C={ ‘ A', ‘ B…，‘ Z，‘ a'b '，…，‘ z ' }，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2 •试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。
1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中 ，数据元素的①、数据信息在计算机中的② 的运算等的课程。
① A .操作对象 E.计算方法 C.逻辑结构 D.数据映象 ② A •存储结构 E.关系 C.运算 D.算法 2. 数据结构DS(Data Struct)可以被形式地定义为 DS= ( D, R ),其中D 是① _____________ 的有限集合，R 是D 上的② ______ 有限集 合。
① A .算法 E.数据元素 C.数据操作 D.数据对象 ② A .操作 E.映象 C.存储 D.关系 3. 在数据结构中，从逻辑上可以把数据结构分成 ____________ 。
A. 动态结构和静态结构 E.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4. 算法分析的目的是① _______ ，算法分析的两个主要方面是② ________ 。
①A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C.分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂性和时间复杂性B.正确性和简明性C. 可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是① ，它必具备输入、输出和②等五个特①A. 计算方法B.排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性while (s<n)数据结构练习题 习题1 绪论以及一组相关1.2 填空题 (将正确的答案填在相应的空中)1. 数据逻辑结构包括 _______ 、2. 在线性结构中，第一个结点 结点，其余每个结点有且只有 ______3. 在树形结构中，树根结点没有 和 _____ 前驱结点，其余每个结点有且只有 个后续结点。
______ 结点，其余每个结点有且只有 三种类型，树形结构和图形结构合称为 _________ 。
