资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
文档供参考,可复制、编制,期待您的好评与关注! 哈尔滨工程大学试卷考试科目: 数据结构A 卷 题号一二三四五总分分数评卷人一、 单项选择题(每空1分,共15分)1. 从逻辑上可以把数据结构分为( )两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构2. 下述哪一条是顺序存储结构的优点?( )A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示3. 栈在( )中应用。A递归调用 B子程序调用 C表达式求值 DA,B,C4. 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。A5 1 2 3 4 B4 5 1 3 2 C4 3 1 2 5 D3 2 1 5 45. 最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是 ( )。A(rear+1) MOD n=front Brear=front Crear+1=front D(rear-l) MOD n=front6. 表达式a*(b+c)-d的中缀表达式是 。A-*a+bcd Ba*b+c-d Cabc*+d- Dabc+*d-7. 串的长度是指( )。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数8. 设有数组Ai,j,数组的每个元素长度为3字节,i的值为1 到8,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A5,8的存储首地址为( )。ABA+141 BBA+180 CBA+222 DBA+2259. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( )。Ahead(tail(LS) Btail(head(LS)Chead(tail(head(tail(LS) Dhead(tail(tail(head(LS)10. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为( )。A5 B6 C7 D811. 设给定权值总数有n 个,其哈夫曼树的结点总数为( ) 。A不确定 B2n C2n+1 D2n-112. 在下列存储形式中,哪一个不是树的存储形式?( )A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法13. 要连通具有n个顶点的有向图,至少需要( )条边。An-l Bn Cn+l D2n14. 哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行( )次探测。Ak Bk+1 Ck(k+1)/2 D1+k(k+1)/215. 某内排序方法的稳定性是指( )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0(n log n)的排序方法 D以上都不对二、 判断题(每空1分,共10分)1. 算法的优劣与算法描述语言无关,但与所用计算机有关。( ) 2. 循环链表不是线性表。 ( ) 3. 栈和队列都是限制存取点的线性结构。( )4. 通常使用队列来处理函数或过程的调用。( )5. 完全二叉树一定存在度为1的结点。( )6. 树与二叉树是两种不同的树型结构。( )7. 在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。( )8. 查找相同结点的效率折半查找总比顺序查找高。( )9. 直接选择排序算法在最好情况下的时间复杂度为O(N)。( )10. 在待排数据基本有序的情况下,快速排序效果最好。( )三、 填空题(每空1分,共10分)1. 在下面的程序段中,对x的赋值语句的频度为_(表示为n的函数)。 FORi: TO nDO FORj:TO iDO FOR k:1TOjDOx:xdelta;2. 循环单链表的最大优点是:_。3. 设有一个空栈,现有输入序列为1,2,3,4,5,经过PUSH,PUSH,POP,PUSH, POP,PUSH,PUSH之后,输出序列是_。4. 在二叉树中,指针p所指结点为叶子结点的条件是_。5. 具有256个结点的完全二叉树的深度为_。6. 为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需_存放被访问的结点以实现遍历。7. 对n个记录的表r1.n进行简单选择排序,所需进行的关键字间的比较次数为_。8. 设用希尔排序对数组98,36,-9,0,47,23,1,8,10,7进行排序,给出的增量序列依次是4,2,1写出第一趟结束后,数组中数据的排列次序_。9. 关键码序列05,23,16,68,94,72,71,73是否满足堆的性质_。10. 将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是_。四、 应用题(每题7分,共35分)1. 对关键字序列(30,51,46,20,64,60,8,28,15),构造一棵平衡二叉树并画图。2. 一棵二叉树的先序序列是ABIJCDFGEH,中序序列是BJIAFDGCEH,请写出后序序列并画出该二叉树。3. 假设字符R、S、T、U、V、W的应用频率分别是2,3,6,9,12,15,请画出相应的哈夫曼树,并求其哈夫曼编码。4. 对无向带权图,用克鲁斯卡尔算法构造最小生成树。62953413ABDFCEG25. 给出一组关键字58,24,29,15,18,60,34,38,写出堆排序的过程(包括初始建大顶堆、堆顶每取下一个元素后堆调整)。五、算法设计题(每题15分,共30分)1. 已知不带头结点的线性链表list,链表中结点构造为(data,link),其中data为数据域,link为指针域。请写一算法,将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。2. 在一棵以二叉链表表示的二叉树上,试写出统计树中具有度为1的结点数目的算法。 /
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号