数据结构期末复习题答案

第1页共9页《数据结构》复习题（含部分参考答案版）一、单项选择题1.按照数据逻辑结构的不同，可以将数据结构分成C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.下列关于数据结构的叙述中正确的是A。A.数组是同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为复杂C.树是一种线性的数据结构D.用一维数组存储二叉树，总是以先序顺序遍历各结点3.在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为BA.逻辑结构B.顺序存储结构C.链式存储结构D.以上都不对4.以下关于算法特性的描述中，B是正确的。（1）算法至少有一个输入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去A.（1）B.（2）C.（3）D.（2）和（3）5.对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是C。A.O(n)B.O(n-i)C.(n/2)D.O(n-1)6.链表不具有的特点是A。A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比7.线性链表中各链结点之间的地址C。A.必须连续B.部分地址必须连续C.不一定连续D.连续与否无关第2页共9页8.以下关于链式存储结构的叙述中，C是不正确的。A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的存储地址D.插入、删除操作方便，不必移动结点9.设依次进入一个栈的元素序列为d,a,c,b,得不到出栈的元素序列为D。A.dcbaB.acdbC.abcdD.cbda10.将新元素插入到链式队列中时，新元素只能插入到B。A.链头B.链尾C.链中D.第i个位置，i大于等于1，大于等于表长加111.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是C。A.6B.4C.3D.212.下面D是‘abcd321ABCD’的子串。A.abcdB.321abC.‘abcABC’D.‘21AB’13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时C元素相同。A.a[7，3]B.a[8，3]C.a[1，4]D.ABC都不对14.数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为A。A.1175B.1180C.1205D.121015.下列广义表中，长度为3的广义表为B。A.（a,b,c,()）B.((g),(a,b,c,d,f),())C.(a,(b,(d)))D.((()))16.以下关于广义表的叙述中，正确的是A。A.广义表是0个或多个单元素或子表组成的有限序列B.广义表至少有一个元素是子表C.广义表不可以是自身的子表第3页共9页D.广义表不能为空表17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有D个叶结点。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是B。A.100B.101C.102D.10319.在有n个叶子结点的霍夫曼树中，其结点总数为：。A.nB.2nC.2n+1D.2n-120.具有12个结点的完全二叉树有B。A.5个叶子结点B.5个度为2的结点C.7个分支结点D.2个度为1的结点21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x在y之后，则x和y的关系是C。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的后代22.先序遍历序列与中序遍历序列相同的二叉树为。A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树23.若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf，则其后序遍历序列为A。A.ceadfbB.feacdbC.eacdfbD.以上都不对24.设无向图的顶点个数为n，则该图最多有C条边。A.n-1B.n(n-1)C.n(n-1)/2D.n25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是C。A.e/2B.eC.n+2eD.n+e26.无向图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)｝。第4页共9页对该图进行深度优先遍历，下面不能得到的序列是D。A.acfdebB.aebdfcC.aedfcbD.abecdf27.在下述排序方法中，不属于内排序方法的是C。A.插入排序法B.选择排序法C.拓扑排序法D.归并排序法28.直接插入排序在最好情况下的时间复杂度为B。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)29.对有n个记录的表作快速排序，在最坏情况，算法的时间复杂度是D。A.O(n3)B.O(n)C.O(nlog2n)D.O(n2)30.下面的排序算法中，稳定是A。A.直接插入排序法B.快速排序法C.直接选择排序法D.堆排序法二、填空题1.一个算法具有5个特性：、、、有零个或多个输入，一个或多个输出。2..设数组a[1…50，1…80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为9174；若以列序为主序顺序存储，则元素a[45，68]的存储地址为8788。3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。4.两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。5.字符串“abcd”中共有个长度大于0的字串。6.广义表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的长度及深度分别为和。7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点。8.若无向图满足有n-1条边的连通图，则该图是树。9.若无向图中有n个顶点，则其边数最少为n-1，最多为n(n-1)/2。10.堆排序的时间复杂度和空间复杂度分别为O(nlog2n)和O(1)。第5页共9页三、名词解释（1）抽象数据类型（2）算法及其特性（3）串的模式匹配（4）优先级队列（5）完全二叉树（6）堆（7）Huffman编码（8）Huffman树（9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法（12）普里姆算法（13）希尔排序（14）快速排序（15）教材等等相关名次解释题四、简答题1.请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题）2.单链表为什么要引入头结点？3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？参考答案：单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比，它还节省了空间。循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结点。缺点同单链表的缺点。双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。4.内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。5.假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。问：（1）能否得到下列的输出序列：①B，C，D，E，A；②E，A，B，C，D；③E，D，C，B，A。（2）写出所有可能正确的输出序列（至少5种）。6.用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。参考答案：队空条件为max_size==1;队满的条件为（max_size+1）%MAXSIZE.7.设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求：（1）画出该二叉树；（2）写出该二叉树的先序遍历序列；（3）画出该二叉树对应的森林。8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序列为AEBGFDIMH，中序遍历序列为GEFAMDBHI。第6页共9页请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子—兄弟表示，请画出该森林。（西电2004年考研试题）9.已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为23、5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。10.给定下列图G用两种不同表示法画出该图的存储结构图。11.针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。（1）100，90，80，60，85，75，20，25，10，70，65，50（2）100，70，50，20，90，75，60，25，10，85，65，8014.已知一序列（12，70，33，65，24，56，48，92，86，33），问该序列是否是堆？如果不是，则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电2005年考研试题）15.试为下列情况选择合适的排序算法：（西电2006年考研试题）（1）n=30，且要求最坏情况下速度最快；（2）n=30，且要求既要快，又要排序稳定；（3）n=2000，要求平均情况下速度最快；（4）n=2000，要求最坏情况下速度最快，又要节省存储空间。五、算法设计题ABGFEDC48122420121510第7页共9页1.实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。（教材P74页）2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value的新结点并将其插入到当前结点之后。（教材P91页）（b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前指针指到链表中下一个结点位置。（教材P91页）3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材P107页）（b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材P117页）4.对二叉链表，实现一个函数Parent(*BinTreeNodeType*start,*BinTreeNodeType*curent)从结点start开始，搜索结点current的双亲结点，并返回其地址，否则返回NULL。（教材P171页）5.若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法：（1）统计二叉树中叶子结点的个数；（2）交换每个结点的左子女和右子女。6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法7.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完成下面的入队列和出队列的算法：（西电2004年考研试题）#defineMAXQSIZE100//最大队列长度Typestruct｛Qelemtype*base;//base为队列所在区域的首地址intlength;//队列长度intrear;//队尾元素位置｝SqQueue;StatusEnQueue(SqQueue&Q,Qelemt