下载文档原格式
数据结构试卷B试题B⼀、填空题（18⼩题，40个空，每空分，共20分）1、数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。
2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
3、在顺序表中插⼊或删除⼀个元素，需要平均移动，具体移动的元素个数与有关。
4、在顺序表中访问任意⼀结点的时间复杂度均为，因此，顺序表也称为的数据结构。
5、顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置相邻。
6、若n为主串长，m为⼦串长，则串的古典（朴素）匹配算法最坏的情况下需要⽐较字符的总次数为。
7、求下列⼴义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ; //头元素不必加括号—（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、⼀棵具有２５７个结点的完全⼆叉树，它的深度为。
9、设⼀棵完全⼆叉树具有1000个结点，则此完全⼆叉树有个叶⼦结点，有个度为2的结点，有个结点只有⾮空左⼦树，有个结点只有⾮空右⼦树。
10、图有、等存储结构，遍历图有、等⽅法。
11、n个顶点e条边的图采⽤邻接矩阵存储，⼴度优先遍历算法的时间复杂度为；若采⽤邻接表存储，该算法的时间复杂度为。
12、⽤Dijkstra算法求某⼀顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。
13、假设在有序线性表a[20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为；⽐较四次查找成功的结点数为；平均查找长度为。
14、在各种查找⽅法中，平均查找长度与结点个数n⽆关的查找⽅法是。
⼤多数排序算法都有两个基本的操作：和。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题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. 编写一个函数，实现链表的插入操作。
《数据结构》期末考试试题及答案(2003-2004学年第2学期)单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。
(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（ a ）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（ d ）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（ c ）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ a ）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（ a b ）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（ c ）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（ c ）域存储后继结点的地址。
| || | | | | |装| | | | |订| | | | | |线| | | | | | | | |数据结构试卷（B）期末考试标准答案及评分细则一、选择题（本大题共15小题，每题2分，共30分。
）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ）。
A 数据的处理方法B 数据元素的类型C 数据元素之间的关系D 数据的存储方法2、算法的时间复杂性是（ C ）。
A简单操作次数的多少 B 算法运行时间的多少C 一个算法运行时间的相对度量D数据处理时间的多少3、下列关于顺序存储结构的叙述中，不正确的是（C ）。
A 结点之间的关系由存储单元的邻接关系来体现B存储密度大，存储空间利用率高C 插入、删除操作灵活方便，不必移动结点D 可以通过计算机直接确定第i个结点的存储地址4、栈中元素的进出原则是（ B ）。
A 先进先出B后进先出C栈空则进D栈满则出5、一个队列的入队顺序是w,x,y,z,，则队列的输出顺序是（ A ）。
A w,x,y,zB z,y,x,wC w,z,x,yD x, y,z,w6、稀疏矩阵一般的压缩存储方式有两种，即（C ）。
A 二维数组和三维数组B 三元组和散列C 三元组和十字链表D 散列和十字链表7、设有一个5阶的对称矩阵array采用按行优先压缩存储，array[0][0]为第一个元素，其存储地址为1000，每个元素占3个存储单元，则元素A[4][4]的存储地址为（ A ）。
A 1042B 1052C 1056D 10928、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有右子树，则右子树的根结点是（ B ）。
A A[2i-1] B A[2i+1] C A[i/2] D A[2i]9、设二叉树有n个结点，则其深度为（ D ）。
A n-1B nC ⎣log2n⎦ +1D 不能确定10、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（B ）倍。
一、单项选择题（每小题2分，共30分）1.下列关于栈的叙述中，正确的是（）oA.栈底元素一定是最后入栈的元素B.栈操作遵循先进后出的原则C.栈顶元素一定是最先入栈的元素D.以上三种说法都不对2.在数据结构中，与所使用的计算机硬件无关的是数据的（）结构。
A.逻辑B.存储C.逻辑和存储D.物理3.以下说法正确的是（）oA.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构4.六个元素按照6, 5, 4, 3, 2, 1的顺序入栈，下列哪一个是合法的出栈序列？（）A.546132B. 453126C. 346512D. 2341565.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为（）A.8B. 9C. 10D. 116.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A, （100,80,90,60,120,110,130） B. （100,120,110,130,80, 60,90）C, （100,60,80,90,120,110,130）D, （100,80, 60,90,120,130,110）7.下列陈述中正确的是（）A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分8.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A. eB. 2eC. n2—eD. n2—2e9.栈和队列都是（）A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构10.在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（）A. 2n+lB. 2nC. 2n・lD. 2n-211.在循环双链表的P所指的结点之前插入S所指结点的操作是（）oA.p->prior = s； s->next = p； p->prior->next = s； s->prior = p->priorB.p->prior = s； p->prior->next = s； s->next = p； s->prior = p->priorC.s->next = p； s->prior = p->prior； p->prior = s； p->prior->next = sD.s->next = p； s->prior = p->prior； p->prior->next = s； p->prior = s12,单链表中，增加一个头结点的目的是为了（）oA.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便算法的实现D.说明单链表是线性表的链式存储13,对一个满二叉树，m个叶子，n个结点，深度为h,则（）。
计算机学院数据结构与算法分析期末试题答案一、单项选择题（每小题2 分，共20分）1．在下面给出的链式存储结构中，能在O(1)时间内完成在指定结点p之前插入元素x 的结构是为（）。
A）单向链表B）单向循环链表C）带表头的单向链表D）双向循环链表参考答案：D）2．栈应用的典型事例是（）。
A）排队B）查找C）归并D）用“算符优先法”进行表达式求值参考答案：D）3．一般情况下，将递归算法转换成等价的非递归算法应该设置（）。
A）栈B）队列C）堆栈或队列D）数组参考答案：A）4．（）是C语言中"abcd32lABCD"的子串。
A）abed B）d2lAB C）"abcABC" D）"21AB"参考答案：D）5．有一矩阵为A[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a-1,4的地址为（）。
A）111 B）112 C）113 D）125参考答案：B）6．从L=((apple,pear),(banana,orange))中，取出pear元素的表达式为（）。
A）head(tail(L)) B）head(head(tail(L)))C）tail(head(tail(L))) D）head (tail (head(L)))参考答案：D）7．若一个具有N个顶点，K条边的无向图是一个森林（N＞K），则该森林中必有（）棵树。
A）K B）N C）N-K D）1【分析】因为一棵具有n个顶点的树有n-1条边，因此设此森林中有m棵树，每棵树具有的顶点数为v i（l≤i≤m），则：v1+v2+…+v m=N (1)(v1-1)+(v2-1)+…+(v m-1)=K (2)由(1)-(2)可知N-K为森林所含树的棵数。
参考答案：C）8．采用分块查找时，如某线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块，则每块包含（）个结点时，平均查找长度最小。
广州轻工职业学校（大源校区）试卷用纸 第 1 页，共 1 页
专 班级 姓名 学号
注意：广州轻工职业学校（大源校区）
2015-2016学年第二学期《数据结构》期末考试试卷（B 卷）
注 意 事 项
1、请首先按要求在试卷的标封处填写您的专业、姓名、学号和所在的班级名称；
2、请仔细阅读各种题目的回答要求，在规定的位置填写您的答案；
3、不要在试卷上乱写乱画，不要在标封区填写无关内容。
使用对象：15计算机设计班 考试时间：45分钟 考试方式：考查
一、名词解释题（每小题5分，共35分）：
1. 顺序映像
2. 链式映像
3. 数据对象
4. 数据结构
5. 数据类型
6. 抽象数据类型
7. 算法
二、简答题（每小题10分，共30分）：
1. 数据元素与数据项有什么关系？
2. ADT 的特性有哪些？
3. 算法的特性有哪些？
三、论述题（共15分）：
在设计算法时，什么样的算法才是好的算法？
四、项目设计题（共20分）：
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N 块木头，每块木头长度为整数L 个长度单位。
于是他购买了一条很长的、能锯成N 块的木头，即该木头的长度是L 的总和。
但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。
为简单起见，不妨设酬金等于所锯木头的长度。
例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头将木头锯成12和8，花费20；第二次锯木头将长度为12的木头锯成
7和5花费12，总花费32.如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费35（大于32）.
请设计农夫将木头锯成N 块的最少花费。
《数据结构》试卷（B）学号：姓名：日期：一.选择题（每小题2分，共30分，请写在答卷纸上）：1.下面程序的时间复杂为（）。
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}A.O(n)B.O(n2)C.O(n3)D.O(n4)2.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。
A.线性结构B.树型结构C.物理结构D.图状结构3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B.q=p->next；q->data=p->data；p->next=q->next；free(q)；C.q=p->next；p->next=q->next；free(q)；D.q=p->next；p->data=q->data；free(q)；4.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点5.设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
A.BADCB.BCDAC.CDABD.CBDA6.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
数据结构试卷B卷(含答案)-CAL-FENGHAI.-(YICAI)-Company One1《数据结构》试卷B一、填空题（每空1分，共15分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。
不允许插入和删除运算的一端称为。
3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。
4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。
5. 在具有n个单元的循环队列中，队满时共有个元素。
6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。
二、判断正误（判断下列概念的正确性，并作出简要的说明。
）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（）2. 在表结构中最常用的是线性表，栈和队列不太常用。
（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。
（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
三、单项选择题（每小题1分，共20分）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j（ ）5．具有n(n>0)个结点的完全二叉树的深度为 。
《数据结构》 复 习 卷 B
一． 选择题(1*15=15分)
1．算法指的是……..……………………………..…………………..……………（ ） A ．计算机程序 B ．解决问题的计算方法 C ．排序算法
D ．解决问题的有限运算序列
2．某程序的时间复杂度为（3n +n 2+8）, 其数量级表示为.…….……（ ） A ．O （3n ） B ．O （n ） C ．O （n 2） D ．1
3．线性表采用链式存储时，结点的存储地址………………………….…………（ ） A ．必须是不连续的 B ．连续与否均可
C ．必须是连续的
D ．和头结点的存储地址相连续
4．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为…………………………（ ） A ．front=front+1 B ．front=(front+1)%(m-1) C ．front=(front-1)%m D ．front=(front+1)%m
5．若已知一个栈的入栈序列是1 2 3 4 5，不可能有下列那个出栈序列（ ） A ．1 2 3 4 5 B ．1 3 4 2 5 C ．3 4 5 2 1 D ．1 4 2 3 5
6．一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是………………………………………………………………（ ） A. 110 B. 108 C. 100 D. 120
装 订 线
7．一棵二叉树有8个叶子,则度为2的结点个数为…………….. ……..…() A．8 B．2
C．9 D．7
8．一棵深度为5层的二叉树，其结点总数最多不会超过：……….. ……..…() A． 31个 B．36个
C． 72个D．63个
9．串是一种特殊的线性表，其特殊性体现在：………………………( ) A．可以顺序存储 B．串中的每个数据元素仅由一个字符组成C．可以链式存储 D．数据元素可以是多个字符
10．下面程序段的时间复杂度为………..………………..…………….. () y=0;
For(i=1;i<=n;i++)
y++;
A．O(n) B．O(n2)
C．O(sqrt(n)) D．O(1)
11．设有两个串p和q，求q在p中首次出现的位置的运算称作…………（）Ａ．连接B．子串定位操作
C．求子串D．求串长
12．已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（）A．DEBAFC B．DEFBCA
C．DEBCFA D．DEBFCA
13．按照二叉树的定义,具有3个结点的二叉树的状态数为……………….……（）
A. 5
B. 4
C. 3
D. 2
14．将长度为n的单链表链接在长度为m的单链表之后的的时间复杂度为……（） A．O（1） B．O（n）
C．O（m） D．O（m+n）
15．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是…..……（ ） A ．插入 B ．删除 C ．排序 D ．定位 二．填空题(1*20=20分)
1．所有能输入到计算机中并被计算机程序处理的符号总称，被称为___________。
在计算机程序中通常作为一个整体进行考虑和处理的，通常被称为 _____________。
不可分割的、含有独立意义的数据的最小单位，被称为_____________。
2．在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用p 表示为head=__ _。
3． 线性结构包括__________ 、___________、__________、数组、串。
4． 判定顺序表a 为空的条件是：__________________________________。
5． 顺序存储结构的队列称为_________________，链式存储结构的队列称为
________________。
6． 串的存储方式主要分为二种：_____________存储结构和_______________存
储结构。
7．若二叉树有m 个叶结点，则度为2的结点有 个。
8．树中结点的最大层次称为树的_____________。
树中除根结点以外，每个结点都有_____________个前驱和0到多个后继。
9．对于一棵完全二叉树按层次从左到右编号之后，结点i 的左孩子编号为
_________，右孩子编号为__________，其父结点的编号为__________。
10．深度为K 的二叉树，结点最多有 个，最少有 个。
三．综合运用题(5*5=25分)
装 订 线
1．写出按先根序列遍历下面二叉树的结果：
2．4．把下列森林转换为对应的二叉树。
3.已知一棵二叉树的后序扫描序列和中序扫描序列分别为DECBHGFA 和BDCEAFHG ，试画出该二叉树。
4．画出下面树的孩子兄弟表示法。
5．将以下二叉树转换为森林。
四、选择填空（4*5=20分）
已知L 是无头结点的单链表，且p 结点既不是首结点，也不是尾结点，试从下列提供的语句中选出合适的语句序列。
（1）在p 结点后插入s 结点： 。
（2）在p 结点前插入s 结点： 。
（3）在表首插入s 结点： 。
（4）在表尾插入s 结点： 。
（5）删除p 结点： 。
①p->next=s; ②s->next=L; ③free(p)
④s->next=p->next; ⑤L=s;
⑥q->next=p->next; ⑦q=L;
⑧while(q->next!=p)q=q->next; ⑨q ->next=s;
⑩while(q->next!=null)q=q->next;
○
11 s->next=q->next; ○
12 s->next=p;
装 订 线
typedef struct node
{ int data;
struct node *next;
} LINKLIST;
int average(LINKLIST *head)
{
}
2.采用中序递归遍历算法，编制一个求二叉树结点元素总和的函数。
typedef struct node1
{ int data;
struct node1 *lchild,*rchild;
}BTCHINALR;
int sum(BTCHINALR *bt)
{
3．编写算法：已知线性链表head，在p指针所指向的结点后插入一个元素x。
}。
