搜索
习题第1章习题一、选择题1、下列关于算法的说法，正确的是。A.算法的可行性是指指令不能有二义性B.算法最终必须由计算机程序实现C.程序一定是算法D.为解决某问题的算法与为该问题编写的程序含义是相同的2、以下关于数据的存储结构的叙述中，正确的有。A.顺序存储方式只能用于存储线性结构B.顺序存储方式的优点是存储密度大，且插入、删除运算效率高C.链表的每个节点中都恰好包含一个指针D.散列法存储的基本思想是由关键字的值决定数据的存储地址E.散列表的节点只包含数据元素自身的信息，不包含任何指针3、下列说法正确的是。A.数据元素是具有独立意义的最小标识单位B.原子类型的值不可再分解C.原子类型的值由若干个数据项值组成D.结构类型的值不可以再分解二、判断题1、数据项是具有独立含义的最小标识单位。2、数据的逻辑结构是指各数据元素之间的逻辑关系，与物理结构无关。3、运算的定义依赖于逻辑结构，运算的实现也依赖于逻辑结构，而与存储结构无关。4、数据结构是指相互之间存在一种或多种关系的数据元素的全体。三、填空题1、数据的逻辑结构被分为、、、四种。2、当问题规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的。3、时间复杂度在最好和最坏情况下分别是和。4、通常从正确性、、及时空效率等四个方面评价算法的质量。5、数据的存储结构主要有顺序存储、、和四种。四、算法设计1、写一算法，从键盘输入若干个非0整数（以0作为结束标志），找出其中最大和最小的数，并分析算法的时间复杂度（输入数据不需保存）。2、在数组A[1..n]中查找值为K的元素，若找到则输出其位置i（1≤i≤n），否则输出0作为没有找到的标志，并分析算法的时间复杂度。第2章习题一、选择题1、线性表在链式存储中，各结点之间的地址是。A.必须连续B.部分地址必须连续C.不能连续D.连续与否无所谓2、对单链表表示法，以下说法错误的是。A.数据域用于存储线性表的一个数据元素B.指针域用于存放直接后继结点的指针C.所有数据通过指针的链接而组成单链表D.单链表中各结点地址不可能连续3、某线性表中最常用的操作是在最后一个元素之后插入一个数据和删除第一个元素，则采用存储方式最节省运算时间。A.单链表B.仅有尾指针的单循环链表C.双向链表D.仅有头指针的单循环链表4、线性表（a1,a2,....,an）以链式方式存储时，访问第i个元素的时间复杂性为。A.O(n)B.O(1)C.O(i)D.O(i-1)二、判断题1、顺序表可以用一维数组表示，因此顺序表与一维数组在结构上是一致的，可以通用。2、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。3、链式存储结构中，访问任何结点都必须从表头开始。4、循环链表可以在尾部设置头指针。三、填空题1、已知L是无表头结点的单链表，且P结点即不是首结点，也不是尾结点，试在下述要求中填上适合的语句序列。（1）在P结点之后插入S结点语句序列。S-next=p-next;p-next=S;（2）在P结点之前插入S结点语句序列。pre=L;while(pre-next!=P)pre=pre-next;S-next=pre-next或P;pre-next=S;2、已知P结点是某双向链表中的中间结点，请填空。（1）在P结点之后插入S结点的语句序列。S-next=P-next;S-prior=P;P-next-prior=S;P-next=S;（2）删除P结点的直接后继结点的语句序列。Q-P-next;P-next=Q-next;Q-next-prior=P;free(Q);四、算法设计1、设L为带头结点的单链表，编写算法，删除链表中值相同的元素，并分析算法时间复杂性。假设单链表L元素递增有序。2、已知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个集合的交集运算A=A∩B。第3章习题一、选择题1、栈与一般线性表的区别在于。A.数据元素的类型不同B.数据元素的个数不同C.运算是否受限制D.逻辑数据不同2、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是。A.3B.4C.5D.63、若已知一个栈的入栈序列是1,2,3,…,30，其输出序列是p1,p2,p3,…,pn，若p1=30，则p10为。A.11B.20C.30D.214、循环队列A[m]存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是。A.（Q-rear+1）%m==Q-frontB.Q-rear+1==Q-frontC.Q-rear==Q-front+1D.Q-rear==Q-front5、设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列是。A.fedcbaB.cabdefC.dcefbaD.bcafed二、判断题1、消除递归一定需要使用栈。2、栈与队列是一种特殊的线性表。3、队列逻辑上是一端既能增加又能减少的线性表。4、任何一个递归过程都可以转换为非递归过程。三、填空题1、已知一个栈s的输入序列为abcd，判断下面两个序列能否通过的Push和Pop操作输出：（1）dbca。（2）cbda。2、假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是。3、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是。四、算法设计1、已知Q是一个非空队列，S是一个空栈，仅用队列和栈的基本操作和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。2、假设称正读和反读都相同的字符序列为“回文”，例如“123321”、“abcdedcba”是回文，“asdasd”不是回文。试编写一个算法判断读入的一个以“@”为结束符的字符序列是否为回文。第4、5章习题一、选择题1、下列关于串的叙述中，不正确的是。A.串是字符的有限序列B.模式匹配是串的一种重要运算C.空串是由空格构成的串D.串既可采用顺序存储，也可以采用链式存储2、已知串S=“aaab”，其next数组值为。A.0,1,2,3B.1,1,2,3C.1,2,3,1D.1,2,1,13、串ababaabab的next数组值为。A.0,1,2,3,4,5,6,7,8B.0,1,1,2,3,4,5,3,4C.0,1,2,1,2,1,1,1,2D.0,1,2,3,0,1,2,2,24、在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置为。A.主串的最末字符B.模式串的第一个字符C.主串的第一个字符D.模式串的最末字符二、判断题1、串是一种数据对象和操作都特殊的线性表。2、空串与空格串是相同的。3、KMP算法的特点是在模式匹配时指示主串的指针不会变小。4、从串中取若干个字符组成的字符序列称为串的子串。三、填空题1、两个串相等的充分必要条件是。串长度相等且对应位置上的字符也相等2、StrIndex(MYSTUDENT,STU)=。四、算法设计1、利用C的库函数strlen,strcpy写一算法voidStrDelete（char*S,inti,intm）,删除串S中从位置i开始的连续m个字符。若i≥strlen（S），则没有字符被删除；若i+m≥strlen（S），则将S中位置i开始直至末尾的字符都删去。2、设s,t为两个字符串，试写一算法判断t是否为s的子串。五、简答题求下面各广义表的操作结果。(1)GetHead((a,(b,c),d))(2)GetTail((a,(b,c),d))(3)GetHead(GetTail((a,(b,c),d)))(4)GetTail(GetHead((a,(b,c),d)))第6章习题一、选择题1、下面关于二叉树的描述中，正确的是。A.二叉树中，度为0的结点个数等于度为2的结点个数加1B.完全二叉树中，任何一个结点的度或者为0，或者为2C.二叉树中结点个数必大于0D.二叉树的度为22、对一个满二叉树，m个树枝，n个结点，深度为h，则。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-13、以二叉链表作为二叉树的存储结构，在有n个结点的二叉链表中（n0），链表中空链的个数为。A.2n-1B.n-1C.n+1D.2n+14、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为。A.33B.34C.35D.365、在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序。A.都不相同B.先序和中序相同，而与后序不同C.完全相同D.中序和后序相同，而与先序不同6、一棵二叉树满足下列条件：对任意一个结点，若存在左、右子树，则其值都小于它的左子树上的所有结点的值，而大于右子树上所有结点的值。现采用遍历方式就可以得到这棵二叉树上所有结点的递减序列。A.先序B.中序C.后序D.层次7、由3个结点可以构造出种不同的二叉树。A.3B.4C.5D.68、设给定权值的叶子总数有n个，其赫夫曼树的结点总数为。A.不确定B.2nC.2n+1D.2n-19、某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是。A.高度等于结点数B.完全二叉树C.单支树D.空或只有一个结点10、在一棵三叉树中，已知度为3的结点数等于5，度为0的结点数等于17，则度为2的结点数等于。A.6B.5C.4D.3二、判断题1、有非空的一棵二叉树，已知先序和后序遍历的序列，则能惟一确定该二叉树。2、完全二叉树中，若一个结点没有左孩子，则它一定是叶子。3、将一棵树转换成二叉树后，根结点没有左子树。4、必须把一般树转换成二叉树后才能存储。三、填空题1、已知二叉树有10个叶子结点，则该二叉树的总结点数至少是。2、叶子权值（3,6,7,2）所构造的赫夫曼树带权路径长度为。3、N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号，若：（1）任一结点的编号等于它的左子树中最小编号减1，则为遍历；（2）某结点右子树中最小编号等于左子树中的最大编号加1，则为遍历。4、40个结点的完全二叉树，编号最大的非叶子结点是号结点，编号最小的叶子结点是号结点。四、算法设计1、写出中序遍历的递归和非递归算法。2、编写一算法，计算二叉树T中结点的个数。五、简答题1、写出下列二叉树的先序遍历、中序遍历、后序遍历序列。2、给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，给出各字符的编码值。第7章习题一、选择题1、具有5个顶点的有向图至少应有条边才能确保一个强连通图。A.4B.5C.6D.72、在一个无向图中，所有顶点的度数之和等于所有边数B倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的C倍。A.21B.2C.1D.43、下列图的邻接矩阵是对称矩阵的是。A.有向图B.AOV网C.AOE网D.无向图4、关键路径是指AOE（ActivityOnEdge）网中。A.最长的回路B.最短的回路C.从源点到汇点的最长路径D.从源点到汇点的最短路径5、在有向图的邻接表存储结构中，顶点v在链表结点中出现的次数是。A.顶点v的入度B.顶点v的出度C.顶点v的度D.依附于顶点v的边数6、下面的叙述中，不正确的是。A.任何关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C.所有关键活动都提前完成，将使整个工程提前完成D.所有关键活动不按期完成就会影响整个工程的完成时间7、无向图G=（V，E），其中V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列是。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b8、G是一个非连通的无向图，共有28条边，则