《数据结构与算法》期末练习题(含答案)

1、数据结构与算法期末练习一选择题1. 以下与数据的存储结构无关的术语是（D）。A.循环队列B.链表C.哈希表D.栈2. 算法的时间复杂度取决于（A）A问题的规模B.待处理数据的初态C.A和BD.计算机cpu3. 一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.154324. 有关静态链表的叙述：（1）静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。（2）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移

2、动。以上错误的是（B）A（1），（2）B（1）C（1），（2）,（3）D.（2）5对于有n个结点的二叉树,其高度为（D）Anlog2nBlog2nC?log2n?|+1D不确定6从下列有关树的叙述中,选出正确的叙述（C）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B.当KA1时高度为K的二叉树至多有2k-1个结点。C.哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。D.在二叉树中插入结点，该二叉树便不再是二叉树。7.设无向图的顶点个数为n,则该图最多有（B）条边。A n-1B n(n-1)/2C n(n+1)/2En28已知有向图G=(V,E)，其中V=V

3、1,V2,V3,V4,V5,V6,V7，E=<V1,V2>,<V1,V3>, <V1,V4>, <V2,V5>,<V3,V5>,<V3,V 6>, <V4,V6>, <V5,V 7>,<V6,V7>,G的拓扑序列是（AA V1,V3,V4,V6,V2,V5,V7V1,V3,V2,V6,V4,V5,V7C V1,V 3,V4,V5,V2,V6,V7V1,V2,V5,V3,V4,V6,V79下列排序算法中，其中（A. 堆排序，冒泡排序B.快速排序，堆排序是稳定的。C. 希尔排序，归并排序D.

4、归并排序，冒泡排序10对一组数据（84，47，2515，21）排序，数据的排列次序在排序的过程中的变化为1)8447251521(2)1547258421(3)1521258447(4)152125478411.则采用的排序是（A）。A.选择B.冒泡C.快速D.插入12以下数据结构中，哪一个是线性结构（D）A.广义表B.二叉树C.稀疏矩阵D.串13下面关于线性表的叙述中，错误的是哪一个（B）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。14. 设

5、一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A.51234B.45132C.43125D.15. 设n为正整数.下列程序段中前置以的语句的频度为（B）i=1;k=0;dok+=10*i;i+;While（i<=n-1）;A.n-1B.nC.n+1D.n-216. 一棵具有n个结点的完全二叉树的树高度（深度）是（A）A?logn?+1Blogn+1C?logn?Dlogn-117. 一个栈的输入序列为123-n,若输出序列的第一个元素是n,输出第i（1<=i<=n）个元素是（B）。n-iA. 不确定B. n-i+1C. iD.D ）。18.

6、 n个结点的完全有向图含有边的数目（A.n*nB.n（n+1）C.n/2D.n*（nl）19稳定的排序方法是（B）A直接插入排序和快速排序B折半插入排序和起泡排序C希尔排序和四路归并排序D树形选择排序和shell排序20有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为（A）（按递增序）。A.下面的B,CD都不对。B.9,7,8,4,-1,7,15,20C20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2021以下那一个术语与数据的存储结构无关（A）A.栈B.哈希表 C.线索树D.双向链表22下面关于串的的叙述中，哪一个是不

7、正确的（B）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储23. 某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（D）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b24.关于二叉树的叙述：只有一个结点的二叉树的度为0；二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉关的结点个数小于或等于深度相同的满二叉关。正确的是（D）A.B.C.D.25高度为K的二叉关最大的结点数为（C）。A2kB2k-1C2k-1D2k-1-126从下列有关树的叙述中,选出正确

8、的叙述（C）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B.当KA1时高度为K的二叉树至多有2k-1个结点。C.用树的前序遍历和中序遍历可以导出树的后序遍历。D.哈夫曼树是带权路径最长的树，路径上权值较大的结点离根较近。27 .关键路径是事件结点网络中（A）。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路28 .用DFS遍历一个无环有向图，并在DFS#法退栈返回时打印相应的顶点，则输出的顶点序列是（A）。A.逆拓扑有序29一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果

