若一个栈的输入序列为1.ppt

《若一个栈的输入序列为1.ppt》由会员分享，可在线阅读，更多相关《若一个栈的输入序列为1.ppt（10页珍藏版）》请在知学网上搜索。

1、复习复习3.若一个栈的输入序列为若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是输出序列的第一个元素是i，则第则第j个输出元素是（个输出元素是（）。）。A.i-j-1B.i-jC.j-i+1D.不确定的不确定的【武汉大学武汉大学2000二、二、3】1、下列程序段的时间复杂、下列程序段的时间复杂度为：度为：i=1;k=0;n=100;dok=k+10*i;i=i+;while(i!=n);2.一个栈的输入序列为一个栈的输入序列为123n，若输出序列的第一个元素若输出序列的第一个元素是是n，输出第输出第i（1=inext=p;p-next=s;B.s-next=p-next;p-next

2、=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;6、从一个栈顶指针为、从一个栈顶指针为HS的链栈中删除一个结点时，用的链栈中删除一个结点时，用x保存被保存被删结点的值，则执行：删结点的值，则执行：A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;D.32154B.s-next=p-next;p-next=s;D.x=HS-data;HS=HS-next;9 9若一棵二叉树具有若一棵二叉树具有1010个度为个度为2 2的结点，的结点，5 5个度为个度为1 1

3、的结点，的结点，则度为则度为0 0的结点个数是（的结点个数是（）A A9 B9 B11 C11 C15 D15 D不确定不确定 【北北京工商大学京工商大学20012001一一.7(3.7(3分分)】7 7已知一算术表达式的中缀形式为已知一算术表达式的中缀形式为 A+B*C-D/EA+B*C-D/E，后缀形式后缀形式为为ABC*+DE/-ABC*+DE/-，其前缀形式为其前缀形式为()()A A-A+B*C/DE B.-A+B*CD/E C-A+B*C/DE B.-A+B*CD/E C-+*ABC/DE -+*ABC/DE D.-+A*BC/DED.-+A*BC/DE【北京航空航天大学北京航空航

4、天大学 1999 1999 一、一、3 3（2 2分分)】8 8、设树、设树T T的度为的度为4 4，其中度为，其中度为1 1，2 2，3 3和和4 4的结点个数分别为的结点个数分别为4 4，2 2，1 1，1 1 则则T T中的叶子数为（中的叶子数为（）A A5 B5 B6 C6 C7 D7 D8 8【南京理工大学南京理工大学 2000 2000 一、一、8 8（1.51.5分）】分）】D.-+A*BC/DED8B1112一个一个n个顶点的连通无向图，其边的个数至少为（个顶点的连通无向图，其边的个数至少为（）。）。【浙江大学【浙江大学1999四、四、4(4分分)】An-1BnCn+1Dnlo

5、gn；11设无向图的顶点个数为设无向图的顶点个数为n，则该图最多有（则该图最多有（）条边。）条边。An-1Bn(n-1)/2Cn(n+1)/2D0En2【清华大学清华大学1998一、一、5（2分）】【西安电子科技大分）】【西安电子科技大1998一、一、6（2分）】分）】【北京航空航天大学【北京航空航天大学1999一、一、7（2分）】分）】10.Givenatreewithn1nodesofdegree1,n2nodesofdegree2,nmnodesofdegreem.Howmanyleafnodesdoesthistreehave?Bn(n-1)/2An-11616、判定一个有向图是否存在

6、回路除了可以利用拓扑排序方、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用：法外，还可以利用：A.A.求关键路径的方法求关键路径的方法 B.B.求最短路径的求最短路径的DijkstraDijkstra方法方法C.C.宽度优先遍历算法宽度优先遍历算法 D.D.深度优先遍历算法深度优先遍历算法13、设高度为、设高度为h的二叉树上只有度为的二叉树上只有度为0和度为和度为2的结点，的结点，则此类二叉树中所包含的结点数至少为：则此类二叉树中所包含的结点数至少为：A.2hB.2h-1C.2h+1D.h+11515、具有、具有6 6个顶点的无向图至少应有多少条边才能确保是个顶点的无向图至少

