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

1、班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目: 数据结构a 卷 题号一二三四五总分分数评卷人一、 单项选择题（每空1分，共15分）1、下面说法错误的是（ ）。（1）算法原地工作的含义是指不需要任何额外的辅助空间。（2）在相同的规模n下，复杂度o(n)的算法在时间上总是优于复杂度o(2n)的算法。 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。（4）同一个算法，实现语言的级别越高，执行效率就越低。a（1） b（1），（2）c（1），（4） d（3）2、双向链表中有两个指针域，llink和rlink，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点

2、，现要求在p前插入q，则正确的插入为（ ）。 ap->llink=q; q->rlink=p; p->llink->rlink=q; q->llink=p->llink;bq->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink=q->rlink; cq->rlink=p; p->rlink=q; p->llink->rlink=q; q->rlink=p;dp->llink->rlink=q; q->rlin

3、k=p; q->llink=p->llink; p->llink=q;3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。a顺序表 b双链表 c带头结点的双循环链表 d单循环链表4、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（ ）。afedcba bbcafed cdcefba dcabdef5、下面关于串的叙述中，（ ）是不正确的。a串是字符的有限序列 b空串是由空格构成的串c模式匹配是串的一种重要运算d串既可以采用顺序存储，也可以采用链式存储6、广义表a=(a,b,(c,d)

4、,(e,(f,g)，则head(tail(head(tail(tail(a)的值为（ ）。a(g) b(d) cc dd7、将一个a1.100，1.100的三对角矩阵，按行优先存入一维数组b1.298中，a中元素a6665（即该元素下标i=66，j=65）在b数组中的位置k为（ ）。a198 b195 c197 8、下述二叉树中，（ ）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。a二叉排序树 b哈夫曼树 c平衡二叉排序树 d堆9、一棵树高为k的完全二叉树至少有（ ）个结点。a2k1 b2k-11 c2k-1 d2k10、设图如下所示，在下面的5个序列中，符合深度优先遍历

5、的序列有（ ）。a e b d f c a c f d e b a e d f c b a e f d c b a e f d b ca5个 b4个 c3个 d2个 11、具有12个关键字的有序表，折半查找的平均查找长度为（ ）。 a3.1b4c2.5d512、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。a(n+1)/2 bn/2 cn d(1+n)×n /213、在下列排序算法中，（ ）算法的时间复杂度与初始排序无关。a直接插入排序 b冒泡排序 c快速排序 d直接选择排序14、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为

6、4，9，-1，8，20，7，15，则采用的是（ ）排序。a选择b快速c希尔d冒泡15、有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（ ）。a-1，4，8，9，20，7，15，7 b-1，7，15，7，4，8，20，9c-1，4，7，8，20，15，7，9 da，b，c均不对二、 判断题（每空1分，共10分）1、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）2、线性表的特点是每个元素都有一个前驱和一个后继。（ ）3、即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）4、循环队列也存在空间溢出

7、问题。（ ）5、一个稀疏矩阵am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，就完成了am*n的转置运算。（ ）6、对一棵二叉树进行层次遍历时，应借助于一个栈。（ ）7、在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。（ ）8、一个有向图的邻接表和逆邻接表中结点的个数可能不等。 （ ）9、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）10、在9阶b-树中，除叶子以外的任意结点的分支数介于5和9之间。 （ ）三、 填空题（每空1分，共10分）1、数据结构中评价算法的两个重要指标是_。2、当线

8、性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。3、两个栈共享空间时栈满的条件是_。 4、空格串的长度等于_。5、设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_。6、己知三对角矩阵a1.9,1.9的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素a7,8的地址为_。7、广义表运算式head(tail(a,b,c),(x,y,z)的结果是_。8、高度为8的完全二叉树至少有_个叶子结点。9、有向图g=(v,e)

9、，其中v(g)=0,1,2,3,4,5，用<a,b,d>三元组表示弧<a,b>及弧上的权d，e(g)为<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>，则从源点0到顶点3的最短路径长度是_。10、在一棵m阶b-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_。四、 应用题（每题7分，共35分）1、已知长度为l2的表jan,feb,mar,apr,m

10、ay,june,july,aug,sep,oct,nov,dec，按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。2、已知一棵二叉树的中序遍历序列为dgbaechif，后序遍历序列为gdbeihfca，（1）试画出该二叉树；（2）试画出该二叉树的中序线索树；（3）试画出该二叉树对应的森林。3、给定一组权值2,3,5,7,11,13,17,19,23,29,31,37,41，试为这些字符设计哈夫曼编码。4、根据普利姆(prim) 算法，求下图的最小生成树。eabgcdf5361413255、对下面的关键字集30,15,21,40,25,26,36,37，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，（1）设计哈希函数； （2）画出哈希表；（3）计算