华东理工大学数据结构(新)期末考试复习题及参考答案.pdf

《华东理工大学数据结构(新)期末考试复习题及参考答案.pdf》由会员分享，可在线阅读，更多相关《华东理工大学数据结构(新)期末考试复习题及参考答案.pdf（174页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一、计算（每题参考分值5分）1、已知一介网的邻接矩阵A 如下，试画出该网。00150022CO00000011COcoCOco3cococo28220000coQO0000000000CO0015coCOCOCOCO正确答案:2、以24,Z68,2Z55,23,11,10,19,20,79,84,构造 hash 表并求平均蛰找长度。hash 表长度为 17,hash(key)=key%17o用线性探测法解决冲突。正确答案：2 3 4 5 6 7 8 9 10 11 12 13 14 15 1668 1 19 20 55 23 27 11 10 79 14 84ASL=(1*10+3*2)/12

2、=16/123、已知二叉树先序遍历序列是:abcdefg;中序遍历序列是:但a或必写出后序遍历序列。正确答案：后序遍历序列：cdbgfea4、设通信用8 个字符abcdefgh,各字符使用的相对频率分别为 25,36,2,5,8,10,14,50,构造哈夫曼树，设计哈夫曼编码,求该树的带树路径长度WPLO正确答案：0T0T：40 0i V/oaIIOOT：3IOOOI：POOOOT：3io：qOO：e国 国g:1011h:llWPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5=3855、对 49,38,65,97,76,13,27,49)进行直接插入排序，写出每一趟排序过

