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

班级：学号：姓名：装订线第1页共6页第2页共6页一、单项选择题（每空1分，共15分）1、以下与数据的存储结构无关的术语是（）。A．循环队列B.链表C.哈希表D.栈2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)3、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A．s-next=p；p-next=s；B．s-next=p-next；p-next=s;C．s-next=p-next；p=s；D．p-next=s；s-next=p;4、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表5、对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度6、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head＝＝NULLB．head-next＝＝NULLC．head-next＝＝headD．head!=NULL7、一个队列的入队序列是a、b、c、d、e，则队列的输出序列是()。A．a，b，c，e，dB．c，d，e，b，aC．a，b，c，d，eD．d，e，a，c，b8、若串S1=‘ABCDEFG’，S2=‘9898’，S3=‘###’，S4=‘012345’，执行Concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）A．ABC###G0123B．ABCD###1234C．ABC###G2345D．ABC###G12349、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（ij）的位置k的关系为()。A．i*(i-1)/2+jB．j*(j-1)/2+IC．i*(i+1)/2+jD．j*(j+1)/2+i10、表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A．3,2,4,1,1；(*^(+*-B．3,2,8；(*^-C．3,2,4,2,2；(*^(-D．3,2,8；(*^(-11、设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是。A．m-nB．m-n-1C．n+1D．条件不足，无法确定12、一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间13、下列关于m阶B-树的说法错误的是()A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页14、有向完全图是20个顶点的有向图最大边数是()。A．400B．380C．200D．19015、关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路二、判断题（每空1分，共10分）1、()2、队列和栈都是运算受限的线性表，只允许在表的两端进行运算()3、()4、栈是实现过程和函数等子程序所必需的结构。()5、二叉树中序线索化后，不存在空指针域。()6、当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。()7、在n个结点的无向图中，若边数大于n-1，则该图必是连通图。()8、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列()9、()10、()数据结构的抽象操作的定义与具体实现有关。稀疏矩阵压缩存储后，必会失去随机存取功能。邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（101，88，46，70，34，39，45，58，66，10）是堆。Hash表的平均查找长度与处理冲突的方法无关。三、填空题（每空1分，共10分）1、链接存储的特点是利用________来表示数据元素之间的逻辑关系。指针2、一个栈的输入序列是：1，2，3则不可能的栈输出序列是________。3、广义表A(((),(a,(b),c)))，head(tail(head(tail(head(A))))等于________。4、表达式A+B/(C-D)+E-F*G的后缀表达式是________。ABCD-/+E+FG*-5、带头结点的双循环链表L中只有一个元素结点的条件是：________。6、在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应选取________排序。堆7、有一个10阶对称阵A，采用压缩存储方式(以行序为主序，且A[0][0]＝1)，则A[8][5]的地址是________。428、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为________。9、一棵3阶3层（根为第一层，叶子为第三层）的B-树，至多有________个关键字。810、求图的最小生成树中有两种算法，________算法适合于求稀疏图的最小生成树。四、应用题（每题7分，共35分）1、假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。2、给出一组关键字{24，18，37，29，14，42，8，4}，写出用快速排序算法（选第一个记录为枢轴）从小到大排序时每一趟的排序结果。3、对于输入关键字序列{C，G，E，D，A，B，H，I，F}，建一棵平衡二叉树，画出过程（每次调整有一张）。4、下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出班级：学号：姓名：装订线第5页共6页第6页共6页13654219211656611141833所有可能的选择。5、设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=KMOD16,K为关键字，用线性探测再散列法处理冲突，输入关键字序列：(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题：(1)画出哈希表示意图；(2)若查找关键字63，需要依次与哪些关键字比较?(3)若查找关键字60，需要依次与哪些关键字比较?(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。五、算法设计题（每题15分，共30分）1、在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。2、设计算法，统计一棵二叉树中所有叶结点的数目及非叶结点的数目。