数据结构自测题答案.doc

第1章 绪论 一、选择题12345678CCADABCC二、填空题1. 4种基本结构是：集合、 线性结构 、 树形结构 、 图状结构 。2. 树形结构中元素的关系是 一对多 ，图形结构中元素的关系是 多对多 。3. 顺序存储结构中数据元素的存储位置与其 逻辑顺序 是对应的。4. 算法效率的度量方法有：事后统计方法和 事前分析估算方法 。5. 好算法应达到的目标： 正确性 、 可读性 、 健壮性 、 执行时间短 、 存储量低 。6. 抽象数据类型可细分为3种： 原子类型 、 固定聚合类型 和 可变聚合类型 。7. 抽象数据类型的定义包括： 数据对象的定义 、 数据关系的定义 、基本操作的定义 。三、判断题1234567891011五、应用题1. 按增长率从小到大的顺序排列下列各函数： (2/3)n ，n ，n2 ，n!2. 写出以下各函数的功能，并求出其时间复杂度。(1) 功能是判断n是否为素数 ，时间复杂度为O(n ) 。(2) 功能是计算1!+2!+n! ，时间复杂度为O(n ) 。(3) 功能是计算1!+2!+n! ，时间复杂度为O(n2 ) 。六、算法题1. 编写算法计算1!+2!+n!，并使算法的时间复杂度为O(n)。算法思想：用循环实现阶乘的累加求和，注意在求n!时，使用前一次循环中已经求出的(n-1)!的结果。double factorial(int n) int i; double p=1, sum=0; for( i=1; iMAXINT（0kn）时，应进行出错处理。算法思想：先判断n的取值是否合法，若非法则直接退出程序，若n 合法则继续计算2i，在计算2i时，需要判断2i的值是否大于MAXINT/2，这个条件其实就是判断2i+1的值是否大于MAXINT#define arrsize 100#define MAXINT 65535void calculate(int a , int n) int i; if(narrsize) printf(n error!n); exit(-1); a0=1; printf(a0=%dn, a0); for(i=1; iMAXINT/2 ) printf(“i=%d, ERROR!n”, i+1)； break; 第2章 线性结构一、选择题1234567891011121314151617ABCADBBACACBBBDCD二、填空题1. 需向后移动_n-i+1_个元素。2. 应采用_顺序_存储结构。3. 有n个结点的单链表，在x的结点后插入一个新结点的时间复杂度为_O(n)_。4可以将线性链表分成_单链表_和多重链表。5链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。6. 顺序存储结构是通过_ 物理位置相邻_表示元素之间的关系的;链式存储结构是通过_指针_表示元素之间的关系的。7. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素_。8. 带头结点的单循环链表L，L为空表的条件是：_ L-next=L_。三、判断题12345678四、简答题1. 对线性表中的插入操作，分别写出顺序存储结构和链式存储结构下的时间复杂度。答： O(n), O(1)2. 线性结构的特点是什么？答：在数据元素的非空有限集中，(1)存在唯一的一个被称为“第一个”的数据元素; (2)存在唯一的一个被称为“最后一个”的数据元素; (3)除第一个之外，集合中的每个元素均只有一个前驱; (4) 除最后一个之外，集合中每个元素均只有一个后继3. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（有些情况下也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。4. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。*5. 顺序表在插入或删除元素时一般需要移动元素，如果想不移动多个元素就实现插入和删除，应该如何处理？答：插入元素时，直接将新元素插在第n+1个位置；删除第i个元素时，将第n个元素补到第i个位置。五、算法题1、利用线性表的基本操作(教材P19)，实现在线性表A中删除在线性表B中出现的元素。#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct int *elem;int length;int listsize;SqList;void Delete(SqList &A, SqList B) /线性表A、B已存在 B_len=ListLength(B); for(i=1; i=B_len; i+) GetElem(B, i, e); / 用e返回B中第i 个元素的值 n= LocateElem(A, e, equal); / n为e在A中的位序 if ( n!=0) ListDelete(A, n, e ); /删除A中第n个元素 2、编写算法，将一个有n个非零元素的线性表A拆分成两个线性表，其中大于零的元素存放线性表B中，小于零的元素存放在线性表C中。#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct int *elem;int length;int listsize;SqList;void separate(SqList A, SqList &B, SqList &C) /线性表A已存在，B和C不存在 InitList(B); InitList(C); na=A.length; nb=nc=0; for(i=0; i0 ) B.elemnb=A.elemi; nb+; else C.elemnc=A.elemi; nc+; B.length=nb; C.length=nc;3、分别基于线性表的顺序存储结构和链式存储结构（带头结点），实现以下操作：(1) 从线性表中删除具有给定值x的所有元素。(2) 从线性表中删除其值在有给定值s与t之间的所有元素，其中要求s=t ，若s或t不合理，或线性表为空，则显示出错信息并退出程序。(3) 假设线性表的元素按递增顺序排列，删除表中所有大于s且小于t的所有元素（若存在这样的元素），要求s0; i-) /从后面开始删除，可以减少元素的移动次数 if (L.elemi-1 = x ) for( int j=i; jt ) printf( ”s, t的值不合理!n”); return ; for( int i=L.length; i0; i-) /从后面开始删除 if (L.elemi-1 = s & L.elemi-1=t ) for( int j=i; jt ) printf( ”s, t的值不合理!n”); return; for( int i=0; iL.length & L.elemis; i+) /寻找值大于等于s的第1个元素 ； /注意循环体为空语句 if ( i=L.length ) printf(”线性表中所有元素值都小于s!n”); return ; for( int j=i; jL.length & L.elemj=t; j+)； /寻找值大于t的第1个元素 for( int n=i, k=j; kL.length; n+, k+) L.elemn=L.elemk; L.length=L.length-(j-i); (4) void Delete_same(SqList &L) /L为有序表 if( L.length=0) printf(线性表为空!n); return; for( int i=0; iL.length; i+) while( iL.length-1 & L.elemi!=L.elemi+1 ) i+; /寻找重复元素 if(i=L.length-1) break; for( int j=i+1; L.elemj=L.elemi; j+); /寻找与第i个元素不相同的元素 for( int t=i+1, k=j; knext; q=L; while (p!=NULL ) if(p-data!=x) q=p; p=p-next; else q-next = p-next; free(p);p=q-next; (2)void ListDelete_st(LinkList &L, int s, int t) /删除值在st之间的元素 LinkList p,q; if(L=NULL) printf(链表为空！n); return; p = L-next; q=L; while (p!=NULL ) if (p-data=s & p-datanext = p-next; free(p); p=q-next; else q=p; p=p-next; (3) void Delete_st(LinkList &L, int s, int t) / 在有序单链表L中，删除值在st之间的结点 LinkList p, q, p1, p2; if(L=NULL) printf(链表为空！n); return ; p = L-next; while(p!=NULL & p-datanext; / p指向该元素，q指向p的前驱结点 if(p=NULL) printf(链表中所有元素值都小于s!n); return ; while(p!=NULL & p-datanext; p1=q-next; q-next = p; /删除值在st之间的所有结点 while(p1!=p) /循环释放st之间的所有结点的空间 p2=p1; p1=p1-next; free(p2); (4) void Delete_same(LinkList &L) / 在有序单链表L中，删除值相同的多余结点 LinkList p,q; if(L=NULL) printf(链表为空！n); return ; p = L-next; while(p!=NULL & p-next!=NULL) q=p-next; if(p-data!=q-data) p=p-next; else p-next=q-next; free(q); p=p-next; *4、设有一个不带头结点的非空单链表，编写递归算法实现以下操作：(1) 求链表中的结点个数 (2) 求链表中的最大整数（设链表结点的数据域中存放的是整型数据）typedef struct LNode int data;Struct LNode *next;Lnode, *LinkList;(1) int Num(LinkList L) / 链表L已存在 if( L-next=NULL ) return 1; else return (1+Num( L-next); (2) void Max(LinkList L,int &m) / 链表L已存在，找到的最大整数存在m中 int n; if( L-next=NULL ) m=L-data; else Max( L-next, n); m= L-datan?L-data:n; 第3章 栈和队列一、选择题1234567891011BCBBADCADDC二、填空题1. 栈和队列都是 线性 结构，对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。3. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。4. 向栈中插入元素的操作是先 存入元素 ，后 移动栈顶指针 。5. 带表头结点的空循环链表的长度等于 0 。6. 设循环队列Qmaxsize的队头指针为front，队尾指针为rear，则该队列的队满条件是 Q.front=(Q.rear+1)%maxsize 。三、判断题1234567891011四、简答题1.说明线性表、栈与队的异同点。答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。答：至少有14种。 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 假设正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？答：线性表是随机存储，可以实现，靠循环变量从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶设置到数组末尾，然后直接用POP动作实现。若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部入栈后再依次输出。4. 顺序队列的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满、队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N5. 设循环队列的容量为40（序号从0到39）， 现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、算法阅读题1. 答：输出为“stack”。2. 答：输出为“char”。3. 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。六、算法题1. 试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。int PalindromeTest(void) /判别输入的字符串是否回文序列,是则返回1,否则返回0 InitStack(S); InitQueue(Q); /同时使用栈和队列两种结构while(c=getchar()!=) Push(S,c); EnQueue(Q,c); while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); if(a!=b) return 0; return 1; 2. 假设以带头结点的循环链表表示队列，只设一个指向队尾结点的尾指针，不设头指针，分别写出入队列和出队列的算法。typedef struct node ElemType data; Struct node *next; *LinkQueue;void EnQueue(LinkQueue &rear, ElemType e) LinkQueue s; s=(Qnode *) malloc(sixeof(Qnode); s-data=e; s-next=rear-next; rear-next=s; rear=s;void DeQueue(LinkQueue &rear, ElemType &e) LinkQueue h, p; if ( rear=rear-next ) printf(“队空”); return; h=rear-next; p=h-next; e=p-data; if ( p=rear ) rear=h; h-next=p-next; free(p);第6章 树和二叉树一、选择题1234567891011121314CABCADCBCACDAB二、填空题1. 可能最大高度是 n ，叶结点数为 1 ，可能最小高度是 ，叶结点数为 n2+1。2. 一棵完全二叉树有12个叶结点，则该树最多有 24 个结点。答：n0=12， n2=n0-1=11， n=n0+n2+1=12+11+1=243. 先序序列为ABDCEF，中序序列为DBAECF，则后序序列为 DBEFCA 。4. 二叉树的层次遍历需要使用 队列 辅助才能实现。 5. 设二叉树有n个结点，则二叉链表中空指针数为 n+1 。6. 由3个结点所构成的二叉树有 5 种形态。 7. 一棵深度为6的满二叉树有 31 个分支结点和 32 个叶子。答：满二叉树没有度为1的结点，分支结点数就是度为2的结点数。n1+n2=0+ n2= n0-1=31， 26-1 =328 一棵具有257个结点的完全二叉树，它的深度为 9 。答：用 log2(n) +1= 8.xx +1=99. 设一棵完全二叉树有700个结点，则共有 350 个叶子结点。答：因n=n0+n2+1, n2=n0-1, 所以 n=2*n0, n0n/2350 10. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。答：n0n/2500，n2=n0-1=499。 最后一个结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树不可能有左空右不空的情况，所以非空右子树数0.11. 一棵有n(n1)个结点的k叉树，可能的最大深度为 n ，可能的最小深度为 2 。答：当k=1(单叉树)时应该最深，深度n（层）；当k=n-1（n-1叉树）时应该最浅，深度2（层），但不包括n=0或1时的特例情况。三、判断题12345678910111211. 正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）12. n0=n/26，再求n2=n0-1=5四、应用题1. 在一棵度为4的树中，有20个度为4的结点， 10个度为3的结点， 1个度为2的结点，10个度为1的结点，请计算树中度为0的结点个数。(写出计算过程)答：因 n=n0+n1+n2+n3+n4, 总分支数e=n-1, e= n0+n1+n2+n3+n4-1, e=4*n4+3*n3+2*n2+n1 n0=e-n1-n2-n3-n4+1=(4-1)*n4+(3-1)*n3+(2-1)*n2+1=3*20+2*10+1*1+1=822. 一棵二叉树有1024个结点，有叶子结点465个，度为2和度为1的结点各有多少个。答：因n0=n2+1，所以n2=465-1=464，n1=1024-465-464=953. 请画出一棵先序序列和中序序列相同的二叉树（注：空树和只有根结点的树除外）。答：右单枝树的先序序列与中序序列相同abc4. 已知二叉树的层次遍历序列为ABCDEFG，中序序列为DBFEGAC，请画出该树。ACBEDGF5. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。解：要遵循中序遍历的轨迹来画出每个前驱和后继。2825 3340 60 08 54 55中序遍历序列：55 40 25 60 28 08 33 5482540555560330854NULLNULL 2825 33 40 60 08 54 556. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A7. 把如图所示的树转化成二叉树。 五、算法题1. 借助于栈实现二叉树的非递归中序遍历算法。（可以直接使用栈的基本操作）typedef struct BiTNode char data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree; /定义二叉链表的存储结构void Inorder(BiTree T) SqStack S; BiTree p=T; InitStack(S); do while(p!=NULL) Push(S,p); p=p-lchild; if (!StackEmpty(S) Pop(S, p); printf(%c , p-data); p=p-rchild; while(p!=NULL | ! StackEmpty(S) ); 2. 设二叉树以二叉链表做存储结构，编写递归算法实现以下功能：(1) 统计二叉树中度为1的结点个数 (2) 统计二叉树中叶子结点的个数(3) 计算二叉树的高度(4) 删除二叉树中所有的叶子结点(5) 求指定结点的父结点(指定二叉树中某个结点的值)typedef struct BiTNode char data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree; /定义二叉链表的存储结构(1) int Degree1(BiTree T) /计算度为1的结点个数 if (T=NULL) return 0; if( (T-lchild!=NULL & T-rchild=NULL) | (T-lchild=NULL & T-rchild!=NULL) return 1; return Degree1(T-lchild)+Degree1(T-rchild); (2) int leaves(BiTree T) /计算叶子结点的个数 if (T=NULL) return 0; if( T-lchild=NULL & T-rchild=NULL) return 1; return leaves(T-lchild)+leaves(T-rchild);(3) int Height(BiTree T) /计算二叉树的高度 int Lh, Rh, h; if (T=NULL) return 0; Lh=Height(T-lchild);Rh=Height(T-rchild);h=LhRh?Lh: Rh;return(h+1);(4) void del_leaves(BiTree &T) /删除所有叶子结点 if (T=NULL) return; if( T-lchild=NULL & T-rchild=NULL) free(T); T=NULL; else del_leaves(T-lchild); del_leaves(T-rchild); (5) void parent(BiTree T,BiTree &p,char x) /求指定结点值为x的父结点 if (T=NULL) p=NULL; if( T-lchild!=NULL & T-lchild-data=x | T-rchild!=NULL & T-rchild-data=x) p=T; if(T-lchild!=NULL) parent(T-lchild,p,x); if(T-rchild!=NULL) parent(T-rchild,p,x);3. 设二叉树以二叉链表做存储结构，利用先序遍历求先序序列中的第k个结点。BiTree search_k(BiTree T, int &count, int k) /count必须是引用参数 BiTree p;if (T) count+; if(count=k) return T; if( p=search_k(T-lchild, count, k) return p; if( p=search_k(T-rchild, count, k) return p;return NULL;4. 设二叉树以二叉链表做存储结构，编写算法判断一个二叉树是否是完全二叉树。算法思想：利用层次遍历，让二叉树的结点逐层入队列，如果中间出现空结点，则说明该树不是完全二叉树。算法返回1表示是完全二叉树，返回0表示不是完全二叉树int CompleteBiTree(BiTree T) LinkQueue Q; int flag=0;if(T=NULL) return 1;InitQueue(Q);EnQueue(Q,T); while( !QueueIsEmpty(Q) ) DeQueue(Q,T); if(T=NULL) flag=1;elseif(flag) return 0;else EnQueue(Q,T-lchild); EnQueue(Q,T-rchild); DestroyQueue(Q);return 1;第7章 图一、选择题123456789101112131415161718CBBCCBADCDACADAADA二、填空题1. 图的存储结构最常用的有 邻接矩阵 、 邻接表 ，遍历图的方法有： 深度优先遍历 、 广度优先遍历 等。2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。3. 如果n个顶点的图是一个环，则它有 n 棵生成树。 4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。6. 设有一稀疏图G，则G采用 邻接表 存储较省空间。7. 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。8. 图的逆邻接表存储结构只适用于 有向 图。9. 图的深度优先遍历序列 不是 惟一的。10. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。11. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。12. Prim算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。13. 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。14. 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解。15. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。16. 求最短路径的Dijkstra算法的时间复杂度是 O(n2) 。17. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。三、判断题123456789四、简答题1. 50个顶点、15条边的有向图的邻接矩阵有多少个矩阵元素？该矩阵是否是稀疏矩阵？答：50*50=2500 有2500个矩阵元素，15/2500=0.0060.05 该矩阵是稀疏矩阵2.有n个顶点的无向图最多有几条边，最少有几条边；如果该图是连通图，则该图最多有几条边，最少有几条边？答：无向图最多有n(n-1)/2边，最少有0条边。无向连通图最多有n(n-1)/2边，最少有n-1条边。3. 有n个顶点的有向图最多有几条边，最少有几条边；如果该图是强连通图，则该图最多有几条边，最少有几条边？答：有向图最多有n(n-1)边，最少有0条边。强连通图最多有n(n-1)边，最少有n条边。4、对下面所示的有向图，请回答：该图是强连通图吗？若不是，请画出其强连通分量。答：该图不是强连通图。有6个强连通分量，即各个顶点。 五、应用题1. 已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