资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
河北工程大学单项选择题1.数据的(B )包括集合、线性、树和图 4 种基本类型A存储结构 B逻辑结构 C基本运算 D算法描述2.对一个长度为 n 的顺序表,在第 i 个元素(1in+1)之前插入一个新元素时需向右移动(B )个元素。An-i Bn-i+1 Cn-i-1 Di3 下面程序的时间复杂度为(C ) 。For(i=0;inext=p-next ) , ( p-next=q ) 。5 数据的( 逻辑 )结构与数据元素本身的内容和形式无关。6 一个算法的好坏取决于该算法的( 时间复杂度 )和( 空间复杂度 ) 。7 数据结构中评价算法的两个重要指标是( 时间复杂度 ) 、空间复杂度。 8 一个循环队列存储于下标由 0 开始且长度为 m 的一维数组中,假定队头和队尾指针分别为 front 和 rear,则判断队空的条件为( (rear+1)%n=front) 。则判断队满的条件为( front=rear ) 。9 队列的插入操作是在队列的( 队尾 )进行,删除操作是在队列的( 队头 )进行。10 堆栈的逻辑特点是( 先进后出 ) ,队列的逻辑特点是( 先进先出 ) 。11 堆栈的逻辑特点是( 先进后出 ) ,队列的逻辑特点是( 先进先出 ) 。二者的河北工程大学共同点是只允许在它们的( 端点 )处插入和删除数据元素。12 堆栈操作设输入元素的顺序为 1,2,3,4,5,要在栈的输出端得到 43521,则应进行栈的基本运算表示应为:Push( S,1) ,Push(S,2),Push(S,3),Push(S,4) ,Pop(S), ( Pop(S) ) , ( Push(S,5) ) ,Pop(S),Pop(S),Pop(S)。13 设有一个链队,结点结构为 data|next,front 为队头指针, rear 为队尾指针,当执行入队操作时需执行下列语句:malloc(p);p-data=x; p-next=NULL;( ) ;( ) ; 13、一棵二叉树有 67 个结点,这些结点的度要么是 0,要么是 2。这棵二叉树中度数为2 的结点有 个。14、一个哈夫曼(Huffman)树有 19 个结点,则其叶结点的个数是 。15、一棵深度为 6 的满二叉树有 31 个分支结点和 32 个叶子。16、设二叉树结点的先序序列为 ABDECFGH,中序序列为 DEBAFCHG,则二叉树的后序序列是 。 17. 克鲁斯卡尔算法的时间复杂度为( ) ,适合求( )的最小生成树。18.空串是() ,其长度等于( ) 。19.空格串是() ,其长度等于( ) 。20.两个字符串相等的充分必要条件是() 。21 写出模式串 p=“abaabcac”的 next 函数值序列为()22、设有一稀疏图 G,则 G 采用 存储结构较省空间。23、已知广义表 A=(a,b,c),(d,e,f),则运算 head(head (tail(A))=_ _.24一棵深度为 6 的满二叉树有 个分支结点和 个叶子。25在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第 7 个记录 60 插入到有序表时,为寻找插入位置至少需比较 次。应用题1什么是线性结构?线性结构的特点是什么? 列举?2.什么是树形结构?树形结构的特点是什么?3.什么是图结构?河北工程大学4.已知二叉树的前序 ABCDEFGHIJ 和中序 CDBFEAIHGJ,试构造出相应的二叉树。5.已知一棵二叉树的后序遍历序列为 EICBGAHDF,中序遍历序列为 ECIFBAGDH,请画出这棵二叉树,7. 对于一个有 10000 个结点的二叉树,树叶最多有多少个?最少有多少个?8 写出某个有向图的顶点 V 和弧 E 的邻接矩阵。9 已知某二叉树,写出前序遍历、中序遍历和后序遍历10 根据普里姆算法思想,画出构造该无向带权图最小生成树的过程。 (5 分)11 的有向带权图,根据狄克斯特拉算法思想,画出生成从顶点 A 到其余各项顶点最短路径的过程。12 已知序列34,17,6,29,33,11,80,37请用冒泡排序的方法从大到小进行排序,并给出详细过程。13 已知序列34,17,6,29,33,11,80,37请用直接选择排序的方法从大到小进行排序,并给出详细过程。14、已知一棵二叉树的中序序列和后序序列分别为: DBGEACHF 和 DGEBHFCA,则该二叉树的前序序列是什么?试画出这棵二叉树。15、给定权值集合15,03,14,02,06,09,16,17,构造相应的哈夫曼树,并计算它的带权路径长度。16设一数组 A56,A00的地址为 1100,且每个元素占 2 个存储单元,则这个二维数组的存储量为多少?A45 的地址为多少?如按行优先顺序存储 A23的地址为多少?17.用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画出该树,并求在等概率情况下查找成功的平均查找长度18.按下列要求,写出相应结果设关键字的输入次序为 45,24,53,45,12,24,90。画出生成的二叉排序树(5 分)。19 试画出具有 3 个结点的二叉树所有不同形态(5 分) 。写算法1.请写出顺序存储的线性表中,在第 i 个位置插入和删除数据元素 x 的实现算法。 (请在关键部分给出注释。 )河北工程大学2.请写出链式存储的线性表中,在第 i 个位置插入和删除数据元素 x 的实现算法。 (请在关键部分给出注释。 )3. 请写出链式堆栈操作中,入栈和 出栈的实现算法。 (请在关键部分给出注释。 )
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号