大工数据结构课程考试模拟试卷a

机 密★启用前大连理工大学网络教育学院2015年3月份《高等数学》课程考试 模拟试卷答案考试形式：闭卷 试卷类型：A一、单项选择题（本大题共10小题，每小题2分，共20分）1、C2、A3、C4、B5、B6、C7、D8、B9、C 10、A二、填空题（本大题共10小题，每小题3分，共30分）1、21-=x y 2、0 3、dx x x x x x x x ⎪⎪⎭⎫ ⎝⎛-+---2222121)23(arccos 64、>（或写成“大于”）5、C x x +-3sin 31sin6、13-=x y7、x 2sin 2ππ 8、C e x +--9、必要 10、22y x xy+三、计算题（本大题共5小题，每小题8分，共40分）1、解：所给极限为“00”型，注意当0→x 时，x x ~)1ln(+（4分）。

因此211sin lim sin lim )1ln(sin lim 000=+=⎪⎭⎫⎝⎛+=+=++→→→x x x x x xx x x x x x x （4分）2、解：本题为第一类换元法计算不定积分解法Ⅰ 做变量代换，令,1,ln du dx x u x ==（4分）C x C u udu dx x x+=+==⎰⎰ln sin sin cos ln cos （4分）解法Ⅱ 凑微分法，使用凑微分公式⎰⎰+===C x x xd dx x xx d dx x ln sin )(ln ln cos ln cos ),ln(13、解：依前述求定义域的原则，需有⎩⎨⎧>+-≥--01204222x y y x ，（4分）即⎩⎨⎧>+≤+x y y x 214222（4分） 从几何图形来看，已给函数的定义域为介于圆422≤+y x （包括边界）内，在抛物线x y 212=+右侧（不包括抛物线上的点）的区域，如下图所示。

4、解法一：利用全微分公式，设y z y z x z y x F ++=2222),,(，则z y x F yz F xz F z y x 2224,14,2+='+='='。

《数据结构》试卷A一、填空，请将答案写在横线上（每空2分，共20分）1.数据的逻辑结构是从逻辑关系上描述数据，它与数据的_____无关，是独立于计算机的。

2.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=。

3.栈顶的位置是随着操作而变化的。

4.在有序表（12，24，36，48，60，72，84）中二分查找关键字48时所需进行的关键字比较次数为。

5.多重表文件和倒排文件都归属于文件。

6.链表适用于查找。

7.队列的插入操作在进行，删除操作在进行。

8.数据的基本存储方式为顺序存储方式、链式存储方式和、四种。

二、是非题（用“√”、“×”分别标记正确与错误的说法。

每小题1分，共10分）：1.线性表的逻辑顺序与物理顺序总是一致的。

（）2.线性表的顺序存储表示优于链式存储表示。

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

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

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

（）6.二维数组可以视为数组元素为一维数组的一维数组。

（）7.链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。

（）8.在用单链表表示的链式队列中，队头在链表的链尾位置。

（）9.凡是递归定义的数据结构都可以用递归算法来实现它的操作。

（）10.进行折半搜索的表必须是顺序存储的有序表。

（）三、单项选择题，在括号内填写所选择的标号。

（每小题2分，共计30分）1．算法指的是（）A．计算机程序 B．解决问题的计算方法C．排序算法 D．解决问题的有限运算序列2．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（） A．O（1） B．O（n） C．O（m） D．O（m+n）3．由两个栈共享一个向量空间的好处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率4．如下陈述中正确的是（）A．串是一种特殊的线性表 B．串的长度必须大于零C．串中元素只能是字母 D．空串就是空白串5．一个非空广义表的表头（）A．不可能是子表 B．只能是子表C．只能是原子 D．可以是子表或原子6．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．77．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e8．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)9．适于对动态查找表进行高效率查找的组织结构是（）A．有序表 B．分块有序表 C．三叉排序树 D．线性链表10．不定长文件是指（）A．文件的长度不固定 B．记录的长度不固定C．字段的长度不固定 D．关键字项的长度不固定11．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )A. front == rearB. front != NULLC. rear != NULLD. front == NULL12. 图的广度优先搜索类似于树的（）次序遍历。

数据结构模拟试卷及参考答案一、简答题（共10题，每题10分，共计100分）1. 什么是数据结构？请简要解释。

数据结构是计算机中用于组织和存储数据的方式，它包含了一系列的数据元素，以及这些数据元素之间的关系和操作。

通过使用不同的数据结构，可以更高效地存储、查找和操作数据。

2. 请解释什么是栈，并给出一个栈的应用场景。

