2022年徐师大数据结构复习资料 .pdf

《2022年徐师大数据结构复习资料 .pdf》由会员分享，可在线阅读，更多相关《2022年徐师大数据结构复习资料 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、注：算法题：程序填空；添加注释；写运行结果；画图；描述算法思想。综合题：画图；根据图表回答问题。数据结构考试重点（答案仅供参考）绪论1谈谈你对“数据结构”概念的理解。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的。而是他们之间存在着某种关系，这种数据元素相互之间的关系称为结构，这也是我们要讨论的数据结构的主要内容。一般来说，数据结构包括以下三方面的内容：（1）数据元素之间的逻辑关系，也称数据的逻辑结构。数据的逻辑结构是抽象的，它不依赖计算机的实现，只依赖人们对事物的理解和描述。（2）数据元素及其关系，在计算机内部（内存）中的表示，称其为数据的物

2、理结构或数据的存储结构。2谈谈你对“抽象数据类型（ADT） ”的理解。抽象数据类型 (Abstract Data Type 简称 ADT)是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数据类型需要通过固有数据类型( 高级编程语言中已实现的数据类型) 来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。线性表3 顺序表的动态内存分配的好处是什么？

3、（1）长度能动态增长；根据实际需要分配所需内存大小，合理利用资源（2）不需要预先分配存储空间；算法题（ 26） 简答题（ 40） 综合题（ 24） 论述题（ 10）结论（ 10）*线性表（ 10）*栈队列（ 18）* *串（4）*数组（ 4）*树与二叉树（ 17）*图（6）*查找（ 16）*排序（ 15）*精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 19 页4 单链表中引入“头结点”的好处是什么？什么情况下单链表需要使用“尾指针”？（1）由于开始结点的位置存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理

4、。(2) 只有“头指针”时，访问“头”方便，而访问“尾”不方便。有时候，根据需要，一个单向循环链表只设置尾指针，而不设置头指针。此时访问“头”和“尾”都很方便。5 在主调函数中构建了一个“不带头结点”的单链表L1（即该链表已完成初始化，甚至链表已不空），在子函数中对该单链表进行插入 /删除操作。说明在参数传递时， 使用“引用”与不使用“引用”的区别。6 在主调函数中声明了一个单链表L1，在子函数InitLink( )中对该单链表初始化为一个“带头结点”的单链表。在“不使用引用型参数”的情况下，1） 写出初始化函数。typedef int data; typedef struct LNode d

5、ata d; Struct LNode *next; LNode ,*LinkList; LinkList initialize (void) LinkList L; L=(LinkList)malloc (sizeof(LNode);L-next=NULL;return L; 2）写出调用该函数的语句。Void main () LinkList L1; L1=initialize(); . . . return 0; 栈队列7 对“链栈”， 哪一端是“栈顶”？为什么？链头作为栈顶原因：链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上操作，因此将链头作为栈顶方便操作。精选学习资料 -

6、 - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 19 页8 链栈中还要不要“头结点”？为什么？不要。原因：链栈是运算受限的单链表，其插入和删除的操作仅在链表头位置上进行。如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂。9 顺序栈采用动态内存分配，数据结构定义如下：typedef struct sStack DataType *base; DataType *top; int stacksize; /最大容量 SqStack; 1）如何求栈高？Int stackHeight (SqStack sq) return sq.top-sq.

7、base; 2）能否将top 定义成int 类型？可以10链队列的“队头”与其它链式结构（如链栈或者单链表）有什么不同？11为什么引入“循环队列”？写出循环队列判队满，判队空以及求队长的表达式。原因：为充分利用向量空间，克服假溢出 现象方法：1）设置一个队长变量2）牺牲一个元素空间队空： Q.front= Q.rear; 队满： (Q.rear+1)%maxsize= Q.front 队长 (Q.rear-Q.front+MAXSIZE)%MAXSIZE 知识：12.对于一般的顺序存储结构，若采用“动态内存分配” ，当插入元素而空间不足时，可以动态增加内存分配。而对于循环队列，能否这样做？为什

8、么？不能循环队列是将顺序队列臆造成一个环状空间，当插入元素而空间不足时，动态增长内存分配会破坏循环队列的结构。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 19 页能力：13.定义一个长度为k 的循环队列，有一个字符串S（长度 k ） ，编写程序完成进队出队。调试完毕后，将完整代码写在实验报告册上。特别强调：将关键代码加注释，注释行数不少于总代码行的2/3 。#include stdio.h #include stdlib.h #define MAXSIZE 10; /最大队列长度typedef char DataType; type

9、def struct DataType *base; /初始化的动态分配存储空间int front ,rear; /头，尾指针，若队列不空，指队头元素、队列尾元素的下一个位置 SqQueue; /-实现 - void InitQueue (SqQueue &Q) /初始化队列 Q.base=(DataType *)malloc( MAXSIZE* sizeof( DataType) ); Q.front=Q.rear=0; bool isQEmpty( SqQueue Q) /判队空 if (Q.front=Q.rear) return true; else return false; boo

10、l isQFull( SqQueue Q) /判队满 if (Q.rear+1) % MAXSIZE =Q.front) return true; else return false; void EnQueue(SqQueue &Q, DataType &e) /向队列中添加元素 Q.baseQ.rear=e; Q.rear=(Q.rear+1)% MAXSIZE; void OutQueue(SqQueue &Q, DataType &e) /出队 e=Q.baseQ.front; Q.front=(Q.front+1)% MAXSIZE; 精选学习资料 - - - - - - - - -

