数据结构与算法排列组合.doc

数据结构与算法题1、 S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，问下列哪一个序列是可能的出栈序列？ （多选）A)E、D、C、B、A、F B)B、C、E、F、A、DC)C、B、E、D、A、F D)A、D、F、E、B、C2、 顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码值12,所需的关键码比较次数为 A)2 B)3 C)4 D)53、 设有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X)，问新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列哪个排序算法一趟扫描的结果？ A)起泡排序B)初始步长为4的希尔排序C)二路归并排序D)以第一元素为分界元素的快速排序4、 结构化程序设计所规定的三种基本控制结构是 A) 输入、处理、输出 B) 树形、网形、环形C) 顺序、选择、循环 D) 主程序、子程序、函数5、一棵深度为K的完全二叉树(满二叉树)有( )个结点。A.2K-1 B.2k-1 C. 2K D.2k E.2k+16、一棵二叉树的中序遍历序列为：DGBAECHF，后序遍历序列为：GDBEHFCA，则前序遍历的序列是( )。A.ABCDFGHE B.ABCDEFGH C.ACBGDHEF D.ACEFHBGD E.ABDGCEFH7、给出一组数据：5、10、3、4、9、13、15、8、21、9、8，将它们生成一棵二叉排序树，所需的关键码的比较次数为( )。A.22 B.23 C.35 D.25 E.368、冒泡法排序的算法如下: 比较相邻的两个数据，若是逆序，交换两个数据的位置，否则比较下一对，直到将全部序列排好为止。若用冒泡法将数据5，6，2，7，8，9按从小到大进行排列,则需要进行数据比较的次数是（ ）。A.4 B.5 C.9 D.10 E.309、假设有一组数，以下列的形式存放在C数组中：1 3 4 8 52 7 6 4 93 10 8 6 76 8 7 9 3如果这一数组的最小下标为(1,1)，即第一个元素为C(1,1)，若已知：X=1,Y=2,Z=3，则C(C(Y,4)-1,C(X+Z,Y+Z)的值为（ ）。A）3 B）8 C）10 D）7 E）610、已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按列存贮分配的。试问：A（5，8）的起始地址为（）A.SA+141B. SA+117C. SA+222D. SA+22511、某数列有1024个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（BINARY-SEARCH），在最坏的情况下，需检视（）个单元。A.1024B. 10C. 11D. 51212、在有N个叶子节点的哈夫曼树中，其节点总数为（）A.不确定B. 2N-1C. 2N+1D. 2N13、小张用十六进制，八进制和十进制写了如下一个等式：6413=33式中三个数是各不相同进位制的数，试问64，13，33，分别为_。A八进制，十进制，十六进制 B十进制，十六进制，八进制C八进制，十六进制，十进制 D十进制，八进制，十六进制14、在Pascal语言中，表达式35 div 3 mod 4 的值是 _。A0B2C3D6 15、在数据结构中，树结构下层结点出现三个以上的结点，这种结构称为_。A三层树 B三叉树 C多层树 D多叉树16、设栈S的初始状态为空,现对序列1,2,3,4,5在栈S上,依次进行如下操作(从元素1开始,出栈后不再进栈):进栈,出栈,进栈,进栈,出栈,出栈。试问出栈的元素序列是( )。(A)1,2,3B) 1,3,2C) 3,2,1D) 2,3,1 (E)以上都不对17、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点(A)2h-1 (B)2h-1 (C)2h+1 (D)h+1 (E)h*h+118、无向图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,f(B)a,c,f,e,b,d(C)a,e,b,c,f,d(D)a,b,e,d,f,c 19、将三封信投到4个邮筒，最多的投法有（ ） （A） 种 （B） 种 （C） 种 （D）34种 E. 20、一棵完全二叉树的结点总数为18，其叶结点数为（ ）。A7个 B8个 C9个 D10个 E11个21、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。A堆栈 B数组 C线性表 D队列 E链表22、下面描述用多维数组表示的数据结构的语句中，正确的是（ ）。A 多维数组存放的都是同一种类型的数据B 多维数组各维的下标范围必须一样C 多维数组在内存中的地址是连续的D 多维数组中的下标不能是表达式E 多维数组是随机存取的数据结构23、下列关于数据结构的叙述中正确的是（ ）。A数据结构是带有结构的数据元素的集合B线性表的线性存储结构优于链式存储结构C队列是限定仅在一端进行插入，在另一端进行删除的线性表D二维数组是其数据元素为线性表的线性表E图是一种非线性数据结构24、二维数组AI，j的元素是2个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到5，列下标j的范围从1到4。M按行存储元素M3，2的起始地址与M按列存储时元素( )_的起始地址相同。Am0,3 Bm3,1 Cm4,1 Dm4,325用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是 。 A选择排序 B希尔排序 C归并排序 D快速排序26、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构( )A栈B树 C双向队列 D广义表 27、 由3个结点可以构造出多少种不同的二叉树( )A2B3C4D5 E.628、具有12个记录的序列，采用冒泡排序最少的比较次数是( )A1 B144 C11 D6629、二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要( )个字节( )A90 B180 C240 D54030、那天早上可真不巧，本来快迟到了，想问问时间，却碰上了一个老学究。他用手托了托那副深度近视镜，对我说：“从零点起到现在的2/5 等于从现在起到12 点的2/3。” 请问几点钟？A6点30分B7点 C7点30分 D8点E. 8点30分31、深度为5的二叉树至多有节点数为（ ）A15B31 C32 D64E. 1032、设有一10阶（10*10）对称矩阵，每个元素占1个字节，采用压缩存储方式，以行序为主序存储，A111，则A85的地址为（ ）A13B18 C33 D40E. 5033、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为( )A插入排序B归并排序C选择排序D快速排序E冒泡排序34、已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，层次序列为（ ）。A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG问题分析题1、 给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。2、哈里与吉姆是打弹子游戏的两位竞争对手。游戏开始时他们都有着同样数目的弹子。哈里在第一轮中蠃到了20粒弹子，但后来暴露出弱点，败下阵来，输掉了手中弹子的三分之二。结果使吉姆所拥有的弹子数是哈里的四倍。 试问:开始玩游戏时，每个孩子手上有多少弹子?3、只猫把只老鼠捉光，有种不同的捉法。4、光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，那么同时只参加两个小组的同学有多少人？ 5、用邻接矩阵表示下面的无向图： 6、小王、小张和小李中一位是工人，一位是教师，一位是律师。现在知道小李比律师年龄大，小王和教师不同岁，教师比小张年龄小。问： 是工人、 是教师、 是律7、编号为1到13的纸牌顺时钟排成一圈，有人从编号为1的牌从数字1开始顺时钟数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字N时，所在纸牌的编号为 。8、“鼠算遗题”。这是日本数学家吉田光在1627年提出来的。他是这样说的：“正月里，鼠父鼠母生了12只小鼠，于是大小鼠共14只。二月里，两代鼠全部配对，每对鼠又各生了12只小鼠。因此共有98只。如这样下去，每月所有的鼠全部配对，每对鼠又各生了12只小鼠。十二个月后，鼠的总数是多少呢？”假设每月都按这样的规律生，而所生的鼠又全部成活，十二个月后，鼠的总数是27682574402只。你能找出计