栈是一种具有特定操作限制的数据结构，它遵循"先进后出"（LIFO）的原则。

栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器中的历史记录。

3. 什么是队列？请给出一个队列的实际应用例子。

队列是一种具有特定操作限制的数据结构，它遵循"先进先出"（FIFO）的原则。

一个实际应用例子是操作系统的进程调度，进程按照到达时间加入队列，并按照一定规则出队执行。

4. 请解释什么是链表，并给出一个链表的优点和缺点。

链表是一种动态数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。

链表的优点是可以动态地分配内存空间，且插入和删除节点的时间复杂度为O(1)。

缺点是访问链表某个具体节点的时间复杂度为O(n)，且需要额外的内存空间存储指针。

5. 请解释什么是树，并给出一个树的实际应用例子。

树是一种分层次的数据结构，它由一系列节点和节点之间的关系构成。

一个实际应用例子是文件系统的目录结构，文件和文件夹通过树的结构进行组织和存储。

6. 请解释什么是图，并给出一个图的实际应用例子。

图是一种由节点和节点之间的连接关系组成的数据结构。

一个实际应用例子是社交网络，人与人之间的关系可以用图来表示，每个人是一个节点，节点之间的连接表示关系。

7. 请解释什么是散列（哈希）表，以及它的优势和劣势。

散列表是一种根据关键字直接访问的数据结构，它通过将关键字映射到表中的位置来实现快速的查找操作。

散列表的优势是查找操作的平均时间复杂度为O(1)。

劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：广东商学院试题参考答案及评分标准20XX12-20XX13 学年第一学期课程名称： 数据结构（A 卷） 课程代码：20XXXX0XX20XXXX0XX 课程负责人：罗勇题号1 2 3 4 5 6 7 8 9 20XXXX 答案B A AC BACADC题号1 2 3 4 5 6 7 8 9 20XXXX 答案C B C B DDABAB题号1 2 3 4 5 6 7 8 9 20XXXX答案× √ × √ √ × × × √ ×四、算法分析（每小题5分，共20XXXX 分）1．(1) ABC_1是直接插入排序方法。

