大工数据结构课程考试模拟试卷a
- 格式：doc
- 大小：255.00 KB
- 文档页数：4
下载文档原格式
合集下载
大工《高等数学》课程考试模拟试卷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及答案
《数据结构》试卷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)。
劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。
大学1数据结构试题及答案-数据结构A参考答案
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的有序表时，排序码的比较次数至少是___次，至多是___次。
《数据结构》期终考试试卷(A卷)及答案
适用专业：一、单项选择题（每题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的结点。
《数据结构》3套模拟试题综合测试题带答案5
《数据结构》模拟试题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)答案数据结构试卷(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.数据的物理结构被分为_________、________、__________和___________四种。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
少年易学老难成，一寸光阴不可轻- 百度文库《数据结构》一、单项选择题（本大题共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. 树B. 图C. 数组D. 二叉树2、下列排序中，占用辅助空间最多的是（）。
A. 堆排序B. 冒泡排序C. 直接选择排序D. 二路归并3、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A. 选择排序B. 冒泡排序C. 希尔排序D. 插入排序4、在待排序序列局部有序的情况下，最好的内部排序应该是（）。
A. 直接选择排序B. 堆排序C. 直接插入排序D. 快速排序5、下列排序算法中不稳定的是（）。
A. 直接选择排序B. 直接插入排序C. 起泡排序D. 归并排序6、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A. top++B. top--C. top=0D. top=N-17、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。
A. 2B. 3C. 4D. 58、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。
A. 3B. 4C. 5D. 69、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。
A. nB. 2nC. eD. 2e10、index(s,t)表示子串定位运算。
若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。
若s="ababa",t="ba",则index(s,t)=（）。
A. 0B. 1C. 2D. 3二、判断题（本大题共15小题，每小题2分，共30分）1、栈和队列逻辑上都是线性结构。
（A.正确）2、算法的优劣与算法描述语言无关，但与所用计算机有关。
（B.错误）3、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。
（B.错误）4、空串是任意串的子串。
（A.正确）5、快速排序并非在任何情况下都比其他排序方法速度快。
（A.正确）6、通常把串s称为主串，串t称为模式串，从主串s中查找与模式串t完全相同的子串的过程叫做模式匹配。
（A.正确）7、堆排序是一种选择排序。
（A.正确）8、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
（B.错误）9、文件是性质相同的记录的集合，文件通常存储在外存上。
（A.正确）10、散列文件的优点是存取速度通常比索引文件更快，插入删除方便，不需要索引区。
（A.正确）11、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
（B.错误）12、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
（B.错误）13、散列函数越复杂越好，因为这样随机性好，冲突概率小。
（B.错误）14、负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。
（A.正确）15、交换排序的基本思想是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。
（A.正确）1、算法的有穷性是指一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（A.正确）2、算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。
（A.正确）3、链式存储方法，它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现。
（B.错误）4、在栈中，出栈操作的时间复杂度为O(n)。
（B.错误）5、栈和队列的共同特点是先进先出。
（B.错误）6、在用单链表表示的线性表中，从任何一个结点都能通过next域找到它的后继和前驱。
（B.错误）7、数据结构的概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。
（A.正确）8、给定一棵二叉树结点的先序序列和中序序列就可以唯一地确定一棵二叉树。
（A.正确）9、difference(A,B,C)表示求集合A和B的差集C。
（A.正确）10、完全二叉树中，若一个结点没有左孩子，则它必是树叶。
（A.正确）11、字典是一种特殊的集合，其中每个元素由关键码和属性组成。
（A.正确）12、若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。
（A.正确）13、哈希表查找无须进行关键字的比较。
（B.错误）14、直接选择排序是一种不稳定的排序方法。
（A.正确）15、倒排文件的优点是加快查找速度，尤其在处理多个次关键字查找时，查询速度更佳。
（A.正确）三、填空题（本大题共5个空，每空31、允许在表的一端插入和删除的线性表称为栈。
2、一个算法的时间复杂度为（n2+2nlog n），其数量级表示为O(n2)。
3、高度为5的完全二叉树T中最多有31个结点。
4、若一棵完全二叉树中有90个结点,其中有45个叶子结点。
5、设森林F 中有四棵树，第一、第二、第三和第四棵树的结点个数分别为50、40、30 和20。
由森林F 转换的二叉树中,根结点的左子树上的结点个数是49。
1、在有n 个结点的无向图中，其边数最多为 n(n-1)/2 。
2、有向图G 用邻接矩阵A[n][n]0代表无弧，其i(0≤i≤n -1)行的所有元素之和等于顶点i 的 出 度。
3、设30个整数按从小到大顺序存于一维数组A[30]中，若用二分法进行查找，需要进行5次比较查找成功的整数个数为 15 。
4、二叉排序树在进行 中序 遍历所输出的关键字序列是递增的有序序列。
5、对32,共需进行 5 趟归并。
四、简答题（本大题共3小题，每小题51、设广义表L=((a,b),c,((d,e),f),h), 求广义表L 的长度和深度；广义表L 的表头和表尾分别是什么？1、答： 表L 的长度是4。
（1分） 深度是3。
（1分）表L 的表头是(a,b)。
（1分）表尾是(c,((d,e),f),h) 。
（2分）2、设二叉树中每个结点的数据域值为一个字母，请画出先序序列是bcd 的所有不同形态的二叉树。
2、答：（下列每图1分）3、对整数序列{50,40,20,12,80,18}按从小到大顺序进行排序，请分别写出直接选择排序和二路归并排序的第一趟排序结果。
3、答：直接选择排序第一趟排序结果：{12,40,20,50,80,18 } （3分）二路归并排序第一趟排序结果：{[40,50],[12,20],[18,80]} （2分）1GC D P R EM K H1、答：GK CD H PR EM253，46，30，13，42，67，78}，散列函数H （k ）=k % 10，采用散列表的线性探查法解决冲突。
试在0到9的散列地址空间内对该关键字构造散列表，并求出在等概率的情况下，查找成功时的平均查找长度。
2、答： (1) 用函数计算散列地址如下： H （22）=2；H （41）=1；H （53）=3；H （46）=6；H （30）=0； H （13）=3（冲突）=4；H （42）= 2（冲突）=3（冲突）=4（冲突）=5； H （67）= 7；H （78）=8； 构造的散列表如下：bd cb c c c c d d d db b b0 1 2 3 4 5 6 7 8 930 41 22 53 13 42 46 67 78成功探查 1 1 1 1 2 4 1 1 1(2)在等概率情况下，查找成功的平均查找长度：ASLs成功=（1+1+1+1+2+4+1+1+1）/9=13/93、给定的整数序列{58, 34, 90, 20, 80, 98, 18, 27}进行从小到大排序时，请写出直接选择排序、归并排序的第一趟排序结果。
3、答：直接选择排序一趟排序结果：{18,34,90,20,80,98,58,27}归并排序一趟排序结果：{[34,58],[20,90],[80,98],[18,27]}五、算法题（本大题1小题，共10分）1、已知一整型数组r，编写一个函数，每输入一个数组元素的下标，便输出相应的数组元素的值，输入-1时结束。
1、void f(int r[]) // (此语句2分){int i;scanf(“%d”,&i); // (此语句2分)while(i!=-1) // (此语句2分){printf(“%d”,r[i]); // (此语句2分)scanf(“%d”,&i); // (此语句2分)}}1、已知二叉树以二叉链表作存储结构，阅读算法并回答下列问题：(1) 该算法的功能是什么？(2) 算法中n的作用是什么？二叉链表中结点类型定义为：typedef struct node{char data；struct node *lchild,*rchild；}BTNode；int unknown (BTNode *t,int n){ if (t){ if(t->lchild && t->rchild)n++；n=unknown(t->lchild,n)；n=unknown(t->rchild,n)；}return n；}1、答：（1）该算法的功能是计算二叉树中度为2的结点个数，（2）算法中n的作用是保存度为2的结点个数。