数据结构复习题-和答案讲解

1、说明:此复习题为复习专用，其给定了期末考试的 主要范围，并非给 定考试原题，考试时相关的题目基本都要进行改动。 因此同学们请 注意，不要去背答案，要将题理解并做会。（请注意这决不是原题，只有弄会才可能通过）第 1章 绪 论 1、数据结构主要研究的三个内容为、 以及定义在该结构上的。2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。3、数据结构被形式地定义为 (D，R)，其中 D是的有限集， R是D 上的 有限集。4、数据的结构在计算机内存中的表示是指()A. 数据的存储结构 B.数据结构 C.数据的逻辑结构D.数据元素之间的关系 5、给出以下给定的两个程序段中划波浪线的语句的

2、执行频度(次数)。( 1) sum=0; for(i=0;in;i+) for(j=0; jn; j+) sum+=aij;( 2) sum=0; for(i=0;in;i+) for(j=0; j=i; j+) sum+=aij;(3) sum=0; for(i=0;in;i+) for(j=0; jm; j+) sum+=aij; 6、分析以下各程序段的时间复杂度为(用大O 记号表示)( 1) i=s=0;while(sn) i+; s+=i;( 2) i=1;while(i=0)个元素的线性结构表示成 (a1，a2,an)，a1称为元素， an称为 元素， i 称为 ai 在线性表中的

3、。对任意一对相邻结点 ai、 ai+1(1=in),a i 称为 ai+1 的 ， ai+1 称为 ai的。2、在表长为 n 的顺序表的第 i 个位置插入一元素( 1=i=n+1 ，插入的新元素作为第 i 个 元素)，则涉及到的元素的移动次数为 ；若删除第 i(1=inext;【 2】; free（q）;（ 3）若 L 为带头结点的单链表，则：a）在表首插入 s 结点的语句序列是：【3】b）单链表为空的判定条件为：【4】（ 4）若 L 为不带头结点的单链表，则：a） 在表首插入 s 结点的语句序列是：【 5】b） 单链表为空的判定条件为：【 6】 12、已知 L 是 带表头结点 的双向链表 （

4、L 为头指针，且结点的后继指针分量为next，前驱指针为 pre ）,其 p 结点（ p 为链表中某结点的指针）既不是首元结点，也不是尾元结点。a）在 p 结点后插入 s结点 （s为某结点的指针 ）的语句序列是： s-next=p-next ； s-pre= 【 1】;【 2】 =s; p-next=s;b）在 p 结点前插入 s结点 （s 为某结点的指针 ）的语句序列是： s-pre=p-pre;s-next=【3】;【 4】 =s; p-pre=s;c）删除 p 结点的直接后继结点的语句序列是：q=p-next; p-next=【 5】;【 6】=p; free（q）;d）删除 p 结点的

5、直接前驱结点的语句序列是：q=ppre;【 7】;【8】=p; free（q）;e）删除该 p 结点语句序列是：【 9】 =p-next; p-next-pre= 【10】 ; free（p）;f）在表首插入 s 结点的语句序列是：s-next=L-next;【 11】 =L;【 12】; L-next=s;13、设带头结点的单链表类型定义如下：typedef struct LNode Elemtype data; / Elemtype 为数据元素类型struct Lnode *next; /后继结点的指针 *LinkedList;（ 1）函数 InverseList（L） 的作用是将一 带头

6、结点 的单链表实现就地逆置的算法（即利用原来链表的空间，将单链表中的结点按原来相反的顺序存储) 。填写空缺位置，使此该算法完整。 InverseList(LinkedList &L) p=L-next;L-next= NULL;while ( p ) q=p-next;【 1】;【2】; p=q;(2) MergeList(La, Lb) 函数的作用是将两个递增有序的带头结点的单链表La, Lb，利用原来的结点空间，合并成一个递增有序的链表La。填写空缺位置，使此该算法完整。void MergeList (LinkedList &La, LinkedList &Lb) pa=La-next;