11、名师归纳总结 - - - - - - -第 4 页，共 19 页 /-实现完毕 - void main() /调用函数 SqQueue Q1; InitQueue (Q1); char c1, c2; cout 请读入符号串，以# 号结束 :c1; while( c1!=#) if( ! isQFull(Q1) ) EnQueue(Q1, c1); cinc1; else OutQueue(Q1,c2); coutc2; while( ! isQEmpty(Q1) ) OutQueue(Q1,c2); coutc2; coutendl; */ 串14.能力：在第 1 章 绪论中，曾经写了一个描

12、述“串”的ADT ，并给出了其表示与实现，以及一个完整的程序。要求：给该程序关键代码加注释，注释行数不少于总代码行的2/3 。#include iostream.h #include malloc.h typedef struct str 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 19 页char *ch; int length; HString; /- 基本操作算法描述- bool StrAssign(HString &T, char *chars) /将 chars串赋给 T int i; char *c; if( T.ch)

13、 free( T.ch); /这行代码有问题，思考？for( i=0, c=chars; *c ; i+, c+) /求 chars串的长度; if( !i) T.ch=NULL; T.length=0; /建立一个空串else T.ch=( char *) malloc( i* sizeof( char) );/注意：这里没有检测是否内存分配成功，其实是应该做的for( int j=0; ji; j+) T.chj=charsj; /注意： T 串的末尾没有添加0 T.length=i; return true; /赋值成功 int StrLength( HString S) /求串长 re

14、turn S.length; int StrCompare( HString S, HString T) /串大小的比较 int i; for( i=0; iS.length & iT.length; i+) if( S.chi != T.chi ) return S.chi - T.chi; return S.length - T.length; /请理解这一行的意思 bool SubString(HString &Sub, HString S, int pos, int len) /求子串 if( posS.length | lenS.length-pos+1) return false;

