深圳大学 数据结构 树作业

第九章查找一、基本概念（共40分，每题4分）1、具有12个关键字的有序表，折半查找的平均查找长度________.A、3.1B、4C、2.5D、52、下面关于折半查找的叙述正确的是________A、表必须有序，表可以顺序方式存储，也可以链表方式存储B、表必须有序，而且只能从小到大排列C、表必须有序且表中数据必须是整型，实型或字符型D、表必须有序，且表只能以顺序方式存储3、与其他查找方法相比，散列查找法的特点是_______。

A．通过关键字的比较进行查找B．通过关键字计算元素的存储地址进行查找C．通过关键字计算元素的存储地址并进行一定的比较进行查找D．以上都不是4、适用于折半查找的表的存储方式及元素排列要求为______________。

A.链式方式存储，元素无序B.链式方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序5、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则折半查找元素55需要比较______次。

A．1 B．2 C．3 D．46、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较______次。

A．3 B．4 C．5 7、 D．67、若对数据集{23,44,48,36,52,73,64,58}建立散列表，采用H(k)=k MOD 13计算散列地址，并采用链地址法处理冲突，则元素64的散列地址为。

8、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中。

这种方式主要适合于_______。

A．静态查找表B．动态查找表C．静态查找表与动态查找表D．两种表都不适合9、在线性表的哈希存储中，处理冲突有________________和________________两种；装填因子的值越大，存取元素时发生冲突的可能性就________________，装填因子的值越小，存取元素时发生冲突的可能性就________________。

数据结构第二次作业一、单选题 (共100.00分)1. 数组的存储方式有以下两种（）A. 顺序表和链表B. 堆栈和队列C. 行优先和列优先D. 对称矩阵和三角矩阵正确答案：C2. 广义表的表头是指（）A. 表中第一个元素B. 表中最后一个元素C. 除表中第一个元素以外，其余元素组成的子表D. 除表中最后一个元素以外，其余元素组成的子表正确答案：A3. 广义表的表尾是指（）A. 表中第一个元素B. 表中最后一个元素C. 除表中第一个元素以外，其余元素组成的子表D. 除表中最后一个元素以外，其余元素组成的子表正确答案：C4. 已知二维数组有4行5列，首元素的数组下标为a00，则数组最后一个元素的数组下标是（）A. a44B. a55C. a45D. a34正确答案：D5. 已知对称矩阵有4行4列，必定与元素a23相等的元素是（）A. a32B. a33C. a00D. a22正确答案：A6. 已知矩阵A有4行5列，矩阵首元素下标为[0,0]，每个元素使用4个字节，现用一维数组B存储该矩阵，数组B的内存首址为10000，若采用行序为主，矩阵元素A[3, 2]在内存的地址是（）A. 10052B. 10068C. 10005D. 10020正确答案：B7. 已知广义表L=((x,y,z),a,(u,t,w))，假设head表示取表头运算，tail表示取表尾运算，求head(tail(L))的结果是（）A. uB. (x)C. aD. (u, t, w)正确答案：C8. 以下哪一种是串在计算机中的常见表示方式（）A. 定长顺序B. 堆分配C. 块链D. 前三种都是正确答案：D9. 在数据结构中，串可以等同于（）的处理A. 整数串B. 浮点数串C. 字符串D. 多种类型的数组正确答案：C10. 以下哪一种是串匹配的常用算法（）A. 普里姆算法B. 克鲁斯卡尔算法C. KMP算法D. 关键路径算法正确答案：C已知主串为abcbcaddabc，模式串为cad，假设串位置从1开始，则串匹配位置是（）A. 3B. 5C. 7D. 不存在正确答案：B12. 已知串S的内容为1+2+3，以下描述哪一个是正确的（）A. 串S的长度是6B. 串S的运算结果是6C. 整数1是串S的子串D. 符号+是串S的子串正确答案：D以下描述哪一个是正确的（）A. 串是字符有限序列B. 串是整数、浮点数、字符等多种数据的有限序列C. 只包含空格的串称为空串D. 串只能使用顺序表存储正确答案：A串函数Sub(S, x, y)表示在串S中，从x位置开始，取出y个字符，串位置从1开始计算。

数据结构大作业在计算机科学领域中，数据结构是非常重要的一个概念。

它是指组织和存储数据的方式，以及对数据进行操作的方法。

数据结构的选择与实现直接影响着算法的复杂度和程序的性能。

因此，在学习数据结构的过程中，一般都会有相应的大作业，以帮助学生更好地理解和应用所学的知识。

本篇文章将重点介绍数据结构大作业的一般要求和一种可能的实现方案，供读者参考。

一、数据结构大作业要求数据结构大作业一般旨在让学生将所学的数据结构知识应用于实际问题的解决。

作业要求通常包括以下几个方面：1. 题目选择：作业题目需要涵盖数据结构的各个方面，例如链表、栈、队列、树、图等等。

题目应具备一定的难度，能够考察学生对数据结构的理解和运用能力。

2. 实现方式：学生需要根据题目要求选择合适的数据结构和算法，并进行实现。

一般要求使用编程语言来完成实现，并给出相应的代码。

3. 功能要求：作业题目通常会要求实现某些特定的功能或解决某些问题。

学生需要确保所实现的程序能够满足这些功能需求，并能正确运行。

4. 性能评估：作业可能会要求对所实现的程序进行性能评估，比如时间复杂度、空间复杂度等。

学生需要能够分析和解释程序的性能，并对可能的改进方法进行讨论。

5. 报告撰写：作业一般要求学生完成一份报告，对所实现的程序进行详细的说明和分析。

报告需要包括程序设计思路、实现细节、运行结果以及遇到的问题和解决方法等。

二、数据结构大作业实现方案示例以下是一个可能的数据结构大作业实现方案示例，以一个简化的社交网络系统为题目：1. 题目描述：设计一个基于图的社交网络系统，能够实现用户的注册、好友关系的建立和查询、用户之间的消息传递等功能。

2. 数据结构选择：可以使用图的数据结构来存储用户和好友关系的信息，使用链表来存储用户的消息队列。

3. 算法实现：根据题目要求，需要实现用户注册、好友关系的建立和查询、消息传递等功能的算法。

可以使用深度优先搜索或广度优先搜索算法来查找用户的好友关系，使用链表来实现用户消息的发送和接收。

