《数据结构》期末考试试题及答案
贵州大学理学院数学系信息与计算科学专业
《数据结构》期末考试试题及答案
(2003-2004学年第2学期)
一、单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性(B). 可行性(C). 健壮性(D). 输入性
2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)
for(j=0；j (A)、n2(B). O(nlgn) (C). O(n) (D). O(n2) 3．折半查找法适用于（）。 （A）、有序顺序表（B）、有序单链表 （C）、有序顺序表和有序单链表都可以（D）、无限制 4．顺序存储结构的优势是（）。 （A）、利于插入操作（B）、利于删除操作 （C）、利于顺序访问（D）、利于随机访问 5．深度为k的完全二叉树，其叶子结点必在第（）层上。 （A）、k-1 （B）、k （C）、k-1和k （D）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、37 7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。 （A）、先序（B）、中序（C）、后序（D）、层序 8．在下列链队列Q中，元素a出队的操作序列为（） （ （B）、p=Q.front->next; Q.front->next=p->next; （C）、p=Q.rear->next; 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．逻辑结构决定了算法的，而存储结构决定了算法的。 2．栈和队列都是一种的线性表，栈的插入和删除只能在进行。3．线性表（a1,a2,…,a n）的顺序存储结构中，设每个单元的长度为L，元素a i 的存储地址LOC(a i)为 4．已知一双向链表如下(指针域名为next和prior)： 现将p所指的结点插入到x和y结点之间，其操作步骤为：； ；；； 5．n个结点无向完全图的的边数为， n个结点的生成树的边数为。 6．已知一有向无环图如下： 任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。 三、应用题 1．设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分) (1) 构造HASH表。 (2) 分别求查找成功和不成功时的平均查找长度。 2．给定表（19,14,22,15,20,21,56,10）.（8分） （1）按元素在表中的次序，建立一棵二叉排序树 （2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。 （3） 画出对(2)中的遍历序列进行折半查找过程的判定树。 3． 已知二个稀疏矩阵A 和B 的压缩存储三元组表如下： 写出A-B 压缩存储的三元组表。（5分） 4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n 个元素的插入排序的时间复杂度是多少？(5分) 5． 已知一网络的邻接矩阵如下，求从顶点A 开始的最小生成树。(8分，要有过程) A B C D E F （1）求从顶点A 开始的最小生成树。 （2）分别画出以A 为起点的DFS 生成树和BFS 生成树。 6把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。 （1） 画出对应的Huffman 树。 （2） 计算带权路径长度WPL 。 （3） 求A 、B 、C 、D 、E 、F 的Huffman 编码。 ??????? ?? ? ??????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞64266346751275356156F E D C B A 7． 已知有如下的有向网： 求顶点A 到其它各顶点的最短路径（采用Dijkstra 算法，要有过程）。（6分） 三、 设计题（30分，每题10分,用C 语言写出算法，做在答题纸 上） 1． 已知线性表（a 1,a 2,…,a n ）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 //顺序表初始分配容量 typedef struct { Elemtype *elem; //顺序存储空间基址 int length; //当前长度（存储元素个数） }SqList; 设计一个算法，删除其元素值为x 的结点（假若x 是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下： S tatus ListDelete(Sqlist &L,Elemtype x) { …… } 2．设顺序栈如左图所示。 其中结点定义如下： typedef struct { Elemtype *base; //栈底指针 Elemtype *top; //栈顶指针 }Stack; 设计算法，将栈顶元素出栈并存入e 中． base 3．设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node{ Elemtype data; struct node *lchild, *rchild; }BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法: S tatus CountLeaves(BinTree &root,int &n) {//n is the number of leaves …… } 答案： 选择题（每题1分） 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、填空题 1．设计、实现 2．特殊、栈顶 3．LOC（a1）+(i-1)*L 4．p->next=q->next;q->next->prior=p; q->next=p;p->prior=q; 5．n(n-1)/2、n-1 6．ADCBFEG、ABCDEFFG 7．ABC、ABC 二、应用题 （2）查找成功的平均查找长度：（1分） （5*1+1*2+2*3+1*7）/9=20/9 查找不成功的平均查找长度：（1分） （2+1+9+8+7+6+5+4+3+2+1）/13= 2（1）、构造（3分） (2)、10 14 15 19 20 21 22 56（2分） （3）、（3分） 3、(5分，每行 4、 初始关键字： [18] 12 25 53 18 第 一 趟：[12 18] 25 53 18 第 二 趟：[12 18 25] 53 18 第 三 趟：[12 18 第 四 趟：[12 18 18 （4分） O （n 2）（1分）。 5、7分 （1）4分 （2）4分 6、(1) 3分 A B 1 C 3 2 5 D 4 E F （2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分) （3）A ：010 B ：011 C ：110 D ：111 E ：00 F ；10 （3分） 12、A-B ：（A 、B ） 1分 A-C ：（A 、D 、C ） 2分 A-D ：（A 、D ） 1分 A-E ：（A 、D 、E ） 2分 三，设计题（20分） 1、(10分) Status ListDelete(Sqlist &L,ElemType x) { int i,j; for(i=0;i if(L->elem[i]==x) break; if(i=L->length) return ERROR; for(j=i;j 设元素个数记为n ，则平均时间复杂度为： ∑=-= -=n i n i n n E 12 1 )(1 2（10分） void pop(Stack &S,Elemtype &e) { if(S.top==S.base) return ERROR; S.top--; e=*s.top; } 2、（10分） voidCountLeaves(BinTree T,int &n) { if(T) { if((!(T->lchild)&&!( T->rchild)) n++; CountLeaves (T->lchild,n); CountLeaves (T->rchild,n); } } c语言期末测试题附答 案 集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN# 课程代码：A100002 座位号： 《计算机技术基础（C 语言）》试卷A 姓名: 学号: 专业: 学院: 班级: 20 年 月 日 第一 部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每题只有一个正确答 案，答对一题得 2 分，共 30 分） 1、以下关于C 语言标识符的描述中，正确的是 【 】。 A ）标 识符可以由汉字组成 B ）标识符只能以字母开头 C ）关键字可以作为用户标识符 D ）Area 与area 是不同的标识符 2、使下列程序段输出“123，456，78”，键盘输入数据，正确的输入是【 】。 int i,j,k; scanf(“%d,%3d%d”,&i,&j,&k); printf(“%d,%d,%d \n”,i,j,k); 3、判断char 类型的变量c1是否为数字字符的正确表达式为 【 】。 A) (c1>=0)&&(c1<=9) B) (c1>=’0’)&&(c1<=’9’) C) ’0’<=c1<=’9’ D) (c1>=’0’)||(c1<=’9’) 4、若有语句int a=1,b=2,c=3；则以下值为0的表达式是 【 】。 A ）’a’&&’b’ B ）a<=b C ）((a>b)||(b c期末考试试题及答案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 AutoCAD 试卷 一、 单项选择 1、AutoCAD 默认扩展名是 A 、dwt B 、dwg C 、bak D 、dxf 答案：B 2、在CAD 中，以下哪个命令可用来绘制横 平竖直的直线 A 、栅格 B 、捕捉 C 、正交 D 、对象捕捉答案：C 3、按哪个键可切换文本窗口和绘图窗口 A 、F2 B 、F8 C 、F3 D 、F5答案：A 4、默认情况下，命令提示行显示为几行 A 、3 B 、5 C 、2 D 、8答案：A 5、在CAD 中为一条直线制作平行线用什么命令 A 、移动 B 、镜像 C 、偏移 D 、旋转答案：C 6、在图层特性管理器中不可以设定哪项 A 、颜色 B 、页面设置 C 、线 宽 D 、是否打印答案：B 7、绘制建筑图步骤为 A 、墙线、轴线、门窗 B 、墙线、 门窗、轴线 C 、轴线、门窗、墙线 D 、轴线、 墙线、门窗答案：D 8、哪个命令可用于绘制直线与圆弧的复合 体 A 、圆弧 B 、构造线 C 、多段线 D 、样条曲线答案：C 9、如何在图中输入“直径”符号 A 、%%P B 、%%C C 、%%D D 、%%U 答案：B 10、如果要在一个圆的圆心写一个“A”字，应使用以下哪种对正方式 A、中间 B、对齐 C、中心 D、调整答案：A 11、在哪个层创建的块可在插入时与当前层特性一致 A、0层 B、在所有自动产生的层 C、所有图层 D、新建的图层答案：A 12、一个完整的尺寸由几部分组成 A、尺寸线、文本、箭头 B、尺寸线、尺寸界线、文本、标记 C、基线、尺寸界线、文本、箭头 D、尺寸线、尺寸界线、文本、箭头 答案：D 13、要将图形中的所有尺寸都为原有尺寸的2倍，应设定以下哪项A、文字高度 B、使用全局比例 C、测量单位比例 D、换算单位 答案：B 14、三维模型中哪种模型可以进行布尔运算 A、线框模型 B、实心体模型 C、表面体模型答案：B 15、渲染三维模型时，哪种类型可以渲染出物体的所有效果 A、一般渲染 B、普通渲染 C、照片级真实感渲染 D、照片级光线跟踪渲染答案：D 16、样板文件的括展名是 A、BAK B、SVS C、DWT D、DWG 答案：C 17、以下哪种相对坐标的输入方法是画8个单位的线长 A．8, 0 B．@0，8 C．@0<8 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 .没有共同点 C期末考试题及答案 Revised at 2 pm on December 25, 2020. 一、填空题（每空0.5分，共30分） 1、世界坐标系简称__WCS_用户自定义坐标系简称__UCS_。 2、工作空间的切换：“工具”/“工作空间”或“工作空间”工具栏。 3、工具栏包括30种，系统默认的显示工具栏包括：“标准”、“属性”、“绘图”和“修改”等工具栏。 4、多线的对正方式有_上（T）_、_无(Z)_和_下（B）_。 5、文字标注包括标注单行文字和标注多行文字。 6、渲染环境是指在渲染对象时进行的雾化和深度设置。 7、漫游和飞行用户可以通过键盘和鼠标来控制视图显示，并创建导航动画。 8、编辑实体的边的种类：压印边、复制边、着色边。 9、动态块是通过自定义夹点或自定义特性定义的块。在图形中使用动态块，用户可以随时对组成块的对象进行修改。 10、三维实体是具有体积、质量、重心、回转半径、惯性距等特征的三维对象。 11、在AutoCAD 2007中，用户可以创建的光源有电光源、聚光灯光源和平行光光源。 12、相切、相切、半径法是指：通过指定圆的两个切点和半径来绘制圆。 13、绘制圆环的步骤中，先输入圆环的内径和外径，后确定圆环的中心点。 14、计算机辅助设计是：工程技术人员在CAD系统的辅助下，根据产品的设计程序进行设计的一项新技术。 15、菜单栏包括11种，每一种菜单中都含有四种显示情况：命令后跟右三角 、后跟省略号、后跟快捷键或功能键或命令呈灰色。 16、要对图形对象进行编辑就必须选中图形对象，在AutoCAD 2007中，选择对象的方法很多，常用的有_直接拾取_、矩形框选择_、_不规则区域选择_和快速选择。 17、在设置显示精度时，如果设置的精度越高，即分辨率就越高，计算机计算的时间 也越长，显示图形的速度也就越慢。 18、三维基本实体的种类包括：多段体、长方体、楔体、圆柱体、圆锥体、球体、圆环体、棱锥面。 19、布尔运算中只留重复的一部分的运算是交集运算。从一个图形中去掉与另一个图形重复部分的运算是差集运算。 数据结构期末考试题及答案 、选择题 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 √ 2.× 3.√ 4.× 5. × 6. ×7. ×8. ×9.√10. ×二，选择 1. D 2. D 3. B 4. B 5. B 6. A 7. D 8. B 9. C 10. A 三填空 1. 测试计划、测试用例 2. 稳定性测试、负载测试、压力测试 3. 非增量是集成测试自顶向下增量式测试、自底向上增量式测试 4. 回归 5. 软件需求 四简答题（30分） 1.试描述软件测试的定义？（3分） 答：利用手工或者自动化的方式，按照测试方案对系统执行测试用例的过程叫做软件测试。 2.什么是软件缺陷？（4分） 答：满足以下条件的问题都叫缺陷： 软件未达到产品说明书中已标明的功能 软件出现了产品说明书中指明不会出现的错误 软件功能超出了产品说明书指明的范围 软件未达到产品说明书虽未指出但应达到的目标 软件测试员认为软件难以理解，不易使用，运行速度缓慢，或者最终用户认为该软件使用效果不好。 3.常见的黑盒测试用例的设计方法？并分别简单介绍一下各自的思想。（8分）答：等价类划分：等价类划分法是一种重要的、常用的黑盒测试方法，它将不能穷举的测试过程进行合理分类，从而保证设计出来的测试用例具有完整性和代表性。 边界值分析：对输入输出的边界值进行测试的一种黑盒测试方法。 决策表法：决策表是分析和表达多逻辑条件下执行不同操作的情况的工具 因果图分析法：是一种利用图解法分析输入的各种组合情况，从而设计测试用例的方法，它适合于检查程序输入条件的各种组合情况。 错误推测法：基于经验和直觉推测程序中所有可能存在的各种错误，从而有针对 性的设计测试用例的方法。 4. 列举常见的系统测试方法。答出来5个即可。（5分） 答：恢复测试 安全测试 强度测试 性能测试 正确性测试 可靠性测试 兼容性测试 Web测试 5.文档测试主要测试哪些内容？答出来5点即可（5分） 答：（1）检查产品说明书属性 （2）检查是否完整 （3）检查是否准确 （4）检查是否精确 （5）检查是否一致 （6）检查是否贴切 （7）检查是否合理 （8）检查代码无关 （9）检查可测试性 6. 单元测试主要测试那几方面的问题？（5分） 答：模块接口、局部数据结构、边界条件、独立的路径和错误处理。五，设计题 课程代码： A100002 《计算机技术基础( C 语言)》试卷 A 姓名: 学号: 专业 : 学院 : 班级 : 20 年 月 日 选择题(共 30 分) 题(本大题共 15 小题，每题只有一个正确答案，答 分，共 30 分) 1、以下关于 C 语言标识符的描述中，正确的是 【 】。 A) 标识符可以由汉字组成 B )标识符只能以字母开头 C )关键字可以作为用户标识符 D ) Area 与 area 是不同的标识符 2、使下列程序段输出“ 123， 456，78”，键盘输入数据，正确的输入是【 】 int i,j,k; scanf( “%d,%3d%”d ,&i,&j,&k); printf( “%d,%d,%dn ”,i,j,k); A ) 12345678 B )123，456， 78 C ) 123，45678 D ) 123，*45678 3、判断 char 类型的变量 c1 是否为数字字符的正确表达式为 【 】。 A) (c1>=0)&&(c1<=9) B) (c1>= '0')&&(c1<='9') C) '0'<=c1<='9' D) (c1>= '0')||(c1<= '9') 4、若有语句 int a=1,b=2,c=3 ；则以下值为 0 的表达式是 【 】。 A )' a '&&'b ' B )a<=b C )((a>b)||(b 计算机技术基础试题 第 2 页(共 10 页) A. *(a[0]+2) B. a[1][3] C . a[1][0] D. *(*(a+1)+2) 6、在循环语句的循环体中执行 break 语句，其作用是 【 】。 A )跳出该循 环体，提前结束循环 B) 继续执行 break 语句之后的循环体各语句 C) 结束本次循环，进行下次循环 D) 终止程序运行 7、执行语句 for(i=10;i>0;i--) ；后，变量 i 的值为 【 】。 A ) 10 B )9 C )0 D )1 8、若有 int *p1, *p2， k; 不正确的语句是 【 】 A. p1=&k B. p2=p1 C. *p1=k+12 D. k=p1+p2 9、在函数中未指定存储类别的局部变量，其隐含的存储类别是 【 】 A. 静态( static ) B. 外部( extern ) C. 自动( auto ) Ｄ . 寄存器( register ) 10、如下程序的输出结果是 【 】 main( ) { int x=2,a=0,b=0; switch(x) { case 2: a++; b++; case 1: ++a; b--; break; case 0: b++;} printf("a=%d, b=%d\n", a, b);} A. a=2, b=0 B. a=2, b=1 C. a=1, b=1 D. a=1, b=0 11、表示关系 a 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.算法分析是计算机科学的基础 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指数函数增长> 幂函数增长> 对数函数增长 数据库期末考试试题 ━━━━━━━━━━━━━━━ 一、填空共30题（共计30分） ━━━━━━━━━━━━━━━ 第1题（分）题号:2385 ORDER BY 子句实现的是【1】. 答案： =======(答案1)======= 排序 第2题（分）题号:2374 如果列上有约束,要删除该列,应先删除【1】 答案： =======(答案1)======= 相应的约束 第3题（分）题号:2394 在每次访问视图时,视图都是从【1】中提取所包含的行和列. 答案： =======(答案1)======= 基表 第4题（分）题号:2372 1.在增加数据文件时,如果用户没有指明文件组,则系统将该数据文件增加到【1】文件组.答案： =======(答案1)======= 主 第5题（分）题号:2371 查看XSCJ数据库信息的存储过程命令是【1】 答案： =======(答案1)======= sp_helpdb 第6题（分）题号:2392 创建视图定义的T-SQL语句的系统存储过程是【1】. 答案： =======(答案1)======= sp_helptext 第7题（分）题号:2379 1.表的外键约束实现的是数据的【1】完整性. 答案： =======(答案1)======= 参照 第8题（分）题号:2390 要进行模糊匹配查询,需要使用【1】关键字来设置查询条件. 答案： =======(答案1)======= LIKE 第9题（分）题号:2380 定义标识列的关键字是【1】. 答案： =======(答案1)======= identity 第10题（分）题号:2383 在进行多表查询是,必须设置【1】条件. 答案： =======(答案1)======= 连接 第11题（分）题号:2363 联系两个表的关键字称为【1】 答案： =======(答案1)======= 外键 第12题（分）题号:2382 用【1】字句可以实现选择行的运算. 答案： C语言程序设计 期末考试试题及其答案 一、单项选择题（本大题共20题，每题2 分，共40分） 1、以下不是C语言的特点的是( ) A、C语言简洁、紧凑 B、能够编制出功能复杂的程序 C、C语言可以直接对硬件进行操作 D、C语言移植性好 2、以下不正确的C语言标识符是( ) A、ABC B、abc C、a_bc D、ab.c 3、一个C语言程序是由( ) A、一个主程序和若干子程序组成 B、函数组成 C、若干过程组成 D、若干子程序组成 4、一个算法应该具有“确定性”等5个特性，对另外4个特性的描述中错误的是( ) A、有零个或多个输入 B、有零个或多个输出 C、有穷性 D、可行性 5、设变量a是整型，f是实型，i是双精度型，则表达式10+‘a’+i*f值的数据类型为( ) A、int B、float C、double D、不确定 6、在C语言中，char型数据在内存中的存储形式是( ) A、补码 B、反码 C、源码 D、ASCII码 7、有如下程序，输入数据：12345M678＜cR＞后（ #include 诚信应考 考出水平 考出风格 浙江大学城市学院 2013 — 2014 学年第 一 学期期末考试试卷 《 数据结构基础 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 1 月 14 日； 所需时间： 120 分钟 一．选择题 (本大题共 18 题，每题 1 分，共 18 分) 1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述 2. 中任何两个结点之间都没有逻辑关系。 A. 树形结构 B. 集合 C. 图形结构 D. 线性结构 3. 下面的程序段违反了算法的 原则。 void fun() { int x=2; while (!(x%2)) x=x*2; printf(“%d ”,x); } A. 健壮性 B. 确定性 C. 可行性 D. 有穷性 4. 算法分析的两个主要方面是 。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 用数组表示线性表的优点是。 A. 便于插入和删除操作 B. 便于随机存取 C. 可以动态地分配存储空间 D. 不需要占用一片相邻的存储空间 6. 循环链表的主要优点是。 A. 节约存储空间 B. 已知某个结点的位置后，能够很容易找到它的直接前驱 C. 在进行插入、删除运算时，能更好的保证链表不断开 D. 从表中的任意结点出发都能访问到任何一个结点 7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是。 A. 可以加快对表的遍历 B. 节省存储空间 C. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度 8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==h，则。 A. p指向头结点 B. p指向尾结点 C. *p的直接后继是头结点 D. *p的直接后继是尾结点 9. 线性表中，只有直接前驱而无后继的元素是。 A. 首元素 B. 尾元素 C. 中间元素 D. 全部元素 10. 以下不是栈的基本运算的是。 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈 11. 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为1和4。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为。 A. 3和5 B. 2和0 C. 0和2 D. 5和3 12. 最不适合用作链队的链表是_____。 A. 只带队头指针的非循环双链表 B. 只带队头指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表 13. 最不适合用作栈的链表是。 A. 只有表头指针没有表尾指针的循环双链表 B. 只有表尾指针没有表头指针的循环双链表 C. 只有表尾指针没有表头指针的循环单链表 D. 只有表头指针没有表尾指针的循环单链表 14. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率。 A. 高 B. 低 C. 相同 D. 无法确定 一、选择题（每题1分，共20分） 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是（ A ）阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2．数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为（D）。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3．数据库的概念模型独立于（A）。 A.具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4．数据库中，数据的物理独立性是指（C）。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5．关系模式的任何属性（A）。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6．下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字： 职工（职工号，职工名，部门号，职务，工资） 设备（设备号，职工号，设备名，数量） 两个关系的属性中，存在一个外关键字为（ C ）。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7．以下四个叙述中，哪一个不是对关系模式进行规X化的主要目的（ C ）。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8．关系模式中各级X式之间的关系为（ A ）。 A. B. C. D. 9．保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指数据的（ A ）。 A. 安全性 B.完整性 C.并发控制 D.恢复 10．事务的原子性是指（ B ）。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11．下列哪些运算是关系代数的基本运算（ D ）。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 C++期末考试试卷及答案1 一、单项选择题（每题2分，共40分） 1. ______不是属于面向对象程序设计的特性 A. 抽象性 B. 数据相关性 C. 多态性 D. 继承性 2. 将对某一类数据的处理算法应用到另一类数据的处理中,要用到C++的______ A. 类 B. 虚函数 C. 运算符重载 D. 模板 3. C++与C语言最根本的不同之处在于_______ A. 使用了类 B. 能够实现变量自动初始化 C. 支持软件重用 D. 支持接口重用 4. 动态内存分配的主要目的是_______ A. 使程序按动态联编方式运行 B. 正确合理的使用内存 C. 提高程序的运行速度 D. 提高程序的可维护性 5. 在C++函数的形参前加const关键字,是为了提高函数的_______ A. 数据封装性 B. 可理解性 C. 可维护性 D. 可重用性 6. 函数重载的目的是________ A. 实现共享 B. 使用方便，提高可读性 C. 提高速度 D. 减少空间 7. 从程序片断：char name[] = "C++"; course(name);可判断函数course的调用采用的是_______ A. 传值调用 B. 带缺省参数值的函数调用 C. 引用调用 D. 传址调用 8. 用来说明类中公有成员的关键字是________ 9. 如果一个类的成员函数print()不修改类的数据成员值，则应将其声明为 A. void print() const; B. const void print(); C. void const print(); D. void print(const); 10. 下列关于构造函数的论述中,不正确的是_______ A. 构造函数的函数名与类名相同 B. 构造函数可以设置默认参数 C. 构造函数的返回类型缺省为int型 D. 构造函数可以重载 11. 在程序代码：A::A(int a, int *b) { this->x = a; this->y = b; }中，this的类型是______ A. int B. int * C. A D. A * 12. 内存泄漏是指_______ A. 内存中的数据出现丢失 B.试图释放一个已经释放了的动态分配的堆内存 C. 函数中局部变量所占的栈内存没有及时回收 D. 动态分配的堆内存在程序退出后始终被占用 A. 私有成员数据 B. 私有成员函数 C. 公有成员数据 D. 公有成员函数 14. 友元函数_______ A. 可以被声明为const B. 没有this指针 C. 可以用类名或对象名来调用 D. 只能用对象名来调用 15. 若一个类的成员函数前用static关键字修饰，则该成员函数________ A. 可以被声明为const B. 没有this指针 C. 可以访问该类的所有成员 D. 只能用对象名来调用 16. C++是用_______实现接口重用的 广东创新科技职业学院期末考试试题（标明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 宁夏大学期末考试试卷 2006至2007学年第 一 学期 考试科目 算法与数据结构 学分 学院 数计学院 年级 二年级 专业 软件工程 任课教师 肖军 试题来源 一、填空题（每空1分，计15分） 1、数据的存储结构是数据在计算机存储器里的表示，主要有四种基本存 储方法： 、 、散列和索引。 2、将下列复杂度由小到大重新排序，结果是 。 2n n! n 5 100000 n*log 2(n) 3、栈下溢是指在____________时进行出栈操作。 4、已知substr(s,i,len)函数的功能是返回串s 中第i 个字符开始长度为len 的子串，strlen(s)函数的功能是返回串s 的长度。若s=″ABCDEFGHIJK ″,t=″ABCD ″,执行运算substr(s,strlen(t), strlen(t))后的返回值为 。 5、在有向图中，以顶点v 为终点的边的数目称为v 的 。 6、产生冲突现象的两个关键字称为该散列函数的 。 7、在有 n 个叶子结点的哈夫曼树中，总结点数是_______ 。 8、在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中， 堆顶结点的值是所有结点中的 。 9、在线性表的散列存储中，处理冲突有 和 两种方法。 10、在一棵树中， 结点没有前驱结点。 11、已经一棵完全二叉树中共有653个结点，则该树中共有 个分支结点。 12、一种抽象数据类型包括数据类型定义和 两个部分。 二、选择题（每题2分，计30分） 1、栈和队列的共同点是（ ）。 A 、都是先进后出 B 、都是先进先出 C 、只容许在端点处插入和删除元素 D 、没有共同点 2、已知二叉树后根周游序列是DABEC ，中根周游序列是DEBAC ，它的先根周游序列是（ ） 题号 一 二 三 四 五 六 七 八 九 总分 得分 评阅人 学号 姓名 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 毛概期末考试试题 项选择题<每题1分，共15分）1、全面贯彻“三个代表”重要思想的关键在 D、把我国建设成为富强、民主、文明的社会主义现代化国家7、我国的工业化任务还没有完成，总体上看，现在还处于< C） A、农业社会 B、现代化工业社会 C、工业化中期阶段 D、工业化高级阶段 8、实现全面建设小康社会的目标重点和难点在< D） A、大城市 B、中等城市 C、小城镇 D、农村 9、实行以家庭承包经营为基础、统分结合的双层经营体制，是党在农村的基本政策，必须长期坚持。稳定和完善这一双层经营体制的关键和核心是c语言期末测试题附答案
c期末考试试题及答案完整版
2017年数据结构期末考试题及答案A
C期末考试题及答案
数据结构期末考试题及答案
最新软件测试期末考试试题及答案
c语言期末测试题(附答案)
《数据结构》期末考试题及答案
数据结构复习资料,java数据结构期末考试
数据库期末考试试题及答案
C语言程序设计期末考试试题(含答案)
数据结构期末考卷13-14
数据库期末考试试题及答案
C期末考试试卷及答案
《数据结构》期末考试试卷
2006学年数据结构期末考试试卷
数据结构期末考试试题及答案
2018毛概期末考试试题及答案
- 数据结构期末考试试题
- 数据结构期末考试试题及答案
- (word完整版)2017年数据结构期末考试题及答案A,推荐文档
- 数据结构c语言版期末考试复习试题
- 《数据结构》期末考试卷-b卷
- (完整版)数据结构期末考试试题及答案
- 数据结构期末测试题及答案
- 数据结构复习资料java数据结构期末考试
- 《数据结构》期末考试试卷
- 数据结构期末考试试题及答案
- 大学数据结构期末考试试题(有答案)
- 《数据结构》期末考试试题及答案
- 数据结构(C语言版)期末考试复习试题
- 2017年数据结构期末考试题及答案A
- 数据结构期末考试试题A答案
- 数据结构期末考试复习总结
- 数据结构与算法期末练习题(含答案)
- 大学数据结构期末考试试题(有答案)
- 数据结构期末考试试题及复习资料
- 《数据结构》期末考试题及答案