数据结构与算法题库下发版.doc

一、单选题知识点一：绪论1.设有如下遗产继承规则:丈夫和妻子可以互相继承遗产;子女可以继承父亲或母亲的遗产:子女间不能相互继承。则表示该遗产继承关系的最合适数据结构应该是( )。A树 B.图 C.数组 D.二叉树 2.设有一遗传关系:X是Y的父亲，X可以把它的属性遗传给Y。则表示该遗传关系最适合的数据结构为( )。A.向量 B.树 C.图 D.广义表 3.在数据结构中，从逻辑上可以把数据结构分成 ( )A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构4.数据结构在计算机内存中的表示是指 ( )A.数据的存储结构B.数据结构 C.数据的逻辑结构D.数据元素之间的关系 5. 计算机算法指( ) A.计算方法B.排序方法 C.解决问题的有限运算序列D.调度方法 6. 在以下的叙述中，正确的是 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.校的操作方式是先进先出 D.队列的操作方式是先进后出 7.在决定选取何种存储结构时，一般不考虑( ) A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用编程语言实现这种结构是否方便 8. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )A.数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 9.以下说法正确的是( ) A.数据元素是数据的最小单位 B.数据项是数据的基本单位C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 10设计一个“好”的算法应达到的目标为（ ）。A.正确性、可读性、健壮性及效率与低存储量需求 B.正确性、可读性、健壮性及有穷性C.正确性、可读性、健壮性及可行性 D.正确性、可读性、健壮性及确定性知识点二：线性表11.与线性表的链接存储相符的特性是( )。 A.插入和删除操作灵活 B.需要连续存储空间 C.便于随机访问 D.存储密度大12.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是( )。 A. p=NULL B. p-next=NULL C. p=h D. p-next=h13.与线性表的链接存储不相符的特性是( )。 A.插入和删除操作灵活 B.需要连续的存储空间C.存储空间动态分配 D.需另外开辟空间来保存元素间的关系14.以h为头指针的带头结点的单向循环链表为空的条件是( )。 A. h=NULL B. h-next=NULL C. h-next=h D. h-next-next=h 15.与线性表的链式存储不相符合的特性是( )。 A插入和删除操作灵活B.需要连续的存储空间 C.存储空间动态分配D.非紧凑结构16. 链表不具备的特点是( )A.可随机访问任一结点B.插入删除不需要移动元素 C.不必事先估计存储空间D.所需空间与其长度成正比 17. 带头结点的单链表head为空的判定条件是 ( )A. head = NULL B. head-next=NULL C. head-next = head D. head!=NULL 18.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构 A.单链表B.静态链表c.线性链表D. 顶序存储结构 19. 如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。 A.单链表B.双链表C.单循环链表D.顺序表 20. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的 时间复杂度是 A. 0(1) B. O(n) C. 0(n2) D. 0(nlog2n) 21. 与单链表相比，双链表的优点之一是 ( )A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.顺序访问相邻结点更灵活 22.一维数组和线性表的区别是 ( )A.前者长度固定，后者长度可变 B.后者长度固定，前者长度可变 C.两者长度均固定 D.两者长度均可变 知识点三：栈和队列23.若进队序列为1， 2， 3， 4，则出队序列是( )。 A. 4， 3， 2， 1 B. 1， 2， 3， 4 C. 1， 3， 2， 4 D.3， 2， 4， 124.设输入序列为1， 2， 3， 4借助一个栈不可能得到的输出序列是( )。 A.1， 2， 3， 4 B.4， 3， 2， 1 C.3， 4， 1， 2 D. 1， 3， 4， 225.若进栈序列为1，2，3,4则不可能得到的出栈序列为（ )。 A. 3， 2， 1， 4 B. 3， 2， 4， 1 C. 4， 2， 3， 1 D.2， 3， 4， 1 26.栈应用的典型事例是（ ）。A.排队 B.查找 C.归并 D.用“算符优先法”进行表达式求值27.栈和队列都是( )。 A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构28.对于顺序存储的队列，存储空间大小为n，头、尾指针分别为F和R，若将其看成一个首尾相接的圆环，则队列中元素个数为( )。 A. R-F B. n+R-F C. C(R-F+1)%n D. (n+R-F)%n29.从一个顺序队列删除元素时，首先需要 。A. 前移一位队首指针 B. 后移一位队首指针C. 取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素30. 假定一个顺序队列的队首和队尾指针分别为f 和r，则判断队空的条件为 。A. f+1=r B. r+1=f C. f=0 D. f=r31.初始为空的堆栈中依次插入元素:f 、e、d、c、b、a以后，连续进行了3次删除操作，此时的栈顶元素是（ ）。A.c B.d C.b D.e32在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。A.堆 B.队列 C.数组 D.线性表33设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（ ）。A.ABCD B.DCBA C.ACDB D.DABC34设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（ ）。A.1、2、3、4、5、6 B.2、1、3、4、5、6C.3、4、2、1、5、6 D.4、3、2、1、5、635设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（ ）。A.n-i+1 B.i C.n-i D.前面都不正确知识点四：串36串的长度是（ ）。A.串中不同字母的个数 B.串中不同字符的个数C.串中所含数字的个数 D.串中所有字符的个数37（ ）是C语言中abcd32lABCD的子串。A.abed B.32lAB C.abcABC D.21AB 38串是（ ）。A.不少于一个字符的序列 B.有限个字符的序列C.不少于一个字母的序列 D.任意个字母的序列39设有两个串p和q，求q在p中首次出现的位置的运算称做( ) A.连接 B.模式匹配 C.求子串 D.求串长 40若串s=software ，其真子串(不含自身)的个数是 A.8 B.37 C.36 D.9 41有串sl =ABCDEFG， s2=PQRST，假设函数con(x,y)返回x和y串的连接串，subs( s，i，j)返回串S的从序号i的字符开始的j个字符组成的子串， len(s)返回串S的长 度，则con( subs( s 1 ，2，len( s2) )，subs( s 1 ，len( s2 )，2)的结果串是 A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG 42串是一种特殊的线性表，其特殊性体现在 ( )A.可以顺序存储B.数据元素是一个字符 C.可以链式存储D.数据元素可以是多个字符 知识点五：数组和广义表43.己知广义表A=(a，b)(c，d)，则head(A)等于( )。 A. ( a，b ) B. ( a，b ) C. a， b D. a44. 设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_ _。A. O(m) B. O(n) C. O(n+t) D. O(n*t)45一个三对角矩阵Ann已按行压缩存储到一维数组B中，则B的长度至少为（ ）。A.3n+1 B.3n C.3n-1 D.3n-246二维数组A1020采用列序为主方式存储，每个元素占1个存储单元， 并且AOO的存储地址是200，则A612的地址是( )A. 328 B. 327 C.326 D. 32947.多维数组的数组元素之间的关系， A.是线性的B.是树形的 C.既是线性的，又是树形的D.既不是线性的，也不是树形的 知识点六：树和二叉树48.n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为 ( )。 A.n B. 2n C. n-l D. n+l 49.对于下边的二叉树，其中序序列为( )。 A. DBAFCG B. DBAFGC C. ABDCFG D. ABCDFG 50.在一棵二叉树上，第5层的结点数最多为( )。 A.8 B. 15 C. 16 D. 32 51.对于下面的二叉树，其中序序列为( )。 A. ABCDEFG B. ABDECFG C. DBEAFCG D. ADEBCFG 52n个结点的二叉树中，用二叉链表做存储，非空指针数目为( )。 A. n B. 2n C. n-1 D. n+1 53. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A. 24 B. 48 C. 72 D. 5154.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK中序遍历：HFIEJKG该二叉树根的右子树的根是（ ）。A.E B.F C.G D.H55.树结构最适合用来表示（ ）。A.元素间具有分支层次关系的数据 B.无序数据C.有序数据 D.元素间没有关联的数据56.具有127个结点的完全二叉树其深度为（ ）。A.8 B.7 C.6 D.557.哈夫曼树是（ ）。A.满二叉树 B.二叉排序树C.树的路径长度最短的二叉树 D.带权路径长度最短的二叉树58设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。A.2n+2 B.2n+1 C.2n D.2n-159设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（ ）。A.n0+n1+n2 B.n2+n1+2n0 C.2n2+n1 D.2n0+n160用权值分别为15，2，4，5的四个结点，构造出的哈夫曼树为（D）。61由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为（ ）。A.50 B.60 C.52 D.6562 A、B两个结点可以构成（ ）棵不等价的二叉树。A.2 B.3 C.4 D.563设哈夫曼树的叶结点数为n，则它的结点总数为（ ）。A.2n-1 B.2n C.2n+1 D.不确定64.深度为k的完全二叉树所含叶结点的个数最多为( )A. 2k B. 2k-1 C. k D. 2k65.在线索化二叉树中， t所指结点没有左子树的充要条件是 A. t一lchild = NULL B. t一ltag=1 C. t-ltag=l且t一lchild=NULL D. .以上都不对 66.在一非空二叉树的中序遍历序列中，根结点的右边 （）A.只有右子树上的所有结点B.只有右子树上的部分结点 C.只有左子树上的部分结点D.只有左子树上的所有结点67.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次 A不发生改变B.发生改变C.不能确定D.以上都不对68.对一个满二叉树，m个树叶， n个结点，深度为h，则 （）A. n=h+m B. h+m=2n C. m=h-l D. n=2h-l 69.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定 （）A.空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数 70.线索二叉树是一种（）结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性知识点七：图71.给定下列有向图，从顶点V1出发，其深度优先搜索序列为( )。 A. 12534 B.12435 C. 14325 D. 12345 726个顶点的连通图的深度优先生成树，其边数为( )。 A. 6 B. 5 C. 7 D. 4 73.具有8个顶点的连通图的深度优先生成树，其边数为( )。 A. 8 B. 9 C. 7 D. 674G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。A.6 B.7 C.8 D.9 75一个n个顶点的连通无向图，其边的个数至少为（ ）。A.n-1 B.n C.n+1 D.nlogn76对于有向图的邻接矩阵，该图共有（ ）条弧。A.5 B.4 C.3 D.277对于具有n个顶点的强连通图，其弧条数的最小值为（ ）。A.n+1 B.n C.n-1 D.n-278采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（ ）。A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历79.采用邻接表存储的图的广度优先遍历算法类似于二叉树的 （ ）A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历80对某个无向图的邻接矩阵来说， A.第i行上的非零元素个数和第i列的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第i行上，第i列上非零元素总数等于顶点Vi的度数D.矩阵中非全零行的行数等于图中的顶点数 81以下说法中不正确的是 A.无向图中的极大连通子图称为连通分量 B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.图的深度优先搜索中一般要采用找来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索方法 82.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）A.n B.n+l C.n-l D.n+e 83.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有邻接表中的结点总数是（）A. e/2 B. e C.2e D.n+e知识点八：查找84以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_.A.n(n+1)/2 B.n2 C.n(n-1)/2 D.log2n85. 以二分查找方法查找一个线性表时，此线性表必须是顺序存储的_A.有序表 B.无序表 C.栈 D.队列86若在线性表中采用折半查找法查找元素，该线性表应该（ ）。A.元素按值有序 B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构 D.元素按值有序，且采用链式存储结构87.衡量查找算法效率的主要标准是( )。 (A)元素个数 (B)所需的存储量 (C)平均查找长度 (D)算法难易程度 88.设哈希表长m=14,哈希函数H(key)=key%11,表中已有4个结点:Add(15)=4Add(38)=5Add(61)=6Add(84)=7其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点地址是()A.8 B.3 C.5 D.9知识点九：排序89.下列排序算法中，最坏情况下，时间复杂度为O(n2)的排序算法是( )。 A.堆排序 B.希尔排序 C.归并排序 D.快速排序90Shell排序的平均时间复杂度为( )。 A. O(n) B.O(n log 2n) C. O(n2) D. n1.3 91.下列排序中，占用的辅助空间最多的是( )。 A.快速排序 B.冒泡排序 C.直接选择排序 D.二路归并排序 92.下列排序算法中不稳定的是( )。 A.直接选择排序 B.二分插入排序 C.冒泡排序 D.归并排序93.在文件局部有序的情况下，最好的内部排序应该是( )。 A.直接插入排序 B.冒泡排序 C.直接选择排序 D.快速排序94.n个关键字的直接插入排序所需的最小移动次数是( )。 A. 2(n-1) B.0 C. (n+3)(n-2)/2 D. n2/2 95.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。A.直接插入排序 B.快速排序 C.归并排序 D.选择排序96初始文件中有两个关键字相同的记录，通过不稳定的排序方法排序后，（ ）。A.使得领先关系不发生变化 B.领先关系一定发生变化C.两个位置都不会发生变化 D.领先关系可能发生变化97每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。A.冒泡排序 B.简单选择排序C.希尔排序 D.直接插入排序知识点十：文件98.在索引顺序文件中（）A.主文件是无序的B.主文件是有序的 c.不适合随机查找D.索引是稠密索引 99.散列文件的特点是 A.记录按关键字排序B.记录可以进行顺序存取 c.存取速度快，但占用较多的存储空间D.记录不需要排序，存取效率高 100.用ISAM和VSAM组织文件属于A.顺序文件B.索引文件c.散列文件 解ISAM和VSAM都属于索引顺序文件。二、填空题绪论1在数据结构中，从逻辑上可以把数据结构分成 结构和 结构。2分析一个算法的优劣要从两个方面，即 复杂度和 复杂度。3数据的 结构是依赖于计算机存在的。4线性结构元素之间是 对 的关系；树形结构元素之间关系是 ；图形结构元素之间关系是 。线性表5单链表的结点空间包括两部分，即 域和 域。6带头结点的单链表L为空的条件是 。7单链表的 和 操作大多数情况下要优于顺序表。8在长度为n的顺序表中删除第i个元素时，假设i值合法，需向前移动 个元素。9在线性表的顺序存储中，若一个元素的下标为i, 则它的前驱元素的下标为 ，后继元素的下标为 。栈和队列10.插入限定在表的一端，而删除限定在表的另一端进行的线性表称为_ _ ,允许插入的一端称为_ _。11.顺序循环队列QM，下标从0到M-l，头尾指针分别用F和R表示，则队空条件是_。12._是限定仅在表尾进行插入或删除操作的线性表。13.插入和删除操作在 进行。串14.串s=“love”,其真子串（不含自身）的个数是 。15.设S1=“GOOD”，S2=“”，S3=“BYE!”，则S1，S2，S3连接之后的结果是 。数组和广义表16一个广义表的深度等于_ _嵌套的最大层数。17在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_ _、_ _和_ _三项。树与二叉树18二叉树的叶结点数no与二度结点数n2的关系是_ _。19具有256个结点的完全二叉树的深度为_ 。20深度为k的完全二叉树至少有_个结点，至多有_个结点。21如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_。22具有n个结点的二叉树，采用二叉链表存储，共有_个空链域。23线索二叉树的左线索指向其_，右线索指向其_。24具有50个结点的完全二叉树的高度是 。25.具有100个结点的完全二叉树有 个叶子。图26具有n个顶点的图用邻接矩阵存储，矩阵是 行 列。27一个n个顶点的连通无向图，其边的个数至少为 。28要连通具有n个顶点的有向图，至少需要 条边。29n个结点的完全有向图含有边的数目是 。30具有10个顶点的无向图，边的总数最多为 。31在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的 ；对于有向图来说等于该顶点的 。查找、排序32顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ _次；最少为 次。33以二分查找方法查找一个线性表时，此线性表必须是_ _存储的_ _表。34每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_ _排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_ 排序。35n个元素进行冒泡排序，最少的比较次数是 。三、判断题绪论1. 在数据结构中，数据的逻辑结构与所使用的计算机无关2. 数据元素是数据的最小单位。3. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态线性表4. 线性表的逻辑顺序与存储顺序总是一致的5. 在线性表的顺序存储结构中，逻辑上相邻的2个元素在物理位置上并不一定紧邻6. 顺序存储的线性表示可以按序号随机存取7. 循环链表中每一个元素都有后继8. 线性表的唯一存储形式是链表。9. 在顺序表中取出第i个元素所花费的时间与i成正比。10. 线性表的长度是线性表所占用的存储空间的大小。11. 线性表的链式存储结构优于顺序存储结构。12. 链表的每个节点中都包含一个指针域。栈和队列13. 一个栈的入栈顺序为A、B、C、D、E，则，出栈顺序ACEDB是不可能的。14. 栈和队列都是运算受限的线性表。15. 在栈为空的情况下，不能做出栈操作，否则产生下溢出。16. 在循环队列中，若尾指针Rear大于头指针Front，则其元素数为(Rear Front)。17. 一个栈的输入序列是12345，则输出序列43512是可能的。18. 循环队列队满的条件是rear+1=front。19. 循环队列是链队列。串20. 串长度是指串中不同字符的个数。21. 串是n（0）个字母的有限序列。22. 空串的长度为零。23. 子串是指串中任意个连续字符组成的子序列。24. 空串是任何串的子串。25. 空串与空白串是相同的。数组和广义表26. 广义表的长度是指广义表中的原子个数。27. 取出广义表A=(a, (b,c), d)中的运算head(tail(A)的结果不是b。28. 若广义表中的每个元素都是原子，则广义表为线性表。29. 稀疏矩阵是指大多数元素值为0，只有少数元素值不为0的矩阵。30. 矩阵的压缩存储适用于所有矩阵。31. 稀疏矩阵可以用三元组的方式存储。树和二叉树32. 完全二叉树中没有度为1的结点。33. 树是一种线性结构。34. 已知一棵树的先序序列和后序序列，一定能构造出该树。35. 二叉树只能采用二叉链表来存储。36. 若树的度为2时，该数为二叉树。37. 树最适合表示元素之间具有层次关系的数据。38. 具有三个结点的二叉树有五种。39. 深度为5的二叉树最多有3层。图40. 有向图用邻接矩阵表示后，顶点i 的入度等于邻接矩阵中第i列的元素个数。41. 对任意一个图，从它的某个结点出发进行一次DFS或BFS可访问到该图的每个结 点。42. 有向图用邻接矩阵表示后，结点i的出度等于第i行中非0且非的元素个数。 43. 图的广度优先搜索算法类似于二叉树的按层遍历操作。44. 无向图的极大连通子图称为连通分量。45. 有n个顶点的无向图最多有n(n+1)条边。查找46. 二分查找只适用于有序表。47. 二分查找对线性表的存储结构无任何要求。48. 采用顺序查找的平均查找长度为n-1/2。排序49. 只有初始数据为倒序时，冒泡排序所执行的比较次数最多。50. 选择排序的比较次数与数据初始状态无关。四、综合应用题树和二叉树1.己知二叉树的中序序列为DBHEIAFJCKG ，先序序列为ABDEHICFJGK，请画出该二叉树。2.对于给定的5个实数W=8，5，13，2，6，试构造Huffman树，并求出该树的最小带权路径长度。3.请分别写出下列二叉树的先序、中序和后序序列。图4.对下图进行如下操作: (1)写出其邻接矩阵。(2)求出从顶点V5出发的广度优先搜索遍历序列。5给定无向图如下，写出它的邻接矩阵，求出一棵最小生成树6.对下边给出的图进行如下操作: (1)写出图的邻接矩阵。 (2)画出图的邻接表。 (3)写出从顶点1出发的广度优先搜索遍历序列。 查找7.给定有序表D= 15，17，18，22，35，51，60，72，93，用折半查找法在D中查找18。现要求:试用图示法表示查找过程。排序8.假定有以下关键字序列，试给出快速排序的第一趟排序结果。 80 15 85 25 65 90 05 959.用直接选择排序的方法对下列关键字序列进行排序，请写出每一趟排序的结果。60 40 20 80 30 10 50 10.假定有以下关键字序列，试给出两两归并排序的每一趟排序结果。70 80 76 25 94 16 05 68五、程序填空题第二章以下算法是实现在顺序表的第i个位置插入元素e，请将程序补充完整1int ListInsert(SqList *&L,int i,ElemType e)int j;if (iL-length+1)return 0;i-;/将顺序表位序转化为elem下标for (j=L-length-1;ji;j-) /将datai及后面元素后移一个位置L-data =L-data ;L-data =e;L-length ; /顺序表长度增1Return 1;2以下算法是头插法建立长度为n，元素值由数组a赋值的带头结点的单链表，请将程序补充完整void CreateListF(LinkList *&L,ElemType a,int n)/头插法建立单链表LinkList *s;int i; L=(LinkList *)malloc(sizeof(LinkList); /创建头结点 L-next=NULL; for (i=0;idata=ai; ； /将*s插在原开始结点之前,头结点之后 ； 3以下代码是实现在单链表L的第i个位置插入元素e，请将程序补充完整。int ListInsert(LinkList *&L,int i,ElemType e) int j=0; LinkList *p=L,*s; while (jdata=e; ; /将*s插入到*p之后 ; return 1; 第三章：4以下代码是顺序栈的入栈算法，请将程序补充完整。int Push(SqStack *&s,ElemType e) if (s-top=MaxSize-1) /栈满的情况，即栈上溢出 return 0; s-top ; s-data =e; return 1;5以下代码是实现循环队列的入队算法，请将程序补充完整。int enQueue(SqQueue *&q,ElemType e) if ( ) /队满 return 0; q-rear= ;/入队时队尾增1 q-dataq-rear=e; return 1;第四章：6以下代码是实现两个字符串的连接，请将程序补充完整。SqString Concat(SqString s,SqString t) SqString str; int i; str.length=s.length+t.length; for (i=0;is.length;i+) /将s.data0s.datas.length-1复制到str ; for (i=0;it.length;i+) /将t.data0t.datat.length-1复制到str ; return str;7以下代码是实现删除一个字符串从i位置开始的连续j个字符，请将程序补充完整。SqString DelStr(SqString s,int i,int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) /参数不正确时返回空串 return str; for (k=0;k ;k+) /将s.data0s.datai-2复制到str str.datak=s.datak; for (k= ;ks.length;k+)/将s.datai+j-1datas.length-1复制到str str.datak-j=s.datak; str.length= ; return str;查找算法：8以下代码是实现对长度为n的顺序表R查找K的折半查找算法，请将程序补充完整。int BinSearch(SeqList R,int n,KeyType k) int low= ,high= ,mid; while (lowk) /继续在Rlow.mid-1中查找 high= ; else low= ; /继续在Rmid+1.high中查找 return -1;排序算法：9以下代码是选择排序算法，请将程序补充完整。void SelectSort(int R,int n) int i,j,k,l; int temp; for (i=0;in-1;i+) /做第i趟排序 k=i; for (j=i+1;jn;j+) /在当前无序区Ri.n-1中选key最小的Rk if (Rj.keyRk.key) ; /k记下目前找到的最小关键字所在的位置 if (k!=i) /交换Ri和Rk ; ; ; printf(i=%d: ,i); for (l=0;ln;l+) printf(%d ,Rl.key); printf(n); 10以下算法是对R进行冒泡排序，请将程序补充完整。void BubbleSort(RecType R,int n) int i,j,k; RecType tmp; for (i=0;ii;j-) /比较,找出本趟最小关键字的记录 if (Rj.keyRj-1.key) ; /Rj与Rj-1进行交换,将最小关键字记录前移 ; ; for (k=0;kdata=_; p=head-next; while (p!=NULL) &( p-data!=a) _;if (p=NULL) cout不存在结点a;else _;_;2.快速排序 void qksort (int R ， int p， int q) /按递增序对RpRq进行快速排序 int i=p， j=q; R 0 =R i ; IIRO作临时单元 while (ji )&( R j _R 0) j-; if (ji) R i =Rj; i+; while (ij )& (R i _R 0) i+; if(ip) qksort(R，p，j); if (iq) _;模拟试题二一、判断题(下列各题，你认为正确的，请在前面的括号内打.J，错误的打。每小题 1分，共10分) ( ) 1.数据的存储结构独立于计算机。（ ) 2.线性表简称为顺序表。 ( ) 3.对数据的任何运算都不能改变数据原有的结构特性。 ( ) 4.从循环单链表的任一结点出发，可以找到表中所有结点。 ) 5.校是一种先进先出的线性表。 ( ) 6.链表的主要缺点是不能随机访问。 ) 7.二叉树是树的特殊形式。 ( ) 8.图可以没有边，但不能没有顶点。 ) 9.冒泡排序算法是稳定的排序。 ( ) 10.散列法是一种对关键字进行比较的查找方法。二、填空题（每空2分，共20分）1.对数据所施加的运算可分为两类，即_型和_型。 2.将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为_,允许插入的一端称为_.3.二叉树的叶结点数no与二度结点数n2的关系是_.4.对于顺序循环队列QM，下标从0到M-l，头尾指针分别用F和R表示，则队空条件是_.5. n个顶点的无向完全图具有_边。6.拓扑排序的操作对象是_.7.快速排序的最坏情况是初始序列为正序和反序，其时间复杂度为_. 8.希尔排序是属于_排序的改进方法