数据结构经典十套卷之五 |
您所在的位置:网站首页 › 设一组初始记录关键字序列为60 › 数据结构经典十套卷之五 |
一、选择题(20分) 1.数据的最小单位是( )。 (A)数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为( )。 (A)40,50,20,95 (B)15,40,60,20 (C)15,20,40,45 (D)45,40,15,20 3.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。 (A) 15,25,35,50,20,40,80,85,36,70 (B) 15,25,35,50,80,20,85,40,70,36 (C) 15,25,35,50,80,85,20,36,40,70 (D) 15,25,35,50,80,20,36,40,70,85 4.函数substr(“DATASTRUCTURE”,5,9)的返回值为( )。 (A)“STRUCTURE” (B) “DATA” (C)“ASTRUCTUR” (D) “DATASTRUCTURE” 5.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( )。 (A)O(log2n) (B) O(1) (C) O(n2) (D) O(n) 6.设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=( )。 (A)Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C)N2+2N3+3N4+……+(m-1)Nm (D)2Nl+3N2+……+(m+1)Nm 7.设有序表中有1000个元素,则用二分查找查找元素X最多需要比较( )次。 (A)25 (B) 10 (C) 7 (D) 1 8.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为( )。 解:图的广搜深搜 (A)abedfc (B) acfebd (C) aebdfc (D) aedfcb 9.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是( )。 (A)n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是( )。 (A)40,42,45,55,80,83 (B) 42,40,45,80,85,88 (C)42,40,45,55,80,85 (D) 42,40,45,85,55,80
二、填空题(共20分) 1. 设有一个顺序共享栈S[0:n-1],其中第一个栈项指针top1的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是__ top1+1=top2__________________。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是_可以随机访问到任一个顶点的简单链表___________________。 3. 设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+1)个连续的存储单元中,则A[i][j]与A[0][0]之间有_i(i+1)/2+j-1___个数据元素。 4. 栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为_FILO_________表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为_FIFO________表。 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为_ABDECF__________,中序遍历序列为_DBEAFC__________,后序遍历序列为__DEBFCA_________。 6. 设一棵完全二叉树有128个结点,则该完全二叉树的深度为__8______,有______64____个叶子结点。 7. 设有向图G的存储结构用邻接矩阵A来表示,则A中第i行中所有非零元素个数之和等于顶点i的_出度_______,第i列中所有非零元素个数之和等于顶点i的__入度________。 8. 设一组初始记录关键字序列(k1,k2,……,kn)是堆,则对i=1,2,…,n/2而言满足的条件为_______________________________。 9. 下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句。 void bubble(int r[n]) { for(i=1;i int low=0,mid,high=n-1; while(low if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0||bt1->data!=bt2->data) return(0); elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 2. 设计两个有序单链表的合并排序算法。 voidmergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->datadata){if(s==0)hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb;s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |