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

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

1、一.计算（每题参考分值5分）L一个网的邻接矩阵A如下，试画出该网。001500220000ex)001100aocoCOScoCOCO282200oo000000ex)000000aoco15oococococo/ h:带头结点的单链表的头指针 q=h; p=hnext; 初值while (p! = NULL & p-datanext;/ p指向其值min的结点,q是p的前趋while (p! = NULL & p-datanext; delete u ;/删除所有的其值min并且next=p; / del.l三、单项选择（每题参考分值2.5分）11、深度为k的完全二叉树中最少有（）个结点。A

2、.2匕1一1B.2匕1答案：【B】16、假设线性表最常用的操作是存取第i个元素的值，那么采用存储方式节省时间。A. 单链表B. 双链表C. 单循环链表D. 顺序表答案：【D】17、设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n ,那么这棵 二叉中共有（）个结点。A. 2nB.n + lC.2n-lD.2n + l答案：【c】18、()二叉排序树可以得到一个从小到大的有序序列。A.先序遍历中序遍历C.后序遍历D.层次遍历答案：【B】19、下面程序的时间复杂度为()for (i=l , s=0 ; i = n ; i+ ) t=l ; for(j=l ; j2)c.O(nlog2

3、n)D.O(log2n)答案：【。24、设输入序列是1、2、3 n，经过栈的作用后输出序列的第一个元素是n ,那么输出序列中第i个输出元素是（）。A.n-iB.n-1-iC.n + 1-iD.不能确定答案：【C】25、设有一个二维数组4词川，假设40存放位置在644qo）, 422存放位置在676（io）,每个元素占一个空间，问433qo）存放在什么位置?脚注（10）表示用10进制表ZJoA.688B.678692696答案：【O26、一个队列的入队序列是1 , 2 , 3,4 ,那么队列的输出序列是1,2,3,4c.1,4,3,2D.3,2,4, 1答案：【A】27、以下四种排序中（）的空间

4、复杂度最大。A. 插入排序B. 冒泡排序C. 堆排序D.归并排序答案：【D】28、假设有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行 二分查找，那么查找A3的比拟序列的下标依次为()1,2,39,5,2,39,5,39,4,2,3答案：【D】29、对于线性表(7,34,55,25,64,46,20,10 )进行散列存储时，假设选用H(K) = K%9作为散列函数，那么散列地址为1的元素有()个。c.21+1D.2k-l答案：【B】12、设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n ,那么输出 序列中的第i个输出元素是（）on-in-l-iA.1234

5、答案：【D】30、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指 针，指针变量s指向将要入队列的结点X,那么入队列的操作序列为（）。A.front-next=s ; front=s ;B.s-next=rear; rear=s ;rear-next=s ; rear=s ;s-next=front; front=s ;答案：【c】z Nm个度31、设一棵m叉树中有Ni个度数为1的结点，叱个度数为2的结点, 数为m的结点，那么该树中共有（）个叶子结点。A.m=1m2=1C.m2M2=2D.m1 + Z（-1）M f=2答案：【D】32、一个非空广义表的表头A.

6、一定是子表B. 一定是原子C. 不能是子表D. 可以是原子，也可以是子表答案：【B】33、单链表的存储密度A. 大于1B. 等于1C. 小于1D. 不能确定答案：【C）个叶子结点。）个叶子结点。34、设某哈夫曼树中有199个结点，那么该哈夫曼树中有（ A.99B.100C.101D.102答案：【B】35、建立一个长度为n的有序单链表的时间复杂度为() A.O(n)B.0(1)C.0(M)D.O(log2n)答案：【c】36、设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有()条有向边。 A.n n-1B. mm-1答案：【。37、设一组初始记录关键字序列为（25 , 50,15

7、, 35,80,85,20,40,36,70）,其 中含有5个长度为2的有序子表，那么用归并排序的方法对该记录关键字序列进行一趟归 并后的结果为（）。A. 15 , 25 , 35 , 50,20,40,80 , 85 , 36,70B. 15 , 25 , 35 , 50,80,20 , 85,40,70 , 36C. 15 , 25 , 35 , 50,80,85 , 20 , 36,40,70D. 15,25 , 35 , 50,80,20,36,40,70,85答案：【A】38、设完全无向图中有n个顶点，那么该完全无向图中有（）条边。A.n(n-l)/2n(n-l)n(n + l)/2

8、(n-l)/2答案：【A】39、具有n个结点的完全二叉树的深度为Plog2nJ +1Iog2n + 1c.log2nD.Flog2nJ答案：【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】D.不能确定答案：【c】13、设散列表中有m个存储单元,散列函数H(key)= key % p ,那么p最好选择()。A. 小于等于m的最大奇数B. 小于等于m的最大素数C. 小于等于m的最

9、大偶数D. 小于等于m的最大合数答案：【B】42、假设有18个元素的有序表存放在一维数组A19中，第一个元素放A中，现进行 二分查找，那么查找A 3 的比拟序列的下标依次为（）A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,3答案：【D】43、循环队列SQ的存储空间是数组dm,队头、尾指针分别是front和rear,那么执行 入队后其尾指针值rear是A. rear=rear+lB.rear=(rear+l)%(m-l)C. rear=(rear+l)%mD.rear=(rear-l)%m答案：【c】44、设无向图G中有n个顶点，那么该无向图的最小生成树上有()条边。 A

10、.n n-1C.2nD.2n-l答案：【B】45、设一组初始记录关键字序列为(45,80 , 55,40,42,85),那么以第一个记录关键 字45为基准而得到一趟快速排序的结果是()。A. 40,42,45,55 , 80,83B. 42,40,45,80,85,88C. 42,40,45,55 , 80,85D. 42,40,45,85 , 55 , 80答案：【。46、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()0(1)0(n)0(log2n)0(n2)答案：【c47、设II页序线性表的长度为30 ,分成5块，每块6个元素，如果采用分块查找，那么其 平均查找长度为()。A

11、.B. 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. n , eB. e , nC. ,D.n , 2e答案：【D】50、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持 有序，那么该操作的时间复杂度为()。A. O(log2n)B. 0(1)C. O(n2)D. O(n)答案：

12、【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 struct nodeint key; struct node *lchild,*rchild;bitree;void inorder(bitree *bt)if (bt!=O) inorder(bt-lchild); if(minnum b

13、t- key)flag=0;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、在链式存储结构上建立一棵二叉排序树。正确答案：解：在链式存储结构上建立一棵二叉排序树。#define n 10typedef struct nodeint key; struct node *lchild/*rchild;bitree

14、;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); else bstinsert(bt-rchild,key);)void createbsttree(bitree *&bt)(int i;for(i = l;ilength-l;i=0;i-)if(x = L-datai)break;for(j = L-length-l;j =

15、i+l;j-)L-dataj + l = L- data Q;L-datai + l=x;L-length + +;6、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链 表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。正确答案: 解：设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链 表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;void spl

16、it(lklist *headjklist *&hajklist *&hb,lklist *&hc)(Iklist *p; ha=0zhb=0,hc=0;for(p=head;p!=0;p=head)(head = p-next; p-next=0;if (p-data = A & p-datanext=ha; ha=p;else if (p-data = 0 & p-datanext=hb; hb=p; elsep-next=hc; hc=p;)7、设计在单链表中删除值相同的多余结点的算法正确答案:解：设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typ

17、edef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&head)(Iklist *p/q/s;for(p=head;p!=0;p=p-next)(for(q = p-nextzs=q;q!=0;)if (q-data= = p-data) s-next=q-next; free(q);q=s-next; else s=qzq=q-next;)8、一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA正确答案：解：

18、9、设计计算二叉树中所有结点值之和的算法。正确答案：解：设计计算二叉树中所有结点值之和的算法。void sum(bitree *bt,int &s)(if(bt!=O) s=s+bt-data; sum(bt-lchild/s); sum(bt-rchild/s);10、设计在链式结构上实现简单项选择择排序算法。正确答案:解：设计在链式结构上实现简单项选择择排序算法。void simpleselectsorlklist(lklist *&head)(Iklist *p,*q,*s; int min,t;if(head=0 |head-next=O) return;for(q = head; q

19、!=0;q=q-next)(min=q-data; 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;)一、计算(每题参考分值5分)1、以 45,53,12,37,24,100361,90,78 )构造二叉排序树。正确答案:2、以14468,27；55,23,11,10,19,20,79,84,构造 hash 表并求平均直找长度。hash 表长度为 17, hash(key) = key % 17o用线性探测法解决冲突。正确答案:0

20、1234567 8910 11 1213 14 15 1668 119 20 552327 11 10 79 1484ASL=(l*10+3*2)/12 = 16/123、二叉树先序遍历序列是:abcdefg;中序遍历序列是:胭a曲;写出后序遍历序列。正确答案:后序遍历序列：cdbgfea4、一个网的邻接矩阵A如下，试画出该网。Q01500220O00co00110000aoCOSco00co2822COoo00QOCOco00000000ao15cococococo正确答案:5、对 49f 38, 65f 97, 76,13, 27f 49 进行直接插入排序，写出每一趟排序过程正确答案:第

21、1趟 i=2(38 49) 65 97 76 13 27 49第2趟 i=3第2趟 i=3(38 4965)9776 13 27 49第3趟 i=4(38 49 6597) 7613 27 49(38 49 65 76 97) 1327 49第5趟 i=6(13 38 4965 76 97) 27 49第6趟i=7(13 27 38 49 6576 97) 49第7趟i=8(13 27 38 49 49 65 76976、设通信用8个字符abcdefgh,各字符使用的相对频率分别为25,36,2,5,8,10,14,50,构造哈夫曼树，设计哈夫曼编码,求该树的带树路径 长度WPL。正确答案:a

22、:00b:01c:10000d:10001e:1001冒泡排序C.直接选择排序D.快速排序答案：【C】16、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()。A.0(n)B.O(nlog2n)C.0(M)g:1011h:llWPL=(25 + 36+50)*2 +(8+10+14)*4+(2 + 5)*5= 3857、对对 278,109f 63f 930, 589,184, 505, 269, 8f 83 )用基数排序方法进行排序， 写出每一趟排序过程正确答案：第一趟排序后（个位有序）：930, 063, 083, 184, 505f 278, 008f 109f 589f 26

23、9第二趟排序后（在个位有序的基础上使拾位有序）：505, 008, 109, 930, 063, 269,278f 083, 184, 589第三趟排序后（在拾位有序的基础上使百位有序）：008, 063, 083, 109, 184, 269, 278f 505, 589, 9308、用kruskal方法求以下图的最小生成树正确答案:9、设计算法求二叉树的高度正确答案：int depth(BTree T)int l,r;if (T= = NULL)return 0;else 1= depth(T-lchild);r=depth(T-rchild);return (lr)?(l + l):(r

24、+l)10、设线性表存于整型数据al.MAXSIZE的前n个分量中且递增有序，将x插 入到线性表的适当位置。正确答案：void insert() if ( n = l & xnext;elsemark=0;return mark;三.单项选择(每题参考分值2.5分)11、建立一个长度为n的有序单链表的时间复杂度为()A. 0(n)B. 0(1)C. 0(n2)D. O(log2n)答案：【c】12、设有序顺序表中有n个数据元素，那么利用二分查找法查找数据元素X的最多比拟次数不超过()OA.Iog2n + 1Iog2n-1log2nIog2（n + 1）答案：【A】13、下面关于线性表的表达错误

25、的选项是（）。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间c.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现答案：【D】14、队列是一种（）的线性表。A. 先进先出B. 先进后出C. 只能插入D.只能删除答案：【A】15、以下四种排序中（）的空间复杂度最大。A. 插入排序B. 冒泡排序C. 堆排序D. 归并排序答案：【D】16、假设线性表最常用的操作是存取第i个元素的值，那么采用存储方式节省时间。A.单链表B.双链表c.单循环链表D.顺序表答案：【D】17、下面程序的时间复杂度为()for (i=

26、l , s=0 ; i = n ; i+ ) t=l ; for(j=l ； j = i ； j + +) t=t*j ; s=s+t; A. 0(n)B. 0(n2)c.0(n3)D.0(n4)答案：【B】18、设输入序列是1、2、3 n,经过栈的作用后输出序列的第一个元素是n ,那么输出序列中第i个输出元素是()。A. n-iB. n-1-iC. n + 1-iD.O(log2n)答案：【c】17、图G的某一最小生成树的代价一定小于其他生成树的代价A.一定是B.肯定不是C.不一定是D.都不对答案：D.不能确定答案：【c】19、具有n个结点的完全二叉树的深度为A.riog2nj +1B.Io

27、g2n + 1C.log2nD.Flog2nJ答案：【D】20、二路归并排序的时间复杂度为()。A. O(n)B. O(n2)c.O(nlog2n)D.O(log2n)答案：【c】21、设有一个二维数组囱假设40存放位置在644(10)42 2存放位置在676(1。), 每个元素占一个空间，问433qo)存放在什么位置?脚注(10)表示用10进制表示。A.688B.678692696答案：【c】22、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为() A.0(1)B.0(n)C.O(log2n)D.O(n2)答案：【C】23、假设有18个元素的有序表存放在一维数组A19中，第一个元素

28、放Al中，现进行二分查找，那么查找A3的比拟序列的下标依次为()A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,3答案：【D】24、以下算法的时间复杂度是for(i=0;inext=s ; front=s ;B.s-next=rear; rear=s ;C.rear-next=s ; rear=s ;D.s-next=front; front=s ;答案：【C】33、假设有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二分查找，那么查找A3的比拟序列的下标依次为（）A.1,2,39,5,2,39,5,39,4,2, 3答案：【D】34、利用直接插入排

29、序法的思想建立一个有序线性表的时间复杂度为（）。A.0(n)B.O(nlog2n)C.0(2D.O(log2n)答案：【c】35、设一组权值集合W=Q5 , 3 , 14,2 , 6 , 9 , 16 , 17),要求根据这些权值集合构造 一棵哈夫曼树，那么这棵哈夫曼树的带权路径长度为()。A. 129B. 219c.189D.229答案：【D】36、一个队列的入队序列是1,2,3,4,那么队列的输出序列是 A.1,2,3,44,3,2, 11,4,3,2D.3,2,4,1答案：【A】37、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式 是Ill页序存储链式存储索引

30、存储散列存储答案：【D】38、设有序表中的元素为(13 , 18 , 24,35,47,50 , 62),那么在其中利用二分法查找值为24的元素需要经过()次比拟。A.1234答案：【c】39、单链表的存储密度大于1等于1c.小于1D.不能确定答案：【c】40、设一组初始记录关键字序列为(25 , 50,15 , 35,80,85,20,40,36,70),其中 含有5个长度为2的有序子表，那么用归并排序的方法对该记录关键字序列进行一趟归并后 的结果为()。A. 15 , 25 , 35 , 50,20,40,80 , 85 , 36,70B. 15 , 25 , 35 , 50 , 80,2

31、0 , 85,40,70 , 36C. 15 , 25 , 35 , 50,80,85 , 20 , 36,40,70D.15 , 25 , 35 , 50,80,20 , 36,40,70 , 85答案：【A】41、设一组初始记录关键字序列为(45,80 , 55,40,42,85),那么以第一个记录关键字45为基准而得到一趟快速排序的结果是()。A. 40,42,45,55 , 80 , 83B. 42,40,45,80,85 , 88C. 42,40,45,55 , 80 , 85D. 42,40,45,85 , 55,80答案：【C】42、设一组初始记录关键字序列为（Q ,H,C,Y，

32、P,A，M，S,R，D，F,X）,那么按字 母升序的第一趟冒泡排序结束后的结果是（）。A. 2nB. n+lC.2n-lD.2n + l答案：【D】43、设某棵三叉树中有40个结点，那么该三叉树的最小高度为（）。A.B.4C.5D.6答案：【B】）个结点。44、深度为k的完全二叉树中最少有（2匕1一12匕1C.B.两个字符串中对应位置上的字符相等A.同时具备(A)和(B)两个条件B.以上答案都不对答案：【C】20、设指针变量top指向当前链式栈的栈顶，那么删除栈顶元素的操作序列为()。A.top=top+l;B.top=top-l;C.2匕1+1D.2k-l答案：【B】45、二分查找要求结点有

33、序、顺序存储有序、链接存储无序、顺序存储无序、链接存储答案：【A】46、设散列表中有m个存储单元,散列函数H（key）=key % p ,那么p最好选择（）。A. 小于等于m的最大奇数B. 小于等于m的最大素数C. 小于等于m的最大偶数D. 小于等于m的最大合数答案：【B】47、设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B ,指针s指 向被插入的结点X ,那么在结点A和结点B插入结点X的操作序列为（）。A.s-next=p-next; p-next=-sB.q-next=s ; s-next=pp-next=s-next; s-next=pp-next=s ; s-next

34、=q答案：【B】48、设无向图G中有n个顶点,那么该无向图的最小生成树上有（）条边。A. B.n-1C.2nD.2n-l答案：【B】49、设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有（）条有向边。 A.n n-1B. mm-1答案：【。50、对于线性表(7,34,55,25,64,46,20 , 10 )进行散列存储时，假设选用H (K)= K%9作为散列函数，那么散列地址为1的元素有()个。A. 1B. 2C. 3D. 4答案：【D】top-next=top;D.top=top-next;答案：【D】21、设某无向图有n个顶点，那么该无向图的邻接表中有（）个表头结点。A. 2

35、nB. nC.n/2D.n(n-l)答案：【B】22、JII页序查找不管在顺序线性表中还是在链式线性表中的时间复杂度为( A.0(n)B.0(n2)c.0(n1/2)D.O(log2n)答案：【A】)个元素。23、设II页序线性表中有n个数据元素，那么删除表中第i个元素需要移动( A.n-i正确答案:正确答案:2、以242,68,2755,23,11,10,19,20,79,84,构造 hash 表并求平均查找长度。hash 表长度为 17, hash(key) = key % 170用线性探测法解决冲突。正确答案:B.n + l-in-l-iI答案：【A】24、算法必须具备输入、输出和计算方

36、法排序方法C.解决问题的有限运算步骤D.程序设计方法答案：【C】25、()是线性表。A. (1,2,3,.-)B. a,b,c,d,eC. (1,3,5,7)D. 答案：【。26、以下各种排序算法中平均时间复杂度为0（M）是（）。A. 快速排序B. 堆排序C. 归并排序D. 冒泡排序答案：【D】27、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。A. 0(n)B.O(log2n)C.O(nlog2n)D.0(M)答案：【B】28、设某哈夫曼树中有199个结点，那么该哈夫曼树中有()个叶子结点。A.99100C.101D.102答案：【B】29、设二叉排序树上有n个结点，那么在二叉排序树

37、上查找结点的平均时间复杂度为()o A.O(n)B.0(小)c.O(nlog2n)D.O(log2n)答案：【D】30、设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X ,那么在结点A的后面插入结点X的操作序列为（）。A. p-right=s ; s-left=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-le

38、ft=p ; s-right=p-right; p-right-left=s ; p-right=s ;答案：【A】31、设用邻接矩阵A表示有向图G的存储结构，那么有向图G中顶点i的入度为（）o A.第i行非0元素的个数之和B.第i列I非。元素的个数之和第i行。元素的个数之和第i列。元素的个数之和答案：【B】32、设输入序列为1、2、3、4、5、6 ,那么通过栈的作用后可以得到的输出序列为（）0 A.5,3,4,6, 1,2B.3,256,4,1C.3,1,254,6D.1,5,4,6,2,3答案：【B】33、设一条单链表的头指针变量为head且该链表没有头结点,那么其判空条件是（）。A. head = =OB. head-next=OC. head-next= = headD. head!=O答案：【A】34、设顺序表的长度为n ,那么JII页序查找的平均比拟次数为()。A. n n/2c.(n+1