山东大学数据结构第4-7章作业

习题答案1.填空题（1）非线性、一对多（2）前驱（3）叶结点（叶子结点）（4）度数（5）两（6）满二叉（7）从根结点到该结点之间的路径长度与该结点的权值的乘积（8）树中所有叶结点的带权路径长度之和（9）递增（10）平衡因子（11）B树的阶2.选择题（1）B （2）D （3）A （4）C （5）B （6）A （7）D （8）D3.思考题（1）如果i=1，则结点i无双亲，为根结点。

如果i>1，则结点i的双亲结点是结点i/2。

如果2i≤n，则结点i的左孩子是结点2i，否则结点i为叶结点。

如果2i+1≤n，则结点i的右孩子是结点2i+1，否则结点i无右孩子。

（2）非叶结点最多只有M个孩子，且M>2。

除根结点以外的非叶结点都有k个孩子和k-1个数据元素，k值满足[M/2]≤k≤M。

每一个叶结点都有k-1个数据元素，k值满足[M/2]≤k≤M。

所有叶结点都在同一层次。

所有分支结点的信息数据一致（n,A0,K1,A1,K2,A2……K n,A n），其中：K i（i=1,2……n）为关键字，且K i<K i+1（i=1,2……n-1）；A i为指向孩子结点的指针，且指针A i−1指向子树中的所有结点均小于K i，A n所指子树中的所有结点的关键字均大于K n；n为关键字的个数（[M/2]-1≤n≤M-1）。

（3）B+树是B树的升级版，区别在于叶结点在B+树的最底层（所有叶结点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。

叶结点按照关键字的大小，从小到大顺序链接。

分支结点不保存数据，只用来作索引，所有数据都保存在叶结点。

B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶子结点上增加了指向兄弟结点的指针。

4.编程题（1）1//参数1为树的结点个数，参数2起始结点编号2btree_t *btree_create(int n, int i){3 btree_t *t;4 //使用malloc函数为结点申请内存空间5 t = (btree_t *)malloc(sizeof(btree_t));6 //将结点编号作为数据，保存至data中7 t->data = i;89 if(2 * i <= n){ //满足条件，说明结点有左孩子，编号为2i10 //递归调用，为左孩子的创建申请空间11 t->lchild = btree_create(n, 2 * i);12 }13 else{ //不满足条件，则没有左孩子14 t->lchild = NULL;15 }1617 if(2 * i + 1 <= n){ //满足条件，说明结点有右孩子，编号为2i+118 //递归调用，为右孩子的创建申请空间19 t->rchild = btree_create(n, 2 * i + 1);20 }21 else{ //不满足条件，则没有右孩子22 t->rchild = NULL;23 }2425 return t;26}。

数据结构第四五六七章作业答案数据结构第四、五、六、七章作业答案第四、五章一、填空题1.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2.设s=“a;/document/mary.doc”，则strlen(s)=20,“/”的边线为3。

3.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

