数据结构自测题答案.docx

《数据结构自测题答案.docx》由会员分享，可在线阅读，更多相关《数据结构自测题答案.docx（33页珍藏版）》请在三一办公上搜索。

1、第1章绪论一、选择题12345678CCADABCC二、填空题1. 4种基本结构是：集合、线性结构、树形结构、图状结构。2. 树形结构中元素的关系是一对多，图形结构中元素的关系是多对多。3. 顺序存储结构中数据元素的存储位置与其逻辑顺序是对应的。4. 算法效率的度量方法有：事后统计方法和事前分析估算方法。5. 好算法应达到的目标：正确性、可读性、健壮性、执行时间短、存储量低。6. 抽象数据类型可细分为3种：原子类型、固定聚合类型和可变聚合类型。7. 抽象数据类型的定义包括：数据对象的定义、数据关系的定义、基本操作的定义。三、判断题1234567891011VXVXVVXXXVX五、应用题1.

2、按增长率从小到大的顺序排列下列各函数：(2/3)n，log2n，n，n2, n!2. 写出以下各函数的功能，并求出其时间复杂度。 功能是判断n是否为素数，时间复杂度为O(n )。 功能是计算1!+2!+.+n!，时间复杂度为O(n )。 功能是计算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; iMAX

3、INT (OWkWn)时，应进行出错处理。算法思想：先判断n的取值是否合法，若非法则直接退出程序，若n合法则继续计算2i， 在计算2i时，需要判断2i的值是否大于MAXINT/2,这个条件其实就是判断2i+i的值是否大于MAXINT#define arrsize 100#define MAXINT 65535 void 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”

4、，i+1)； break;第2章线性结构一、选择题1234567891011121314151617ABCADBBACACBBBDCD二、填空题1. 需向后移动p-i+1 个兀素。2. 应采用顺序存储结构。3. 有/个结点的单链表，在x的结点后插入一个新结点的时间复杂度为O(n) 。4. 可以将线性链表分成 单链表 和多重链表。5. 链接存储的特点是利用_指针来表示数据元素之间的逻辑关系。6. 顺序存储结构是通过 物理位置相邻一 表示元素之间的关系的;链式存储结构是通过 指针表示元素之间的关系的。7. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素。8. 带头结点的单循环链

5、表L, L为空表的条件是：_L-next=二L 。三、判断题12345678XXXXXXXV四、简答题1. 对线性表中的插入操作，分别写出顺序存储结构和链式存储结构下的时间复杂度。答：O(n), 0(1)2. 线性结构的特点是什么？答：在数据元素的非空有限集中，(1)存在唯一的一个被称为“第一个”的数据元素;(2)存 在唯一的一个被称为“最后一个”的数据元素;(3)除第一个之外，集合中的每个元素均只 有一个前驱;(4)除最后一个之外，集合中每个元素均只有一个后继3. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结 点的关系。答：在线性表的链式存储结构中，头指针指链表

6、的指针，若链表有头结点则是链表的头结 点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统 一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(有些情况下也可存放 链表的长度、用做监视哨等)，有头结点后，对在第一元素结点前插入结点和删除第一结 点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元 结点也就是第一元素结点，它是头结点后边的第一个结点。4. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点？答：在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点， 链表只能从头指针开始，访问到链表中每个结点。

7、在双链表中求前驱和后继都容易，从当 前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。*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

8、;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#de

9、fine 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、分别基于线性表的顺序存储结构和链式存储结构

10、(带头结点)，实现以下操作：从线性表中删除具有给定值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 =

11、 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.e

12、lemk;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;wh

13、ile (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-ne

14、xt; 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!=

15、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

16、) 求链表中的结点个数(2) 求链表中的最大整数(设链表结点的数据域中存放的是整型数据)typedef struct LNode int data;Struct LNode *next;Lnode, *LinkList;(1) int Num(LinkList L) / 链表 L 已存在 if( L-next=NULL ) return 1;elsereturn (1+Num( L-next);void Max(LinkList L,int &m)/链表L已存在，找到的最大整数存在m中 int n;if( L-next=NULL ) m=L-data;else Max( L-next, n);

17、m= L-datan?L-data:n;第3章栈和队列一、选择题1234567891011BCBBADCADDC二、填空题1. 栈和队列都是 线性 结构，对于栈只能在栈顶插入和删除元素；对于队列只能在队尾 插入和 队首删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底 。3. 在具有n个单元的循环队列中，队满时共有n-1个元素。4. 向栈中插入元素的操作是先存入元素，后移动栈顶指针。5. 带表头结点的空循环链表的长度等于0。6. 设循环队列Qmaxsize的队头指针为front，队尾指针为rear，则该队列的队满条件是 Q.front=(

18、Q.rear+1)%maxsize 。三、判断题1234567891011VXXVVXXVXXV四、简答题1. 说明线性表、栈与队的异同点。答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和 队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点: 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是 后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2. 设有编号为1，2, 3, 4的四辆列

19、车，顺序进入一个栈式结构的车站，具体写出这四辆 列车开出车站的所有可能的顺序。答：至少有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,12,3,4,12,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 则不是回文。假设一字符序列已存

20、入计算机，请分析用线性表、堆栈和队列 等方式正确输出其回文的可能性？答：线性表是随机存储，可以实现，靠循环变量从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表 从后往前读取即可，或将堆栈栈顶设置到数组末尾，然后直接用POP动作实现。若正文 是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部入栈后再 依次输出。4. 顺序队列的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数

21、组 中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满、队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数(即队列长度)。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是：f=rear队满标志是：f=(r+1)%N5. 设循环队列的容量为40 (序号从0到39)，现经过一系列的入队和出队运算后，有front=11，rear=19; front=19，rear=11 ；问这两种情况下，循环队列中各有元素 多少个？答：用队列长度计算公式：

22、(N+rf)% N L= (40+19 11) % 40=8 L= (40+11 19) % 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);wh