（1分） 最坏情形下，)(2/2/)1)(2(i KCN 222n O n n n ni =≈-+==∑= （1分）)(2/2/)1)(4()21(RMN 22n2n O n n n i i =≈-+=+-=∑= （1分）(2) 排序过程如下：（2分）初始key r[0] (65) 38 80 50 20XXXX 27i=2 38 (38 65) 80 50 20XXXX 27 i=3 38 (38 65 80) 50 20XXXX 27 i=4 50 (38 50 65 80) 20XXXX 27i=5 20XXXX (20XXXX 38 50 65 80) 27 i=6 27 (20XXXX 27 38 50 65 80) （注：哨兵单元不正确扣1分，已排序列不正确扣1分）2．(1) 算法ABC_2功能：以中序遍历的次序，按关键字值递增的顺序依次输出值小于等于给定值60的结点。

若找到值大于60的结点，提前退出算法。

（3分）（2）20XXXX 20XX 35 45 55（每个值输出后换行）（2分）五、算法设计（共10分）（1）写出单链表存储结构的类型定义。

Typedef struct {int data; (1分)struct LNode *next; (1分)} LNode, *LinkList; (1分)（2）status Delete_L(LinkList &L, int min, int max) { LinkList p,q,s;p=L;while (p&&p->next->data<=min) （2分）p=p->next;if (!p) return ERROR;q=p->next;while (q&&q->data<=max) （3分）{ s=q;q=q->next;free(s);} //whilep->next=q; （2分）return OK;}//Delete_L教师（签名）：年月日。

数据结构模拟试题一一、判断题（每小题1 分，共15分）1.计算机程序处理的对象可分为数据和非数据两大类。

2.全体自然数按大小关系排成的序列是一个线性表。

3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。

4.顺序栈是一种规定了存储方法的栈。

5.树形结构中的每个结点都有一个前驱。

6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。

7.若某顶点是有向图的根，则该顶点的入度一定是零。

8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。

9.用一维数组表示矩阵可以节省存储空间。

10.广义表的长度与广义表中含有多少个原子元素有关。

11.分块查找的效率与线性表被分成多少块有关。

12.散列表的负载因子等于存入散列表中的结点个数。

13.在起泡排序过程中，某些元素可能会向相反的方向移动。

14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。

15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。

二、填空题（每空1分，共15分）1.顺序表是一种_____________线性表。

2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。

3.栈和队列的区别在于________的不同。

4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。

5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。

6.n个顶点的有根有向图中至少有___条边，至多有___条边。

7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。

8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。

9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。

适用专业：一、单项选择题（每题2分，共40分）1．以下说法正确的是A．线性结构的数据元素之间存在一对多的线性关系B．图形结构和树型结构是线性结构C．时间复杂度是用算法执行过程中所需要的基本运算次数来度量D．时间复杂度总是与空间复杂度成正比2．以下C语言程序的时间复杂度是for(i=1;i<=n;i++)for(j=1;j<=n;j++)s+=i*j;A．O(n) B．O(n2) C．O(2n) D．O(log2n) 3．按照“后进先出”原则组织数据的数据结构是A．队列B．栈C．双向链表D．二叉树4．链表不具有的特点是A．可随机访问任一元素B．插入删除不需要移动元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比 5．有关二叉树的下列说法正确的是 A 、任何一棵二叉树中至少有一个结点的度为2 B 、一棵二叉树的度可以小于2C 、二叉树中任何一个结点的度都为2D 、二叉树的度为26．若要在单链表中的结点p 之后插入一个结点s ，则应执行的语句是A ．s->next=p->next; p->next=s;B ．p->next=s; s->next=p->next;C ．p->next=s->next; s->next=p;D ．s->next=p; p->next=s->next;7．下图是栈的逻辑结构图，现从栈中删除一个元素，这个元素是topA 、97B 、 45C 、37D 、558．栈底至栈顶依次存放元素a b c ，在第四个元素d 入栈前，栈中元素可以出栈，则出栈序列可能是 A 、abcd B 、dabc C 、cbda D 、cdab 9．栈和队列都是A ．链式存储的线性结构B ．顺序存储的线性结构C ．限制存取位置的线性结构D ．限制存取位置的非线性结构 10．关于字符串的说法中，错误的是 A 、字符串是零个或多个字符组成的有限序列 B 、串中字符的个数称为串的长度 C 、长度为零的串称为空串D 、由空格组成的字符串称为空串 11．具有10个叶子结点的二叉树中有 个度为2的结点。

《数据结构》模拟试题13一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。

2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。

3、串是一种特殊的线性表，其特殊性体现在。

4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、对线性表进行二分查找时，要求线性表必须是，且要求。

8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。

Long int Sum (int n){ long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }return(sum) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。

（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。

（）（A）(a) ((b),c),(((d))) （B）(a) (((b),c),(((d))))（C）((a),((b),c)),(((d))) （D）(a) (((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。

《数据结构》模拟试题一、单项选择题（30分）1．在数据结构的讨论中把数据结构从逻辑上分为C。

A. 内部结构与外部结构B. 静态结构与动态结构C. 线性结构与非线性结构D. 紧凑结构与非紧凑结构。

2．算法分析的两个主要方面是 D。

A. 正确性和简明性B. 可读性和文档性C. 数据复杂性和程序复杂性D. 空间复杂性和时间复杂性3．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储B。

A. 数据的处理方法B. 数据元素的类型C. 数据元素之间的关系D. 数据的存储方法4．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为c。

A.5B.6C.7D.95．线性表采用链式存储结构时，要求内存中可用存储单元的地址d。

A. 必须是连续的B. 必须是部分连续的C. 一定是不连续的D. 连续和不连续都可以6．对具有n个结点的线性表进行插入和删除操作，所需的算法时间复杂度为 d。

A. O(1)B. O(n)C. O(nlog2n)D. O(n2)7．在单链表中指针p所指结点之后插入指针为s的结点，正确的操作是b。

A. p->next=s;s->next= p->next;B. s->next= p->next; p->next=s;C. p->next=s; p->next = s->nextD. p->next=s->next; p->next=s; 8．栈中元素的进出原则是b。

A．先进先出 B．先进后出 C．栈空则进 D．栈满则出9．长度是n的顺序循环队列，front和rear分别指示队首和队尾，判断队列为满队列的条件是__d____。

A．rear=0 B．front=0C．rear==front D．（rear+1）%n==front10．下面说法不正确的是_____c_____。

A．广义表的表头总是一个广义表 B．广义表的表尾总是一个广义表C．广义表难以用顺序存储结构 D．广义表可以是一个多层次的结构11．已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为____d___。

数据结构试卷(A)答案数据结构试卷(A)答案一、单选题（共10题，每题2分）1. 答案：B解析：选项A和C的时间复杂度为O(n)，不符合题目要求。

选项D的时间复杂度为O(n^2)，也不符合题目要求。

选项B的时间复杂度为O(1)，是最优解。

2. 答案：C解析：选项A的时间复杂度为O(n)，不符合题目要求。

选项B和D的时间复杂度为O(n^2)，也不符合题目要求。

选项C的时间复杂度为O(logn)，是最优解。

3. 答案：A解析：选项B和D的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(logn)，也不符合题目要求。

选项A的时间复杂度为O(nlogn)，是最优解。

4. 答案：D解析：选项A和B的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(nlogn)，也不符合题目要求。

选项D的时间复杂度为O(n)，是最优解。

解析：选项A和D的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项C的时间复杂度为O(n)，是最优解。

6. 答案：B解析：选项A和C的时间复杂度为O(n^2)，不符合题目要求。

选项D的时间复杂度为O(n)，也不符合题目要求。

选项B的时间复杂度为O(1)，是最优解。

7. 答案：D解析：选项A和C的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项D的时间复杂度为O(n)，是最优解。

8. 答案：C解析：选项A和D的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项C的时间复杂度为O(n)，是最优解。

9. 答案：A解析：选项B和D的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(nlogn)，也不符合题目要求。

选项A的时间复杂度为O(n)，是最优解。

解析：选项A和B的时间复杂度为O(n^2)，不符合题目要求。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

以下6-8题基于图1。

6.该二叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

××科技大学成都学院二零零八至二零零九学年第一学期一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。

2.下面程序段的时间复杂度为___O(n2)______。

(n>1)for(i = 1; i <= n; i++)for(j = 1; j <= i; j++)x = x + 1;3.静态链表中指针表示的是______下一结点的地址______。

4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。

5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。

6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。

7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。

8.带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。

9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。

10.在hq的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。

11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。

12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。

13.空串是_______长度为0的串______，其长度等于___0________。

14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________ 。

13哈尔滨工业大学数据结构试题及答案数据结构试卷（一）；一、单选题（每题2分，共20分）；1.栈和队列的共同特点是()；A.只允许在端点处插入和删除元素；B.都是先进后出；C.都是先进先出；D.没有共同点；2.用链接方式存储的队列，在进行插入运算时().；A.仅修改头指针B.头、尾指针都要修改；C.仅修改尾指针D.头、尾指针可能都要修改；3.以下数据结构中哪一个是非线性结构？()；A.队列B.数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965. 树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 二叉树的第k层的结点数最多为( ).kk-1 A．2-1 B.2K+1 C.2K-1 D. 27. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

数据结构期末试卷一、选择题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的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

《数据结构》模拟试题A一、单项选择题（每题 3 分，共24分）1．下面关于线性表的叙述错误的是（）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

(A)2m-1 (B)2m (C) 2m+1 (D) 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

(A) 9(B) 10(C) 11(D) 127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

(A) n-1 (B) n (C) n+1 (D) 2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

(A) 2，3，5，8，6 (B) 3，2，5，8，6(C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空题（每题2分，共16分）1.为了能有效地应用HASH查找技术，必须解决的两个问题是（）和（）。

2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

数据结构模拟卷（含答案）经典习题.doc 练习题⼀、单项选择题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. 散列存储和顺序存储B．数据的存储结构C．⼀组性质相同的数据元素的集合D．相互之间存在⼀种或多种特定关系的数据元素的集合8. 算法分析的⽬的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输⼊与输出的关系D．鉴别算法的可读性9. 在线性表的下列运算中,不．改变数据元素之间结构关系的运算是（）A．插⼊B．删除C．排序D．定位10. 下列图⽰的顺序存储结构表⽰的⼆叉树是( )11. 设串sl=″Data Structures with Java″,s2=″it″,则⼦串定位函数index(s1,s2)的值为(）A．15 B．16C．17 D．1812. ⼆维数组A[8][9]按⾏优先顺序存储,若数组元素A[2][3]的存储地址为1087 ,A[4][7]的存储地址为1153 ,则数组元素A[6][7]的存储地址为（）A．1213 B．1209C．1211 D．120713. 在按中序遍历⼆叉树的算法中,需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表14. 在任意⼀棵⼆叉树的前序序列和后序序列中,各叶⼦之间的相对A．不⼀定相同B．都相同C．都不相同D．互为逆序15. 若采⽤孩⼦兄弟链表作为树的存储结构,则树的后序遍历应采⽤⼆叉树的（）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法16. 若⽤邻接矩阵表⽰⼀个有向图,则其中每⼀列包含的″1″的个数为（）A．图中每个顶点的⼊度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数⽬17. 图的邻接矩阵表⽰法适⽤于表⽰（）A．⽆向图B．有向图C．稠密图D．稀疏图18. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t）,则在⼆分查找关键字b的过程中,先后进⾏⽐较的关键字依次为（）A．f,c,b B．f,d,bC．g,c,b D．g,d,b19. 下⾯程序段的时间复杂度为( )s=0；for(i=1；ifor(j=1；js+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)20. 已知指针p和q分别指向某单链表中第⼀个结点和最后⼀个结点。

数据结构模拟试卷及参考答案(总17页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。

A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（ B ）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ C ）A．插入B．删除C．定位 D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ D ）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，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（ A ）A．15 B．16C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（ B ）。

A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（ C ）个结点。

A. nB. n/2C. (n+1)/2D. (n-1)/2 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ D ）A．不一定相同B．互为逆序C．都不相同 D．都相同9．高度为5的二叉树至多有结点数为（ A ）A. 63B. 32C. 24 10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ B ）A．图中每个顶点的出度 B．图中每个顶点的入度C．图中弧的条数 D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（ C ）A ．无向图B ．有向图C ．稠密图D ．稀疏图12．在一个单链表中，若p 所指的结点不是最后一个结点，在p 之后插入s 所指的结点，则执行（ D ）。

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 《数据结构》一、单项选择题（本大题共10小题，每小题3分，共30分）1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。

A. 3,2,1,4B. 3,2,4,1C. 4,2,3,1D. 2,3,4,12、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。

A. 2kB.2k-1C. kD. 2k-13、衡量查找算法效率的主要标准是（）。

A. 元素个数B. 所需的存储量C. 平均查找长度D. 算法难易程度4、与线性表的顺序存储不相符的特性是（）。

A. 插入和删除操作灵活B. 需要连续的存储空间C. 便于随机访问D. 存储密度大5、若进队序列为1，2，3，则出队序列是（）。

A. 3,2,1B. 1,2,3C. 1,3,2D. 3,1,26、不带头结点的单链表L为空的判定条件是（）。

A. L==NULLB. L->next==NULLC. L->next==LD. L!=NULL7、union(A,B,C)表示求集合A和B的并集C。

若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。

A．{a,b,c,d} B．{a,b,c}C．{a,b} D．{c,d}8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。

A. 90B. 70C. 50D. 309、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。

A. 都不相同B. 完全相同C. 先序和中序相同D. 中序和后序相同10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。

A. 文件长度B. 平均码长C. 被压缩文件的特征D. 以上都不是1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或母亲的遗产，子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构试卷A卷（含答案）《数据结构》试卷A⼀、填空题（每空1分，共22分）1、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

2、⼀个算法的效率可分为效率和效率。

3、向⼀个长度为n的向量的第i个元素(1≤i≤n+1)之前插⼊⼀个元素时，需向后移动________个元素。

4、在⼀个循环队列中，队⾸指针指向队⾸元素的位置。

5、在具有n个单元的循环队列中，队满时共有个元素。

6、向栈中压⼊元素的操作是先，后。

7、称为空串；称为空⽩串。

8、假设有⼆维数组A6×8，每个元素⽤相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第⼀个字节地址为；若按⾏存储时，元素A14的第⼀个字节地址为；若按列存储时，元素A47的第⼀个字节地址为。

9、设⼀棵完全⼆叉树具有1000个结点，则此完全⼆叉树有个叶⼦结点，有个度为2的结点，有个结点只有⾮空左⼦树，有个结点只有⾮空右⼦树。

10、线性有序表（a1，a2，a3，…，a256）是从⼩到⼤排列的，对⼀个给定的值k，⽤⼆分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。

设有100个结点，⽤⼆分法查找时，最⼤⽐较次数是。

11、散列法存储的基本思想是由决定数据的存储地址。

⼆、判断题（每题1分，共10分）（）1. 队是⼀种插⼊与删除操作分别在表的两端进⾏的线性表，是⼀种先进后出型结构。

（）2.⼆叉树中所有结点个数是2k-1-1，其中k是树的深度。

（）3. 栈和队列的存储⽅式既可是顺序⽅式，也可是链接⽅式。

（）4.⼆叉树中所有结点，如果不存在⾮空左⼦树，则不存在⾮空右⼦树。

（）5.对于⼀棵⾮空⼆叉树，它的根结点作为第⼀层，则它的第i层上最多能有2i－1个结点。

（）6. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会⾃动将后续各个单元向前移动。

（）7.⽤⼆叉链表法（link-rlink）存储包含n个结点的⼆叉树，结点的2n个指针区域中有n+1个为空指针。

2022年大连工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。