7、pb=Lb-next; s=La;while(【 3】) if(pa-datadata) s-next=pa; s=pa; pa=pa-next; else s-next=pb; s=pb; 【 4】 ; if (pa) s-next=pa; else s-next= 【 5】 ; free(Lb);( 3)函数 Search(L,i) 用来返回带头结点的单链表 L 的第 i 个元素的位置指针。填写空缺位 置，使此该算法完整。LinkedList Search(LinkedList L, int i) p=L; j= 【 6】 ;while(【 7】) p=p-next; j+;if(【 8】

8、 ) return p;else return NULL;(4)函数 ListLength(L) 用来求一带头结点的单链表 L 的长度。 请写出此函数的算法代码。14 、函数 DeleteElem(int a, int n, int i) 的作用为：在一个长度为 n 的数组中，删除其第 i 个 元素。其中第数组的第一个元素为 a0，第二个元素为 a1 ，依次类推。请写出此函数的算法 代码。第 3 章 栈与队列1、栈与队列是二种特殊的线性表，栈其亦称为；队列亦称为 。2、现有一个空栈，现有 4 个元素其入栈顺序为 a、 b、c、d，则不可能得到了出栈顺序 为。A ) a,b,c,d B) d,c

9、,b,a C) c,a,b,d D) a,c,b,d3、现有一个空栈， 已知其入栈序列为 1, 2, 3, , n，其输出序列为 p1, p2, p3, , pn。若 p1=n ， 则 pi( 1i n)为A ) i B) n-i C) n-i+1D） 不确定4、栈与队列的共同点是B）都是先进先出A ）都是先进后出C）只允许在端点处插入和删除元素D） 没有共同点5、设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素出线的顺序是 s2,s3,s4, s6 , s5 ,s1, 则栈的容量至少应该是（ ） 2 3 5 66、设有一顺序栈已含 3 个元素（当前栈顶元

10、素为 a3），如下图所示，元素 a4正等待进栈。 那么下列 4 个序列中不可能出现的出栈序列是（）sqa1a2a30 1 2 3maxsize-1 a3,a1,a4,a2 a3,a2,a4,a1 a3,a4,a2,a1 a4,a3,a2,a17、一个队列的入列序是1，2，3，4，则队列的输出系列是（） 4， 3， 2，1 1，2，3，4，1， 4，3，2 3， 2，4， 18、向一个栈顶指针为Top（ Top 指向栈顶元素）的链中插入一个s 所指结点时，其操作步骤为（ ） Top-next=s s-next=Top-next;Top-next=s s-next=Top;Top=s s-next

11、=Top;Top=Top-next9、在一个栈顶指针为 Top（ Top 指向栈顶元素）的链栈中，进行出栈操作，并将被出栈元 素的值保存到 x 中，其操作步骤为（ ） p=Top;x=Top-data;Top=Top-next; free（p）; p=Top;Top=Top-next;x=Top-data;free（p）; x=Top;Top=Top-next;free（Top）; x=Top-data; free（Top）;10、对于顺序存储的栈，其类型描述如下：typedef struct ElemType ElemMAX; /*ElemType 为栈内元素类型， MAX 为一预定义常量，

12、数 组 Elem 的首端为栈底，另一端为栈顶 */int Top; /*Top 指示栈顶位置，其值为下标值 */ SqStack;若 Top 指示的位置为 当前栈顶元素的位置 ，则栈空的判定条件为： ；若 Top 指示的位置为 当前栈顶元素的下一位置 ( 即入栈位置 )，则栈空的判定条件为：11、阅读下列算法，写出其完整的功能。#define MAX 100 typedef struct LNode DataType data; /DataType 为数据元素类型struct Lnode *next; /后继结点的指针 *LinkedList;void RVList( LinkedList h

13、ead) DataType SMAX; int top=0;LinkedList p; p=head-next; while(p) Stop+=p-data; p=p-next; p=head-next;while(top) p-data=S-top; p=p-next;12、以下算法是以顺序存储结构实现一个双向栈(即在一维数组的存储空间中存在着两个 栈，它们的栈底分别设在数组的两个端点) 。以下给出了此双向栈类的定义及此双向栈的初始化操作和入栈操作与出栈的算法。填写空白位置，使此算法完整。( 注：双向栈结构如下图所示 )低下标处的栈高下标处的栈012 i Max-j-1 Max-2Max-1

