数据结构期中卷

第页/共 页 《数据结构》期中考试试卷一、选择题（每题2分，共40分）1．组成数据的基本单位是【 】。

A ．数据项B ．数据类型C ．数据元素D ．数据变量 2．线性表采用链式存储时，结点的存储地址【 】。

A ．必须是不连续的 B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3. 有一个含头结点的单链表，头指针为head ，判断其是否为空的条件为【 】。

A ．head==NULL B ． head->next==NULL C ．head->next==head D ．head!=NULL 4．算法分析的目的是【 】。

A ．辨别数据结构的合理性B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性5．已知指针p 所指结点不是尾结点，若在*p 之后插入结点*s ，则应执行下列哪一个操作？【 】。

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 ； 6．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可 能出现的出栈序列为【 】。

A ．3，2，6，1，4，5B ．5，6，4，2，3，1C ．1，2，5，3，4，6D ．3，4，2，1，6，5 7．一个元素进入队列的时间复杂度是【 】。

A O(1)B O(n)C O(n 2)D O(log 2n) 8．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为【 】。

A 1140 B 1145 C 1120 D 1125 9．链表不具有的特点是【 】。

数据结构期中考试题一、选择题1. 数据结构是（）的研究。

A. 算法B. 数据C. 硬件D. 软件2. 下列哪种数据结构在插入和删除操作时效率较高？A. 数组B. 链表C. 栈D. 队列3. 以下哪种数据结构使用了先进先出（FIFO）的策略？A. 栈B. 队列C. 链表D. 数组4. 在二叉树中，每个节点最多可以有几个子节点？A. 0B. 1C. 2D. 35. 以下哪种数据结构在查找操作时效率较高？A. 数组B. 链表C. 栈D. 二叉树二、简答题1. 请简要介绍栈（Stack）和队列（Queue）的特点及应用场景。

2. 请解释树（Tree）和图（Graph）的区别，并给出它们各自的应用场景。

3. 请描述二叉树（Binary Tree）的特点并给出一个示例图。

4. 请简要介绍哈希表（Hash Table）的原理及其在实际应用中的优势。

三、编程题1. 设计一个栈，使得它具有以下功能：- push(val)：将元素val压入栈中。

- pop()：弹出栈顶元素，并返回弹出的元素。

- getMin()：返回栈中最小的元素。

2. 设计一个队列，使得它具有以下功能：- push(val)：将元素val插入队列中。

- pop()：移除并返回队列头部的元素。

- peek()：返回队列头部的元素。

- empty()：检查队列是否为空。

四、综合题某公司需要设计一个学生信息管理系统，主要功能包括添加学生信息、查询学生信息、删除学生信息以及修改学生信息。

请使用合适的数据结构和算法来实现该系统，并说明你的选择理由。

总结：通过本次期中考试题，我们从选择题、简答题到编程题，对数据结构的基本知识和应用有了更深入的了解。

数据结构在计算机科学中扮演着重要的角色，合理的选择和运用数据结构可以提高程序的效率和性能。

希望大家能够加强对数据结构的学习和应用，为解决实际问题提供更有效的解决方案。

一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。

A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。

A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。

A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。

D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。

A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。

A )。

A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。

《数据结构》期中考试试卷(供2012级计算机专业用)一、单项选择题，在括号内填写所选择的标号（每小题1分，共20分）1、算法指的是（）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2、如下陈述中正确的是（）A．串是一种元素仅为字符的线性表 B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串3、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A. O(1)B. O(n2)C. O(n)D. O(n/2)4、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A. n-2B. n-1C. nD. n+15．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear 分别为队列的队头指针和队尾指针) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。

