下载文档原格式
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）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. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
课程测试试题（卷）----------------------以下为教师填写--------------------I、命题院（部）：数学与计算机科学学院II、课程名称：数据结构III、测试学期：20 －20 学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、选择题（20分）1．组成数据的基本单位是（）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。
(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。
(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。
(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。
(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。
(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若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 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。
2005级数据结构试题A卷注：回答问题，请在答题卡上回答，不要回答在试题上。
一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代24分）（1）线性表的逻辑顺序与物理顺序总是一致的。
（2）线性表的顺序存储表示优于链式存储表示。
（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
（4）二维数组是其数组元素为线性表的线性表。
（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。
(6 ) 二叉树必须有父结点、但不一定有左孩子结点或是右孩子结点。
（7）用n个结点构造Huffman树，这个树有2n个结点。
（8）有n个顶点的有向图，各个顶点完全连通则有n-1条边。
（9）拓扑排序的有向图，要求图入度为0的顶点只能有一个。
（10）在二叉排序树上查找，其效率总是高于顺序表上查找。
（11）归并排序是稳定排序且时间复杂度为O(nLogn)。
（12）Floyd最短路计算需要深度遍历图、且仅仅适合于有向图。
二，选择判断（每个题目仅有一个答案30分）1．算法指的是A．计算机程序 B．解决问题的计算方法C．排序算法 D．解决问题的有限运算序列2．关于以下图问题的计算，使用深度编历算法的是：A．Dijkstra最短路B．拓扑排序C．关键路径计算D．Prim最小生成树3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为A．O（1） B．O（n） C．O（m） D．O（m+n）4．哈希表查找中，填充因子和查找效率的关系是：A．填充因子越大、查找效率越好B．填充因子越小、查找效率越好C．填充因子要根据查找对象计算D．填充因子和查找效率没直接关系5．图的拓扑排序中，主要使用了哪种数据结构存储来暂存顶点?A．顺序表 B．栈C．队列 D．数组6．如下陈述中正确的是A．串是一种特殊的线性表 B．串的长度必须大于零C．串中元素只能是字母 D．空串就是空白串7．图的顶点个数是n，深度遍历该图，时间复杂度是：A．O（1） B．O（n） C．O（n2） D．O（n3）8、有数组char A[3][3][3]，按行存放于一个连续的存储空间中,如A[0][0][0] 存储地址是200（10进制），则它的数组元素A[1][1][2]在内存中的位置是：A．212 B．211 C．214 D．2159．对一个单向链表，下列程序段中，p指针类型为：struct Node {int X;struct Node *next;}如p开始指向链表头结点，最后p一定指向尾结点的是：A．while(p!=NULL) p=p->next;B．while(p!=NULL) p++；C．while(p->next!=NULL) p++;D．while(p++ ->next!=NULL);10．索引文件通常由索引表和主文件两部分构成，其中A．索引表和主文件均必须是有序文件B．索引表和主文件均可以是无序文件C．索引表必须是有序文件D．主文件必须是有序文件11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为A．e B．2*e C．n2－e D．n2－2*e12．假设一个有n个顶点和e条弧的有向图用邻接矩阵表示,则删除与某个顶点Vi相关的所有弧的时间复杂度是A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．对n个不同值元素的集合，找到最大/最小元的算法，应该进行多少种比较?A．n B．n-1 C．n2 D．n2-115．下列排序方法中，属于不稳定的排序方法是A．直接插入排序法B．快速排序法C．冒泡排序法D．希尔排序法三、计算、简答题(28分)1 有二叉树，先序遍历结果EBADCFHGIKJ，中序遍历结果为ABCDEFGHIJK，则后序遍历结果是什么？2 有数字序列（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵A VL树，对该树插入完成后，给出该树的后序遍历结果。
全国2005年10月高等教育自学考试全国统一命题考试数据结构试题课程代码：2331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上【】A. 操作的有限集合B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为【】A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是【】A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是【】A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是【】A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是【】A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为【】第 1 页共12 页A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为【】A. 429B. 432C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是【】A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是【】11. n个顶点的强连通图中至少含有【】A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为【】A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为【】第 2 页共12 页A. 4B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树【】A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是【】A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。
浙江工商大学2006/2007学年第一学期考试试卷课程名称：《数据结构》考试方式：闭卷完成时限：120分钟班级名称：学号：姓名：题号一二三四五六总分分值10 10 10 14 20 36 100得分阅卷人一.判断题（每题1分，共10分）1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。
................................()2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构相关，是依赖于计算机的。
................................()3、线性表中的每个结点最多只有一个直接前驱和一个直接后继。
..................................................()4、线性的数据结构可以顺序存储，也可以链接存储。
非线性的数据结构只能链接存储。
........................................()5、二维数组是其数组元素为线性表的线性表。
................()6、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。
..................................()7、由一棵二叉树的前序序列和后序序列可以唯一确定它。
......(错)8、在数据的存放无规律而言的线性表中进行查找的最佳方法是顺序查找（线性查找）。
......................................()9、多重表文件和倒排文件都归属于多关键字文件。
............()10、不定长文件是指文件的长度不固定。
..................... ()二.填空题（每题1分，共10分）1、若将数据结构形式定义为二元组(D，R)，其中D是数据元素的有限集合，则R是D上关系的有限集合。
2、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为。
华南农业大学期末考试试卷（A卷）2005年度第2学期考试科目：数据库原理及应用考试类型：闭卷考试时间：120分钟班级学号姓名（√）1. 数据模型是面向数据库全局逻辑结构的描述，它包含以下几个方面的内容：数据表示、数据操作和数据约束条件。
（×）2. 数据库系统的三级模式结构中，内模式又称为逻辑模式，是数据库中全体数据的逻辑表示。
（√）3. 在一个关系中，每一横行称为一个元组。
（×）4. 一个关系模式中，可以有多个候选码，由于主码是在候选码中产生的，所以主码也可以有多个。
（×）5. 关系模型的参照完整性是指关系中的主键不能是空值且不能有相同值。
（√）6. 关系模式的分解应该符合“无损连接”和“保持依赖”的原则。
（√）7. 关系的集合运算中，R⋂S＝S－(S－R)。
（×）8. Access数据库中，用％表示任意一个字符，用_表示任意多个字符。
（×）9. Access数据库中，默认的数字型字段的数据类型为整型。
（√）10. 数据库应用系统的开发过程可以描述为以下几个阶段：系统分析、系统设计、系统实施以及系统维护。
二. 简答题（每题10分，共40分）1. 试描述数据处理过程中，数据管理技术发展的各个阶段的特点。
答：（1）人工管理阶段：数据不保存；应用程序与数据之间缺少独立性；数据不能共享。
（2）文件系统阶段：数据长期保存；应用程序与数据之间有了一定的独立性；数据文件形式多样化；数据文件不再只属于一个应用程序；仍有一定的数据冗余；数据的不一致性。
（3）数据库系统阶段：数据整体结构化；数据共享性高；具有很高的数据独立性；完备的数据控制功能。
2. Access数据库系统中，以下表达式中常用的计算符号分别有什么功能？/ ，^ ，& ，or ，?答：（1）“/”：两个字段或常量的商（2）“^”：求一个字段的值或常量的多少次方（3）“&”：用来强制两个表达式进行字符串连接（4）“or”：满足两个条件之一时即为真（5）“?”：仅替代一个字符3. 什么是关系模型的完整性约束，关系模型中提供了哪几种完整性约束，分别描述之。
东莞理工学院（本科）试卷（A 卷）2006 -2007 学年第二学期开课单位：软件学院，考试形式：闭卷，允许带入场科目：数据结构与算法分析班级：姓名：学号：一、填空题（每小题2分，共18分）1、对于给定的n个元素,可以构造出的逻辑结构有集合, ，和四种。
2、数据结构中评价算法的两个重要指标是和。
3、数据类型指的是和定义在的总称。
4、顺序存储结构是通过表示数据元素之间的(逻辑)关系；链式存储结构是通过表示数据元素之间的(逻辑)关系。
5、栈是的线性表，其操作数据的基本原则是。
6、设有一个二维数组A[0…9][0…9]，若每个元素占3个基本存储单元，A[0][0]的地址是600，若按行优先（以行为主）顺序存储，则A[6][8]的存储地址是。
7、树的先序遍历实质上与将树转换成二叉树后对二叉树的相同；而树的后序遍历实质上与将树转换成二叉树后对二叉树的相同。
8、若采用邻接矩阵存储一个图所需要的存储单元取决于图的；无向图的邻接矩阵一定是。
9、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。
二、单项选择题（请将答案写在题目后的括号中。
每题2分，共18分）1、有算法sum(n)，其时间复杂度是（ A ）。
sum( int n ){ int sum=0, m, t ;for (m=1; m<=n; m++){ p=1 ;for (t=1; t<=m; t++) p*=t ;sum+=p ;}return (sum) ;}（A）O(n2) （B）O(m2) （C）O(m+n) （D）O(n×m)2、设p是非空单链表中结点q的直接前驱结点，删除q的正确操作是（ B ）。
（A）p->next=q->next；free(p) ; （B）p->next= q->next；free(q) ;（C）q->next=p->next；free(p) ; （D）q->next=p->next；free(q) ;3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ D ）。
阜阳师范学院…………….……………..装……………………订………………..线…………….……………..计算机 题 得 系 号 分 05 专升本,03 职 一 班级 二 数据结构 三 课程2005四——五 六2006七学 年 度 第 二 学 期 考 试 卷 (A)份, 八 年 月 九 日 十 — 考试，任课教师 范、王 拟题 十一 十二 总 分 软件教研室 备 注期末 考试，共 2 页，第 1 页，共印刷学号阅卷教师签名 一、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入 题干的括号内，多选不给分，每小题 3 分，共 30 分） 1. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ C．head→link==head ） 2. 二、填空题（每题 2 分，共 10 分）1.某线性表采用顺序存储结构,每个元素占据 2 个字节,首地址为 100,则下标为 11 的(第 12 个)元 素的存储地址为 采用左右指针法存储 N 个结点的二叉树,该二叉树中共有 针 个. 个指针域, 其中非空指A．head==NULL B．head→link==NULL 2. 对于栈操作数据的原则是（ A. 先进先出 B. 后进后出 ） 。
D．head!=NULL姓名C.后进先出D. 不分顺序3. 4.如果树中某结点 A 有 3 个兄弟，而且 B 是 A 的双亲，则 B 的度是_ ____ 在一个长度为 n 的顺序表中第 i 个元素 （1<=i<=n） 之前插入一个元素时， 需向后移动_ _______ 个元素。
二分法检索有序表（4，6，12，20，28，38，50，70，88，100） ，若检索表中元素 20，它将依 次与表中元素 比较大小。
3. 具有 10 个叶结点的二叉树中有（ A．8 B．9 C．10）个度为 2 的结点. D．ll ). D．中序序列班4. 树的后根遍历序列等同于该树对应的二叉树的( A. 先序序列 B.层次序列 C. 后序序列5.5. 对 N 个元素的表做顺序检索时，若检索每个元素的概率相同（不考虑失败的情况下） ，则平 三、判断题（下列各题，你认为正确的，请在后面的括号内打√，错误的打×。
东莞理工学院（本科）试卷（B卷）参考答案及评分标准2007--2008学年第2学期《数据库系统原理II》试卷开课单位：软件学院，考试形式：闭卷'、选择题（共40分每题2分）1. D 2 . C 3 . B 4 . B 5 . C6. C 7 . D 8 . C9 . C10 . C11 . B 12 . D 13 . C14.D15 . D16 . A 17 . B 18 . A19.B20 . A—- 、、填空题（共10分每题1分）21逻辑22.可串行性23 •关系模型24. 用户定义完整性25. 丢失修改26. 介质故障27•实体联系模型（ER模型）28. 自主存取控制29. 数据加密30. 隔离性三、简答题（共15分每题5分）31. 简述利用日志文件恢复事务的过程。
答：系统恢复的步骤为1）反向扫描文件日志即从最后向前扫描日志文件，查找该事务的更新操作2）对该事务的更新操作执行逆操作。
即将日志记录中“更新前的值”写入数据库。
这样, 如果记录中是插入操作，即相当与做删除操作；若记录中是删除操作，则作插入操作；若是修改操作，则相当于用修改前的值代替修改后的值。
3）继续反向扫描日志文件，查找该事务的其他更新操作，并作同样处理。
4）如此处理下去，直至读到此事务的开始标记，事务恢复就完成了。
32. 在参照完整性中，为什么外部码的属性值可以为空值？请举例说明在什么样的情况下才可以为空？答：包含在外部码中的属性不是主属性，因此可以为空值。
只有当包含在主属性的值不确定时，才能去空值。
例如员工表参照部门表，员工表中的部门号做候选键，当一个员工未分配部门时，部门号取空值。
33.答：数据库的安全性是指保护数据库，防止不合法的使用，以免数据的泄漏、非法更改和破坏。
数据库安全性控制的方法主要有：（1）用户标识与系统鉴定DBMS都要提供一定的方式供用户标识自己。
在存取数据库的数据之前，用户首先要自我标识，系统对用户的标识进行核定，通过鉴定后，才提供数据库的使用权。
