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

班级：学号：姓名：装订线第1页共6页第2页共6页一、单项选择题（每空1分，共15分）1.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2.下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示3.栈在（）中应用。A．递归调用B．子程序调用C．表达式求值D．A，B，C4.设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。A．51234B．45132C．43125D．321545.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A．(rear+1)MODn=frontB．rear=frontC．rear+1=frontD．(rear-l)MODn=front6.表达式a*(b+c)-d的中缀表达式是。A．-*a+bcdB．a*b+c-dC．abc*+d-D．abc+*d-7.串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数8.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A．BA+141B．BA+180C．BA+222D．BA+2259.已知广义表LS＝((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是()。A．head(tail(LS))B．tail(head(LS))C．head(tail(head(tail(LS)))D．head(tail(tail(head(LS))))10.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（）。A．5B．6C．7D．811.设给定权值总数有n个，其哈夫曼树的结点总数为()。A．不确定B．2nC．2n+1D．2n-112.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法13.要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n14.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行()次探测。A．kB．k+1C．k(k+1)/2D．1+k(k+1)/215.某内排序方法的稳定性是指()。哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对二、判断题（每空1分，共10分）1.算法的优劣与算法描述语言无关，但与所用计算机有关。()2.循环链表不是线性表。()3.栈和队列都是限制存取点的线性结构。()4.通常使用队列来处理函数或过程的调用。()5.完全二叉树一定存在度为1的结点。()6.树与二叉树是两种不同的树型结构。()7.在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。()8.查找相同结点的效率折半查找总比顺序查找高。()9.直接选择排序算法在最好情况下的时间复杂度为O（N）。()10.在待排数据基本有序的情况下，快速排序效果最好。()三、填空题（每空1分，共10分）1.在下面的程序段中，对x的赋值语句的频度为________（表示为n的函数）。FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOx：＝x＋delta；2.循环单链表的最大优点是：________。3.设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是________。4.在二叉树中，指针p所指结点为叶子结点的条件是________。5.具有256个结点的完全二叉树的深度为________。6.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需________存放被访问的结点以实现遍历。7.对n个记录的表r[1..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.对无向带权图，用克鲁斯卡尔算法构造最小生成树。5.给出一组关键字{58，24，29，15，18，60，34，38}，写出堆排序的过程（包括初始建大顶堆、堆顶每取下一个元素后堆调整）。62953413ABDFCEG2班级：学号：姓名：装订线第5页共6页第6页共6页五、算法设计题（每题15分，共30分）1.已知不带头结点的线性链表list，链表中结点构造为（data，link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。2.在一棵以二叉链表表示的二叉树上，试写出统计树中具有度为1的结点数目的算法。