23、ile(!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-nex

24、t;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，可能最小高度是Llog2n+1 ,叶结点数为n2+1。2. 一棵

25、完全二叉树有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的结点数。气+明=0+ 明=%-1=31，26-1 =328. 一棵具有257个结点的完全二叉树，它的深度为9。答：用L log2（

26、n）+1= L 8.xx+1=99. 设一棵完全二叉树有700个结点，则共有350个叶子结点。答：因 n=n0+n2+1, n2=n0-1,所以 n=2*n0, n0=n/2 = 35010. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499 个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。答：n0=n/2=500，n2=n0-1=499。最后一个结点为2i属于左叶子，右叶子是空的，所 以有1个非空左子树。完全二叉树不可能有左空右不空的情况，所以非空右子树数=0.11. 一棵有n（n 1）个结点的k叉树，可能的最大深度为n ，可能的最小深度为2

27、 。 答：当k=1（单叉树）时应该最深，深度=n （层）；当k=n-1 （n-1叉树）时应该最浅，深度 =2 （层），但不包括n=0或1时的特例情况。三、判断题123456789101112VVXVXVXXXXVV11.正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中， 除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子 女结点的指针，还有n+1个空指针。）12. n0=n/2 = 6，再求 n2=n0-1=5四、应用题1. 在一棵度为4的树中，有20个度为4的结点，10个度为3的结点，1个度为2的结 点，10个度为1的结点，请计算树中度

28、为0的结点个数。（写出计算过程）答：因 n=n0+n1 +n2+n3+n4, 总分支数 e=n-1, e= n0+n1+n2+n3+n4-1,JL。IjJL。=4*%+3*%+252+%n _p n n n n11*” ifQ 1l*n -kf? 1 l*n _l 1 1 H_l 1 *1_l12?n一e-n -n-n-ni+1（4-1）n.+（3-1）n+2-1）n+1320+210+11+1022. 一棵二叉树有1024个结点，有叶子结点465个，度为2和度为1的结点各有多少个。答：因 n0n2+1，所以 n2465-1464，n11024-465-464953. 请画出一棵先序序列和中序

29、序列相同的二叉树（注：空树和只有根结点的树除外）。 答：右单枝树的先序序列与中序序列相同4.已知二叉树的层次遍历序列为ABCDEFG，中序序列为DBFEGAC，请画出该树。料、少、/40 6008 5425/3 nul406。0854mirjr 4!E :1 为NUL5.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60 28 08 33 54MIRI、3，6. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR： A B D F J G K C E H I L M LDR: B

30、F J D G K A C H E L I M LRD： 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-lchil

31、d; if (!StackEmpty(S) Pop(S, p);printf(%c ”, p-data);p=p-rchild;while(p!=NULL II ! StackEmpty(S);2. 设二叉树以二叉链表做存储结构，编写递归算法实现以下功能:(1) 统计二叉树中度为1的结点个数(2) 统计二叉树中叶子结点的个数(3) 计算二叉树的高度(4) 删除二叉树中所有的叶子结点(5) 求指定结点的父结点(指定二叉树中某个结点的值)typedef struct BiTNode char data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree

32、;定义二叉链表的存储结构int Degree1(BiTree T) 计算度为1的结点个数if (T=NULL) return 0;if( (T-lchild!=NULL & T-rchild=NULL) II (T-lchild=NULL & T-rchild!=NULL) return 1;return Degree1(T-lchild)+Degree1(T-rchild);int leaves(BiTree T)计算叶子结点的个数if (T=NULL) return 0;if( T-lchild=NULL & T-rchild=NULL) return 1;return leaves(T-

33、lchild)+leaves(T-rchild);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

34、(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(BiTr

35、ee 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表示不是完全二叉树 in

36、t 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;一、选择题123456789101112131415161718CBBCCBADCDACADAADA二、填空题

37、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条边的图采用邻接矩阵存储，深

38、度优先遍历算法的时间复杂度为_0虹 若采用邻接表存储时，该算法的时间复杂度为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算法求某一顶点到其余各顶点间

39、的最短路径是按路径长度递增 的次序来得到最短路径的。16. 求最短路径的Dijkstra算法的时间复杂度是O(n2)。17. 拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。三、判断题123456789XXVVXVVXV四、简答题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个顶点的有向图最多有几条边，最少有几条边；如果该图是强连通图，则该图最 多有几条边，最少