15、 if( Sub.ch) free(Sub.ch); /这行代码有问题，思考？if( !len) Sub.ch=NULL; Sub.length=0; else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 19 页Sub.ch=( char*) malloc( len * sizeof( char) );/注意：这里没有检测是否内存分配成功，其实是应该做的for( int j=0, k=pos-1; j0) n=StrLength(S); m=StrLength(T); i=pos; while( ipos; coutIndex(

16、S, T, pos)endl; 数组知识：15.二维数组A89 按行优先顺序存储，若数组元素A23 的存储地址为1087，A47 的存储地址为1153，则数组元素A67 的存储地址是多少？A47 和 A23 相差 22 个元素(4 9+7)-(2 9+3)=22 1153-1087=66 即一个数组元素占3 个字节A67 和 A47 相差 18 个元素(6 9+7)-(4 9+7)=18 则 A67 存储地址为 1153+183=1207 16、三角矩阵和对称矩阵在进行压缩存储时有什么不同？三角矩阵是指上（下）三角矩阵的下（上）三角（不包括对角线）中的元素均为常数C 或 0，所以在压缩存储时只

17、存储上（下）三角中的元素，并加一个存储常数C 的存储空间。树和二叉树：知识：17、对于二叉树，什么情况下选用“顺序存储”较好？稠密的树18、先序序列为：ABCDEFG ，中序序列为：CBAEFGD ，画出该二叉树，及二叉链表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 19 页19、实现二叉链表的层序遍历，需要借助于什么数据结构？为什么？层序遍历需要借助于“队列”完成，对二叉树遍历，除了按先序、中序、后序遍历外，还可以按“层序”遍历。先一层的遍历完须保存下来。20、结点权值分别是：0.05,0.29,0.07,0.08,0.14,0

18、.23,0.03, 0.11 ，构造最优二叉树。21、能力：1）按右图所示的二叉树建立二叉链表，然后：2）按 “ 中序 ” 遍历二叉链表；3）求树高度；调试完毕后，将完整代码写在实验报告册上。要求：将关键代码加注释，注释行数不少于总代码行的2/3 。#include #include typedef char elemtype; typedef struct BiNTree /* 定义二叉树结点类型*/ elemtype data; struct BiNTree *lchild; struct BiNTree *rchild; BiNTree,*BiTree; /创建一棵二叉树void Cre

19、ateBiTree(BiTree &T) if( T) free(T); cinch; if (ch=#) T= NULL; else T=(BiTNode*)malloc(sizeof(BiTNode); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); /递归创建一棵二叉树 return OK; 6 1 2 3 5 4 7 9 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 19 页 void InOrderTraverse(BiTree T) 中序遍历 if

20、(T) InOrderTraverse(T-lchild); 访问左子树printf(%c,T-data); InOrderTraverse(T-rchild); 访问右子树 int Depth(BiTree T) 求树高int depl, depr; 左右子树的高度if (T) depl=Depth(T-lchild); depr=Depth(T-rchild); if (depl=depr) return (depl+1); else return (depr+1); 返回子树高度加上根节点高度 return 0; int main(void) 调用函数 BiTree t; /*定义二叉数

21、 */ CreateBiTree(t); printf(n 中序输出 ); InOrder(t); 访问二叉树Depth(t); return 0; 22、带 “ 空指针域标记 ” 的中序序列能否确定二叉树的形态？为什么？不能精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 19 页图23、（1）画出图（ a）的邻接表，并说明如何根据其邻接表求结点V1 的入度和出度。在有向图的邻接表中，第i 个链表中结点的个数是顶点Vi 的出度。此邻接表中V1 邻接的节点为两个，则V1 的出度为2 但是要求Vi 的入度较困难， 需遍历整张表。此邻接表中

22、只有顶点V4 的单链表中有V1，则V1 的入度为1 （2）写出从V1 开始的深度优先遍历序列。例： V1 V3 V4 V2（答案不唯一）方法：（1）从图中的某个顶点V 出发，访问之；（2） 依次从顶点V 的未被访问过的邻接点出发，深度优先遍历图， 直到图中所有和顶点V 有路径相通的顶点都被访问到；（3） 若此时图中尚有顶点未被访问到，则另选一个未被访问过的顶点作起始点，重复上述（1）（2）的操作，直到图中所有的顶点都被访问到为止。（基本思路（假定从A 出发）先访问 A 点，再访问 A 的第 1 个尚未访问的邻接点B；再访问 B 的第 1个尚未访问的邻接点 C;再访问 C 的第 1 个尚未访问的

23、邻接点D；。到头后沿原路返回，再访问返回路径上其他点的第1 个尚未访问的邻接点，直至所有顶点访问完毕。）（3）画出图（ b）的邻接矩阵，并说明如何根据其邻接矩阵求结点V1 的度。V1 V2 V3 V4 V5 V1 0 1 0 1 0 V2 1 0 1 0 1 V3 0 1 0 1 1 V4 1 0 1 0 0 V5 0 1 1 0 0 （4）写出从V2 开始的广度优先遍历序列。例： V2-V1-V3-V5-V4（答案不唯一）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 19 页查找24、集合元素的关键字依次为：1，2，3， 4，6，

24、8，20，25，26， 27，40，50。（1）画出二分查找的判定树；. （2）每个结点查找等概率情况下，求平均查找长度。ASL=P1C1+P2C2+P3C3+ . +PnCn Pi 与 Ci 分别表示第i 个数被查找的概率与查找该数需要比较的次数。用 ASL 作为衡量一个查找算法执行效率的标准。（3）二分查找对于存储结构有什么特殊要求？二分查找只能适用于有序表，并且以顺序存储结构存储。排序25、从空树起，依次插入关键字50，42，18， 48，12，56，30，23，构造一棵二叉排序树。（1）画出该二叉排序树；（2）画出删除关键字为50 的结点之后的二叉排序树。删除叶结点，只需将其双亲结点指

25、向它的指针清零，再释放它即可。被删结点无右 (左）子树，可以拿它的左（右）子女结点顶替它的位置，再释放它。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 19 页被删结点左、右子树都存在此处的假设：被删除结点为p,其双亲为 f 结点，中序下的前驱为s；p 为 f 的左子树（右子树情况同）可以有两种处理办法: 1. 将 p 的左子树改为f 的左子树 ,将 p 的右子树改为s 的右子树（即左子树上提，右子树下滑）2. 用 s结点的值代替p 结点的值，再将s 结点删除，原s结点的左子树改为s 的双新结点q 的右子树。（3）调整上述一组关键字

26、的输入顺序，使构建的二叉排序树为“平衡二叉排序树”。26、关键字序列为（3, 8, 19, 14, 23, 1, 68, 20, 84, 27 ） 。哈希函数为H(key)= key%7 ，按“开散列组织法”解决冲突问题，（1）画出哈希表H（处理链表时，采用“前插法”或者“后插法”均可）。（2）查找元素“1”需进行几次关键字比较？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 19 页能力：27、关键字序列为（3, 8, 19, 14, 23, 1, 68, 20, 84, 27） 。哈希函数为H(key)= key%7 ，按“开散列

27、组织法”解决冲突问题，写出：（1）写出构造哈希表的算法；（2）写出哈希查找算法。要求：关键代码加注释，注释行数不少于总代码行的2/3 。#include iostream.h #include malloc.h #define MODELE 7 typedef struct node int key; struct node *next; *HashElem; void CreatHash( HashElem H,int n) /创建哈希表 int Num, Address; int i; HashElem p, qMODELE; /qMODELE 用于指向“对应”链的尾部for( i=0;i

28、 MODELE;i+) /初始化哈希表Hi=NULL; for( i=0; iNum; p=(HashElem) malloc( sizeof(struct node); p-key=Num; p-next=NULL; Address=Num% MODELE; if( HAddress=NULL) /后插法HAddress=p; else qAddress-next=p; qAddress=p; int times=0; /全局变量，用于统计比较的次数HashElem Find(HashElem H, int k) /Hash 表上的查找，返回一个指向结点的指针，并统计比较次数HashElem

29、 p; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页int m; m=k% MODELE; p=Hm; while( p!=NULL) times+; if( p-key!=k) p=p-next; else break; return p; main() HashElem Head MODELE, t; /哈希地址的值域为0.5 int n,Num; n=9; /实际元素个数cout 请输入n 个整数，创建哈希表endl; CreatHash( Head,n); cout 请输入要查找的数:Num; /查询 41 t=F

30、ind( Head,Num); /查找if( t=NULL) coutNum No Found!endl; else coutNum Found.endl; cout 比较次数是 :timesendl; 28、描述直接插入排序的算法思想。直接插入算法中设置监视哨有什么好处？直接插入排序的基本思想是：当插入第i (i 1) 个对象时，前面的V0, V1, , vi-1 已经排好序。 这时， 用 vi 的关键字与vi-1, vi-2, 的关键字顺序进行比较，找到插入位置并将 vi 插入，原来位置上之后的所有对象依次向后顺移。好处 ：直接插入排序时，应该考虑到，要交换两个数据的值，需要引入一个辅助变

31、量，A=B,B=C,C=A, 就像此时的A 一样， 是为了帮助交换，监视哨也有这样的作用，另外还有作用也是为了防止溢出。1）保存 Ri 的副本； 2）简化边界条件，防止循环下标越界。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 19 页29、希尔排序的算法思想是什么？对关键字序列（49，38，65，97，76， 13，27，49， 55，4）进行希尔排序，写出每一趟的结果。该方法的基本思想是：先将整个待排对象序列按照一定间隔分割成为若干子序列，分别进行直接插入排序，然后缩小间隔，对整个对象序列重复以上的划分子序列和分别排序工作，直到

32、最后间隔为1，此时整个对象序列已“基本有序” ，进行最后一次直接插入排序。结果：初始趟：49 38 65 97 76 13 27 49 55 4 30、对于初始关键字序列，什么情况下排序效率较高，什么情况下，排序效率较低。31、对 7 个关键字进行快速排序，在最好的情况下仅需进行10 次关键字的比较。（1）假设关键字集合为（1,2,3,4,5,6,7） ，试举出能达到上述结果的初始关键字序列，并说明原因。4 7 1 3 6 5 2 （2）对所举序列进行快速排序，写出“每一趟排序”的结果。初始关键字： 4 7 1 3 6 5 2 一次： （2 3 1）4 （6 5 7）二次： （1）2 （3）4

33、 （5）6 （7）32、描述简单选择排序的算法思想。基本思想是：第i 趟 (i = 1, , n-i) 中，在n-（i-1） 个待排序对象中选出关键字最小/大的对象 , 作为有序序列的第i 个记录。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 19 页void SelectSort( RecType R , int n) for (int i=1; in; i+) k=i; for ( j=i+1;j=n; j+) if (Rj.key Rk.key) k=j; if (i!=k) temp=ri; ri=rk; rk=temp;

34、33、二路归并算法有什么优缺点？优点：算法总的时间复杂度为O(nlog2n) 。归并排序是一个稳定的排序方法。缺点：归并排序无法在原表上进行，需要另外一个与原待排序对象数组同样大小的辅助数组。所以归并排序占用附加存储较多。34、能力：一组待排序的整数为： （ 10，2，8，3，7，9，5，8，6） ，按顺序表存储，存储结构定义如下：typedef struct List int data100; int length; SqList; 分别写出三个基本排序算法，并为关键代码加注释，注释行数不少于总代码行的2/3 。要求： （1）直接插入排序算法用0 号元素作为“监视哨” 。（2）冒泡排序算法要

35、求在某一趟排序中若没有数据交换，则停止下一趟排序的进行。（3）简单选择排序要求从“大”到“小”排序。#include iostream.h typedef struct List int data100; int length; SqList; void InsertSort( SqList &L) /直接插入排序 int i,j; for(i=2; i=L.length; i+) /进行 n-1 趟 L.data0=L.datai; /L.data0 为监视哨j=i-1; while( L.data0L.dataj) L.dataj+1=L.dataj; j-; 精选学习资料 - - - -

36、 - - - - - 名师归纳总结 - - - - - - -第 17 页，共 19 页 L.dataj+1=L.data0; void BubbleSort( SqList &L) /对 L 进行冒泡排序 int i,j; int flag=1; for(i=1; i=L.length-1 & flag; i+) / 进行 n-1 趟 flag=0; for( j=1;j L.dataj+1 ) L.data0=L.dataj; L.dataj=L.dataj+1; L.dataj+1=L.data0; flag=1; void SelectSort( SqList &L) for (int

37、 i=1; iL.length; i+) int k=i; for ( int j=i+1;j=L.length; j+) if (L.dataj L.datak) k=j; if (i!=k) L.data0=L.datai; L.datai=L.datak; L.datak=L.data0; void print( SqList L) for( int i=1; i=L.length; i+) coutL.datai ; coutendl; void main() SqList L1= -1,5,8,2,1,7,9,10,3,7, 9 ; InsertSort( L1); print( L1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 19 页BubbleSort( L1); print(L1); SelectSort( L1); print(L1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 19 页