14、a0a1a2aibjb1b0Top1Top0#define Max 可用最大空间长度 ；typedef structElemType ElemMax ； /* ElemType 为栈内数据元素的类型 */int Top0,Top1; /* 定义两个栈顶位置指针，分别存储两个栈的当前栈顶元素 的下标*/ DStack;void inistack(DStack &S )/* 双向栈 S 的初始化操作 */ S.Top0= -1; S.Top1= 【 1】 ;Status push(DStack &S, int i ,ElemType e)/*将 e入栈；其中 i为 0或 1，i为0表示对设在低下标

15、处的栈进行操作，i为1，表示对设在高下标处的栈进行操作 */ if (【2】) /* 若栈满 */printf(Stack is overflow);return(ERROR);else if (i=0) S.Elem+S.Top0=e;else【 3】;retrun OK;Status pop(DStack &S, int i ,ElemType &e)/*出栈操作，其中 i为 0或1，i为 0表示对设在低下标处的栈进行操作， i为 1，表示对设在高下标处的栈进行操作，并通过参数 e 返回出栈元素的值 */ if (i=0)if( S.Top0=-1 ) return 0;else e=S.

16、ElemS.Top0-; return 1; elseif(【 4】) return 0;else e= 【 5】 ; return 1;13、以下是有关 循环队列 的类型定义及其有关操作，填写上相应的空白位置。/* 类型描述 */#define MAX 100typedef struct ElemType baseMAX; /* ElemType 为元素的数据类型 */int front; /*头指针，若队列不空，指向队列头元素 */int rear;/*尾指针，若队列不空，指向队列尾元素的下一个位置 */初始化操作 */ SqQueue;/* 说明：少用一个元素空间，以区别队列判空和判满条

17、件 */Status InitQueue(SqQueue &Q) /*入队操作 */ Q.front=Q.rear=0;return OK; Status EnQueue(SqQueue &Q,ElemType e) /* if(1】) return ERROR;/*若队列满，返回出错 */Q.baseQ.rear=e;Q.rear=(Q.rear+1)% MAX; retrun OK; Status DeQueue(SqQueue &Q,ElemType &e) /* 出队操作 */ if（【 2】 ） return ERROR;/*若队列空，则返回出错 */e=Q.baseQ.front;

18、 Q.front=【 3】 ;14 、若用如下图所示一带 头结点的单循环链表来表示队列， 并且只设一个指针 Q 指向队尾 结点（注意不设头指针） 。以下给出了此队列的类型描述、初始化操作、入队操作和出队操作， 在空白处填写上正确答案。Q2)空队列形式typedef struct Lnode/* 类型描述 */ ElemType data; /* ElemType 为元素的数据类型 */ struct Lnode *next; *CLinkQueue;Status InitQueue(CLinkQueue &Q) /* 初始化建立空队列 Q,执行成功函数返回 OK ，否则返回 FALSE*/ Q

19、=(CLinkQueue) malloc(sizeof(struct Lnode);if(!Q) return FALSE; Q-next=【 1】;return OK;Status EnQueue(CLinkQueue &Q, ElemType e) q=(CLinkQueue)malloc(sizeof(struct Lnode*); if(!q) return FALSE; q-data=e;q-next=Q-next; Q-next=q; 【 2】;return OK;Status DeQueue(CLinkQueue &Q, ElemType &e) /* 出队操作 , 操作成功返回

20、 OK ，否则返回 FALSE*/ if(【3】) return FALSE; /*空队时 */p=Q-next-next;Q-next-next=p-next;if(p=Q)【 4】;e=p-data; free(p); return OK;15、若用如下图所示一带 头结点 的单链表来表示队列。以下给出了此队列的类型描述、初 始化操作、入队操作和出队操作，在空白处填写上正确答案。1)一般的队列形式2)空队列形式QQstruct qnode / 结点类型描述 ElemType data; / ElemType 为元素的数据类型 struct qnode *next;typedef struct

