哈尔滨工程大学-考研数据结构真题-8.doc

《哈尔滨工程大学-考研数据结构真题-8.doc》由会员分享，可在线阅读，更多相关《哈尔滨工程大学-考研数据结构真题-8.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目: 数据结构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 B

2、4 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 到

3、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 个，其哈

4、夫曼树的结点总数为( ) 。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

5、）的排序方法 D以上都不对二、 判断题（每空1分，共10分）1. 算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 2. 循环链表不是线性表。 ( ) 3. 栈和队列都是限制存取点的线性结构。( )4. 通常使用队列来处理函数或过程的调用。( )5. 完全二叉树一定存在度为1的结点。( )6. 树与二叉树是两种不同的树型结构。( )7. 在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。( )8. 查找相同结点的效率折半查找总比顺序查找高。( )9. 直接选择排序算法在最好情况下的时间复杂度为O（N）。( )10. 在待排数据基本有序的情况下，快速排序效果最好。(

6、 )三、 填空题（每空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个记录

7、的表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，请写出后

8、序序列并画出该二叉树。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的结点数目的算法。第5页 共6页第6页 共 6页