9、为(C)A(38,40,46,56,79,84)B.(40,38,46,79,56,84)C(40,38,46,56,79,84)D.(40,38,46,84,56,79)30. 一个向量的第一个元素的地址是begin，每个元素的长度是k，则第i个元素的地址是(D)A.begin+(k-1)iB.begin+(k-2)iC.begin+kiD.begin+(i-1)k31. 有一个有序表为1，3，9，12，32，41，45，62，77，88，92，100，用折半查找法，若要找63，要经过(C)次与63比较。A.12B.6C.4D.532. 一个序列的初始状态为(46，77，82，53，31，7

10、0)，今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为(D)。A. (31，46，70，53，77，82)B. (46，77，53，31，70，82)C. (46，31,82，53，77，70)D. (46，53，31，70，77，82)33. 将一个长度为n的向量的第i个元素删除时，需要前移(B)个元素。A.iB.n-iC.n+1D.n-i+134. 不带表头的单链表，头指针为head，判断其是否为空的条件是(A)A.head=0B.head->next=nullC.head=headD.head->next=head35. 在一个单链表中，已知*q是(*q表示指针q所指

11、的结点，以下同)*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是(A)。A)q->next=s;s->next=pB)s->next=p->next;q->next=s;C)p->nexr=s;s->next=p;D)p->next=s;s->next=q;36. 非空循环链表head的尾结点*p满足下列(C)条件A)head->next=p;B)head=p;C)p->next=head;D)p->next=037. 一个栈的输入序列是a,b,c,d,e，则可能的出栈序列是(D)。A.ecdabB)cebda

12、C)daecbD)abcde38. 设栈s的类型为sqstack，判定栈空的条件是(C)。A.s=NULLB)s->top=0C)=0D)=NULL39. 深度为5的二叉树至多有个(B)结点。A.12B.31C.14D.1540. 已知二叉树的后、中根序列分别是bedfca和badecf，则该二叉树的前根遍历序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba41. 一个有n个顶点的有向图最多有(B)弧A)n(n+1)B)n(n-1)C)n(n+1)/2D)n(n-1)/242. 具有n个顶点的无向图至少要有(B)条边才有可能是一个连通图。A)n(n+1)B)n

13、-1C)n+1D)n(n-1)43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是(B)。A)1234B)1423C)1324D)143244. 一个向量的第一个元素的地址是100,每个元素的长度是2,则第五个元素的地址是(C)A)102B)110C)108D)12045. 一个循环顺序队列，队头、尾指针的值分别为front,rear则队列中元素个数为 ( A )maxlen 为循环顺序表的长度)A. (rear-front+maxlen)%maxlenB. (rear-front)%maxlenC. rear-front+1D. front-rear+146. 一

14、个有n个顶点的图最少有(D)条边。A)n(n+1)B)n(n-1)C)n(n+1)/2D)047. 具有5个顶点的无向图至少要有(A)条边才能确保是一个连通图。A)4B)5C)6D)748. 设栈s的类型为sqstack，最多可容纳maxlen个元素，则判定栈满的条件是(B)。A.s=maxlen-1B)=maxlen-1C)s->top=maxlen-1D)=049. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是(C)。A)front=rearB)rear=0C)=D)rear=maxlen-150. 在具有

15、n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)(1) (n)(nlogn)(n*n)51. 链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况52. 二叉树中第5层上的结点个数最多为(C)53. 下列编码中属前缀码的是(A)A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,1154. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用(B)A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法55. 对n个

16、关键字的序列进行快速排序，平均情况下的空间复杂度为(B)(1) (logn)(n)(nlogn)56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为(C)C.(n+1)/2D. n57. 对于哈希函数H(key)=key%13,被称为同义词的关键字是(D)和41和39和44和5158. 关于线性表的说法,下面选项正确的是(B)A线性表的特点是每个元素都有一个前驱和一个后继B线性表是具有n(n>=0)个元素的一个有限序列C线性表就是顺序存储的表D线性表只能用顺序存储结构实现59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相

17、等时，删除一个元素需要移动元素的平均个数为(A)A(n-1)/2Bn/2CnDn-1， 且不带头则应执行下60. 设双向循环链表中节点的结构为（data,LLink,RLink）节点。若想在指针p所指节点之后插入指针s所指节点，列哪一个操作（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RL

18、ink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;61. 栈和队列都是（A）A限制存取位置的线性结构B链式存储的非线性结构C顺序存储的线性结构D限制存取位置的非线性结构62. 单循环链表表示的队列长度为n,若只设头指针，则入队的时间复杂度为(A)AO(n)BO(1)CO(n*n)DO(n*logn)63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少(C)An-kBn-k+1C|

