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

《哈尔滨工程大学-考研数据结构真题-8.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人一、单项选择题（每空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．

2、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开始顺序存放，当

3、用以列为主存放时，元素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．不确定

4、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.某内排序方法的稳定性是指()。第5页共6页第6页共6页班级：学号：姓名：装订线A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n

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

6、分）1.在下面的程序段中，对x的赋值语句的频度为________（表示为n的函数）。FOR　　i：＝１TOn　DO　　　FOR　　j：＝１　TOi　DO　FOR　k：＝1　TO　j　DO　x：＝x＋delta；2.循环单链表的最大优点是：________。3.设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是________。4.在二叉树中，指针p所指结点为叶子结点的条件是________。5.具有256个结点的完全二叉树的深度为________。6.为了实现图的广度优先搜索，除了一个标志数组标志已访问的

7、图的结点外，还需________存放被访问的结点以实现遍历。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个