3、程正确答案：第 1趟 i=2(38 49)65 97 76 13 27 49第 2 趟 i=3(38 49 65)97 76 13 27 49第 3趟 i=438 49 65 97)76 13 27 49第4 趟 i=5(38 49 6576 97)13 27 49第 5趟 i=613 38 49 65 76 97)27 49第 6趟i=7(13 27 38 49 6576 97)49第 7趟i=8(13 2738 49 4965 76976、用 kruskal方法求下图的最小生成树正确答案：0八 0 0 Q j 07、对对 278,109,63,930,589,184,505,269,8.8

4、3 用基数排序方法进行排序，写出每一趟排序过程正确答案：第一趟排序后（个位有序）：930,063,083,184,505,278,008,109,589,269第二趟排序后（在个位有序的基础上使拾位有序）：505,008,109,930,063,269,278,083,184,589第三趟排序后（在拾位有序的基础上使百位有序）：008,063,083,109,184,269,278,505,589,9308、以 45,53,12,37,24,100,3,61,90,78构造二叉排序树。正确答案:二、论述（每题参考分值5分）9、设计算法求二叉树的高度正确答案：int depth(BTree T)

5、int l,r;if(T=NULL)return 0;else 1=depth(T-lchild);r=depth(T-rchild);return(lr)?(l+l):(r+l)10、已知线性表中的元素按值递增排列,并以单链表作存储结构。写一高效算法,删除表中所有值大于min且小于max的元羲若表中存在这样的元素正确答案：void del_l(node*h,int minr int max)/h:带头结点的单链表的头指针q=h;p=h-next;初值while(p!=NULL&p-datanext;/p指向其值min的结点,q是p的前趋while(p!=NULL&p-datanext;del

6、ete u;/删除所有的其值min并且next=p;/del_l三、单选(每题参考分值2.5分)11、深度为k的完全二叉树中最少有()个结点。A.2 k L i2卜1c.2叫1D.2k 一 i答 案：【B】12、设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。A.n-iB.n-1-iC.n+l-iD.不能确定答 案：【。13、设散列表中有m 个存储单元，散列函数H(key)=key%p,则 p 最 好 选 择()。A.小于等于m 的最大奇数B.小于等于m 的最大素数C.小于等于m的最大偶数D.小于等于m 的最大合数答 案：【B】14、某二叉

7、树的后序遍历序列为DABEC、中序遍历序列为DEBAC,则前序遍历为A.ACBEDB.DECABC.DEABCD.CEDBA答 案：【D】15、下列排序算法中时间复杂度不受数据初始状态影响，恒 为0（裙）的是A.堆排序B.冒泡排序C.直接选择排序D.快速排序答 案：【。16、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为().A.0(n)B.O(nlog2n)C.0（的D.O(log2n)答 案：【。17、图 G 的某一最小生成树的代价一定小于其他生成树的代价A.一定是B.肯定不是C.不一定是D.都不对答 案：【C】18、设按照从上到下、从左到右的1 1 1页序从1开始对完全二叉树进

8、行顺序编号，则编号为i结点的左孩子结点的编号为（）。A.2i+lB.2iC.i/2D.2i-l答 案：【B】19、两个字符串相等的充要条件是（）。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备(A)和(B)两个条件D.以上答案都不对答 案：【。20、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为()。A.top=top+l；B.top=top-l;C.top-next=top;D.top=top-next;答 案：【D】21、设某无向图有n个顶点，则该无向图的邻接表中有（A.2nB.nC.n/2D.）个表头结点。n(n-l)答 案：【B】22、J I

9、I页序查找不论在J II页序线性表中还是在链式线性表中的时间复杂度为()。A.0(n)B.。(2C.0(n1/2)D.O(log2n)答 案：【A】23、设顺序线性表中有n 个数据元素，则删除表中第i 个元素需要移动()个元素。A.B.n+l-iC.n-l-iD.i答 案：【A】24、算法必须具备输入、输出和A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法答 案：【。25、()是线性表。A.(1,2,3,.)B.a,b,c,d,eC.(1,3,5,7)D.A B：C 答 案：【。26、下列各种排序算法中平均时间复杂度为0（d）是（）。A.快速排序B.堆排序C.归并排序D.冒泡

10、排序答 案：【D】27、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。A.0(n)B.O(log2n)C.O(nlog2n)D.0(的答 案：【B】28、设某哈夫曼树中有199个结点，则该哈夫曼树中有(A.99B.100)个叶子结点。C.101D.102答 案：【B】29、设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。A.O(n)B.0(2C.O(nlog2n)D.O(log2n)答 案：【D】30、设指针变量p指向双向链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为（）。A.p-right=s;s-left=p;p-rig

11、ht-left=s;s-right=p-right;B.s-left=p;s-right=p-right;p-right=s;p-right-left=s;C.p-right=s;p-right-left=s;s-left=p;s-right=p-right;D.s-left=p;s-right=p-right;p-right-left=s;p-right=s;答 案：【A】31、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和答 案：【B】32、设输入序列为1、2

12、、3、4、5、6,则通过栈的作用后可以得到的输出序列为（）。A.5,3,4,6,1,2B.3,2,5,6,4,1C.3,1,2,5,4,6D.1,5,4,6,2,3答 案：【B】33、设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）.A.head=OB.head-next=OC.head-next=headD.head!=O答 案：【A】34、设顺序表的长度为n,贝皿页序直找的平均匕匕较次数为().A.nB.n/2C.(n+l)/2D.(n-l)/2答 案：【C】35、设某强连通图中有n个顶点，则该强连通图中至少有()条边。A.n(n-l)B.n+1C.nD.n(n+l

13、)答 案：【。36、设某散列表的长度为100，散列函数H(k)=k%P，则 P通常情况下最好选择()。A.99B.97C.91D.93答 案：【B】37、若线性表最常用的操作是存取第i 个元素的值，则采用 存储方式节省时间。A.单链表B.双链表C.单循环链表D.顺序表答 案：【D】38、设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有（）个度数为0的结点。A.5B.6C.7D.8答 案：【C】39、设 有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。A.n2B.n(n+l)C.n(n+l)/2D

14、.n(n-l)/2答 案：【D】40、对n个记录的文件进行快速排序,所需要的辅助存储空间大致为()A.0(1)B.O(n)c.O(log2n)D.O(n2)答 案：【。41、设某无向图中有n个顶点e条 边，则建立该图邻接表的时间复杂度为()。A.O(n+e)B.。(2C.O(ne)D.0(n3)答 案：【A】42、设一棵m叉树中度数为0的结点数为No,度数为1的结点数为N.度数为m的结点数为Nm，则No=()。A.N1+N2+.+NmB.I+N2+2N3+3N4+(m-l)NmC.N2+2N3+3N4+.+(m-l)NmD.2N1+3N2+.+(m+l)Nm答 案：【B】43、二叉树的第k层的

15、结点数最多为()。A.2k-lB.2K+1C.2K-1D.2k-l答 案：【D】44、设指针q指向单链表中结点A，指 针p指向单链表中结点A的后继结点B,指 针s指向被插入的结点X,则在结点A和结点B插入结点X的操作序列为（）。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答 案：【B】45、设输入序列是1、2、3.n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是（）.A.n-iB.n-1-iC.n+1-iD.不能确定答 案：【。46、树最适合

16、用来表示（）.A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答 案：【C】47、设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有 序，则该操作的时间复杂度为()。A.O(log2n)B.0(1)C.0(2D.0(n)答 案：【D】48、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为().A.8B.7C.6D.5答 案：【B】49、设二叉排序树中有n 个结点，则在二叉排序树的平均查找长度为().A.0(1)B.O(log2n)C.O(nlog2n)D.。（2答 案：【B】50、设 有5000个待排序的记录关键字，如果

17、需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A.快速排序B.堆排序C.归并排序D.插入排序答 案：【B】一、简答(每题参考分值5分)L二 维数组int a1010,以行优先存储，第 1 个元素的首址是100,每个元素的长度为4,求 A45的存储首址。正确答案：A45的存储首址=100+(4*10+5)*4=100+45*2=280二、辨析(每题参考分值5分)2、阅读下列算法，并回答问题。float what(float x,int n)float y=x;while(nl)y=y*x;n=nOCl;return y;问 题：（1）该算法的功能是计算（2）该算

18、法的时间复杂度是_ _ _ _ _ _。正确答案：xn,0（n）三、计算（每题参考分值5分）3、对对 278,109,63,930,589,184,505,269,8.83 用基数排序方法进行排序，写 出 每 一 趟排序过程正确答案：第一趟排序后（个位有序）：930,063,083,184,505,278,008,109,589,269第二趟排序后（在个位有序的基础上使拾位有序）：505,008,109,930,063,269,278,083,184,589第三趟排序后（在拾位有序的基础上使百位有序）：008,063,083,109f 184,269,278,505,589,9304、对给定的

19、单链表L,下面算法完成删除L中值为x的结点的直接前驱结点。请填空。void DeleteX(LinkList L,DataType x)/*L是带头结点的单链表/ListNode*p/q;q=L;p=L-next;while(p&p-data!=x)q=p;p=_；)if(_)Error(x is the first node,it has no prior node);q-data=x;q-next=p-next;f r ee()；)正确答案：解：（l）p-next（2 分）（2）p=NULL（2 分）p（l 分）5、以 45,53,12,37,24,100,3,61,90,78）构造二叉排

20、序树。正确答案：6、设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。正确答案：解:E=(l,5),(5,2),(5,3),(3,4)/W=107、已知二叉树先序遍历序列是:abcdefg;中序遍历序 列 是:皿a包与写出后序遍历序列。正确答案：后序遍历序列：cdbgfea8、设计将所有奇数移到所有偶数之前的算法。正确答案：解：设计将所有奇数移到所有偶数之前的算法。void quickpass(int r,int s,int t)int i=s,j=t,x=rs;while(ij)(while(ij&rj%2=0)j=j-l;if(ij)ri=rj;i=

21、i+l;while(ij&ri%2=l)i=i+l;if(ileft);ABC(BT-right);coutdatakey=key;bt-lchild=bt-rchild=O;else if(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);)void createbsttree(bitree*&bt)int i;for(i=l;inext=top;D.top=top-next;答 案：【D】21、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A.2nB.nC.n/2D.n(n-l)答 案：【B】22、

22、J ll页序查找不论在J ll页序线性表中还是在链式线性表中的时间复杂度为()。A.0(n)B.0（的c.0(ni/2)D.O(log2n)答 案：【A】23、设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动()个元素。A.n-iB.n+1-iC.n-1-iD.I答 案：【A】24、算法必须具备输入、输出和A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法答 案：【C】25、()是线性表。A.(1,2,3,.)B.a,b,c,d,e)C.(1,3,5,7)D.A1/B：C 答 案：【C】26、下列各种排序算法中平均时间复杂度为0()是()。A.快速排序B.堆排序c.归

23、并排序D.冒泡排序答 案：【D】27、设二叉排序树上有n 个结点厕在二叉排序树上查找结点的平均时间复杂度为()。A.0(n)B.。(2C.O(nlog2n)D.O(log2n)答 案：【D】28、在二叉排序树中插入一个关键字值的平均时间复杂度为()。A.0(n)B.O(log2n)C.O(nlog2n)D.0(n2)答 案：【B】29、设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。A.99B.100C.101D.102答 案：【B】30、设指针变量p指向双向链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为（）。A.p-right=s;s-lef

24、t=p;p-right-left=s;s-right=p-right;B.s-left=p;s-right=p-right;p-right=s;p-right-left=s;c.p-right=s;p-right-left=s;s-left=p;s-right=p-right;D.s-left=p;s-right=p-right;p-right-left=s;p-right=s;答 案：【A】31、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A.第i行非。元素的个数之和B.第i列非0元素的个数之和C.第i行。元素的个数之和D.第i列0元素的个数之和答 案：【B】32、

25、设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为（）0A.5,3,4,6,1,2B.3,2,5,6,4,1C.3,1,2,5,4,6D.1,5,4,6,2,3答 案：【B】33、设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。A.head=OB.head-next=OC.head-next=headD.head!=O答 案：【A】34、设某强连通图中有n个顶点，则该强连通图中至少有()条边。A.n(n-l)B.n+1c.nD.n(n+l)答 案：【C】35、设II酹 表 的 长 度 为n,则J ll好查找的平均比较次数为()。A.nB.n/2C

26、.(n+l)/2D.(n-l)/2答 案：【C】36、设一棵三叉树中有2个度数为1的 结 点，2个度数为2的 结 点，2个度数为3的结点，则该三叉树中有（）个度数为0的结点。A.5B.6C.7D.8答 案：【O37、若线性表最常用的操作是存取第i个元素的值，则采用.存储方式节省时间。A.单链表B.双链表C.单循环链表D.顺序表答 案：【D】38、设某散列表的长度为100，散列函数H(k)=k%P,则 P通常情况下最好选择().A.99B.97c.91D.93答 案：【B】39、设 有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做()次线性探测。A.n2

27、B.n(n+l)C.n(n+l)/2D.n(n-l)/2答 案：【D】40、设某无向图中有n个顶点e条 边，则建立该图邻接表的时间复杂度为(),A.O(n+e)B.。肝)C.O(ne)D.0(2)答 案：【A】41、设一棵m叉树中度数为0的结点数为No,度数为1的结点数为N i,，度数为m的结点数为Nm，则No=()。A.N1+N2+.+NmB.I+N2+2N3+3N4+(m-l)NmC.N2+2N3+3N4+.+(m-l)NmD.2NI+3N2+(m+l)Nm答 案：【B】42、设指针q指向单链表中结点A,指 针p指向单链表中结点A的后继结点B,指 针s指向被插入的结点X,则在结点A和结点B

28、插入结点X的操作序列为()。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答 案：【B】43、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()A.0(1)B.0(n)C.o (lo g2n)D.O(n 2)答 案：【C】44、二叉树的第k 层的结点数最多为()。A.2k-lB.2K+1C.2K-1D.2-答 案：【D】45、设输入序列是L 2、3.n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是（）.A.n-iB.n-1-iC.n+

29、1-iD.不能确定答 案：【C】46、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。A.8B.7C.6D.5答 案：【B】47、树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答 案：【C】48、设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有 序，则该操作的时间复杂度为()。A.O(log2n)B.0(1)C.0(2D.0(n)答 案：【D】49、设 有 5000个 做 E 序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A.快速排序B

30、.堆排序C.归并排序D.插入排序答 案：【B】50、设二叉排序树中有n 个结点，则在二叉排序树的平均查找长度为（）。A.0(1)B.O（log2n）C.O（nlog2n）D.0（小）答 案：【B】一、计算（每题参考分值5 分）1、对对 278,109,63,930,589,184,505,269,8,83 用基数排序方法进行排序，写出每一趟排序过程正确答案：第一趟排序后（个位有序）：930,063,083,184,505,278,008,109,589,269第二趟排序后（在个位有序的基础上使拾位有序）：505,008,109,930,063,269,278,083,184,589第三趟排序后

31、（在拾位有序的基础上使百位有序）：008,063,083,109,184,269,278,505,589,9302、已知一个网的邻接矩阵A如下，试画出该网。00150022QO0000001100Q Ococo3cococo2822co00co00coQ000cococoQ015cococococo正确答案:3、设通信用8 个字符abcdefgh,各字符使用的相对频率分别为 25,36,2,5,8,10,14,50,构造哈夫曼树，设计哈夫曼编码,求该树的带树路径长度WPL。正确答案：0T0T：40 0i V/oaIIOOT：3IOOOI：POOOOT：3io：qOO：e国 国g:1011h:l

32、lWPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5=3854、用kruskal方法求下图的最小生成树正确答案：5、对 49,38,65,97,76,13,27,49）进行直接插入排序，写出每一趟排序过程正确答案：第 1趟第 2趟第 3趟第4 趟i=2(3849)65 9776132749i=3(384965)9776132749i=4(384965 97)76132749i=5(384965 7697)132749第 5 趟 i=6(13 38 49 65 76 97)27 49第 6 趟 i=7(13 27 38 49 65 76 97)49第 7 趟 i=8(13

33、27 38 49 49 65 76 976、以 45,53,12,37,24,100,3,61,90,78)构造二叉排序树。正确答案：7、以“Z68,2Z55,23,11,10,19,20,79,84,构造 hash 表并求平均查找长度。hash 表长度为 17,hash(key)=key%17o用线性探测法解决冲突。正确答案：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1668 1 19 20 55 23 27 11 10 79 14 84ASL=(l*10+3*2)/12=16/128、对对 278,109,63,930,589,184,505,269,8,

34、83 用基数排序方法进行排序，写出每一趟排序过程正确答案：第一趟排序后（个位有序）：930,063,083,184,505,278,008,109,589,269第二趟排序后（在个位有序的基础上使拾位有序）：505,008,109,930,063,269,278,083,184,589第三趟排序后（在拾位有序的基础上使百位有序）：008,063,083,109,184,269,278,505,589,9309、已知二叉树先序遍历序列是:abcdefg;中序遍历序 列 是:皿a曲;写 出 后 序 遍 历 序 列。正确答案：后序遍历序列：cdbgfea二、论述（每题参考分值5分）10.设线性表存于

35、整型数据aL.MAXSIZE的 前n个 分 量 中 且 递 增 有 序 将x插入到线性表的适当位置。正确答案：void insert()if(nv=MAXSIZE)当顺序表不满时 int i=n;while(i=l&x next;elsemark=O;return mark;)一、辨析(每题参考分值5分)L分析下列的算法，求 T(n).(用大0 表示)i=l；j=O;while(i+jj)j+;else i+;正确答案：T(n)=O(n)二、计算(每题参考分值5分)2、设有一组初始记录关键字为(45,80,48,41并给出构造过程。正确答案：解：，曳*3,22,7 8),要求构造一棵二叉排序树

36、r=l)if(temp=ri-l)break;elserj-l=ri-l;j=i;i=i/2;rj-l=temp;)5、已知二叉树先序遍历序列是:abcdefg;中序遍历序 列 是:皿a更由 写出后序遍历序列。正确答案：后序遍历序列：cdbgfea6、设计在链式结构上实现简单选择排序算法。正确答案：解:设计在链式结构上实现简单选择排序算法。void simpleselectsorlklist(lklist*&head)(Iklist*p,*q,*s;int min,t;if(head=0|head-next=O)return;for(q=head;q!=0;q=q-next)(min=q-da

37、ta;s=q;for(p=q-next;p!=0;p=p-next)if(minp-data)min=p-data;s=p;if(s!=q)t=s-data;s-data=q-data;q-data=t;)7、已知一个网的邻接矩阵A如下，试画出该网。15 co co co co co0015co22co0000001100coQ0CO3cococo2 82200co000000COcococococo正确答案:8、已知一个散列表如下图所示：0123456789 102457364668其散列函数为h(key)=key%ll,处理冲突的方法为二次探查法，探查序列为：hi=(h(key)+di)%

38、m di=l2,-12,22,-22,.,k2,(km/2)回答下列问题：(1)对表中关键字36,46,68和24进行查找时，所需进行的比较次数各为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少？正确答案：解：(1)查 找36,46,68和24时，所需进行的比较次数各为1,4,5和3次。(2分)(2)ASLsucc=(l+l+3+4+5)/5=14/5(3 分)9、已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKLID,画出此二叉树，并画出它的后序线索二叉树。正确答案：解：NULL11 0、设有一组初始记录关键字序列(K i,&，Kn),要求设计

39、一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于乩正确答案：解：设有一组初始记录关键字序列(K i,&，Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i,右半部分的每个关键字均大于等于心void quickpass(int r,int s,int t)int i=s,j=t,x=rs;while(ij)while(ix)j=j-l;if(ij)ri=rj;i=i+l;while(ij&rix)i=i+l;if(ij)rj=ri;j=j-l;ri=x;）三、单选

40、（每题参考分值2.5分）11、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。A.Iog2n+1B.logn-lC.log2nD.Iog2(n+1)答 案：【A】12、下面关于线性表的叙述错误的是（）。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现答案：【D】13、队列是一种（）的线性表。A.先进先出,B.先进后出C.只能插入D.只能删除答 案：【A】14、在二叉排序树中插入一个关键字值的平均时间复杂度为()。A.0

41、(n)B.O(log2n)C.O(nlog2n),D.。（2答 案：【B】15、深 度 为k的完全二叉树中最少有（A.2k l-lB.2 iC.2卜1+1D.）个结点。2k-l答 案：【B】16、若线性表最常用的操作是存取第i 个元素的值，则采用 存储方式节省时间。A.单链表B.双链表C.单循环链表D.顺序表答 案：【D】17、设某棵二叉树中只有度数为0 和度数为2 的结点且度数为0 的结点数为n,则这棵二叉中共有（）个结点。A.2n,B.n+lC.2 n-lD.2n+l答 案：【。18、()二叉排序树可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历答 案：【B

42、】19、下面程序的时间复杂度为()for(i=l,s=0;i=n;i+)t=l;fo r(j=l;j next=s;front=s;B.s-next=rear;rear=s;C.rear-next=s;rear=s;D.s-next=front;front=s;答 案：【c】31、设一棵m叉树中有N i个度数为1的结点，W个度数为2的结点.Nm个度数 为m的结点，则该树中共有（）个叶子结点。A.m2 -1阈i=iB.mEM1=1c.2地2=2D.1+Z（L 1）Wj=2答 案：【D】32、一个非空广义表的表头A.一定是子表B.一定是原子C.不能是子表可以是原子,也可以是子表答 案：【B】33、

43、单链表的存储密度A.大 于 1B.等 于 1C.小 于 1D.不能确定答 案：【。34、设某哈夫曼树中有199个结点，则该哈夫曼树中有（A.）个叶子结点。99,B.100C.101D.102答 案：【B】35、建立一个长度为n的有序单链表的时间复杂度为()A.O(n)B.0(1)C.W),D.O(log2n)答 案：【C】36、设某有向图的邻接表中有n 个表头结点和m 个表结点，则该图中有()条有向边。A.nB.n-1C.mD.m-1答 案：【。37、设一组初始记录关键字序列为（25,50,15,35,8 0,8 5,2 0,4 0,3 6,7 0）,其中含有5个长度为2的有序子表，则用归并排

44、序的方法对该记录关键字序列进行一趟归并后的结果为（）。A.15,25,35,5 0,2 0,4 0,8 0,8 5 ,36,70B.15,25,35,5 0,8 0,2 0,8 5,4 0,7 0 ,36C.15,25,35,5 0,8 0,8 5,2 0 ,3 6,4 0,7 0D.15,25,35,5 0,8 0,2 0 ,3 6,4 0,7 0 ,85答 案：【A】38、设完全无向图中有n个顶点，则该完全无向图中有（）条边。A.n(n-l)/2B.n(n-l)C.n(n+l)/2D.(n-l)/2答 案：【A】39、具 有n个结点的完全二叉树的深度为A.flog2nj+1B.Iog2n+

45、1c.log2nD.logzn答 案：【D】40、下列算法的时间复杂度是for(i=0;in;i+)ci=i;A.0(1)B.0(n)C.O(log2n)D.O(nlog2n)答 案：【B】41、设某棵三叉树中有40个结点，则该三叉树的最小高度为()。A.3B.4C.5D.6答 案：【B】42、若 有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二分查找，则查找A 3 的比较序列的下标依次为（）A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,3答 案：【D】43、循环队列SQ的存储空间是数组dm,队头、尾指针分别是front和rear,则执行入队后其尾指针值

46、rear是A.rear=rear+lB.rear=(rear+l)%(m-l)C.rear=(rear+l)%mD.rear=(rear-l)%m答 案：【c】44、设无向图G中有n个顶点，则该无向图的最小生成树上有()条边。A.nB.n-1C.2n,D.2n-l答 案：【B】45、设一组初始记录关键字序列为(45,80,5 5,4 0,4 2,8 5),则以第一个记录关键字45为基准而得到一趟快速排序的结果是()。A.40,42,45,55,80,83B.4 2,4 0,4 5,8 0,8 5,8 8C.42,40,45,55,80,85D.4 2,4 0,4 5,8 5 ,55,80答 案

47、：【c】46、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()A.0(1)B.0(n)C.0(log2n)D.0(n 2)答 案：【。47、设顺序线性表的长度为30,分 成5块，每 块6个元素，如果采用分块查找，则其平均查找长度为()。A.6B.11C.5D.6.5答 案：【D】48、设散列表中有m 个存储单元，散列函数H(key)=key%p,则 p 最好选择()。A.小于等于m 的最大奇数B.小于等于m 的最大素数c.小于等于m 的最大偶数D.小于等于m 的最大合数答 案：【B】49、设无向图G 中有n 个顶点e 条 边，则其对应的邻接表中的表头结点和表结点的个数分别为（）.A

48、.n,eB.e,nC.2n,eD.n,2e答 案：【D】50、设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有 序，则该操作的时间复杂度为()。A.O(log2n)B.0(1)C.0(2D.O(n)答 案：【D】一、辨析(每题参考分值5分)L 分析下列的算法，求 T(n).(用大0 表示)i=l；j=O;while(i+jj)j+;else i+;正确答案：T(n)=O(n)二、计算(每题参考分值5分)2、设计判断二叉树是否为二叉排序树的算法。正确答案：解：设计判断二叉树是否为二叉排序树的算法。int minnum=-32768,flag=l;typedef str

49、uct nodeint key;struct node*lchild,*rchild;bitree;void inorder(bitree*bt)if(bt!=O)inorder(bt-lchild);if(minnumbt-key)flag=O;minnum=bt-key;inorder(bt-rchild);)3、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。正确答案：解：2,ASL=91*l+2*2+3*4+4*2)=25/94、在链式存储结构上建立一棵二叉排

50、序树。正确答案：解：在链式存储结构上建立一棵二叉排序树。#define n 10typedef struct nodeint key;struct node*lchild,*rchild;bitree;void bstinsert(bitree*&bt,int key)(if(bt=O)bt=(bitree*)malloc(sizeof(bitree);bt-key=key;bt-lchild=bt-rchild=O;else if(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);void createbsttre