还剩35页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
第一章
一、选择题（每题分，共分）2201数据结构是指（）o、A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义
2、数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（）o、存储结构、逻辑结构A B、链式存储结构、顺序存储结构C D
3、算法分析的目的是
（1）,算法分析的主要方法
（2）o
5、
（1）A、找出数据的合理性B研究算法中的输入和输出关系、、分析算法效率以求改进分析算法的易懂性和文档型性CA、低B、高C、相同D正确性和D简、明不性好说
（2）A、空间复杂度和时间复杂度、
6、算法的时间复杂度取决于（）数据复杂性和程序复杂性、可读性和文档性C、B、待处理数据的初始状态
4、问题的规模BA计算机内部处理的基本单元是（）A、、问数题据的规模和B待、处数理据数元据素的初始状态C、数据D项、.不D好、说数据库C数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上,链式存储比顺序存储要（）o
7、数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（）o、正确、错误A B、前半句对，后半句错、前半句错，后半句对C D
8、在数据结构中，从逻辑上可以把数据结构分成（）、动态结构和静态结构、紧凑结构和非紧凑结构A B、线性结构和非线性结构线性、内部结构和外部结构C D、9表的顺序存储结构是一种（（））的存储结构，线性表的链式存储结构是一种存储结构B顺序存取、随机存取A、散列存取、索引存取C、求下列程序段的时间复杂度D10fori=l;i=n;i++forj=l;j=n;j++x=x+l;A、0n2B、0n C、01D、00三种类型，树型结构和图
二、填空题（每题分，共分）
2201、数据逻辑结构包括________形结构合称o、给定的个元素，可以构成的逻辑结构有、、和2n四种、算法的五个重要特性是有穷性、、、输入和输出
3、一个算法的效率可分为效率和效率4后，输出序列是pop,push,push、栈是一种具有特性的线性表.5
三、判断题（每题分，共计分）
210、栈是一种后进先出的线性表（）1o、在个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反（）2n、栈是线性表的特例，是指元素先进后出（）
3、用链式存储结构保存的线性表，称为链表（.）
4、顺序表与顺序栈没有什么区别，它们都是顺序存储结构（）5
三、简答题（每题分，共计分）
721、简述栈的顺序存储结构和链式存储结构的优缺点
1、若依次读入数据元素序列进栈，进栈过程中允许出栈，试写出各种可能21,2,3的出栈元素序列、什么是栈，栈的常用操作有哪些？3
四、程序设计题（共计分）
351、写一算法，借助栈将一个带头结点的单链表倒置（15分）
2、借助栈的思想，将任给的一个十进制数转化为16进制数（20分）
五、附加思考题（10分）统计具有如下特性的电话号码个数（用顺序栈实现）电话号码为位数；8顺着读和倒着读的结果，对应的位数的数字相加等于（如个位加个位，十位加十9位…）第六章
一、选择题（每题分，共计分）
220、、A1,2,3,4B4,3,2,
1、、C1,4,3,2D3,2,4,
1、一个队列的进队序列为则出队序列为11,2,3,4,、、、、A1B2C D
3、若用单链表来表示队列，则应该选用A带尾指针的非循环队列带尾指针的循环队列B、带头指针的非循环队列、带头指针的循环队列C循环队列的条件DQ.rear==Q.front、AQ.rear=0B、（Q.rear+l）%MaxSize==Q.front队、、DQ.front=
05、C在一个链队中，假定front和rear分别为队首和队尾指针，则删除一个结、个结点进队序列为进行一次出队运算后，队头结点为241,2,3,4,点的操作为（）oA、front二front,next B、rear=rear.nextC、rear=front.next栈和队列D、front=rear.next、6的共同点是（）都是先进后、都是先进先出A出B、只允许在端点处插入和删除元素、没有共同点DC插入和删除只能在表的一端进行的线性表，称为（）、、循环队列、栈A B、队列、循环栈C D、在队列中存取数据的原则是（）
8、先进先出、后进先出A B、先进后出、不进不出C D）位置、用单链表表示的链式队列在链表的（
9、链头、链尾A B、链中、不确定C D、把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种10方法存储的线性表简称为（）、顺序表、单链表..、双链表.、循环链表
二、填A B C D空题（每空分，共计分）
三、判断题（每题分，共计分）
2101、队列的特点是先进先出（o
2、将插入和删除限定在表的同一端进行的线性表是队列（o、队列是一种对进队列、出队列操作的次序做了限制的线性表
3、栈和队列没什么区别，都是受限的线性表（
4、链栈与链队没什么区别，都是用链式存储结构保存食物线性表（5
四、简答题（每题分，共计分）
520、简述队列的顺序存储结构和链式存储结构的优缺点？
1、循环队列的优点是什么？如何判断它的空和满？
2、简述栈和队列的区别？
3、简述队列的基本操作有哪些？4
五、程序设计题（每题分，共计分）
1530、在循环队列中，若要使这个存储空间都得到利用，需另设标志来判断循1n flag环队列的空、满状态，以表示空，以表示满请写出此结构相对应的flag=0flag=l队列置空、进队和出队的算法、假设称正读和反读都相同的字符串序列为“回文”，例如是回文，利2abcba用栈和队列的思想，试写一个算法判断读入的字符串序列是否为“回文”第七章
一、单项选择题（每题分，共计分）230为1的结点数为2个，则度为0的结点数为（）个A.4B.5C.6D.7在一棵度为的树中，度为的结点数为个，度为的结点数为个，度L33221假设在一棵二叉树中，双分支结点数为单分支结点数为个，则叶子结点数
2.15,30为（）个A15B.16C.17D.
47.假定一棵三叉树的结点数为则它的最小高度为（）50,oA
3..3B.4C.5D.
64.在一棵二叉树上第4层的结点数最多为（）oA,2B.4C.6D.8用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中结点
7.o二叉树是特殊的树A.二叉树等价于度为的树
8.2完全二叉树必为满二叉树C.二叉树的左右子树有次序之分D.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序
8.oA.不发生改变B.发生改变不能确定C.
9.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（oA.1B.2C.3D.4以上都不对D.根据先序序列和中序序列确定对应的二叉树，该二叉树（
10.ABDC DBAC是完全二叉树不是完全二叉树A.B.是满二叉树不是满二叉树C.D.、对任何一棵二叉树如果其终端结点数为度为的结点数为则（）11T,n0,2n2,、、、、按A n0=n2+l Bn2=nO+1C n0=2n2+1D12n2=2nO+1照二叉树的定义，具有个结点的二叉树有（3种
13、在一颗三叉树上第4层的结点数最多为o、、、、A27B26C80D
81、、、、A3B4C5D
6、有序数据元素、无序数据元素A B、树最适合用来表示（14C、元素之间具有分支层次关系的数据D、元素之间的无联系的数据、若一棵二叉树具有个度为的结点，个度为的结点，则度为的结点15102510个数为（）.不确定A9B11C15D
二、填空题（每题分，共计分）
220、对于一个有个结点的二叉树，当它为一棵二叉树时具有最小高1n度，即为，当它为一棵单支树具有高度，即为O、具有个结点的完全二叉树，其叶结点的个数为2n o、对于一棵具有个结点的二叉树，当进行链接存储时，其二叉链表中的指3n针域的总数为个，其中个用于链接孩子结点，个空闲着、一棵深度为的满二叉树的结点总数为,一棵深度为的完全二叉5k k、在一棵二叉树中，度为的结点个数为度为的结点个数为则40no,2n,2树的结点总数的最小值为,最大值为o、由三个结点构成的二叉树，共有一种不同的形态
6、设高度为的二叉树中只有度为和度为的结点，则此类二叉树中所包7h02含的结点数至少为—o、对于一棵具有个结点的完全二叉树，若一个结点的编号为则8n ilWiWn,它的左孩子结点的编号为，右孩子结点的编号为，双亲结点的编号为o、二叉树的链式存储结构有和两种
9、三叉链表比二叉链表多一个指向的指针域10
三、判断题每题分共计分
110、1二叉树中每个结点的度不能超过所以二叉树是一种特殊的树2,二叉树的先序遍历中，任意结点均处在其子女结点之前、2由二叉树的先序遍历和后序遍历可以唯一确定一颗二叉树、
2、7的结点
2、
8、个结点的二叉树中至少有一个度为的结点9n n
22、二叉树的遍历只是为了在应用中找到一种线性次序10
四、应用题每题8分共计40分、已知一棵树边的集合为1{i,m,i,n,e,i,b,e,b,d,a,b,g,j,g,k,c,其中表示父节点为子节点为请画出这g,c,f,h,1,c,h,a,c},i,m,i m棵树，并回答下列问题哪个是根结点？1哪些是叶子结点？2哪个是结点的双亲？3g哪些是结点的祖先？4g哪些是结点的孩子？5g哪些是结点的孩子？6e（）哪些是结点的兄弟？哪些是结点的兄弟？7e f
（8）结点b和n的层次号分别是什么？
（9）树的深度是多少？（）以结点为根的子树深度是多少？10c、试分别画出具有个结点的树和二叉树的所有不同形态？
24、已知用一维数组存放的一棵完全二叉树写出该二叉树的先3ABCDEFGHIJKL,序、中序和后序遍历序列、一棵深度为的满叉树有如下性质第层上的结点都是叶子结点，其余各4H kH层上每个结点都有棵非空子树，如果按层次自上至下，从左到右顺序从开始对k1全部结点编号，回答下列问题（）各层的结点数目是多少？1
（2）编号为n的结点的父结点如果存在，编号是多少？
（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？（）编号为的结点有右兄弟的条件是什么？其右兄弟的编号是多少？4n、假设一棵二叉树的先序序列为中序序列为请写5EBADCFHGIKJ,ABCDEFGHIJK,出该二叉树的后序遍历序列
五、附加思考题（每题分，共计分）
1030、一棵具有个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完1n全二叉树进行先序遍历的算法、给定一棵用二叉链表表示的二叉树，其中的指针指向根结点，试写出从根开2t始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问、给定一棵二叉树，用二叉链表表示，其根指针为试写出求该二叉树中结点3t,n的双亲结点的算法若没有结点或者该结点没有双亲结点，分别输出相应的信息；n若结点有双亲，输出其双亲的值n第八章
一、单项选择题（每题分，共计分）
230、若查找每个元素的概率相等，则在长度为的顺序表上查找任一元素的平均查1n找长度为（）o（）（）A.n B.n+1C.n-l/2D.n+l/
2、对于长度为的顺序存储的有序表，若采用折半查找，在等概率情况下的平均29查找长度为（）的分之一9A.20B.18C.25D.
22、对于长度为的顺序存储的有序表，若采用折半查找，则查找第个元素的31815比较次数为（）oA.3B.4C.5D.
6、对于顺序存储的有序表若采用折半查找,则查找45,12,20,26,37,42,46,50,64,元素的比较次数为26oA.2B.3C.4D.
5、对具有个元素的有序表采用折半查找，则算法的时间复杂度为5noA.0n B.0n2C.01D.0log n
2、在索引查找中，若用于保存数据元素的主表的长度为它被均分为个子6n,k表，每个子表的长度均为则索引查找的平均查找长度为n/k,oA.n+k B.k+n/k C.k+n/k/2D.k+n/k/2+l、在索引查找中，若用于保存数据元素的主表的长度为它被均分为子表，7144,12A.13B.24C.12D.79每个子表的长度均为则索引查找的平均查找长度为12,o、从具有个结点的二叉排序树中查找一个元素时，在平均情况下的时间复8n杂度大致为oA.0n B.01C.0log n D.0n
22、从具有个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度9n为oA.0n B.01C.0log nD.0n
210、若根据查找表23,44,36,48,52,73,64,58建2立哈希表，采用hK=K%13计算哈希地址，则元素的哈希地址为64oA.4B.8C.12D.
13、若根据查找表建立哈希表，采用计算1123,44,36,48,52,73,64,58hK=K%7哈希地址，则哈希地址等于的元素个数3oA.1B.2C.3D.
4、若根据查找表建立长度为的哈希表，采用线性探测法处理冲突，假定对一12m个元素第一次计算的哈希地址为则下一次的哈希地址为d,oA.d B.d+1C.d+l/m D.d+l%m、对线性表进行折半查找时,要求线性表必须
13、以顺序方式存储、以链接方式存储A B、以顺序方式存储,且结点关键字有序排列C、以链接方式存储,且结点关键字有序排列D、衡量查找算法效率的主要标准是14o、元素个数、所需的存储空间、平均查找长度、算法难易程度A B C D、索引查找的条件，查找表是15o、有序、无序、块间有序块内无序、无所谓A BC D
二、填空题每题分，共计分
220、以顺序查找方法从长度为的顺序表或单链表中查找一个元素时，平均查1n找长度为,时间复杂度为o、对长度为的查找表进行查找时，假定查找第个元素的概率为,查找长2n iPi度即在查找过程中依次同有关元素比较的总次数为小，则在查找成功情况下的平均查找长度的计算公式为o、.假定一个顺序表的长度为并假定查找每个元素的概率都相同，则在340,查找成功情况下的平均查找长度，在查找不成功情况下的平均查找长度o、以折半查找方法从长度为的有序表中查找一个元素时，平均查找长4n度约等于的向上取整减时间复杂度为1,o、以折半查找方法在一个查找表上进行查找时，该查找表必须组织成5存储的表、从有序表中分别折半查找和元素时,其比612,18,30,43,56,78,82,954356较次数分别为和O、假定对长度的有序表进行折半查找，则对应的判定树高度为7n=50,最后一层的结点数为o一广震定在索引查找市，查找表长度为每个子表的长度相等，设为n,s,则进行成功查找的平均查找长度为O、在索引查找中，假定查找表即主表的长度为被等分为个子表,则进996,8行索引查找的平均查找长度为o、假定对线性表进行哈希存储，采用作为哈1038,25,74,52,48HK=K%7希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到次存储冲突、折半查找要求待查找表必须是有序的
12、索引查找要求要求查找的数据必须是顺序存储方式o
三、判断题每题分，共计分
210、顺序查找对数据的存储方式没有要求
3、顺序查找比折半查找的时间效率高
4、哈希查找要求查找表必须是顺序存储5
四、应用题每题分，共计分
1040、已知一个顺序存储的有序表为试画出对115,26,34,39,45,56,58,63,74,76,应的折半查找判定树，求出其平均查找长度、有一个项线性表，若采用等分区间顺序查找方法进行查找，问
210000、每块的理想长度为多少？
1、分成多少块较为理想？
2、平均查找长度是多少？
3、若每块长度为则平均查找长度为多少？440,、简述顺序查找法、折半查找法和分块查找法对查找表中元素的要求若查3找表中每个元素的概率相同，此时对于长度为的表，用上面的三种查找方法进行n检索时，平均查找长度是对少？、假定一个待哈希存储的线性表为4哈希地址空间为，若采用除32,75,29,63,48,94,25,36,18,70,49,80,HT
[12]留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度
五、附加思考题每题分，共计分
1030、试将折半查找的算法改写成递归调用算法来实现
1、写一个函数，利用折半查找算法在一个有序表中插入一个元素并保2x,持表的有序性、线性表中各节点查找概率不等，则可利用如下策略提高顺序查找的效率3若找到指定的结点，将该结点与前驱结点若存在的话交换，使得经常被查找的结点尽量位于表的前端试设计在线性表的顺序存储结构和链式结构上实现上述策略的顺序查找算法第九章
一、单项选择题每题分，共计分
230、若对个元素进行直接插入排序，在进行第趟排序时，假定元素的1n ir[i+l]插入位置为则需要移动元素的次数为r[j],oA.j-i B.i-j-1C.i-j D.i-j+
1、若对个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找2nA.01B.0n C.0n2D.0log n.
2、.在对3n个元素进行直接插入排序的过程中，共需要进行趟A.n B.n+
2、在对个元素进行冒泡排序的过程中，第一趟排序至多需要进行一5n对相邻元素之间的交换A.n B.n-1C.n+1D.n/
2、在对个元素进行冒泡排序的过程中，至少需要趟完成6nB.1B.n C.n-1D.n/
2、在对个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中7n元素的个数相等或只差一个，则整个排序过程得到的含两个或一个元素的区间个数大致为oC.n B.n/
2、在对个元素进行快速排序的过程中，第一次划分最多需要移动8n次元素，包括开始把支点元素移动到临时变量的一次在内A.n/
2....B.n-1C.nD.n+
1、在对个元素进行快速排序的过程中，平均情况下的时间复杂度为9n oA.01B.0log nC.0n2D.0n log n
22、对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，10A.1,3,5,7,9B.9,7,5,3,1则在该次划分过程中需要移动元素次数最多的序列为oC.5,3,1,7,9D.5,7,.9,1,
3、假定对元素序列进行快速排序，则进行第一次划分117,3,5,9,1,12,8,15后，得到的左区间中元素的个数为oA.2B.3C.4D.5在对个元素进行简单选择排序的过程中，需要进行趟选择、和n12交换A.n B.n+1C.n-1D.n/
213、若要从1000个元素中得到10个最小值元素，最好采用方法直接插入排序简单选择排序A.B.C.泡排序D.快速排序A直接插入排序B直接选择排序C快速排序
15、在平均情况下速度最快的排序方法为（）o简单选择排序直接插入排序冒泡排序A.B.C.D.、下列稳定的排序方法是（14快速排序
二、填空题（每题分，共计分）
220、每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置,此1种排序方法叫做排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序、在简单选择排序中，记录比较次数的时间复杂度为,记录移动次数的时间2复杂度为o、对个记录进行冒泡排序时，最少的比较次数为，最少的趟数为3n o、快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为4o、若对一组记录（）进行直接插入排序，当把546,79,56,38,40,80,35,50,
746、假定一组记录为46,79,56,38,40,84,在ill泡排序的过程中进行第一第个记录插入到前面已排序的有序表时，为寻找插入位置需比较次8趟排序后的结果为O行第一趟排序时，元素79将最终下沉到其后第个元素的位置、假定一组记录为（），在冒泡排序的过程中进746,79,56,64,38,40,84,
43、假定一组记录为（）对其进行快速排序的过程中，共846,79,56,38,40,80,需要趟排序、假定一组记录为（），对其进行快速排序的第946,79,56,25,76,38,40,80一次划分后，右区间内元素的个数为排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮
三、判断题（每题分，共计分）
210、快速排序并非在任何情况下都比其它排序方法速度快
2、对快速排序来说，初始序列为正序和反序都是最坏的情况
（3）、快速排序最坏的情况下的时间复杂度是（）
40、直接插入排序与折半插入排序要移动的元素次数相同
（5）
四、应用题（每题分，共计分）
1040、一个线性表中的元素有正整数和负整数试设计一算法，将正整数和负整数分1开，使线性表的前一半为负整数，后一半为正整数不要求对这些整数排序,但要求尽量减少次数、对于给定的个整数分别写出用直接21023,13,17,21,30,60,58,28,31,90,插入排序、冒泡排序和直接选择排序方法排序的各趟结果O、在冒泡排序过程中，有的关键字在某堂排序中可能朝着与最终排序相反的方3向移动，试举例说明之，快速排序过程中有没有这种现象？、试以单链表为存储结构实现简单选择排序的算法4
五、附加思考题（每题分，共计分）
1040、输入一系列正整数，以小于等于为结束标志试设计算法，将这些数10按其最末两位分类，同一类按大小排序、假设有个关键字小于的整数记录序列，设计一种排序算法,要2100010000求尽可能少的比较次数和移动次数实现排序、用插入排序方法，将一个无序的链表排列成一个按降序的有序链表
3、编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡4第十章、编程实现求今■（精确计算）、统计数字问题12+22+222+2222+…+2一本书的页码从自然数开始顺序编码直到自然数书的页码按照通常的习1n惯编排，每个页码都不含多余的前导数字例如，第页用数字表示，而不是066用或等数字计算问题要求对给定书总页码计算出书的全部页码中分别06006n,用到多少次数字0,1,2,…，9o、最多约数问题3正整数x的约数是能整除x的正整数正整数x的约数个数记为div（X）o例如都是正整数的约数，且（）设和是两个正1,2,5,1010div10=4o a b整数，找出和之间约数约数个数最多的数ab,a b、车牌问题4若车牌是由到的十个数字组成的五位数，现将车牌号每位的数字进行相加09求和，得到一个新数字，若新数字大于仍将各位数字相加求和，又得到一个新10,数字，…，如此下去，最后总能得到小于的正整数，（例如车牌为1054235,）编程实现，求取各种可能的车牌号,经过如上处5+4+2+3+4=19,1+9=10,1+0=1理，最后得到到各个数字的个数，看看有什么规律，为什么？、狼找兔子问095题一座山周围有个洞，顺时针编号为一只狼从号洞开始，顺n0,L2,•••,n-1,0时针方向计算经过个洞时，就进去找兔子例如狼经过的洞依次为m n=5,m=3,0,.输入试问兔子有没有幸免的机会？如果有该藏在哪里？、俘虏3,1,4,2,0m,n6o问题在一次战斗中，抓住了个俘虏分别关闭在个不同的牢房里，并编号号码（n n1,2,3…，n）,正好国王举行婚礼，大势释放俘虏，第一天将所有牢房中单号的俘虏进行释放，将剩下的俘虏从新排号，（不改变原来的顺序）；第二天释放剩下的编号为双号俘虏，仍重新编号（不改变顺序）；第三天又释放剩下的编号为单号的俘虏仍重新编号（不改变顺序）；依次下去，问什么最后一个被释放的俘虏开始呆在第几号牢房、线性结构中元素之间存在关系；树型结构中元素之间存在关系；图形结构5中元素之间存在关系、数据结构按逻辑结构可分为两大类，分别是和6o、数据的存储结构可用四种基本的存储方法，它们是存储方法、7存储方法、索引存储方法、散列存储方法、数据元素之间存在的相互关系为-
8、时间复杂度的衡量方法包括和9o算法的要素包括、、103o
三、判断题每空分，共分
1、一个算法可以没有输入，但不能没有输出
2、顺序存储结构通过数据元素的地址直接反应数据元素的逻辑关系
3、链式存储结构通过指针间接反映数据元素之间的逻辑关系
4、数据的存储结构通常只有顺序存储结构和链式存储结构两种
5、逻辑结构不同的数据应该采用不同的存储结构
6、算法分析的前提是算法的时空效率高
9、算法可以用任意的符号来描述10
四、简答题每题分，共分
520、数据结构中元素之间的逻辑关系可以由种基本数据关系组成，简述他们的名14称和含义、物理存储结构主要包括顺序存储结构和链式存储结构，请简述它们各自的特点
2、简述算法的特征和设计要求
3、简述时间复杂度和空间复杂度的含义4
五、分析题每题分，共分630分析下列算法的复杂度、1mainint i,n,s=0;while n0|s+=n%10;n=n/10;、2mainO{int i=ll,j,n,counter=0;、箱子问题7有想产品，每箱有件，正品每件克，其中几箱是次品，每件次品101000100比正品轻克，问能否用称只称一次，就找出哪几箱是次品
108、求水仙花数，即存在这样的三位数，ABC；满足如下表达式:=3+3+3ABC A BC请编程求所有这样的整数、打靶问题9一个射击运动员打靶，靶一共有环，连开枪打中环的可能性有多少种？
101090、八皇后问题10一个古老而著名的问题，是回溯算法的典型例题该问题是世纪著名的数学家19高斯年提出在格的国际象棋盘上摆放个皇后，使其不能互相攻击，18508X88即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法第章
11、求解的结果11+2+3+…+
1002、已知a1=1；a2=1；当n2时有an=anT+an-2,请用递归算法求解的结果a
25、猴子吃桃子问题3猴子吃桃子问题一只小猴子摘下若干个桃子，每天吃现有的一半多一个，到第天时就只有一个桃子了，求原有多少个桃子
10、编写将十进制正整数转变为进制数4n klk
10、任何一个正整数都可以用的塞次方来表示52如请用递归算法，实现任意输入一个正整数显示的嘉次表137=2-7+2-3+2-0,n,2达式结果、一个射击运动员打靶，靶一共有环，连开枪打中环的可能性有多6101090少种？.、八皇后问题是一个古老而著名的问题，是回溯算法的典型例题该问题7是世纪著名的数学家高斯年提出在格的国际象棋盘上摆放个皇1918508X88后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法、通过我们在上楼梯时，有时一步一级楼梯，也有时一步两级楼梯如果楼8梯有级，走完这级楼梯有多少种不同的方法？n n、求一个位数,该数的每一位均是之间的数,但是每位上的数字991-9各不相同.最后使得这个位数从高位开始,前一位能被整除,前两位能被整
912、求两个正整数的最小公约数10m,n除,前三位能被整除,前四位能被整除……一直到整个位数能被整除.3499第］章
2、阿米巴用简单分裂的方式繁殖，它每分裂一次要用分钟将若干个阿米巴放13在一个盛满营养参液的容器内，分钟后容器内充满了阿米巴已知容器最多可45以装阿米巴个试问，开始的时候往容器内放了多少个阿米巴220请编程序算出.、验证谷角猜想2赌徒到赌场与庄家一对一赌博，规则是这样的:美元起押，不带一元以下的辅币庄家收到赌徒的所押的赌注后，如果赌注5金额为偶数，庄家将剥夺这笔钱的一半；如果赌注金额为奇数，庄家收到赌注后必须赔付赌注的倍再加元这就完成了这场赌博的一个回合31当一个回合结束后，下一回合立即开始赌注就是上一回合赌徒得到的回报就这样一轮又一轮地玩下去，除非赌博陷入了循环，赌徒才可以且必须选一个问在元之内，那个数字,回合数最多？那些数字输得最快100对自己最有利的时机退出、购房贷款3以年期万元的房贷为例，按照现在各大银行执行的新房贷利率计算,购
20505.94%房人每月的月供为多少元计算年后，总共付了多少？
20、中国人口预测4按去年的人口数和人口增长率，计算多少年后我国人口达至亿（人口数和增16长率，学生输入）、辗转相除法（欧几里得算法）5所谓辗转相除法是指对于任何两个自然数当时，其中，是除a,b,ab a=q*b+ro qb是的最大公约数否则,的最大公约数就等于、的最大公约数，这a,b a,b b r得到的部分商，是除以后得到的余数显然，当等于时，就a ra br0b是因为与的约数也一定是与的约数而将作为新的除式中的，abbrb ar和b的］大公约数作为新的除式中的这样反复求约数，直至等于这时的就是原先的b,r0,b a、取火柴棒游戏6取火柴棒游戏可供两个以上的人来玩一开始请通过键盘输入的人数，然后计算机会随机给出火柴棒根数（）之内接着由游戏者轮流取火柴，每人最多10-40根，最少根，并且所取的火柴数不能超过剩下的火柴数，否则计算机会让你31重新取游戏者这样依次取火柴，谁最后取完火柴，谁就是胜利者、算术平方根的计算7可以使用如下方法来计算正数的平方根右,计算的方法是这样的任意选定一个a正数与，从1出发按下面公式计算E同样，从％计算乂22%、1az++一）X2，当值较大时，能得到血n2王，并逐步递推出Z的较精确的近似值乙根据上述方法设计一个计算的算法，计算正数的平方a根、分期付款8家电一件元，实行分期付款，每期付款相同，每期一个月，购买后一个月付2000款一次，共付次，即购买了一年后付清，若按月利率为（按复利计算），则1210%每期应付多少元？.、银行存款9某银行储蓄的年利率为按复利计算设计一个算法，计算元在银行
2.15%,10000储蓄年后所得的本金与利息之和（精确到两位小数）例如，用户把元存20100入该银行年，到期后可得到的本金与利息之和为（）（）3100*1+
0.0215*1+
0.0215（）约为元*1+
0.0215,
106.
59、次多项式的求解10N例如对给定的X,计算多项式Y=3X4+2X3+5X2+2X+7的值可变型为（（（）））Y=3X+2X+5X+2X+7o第章
13、棋子问题:1有一堆棋子，枚枚地数，最后余枚；枚枚地数，最后余枚；枚枚地22133255数，最后余枚；枚枚地数，最后余枚；只有枚枚地数，最后正好数完466577编程求这堆棋子最少有多少枚棋子在国际象棋棋盘上放8个皇后,际象棋棋盘共有8行8列，皇后可以吃掉与、用枚举法解皇后问题:28之同行同列以及同一对角线的其他皇后为让他们共存，请编写算法找出各种放置方法O、百马百担问题:3有匹马，驮担货，大马驮担，中马驮担两小马驮担，问大、中、小100100321马各多少？、编程实现寻找满足下列条件的位整数44）无重复数字1）千位数字非20）能整除它的各位数字和的平方
3、猴子吃桃子问题5猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了两个，第二天早上又将剩下的桃子吃掉一半，又多吃了两个，以后每天早上都吃了前一天剩下的一半零两个，到第天早上再吃时，就只剩下两个桃子了问第一天猴子摘下10多少个桃子（用蛮力法实现）、扑克问题6张扑克牌，两人轮流拿牌，每人每次最少取张，最多取张，谁拿最后一张5414谁输，编写模拟计算机先拿牌且必胜的算法
7、将1,
2.・.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例，试求出所有满足条件的三个三位数.、方程问题8有形如ax3+bx2+cx+d=0这样的一个一元三次方程给出该方程中各项的系数（均为实数），并约定该方程存在三个不同实根（根的范围在至a,b,c,d TOO100之间）,且根与根之差的绝对值＞=1要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后位
14、用分治算法求一维整数组数据的和
1、用分治法求一维整型数组的第二小数
23、应用分治算法求方程f x=x3+2*sin x-4,在［1,2］之间的近似解,精确到
0.
0001.、什么是分治法，分治法适合用于求解哪些问题，分治法设计的步骤如何？、有45块银币中有一块不合格，已知不合格的银币比正常的银币重，现用一没N有刻度的天平，请用它来找不合格的银币，并且用天平的次数最少
6、输入正整数n,计算阶乘之和n!+n-1!+...+1!o
7、设A［L,n］是一个由n个整数组成的数组,是一个整数,给出一个分治算法，要求找出在数组中的频度，即在中出现的次数你的算法的时间x Ax A复杂性是什么？如果n=2二;…如果n=
238、2rl寨有如下递归式:请用分治算法计算任意输入一个整数的结果n n
40、插入排序可以如下改写成一个递归过程为排序先递归地排序9A］然后再将［］插入到已排序的数组［］中去对于插入排序Ll..n-1,A nA L.n-1的这一递归版本，为它的运行时间写一个递归式并用分治法实现第章
15、设计一个算法，把一个真分数表示为埃及分数之和的形式所谓的埃及分数,是1指分子为的分数例如17/8=l/2+l/3+l/24o、购物单问题:2小明被评为省级三好学生，妈妈决定奖励他元小明开始做预算，但是他想N买的东西太多，肯定会超过妈妈限定的元于是他把每件物品规定了重要度，N分为等；用整数表示，第等最重要他还从因特网查到了每件物品的价51〜55格（都是整数元）他希望在不超过元（可以等于元）的前提下，使每件物N N品的价格与重要度的成绩的总和最大、背包问题3一个商人带着一个能装公斤的背包去乡下收购货物，准备将这些将这些货物m卖到城里获利现有种货源，且知第种货物有公斤，可获利元请编写n iwi pi算法帮助商人收购货物，以获得最高的利润（假设每一种货物可以分成需要的任意一小部分放入背包）、什么是贪心算法，贪心算法适合解决那些问题，贪心算法设计要点是什4么？、均分纸牌问题5有N堆纸牌，编号分别为L2,…，No每堆上有若干张，但纸牌总数必为N的倍数可以在任一堆上取若干张纸牌，然后移动移牌规则为在编号为堆上取的纸牌，1只能移到编号为的堆上；在编号为的堆上取的纸牌，只能移到编号为的2N N-1堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多例如N=4,4堆纸牌数分别为
①9
②8
③17
④6移动次可达到目的从
③取张牌放到
④（）-从
③34981310取3张牌放到
②
（9111010）-从
②取1张牌放到
①
（10101010）o
6、找零钱问题当前有面值分别为角分，角，分，分的硬币，请给出找分钱的最佳方案25151n（要求找出的硬币数目最少）、求最大数:7设有个正整数，将它们连接成一排，组成一个最大的多位整数n例如时,个整数连成的最大整数为n=3313,312,343,34331213又如:时，个整数连成的最大整数为n=447,13,4,246,
7424613、装箱问题8设有编号为、、…、的种物品，体积分别为、将这种物01n-l nv0vl•••vn-lo n品装到容量都为的若干箱子里约定这种物品的体积均不超过即对于V nV,OWiVn,有不同的装箱方案所需要的箱子数目可能不同装箱问题要求使装尽OVviWV这种物品的箱子数要少n、汽车加油问题9一辆汽车加满油后可以行驶千米旅途中有个加油站个加油站相邻的距离N kk用数组表示设计一个有效的算法，指出应在那些加油站停靠加油，使得沿途a[k]的加油次数最少要求算法执行的速度越快越好for;i=n;i+=2{forj=2;j=i-l;j++ifi%j==0break;if j=icounter++;.、3i=s=0;whilesn{i++；s+=i;、4s=0;fori=0;in;i++forj=0;jm;j++s+=a[i][j];、5int i,n;whilei=ni=i*3;答案
一、选择题每题分，共分2201A2C3CA4B5B6C7B8C9A B10A
二、填空题（每题分，共分）
220、集合、线性、非线性非线性
1、集合、线性、树、图
2、确定性、可行性
3、时间、空间
4、一对
一、一对多、多对多
5、线性结构和非线性结构
6、顺序、链式、事前分析和时候统计
79、操作、控制结构、数据结构
三、判断题（每空分，共分）10110XVXVVXXVVV
四、简答题（每题5分，共20分）略
五、分析题（每题分，共分）
630、10logion
2、0n
2、（册）3040log n3第二早
一、单项选择题（每题分，共分）220线性表是
1.o一个有限序列，可以为空一个有限序列，不可以为空A.B.一个无限序列，可以为空一个无限序列，不可以为空C.D.在一个长度为的顺序表中删除第个元素（〈=）时，需向前移动一个元
2.n i0=i n素A.n-i B.n-i+1C.n-i-1D.i以下关于线性表的说法不正确的是
3.o线性表中的数据元素可以是数字、字符、记录等不同类型A.线性表中包含的数据元素个数不是任意的B.线性表中的每个结点都有且只有一个直接前趋和直接后继C.存在这样的线性表表中各结点都没有直接前趋和直接后继D,线性表的顺序存储结构是一种的存储结构
4.随机存取链式存取索引存取哈希存取A.B.C.D.在顺序表中，只要知道，就可在相同时间内求出任一结点的存储地址
5.在等概率情况下，顺序表的插入操作要移动
6.结点基地址结点大小向量大小基地址和结点大小A.B.C.D.全部一半三分之一四分之一A.B.C.D.、线性表是具有个（7n）的有限序列、表元素、字符A B、数据元素、数据项C D
8、在顺序表中删除一个元素的时间复杂度为（Do、0n
2、、、“线性表的逻辑结A01B0lognC0n92构与存储结构总是一致的」这个结论是（）o、正确的、错误的、不一定、与具体的结构有关A BC、对于顺序表，以下说法错误的是（）
10、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址A、顺序表的所有存储结点按相应数据元素之间的逻辑关系决定的次序依次排序B、顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻C、顺序表的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中D
二、填空题（每题分，共分）220线性表是一种典型的结构
1.在一个长度为的顺序表的第个元素之前插入一个元素，需要后移一个元素
2.n i.顺序表中逻辑上相邻的元素的物理位置3要从一个顺序表长度为删除第个元素时，被删除元素之后的所有元素均
4.n i需一个位置，移动过程是从向依次移动每一个元素在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线
5.
6.顺序表中逻辑上相邻的元素，物理位置相邻，链表中逻辑上相邻的性表的链接存储中，元素之间的逻辑关系是通过决定的元素，物理位置相邻、在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点
78、在线性结构中，最后一个结点后驱结点,其余每个结点有且只有个后驱结点
9、顺序表的特点是_____________、线性表典型的基本运算包括:10等
三、判断题每题1分，共10分、线性表是由个相同类型元素组成的有限序列1n
20、用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关2系、星非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱
3、数据的逻辑结构可以看作是从具体问题抽象出来的数学模型
4、线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中
5、线性表的顺序存储结构称为顺序表
6、逻辑结构不相同的数据，必须采用不同的存储方法来存储
7、线性表的链式存储结构优于顺序存储结构
8、线性表就是顺序表....
9、线性表的特征之一是能够随机存取10
三、简答题每题分，共分
510.什么是线性表，线性表有哪些特性？.
1.什么是顺序表，顺序表有哪些缺点和优点？
四、算法设计题共分
240、在顺序表有多个元素并且任何元素不为拆分成两个顺序表，使中大于1A0A的元素存放在中，小于的元素存放在中分0B0C
15、设顺序表中的元素递增有序试写一算法，将插入到顺序表的适当位置2L e插入后保持该表的有序性分
15、试设计一个算法，实现顺序表…，的就地逆置，用最少的辅3al,a2,an助存储空间来实现分10
五、附加思考题每题分
10、设计一个算法，删除顺序表中相同值的结点元素
1、设计算法，将两个有序的顺序表合并成一个有序顺序表2A,BC答案
一、选择题（每题分，共分）2201A2A3C4A5D6B7C8C9C10B
二、填空题（每题分，共分）
220、一对一的逻辑
1、2n-i+
1、也相邻
3、前移动，4i,n、物理位置或数组下标，指针
5、也，不一定
6、无，一
7、无,一
8、逻辑相邻物理相邻，存储密度大，随机存取，一片连续空间
9、增加、删除、查找、修改10
三、判断题（每空分，共分）110V V X V VV X XXX、简答题（每题分，共分）510三略
四、算法设计题（共分）40略
五、附加思考题（每题分）略10第四章
一、单项选择题（每题分，共分）
220、线性表采用链式存储时，其地址1o必须是连续的一定是不连续的A.B.部分地址必须是连续的连续与否均可以C.D.、在双向循环链表中，在所指的结点之后插入指针所指的结点，其操作2p s是—oA.p.next=s;s.prior=p;p.next.prior=s;s.next=p.next;B.s.prior=p;s.next=p.next;p.next=s;p.next.prior=s;s.prior=p;s.next=p.next;D.s.prior=p;s.next=p.next;p.next.prior=s;p.next=s;、.设单链表中指针指向结点若要删除之后的结点（若存在），则需3p m,m修改指针的操作为oA.p.next=p.next,next;B.p=p.next;C.p=p.next,next;D.p.next=p;、在一个单链表中，已知结点是结点的前驱结点，若在和之间插入结点，4q pq ps则须执行A.s.next=p.next;p.next=sB.q.next=s;s.next=pC.p.next=s.next;s.next=pD.p.next=s;.s,next=q、在一个具有个结点的有序单链表中插入一个新结点并保持该表有序的时间复5n杂度是o（）（）A.01B.0n（）（）C.0n2D.0log2n、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个6是（）、当前结点所在地址域、指针域.、空域、空闲域、在以单链表为存A BC D7储结构的线性表中，数据元素之间的逻辑关系用（）、数据元素的相邻地址表示、数据元素在表中的序号表示A B、指向后继元素的指针表示、数据元素的值表示C D、在链表的第一个结点之前附加一个结点，称为（）
8、头指针、头结点.、尾指针、尾结点ABC DA、head==NULL B、head.next=NULL、、在、C head.next=head10D head!=NULL（）运算中,使用顺序表比链表好、插入A、删除B、根据序号查找C、根据元素值查找D
9、带头结点的单链表为空的判定条件是（）o
二、填空题（每题分，共分）
220、在双向链表中，每个结点含有两个指针域，一个指向结点，另一1个指向结点、当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采2用存储结构为宜相反，当经常进行的是插入和删除操作时，则采用
三、判断题（每题分，共分）
110、从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前1驱结点（）o、单链表设置头结点的目的是为了简化运算（）2o、从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结3点（）o、单链表结点的指针域是用来存放其直接后继结点的首地址的（）4o、对数据的任何运算都不能改变数据原有的结构特性（）5o、从循环单链表的任一结点出发，可以找到表中的所有结点（）
67、链表的确定是不能随机访问（.）o、单链表设置头结点的目的是为了把空表和非空表、第一个结点处和非第一个8结点处的运算统一起来（）、双向链表结点的指针域用来存放其直接前驱后继o9结点的首地址（）o、没有前驱的结点称为终端结点（）10
四、简答题（每题4分，共20分）、描述以下三个概念的区别头指针，头结点，表头结点
1、线性表的两种存储结构各有哪些优缺点？
2、对于线性表的两种存储结构，如果有个线性表同时并存，而且在处理过程中3n各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？、对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删4除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由、在单循环链表中设置尾指针比设置头指针好吗？为什么5
五、算法设计题（每题10分，共30分）
1、设计在无头结点的单链表中删除第i个结点的算法在双向链表上实现线性表的求表长（）运算、ListLength L2设计将带头结点的单向链表逆置算法附加思考题（每题分，共分）、
10303、假设有一个带表头结点的链表，表头指针为每个结点含三个域
六、1head,data,和其中为整型数域，和均为指针域现在所有结点已经next priordata next prioro由域连接起来，试编一个算法，利用域（此域初值为）把所有结nextpriorNULL点按照其值从小到大的顺序链接起来试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构2素）的算法、单向循环链表的初始化方法实现的步骤、流程图以及代码3答案
一、选择题（每题分，共分）2201D2D3A4B5B6A7C8B9B10C
二、填空题（每题分，共分）
220、一对一的逻辑
1、2n-i+
1、也相邻
3、前移动，4i,n
5、物理位置或数组下标，指针、也，不一定
6、无,一
7、无，一
8、逻辑相邻物理相邻，存储密度大，随机存取，一片连续空间
9、增加、删除、查找、修改10
三、判断题（每空1分,V共10分XXX第五章共计分）一.选择题（每题分,243向一个栈顶指针为top的链栈中插入一个结点）、B s.next=top.next;top.next=s;、A top.next=s;D、s.next=top;top=top.next;、C s.next=top;top=s;两种存储结构为栈通常采用）顺序存储结构和链式存储结构BA、散列方式和索引方式、线性存储结构和非线性存储结、链表存储结构和数组构C D
3、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）A e,d,c,b,a BNd,e,c,b,a C、d,c,e,a,b D、a,b,c,d,e用一个顺栈一旦说明，其占空间的大小A、已固定B、可以改变C、不能固定D、动态变化（最多结为栈满的条件是VXJ VVX、、、、A top==0B top==m Ctop!=0D top!=m
6、在栈中存取数据的原则是（）A、先进先出B、后进先出C、后进后出D、随意进出
7、经过以下栈运算后，x的值是（）A、a B、b C、1D、0InitStack s;Push s,a;Push s,b;Pop s,x;GetTop s,x;、若已知一个栈的入栈序列是其输出序列为若则81,2,3,n,pl,p2,…,pn,pl=n,pi为（）、、、、不确定A n-i BI Cn-i+1D二.填空题（每题分，共计分）
210、允许在线性表的一端进行插入和删除的线性表称为1o、当栈满时再做进栈运算将产生当栈空时再做出栈运算将产2生、带有头结点的单链表为空的条件是3head o、设有一空栈,现有输入序列经过4L2,3,4,5,push,push,pop,push,。
个人认证
优秀文档
获得点赞 0