21、 / 链队类型描述 struct qnode *front;struct qnode *rear; LinkQueue;Status InitQueue(LinkQueue &Q) /* 初始化建立空队列 Q,执行成功函数返回 OK ，否则返回 FALSE*/ Q.front=Q.rear=(LinkQueue) malloc(sizeof(struct Lnode);if(!Q.front) return FALSE;【 1】;return OK;Status EnQueue(LinkQueue &Q, ElemType e) p=(LinkQueue)malloc(sizeof(struc

22、t Lnode*);if(!p) return FALSE;p-data=e; p-next=NULL;【 2】;【3】;return OK;Status DeQueue(LinkQueue &Q, ElemType &e) /* 出队操作 , 操作成功返回 OK ，否则返回 FALSE*/ if(【4】) return FALSE; /*空队时 */p=Q.front-next;Q.front-next=p-next;if(p=Q.rear)【 5】;e=p-data; free(p); return OK;第 6 章 树与二叉树1、在一棵含有 n 个结点的二叉树中，其分支数（边数）为：；若

23、此二叉树只有度为 2 的分支结点，和度为 0 的叶子结点，则该树中叶子结点的数目为 ；若此二叉 树的深度（根所在数为 1，深度为树的最大层数）为 d，且此树为满二叉树，则此树的结点数n为。2、对于一棵有 n 个结点的完全二叉树，其深度为（根所在数为1，深度为树的最大层数） ；若对其结点按层进行编号 （根结点为 1，每层从左到右） ，则对于一编号为 i（1i 且 2i=dr) return dl+1;else return【 3】(2)递归函数 PreOrder(T) 、InOrder(T) 、PostOrder(T)的作用对以 T 为根指针的二叉树 进行先根(序)遍历、中根(序)遍历、后根(序

24、)遍历。void PreOrder (BiTree T ) /*先序遍历以 T 为 根指针的二叉树 */ if ( T ) visit (T-data); /* 其中 visit() 为结点数据的访问函数 */【 1】;【 2】;void InOrder (BiTree T ) /* 中序遍历以 T 为根指针的二叉树 */ if ( T )【 3】;visit (T-data); /* 其中 visit() 为结点数据的访问函数 */【 4】;void PostOrder (BiTree T ) /* 后序遍历以 T 为根指针的二叉树 */ if ( T )【 5】;【 6】;visit (T

25、-data); /* 其中 visit() 为结点数据的访问函数 */22、假设用于通讯的电文仅由 5 个字母( A、B、C、D、E)组成，字母在电文中出现的频 率分别为 0.25, 0.05,0.40, 0.20,0.10 。试为这 5个字母设计出哈夫曼编码。 (要求： 画出相 应的哈夫曼树，并根据哈夫曼树给出每个字符的哈夫曼编码1、选择题（ 1）在一个图中，所有顶点的度数之和等于图的边数的倍。A 1/2B. 1 C. 2 D. 42）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A 1/2B. 1 C. 2 D. 43）有 8 个结点的无向图 最多 有条边。A 14B. 2

26、8 C. 56 D. 1124）有 8 个结点的无向连通图 最少 有条边。A 5B. 6 C. 7 D. 85）有 8 个结点的有向完全图有条边。A 14B. 28 C. 56 D. 1126）用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A 栈 B. 队列 C. 二叉树 D. 树7）已知图的邻接矩阵，根据算法思想， 则从顶点 0 出发，按深度优先遍历的结点序列是：A 0 2 4 3 1 5 6B. 0 1 3 5 6 4 2C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6（ 8）已知图的邻接矩阵同上题 列是：8，根据算法，则从顶点 0 出发，按广度优先遍历的结点

27、序A 0 2 4 3 1 6 5B. 0 1 3 5 6 4 2C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 60 出发按深度优先遍历的结点序列是：9）已知图的邻接表如下所示，根据算法， 则从顶点10）已知图的邻接表如下所示，根据算法，则从顶点A0 1 3 2B. 0 2 3 1C. 0 3 2 1 D. 0 1 2 30 出发按广度优先遍历的结点序列0111101100100110001001100110101101000011011100010是：A0 3 2 1B. 0 1 2 3C. 0 1 3 2D. 0 3 1 211） 图的简单路径是指（）不重复的路径。A. 权

28、值 B. 顶点 C. 边12） 设无向图的顶点个数为 n，则该图最多有（D. 边与顶点均 ）条边。A. n-1B. n(n-1)/2C. n(n+1)/213） n 个顶点的连通图至少有（）条边。A. n-1B. nC. n+1D. n(n-1)D. 014）若采用邻接矩阵法存储一个 n 个顶点的无向图，则该邻接矩阵是一个 （ ） 。A. 上三角矩阵 B. 稀疏矩阵C. 对角矩阵 D. 对称矩阵15)设 G1 = (V1, E1) 和 G2 = (V2, E2)为两个图，如果 V1 V2 ，E1 E2，则称（）。A. G1 是 G2 的子图B. G2 是 G1 的子图C. G1是G2的连通分量

29、D. G2是 G1的连通分量16）一个连通图的生成树是包含图中所有顶点的一个（ ）子图。A. 极小 B. 连通 C. 极小连通 D. 无环17）对于具有 e 条边的无向图，它的邻接表中有（）个边结点。A. e-1B. eC. 2（e-1）D. 2e18）与邻接矩阵相比，邻接表更适合于存储（）图。A. 无向B. 连通C.稀疏D. 稠密图19）在有向图 G 的拓扑序列中， 若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是 。A. G 中有弧 vi，vjB. G 中有一条从 vi 到 vj 的路径C. G中没有弧 vi，vjD. G 中有一条从 vj 到 vi 的路径20）有向图 G 用邻

30、接矩阵 A 存储，则顶点 i 的出度等于 。A. 第 i 行非 0 元素个数 B. 第 i 列非 0 元素个数C. 第 i 行和第 i 列所有非 0 的元素个数 D. 矩阵 A 中所有非 0 元数个数2、填空题（1）具有 n 个顶点的无向连通图最多具有边数为：，其生成树具有边数为： 。（2）具有 n 个顶点的有向图最多具有弧数为：。（ 3）遍历图有、 等方法。（ 4）图的逆邻接表存储结构只适用于图。（ 5）用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。（ 6）拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。3、求出图 1 所示无向图中每

31、个的度，及图2 所示有向图每个顶点的出度与入度。4、给出图 1 所示的无向图的邻接矩阵（邻接数组） 。5、给出图 1 所示的无向图的邻接表6、对于图 2 所示的有向无环图给出其三种拓扑排序序列。7、给出图 3 所示连通网的邻接矩阵。8、对如图 3 所示连通网（边上的数值为此边的权值） ：（1）从结点 v1出发，利用 普里姆 算法构造其最小生成树。（ 2）利用 克鲁斯卡尔 算法构造其最小生成树。（只需画出最终的最小生成树，并在每条边的两侧分别注明边的权值和选边的顺序，并将选边的顺序用括号 括起来以区别权值 ）9、用 C 语言分别定义图的邻点矩阵表示法和邻接表表示法的数据类型。10、图的邻接矩阵表

32、示如下：#define MaxVexNum 20typedef struct VexType VexsMaxVexNum; / 定义顶点数组， VexType 为顶点类型int ArcsMaxVexNum MaxVexNum; / 定义邻接矩阵，有弧或边则值为 1，否则为 0 int vexnum,arcnum; / 顶点数或边数 MGraph;函数 FirstAdjVex（G,v） 的作用为：在图 G 中，求顶点 v（v 为顶点在顶点数组中的下标，下 同 ）的第一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回 -1。函数 NextAdjVex（G,v,w） 的

33、作用为：在图 G中，已知顶点 w 是顶点 v当前的一个邻接顶点， 函数用来求相对于顶点 w 顶点 v 的下一个邻接顶点；若存在函数返回所求得的邻接顶点（即其 在顶点数组中的下标） ，否则返回 -1。 如下给出了这两个函数头的定义，请给出这两个函数的完整定义。int FirstAdjVex(MGraph &G ,int v)int NextAdjVex(MGraph &G , int v, int w)第 9章 查 找1以顺序查找方法从长度为 n 的线性表中查找一个元素时， 平均查找长度为 ，时间复杂度为 。2以折半查找方法查找一个线性表时，此线性表必须是 存储的 表。3、在有序表 A1.18

34、中，采用二分查找算法查找元素值等于A7 的元素，所比较过的元素的下标依次为 。4、已知数组 a中元素从 a1至 an递增有序， Search_Bin 函数采用折半查找 (即二分法查找 )的 思想在 a1an中查找值为 m 的元素。若找到，则函数返回相应元素的位置(下标)，否则返回0。填写空缺置，使算法完整。int Search_Bin(int a , int n, int m) low=1;high=n;while (【 1 】 ) mid=(low+high)/ 2;if (m=amid ) return【 2 】 ;else if (mdata=m） return【 1】;else if（

35、mdata） p=p-lchild;else【 2】;return NULL;9、对于给定的关键字序列（ 15，19，8，43，10），选取哈希函数为： H（key）=key%7 ，分别 利用以下给出的解决冲突的方法，在 06 的地址空间上构造出哈希表（画出所构造的哈希表即 可） ,并求出在等概率查找的情况下查找成功时的平均查找长度。（ 1）开放定址法的线性探测再散列；（ 2）开放定址法的二次探测再散列；10、设哈希表长度为 11，哈希函数 H（K）=（K 的第一字母在字母表中的序号） MOD 11 ，若 输入顺序为（ D，BA ，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散

36、列，要求 构造哈希表，并求出等概率情况下查找成功平均查找长度。第 10 章 排 序1、外排序是指 。A）用机器指令直接对硬盘中需排序数据排序。B）把需排序数据，用其他大容量机器排序。C）把外存中需排序数据一次性调入内存，排好序后，再输回外存。D）对外存中大于内存允许空间需排序的数据，通过多次内外存间的交换实现的排序。2、以下给定的序列，哪些是堆（是大顶堆还是小顶堆） ，哪些不是堆，若不是利用建立初 始堆的方法将其建成一大顶堆。A）19，75，34，26，97，56 B）97， 26，34，75，19，56C）19，56， 26，97，34， 75 D）19，34，26，97，56，753、以下

37、给出的排序方法哪些是稳定的，哪些是非稳定的：（ 1）直接插入排序（ 2）希尔排序 （ 3）快速排序 （4）冒泡排序（ 5）二路归并排序（ 6）简单选择排序（ 7）堆排序3、快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 4、假定一组记录的排序码为 （46,79,56,38,40,80） ，对其进行快速排序的一次划分的结果为5、对 20 个记录进行归并排序时，共需要进行 趟归并，在第三趟归并时是把长度为 的有序表两两归并为长度为 的有序表。6 、假定一组记录的排序码为 （46,79,56,38,40,80） ，对其进行归并排序的过程中，第二趟归并后的 结果为 。7、对于给定的待排序的关键字序列（ 49， 38，65，97，76，13，27，49，55，4），利用希 尔排序方法（设增量序列为5、 3、1）给出其排序过程。不写算法，只需画出过程，给出每趟排序的结果。8、对于给定的待排序的关键字序列（ 49，38，65，97， 76，13，27），分别按下列排序方 法给出排序过程。（ 1） 2-路归并排序；（ 2）直接插入排序（ 3）冒泡排序9、填写上相应的空白位置，使该算法完整。void InsertSort（ int a, int n ， ）/*本函数的作用是完成对数组 a 中的 前 n 个数（ a1an ）作 直接插入排序 */ for（i=2 ； i=