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

《哈尔滨工程大学-考研数据结构真题-7.doc》由会员分享，可在线阅读，更多相关《哈尔滨工程大学-考研数据结构真题-7.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目: 数据结构 A卷 题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1算法的时间复杂度取决于 。A问题的规模 B. 待处理数据的初态 C. A和B2链表不具有的特点是 。A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比3在双向链表存储结构中，删除p所指的结点时须修改指针 。A p-prior-next=p-next；p-next-prior=p-prior；B p-prior= p-prior-prior；p-prior-next=p；C p-next-prior=p

2、；p-next=p-next-next；D p-next = p-prior-next； p-prior= p-next-next； 4输入序列为ABC，可以变为CBA时，经过的栈操作为 。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop5设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的

3、容量至少应该是 。A 6 B. 4 C. 3 D. 26设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 。A. 13B. 33C. 18D. 407广义表运算式GetTail(a,b),(c,d)的操作结果是 。A. (c,d) B. c,d C. (c,d) D. d8对n个元素的表做顺序查找时，若查找每个元素的概率相同，则查找成功的平均查找长度为 。A(n+1)/2 B. n/2 C. n D. (1+n)n)/29设有一表示算术表达式的二叉树，它所表示的算术表达式是 。A. A*B+C/(D*E)

4、+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+(F-G) D. A*B+C/D*E+F-G10一棵树高为K的完全二叉树至少有 个结点。A2k1B. 2k-11C. 2k-1D. 2k11若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 遍历方法最合适。A先序 B中序 C后序 D按层次12下面结构中最适于表示稀疏无向图的是 。A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表13在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 型调整以使其平衡。A.

5、LLB. LRC. RLD. RR14数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的 的两趟排序后的结果。A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序15对下列关键字序列用快速排序法进行排序时，速度最快的情形是 。A21,25,5,17,9,23,30 B25,23,30,17,21,5,9C21,9,17,30,25,23,5 D5,9,17,21,23,25,30 二、填空题（每空1分，共10分）1线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。2设有二维数组A0.9,0.19，其每

6、个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6存储地址为_。3当广义表中的每个元素都是原子时，广义表便成了_。4在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_。5一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_。6已知一无向图G=（V，E），其中V=a，b，c，d，e ，E=(a,b)，(a,d)，(a,c)，(d,c)，(b,e)，现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_遍历方法。7. 己知有序表为(12，18，24，35，47，50，6

7、2，83，90，115，134)，当用折半查找法查找100时，需_次才能确定不成功。8在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_。9分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法。10不受待排序初始序列的影响，时间复杂度为O(n2)的排序算法是_。三、判断题（每空1分，共10分）1顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 ( )2线性表的特点是每个元素都有一个前驱和一个后继。( )3循环队列也存在空间溢出问题。( )4一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下

8、标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。 ( )5一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )6用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。( )7在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。( )8在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。( )9堆排序是稳定的排序方法。( )10在任何情况下，归并排序都比直接插入排序快。 ( )四、应用题（每题7分，共35分）1采用哈希函数H(k)=3*k MOD 13，并用线性探测开放

9、地址法处理冲突，在数列地址空间0.12中对关键字序列22、41、53、46、30、13、1、67、51，（1）构造哈希表（画示意图）；（2）求等概率下成功的平均查找长度。2一棵二叉树的先序、中序序列如下，请构造出该二叉树，并进行后序线索化。先序序列 ：A B D H I M E J C F K L G中序序列 ：H D I M B J E A K F L C G3给出一组关键字29，18，25，47，58，12，51，10，写出堆排序的过程（包括初始建大顶堆、堆顶每取下一个元素后堆调整）。4给定一组权值2、3、5、7、11、13、17、19、23、29、31、37、41，试画出哈夫曼树。5用克鲁斯卡尔算法构造下图的一棵最小生成树，并给出选边顺序。五、算法设计题（每题15分，共30分）1有一个带头结点的单链表，头指针为head，它的数据域的类型为整型，而且按自小到大的顺序排列，编写一个算法insertx_list(linklist *head，int x)，在该链表中插入值为x的元素，使该链表仍然有序。2请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。第5页 共6页第6页 共 6页