A．QU->rear==(QU->front+1) % m0B．QU->rear==(QU->rear+1) % m0C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1)7．设有S1=“ABCDEFG”，S2=“PQRST”，函数con(x，y)返回x和y串的连接串，subs(s,i，j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个元素结点。

数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表是按照什么顺序排列的元素集合？A. 任意顺序B. 无序C. 有序D. 线性2. 链表与数组相比，其主要优点是什么？A. 节省空间B. 访问速度快C. 插入和删除操作灵活D. 内存分配简单3. 栈（Stack）是一种遵循什么原则的数据结构？A. 先进先出B. 先进后出C. 后进先出D. 后进后出4. 哈希表解决冲突最常用的方法是？A. 链接法B. 替换法C. 线性探测法D. 二次探测法5. 树和二叉树的主要区别是什么？A. 树的节点数可以比二叉树多B. 树的节点可以有多个子节点C. 树的节点可以没有子节点D. 树的节点可以有左子节点和右子节点6. 什么是二叉搜索树（BST）？A. 所有左子节点的值小于根节点的值B. 所有右子节点的值大于根节点的值C. 所有左子节点的值大于根节点的值D. A和B都正确7. 图的邻接矩阵表示法适用于哪种类型的图？A. 稠密图B. 稀疏图C. 有向图D. 无向图8. 排序算法的时间复杂度为O(n^2)的算法有哪些？A. 选择排序B. 冒泡排序C. 插入排序D. 所有以上9. 什么是递归？A. 函数调用自身B. 函数调用其他函数C. 循环结构D. 条件语句10. 动态规划主要用于解决什么问题？A. 排序问题B. 查找问题C. 优化问题D. 数据存储问题二、简答题（每题5分，共20分）1. 请简述链表和数组的区别。

2. 解释什么是图的深度优先搜索（DFS）。

3. 什么是二叉堆？请简述其性质。

4. 描述快速排序算法的基本思想。

三、编程题（每题15分，共30分）1. 编写一个函数，实现单链表的反转。

2. 编写一个函数，实现二叉树的前序遍历。

四、算法设计题（每题15分，共30分）1. 设计一个算法，用于在无序数组中找到第k小的元素。

2. 设计一个算法，实现最小生成树的克鲁斯卡尔算法。

五、综合应用题（10分）假设你正在开发一个在线图书管理系统，请设计一个数据结构来存储书籍信息，并实现以下功能：- 添加新书- 删除书籍- 查找特定书籍- 列出所有书籍请提供数据结构的设计思路和相应的伪代码。

《数据结构》期中试卷专业________ 学号_________ 姓名________ 成绩_______一、选择题（本大题共50小题，每小题2分，共100分）1. 若广义表K满足head(K)=tail(K),则K为 ( )A.( )B.( ( ) )C. ( () ),( () )D.( (),(),() )2.若要求尽可能快地对实数数组进行稳定的排序，则应选( )A.快速排序B.堆排序C.归并排序D.基数排序3. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（）次关键码比较。

A.2B.3C.4D.54．对包含N个元素的散列表进行查找，平均查找长度( ）A.为 O(log2N)B.为O(N)C.不直接依赖于ND.上述三者都不是5.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，16．下面关于图的存储的叙述中，哪一个是正确的。

（）A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关7. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( )A.前序遍历B.后序遍历C.中序遍历D.层次遍历8.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是( )A.小于B.大于C.等于D.不小于9.下面关于B-树和B+树的叙述中，不正确的是 ( )A. B-树和B+树都是平衡的多分树B. B-树和B+树都是可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索10. 给定下列有向图和初始结点V1,按深度优先遍历的结点序列为( )A.V1，V2，V4，V5，V3B.V1，V3，V4，V5，V2C.V1，V2，V5，V3，V4D.V1，V2，V3，V4，V511. 在数据结构中，从逻辑上可以把数据结构分成（）。

2014-2015学年第二学期《数据结构与算法》期中考试学号：姓名：一、写语句1.设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。

2.设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作3. 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入s结点的C语言描述语句。

4. 一线性表存储在带头结点的双向循环链表中，L为头指针。

如下算法：（1）说明该算法的功能。

（2）在空缺处填写相应的语句。

void unknown (BNODETP *L){ …p=L->next; q=p->next; r=q->next；while (q!=L){ while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；(1) ______；q->next=p->next；q->prior=p；(2) ______；(3) ______；q=r；p=q->prior；(4) ______；} }二、写算法1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；(2) 在单链表将比正整数x小的数按递减次序排列；(3) 将正整数（比）x大的偶数从单链表中删除。

2. 设键盘输入n个英语单词，输入格式为n, w1, w2, …,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（1）如果单词重复出现，则只在链表上保留一个。

数据结构期中试卷（考试时间80分钟, 满分100分）一、填空（2*20=40分）1.数据按逻辑结构可分为___________, __________________和__________________。

2.评价一个算法效率的标准是 __________________和__________________。

3、链式存储中结点分为两个域, 分别是______________和__________________。

4.带头结点的单链表为空表的条件是head->link= =NULL。

5.栈的工作特点是__________________, 队列的工作特点是__________________6、判断环形队列队空的条件是head= =tail, 队满的条件是(tail+1)%MAXN= =head。

7、在顺序存储的线性表中插入、删除一个结点平均移动个结点n/2。

8、有一个400项的表, 若用分块查找法, 则分成____20___块最好。

9、单链表中在p结点后插入q结点的语句为_q->link=p->link,p->link=q。

10、单链表中删除p结点后q结点的语句为p->link=q->link,free(q)。

11.判断带头结点的的环形链表为空表的条件为____head->link= =head____________。

12.二分查找的前提条件是按关键字有序, 分块查找的前提条件是块间有序, 块内有序或无序。

13、广义表中元素若为数据元素则被称为_________, 若为广义表则被称为________________。

二、判断（1*10=10分）1.链式存储结构优于顺序存储结构。

（ F ）2.顺序存储可实现随机存取。

（ T ）3.对于链表中元素逻辑相邻则物理也相邻。

（ F ）4.把中缀表达式转换为后缀表达式时应用的是队列。

（ F ）5.队列是插入、删除限制在表的两端的线性表。

数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。

满分100分，共20道选择题，每题5分。

请在60分钟内完成。

C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。

3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。

线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。

5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。

6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头 B．表尾 C．任意位置 D．指定位置2、下述哪一条是顺序存储结构的优点（2）。

A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D． O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头B．表尾C．任意位置D．指定位置2、下述哪一条是顺序存储结构的优点？（2）。

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D．O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

信科院09计算机《数据结构》期中试卷班级________学号__________姓名___________得分________一．单项选择题（本大题共10小题，每小题2分，共20分）A 1．算法分析的目的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性A 2．把长度为m的单链表LB接在长度为n的单链表LA之后的算法的时间复杂度为( )A．O(m) B．O(n) C．O(m+n) D．O(1)C 3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A．插入B．删除C．定位D．排序B 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，5A 5．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2,1)的值为（）A．15 B．16 C．17 D．18C 6．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（）A. 108B. 112C. 116D. 120A 7．有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是( )A. 访问第i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序C 8. 将递归过程转化为非递归过程需用到( )A．栈B．队C．线性表D．链表B 9. 设有一广义表E=（a,b,(c,d)），其长度为( )A．2 B．3 C．4 D．5D 10．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指结点，则执行（）A. s->next=p; p->next=sB. p-next=s; s->next=pC. p=s; s->next=p->nextD. s->next=p->next; p->next=s二．填空题（本大题共10小题，每小题2分，共20分）1.在数据结构中，数据的逻辑结构分线性结构和非线性结构。

数据结构期中试卷一、选择题（每个选择2分，共 20分）请将正确选项的编号写在题后的括号中。

1．用链接方式存储的队列，在进行插入运算时( ).①.仅修改头指针②头、尾指针都要修改③仅修改尾指针④头、尾指针可能都要修改2.带头结点的单链表first为空的判定条件是：（）①. first == NULL; ②. first->link == NULL;③first->link == first; ④. first != NULL;3若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

①单链表②双链表③单向循环④顺序表4将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为( )①.O(1) ②.O(m)③.O(n) ④.O(m+n)5设矩阵A（a ij，l≤i,j≤ 10）的元素满足：a ij≠0(i≥j, l≤i, j≤ 10)a ij=0 (i<j, l≤i, j≤ 10)现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为①2340 ②2336 ③2164 ④21606如果以链表作为栈的存储结构，则退栈操作时（）①必须判别栈是否满②对栈不作任何判别③必须判别栈是否空④判别栈元素的类型7设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）①front=front+1 ②front=(front+1)% m③rear=(rear+1)%m ④front=(front+1)%(m+1)8.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

①O(n) ②. O(n/2) ③. O(1) ④. O(n2)9.已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）①.5，4，3，2，1，6 ②.2，3，5，6，1，4③.3，2，5，4，1，6 ④.1，4，6，5，2，310.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）①.⎪⎪⎪⎪⎪⎭⎫⎝⎛--00405000000000706080 ②.⎪⎪⎪⎪⎪⎭⎫⎝⎛--00000004053000706080 ③.⎪⎪⎪⎪⎪⎭⎫⎝⎛--00405000073000006080 ④.⎪⎪⎪⎪⎪⎭⎫⎝⎛--00000304050000706080 二、判断题（每题2分，共10分）1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

-、判1、我11表的也辑顾序与物理陨障总是一致的。

（）2、线性表的顺序存储表示优于飪氏存储表示。

（）3、找性表若采用箍式存储表示时所有给点之间的存昭单元地址可连续可不连续。

（）4、二维数组是貝数组元素为线性表的线性表。

（）5、每种数据结枸都应具备三种基本运算：捕人、删除和搜索。

（）6、数齬给构炭念包括数齬之间的逆瑕结构，数据在廿算机中的存储方氏和数据的运算三个方而。

（）7、线性表中的每彳、结点最多只有一彳、痢驱和一个后继。

（）8、我性的数据结枸可£1顺疥存储，也可決存储。

非找ft的数摒结构只能存储。

（）9、枝和从艸逻辑上胡是线性表。

（）10、单箍表从任何一个结点出发，邵能诉冋到所有结点（）11、删除二叉HI If ffl中一个给点，再車新捕人上去，一定能得到原来的二叉UUffflo （）12、快速排床是孙Jf算法中最快的一种。

（）13、多维数组是向量的推广。

（）14. -filfflft二叉树的结点数目制可以力0。

（）15、有接选tHlf是一种不稳定的排序方法。

()16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

()17、在只有度为0和度为k的给点的k叉树中，设度为0的结点有nO个，度力k的结点有nk 个,则有n0=nk+1o ()18、折半搜索只适用与有序表，色括有序的颇序表相有序的85表。

()19、堆枝在数稠中的存储原剧是先进先出。

()20、臥列在数需中的存昭原II是后进先出。

()21、用皿邻矩阵表示图两用的存储空间大小与图的ii数成正比。

()22、略夫曼喲一定是满二叉讯。

()23、程序是用廿算机语言表述的算进。

()24、线徃表的顺Jf存储结构是通ilfiS元索的存储地址胃接反映数摒元索的廻辑关系。

(25、用一组地址连续的存昭单元存笊的元索一定构成找性表。

()26、堆枝、臥列和数组的逆辑结构邵是线性表结构。

()27、给定一组权值，可以唯一构危出一棵盼夫Ifflo ()28、只有在初始数据力逆序时，冒泡排序所执行的比较次数E^o ()29、希尔孙序在较率上较頁接接人松序有较大的ttiSo E是不稳定的。

《数据结构》期中试卷一、填空题（每空2分，共44分）1、数据结构可分为_线性结构_，__树形结构___和__图形结构__。

2、算法的效率包括时间与空间两个方面，分别称为_时间复杂度_与__空间复杂度_。

3、向一个长度为n的线性表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 _n-i_个元素。

4、线性表的存储结构常用的有_顺序存储_、_链式存储___两种。

5、、队列的特性是_先进先出_，而栈的特性是_后进先出_。

6、折半查找算法的时间复杂度为：_____________；顺序查找算法的时间复杂度为：___O（N）__________；7、链式存储中结点分为两个域，分别是__数据域__和__ 指针域__。

8、广义表A=(（a1),（a2,……,an）)的表头为____(a1)_____，表尾为__(a2,……,an) __，用表头和表尾描述a2=_ (head(head(tail(A)))__。

9、构造散列函数的方法通常有_平方取中法_,_移位法__，___数字分析法__,__除留余数法__四种。

10、已知线性表的起始存储位置为b，表中任意一个元素所占用的存储单元为k 个，则表中任意一元素ai的存储位置LOC(ai)为__b+(i-1)*k____________________。

二、选择题（每题3 分，共18分）1、线性表是一个( A )A、有限序列，可以为空B、有限序列，不能为空C、无限序列，可以为空D、无限序列，不能为空2、线性表采用链式存储时，其地址( D )A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以3、已知某顺序线性表有20个元素，其首地址为20，每个元素占2个存储空间，则第15个元素的存储位置为( D )A、35B、40C、45D、484、进栈顺序为ABC,以下不可能的出栈顺序是（ C ）A、ABCB、BACC、CABD、CBA5、采用折半查找的前提是（ D ）A、线性数据集合B、元素分成块C、用二叉排序树存储D、按关键字有序6、索引顺序查找又称分块查找，它要求索引表必须（ A ），各子块必须“按块有序”。