7.3.习题自测第一章数据结构绪论1. 写出算法的特征2. 写出for (i=n; i>0; i/=2); 的时间复杂度第二章线性表1. 循环队列的队首和队尾下标分别为f, r, 最大长度为n, 写出判断队满和队空的条件2. 向量A中已有n个元素，写出删除其第i个位置元素的算法3. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？4. 设线性表的n个结点定义为(a0,a1,…,an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList。

5. 设A和B是两个单链表，其表中元素递增有序。

试写一算法将A和B归并成一个按元素值递增有序的单链表C。

第三章栈和队列1. 设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：⑴. 若入、出栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Pop()，Push(4)，Pop()，则出栈的数字序列为何（这里Push(i)表示进栈，Pop()表示出栈）？⑵. 能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。

⑶. 请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

第四章串1. 现有模式abaabc，写出每个字母的next值。

2. 假设主串abcabadabaabc，模式串如上，说明kmp算法的匹配过程。

3. 回文是指正读和反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。

试写一个算法判定给定的字符向量是否为回文。

（提示：将一半字符入栈）。

第六章树与二叉树1. 若二叉树的先序和中序遍历结果分别是a, b, d, e, c, f, g, h和d, e, b, a, f, c,h, g, 求其后序遍历的结果2. 二叉树的中序和后序遍历结果分别为4, 5, 2, 1, 6, 3, 8, 7和5, 4, 2, 6, 8, 7, 3,1, 求其先序遍历的结果3. 树用孩子兄弟链接法存储，结点结构为：struct Node {char data, struct Node *child, *brother;}写C函数void PreOrder(struct Node *root), 先根遍历树。

深圳⼤学数据结构作业汇总⼀⑴、判断题1、线性表的特点是每个元素都有⼀个前驱和⼀个后继。

（）2、数据的物理结构是指数据在计算机内的实际存储形式。

（）3、数据的逻辑结构说明数据元素之间的次序关系,它依赖于计算机的存储结构（）⼀⑵、选择题1、⼀个算法应该是（）A、问题求解步骤的描述B、程序C、要满⾜五个基本特性D、A和B2、以下数据结构中，（）是⾮线性数据结构A、树B、字符串C、队D、栈3、完成在双循环链表结点p之后插⼊s的操作是（）A、 p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B、 p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;C、 s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D、 s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;4、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A、O(n) O(n)B、O(n) O(1)C、O(1) O(n)D、O(1) O(1)5、设⼀个链表最常⽤的操作是在末尾插⼊结点和删除尾结点，则选⽤( )最节省时间。

A、单链表 B.单循环链表 C、带尾指针的单循环链表 D.带头结点的双向循环链表⼀⑶、填空题1、for (j=1; j<=n; j*=2); 的时间复杂度为。

2、在线性结构中，除第⼀个结点外，每个结点都有⼀个结点，除最后⼀个结点外，每个结点都有⼀个结点。

3、数据逻辑结构包括集合和、、四种。

4、for (j=n; j>=1; j/=2); 的时间复杂度为。

深圳⼤学数据结构树作业数据结构作业⼆（第5-6章：树与⼆叉树,数组和⼴义表）要求：请在2017年11⽉9⽇机房交，迟交适当减分。

⼀、单选题：（每题2分,共12分）1、假设在⼀棵⼆叉树中，双分⽀结点数为15，单分⽀结点数为30个，则叶⼦结点数为______个。

A.15B.16C.17D.472、在⼀棵⼆叉树上第4层的结点数最多为______。

A.2B.4C.6D.83、任何⼀棵⼆叉树的叶⼦结点在先序中序和后序遍历序列中的相对次序___。

A.不发⽣改变B.发⽣改变C.不能确定D.以上都不对4、根据先序序列A B D C和中序序列DB A C确定对应的⼆叉树，该⼆叉树____。

A.是完全⼆叉树B.不是完全⼆叉树C.是满⼆叉树D.不是满⼆叉树5、设森林F中有三棵树，第⼀、第⼆和第三棵树的结点个数分别为N1、N2 和N3。

与森林F对应的⼆叉树根结点的右⼦树上的结点个数是_______。

A.N1B.N1+N2C.N2D. N2+N36.⼀个⼴义表的表头总是⼀个_______。

A.⼴义表B. 元素C. 空表D.元素或⼴义表⼀、简答题：（每空2分,共30分）1.对于⼀棵具有n个结点的树，该树中所有结点的度数之和为。

2.对于⼀棵⼆叉树，若⼀个结点的编号为i，若它的左孩⼦结点存在,右孩⼦结点存在,双亲结点存在,则编号分别为：。

3．设T是⼀棵⼆叉树，除叶⼦结点外，其它结点的度数皆为2，若T中有6个叶结点，则T树的最⼤深度和最⼩可能深度分别为。

4．设给定权值总数有n个，其哈夫曼树的结点总数为：。

5.若⼀棵完全⼆叉树具有35个结点，该树的深度为。

6.在⼀棵⼆叉树的⼆叉链表中，空指针域数是⾮空指针域数：。

7．由3个结点可以构造出种不同形态的⼆叉树，其中树⾼为3的⼆叉树有个。

8.线索⼆叉树中的线索指。

9.在哈夫曼编码中，若编码长度只允许⼩于或等于4，则除了已知两个字符编码为0和10外，还可以最多对个字符编码。

10.⼴义表A=((x,(a,B)),(x,(a,B),y))，则运算h e a d(h e a d(t a i l(A)))的结果为。

数据结构大作业平衡二叉树是一种特殊的二叉树结构，在插入或删除节点时，通过旋转操作来保持树的平衡性，从而提高查找、插入或删除操作的效率。

平衡二叉树的一种常见实现方式是AVL树。

AVL树是由俄罗斯数学家Adelson-Velsky和Landis于1962年提出的，它是一种自平衡的二叉树。

在AVL树中，每个节点的左右子树的高度之差（也称为平衡因子）不超过1、当插入或删除节点后导致一些节点的平衡因子超过1时，就需要通过旋转操作进行平衡调整。

具体来说，插入节点时，需要首先将节点插入到AVL树的合适位置。

然后，自底向上地检查每个节点的平衡因子。

如果发现一些节点的平衡因子超过1，则需要进行相应的旋转操作，使树重新恢复平衡。

旋转操作有四种基本情况，分别是LL、RR、LR和RL旋转。

LL旋转发生在一些节点的左子树的左子树上，RR旋转发生在一些节点的右子树的右子树上，LR旋转发生在一些节点的左子树的右子树上，RL旋转发生在一些节点的右子树的左子树上。

通过这些旋转操作，可以使树重新平衡。

删除节点时，需要先找到待删除的节点，并根据其子树的情况进行删除操作。

然后，从被删除节点的父节点向上检查每个节点的平衡因子，如果发现不平衡的节点，也需要进行相应的旋转操作。

AVL树的平衡调整是通过旋转操作来实现的，旋转操作的时间复杂度为O(1)，因此平衡调整的时间复杂度为O(logn)，其中n为树的节点数。

平衡二叉树的优点是能够保持树的平衡性，提高查找、插入、删除等操作的效率。

总结起来，平衡二叉树是一种特殊的二叉树，通过旋转操作来保持树的平衡性，从而提高查找、插入或删除操作的效率。

AVL树是一种常见的平衡二叉树实现方式，通过LL、RR、LR和RL旋转来使树重新平衡。

平衡二叉树的优点是能够保持树的平衡性，提高操作的效率。

数据结构第一次作业一、单选题 (共100.00分)1. 已知栈S为空，数据1、2、3、4依次逐个进入栈S，则栈顶数据为（）A. 1B. 2C. 3D. 4正确答案：D2. 栈的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：B3. 队列的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：A4. 已知栈包含10元素，其中存放在栈底是第1号元素，则第10号元素可以通过（）进行访问A. 栈底B. 栈中C. 栈尾D. 栈顶正确答案：D5. 以下结构中，哪一个是属于物理结构（）A. 栈B. 队列C. 链队列D. 线性表正确答案：C6. 使用长度为10的数组实现循环队列，则该队列最多存储数据个数为（）A. 1B. 9C. 11.D.5正确答案：B7. 已知顺序表包含1000个数据，现在第88号位置插入新的数据，需要移动的数据个数为（）A. 88B. 87C. 912D. 913正确答案：D8. 若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是（）A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案：D9. 以下结构中，哪一个是属于物理结构（）A. 线性表B. 栈C. 单链表D. 队列正确答案：C10. 已知顺序表包含100个数据，现在要删除第99号位置的数据，需要移动的数据个数为（）A. 99B. 100C. 1D. 2正确答案：C已知指针p指向单链表L的某个结点，判断p指向的结点是尾结点的条件是（）A. if (p->next>p)B. if (p->next==NULL)D. if (p->data==0)正确答案：B12. 以下描述哪个是正确的（）A. 线性表的数据元素的存储位置一定是连续的B. 顺序表的数据元素的存储位置一定是连续的C. 链表的数据元素的存储位置一定不是连续的D. 线性表的数据元素的存储位置一定不是连续的正确答案：B已知顺序表包含100个数据，先在第15号位置插入1个新数据，接着删除第3号位置的数据，需要移动的数据总个数为（）A. 18B. 84C. 184D. 188正确答案：C在数据结构概念中，数据的基本单位是（）A. 数据段B. 数据项C. 数据表D. 数据元素D在数据结构概念中，结构是描述（）A. 数据项的类型B. 数据元素之间的关系C. 数据成员的先后顺序D. 数据对象的取值范围正确答案：B在算法设计中，要求算法便于理解和修改是属于算法要求的（）A. 正确性B. 可读性C. 健壮性D. 效率高正确答案：B以下关于算法的描述，哪个是正确的（）A. 算法可以没有输入B. 算法可以包含无限个执行步骤C. 算法可以没有输出D. 算法的每个步骤允许带有歧义的正确答案：抽象数据类型ADT通过三方面描述，包括数据关系、数据操作和（）A. 数据对象B. 数据来源C. 数据范围D. 数据判断正确答案：A设n为问题规模，以下程序的时间复杂度为（）for (i=1; i<=10000; i++) for (j=1; j<=n; j++) a = a + 1;A. O(1)B. O(n)C. O(10000n)D. O(n2)正确答案：B20.设n为问题规模，以下程序的时间复杂度为（） for (i=1; i< POW（2, n）; i++) //POW(x, y)函数表示x的y次幂a = a+100;A. O(n)B. O(2n)C. O(n!)D. O(2n)正确答案：D。

2022年深圳大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。