数据结构复习

1、填空题（结果由小到大排列）1. 一组记录的关键字为（5，6，2，4，3，1），利用简单选择排序的方法，经过第1趟排序后，其关键字序列为 1 (6 2 4 3 5)经过第2趟排序后，其关键字序列为 1 2 (6 4 3 5)经过第3趟排序后，其关键字序列为 1 2 3 (4 6 5)2. 一组记录的关键字为（5，6，2，4，3，1），利用直接插入排序的方法，经过第1趟排序后，其关键字序列为 (5 6) 2 4 3 1经过第2趟排序后，其关键字序列为 (2 5 6) 4 3 1经过第3趟排序后，其关键字序列为 (2 4 5 6) 3 13. 一组记录的关键字为（38，5，19，26，49，97，1

2、，66），利用冒泡排序，经过第1趟排序后，其关键字序列为 5 19 26 3849 16697经过第2趟排序后，其关键字序列为 5 19 26 381496697经过第3趟排序后，其关键字序列为 5 19 26 1 384966974. 一组记录的关键字为（265，301，751，129，937，863，742，694，76，438），利用快速排序的方法，经过一次划分后，其关键字序列为76 129 265 751 937 863 742 694 301 4385. 一组记录的关键字为（265，301，751，129，937，863，742，694，76，438），利用归并排序的方法经过第1趟排

3、序后，其关键字序列为265 301 129 751 863 937 694 742 76 438经过第2趟排序后，其关键字序列为129 265 301 751 694 742 863 937 76 438经过第3趟排序后，其关键字序列为129 265 301 694 742 751 863 937 76 438珊珊的练习题选择题1. 数据结构DS(Data Struct)可以被形式地定义 为DS=（D，R），其中D是 的有限集 合，R是D上的 有限集合。 A数据对象 数据元素 操作 关系2. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链性存储要比顺序储存要 A低 高 相

4、同不一定3. 计算机算法指的是 ，它具备输入、输出和 等五个特性。 A计算方法 解决问题的有限运算序列可行性、确定性和有穷性确定性、有穷性和稳定性4. 下面程序段执行后变量count的值为（）。int count=0;for(int i=1;i<=10;i+)count= count +i*10;A. 250 B. 350 C. 450 D. 5505. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种_的存储结构。A随机存取 B索引存取 C顺序存取 D散列存取6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。A. 必须是连续的 B. 部分地址必须是连续的C.

5、 一定是不连续的 D. 连续或不连续都可以7. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;C. q->next=s; s->next=p; D. p->next=s; s->next=q;8. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s->next=p; p->next=s; B. s->next=p->

6、;next; p->next=s;C. s->next=p->next; p=s; D. p->next=s; s->next=p;9. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p->next= p->next->next； B. p= p->next; p->next= p->next->next；C. p->next= p->next; D. p= p->next->next；10. 链表不具备的特点是 _ 。A 可随机访问任何一个元素B 插入、删除操作不需要移动元素C 无需

7、事先估计存储空间大小D 所需存储空间与线性表长度成正比11. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_ 。A 4，3，2，1 B 1，2，3，4 C 1，4，3，2 D 3，2，4，112. 一个队列的数据入列序列是1，2，3，4，把队列的数据出队后压入一个栈中，当队列为空时再把数据从栈中弹出，数据的出栈序列是_ 。A 4，3，2，1 B 1，2，3，4 C 1，4，3，2 D 3，2，4，113. 判断一个表达式中左右括号是否匹配，采用 _ 实现较为方便。A 线性表的顺序存储 B 队列 C 线性表的链式存储 D 栈14. 栈与一般线性表区别主要在方面 。A 元素个数

8、 B 元素类型 C 逻辑结构 D 插入、删除元素的位置15. 在一个链队中，假设F和R分别是队首和队尾指针，则数据出队的运算是 。  A R=F->next;  B R=R->next;  C F=F->next;  D F=R->next;填空题（排序结果由小到大排列）6. 数据元素是数据的基本单位，有些情况下它也称为元素、结点、记录。7. 数据项 是数据的不可分割的最小单位。8. 数据结构按逻辑结构可分为 线性结构 和 非线性结构 。9. 一组记录的关键字为（5，6，2，4，3，1），利用简单选择排序的方法，经过3趟排序后，其