4、串成的存储方式存有顺序存储、堆上分配存储和块链存储5、有一个二维数组a[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素a[0,1]的地址是100，若按行主顺序存储，则a[3,5]的地址是176和a[5,3]的地址是208。

若按列存储，则a[7,1]的地址是128，a[2,4]的地址是216。

6、设立数组a[1…60,1…70]的基地址为2048，每个元素占到2个存储单元，若以列序居多序顺序存储，则元素a[32,58]的存储地址为8950。

7、三元素组表中的每个结点对应于稠密矩阵的一个非零元素，它涵盖存有三个数据项，分别则表示该元素的行负号、列于负号和元素值。

8、二维数组a[10][20]使用列序居多方式存储，每个元素占到10个存储单元，且a[0][0]的存储地址就是2000，则a[6][12]的地址就是32609、已知二维数组a[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且a[10][5]的存储地址是1000,则a[18][9]的存储地址是116810、已知二维数组a[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且a[0][0]的存储地址是1024,则a[6][18]的地址是130011、两个串相等的充分必要条件是长度相等、对应位置的字符相同。

12、二维数组a[10][20]使用列序居多方式存储，每个元素占到一个存储单元，并且a[0][0]的存储地址就是200，则a[6][12]的地址就是200+（12*10+6）=326。

2020年山东大学数据结构课后作业答案山东大学继续(网络)教育学院---数据结构课后作业答案一、单选题（共20题,50.0分）1、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A、O(n)B、O(n/2)C、O(1)D、O(n2)我的答案：A得分：2.5分2、带头结点的单链表first为空的判定条件是：（）。

A、first == NULL;B、first->link == NULL;C、first->link == first;D、first != NULL;我的答案：B得分：2.5分3、从逻辑上可以把数据结构分为（）两大类。

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

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

A、空间B、副本C、返回地址D、地址我的答案：D得分：2.5分5、以下数据结构中，哪一个是线性结构（）。

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

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

A、20B、18C、25D、22我的答案：C得分：2.5分8、在有向图中每个顶点的度等于该顶点的（）。

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

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

第一章作业第章作试编个递归数来输个素的 5. 试编写一个递归函数，用来输出n 个元素的所有子集。

例如，三个元素{a, b, c} 的所有子集是：{ }（空集），{a}, {b}, {c}, {a, b}, {a, c}, {,}{,,}b, c} 和a, b, c。

基本思想：用一个一维数组x[1:n]表示大小为n的数组的一个子集。

如果第j个元素包含在子集中，那么x[j]=1 ，否则x[j]=0；x[j]0例如原数组为{a,b},那么他的子集为{0，0}，{0，1}，{1，0}，{1，1}。

分别对应子集{Ø}，{}{}{}{b},{a},{a,b}．函数实现：#include <iostream.h>// 定义全局变量，ｎ在主函数种初始化//定义全局变量在主函数种初始化int x[20], // 子集向量，假设大小为20n; // 数组元素个数void Subsets(int i，int n){// 输出数组a[i:n].的所有子集只有[]在每次递归调用时改变[],被确定为了或// x[i:n] 在每次递归调用时改变，x[1:i-1],已经被确定为了0 1 if (i == n) {// x[n] 可以是0或1// 输出不包含元素n的子集x[n] 0;x[n]=0;for (int j = 1; j <= n; j++)cout << x[j] << " ";cout << endl;cout<<endl;//输出包含元素n的子集x[n] = 1;[]1for (j = 1; j <= n; j++)cout << x[j] << " ";cout << endl;return;// 子集中不包含元素ｉ的情况x[i] = 0;// 递归调用产生不含有元素ｉ的所有子集Subsets(i+1,n);//子集中包含元素ｉ的情况x[i] 1;x[i]=1;//递归调用产生含有元素ｉ的所有子集Subsets(i+1,n);Subsets(i+1n);}#include <iostream>int x[100]; // 子集向量，假设大小为100int x[100];//template <class T>void Subsets(int i ,int n ,T a[]){// 输出数组a[i:n].的所有子集{//a[i:n]// 只有x[i:n] 在每次递归调用时改变，x[1:i-1],已经被确定为了0 或1 if (i == n) {// x[n] 可以是0或1//// 输出不包含元素n的子集x[n] = 0;int temp=0;for (int j = 1; j <= n; j++)f(){ if(x[j]!=0) {cout << a[j] << " ";temp=1;}} if(temp==0)cout<<"空集";cout << endl;输出包含元素的子集//nx[n] = 1;for (j = 1; j <= n; j++) { if(x[j]!=0) cout << a[j] << " ";} cout << endl;cout<<endl;return;}// 子集中不包含元素ｉ的情况x[i] = 0;// 递归调用产生不含有元素ｉ的所有子集Subsets(i+1,n,a);//子集中包含元素ｉ的情况x[i] 1;x[i]=1;//递归调用产生含有元素ｉ的所有子集Subsets(i+1,n,a);Subsets(i+1n a);}void main(void){cout<<"输入数组大小n=";int n;;cin>>n;while(n>100){cout<<"请输入一个在1到100内的数"<<endl;cin>>n;}cout<<"输入"<<n<<"个数组元素：";输个数元素;char y[n+1];//实例化for(int i=1;i<=n;i++)i[i]cin>>y[i] ;Subsets(1,n,y);}第三章习题2.假设一个线性表的描述满足公式（3-1）类的定义增加个函数1)扩充LinearList类的定义，增加一个函数Reverse，该函数将表中元素的次序变反。

第4章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。

A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。

A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。

A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。

A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。

A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。

A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。

A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。

A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。

A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。

第七章习题答案1.填空题(1) 平均查找长度(2) 哈希查找(3)顺序 有序(4)越大(5) 21(n + 1) (6)开放定址法 拉链法(7)3(8)2(9)中序(10)建表2.判断题（1）×（2）×（3）√（4）√（5）√（6）√（7）√（8）√（9）×（10）×3.简答题（1）①表中只有一个关键字等于给定值k 的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。

②无序表：顺序查找不成功时，平均查找长度为n+1；有序表，平均查找长度为1/(n+1)*(1+2+…+(n+1))=(n+2)/2；两者不相同。

③表中只有m 个关键字等于给定值k 的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m ；两者不相同。

（2）（3H(22)=(22 mod 7)+1=2 H(8)=(8 mod 7)+1=2 H(34)=(34 mod 7)+1=7 H(19)=(19 mod 7)+1=6 H(21)=(21 mod 7)+1=1 H(29)=(29 mod 7)+1=2 ①0 1 2 3 4 5 6 7 8②1 2 3 4 5 6 7 8 ③4.（1）int SeqSearch(RecordType r, int n, KeyType k){ i=0;r[n].key=k;while (r[i].key!=k) i++;if (i<n) return n;else return -1;}(2)KeyType MaxNode (BSTree bt){ if (bt!=NULL){ f=bt;while (bt->rchild!=NULL){ f=bt; bt=bt->rchild;}return f->key;}}(3)int level(BSTree bt, KeyType k){ d=0;if (bt==NULL) return 0; //空树深度为0else{ d++; //根结点深度为1while (bt->data!=k){ if (bt->data<k) bt=bt->rchild; //右子树中查找else bt=bt->rchild; //左子树中查找d++;}return d;}(4)#define N 50int IsBSTree(BSTree bt){BSNode *stack[N],*p;KeyType k;int isbst，top;isbst=1; //标志变量，首先假定bt是二叉排序树top=-1; //置空栈p=bt; //p从根出发while (isbst && (p!=NULL || top!=-1)){while ((p!=NULL){k=p->key;if (p->lchild->key>k || p->rchild->key<k){ isbst=0; break;}if (p->rchild!=NULL)stack[++top]=p->rchild;p=p->lchild;}if (top!=-1)p=stack[top--];}return isbst;}(5)BSTree BSTDeleteAll(BSTree t, KeyType k){BSTree p;p=BSTSearch1(t,k); //查找关键字值不小于x的结点while (p!=NULL){ t=BSTDelete(t,p); //删除p所指示结点p=BSTSearch1(t,k);}}注：函数BSTSearch1，BSTDelete参阅教材§7.3.3,§7.3.4。

第3章数据结构3．1数据结构的基本概念一、部分例题及解题思路选择题1.数据结构是指（）。

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

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

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

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），算法分析的两个主要方面是（2）。

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

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

A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。

A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。

A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。

A.数据B.数据元素C.数据项D.数据库填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。

数据结构第四章的习题答案数据结构第四章的习题答案在学习数据结构的过程中，习题是非常重要的一环。

通过解答习题，我们可以更好地理解和应用所学的知识。

在第四章中，我们学习了树和二叉树的相关概念和操作。

下面我将为大家提供一些第四章习题的答案，希望能帮助大家更好地掌握这一章节的内容。

1. 请给出树和二叉树的定义。

树是由n(n>=0)个结点构成的有限集合，其中有且仅有一个特定的结点称为根结点，其余的结点可以分为若干个互不相交的有限集合，每个集合本身又是一个树，称为根的子树。

二叉树是一种特殊的树结构，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。

二叉树具有递归的定义，即每个结点的左子树和右子树都是二叉树。

2. 请给出树和二叉树的遍历方式。

树的遍历方式包括前序遍历、中序遍历和后序遍历。

前序遍历是先访问根结点，然后依次遍历左子树和右子树。

中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历是先遍历左子树和右子树，最后访问根结点。

二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。

前序遍历是先访问根结点，然后依次遍历左子树和右子树。

中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历是先遍历左子树和右子树，最后访问根结点。

3. 给定一个二叉树的前序遍历序列和中序遍历序列，请构建该二叉树。

这个问题可以通过递归的方式解决。

首先，根据前序遍历序列的第一个结点确定根结点。

然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。

接下来，分别对左子树和右子树进行递归构建。

4. 给定一个二叉树的中序遍历序列和后序遍历序列，请构建该二叉树。

和前面的问题类似，这个问题也可以通过递归的方式解决。

首先，根据后序遍历序列的最后一个结点确定根结点。

然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。

1数据结构的形式定义是（D, S），其中D是数据元素的有限集，S是D上的关系有限集。

（答案）对2在数据结构中，从层次上可以把数据结构分成（答案）逻辑结构和存储结构3线性表若采用链式存储结构时，要求内存中可用的存储单元的地址（答案）连续不连续都可以4下面程序的时间复杂度为（答案）O（m×n）5若需要利用形参直接访问实参，则应把形参变量说明为参数。

（答案）引用第二章测试1带头结点的单链表L为空的判定条件是（答案）L→next= =NULL2非空的循环单链表L的尾结点（由p所指向）满足（答案）p→next= =L3在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行。

（答案）p→next=s; s→next=q4在一个单链表中，若删除p所指结点的后继结点，则执行（答案）q=p→next; p→next=q→next5在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的算法的时间复杂度为（答案）O（n）1、一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是。

（答案）DCEAB2、在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是。

（答案）r->next=s; r=s3、一个队列的入队序列是1，2，3，4，则队列的输出序列是。

（答案）1，2，3，44、一个中缀算术表达式为1+（3-x）*y，则其对应的后缀算术表达式为。

（答案）13x-y*+5、一个栈的入栈序列是A，B，C，D，E，f，出栈的序列是B，D，C，F，E，A，则栈的容量至少应（）（答案）3第四章测试1如下图所示的4棵二叉树中，不是完全二叉树。

（答案）C2在线索化二叉树中，t所指结点没有左子树的充要条件是（答案）t->ltag= =13对一个满二叉树，m个树叶，n个结点，深度为h，则（答案）n=2h-14一个具有1025个结点二叉树的高h 为（）（答案）11~10255一颗非空的二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树满足（）（答案）只有一个叶子结点第五章测试1（答案）22对于如下图所示的图，若从顶点a出发深度优先搜索遍历，得到的顶点序列为。