7、应有多少条边才能确保是一个连通图？一个连通图？A.5 A.5 B.6 B.6 C.7 D.8 C.7 D.8C.2h+1C.2A.5D.深度优先遍历算法深度优先遍历算法14、在一个图中，所有顶点的度数之和等于所有边数的多少倍、在一个图中，所有顶点的度数之和等于所有边数的多少倍?A.1/2B.1C.2D.419、某线性表中最常用的操作是在最后一个元素之后插入一、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（个元素和删除第一个元素，则采用（）存储方式最节省运存储方式最节省运算时间。算时间。【南开大学南开大学2000一、一、3】A单链表单链表B仅有头指针的单循环链表

8、仅有头指针的单循环链表C双链表双链表D仅有尾指针的单循环链表仅有尾指针的单循环链表17.链表不具有的特点是（链表不具有的特点是（）【福州大学福州大学1998一、一、8(2分分)】A插入、删除不需要移动元素插入、删除不需要移动元素B可随机访问任一元素可随机访问任一元素C不必事先估计存储空间不必事先估计存储空间D所需空间与线性长度成正比所需空间与线性长度成正比18、设哈希表长、设哈希表长m14，哈希函数哈希函数H（key）key11。表中表中已有已有4个结点：个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空其余地址为空如果用二次探测再散列处理冲突

9、，关键字为如果用二次探测再散列处理冲突，关键字为49的结点的地址是：的结点的地址是：A.8B.3C.5D.9B可随机访问任一元素可随机访问任一元素D.9D仅有尾指针的单循环链表仅有尾指针的单循环链表 20.Amongthegiventrees,()hasthesameinorderandpreordertraversalresults,and(_)hasthesamepostorderandinordertraversalresults.Answer:d,b21.A sorting algorithm is stable if elements with equalkeysareleftint

10、hesameorderastheyoccurintheinput.Whichofthefollowingalgorithmsis/arestable?Answer:(a)insertionsort;(b)quicksort;(c)mergesort;(d)heapsort22.Findallpossiblebinarytreesofwhichthenodesaretraversedintheexactlysameorderunder(a)preorderandinordertraversals;(b)preorderandpostordertraversals;(c)inorderandpos

11、tordertraversals.(a)(c)(a)Thetreeisemptyorisskewedtotheright(b)Thetreeisemptyorhasasinglenodeonly(c)Thetreeisemptyorisskewedtotheleft 算法稳定性：算法稳定性：插入排序：稳定插入排序：稳定希尔排序：不稳定希尔排序：不稳定快速排序：不稳定快速排序：不稳定堆排序：不稳定堆排序：不稳定归并排序：稳定归并排序：稳定基数排序：稳定基数排序：稳定Answer:25Answer:25、1515、2020、4747、3535、2121、6868、8484、2727C.C.归并排序

12、归并排序B.t-ltag=124.24.如如果果待待排排序序的的序序列列中中有有两两个个元元素素具具有有相相同同的的值值，排排序序算算法法能能保保证证在在排排序序前前后后它它们们的的相相对对位位置置不不发发生生变变化化，则则称称该该排排序序算算法法是是稳稳定定的的。下下列列哪哪个个算算法法能能保保证证在在O(O(nlognnlogn)时时间间内内完完成成排排序序且且是是稳稳定的：定的：(A)A)快速排序快速排序 (B)B)堆排序堆排序 (C)C)归并排序归并排序 (D)D)插入排序插入排序23.Givenaintegersequence25、84、21、47、15、27、68、35、20,thefirstsortingresultis()usedshellsortingalgorithmbystep3.25、在线索化二叉树中，、在线索化二叉树中，t所指结点没有左子树的充要条件是：所指结点没有左子树的充要条件是：A.t-left=NULLB.t-ltag=1C.t-ltag=1且且t-left=NULLD.以上都不对以上都不对