计算机专业数据结构综合测试2.docx
- 文档编号:17489378
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:9
- 大小:30.46KB
计算机专业数据结构综合测试2.docx
《计算机专业数据结构综合测试2.docx》由会员分享,可在线阅读,更多相关《计算机专业数据结构综合测试2.docx(9页珍藏版)》请在冰点文库上搜索。
计算机专业数据结构综合测试2
数据结构测试(长春理工大学精品课)
综合测试二
一、选择
1.链表不具有的特点是( )查看答案
A 可随机访问任一元素 B 插入删除不需要移动元素
C 不必事先估计存储空间 D 所需空间与线性表的长度成正比
正确答案为A
解释:
单链表不能随机访问某个元素,这种存储结构必须采用顺序访问的
方式,根据头指针依此才能找到后继元素的地址,以便访问。
收起
2.非空的循环单链表head的尾结点p满足( )查看答案
Ap->next==NULL Bp==NULL
Cp->next==head Dp==head
正确答案为C
解释:
循环链表的尾结点的后继应是头结点。
收起
3.对稀疏矩阵进行压缩存储是为了( )。
查看答案
A 便于进行矩阵运算 B 便于输入和输出
C 节省存储空间 D 降低运算的时间复杂度
正确答案为C
解释:
矩阵采用压缩存储,相同的元素存一次,零元素不存,主要目的是为了节约内存空间,在很多时候为了找到相应元素,需要找到元素和存储位置的对应关系,反而增大了时间复杂度。
收起
4.具有15个结点的二叉树的最小深度是( )。
查看答案
A4 B5
C3 D6
正确答案为A
解释:
n个结点的二叉树最小深度应是完全二叉树的深度logn+1,因此n=15时,最小深度是4。
收起
5.在有n个叶子结点的哈夫曼树中,其结点总数为( )查看答案
A 不确定 B2n
C2n+1 D2n-1
正确答案为D
解释:
赫夫曼树只有度为0和度为2的结点,叶子结点有n个,那么度为2的结点有n-1个,即总结点个数为2n-1个。
收起
6.不带权的无向图的邻接矩阵( )。
查看答案
A 不一定是对称矩阵 B 是对角线元素非零的对称矩阵
C 是上三角矩阵 D 是对角线元素为零的对称矩阵
正确答案为D
解释:
无向图的邻接矩阵为对称矩阵,又因图中各顶点不包含到自身的关系,因此对角线上元素为0。
收起
7.下列排序算法中,( )算法可能会出现下面情况:
初始数据有序,化费时间反而最多.
查看答案
A 堆排序 B 冒泡排序
C 快速排序 D Shell排序
正确答案为C
解释:
对于快速排序每次找到枢轴的位置基本将待排集合对分是最好的情况,如果待排集合基本有序,快速排序算法就退化了,时间复杂度可达到O(n*n)。
收起
8.对关键码集合K={53,30,37,12,45,24,96},从一棵二而叉树开始逐个插入关键码,建立二叉排序树,若希望的到的二叉排序树的高度最小,应选用下列输入序列( )。
查看答案
A45,24,53,12,37,96,30 B37,24,12,30,53,45,96
C12,24,30,37,45,53,96 D30,24,12,37,45,96,53
正确答案为B
解释:
构造的二叉排序树的形态和查找关键字的顺序有关,要想构造的二叉排序树的高度最小,应建立成和完全二叉树一样的高度,关键字是7个,因此最终建立的是一棵满二叉树,又根据排序树的特点,左子树结点比根结点小,根结点比右子树小,根结点应当是37,依此得出答案为B。
收起
9.用折半查找法查找表(a1,a2,…,a11),需要比较4次才能找到的元素是( )。
查看答案
Aa1和a8 Ba4和a7
Ca2和a8 Da4和a10
正确答案为C
解释:
根据折半查找建立折半查找判定树,查找表区间为1-11,第1层树根为a6,第二层为a3,a9,第三层为a1,a4,a7,a10,第四层为a2,a5,a8,a11。
收起
10. 对一棵m阶B-树,下列选项错误的是( )。
查看答案
A 每个结点最多有m个子女 B 除根结点和叶结点外,每个结点
至少有[m/2]个子女
C 有k个子女的结点必有k个 D 根结点至少有两个子女
关键码(k<=m)
正确答案为C
解释:
根据B-树的定义,只有C不满足定义,有k个子女的结点应有k-1个关键字。
收起
二、填空题
1.下面程序段的时间复杂度是()。
查看答案
for( i=1;i {y=y+1; for(j=1;j<(2*n);j++)x=x+1;} 正确答案为O(n*n) 解释: 外层循环循环体执行n-1次,内层循环循环体执行2n-1次,因此算法的时间复杂度为O(n*n) 。 收起 2. 用链表表示线性表,表中元素之间的逻辑关系是通过链表中结点的()来实现的。 查看答案 正确答案为指针 解释: 链式存储结构中线性表中元素的逻辑关系通过后继指针指出。 收起 3.设循环队列用数组A[m]表示,队头、队尾指针分别是front和rear,则判定队满的条件为 () 查看答案 正确答案为(rear+1)%M==front收起 4.已知完全二叉树有200个结点,则整个二叉树有 ()个度为1的结点。 查看答案 正确答案为1 解释: 假设二叉树中度为0的结点个数为n0个,二叉树中度为1的结点个数为n1个,二叉树中度为2的结点个数为n2个,根据完全二叉树的特点,完全二叉树中n1只能是0个或1个,再结合二叉树的性质n0+n1+n2=200,n2=n0-1,得2n0+n1=201,因此n1只能取1。 收起 5.在有向图的邻接矩阵表示中,第j列元素之和等于第j个顶点的 () 查看答案 正确答案为入度 解释: 有向图的邻接矩阵表示法中,第i行非0元素个数之和表示第i个 顶点的出度,第i列非0元素个数之和表示第i个顶点的入度。 收起 6.对用邻接表表示的连通图进行深度或广度优先遍历时的时间复杂度为 () 查看答案 正确答案为O(n+e 收起 7.对于关键字序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从关键字为 ()的结点开始.查看答案 正确答案为60 解释: 初始建堆应从第n/2的位置开始建堆。 收起 8.对n个元素的序列进行冒泡排序时 ()情况下比较次数最少. 查看答案 正确答案为初始有序 解释: 冒泡排序若关键字初始有序,则第一个关键字和第二个关键字比较,无交换,第二个关键字和第三个关键字比较,无交换,依此类推,第n-1个和第n个关键字比较,无交换,共比较n-1次,这种情况是关键字比较次数最少的,算法时间复杂度也降低为O(n)。 收起 9.长度为11的有序表进行折半查找时,在等查找概率情况下查找成功的平均查找长度为 () 查看答案 正确答案为3 解释: 根据折半查找算法建立折半查找判定树,查找表的长度为11,第一层有一个结点,第二层有两个结点,第三层有四个结点,第四层有四个结点,因此平均查找长度为(1+2*2+3*4+4*4)/11=3。 收起 10.哈希查找是通过 ()来确定记录的存储地址的。 查看答案 正确答案为计算哈希函数值 解释: 哈希查找就是通过哈希函数值确定记录的存储位置,建立起关键字和存储位置之间的关系。 收起 三、应用题 1.假设一棵树的先根序列为ABCEFIJHGKD,后根序列为JIKHGFEDCBA。 请画出该树。 查看答案 解: (1)因为树的先根和后根遍历序列分别与其转换后对应的二叉树的先根和中根遍历序列相同,所以可先得到的对应的二叉树如下图所示: (2)根据树与二叉树的转换规则,可得到树如下图所示: 收起 2.请用克鲁斯卡尔算法构造下图所示网络的最小生成树。 查看答案 解: 最小生成树如下图所示: 收起 3.下列是一棵五阶B-树,依次执行以下两步操作,画出每一步执行后所得到的B-树形。 (1)插入n; (2)删除e 查看答案 解: 下列是一棵五阶B-树,依次执行以下两步操作,画出每一步执行后所得到的B-树形。 (1)插入n: (2)删除e: 收起 4.给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序 (2)希尔排序(d1=4)(3)归并排序。 查看答案 解: 给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序: {11,4,13,9,7}14{21,17,28} (2)希尔排序(d1=4) : {7,21,13,4,11,28,17,9,14} (3)归并排序: [11,28][9,17][7,21][4,13][11]收起 四、算法设计题 1.编写算法,将非空单链表hb插入到单链表ha的第i(0 int algo1(LNode *ha, LNode *hb,int i){ for(p=hb;p->next;p=p->next); for(j=1,q=ha;jnext; p->next=q->next; q->next=hb->next; free(hb); } 收起 2.已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中,编写算法打印出编号为k的结点的双亲和孩子结点。 查看答案 intalgo2(char bt[],int n,int k){ if(k<1||k>n)return0; if(k==1) printf(“%cis a root\n”, bt[1]); else printf(“%c’s parent is%c\n”, bt[k], bt[k/2]); if(2*k<=n) printf(“%c’s lchild is%c\n”, bt[k],bt[2*k]); else printf(“%cis not lchild\n”, bt[k])); if(2*k+1<=n) printf(“%c’s rchild is%c\n”, bt[k],bt[2*k+1]); else printf(“%cis not rchild\n”, bt[k])); return1; }收起
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机专业 数据结构 综合测试