9、关键字序列为 1，2，3，4，6，5 10. 一组记录的关键字为（5，6，2，4，3，1），利用直接插入排序的方法，经过3趟排序后，其关键字序列为 2，4，5，6，3，111. 一组记录的关键字为（38，5，19，26，49，97，1，66），利用冒泡排序的方法，经过3趟排序后，其关键字序列为 5，19，26，38，1，49，66，9712. 一组记录的关键字为（265，301，751，129，937，863，742，694，76，438），利用快速排序的方法，经过3趟排序后，其关键字序列为76，129， 265，438，301，694，742，751，863，93713. 一组记录的关键字为

10、（265，301，751，129，937，863，742，694，76，438），利用归并排序的方法，经过3趟排序后，其关键字序列为 129，265，301，694，742，751，863，937，76，43814. 在一个长度为n的顺序表中删除第i个元素，要移动 N-I 个元素。如果要在第i个元素前插入一个元素，要后移 N-I+1 个元素。15. 栈操作数据的原则是后进先出 ，队列操作数据的原则是 先进先出 。16. 在栈中，可进行插入和删除操作的一端称 栈顶 。17. 栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队头_删除元素。18. 计

11、算机在运行递归程序时，要用到 系统 提供的栈。19. 表达式a*(b+c)-d的后缀表达式是abc+*d- 20. 若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_ 18 21. 设将整数1，2，3，4进栈，若入、出栈次序为Push, Pop,Push,Push, Pop, Pop,Push, Pop,则出栈的数字序列为1324 ；若想得到出栈序列1432则具体操作为：Push，Pop，Push，Push，Push，Pop，Pop，Pop22. 在采用少用一个存储空间的具有n个单元的循环队列中，队满时共有n-1个元素。对于下图所示的循环队列，队满的条件是front

12、=(rear+1)%MAXSIZE；队空的条件是rear=front 23. 一棵有n个结点的满二叉树有_0_个度为1的结点、有_(n-1)/2_个分支 （非 终端）结点和_(n+1)/2_个叶子，该满二叉树的深度为_log2(n+1)_。24. 写出下图二叉树的先序遍历结果 ABDCEFJ 中序遍历结果 DBAECJF 、后序遍历结果 DBEJFCA 第九周：排序练习插入排序：初始数据：30 20 50 40 601. 302. 20 303. 20 30 504. 20 30 40 505. 20 30 40 50 60选择排序：初始数据：30 20 50 40 601. 20 30 50

13、 40 602. 20 30 50 40 603. 20 30 40 50 604. 20 30 40 50 60第十二周：查找练习1、已知散列表地址区间为010，哈希函数为H(k)=kll，给定关键字序列（16，13，20，18，23，15，31，45，56）。分别采用线性探测法和链接法，将以上关键字依次存储到哈希表中。请描述出散列地址的计算过程及最后得到的散列表 。 012345678910231345151656182031线性探测法：H(k)=k: ll第一趟K=16H(16)=5第二趟:K=13H(13)=2第三趟:K=20H(20)=9第四趟:K=18H(18)=7第五趟:K=23

14、H(23)=1第五趟:K=15H(15)=4第六趟:K=31H(31)=9由于与20发生冲突，H(31)=(31+1)/11.即H(31)=10第七趟:K=45H(45)=1由于与23发生冲突，H(45)=(45+1)/11.即H(45)=2但又与13发生冲突，H(45)=(45+2)/11.即H(45)=3第八趟:K=56H(56)=1由于与23发生冲突，H(45)=(45+1)/11.即H(45)=2但又与13发生冲突，H(45)=(45+2)/11.即H(45)=3但又与45发生冲突，H(45)=(45+3)/11.即H(45)=4但又与15发生冲突，H(45)=(45+4)/11.即H

15、(45)=5但又与16发生冲突，H(45)=(45+5)/11.即H(45)=6链接法：0156452321334155166718893020102、考虑散列表的查找方法，试完成以下两题 已知哈希函数为H(k)=kll，线性探测法解决冲突，散列表状态如下：012345678910 23134515165618 2031 请描述出关键字45和5的查找过程及结果。查找45:H(K)=K%11K=45H(45)=1由于23不等于45,即H(45)=(45+1)/11=2由于13不等于45，即H(45)=(45+2)/11=3由于H(45)=3时，查找成功.比较次数为3查找5K=

