山大网络《数据结构》试卷( A 卷)上课讲义

122-《数据结构》试卷A参考答案
烟台大学成人高等教育期末考试《数据结构与算法》试卷A 参考答案及评分标准
一、
1．算法的特征：有穷性、确定性、可行性、有输入、有输出。

算法设计的要求：正确、可使用、可读、健壮、高效。

2．数据元素之间的逻辑结构：集合、线形、树形、图形结构
逻辑结构的本质性：数据结构在用户面前的呈现形式，数据元素之间的邻接关系的描
述，与数据的存储无关，独立于计算机。

3．抽象数据类型：
数据元素描述
数据之间的逻辑关系描述
施加在数据上的基本操作
4．（1）链式存储；插入、删除操作频繁，适合链式存储的特点。

（2）顺序存储：数据移用少，随机存储，适合顺存储特点
5. （1）需要求解的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法
与原问题相同，只是规模减小。

（2）递归调用的次数是有限的。

（3）必须有结束递归的条件。

二、
1．n-i+1
2. a b c a b c a a a
-1 0 0 0 1 2 3 4 1
3. GetHead((a,b,c))=(a,b,c)
GetHead(GetTail((a,b),(c,d )))=(c,d)
4. 15
5. 图。

山东大学数据结构（一）一、单选题（每题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层的结点数最多为( ).A．2k-1 +1 C.2K-1 D. 2k-17.如有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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

.6 C二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时刻复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

山大网络教育《数据结构》( A 卷)《数据结构》模拟卷一、选择题1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。

A. O(n)B. O(n/2)C. O(1)D. O(n) 22. 带头结点的单链表first为空的判定条件是：（ B ）。

A. first == NULL;B. first->link == NULL;C. first->link == first;D. first != NULL;3. 从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构4. 在系统实现递归调用时需利用递归工作记录保存实际参数的值。

在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ），在被调用程序中可直接操纵实际参数。

A. 空间B. 副本C. 返回地址D. 地址5. 以下数据结构中，哪一个是线性结构（ D ）。

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串6. 以下属于逻辑结构的是（ C ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表7. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。

A. 20B. 18C. 25D. 228. 在有向图中每个顶点的度等于该顶点的（ C ）。

A. 入度B. 出度C. 入度与出度之和D. 入度与出度之差9. 在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

A. 起泡排序B. 希尔排序C. 归并排序D. 快速排序10. 当α的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。

1。

………………………………………………密………………………………封………………………………线………………………………山东大学 2018-2019 学年 一 学期 数据结构 课程试卷A题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷人得分学院 专业 级 学号 姓名一、线性结构（30分）。

1、已知线性表：（8，9，2，13，0，7，1，6，5），请完成以下题目。

⑴请描述公式化描述及链表描述的空间需求。

如果需要删除元素13，请描述各自的时间复杂度。

⑵ 请分别进行选择排序、插入排序、快速排序（以8为轴），并给出第一轮排序结束后各自的结果。

⑶ 设计散列表，散列函数为H （k)=k%7，散列表长度为11，请给出线性开型寻址的散列表。

⑷ 基于以上散列表，查找元素1，给出需要的查找次数。

⑸若使用单链表存储上述线性表，请阅读以下程序，并给出程序运行结果及其时间复杂度。

二、层次结构（35分）。

1. 二叉树的层次遍历序列为ABCDEFGHIJ ，中序遍历序列为DBGEHJACIF ，写出该二叉树的前序遍历序列。

2. 一个最大堆为（66，37，41，30，25，40，35，18），依次从中删除两个元素，写出最后得到的堆。

3. 有一份电文中共使用6个字符：A 、B 、C 、D 、E 、F ，它们的出现频率依次为10、6、5、2、15、4，试画出对应的赫夫曼树（请按左子树根节点的权小于等于右子树根节点的权的次序构造，左0右1），并求出每个字符的赫夫曼编码。

4. 对给定输入序列{ 19, 5, 7, 11, 26, 18, 16, 17 },构建AVL 树。

5. 在下列5阶B-树中首先插入关键字85，然后删除关键字70，画出插入元素和删除元素后的B-树。

三、网状结构（35分）。

1. 请给出从加权无向图中生成最小耗费生成树的两种方法，请分别描述其算法思想，并给出各自的时间复杂度。

2. 下面是某有向加权图(顶点A,B,C,D,E)的耗费邻接矩阵，先给出一个拓扑序列，然后，使用Dijkstra算法依次计算出顶点A 至其它各顶点的最短路径和最短路径长度。

《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。

6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。

7. 树的根结点的度为______，度为0的结点称为______。

8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。

三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。

10. 简述二叉树的遍历方法。

11. 简述图的存储结构及其特点。

四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。

13. 编写一个算法，实现队列的出队操作。

五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。

15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。

答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。

９，IP协议提供的服务是（）。

A、尽最大努力传递B、可靠的C、面向连接的D、虚电路１０，网络中，用于报告错误和测试的协议为（）。

A、NATB、OSPFC、ICMPD、RIP三、填空题（每题0.5分，共8分）。

1.网络可以有多种分类标准，按照覆盖范围（距离）这个标准，网络可以分为＿＿＿＿、城域网和＿＿＿＿。

2.服务质量用来描述网络能够提供的服务能力或网络应用的要求，网络中经常使用的服务质量参数有＿＿＿＿、＿＿＿＿、＿＿＿＿与＿＿＿＿等。

3.无线局域网对应的IEEE标准为＿＿＿＿＿＿＿＿，宽带无线网络对应的IEEE标准为＿＿＿＿＿＿＿＿。

4.网络中常见的调制方式有＿＿＿＿、＿＿＿＿与＿＿＿＿。

5.TCP协议中校验和校验的范围包括＿＿＿＿、＿＿＿＿和＿＿＿＿＿＿。

6.在以太网中发生冲突后，经常采用＿＿＿＿＿＿＿＿来解决冲突。

7.IP协议中有一个＿＿＿＿＿＿＿＿字段，用于限制分组在网络上的存活时间，避免分组无休止的在网络上循环。

四、简答计算题（每题5分，共20分）1.网络使用CRC校验。

假设使用的生成式为10011，计算发送数据1101011111的校验和。

2.漏桶和令牌桶是网络中用于流量整形的主要方法。

根据所学知识，回答下面问题：五、论述题（每题8分，共32分）1.滑动窗口协议是数据链路层的一个重要协议，提供在一条不可靠的线路上可靠的数据递交。

根据所学知识，回答下述问题：1）发送窗口和接收窗口的含义是什么？2）滑动窗口是如何提供流量控制的？山东大学 2014-2015 学年 2 学期 计算机网络（A ）课程试卷………………………………第 3页 共 4 页4. 地址解析协议（ARP ）是网络层一个重要的协议。

根据所学知识，回答下面问题：1）ARP 协议的目的是什么？2）依据给定内容，完成表格各项，并简述ARP 协议的工作过程。

六、综合题（20分）。

主机H通过以太网连接Internet，IP地址为194.170.0.10，服务器S的IP地址为210.32.70.80。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

年级________；层次________；专业________；姓名________复习资料，自我完善，仅供参考，考完上交！ 《数据结构》试卷（A 卷）一、选择题1. 数据结构是指（A ）。

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

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ D ）。

A.一对一关系B.多对多关系C.多对一关系D.一对多关系4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（B ）。

for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n )C.O(n)D.O(3n ) 5. 算法分析的目的是（1） C ，算法分析的两个主要方面是（2） A 。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6. 计算机算法指的是（1） C ，它具备输入，输出和（2） B 等五个特性。

（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ）。

A.低B.高C.相同D.不好说。