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

班级：学号：姓名：装订线第1页共6页第2页共6页abedcf一、单项选择题（每空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指向一待插入结点，现要求在p前插入q，则正确的插入为（）。A．p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink;B．q-llink=p-llink;p-llink-rlink=q;q-rlink=p;p-llink=q-rlink;C．q-rlink=p;p-rlink=q;p-llink-rlink=q;q-rlink=p;D．p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-llink=q;3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表4、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（）。A．fedcbaB．bcafedC．dcefbaD．cabdef5、下面关于串的叙述中，（）是不正确的。A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储6、广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。A．(g)B．(d)C．cD．d7、将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A6665（即该元素下标i=66，j=65）在B数组中的位置K为（）。A．198B．195C．1978、下述二叉树中，（）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。A．二叉排序树B．哈夫曼树C．平衡二叉排序树D．堆9、一棵树高为K的完全二叉树至少有（）个结点。A．2k–1B．2k-1–1C．2k-1D．2k10、设图如下所示，在下面的5个序列中，符合深度优先遍历的序列有（）。aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页11、具有12个关键字的有序表，折半查找的平均查找长度为（）。A．3.1B．4C．2.5D．512、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A．(N+1)/2B．N/2C．ND．[(1+N)×N]/213、在下列排序算法中，（）算法的时间复杂度与初始排序无关。A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序14、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{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，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不对二、判断题（每空1分，共10分）1、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）2、线性表的特点是每个元素都有一个前驱和一个后继。（）3、即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）4、循环队列也存在空间溢出问题。（）5、一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，就完成了Am*n的转置运算。（）6、对一棵二叉树进行层次遍历时，应借助于一个栈。（）7、在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。（）8、一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）9、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）10、在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。（）三、填空题（每空1分，共10分）1、数据结构中评价算法的两个重要指标是_______。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。3、两个栈共享空间时栈满的条件是_______。4、空格串的长度等于_______。5、设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_______。6、己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为_______。7、广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。8、高度为8的完全二叉树至少有_______个叶子结点。9、有向图G=(V,E)，其中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,May,June,July,Aug,Sep,Oct,Nov,Dec}，按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。班级：学号：姓名：装订线第5页共6页第6页共6页2、已知一棵二叉树的中序遍历序列为DGBAECHIF，后序遍历序列为GDBEIHFCA，（1）试画出该二叉树；（2）试画出该二叉树的中序线索树；（3）试画出该二叉树对应的森林。3、给定一组权值2,3,5,7,11,13,17,19,23,29,31,37,41，试为这些字符设计哈夫曼编码。4、根据普利姆(Prim)算法，求下图的最小生成树。5、对下面的关键字集{30,15,21,40,25,26,36,37}，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功的平均查找长度。五、算法设计题（每题15分，共30分）1、已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。2、在二叉排序树中查找值为x的结点，如果找到这个结点则删除，没找到则插入。EABGCDF536141325