16、5K(5)=5由于16不等于5，即H(5)=(5+1)/11=6由于56不等于5，即H(5)=(5+1)/11=7由于18不等于5，即H(5)=(5+1)/11=8由于H(8)为空，所以关键字5一定不在哈希表中. 已知哈希函数为H(k)=kll，线性探测法解决冲突，散列表状态如下：0123456789103323134515165618 192031 请描述出关键字50的查找过程及结果。H(K)=K%11K=50H(50)=6由于56不等于50，即H(50)=(50+1)/11=7.由于18不等于50，即H(50)=(50+2)/11=8由于19不等于50，即H(50)=(50+3)

17、/11=9由于20不等于50，即H(50)=(50+4)/11=10由于31不等于50，即H(50)=(50+5)/11=0由于33不等于50，即H(50)=(50+6)/11=1由于23不等于50，即H(50)=(50+7)/11=2由于13不等于50，即H(50)=(50+8)/11=3由于45不等于50，即H(50)=(50+9)/11=4由于15不等于50，即H(50)=(50+10)/11=5由于16不等于50，即H(50)=(50+11)/11=6由于游历一遍后，亦没有查找关键字50，即查找失败.第十三周：数的遍历1、 分别写出下面二叉树的层次、先序、中序、后序遍历的次序。GABC

18、DEFH层次：ABCDEFGH先序:ABDFGCEH中序:BFDGAEHC后序:FGDBHECA2、画出上面二叉树的二叉链的链式结构AROOT BCEDHFG3、给出一颗二叉树的后序遍历和中序遍历的次序，画出这颗树。 后序遍历为：BDECA中序编列为：BADCEACBDE第十四周：二叉树1、 画出创建下列数据到二叉排序树的过程，并中序遍历这棵二叉排序树。36 20 50 80 30 20 26 5636 20508010302656中序遍历：10 20 26 30 36 56 50 802、 把下列数据生成一棵完全二叉树，并判断这棵树是不是堆。如果不是就调整为最大堆结构。90 80 60 30

19、 20 50 60 70 90 6080605020307090化成大堆 608060502070“303、 下面是一棵最小堆结构的树，列出输出排序次序的过程（即每次输出根结点后，删除根）。10302060362610过程：3020266036输出1026302060362030266036输出203630266026303660输出2626363060603630303660输出3030603660366036输出3660输出60第十五周 图的存储结构三、练习题1. 画出下面无向图的邻接矩阵和邻接表（参考课件）。ABCDEA01111B10000C10000D10001E10010E DCB

20、AA B A C D A A E D 或0123ACDBvexdatafirstarc 0 0 1 adjvexnext4E 0 03 2 3 4 这个是后插式，还有前插式。2. 画出下面有向图的邻接矩阵和邻接表。ABCDEA01101B00000C00000D10001E00000E C BA B D A E E 或0123ACDBvexdatafirstarc 0 1 adjvexnext4E 2 4 4第3题：struct EdgeNodeint adjvex;EdgeNode *next;struct VertexNodechar vexdata; EdgeNode *firstarc

21、;VertexNode G5;第十六周：复习一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分题号 1 2 3 4 5 6 7 8 9 10 11答案 1.数据的不可分割的基本单位是_D_。A.元素B.结点C.数据类型D.数据项数据项是具有独立含义的标识单位，是数据不可分割的最小单位；数据元素是数据的操作基本单位。数据元素也又可称为元素、结点、顶点、记录等。7.与中缀表达式a+b*c-d等价的后缀表达式是_abc*+d-_。运算符优先级：0：( #1：+ -2：* /利用栈结构存放运算符转换规则：操作数直接存放在后缀

22、表达式中 运算符按照以下规则入栈/出栈：先预存“”至栈底 a)“（”强制入栈 b)遇到“）”开始出栈，直到遇见栈顶元素为“（”为止 c)如果中缀表达式中扫描的当前运算符优先级高于栈顶运算符优先级则当前运算符入栈，否则要栈顶运算符先出栈再进行比较。8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素_D_进行比较,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37数组A：01234567896153037656870728999low=0,high=9(0+9)/2=4 37<A4 l

