要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共计40分）
1. 数据结构是指。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
2. 以下算法的时间复杂度为。
void fun(int n)
{ int i=1;
while (i<=n)
i++;
}
A. O(n)
B. O(n)
C. O(n log2n)
D. O(log2n)
3. 现要设计一个高效的算法，在一个长度为n的有序顺序表中删除所有元素值为x的元素（假设这样的元素是不唯一的），这样的算法时间复杂度为。
A. O(n)
B. O(n log2n)
C. O(n2)
D. O(n)
4. 在一个带头结点的循环双链表L中，要删除p所指结点，算法的时间复杂度为。
A. O(n)
B. O(n)
C. O(1)
D. O(n2)
5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针top为n，则以下元素x 进栈的正确操作是。
A.top++;s[top]=x;
B.s[top]=x;top++;
C.top--;s[top]=x;
D.s[top]=x;top--;
6. 中缀表达式“2*(3+4)-1”的后缀表达式是，其中#表示一个数值的结束。
A. 2#3#4#1#*+-
B. 2#3#4#+*1#-
C. 2#3#4#*+1#-
D. -+*2#3#4#1#
7. 设循环队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。
A. rear-front
B. rear-front-1
C. (rear-front)％N+1
D. (rear-front+N)％N
8. 若用一个大小为6的数组来实现循环队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 1和5
B. 2和4
C. 4和2
D. 5和1
9. 一棵高度为h（h≥1）的完全二叉树至少有个结点。
A. 2h-1
B. 2h
C. 2h+1
D. 2h-1+1
10. 一棵含有n个结点的线索二叉树中，其线索个数为。
A. 2n
B. n-1
C. n+1
D. n
11. 设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对个字符进行编码。
A. 999
B. 998
C. 1000
D. 1001
12. 一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是。
A. 对称矩阵
B. 非对称矩阵
C. 稀疏矩阵
D. 稠密矩阵
13. 设无向连通图有n个顶点e条边，若满足，则图中一定有回路。
A. e≥n
B. e C. e=n-1 D. 2e≥n 14. 对于AOE网的关键路径，以下叙述是正确的。 A. 任何一个关键活动提前完成，则整个工程一定会提前完成 B. 完成整个工程的最短时间是从源点到汇点的最短路径长度 C. 一个AOE网的关键路径一定是唯一的 D. 任何一个活动持续时间的改变可能会影响关键路径的改变 15. 设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是。 A. 25 B. 50 C. 10 D. 7 16. 在一棵m阶B-树中删除一个关键字会引起合并，则该结点原有个关键字。 A. 1 B. ?m/2? C. ?m/2?-1 D. ?m/2?+1 17. 哈希查找方法一般适用于情况下的查找。 A. 查找表为链表 B. 查找表为有序表 C. 关键字集合比地址集合大得多 D. 关键字集合与地址集合之间存在着某种对应关系。 18. 对含有n个元素的顺序表采用直接插入排序方法进行排序，在最好情况下算法的时间复杂度为。 A. O(n) B. O(n log2n) C. O(n2) D. O(n) 19. 用某种排序方法对数据序列{24,88,21,48,15,27,69,35,20}进行递增排序，元素序列 的变化情况如下： （1）{24,88,21,48,15,27,69,35,20} （2）{20,15,21,24,48,27,69,35,88} （3）{15,20,21,24,35,27,48,69,88} （4）{15,20,21,24,27,35,48,69,88} 则所采用的排序方法是。 A. 快速排序 B. 简单选择排序 C. 直接插入排序 D. 二路归并排序 20. 以下排序方法中，不需要进行关键字的比较。 A.快速排序 B.归并排序 C.基数排序 D.堆排序 二、问答题（共4小题，每小题10分，共计40分） 1. 如果一个含有n（n>1）个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构（所有链表均带有头结点），并简要说明理由。 （1）只有尾结点指针没有头结点指针的循环单链表 （2）只有尾结点指针没有头结点指针的非循环双链表 （3）只有头结点指针没有尾结点指针的循环双链表 （4）既有头结点指针也有尾结点指针的循环单链表 2. 对于图1所示的带权有向图，采用Dijkstra算法求从顶点0到其他顶点的最短路径，要求给出求解过程，包括每一步的S集合、dist和path数组元素。 图1 一个有向图 3. 有一棵二叉排序树按先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)。回答以下问题： （1）画出该二叉排序树。 （2）给出该二叉排序树的中序遍历序列。 （3）求在等概率下的查找成功和不成功情况下的平均查找长度。 4. 一个含有n个互不相同的整数的数组R[1..n]，其中所有元素是递减有序的，将其看成是一棵完全二叉树，该树构成一个大根堆吗？若不是，请给一个反例，若是，请说明理由。 三、算法设计题（每小题10分，共计20分） 1. 设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。 2. 假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点（假设这样的结点是唯一的）的双亲结点地址p，提示，根结点的双亲为NULL，若在b中未找到值为x的结点，p亦为NULL。 “数据结构”考试试题（A ）参考答案 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（每小题2分，共计40分） 1. D 2. A 3. A 4. C 5. C 6. B 7. D 8. B 9. A 10. C 11. C 12. A 13. A 14. D 15. D 16. C 17. D 18. A 19. A 20. C 二、问答题（共4小题，每小题10分，共计40分） 1. 答：本题答案为（3），因为实现上述4种运算的时间复杂度均为O(1)。 【评分说明】选择结果占4分，理由占6分。若结果错误，但对各操作时间复杂度作了分析，可给2～5分。 2. 答：该图对应的邻接矩阵如下： ??????? ?????????∞∞∞∞∞∞∞∞∞∞∞∞0730202102960 在求最短路径时，S （存放顶点集），dist[]（存放最短路径长度）和path[]（存放最短路径）的变化如下： S dist[] path[] {0} {0, 4} {0, 1 ,4} {0,1,2,4} {0,1,2,3,4} 最后得到的结果如下： 顶点0到顶点1的最短距离为5，最短路径为：0、4、1 顶点0到顶点2的最短距离为6，最短路径为：0、4、1、2 顶点0到顶点3的最短距离为7，最短路径为：0、4、1、3 顶点0到顶点4的最短距离为2，最短路径为：0、4。 3. 答：（1）先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)，中序序列是一个有序序列，所以为：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以构造出对应的二叉树，如图2所示。 （2）中序遍历序列为：2,5,6,8,10,12,15,16,18,20。 （3）ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。 ASL不成功=(5×3+6×4/11=39/11。 图2 【评分说明】（1）小题占6分，（2）（3）小题各占2分。 4. 该数组一定构成一个大根堆。 当R是递减时，其数组元素为k1、k2、…、k n，从中看出下标越大的元素值越小，对于任一元素k i，有k i>k2i，k i>k2i+1（i 【评分说明】回答是给5分，说明理由给5分。 三、算法设计题（每小题10分，共计20分） 1. 设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。 解：算法如下： void insertion(LinkList *A,LinkList *B,LinkList *&C) { LinkList *p=A->next,*q=B->next,*s,*t; C=(LinkList *)malloc(sizeof(LinkList)); t=C; while (p!=NULL && q!=NULL) { if (p->data==q->data) { s=(LinkList *)malloc(sizeof(LinkList)); s->data=p->data; t->next=s; t=s; p=p->next; q=q->next; } else if (p->data p=p->next; else q=q->next; } t->next=NULL; } 算法的时间复杂度为O(m+n)，空间复杂度为O(MIN(m,n))。 【评分说明】算法为8分，算法的时间复杂度和空间复杂度各占1分。 2. 假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p，提示，根结点的双亲为NULL，若未找到这样的结点，p亦为NULL。 解：算法如下： void findparent(BTNode *b,ElemType x,BTNode *&p) { if (b!=NULL) { if (b->data==x) p=NULL; else if (b->lchild!=NULL && b->lchild->data==x) p=b; else if (b->rchild!=NULL && b->rchild->data==x) p=b; else { findparent(b->lchild,x,p); if (p==NULL) findparent(b->rchild,x,p); } } else p=NULL; } 【评分说明】本题有多种解法，相应给分。 《小绿狼》绘本教案 教学目标： 1．通过教师读，学生参与故事，体验角色，让学生感知故事，走进故事。2．初步认识到做自己最幸福，认同自己、接纳自己、肯定自己。 3．借助图文并茂，以图为主的形式，培养孩子仔细阅读的习惯，激发阅读兴趣。 教学准备：绘本、课件 绘本解读： 这是一本教小读者找回自信、做回自己的励志图画书。故事的主角是一只自卑的绿色小狼。大家知道狼一般都是灰色的，当一只绿色的狼出现在一群大灰狼中时，会发生什么情况？被嘲笑？被驱逐？被排挤？……什么情况都可能发生，在《小绿狼》这本图画书中的那只绿狼，遭遇的还算是最轻的一种──被嘲笑。嘲笑虽无关性命，却涉及自信。在伙伴们的起哄声中，小绿狼发誓要改变自己：他想尽办法让自己变成灰色，却一次次失败。懂得魔法的小仙女也 数据结构》期末考试试题及答案 ( 2003-2004 学年第 2 学期 ) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 7．图的 Depth-First Search （DFS ） 遍历思想实际上是二叉树（ 法的推广。 （A ）、先序 （ B ）、中序 （C ）、后序 （D ）、层序 8．在下列链队列 Q 中，元素 a 出队的操作序列为（ p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9． Huffman 树的带权路径长度 WPL 等于（ c （ A ）、除根结点之外的所有结点权值之和1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 （ c ）。 （A ） 、正确性 （B ）. 可行性 （C ）. 健壮性 2．设 S 为 C 语言的语句 ,计算机执行下面算法时， for （i=n-1 ； i>=0 ； i--） for （j=0 ；j 1?在数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的（）阶段。 A需求分析 B概念设计 C逻辑设计 D物理设计 参考答案 B 数据库设计步骤： （1）规划（必要性、可行性，总目标） （2）需求分析（分析用户活动，产生业务流程图；确定系统范围，产生系统范围图；分析用户活动涉及的数据，产生数据流程图；分析系统数据，产生数据字典。）（3）概念设计（设计出独立于计算机硬件和DBMS的概念模式。E-R模型是主要设计工具） （4）逻辑结构设计（把概念设计阶段设计好的全局E-R模式转换成与选用的具体机器上的DBMS所支持的数据模型相符合的逻辑结构，包括数据库模式和外模式）（5）数据库的物理设计（对于给定的数据模型选取一个垠适合应用环境的物理结构的过程。数据库的物理结构主要指数据库的存储记录格式、存储记录安排和存取方法）（6）数据库的实现（建立实际数据库结构；装入试验数据对应用程序进行调试；装入实际数据，进入试运行状态） （7）数据库的运行与维护（维护数据库的安全性与完整性；监测并改善数据库运行性能; 根据用户要求对数据库现有功能进行扩充；及时改正运行中发现的系统错误） 2.关于数据库概念设计阶段的工作目标，下列说法错谋的是 A定义和描述应用系统涉及的信息结构和范围 B定义和描述应用系统中数据的属性特征和数据之间的联系 C描述应用系统的数据需求 D描述需要存储的记录及其数量 参考答案 3. SQL Server 2000的字符型系统数据类型主要包括（）。 A int、money、char B char> varchar、text C datetime、binary> int D char、varchar> int 参考答案 B 4. 具有联系的相关数据按一定的方式组织排列，并构成一定的结构，这种结构即（）。 A数据模型 B数据库 C关系模型 D数据库管理系统 参考答案 A 5. 在数据库系统中，下列哪个映像关系用于提供数据与应用程序间的逻辑独立性？ A外模式/模式 B模式/内模式 C外模式/内模式 D逻辑模式/内模式 参考答案 B 6. 关系模型的数据结构是 A树 B图 C表 D二维表 参考答案 D 7. 数据字典是数据库管理系统的重要组成部分，其中存储的各类信息通常由 A数据库管理员维护 B程序员维护 C数据库管理系统维护 D—般用户维护 参考答案 A 8. E-R图用于描述数据库的 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（每小题2分，共计40分） 1. 数据结构是指。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为。 void fun(int n) { int i=1; while (i<=n) i++; } A. O(n) B. O(n) C. O(n log2n) D. O(log2n) 3. 现要设计一个高效的算法，在一个长度为n的有序顺序表中删除所有元素值为x的元素（假设这样的元素是不唯一的），这样的算法时间复杂度为。 A. O(n) B. O(n log2n) C. O(n2) D. O(n) 4. 在一个带头结点的循环双链表L中，要删除p所指结点，算法的时间复杂度为。 A. O(n) B. O(n) C. O(1) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针top为n，则以下元素x进栈的正确操作是。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; D.s[top]=x;top--; 6. 中缀表达式“2*(3+4)-1”的后缀表达式是，其中#表示一个数值的结束。 A. 2#3#4#1#*+- B. 2#3#4#+*1#- C. 2#3#4#*+1#- D. -+*2#3#4#1# 7. 设循环队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 8. 若用一个大小为6的数组来实现循环队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。 2019数据库期末复习内容 1.选择题 （1）（数据库）是存储在计算机内结构化的数据的集合 （2）下述关于数据系统正确的描述是（数据库系统减少了数据冗余）。 （3）数据库（DB）、与数据库系统（DBS）和数据库管理系统（DBMS）之间的关系是（DBS 包含DB 和DBMS ）。（4）数据库管理系统的工作不包括（为定义的确据库提供操作系统）。 （5）用于对现实世界进行描述的工具是（数据模型）。 （6）在数据库的三级模式结构中，描述数据库中全局逻辑结构和特征的是（模式）。 （7）E-R图用来建立数据库的（概念模型）。 （8）下列模型中不能直接描述实体间多对多的联系的是（关系模型）。 （9）数据模型的三个要素是（数据结构、数据操作、完整性约束） （10）数据库的设计人员和用户之间沟通信息的桥梁是（实体联系图）。 （11）数据的独立性分为（逻辑独立性和物理独立性）。 （12）数据库通常是根据（数据模型）来分类的。 （13）关系数据库系统能实现专门的关系运算，包括（选择、投影、连接、除）。 （14）在关系模型中，下述关于关键字的说法正确的是（可以由一个或多个其值能唯一标识该关系模式中任何元组的属性组成）。 （15）被称为关系的两个不变性，由关系数据库系统自动支持的是（实体完整性和参照完整性）。 （16）在关系中不能出现相同元组的约束是通过（主码）来实现。 （17）下列数据模型中，数据独立性最高的是（关系模型）. （18）规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足：每一属性都是（不可分解的）。 （19）关系数据库规范化是为解决关系数据库中（插入异常、删除异常和数据冗余）问题而引入的。 （20）在关系数据库中，任何二元关系模式的最高范式必定是（BCNF ） （21）若属性X函数依赖于属性Y时，则属性X与属性Y之间的关系是（多对一）。 （22）设有关系模式：部门（部门代码，部门名称，部门成员，部门经理）由于其中（部门成员）属性存在，使该关系不属于第一范式。 （23）若关系模式R中的属性都是主属性，则R最高属于（3NF ）。 （24）若要彻底消除插入异常和删除异常，关系模式最低要属于（BCNF）。 （25）关系模式分解的无损连接和保持函数依赖两个特性之间的联系是（没有必然联系）。 （26）关系模式中数据依赖的存在，可能会导致成立蕴涵后者数据插入异常，这是指（该插入的数据未被插入）。（27）设要对关系模式R（学号，姓名，课程代码，课程名，课程成绩）进行分解，将其规范化到3NF，下列（B）是正确的规范化结果。B.R1（学号，姓名）R2（课程代码，课程名）R3 （学号，课程代码，课程成绩） （28）有如下关系R（是BCNF）。 （29）对用户访问数据库的权限加以限定是为了保护数据库的（安全性）。 （30）下面（可移植性）不是数据库系统必须提供的数据控制功能。 （31）数据库系统中，对存取权限定义为（授权）。 （32）在数据库的安全性控制中，为了保证用户只能存取他有权存取的数据，在授权的定义中，数据对象的（范围越小），授权子系统就越灵活。 （33）数据库安全性遭到破坏的情况属于（非法用户读取数据库中的数据）。 （34）数据库的（完整性）是指数据的正确性和相容性。 （35）数据完整性保护中的约束条件是指（值的约束和结构的约束）。 （36）实体完整性和参照完整性属于（静态关系约束）。 （37）数据类型、取值范围、空值约束属于（静态列级约束）。 一、单选题（每题 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的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.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 .没有共同点 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. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 数据结构期末考试题及答案 、选择题 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．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散 机考201601 数据库应用1. 项目文件的扩展名是（） A．.PJX 2. 在命令窗口中键入下面哪个命令并按回车，可以退出Visual FoxPro （）C．QUIT 3. 选择哪个菜单下的“工具栏”，可以打开工具栏对话框（） B. “显示” 4. 命令窗口被关闭后，将其重新打开的快捷键是（） D.〈Ctrl 〉+〈F2〉 5. 如果一个学生可以选修多门课程，而每门课程又可以被多个学生选修，则学生和课程之间联系属于（） C. 多对多联系 6. 要想将日期中的年份用4 位数字显示，应当使用的设置命令是（） A. SET CENTURY ON 7. 将“学生”表中所有学生的“入学成绩”加10 分，正确的命令是（） B. REPLACE ALL A学成绩WITH入学成绩+10 8. 设当前记录是第5 条，若要将记录指针指向第8 条记录，不能使用的命令是（） D. SKIP 8 9. 将“学生”表中1990 年出生的学生记录显示出来（“出生日期”字段为日期型），正确的命令是（） C. LIST FOR YEAR（出生日期）=1990 ) OPEN 10. Visual FoxPro 不支持SQL 的哪项功能（） D. 数据控制 11. 在命令窗口中输入并执行如下命令： X=275 Y= Z 二{^2010/05/28} M=.T. 内存变量X 、Y 、Z M 的数据类型分别是（） D . N 、 C 、 D 、 L 12. 顺序执行下列命令之后，“学生成绩”表在几号工作区（ DATABASES 学管理 USE 学生 SELECT 2 USE 课程 SELECT 0 USE 学生成绩 D . 3 13. 向数据库中添加自由表的命令是（ ） A. ADD TABLE 表名 14. 打开“教学管理”数据库的正确命令是（ ） D. OPEN DATABAS 教学管理 15. 在“数据工作期”窗口中可以（ ） 1. 下面程序段的执行次数为（A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225 13. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：( B )A. 2h B .2h-1 C. 2h+1 D. h+1 14. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ( D )A. acbed B .decab C. deabc D. cedba 15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确( A )A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的 二叉树的中序遍历序列相同 D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 ( A )A. 5 B .6 C. 7 D. 8 17. 顺序查找法适合于存储结构为( B )的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储 18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为( C )A. n B .n2 C. (n+1)2 D. (n-1)2 《数据结构与算法》（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 第 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 数据结构试题3 一、单项选择题（每小题3分，共30分） 1、假设有n个关键字，它们具有相同的Hash 函数值，用线性探测法把这n个 关键字存入到Hash地址空间中要做（）次探测。 A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2 2、若有一个栈的输入序列是1，2，3，…，n 输出序列的第一个元素是n，则 第i 个输出元素是（）。 A、n-i B、n-i-1 C、n-i+1 D、不确定 3、在一棵度为3的树中，度为3的结点数为2 个，度为2的结点数为1个， 度为1 的结点树为2个，那么度为0的结点数为（）。 A、4 B、5 C、6 D、7 4、在一个具有n个结点的无向完全图中，包含有（）条边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2 5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当 二分检索值为90的元素时，需（）次比较可检索成功。 A、1 B、2 C、3 D、4 6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（）。 A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序 7、已知8 个元素（34，76，45，18，36，54，92，65），按照依次插入结点的 方法生成一棵二叉排序树，该树的深度为（）。 A、4 B、5 C、6 D、7 8、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主存储，a00为第 一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为（）。 A、13 B、33 C、17 D、32 9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为 （）。 A、6 B、7 C、8 D、20 10、给定权的集合{15，3，14，2，6，9，16，17}，所构造出的哈夫曼树的带 权路径长度为（）。 A、129 B、219 C、189 D、229 二、判断题（认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分， 共１０分） 1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结 点进行查找任何一个元素。（） 2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树 的先序遍历中的最后一个结点。（） 3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空 间大小与图中结点的个数有关，而与图的边数无关。（） 4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突 的方法两个方面。（） 5、因为算法和程序没有区别，所以在数据结构中二者是通用的。（） 6、进栈操作push(x,s)作用于链接栈时，无须判满。（） 7、稳定排序算法是最好的。（） 第一章 一、单项选择题 1、文件系统与数据库系统相比较，其缺陷主要表现在数据联系弱、数据冗余和（C ） A、数据存储量低 B、处理速度慢 C、数据不一致 D、操作繁琐 2、数据的存储结构与数据逻辑结构之间的独立性成为数据的（B） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 3、在数据库系统中，对数据操作的最小单位是（B ） A、字节 B、数据项 C、记录 D、字符 4、数据的逻辑结构与用户视图之间的独立性称为数据的（C） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 5、下述各项中，属于数据库系统的特点的是（C） A、存储量大 B、存取速度快 C、数据共享 D、操作方便 6、在数据库系统中，模式/内模式映像用于解决数据的（B） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 7、在数据库系统中，模式/外模式映像用于解决数据的（C） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 8、数据库结构的描述，称为（D ） A、数据库模式 B、数据库 C、数据库管理系统 D、数据字典 9、数据库中全体数据的整体逻辑结构描述成为（D ） A、存储模式 B、内模式 C、外模式 D、概念模式 10、保证数据库中数据及语义的正确性和有效性，是数据库的（C） A、安全性 B、准确性 C、完整性 D、共享性 11、在数据库系统中，数据独立性是指（C） A、用户与计算机系统的独立性 B、数据库与计算机的独立性 C、数据与应用程序的独立性 D、用户与数据库的独立性 12、结构数据模型的三个组成部分是数据结构、数据操作和（C） A、数据安全型控制 B、数据一致性规则 C、数据完整性约束 D、数据处理逻辑 13、数据操纵语言（DML）的基本功能中，不包括的是( B ) A、插入新数据B描述数据库结构 C、数据库中数据排序 D、删除数据库中数据 14、控制数据库整体结构、负责数据库物理结构和逻辑结构的定义与修改人员是（ D ）《数据结构》期末考试试题及答案
中南大学数据库考试题库
数据结构考试题3
(完整版)大学数据库考试复习试题带答案
清华大学数据结构试题及答案
2017年数据结构期末考试题及答案A
《数据结构》期末考试题及答案
武汉大学数据结构考试题(附答案)
数据结构期末考试题及答案
数据结构考试试题
北京科技大学数据库考试题库
武汉大学数据结构考试试题(附答案) (2)
数据结构(c语言版)期末考试复习试题
数据结构期末考试试题A卷(完成,不知对不对)
数据结构试题3
(完整版)郑州大学数据库原理_期末考试试题
相关主题
文本预览