厦门大学信科数据库及数据结构试题

一、（本题10分）（1）简述线性表的两种存储结构的主要优缺点及各自适用的场合。

（2）在折半查找和表插入排序中，记录分别应使用哪种存储结构，并用一句话简述理由。

答：（1）顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除操作将引起元素移动，降低效率。

对于链式存储，元素存储采取动态分配，利用率高。

缺点是须增设指针域，存储数据元素不如顺序存储方便。

优点是插入与删除操作简单，只须修改指针域。

（2）在折半查找中，记录使用顺序存储，可以快速实现中点的定位；在表插入排序中，记录使用静态链表，可以降少移动记录的操作。

二、（本题15分）在带头结点的非空线性链表中，试设计一算法，将链表中数据域值最小的那个结点移到链表的最前面，其余各结点的顺序保持不变。

要求：不得额外申请新的链结点。

解：程序如下：typedef struct node {int data;struct node * next;}Node,*LinkList;void MinFirst(LinkList L){Node *p,*q,*ptrmin;if(L->next == NULL) return; //空表ptrmin = L; //ptrmin指向当前最小结点的前一个结点p = L->next;//p指向当前结点的前一个结点while(p->next!=NULL) {if( p->next->data < ptrmin->next->data ) ptrmin = p;p = p->next;}//q指向最小结点，并从链表中删除q = ptrmin->next; ptrmin->next = q->next;q->next = L->next; L->next = q; //q指向的最小结点插入到链表头}三、（本题15分）编写函数判断一棵二叉树是否不含有度为1的结点，若任何结点的度都不为1，则返回TRUE，否则返回FALSE。

数据结构考试试题及答案2022-05-12 09:22计科 2 班期中考试题答案提交说明：写清题号，以 word 文本格式保存，文件名命名规则为：姓名+学号，放到 ftp：//192.168.130.50 的“计科 2 班考试”文件夹中。

一．填空题(每题 1 分，共 10 分)( 1 )已知一个顺序存储的线性表，设每一个结点需占m 个存储单元，若第 0 个元素的地址为 address,则第 i 个结点的地址是( address+i*m )。

( 2 )线性表有两种存储结构：顺序存储结构和链式存储结构，就两种存储结构完成下列填空：( 顺序存储结构)存储密度较大，( 链式存储结构)存储利用率较高，(顺序存储结构)可以随机存取，( 链式存储结构)不可以随机存取，( 链式存储结构)插入和删除操作比较方便。

( 3)顺序表中逻辑上相邻的元素在物理位置上(也相邻)，在链表中逻辑上相邻的元素的物理位置( 不一定)相邻。

(4)在一个长度为 n 的顺序表中，在第 i个元素 ( 0<=i<=n ) 之前插入一个新元素时须向后挪移 ( n-i+1 ) 个元素。

( 5)在顺序表 la的第 i个元素前插入一个新元素，则有效的 i值范围是( 0 <=i<=length -1 ) ；在顺序表 lb的第j个元素之后插入一个新元素，则 j的有效范围是( 0 <= j<=length-1 ) ；要删除顺序表 lc的第 k 个元素，则 k 的有效范围是( 0 <=k<=length-1 )。

( 6)设有一个空栈，现有输入序列为 1，2，3，4，5，经过操作序列 push , pop , push , push , pop,push ,push ,pop后，现在已出栈的序列是1,3,5 ，栈顶元素的值是 4 。

( 7)设有栈 S ，若线性表元素入栈顺序为 1，2，3，4，得到的出栈序列为 1，3，4，2，则用栈的基本运算 Push, Pop描述的操作序列为push , pop, push, push , pop, push , p。

1. 数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

2 何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。

程序＝数据结构＋算法3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和占据空间的大小。

4. 何谓频度、时间复杂度、空间复杂度？说明其含义。

算法中语句的重复次数称为该语句的频度。

时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。

空间复杂度是算法对空间占用的量度。

（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。

）5. 时间复杂度的计算：语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。

语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。

【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。

这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。

i=1;while(i<=n)i=i*5;【解】设语句“i=i*5;”的频度为x，则5x<=n，x<=log5n，O(log5n)i=0;s=0;while(s<n){i++; s+=i;}【解】i=1,s=1i=2,s=1+2i=3,s=1+2+3,s就是对等差数列求和，因此s=i(i+1)/2<n，其中i就是循环语句的频度，因此O(n)6. 在一个具有n个结点的有序单链表中插入一个新结点，使得链表仍然有序，该算法的时间复杂度是( )A.O(log2n)B.O(1)C.O(n2)D.O(n)(D)7. 如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。

A.单链表B.双向链表C.单循环链表D.顺序表（D）8. 写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）：(L==L->Next) && (L==L->Prior)注：L->Next==L->Prior不行，因为表长为1时该条件也成立。

2022年厦门大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

2022年厦门大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、有如下C语言程序段：for（k=0；k<1000；k++）a[k]=a[k]+32；若数组a及变量k均为int型，int型数据占4B，数据Cache采用直接映射方式、数据区大小为1KB，块大小位16B，该程序段执行前Cache为空，则该程序段执行过程中访问数组a的Cache缺失率约为（）。

A.1.25%B.2.5%C.12.5%D.25%2、在一个容量为l28KB的SRAM存储器芯片上，按字长32位编址，其地址范围可从0000H到（）。

A.3HB.7HC.7HD.3fH3、float类型（即IEEE754标准中的单精度浮点数格式）能表示的最大整数是（）。

A.2126-2103B.2127-2104C.2127-2105D.2128-21044、假设机器字长为8位（含两位符号位），若机器数DA日为补码，则算术左移一位和算术右移一位分别得（）。

A.B4H EDHB.F4H 6DHC.B5H EDHD.B4H 6DH5、ALU属于（）。

A.时序电路B.控制器C.组合逻辑电路D.寄存器6、在下面描述的PCI总线的基本概念中，不正确的表述是（）。

A.PCI总线支持即插即用B.PCI总线可对传输信息进行奇偶校验C.系统中允许有多条PCI总线D.PCI设备一定是主设备7、总线宽度与下列（）有关。

A.控制线根数B.数据线根数C.地址线根数D.以上都不对8、下列关于计算机操作的单位时间的关系中，正确的是（）。

A.时钟周期>指令周期>CPU周期B.指令周期CPU周期>时钟周期C.CPU周期>指令周期>时钟周期D.CPU周期>时钟周期>指令周期9、下列选项中，能缩短程序执行时间的措施是（）。

1.提高CPU时钟频率Ⅱ.优化数据通路结构ll.对程序进行编译优化A.仪I、ⅡB.仅I、ⅢC.仅Ⅱ、ID.I、Ⅱ、Ⅲ10、下列有关I/O接口的叙述中，错误的是（）。

【2023年】福建省厦门市全国计算机等级考试数据库技术测试卷(含答案)学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 在通常情况下，下面的关系中，不可以作为关系数据库关系的是______。

A.R1(学生号，学生名，性别)B.R2(学生号，学生名，班级号)C.R3(学生号，班级号，宿舍号)D.R4(学生号，学生名，简历)2. 文件的存取方式与文件的物理结构有关，常见的文件物理结构是A.顺序结构、线性结构和链接结构B.线性结构、链接结构和索引结构C.顺序结构、链接结构和索引结构D.顺序结构、线性结构和索引结构3. 若让元素1，2，3依次进栈，则出栈次序不可能出现哪一种情况?A.3，2，1B.2，1，3C.3，1，2D.1，3，24. 在嵌入式SQL中，与游标相关的有4个语句，其中使游标定义中SELECT语句执行的是( )。

A.DECLAREB.OPENC.FETCHD.CLOSE5. 一个1:N联系可转换为一个独立的关系模式，关系的码为A.N端实体的码B.实体的码C.各实体码的组合D.每个实体的码6. 设有一个关系：DEPT(DNO，DNAME)，如果要找出倒数第3个字母为W，并且至少包含4个字母的DNAME，则查询条件子句应写成WHERE DNAME LIKEA.'W %'B.'_% W_ _'C.'W'D.'W %'7. 双链表的每个结点包括两个指针域。

其中rlink指向结点的后继，llink 指向结点的前驱。

如果要在p所指结点后插入q所指的新结点，下面操作序列正确的是A.p↑．rlink↑．ll I nk：=q；p↑．rlink：=q；q↑．llink：=p；q↑．rlink：=p↑．rlink；B.p↑．llink↑．rl I nk：=q；p↑．llink：=q；q↑．rlink：=p；q↑．llink：=p↑．llink；C.q↑．llink：=p；q↑．rlink：=p↑．rlink；p↑．rlink ↑．llink：=q；p↑．rlink：=q；D.q↑．rlink：=p；q↑．llink：=P↑，llink；p↑．llink↑．rlink：=q；p↑．llink：=q；8. 假定一棵三叉树的结点个数为50，则它的最小深度为______。

数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有多个根结点D. 有且只有一个叶子结点答案：C2. 在单链表中，头结点的作用是（）A. 作为链表的起点B. 作为链表的终点C. 存储链表中的数据元素D. 作为链表中的第一个元素答案：A3. 在顺序表中，插入一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：B4. 下列哪种排序算法的平均时间复杂度最高？A. 冒泡排序B. 快速排序C. 直接插入排序D. 希尔排序答案：C5. 在二叉树中，具有3个结点的二叉树有（）种不同的形态。

A. 2B. 3C. 4D. 5答案：C6. 下列哪种情况不适合使用哈希表？A. 查找速度快B. 数据量较大C. 数据量较小D. 数据元素关键字分布均匀答案：C7. 在图的遍历过程中，下列哪种遍历方法属于深度优先遍历？A. 广度优先遍历B. 深度优先遍历C. 混合遍历D. 随机遍历答案：B8. 下列哪种数据结构不适用于实现栈？A. 顺序表B. 链表C. 树D. 图答案：C9. 在双向链表中，删除一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A10. 下列哪种情况不适合使用队列？A. 数据元素先进先出B. 数据元素后进先出C. 数据元素随机进出D. 数据元素按顺序进出答案：B二、填空题（每题2分，共20分）1. 线性表是具有______个数据元素的有限序列。

答案：n2. 在单链表中，每个结点包含两个域：数据域和______域。

答案：指针3. 在顺序表中，插入一个元素的时间复杂度是______。

答案：O(n)4. 快速排序的平均时间复杂度为______。

答案：O(nlogn)5. 哈希表中的冲突指的是______。

答案：不同的关键字对应同一存储位置6. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。

数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。

B、创建一个 PowerPoint 演示文稿，然后批量插入图片。

C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。

D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。

正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。

首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。

则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。

则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。

则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论 (2)第二章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图 (11)第八章查找 (13)第九章排序 (14)简答题 (19)第一章绪论 (19)第二章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图 (36)第八章查找 (38)第九章排序 (39)编程题 (41)第一章绪论 (41)第二章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图 (52)第八章查找 (52)第九章排序 (57)选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？(A ）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素,90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素,90分是数据元素4.*数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C )A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A )。

2022年厦门大学嘉庚学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、设X是树T中的一个非根结点，B是T所对应的二叉树。

在B中，X是其双亲的右孩子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是：A.05，46，13，55，94，17，42B.05，13，17，42，46，55.94C.42，13，94，05，55，46，17D.05，13，46，55，17，42，94二、填空题11、阅读下列程序，指出其功能，并写出空格处应填上的语句。