23、ow=0,high=4-1=3;(0+3)/2=1 37>A1 low=1+1=2,high=3(2+3)/2=2 37>A2 low=2+1=3,high=3(3+3)/2=3 37=A3。9.对长度为10的表作选择(简单选择)排序,共需比较_A_次关键字。 A.45 B.90 C.55 D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为_C_。 A.O(log2 n)B.O(nlog2 n)C.O(n2)D.O(2n )11.对长度为10的表作2_路归并排序,共需移动_C_次(个)记录。 A.20B.45C.40D.30一道关于数据结构归并排序移动记录次

24、数的题目1 2 3 4 5 6 7 8 9 10 11 12 13 141&2 ;3&4 ; 5&6 ; 7&8 ; 9&10 ; 两两归并,共移动10次,比较5次1,2&3,4 ; 5,6&7,8 ; 9,10 两两归并,共移动10次,比较3次1,2,3,4&5,6,7,8 ; 9,10, 两两归并,共移动10次,比较4次1,2,3,4,5,6,7,8 & 9,10,两两归并,共移动10次,比较8次正序共移动10*4=40,比较5+3+4+8=20次二、填空(每空1分,共11分)1.一个数据结构在计算机中的表示(映象)称

25、为 _存储结构或物理结构_。2.线性表中 _元素的个数_ 称为表的长度。3.栈中元素的进出原则为 _后进先出或先进后出_ 。4.设数组A1.10,1.8的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A4,5的存储地址为_2056_；若以列序为主序顺序存储,则元素A4,5的存储地址为_2086_。1、11、21、31、41、51、61、71、82、12、22、32、42、52、62、72、83、13、23、33、43、53、63、73、84、14、24、34、44、54、64、74、85、15、25、35、45、55、65、75、86、16、26、36、46、56、6

26、6、76、87、17、27、37、47、57、67、77、88、18、28、38、48、58、68、78、89、19、99、39、49、59、69、79、810、110、210、310、410、510、610、710、85.一棵深度为6的满二叉树有_31_个非终端结点（分支结点）。满二叉树的性质：性质1：满二叉树中第i层上有2i-1 个结点数（即叶子结点）性质2：深度为h的满二叉树有2h-1个结点数所以：整棵满二叉树的结点数-叶子结点数=分支结点数26-1 - 2(6-1) = 316.若一棵二叉树中有8个度为2的结点,则它有_9_个叶子。 一般二叉树的性质：叶子结点数 = 双分支结点数 -

27、17.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为_1_次, 最多为_n_次；若查找失败,比较关键字的次数为_n+1_次。三、回答下列问题 (每小题5分,共10分)1.线性表的存储结构,在什么情况下采用顺序结构? 为什么?2.二叉树有哪几种基本形态?（五种基本形态） 画图说明之。空树 仅有根结点的二叉树 右子树为空的二叉树 左子树为空的二叉树 左右子树均非空的二叉树3画出下面无向图的邻接矩阵和邻接表（参考课件），列出该图有A为起点的广度优先遍历和深度优先遍历结果11129810邻接矩阵ABCDEA0811109B80000C110000D1000012E9001

28、2049310211180A081B0112C412083D4E31209广度优先遍历：ABCDE或AEDCB 深度优先遍历：ABCDE或AEDCB4列出该图的广度优先遍历和深度优先遍历结果(起点为A)广度优先遍历:ABCED或AECBD 深度优先遍历:ABCED或AECBD四、试画出下列存储结构图(每小题4分,共20分)1.数组A1.2,0.2 的以列序为主序的顺序存储结构。A1、0，A2、0 ，A1、1，A2、1，A1、2，A2、22.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。BDCA栈顶指针五、求解下列问题 (每小题6分,共24分) 2.

