湖北工业大学计算机学院836数据结构历年考研真题汇编

《湖北工业大学计算机学院836数据结构历年考研真题汇编》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目　录2008年湖北工业大学计算机学院917数据结构历年考研真题汇编考研真题52007年湖北工业大学计算机学院440数据结构历年考研真题汇编考研真题122006年湖北工业大学计算机学院409数据结构历年考研真题汇编考研真题172005年湖北工业大学计算机学院409数据结构历年考研真题汇编考研真题212004年湖北工业大学计算机学院411数据结构历年考研真题汇编考研真题25说明：数据结构科目代码更换频繁，2016年科目代码是836，本书以此为准。2008年湖北工业大学计算机学院917数据结构历年考研真题汇编考研真题二○○八年招收硕士学位研究生试卷试

2、卷代号917试卷名称数据结构①试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确②考生请注意：答案一律做在答题纸上，做在试卷上一律无效。一．单项选择题（在每小题列出四个供选择的答案A．B．C．D中，选一个正确的答案,将其代号填在答卷纸相应题号后的下横线上，每小题2分，共20分）1．以下术语与数据的存储结构无关的是（）。A．栈B.哈希表C.双向链表D.线索二叉树2．在一个以h为头指针的双向循环链表中，指针p所指的元素是尾元素的条件是（）。A.p==hB.h->rlink==pC.p->llink==hD.p->rlink==h3．设栈S和队

3、列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是a,c,f,e,d,b，则栈S的容量至少应该是()。A．6B.5C.4D.34．用循环链表表示队列，设队列的长度为n，若只设尾指针，则出队和入队的时间复杂度分别为()。A．O(1)，O(1)B.O(1)，O(n)C.O(n)，O(1)D.O(n)，O(n)5．设串s1=“ABCDEFG”，s2=“12345”，则strconcat(strsub(s1,2,strlen(s2)),strsub(s1,strlen(s2),7))的结果串是()

4、。A．BCDEFB．BCDEFGC．EFGD．BCDEEFG6．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：T中任一结点V，其编号等于V左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按()编号的。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次遍历序列7．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。A．（15，13，14，6，17，16，18）B.（15，17，16，18，13，6，14）C.（15，6，13，

5、14，17，16，18）D.(15，13，6，14，17，18，16)8．已知由7个顶点组成的无向图的邻接矩阵为：ABCDEFG湖北工业大学二○○八年招收硕士学位研究生试卷第2页共4页则从顶点A出发进行深度优先遍历可以得到的序列是：（）A．ACEDBFGB．ACDGFBEC．AECDBGFD．ABDGFEC9．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)10．采用快速排序方法对一组数据（43，3，43，33，38，78，73）进行排序，则以43为基准进行第一趟划

6、分后数据的排序为()（按递增序）。A．（33,3,38,43,43,73,78）B．（3,33,38,43,43,78,73）C．（3,33,38,43,43,73,78）D．（38,3,43,33,43,78,73）二．填空题（每小题2分，本题共20分）1．在下面的程序段中，对ｘ赋值的语句的频度为______。for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)ｘ＝ｘ＋1；2．线性表L=（a1,a2,…,an）用数组表示，假如仅在ai与ai+1（1≤i≤n-1）之间插入元素，且插入元素的概率相同

7、，则插入一个元素平均需要移动元素的个数为______。3．用PUSH表示入栈操作，POP表示出栈操作，若元素入栈的顺序为12345，经过操作后，出栈序列为23，栈内序列为145，相应的PUSH和POP的操作串为______。4．用一个大小为8的数组来实现循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，当rear和front值分别为2．7时，则当前队列中的元素的个数为______。5．设定权集w={1,2,4,6,8,9},构造关于w的哈夫曼树，则其带权路径长度WPL=______。6．若对满二叉树中的结点逐层编号（层号由

8、小到大，同一层中从左到右），根结点编号为1，其它依次为2，3，…，则编号为n的结点的父结点编号为______。7．对有17个元素的有序表