19、logkn|+1D|logkn|其中|k|表示下取整64. 下列序列中(B)不是堆。A.12365368486075B.12485368366075C.12483660756853D.1236605348687565. 在下列内排序方法中，(C)的平均时间复杂性是O(nlogn)。A. 直接插入排序 B. 简单选择排序C. 快速排序D.希尔排序66. 设顺序栈s非空，则语句段（C）可实现栈s的出栈操作，其中为栈顶指针，为栈空间，出栈的元素存放在x中。A.:=+1;B.x:=;x:=;:=+1;C.:=;D.x:=;x：=；：=；67.已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的

20、后继结点应执行操作（A）;要在p结点后插入s结点应执行操作（D）。A.pnext:=pnextnext;B.pnextnext:=.next;C.pnext:=s;snext:=pnext;D.snext:=pnext;pnext:=s;68 .下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序(D)。A.二叉排序树B.哈夫曼树C.AVL树D.堆69 .下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.快速排序70 .若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是(C)。A.快速排

21、序B.堆排序C.归并排序D.直接插入排序二填空题1、在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null2、表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是：(请在表达式中用点(.)将数隔开)23.12.3*2-4/*7/+3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是604、深度为9的完全二叉树具有的个结点2565、已知二叉树后序为DGEBFGA中序为DBGEACF则前序一定是ABDEGCF6、先根遍历树林正好等同于按遍历对应的二叉树.先序7、构造n个结点的强连通图，至少有条

22、弧。n8、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为6,9,11,129、在单链表指针为p的结点之后插入指针为s的结点的操作是:s->next=p->next;p->next=s;10、有N个顶点的有向图，至少需要量的。N-111、在顺序表（8,11,15,19,25,26,30,33,42,48,50半）法查找关键码值12,需做的关键码比较次数为4条弧才能保证是连通）中，用二分（折13、下面是一个无向图的邻接矩阵,（顶点号由1开始）0101110100010101010110010该图的顶点数为为。试将有关数据填入本题的空白处该图的边数

23、为顶点3的度14、后根遍历树林正好等同于按(6)遍历对应的二叉树。中序15、n个结点的完全有向图含有边的数目一n*(nl)16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的。时间复杂度17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC得到输出序列“BCA的操作序列为SSXSXX®由“a*b+c/d”得到“ab*cd/+”的操作序列为oSXSSXXSSXSSXXX18、在一棵度为3的树中，度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是。219、如图所示的有向无环图可以排出种不同的拓扑序列。1220、利用筛选法将关键字序列(37，66，4

24、8，29，31，75)建成的大根堆为()。75,66,48,29,31,3721、 对长度为20的有序表进行二分查找的判定树的高度为。522、 、n个顶点的连通无向图，其边的条数至少为。n-123、 排序(sorting)有哪几种方法，。直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等24、下面程序段的时间复杂度为(用O估计)FORi:=1TOnDOFORj:=iTOnDOs=s+j;O(n*n)25、非线性结构包括r口树，图26、在线性表的存储结构上进行插入或删除操作要移动元素。顺序存储结构27、用一维数组r0.m-1表示顺序存储的循环队列，设队头和队尾指针分别是fr

25、ont和rear,且队头指针所指的单元闲置，则队满的条件是,队空的条件是OFront=rear,rear+1=front28、下面表达式树所对应的表达式的前缀表达式是后缀表达式是+*a-bc/de,abc-*de/+29、在AOE网中，设e(i)和l(i)分别表示活动ai的最早开始时间和最晚开始时间，则当且仅当时，ai为关键活动。e(i)=l(i)30.对有向图进行拓扑排序，若拓扑排序不成功，则说明该图。下面有向图的一个拓扑有序序列是存在回路，831、二叉排序树的特点是其序列是有序的中序遍历三简答题1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性;（3）散列法（hashing）;（4）

26、索引文件。2、堆与二元查找树的区别3、快速分类法的基本思想是什么4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime算法求最小生成树时，如果已确定的边为（5,4）,则，下一条边应在哪几条边中选取选取哪一条5、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确6、有一棵哈夫曼树共有5个叶子结点其权值分别为，,，试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e,分别给出五个叶子对应的哈夫曼编码。7、对于一个队列，若入队的顺序为a,b,c,则所有可能的出队序列是什么9、若一个栈的输入序列是1,2,3，n,其输出序列为p1,

27、p2,pn,若p1=n,则pi为多少10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗11、已知二叉树的中根遍历序列为abc,试画出该二叉树的所有可能的形态。12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf为什么若按广度优先遍历，能否得到序列abedfc为什么13、栈的存储方式有哪两种14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p,能否将p所指结点的数据元素与其确实存在的直接前驱交换请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中:单链表和单循环链表的结datenext点结构为

28、双向链表的结点结构为priordatenext15、假设通信电文使用的字符集为a,b,c,d,e,f,g,字符的哈夫曼编码依次为：0110,10,110,111,00,0111和010。(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；(2)若这些字符在电文中出现的频度分别为：3,35,13,15,20,5和9,求该哈夫曼树的带权路径长度。16、对于线性表的两种存储结构(顺序存储和链式存储结构)，如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构试说明理由。17、内存中一片连续空间(不妨假设地址从1到项提供给两个栈s1和s

29、2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析18、设某二叉树的前序遍历序列为：ABCDEFGHI中序遍历序列为：BCAEDGHF1(1)试画出该二叉树；(2)画出该二叉树后序线索化图。(3)试画出该二叉树对应的森林。19、一棵二叉排序树结构如下，各结点的值从小到大依次为1-9,请标出各结点的值。20、试证明：若借助栈由输入序列1,2，,n得到输出序列为R,P2,Pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k,使R<R<P。四算法阅读1、voidAE(Sta

30、ck&S)InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a5=1,5,8,12,15;for(i=0;i<5;i+)Push(S,2*ai);while(!StackEmpty(S)print(Pop(S);该算法被调用后得到的输出结果为：2、voidABC(BTNode*BT,int&c1,int&c2)if(BT!=NULL)ABC(BT->left,c1,c2);c1+;if(BT->left=NULL&&BT->right=NULL

31、)c2+;ABC(BT->right,c1,c2);写出下述算法A的功能：其中BiTree定义如下:TypedefstructBiTNodeTElemTypedata;structBiTNode*LChild,*RChild;BiTNode,*BiTree;StatusA(BiTreeT)QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)DeQueue(Q,e);If(e=NULL)break;ElsePrint;ENQueue(Q,;ENQueue6. 阅读下列函数algo,并回答问题：(1) 假设队列q中的元素为(2,4,5

32、,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；(2) 简述算法algo的功能。voidalgo(Queue*Q)StackS;InitStack(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(Q);while(!StackEmpty(&S)EnQueue(Q,Pop(&S);五算法填空1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。typedefstructnodeintdata;

33、structnode*next;lklist;voiddel(Iklistrear,int&x);Iklistp,q;q=rear->next;if()printf("itisempty!n");elsep=q->next;x=p->data;if()rear=q;2、堆分配存储方式下，串连接函数。typedefstructchar*ch;intlen;HString;HString*s,t;StatusStrCat(s,t)/*将串t连接在串s的后面*/inti;char*temp;if(temp=NULL)return(0);for(i=0;i

34、+)tempi=s->chi;for(;i<s->len+;i+)tempi=i-s->len;s->len+=;frs->ch=temp;return(1);3、向单链表的末尾添加一个元素的算法。LNode是一个包含(data,Next)的结构体VoidInsertRear(LNode*&HL,constElemType&item)LNode*newptr;newptr=newLNode;If()cerr<<"Memoryallocationfailare!"<<endl;exit(1);=ite

35、m;newptr->next=NULL;if(HL=NULL)HL=;elseLNode*P=HL;While(P->next!=NULL);p->next=newptr;4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。LinkListf30(LinkListL,intc)LinkListLc,p,pre;pre=L;P=(1)；Lc=(LinkList)malloc(sizeof(ListNode);Lc-&

36、gt;next=Lc;while(p!=L)if(p->data>c)pre->next=p->next;(2) 一Lc->next=p;p=pre->next;elsepre=p;(3) 一returnLc;5、已知图的邻接链表的顶点表结点结vertexfirstedge构为边表结点EdgeNodeW结构为adjvexnext下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。intFindDegree(ALGraph*G,inti)firstedge;while(2)if(3)_Jdegree+;break;p=p-&

37、gt;next;returndegree;六简单应用题1、已知一个非空二元树，其按中根和后根遍历的结果分别为：中根：CGBAHEDJFI后根：GBCHEJIFDA试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程3、画出由下面的二叉树转换成的森林4、用Floyed（弗洛伊德）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：AAAAA123123123123123PATHPATHPATHPATHPATH1231231231231235、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图,当构造完成后，请填写最后状态表，如右下图。htntldldhtntldld150001229000237000348000451400056