29、试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；1089122056251915(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?10，12，20，15，19(3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。（1*1 + 2*2 + 3*3 + 3*4 + 1*5）/10(4)对该树进行中序遍历,试写出中序遍历序列。5 6 8 9 10 12 15 19 20 25六、程序填空(在算法中有下划线的位置填空,使之成为完整、正确

30、的算法)算法说明:已知Rn是n个记录的递增有序数组,用折半查找法查找关键字为k的记录,若查找失败,则返回-1；否则返回该记录的序号值。int BinFindList(int Rn, int k)int low=0 , high=n-1;while(low<=high)int mid=(low+high)/2; if(k=L.listmid) return mid;else if(k<L.listmid) high=mid-1;else low=mid+1; return -1;七、算法设计(算法中必须有注释)1.设n个元素的线性表顺序存储在一维数组stmaxlen的前n个位置上,试

31、将新元素e插入表中第i-1个和第i个元素之间,写出算法(可用文字或流程图描述)。/向最大长度为MAXSIZE、有效长度为n的数组st下标i处插入新元素eint Insert(int st,int n,int i, int e)/数组空间是否已满 if(n = MAXSIZE) cout<<"空间满"<<endl; return(-1); /检查插入位置的有效性 if(i < 1 | i > L->length) cout<<"位置错"<<endl;return(0); /向后移动数组元素，

32、空出i位置/从下标length-1开始到i结束，按照从后向前的顺序依次向后移动元素 for(int j = n-1; j >= i; j -) stj+1 = stj; /插入新元素 sti = e ; return (1);/插入成功2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。void print(Node *Head) Node *t = Head->next;/带空表头结点,第一个有效结点应为链表的第二个结点tif(t=NULL)/空表cout<<"Em

33、pty list！"<<endl;return;elsecout<<"首结点数据为："<<t->data<<endl;while(t->next != NULL)/查找尾结点t = t->next;cout<<"尾结点数据为："<<t->data<<endl;1、自己独立实现线性表的链式存储结构的代码（当堂课完成并上传） 操作有：初始化、表头插入、按值查找、按位置删除、输出 具体要求：完成下面代码中红色字的内容 /数据类型定义及函数声明/

34、数据元素ElemType类型为inttypedef int ElemType; /结点数据类型struct NodeElemType data; / data代表数据元素Node*Next; /指向下一结点的指针;/单链表数据类型struct ChainListint nLength; / 代表结点的个数Node*head; /指向单链表的头结点;/初始化线性表为空表void init_ChainList( ChainList &L);/表头插入法 void Insert_ChainList(ChainList &L, ElemType x );/按值查找，返回找到的位置int

35、 Location_ChainList(ChainList &L, ElemType x);/按位置i删除void Delete_ChainList(ChainList &L,int i);/输出线性表的所有元素void print(ChainList &L);各种操作实现代码如下：测试代码详见附件中项目文件/初始化线性表为空表，即表长为0，表头指针为空void init_ChainList( ChainList &L) L.nLength = 0;L.head = NULL;/表头插入法，将元素x插入到表头位置void Insert_ChainList(Cha

36、inList &L, ElemType x )/申请并初始化新结点t（data、next的初始化）Node *t ;t = new Node; t->data = x; t->Next = L.head;/原表头结点head作为新结点t的后继/更新表头指针指向和表长 L.head = t;/表头指针指向新结点tL.nLength+ ;/表长增1/按值查找，返回找到的位置/x存在则返回所在具体位置；x不存在返回0；表空返回1int Location_ChainList(ChainList &L, ElemType x) if(L.nLength = 0)/表空 cou

37、t<<"线性表是空表："<<endl; return -1; /查找结点x Node *p; p = L.head; int j = 1; while(p && p->data != x)/p存在且p指向的结点数据域的值不为x p = p->Next; j+; /分情况返回结果 if(p = NULL)/元素x不存在 cout<<"没找到"<<endl; return 0; else/元素x存在 return j ;/删除第i位置的元素void Delete_ChainList(

38、ChainList &L,int i) /*位置i的有效性判断if(i<=0 | i>L.nLength)/i的位置非法cout<<"删除元素的位置有错："<<endl;return;Node *t; /*当i=1的时候特殊处理if(i=1)t = L.head;L.head = L.head->Next;/表头指针指向原表头的后继结点delete t;L.nLength-;/表长减1return;/*查找位置i的前驱位置jt = L.head;int j = 1;while(j< i-1 && t)t = t->Next;/t指向下一个结点j+;/t指向i结点的前驱位置j/*删除i位置上的结点tNode *p;p = t; /p指向待删除结点的前驱t = p->Next; /t指向待删除结点p->Next = t->Next;/将t的后继连在p的后面，即令t的后继成为p的后继 delete t;L.nLength-;/输出线性表的所有元素void print(ChainList &L) Node *t = L.head;while(t != NULL