1、目录2012年青岛科技大学信息学院861数据结构考研真题2008年青岛科技大学信息学院861数据结构考研真题2007年青岛科技大学信息学院861数据结构考研真题2012年青岛科技大学信息学院861数据结构考研真题考试科目：数据结构注意事项：1本试卷共 四 道大题（共计 38 个小题），满分150 分；2本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；3必须用蓝、黑钢笔或签字笔答题，其它均无效。一、选择题（152=30分）1研究数据结构就是研究 。A数据的逻辑结构B数据的逻辑结构、存储结构及其数据在运算上的实现C数据的逻辑结构D
2、数据的存储结构2下面程序段的时间复杂度为_。for（int i=0; im; i+）for（int j=0; jnext = HL;Bp-next = HL-next; HL-next = p;Cp-next = HL; p = HL;Dp-next = HL; HL = p；更多考研资料 v/q:344647 公众号/小程序：顺通考试资料6栈的插入与删除操作在 进行。A栈底 B栈顶 C任意位置 D指定位置7对长度为64的有序查找表进行折半查找，查找所有关键字，最多比较的次数是 。A7 B32C5D648为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依
3、次写入该缓冲区,而打印机则依次从该缓冲区中取出数据.该缓冲区的逻辑结构应该是 。A栈 B队列 C树 D图9若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是 。A9 B11 C12D不确定10高度为h的二叉树（仅含根结点的二叉树高度为零）的结点最少是多少 。A2h1 Bh1C2h+11D2h11由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 。A72 B53 C48 D2412ALV树是一种平衡的二叉排序树，树中任一结点的 。A左右子树高度差的绝对值不超过1 B左右子树的高度均相同C左子树的高度均大于右子树的高度 D左子树的高度均小于右子树的高度1
4、3下列线性结构中能用折半法进行查找的是 。A单链表 B顺序存储的有序线性表 C二叉链表 D有序线性链表14已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点,则完全二叉树的结点个数最多是 。A52B39 C111 D11915假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是 。Afront!=NULLBfront=rear Crear!=NULL Dfront=NULL二、填空（201=20分）1数据的逻辑结构被分为_、_、_和_四种。2数据的存储结构被分为_和_两种。3在线性表的单链式存储结构中，每个结点包含有两个域，一个叫_域，另一个叫_域。4在一个稀疏矩阵中
5、，每个非零元素所对应的三元组包括该元素的_、_和_三项。5对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为_个，其中_个用于指向孩子结点，_个指针空闲着。6对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_。7从有序表（12,18,30,43,56,78,82,95）中依次二分查找43和56元素时，其查找长度分别为_和_。8对于线性表（18,25,63,50,42,32,90）进行哈希存储时，若选用H（K）=K % 9作为哈希函数，则哈希地址为0的元素有_（18）_个，哈希地址为5的元素有_个。9在一个具有n个顶点的无向完全图中，包含有_条边。三、应用题（50分）1（4分）设计
6、一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。 2（6分）如图1是稀疏矩阵：（1）写出它的三元组线性表；（2）给出它的三元组顺序表的表示； 图13（6分）对于无向图按顺序输入顶点对：（0，1），（0，2），（1，3），（3，2），（3，4），（2，4），画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列。4（6分）已知如下所示长度为10的列表（50,30,80,20,40,90,35,85,22,88）（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树,请画出插入完成后的二叉排序树。（2）若对表中元素
7、先进行排序构成有序表,求在等概率情况下对此表进行折半查找成功的平均查找长度。5（6分）设有一组关键字9，01，23，14，55，20，84，27，采用哈希函数：H（key）=key MOD 7，表长为10，用开放地址法的二次探测再散列方法Hi=（H（key）+di） MOD 10（di=12，22，32，）解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。6（6分）已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点,问该树中有多少个叶子结点？并证明你的结论。7（6分）设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。（1）利用直接
8、插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。（2）利用归并排序的方法写出每一趟二路归并排序后的结果。8（6分）请给“数据结构”和“抽象数据类型”下个定义。9（4分）请叙述一下给单链表加头结点的好处。四、算法设计题（50分）1（10分）用类c的语言写出在带头结点的单链表中，删除单链表L中值为奇数结点的算法。2（10分）用栈和队列写一个算法判断一个字符序列是否是回文（回文就是一个字符串正着读和倒着读都一样，如：“ABCBA”）。3（10分）在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计二叉树叶子结点数目的算法。4（10分）试在无向图的邻接表上实现如下算法：
9、（1）往图中插入一个顶点（2）往图中插入一条边5（10分）请设计一个算法实现将栈中的元素倒置。2008年青岛科技大学信息学院861数据结构考研真题考试科目：数据结构注意事项：1本试卷共 4 道大题（共计 41 个小题），满分150分；2本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；3必须用蓝、黑钢笔或签字笔答题，其它均无效。一、选择题（总分：40分，每小题2分）1以下与数据的存储结构无关的术语是（ ）。A循环队列B链表 C哈希表 D栈2在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为（）。An-i
10、+1Bn-i CiDi-13为查找某一特定单词在文本中出现的位置，可应用的串运算是（）。A插入B删除C串联接D子串定位4下面算法的时间复杂度为（）int f（ unsigned int n ） if （ n=0 | n=1 ） return 1;else return n*f（n-1）;AO（1） BO（n） CO（n2） D.O（n!）5三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A345的存储地址为（）。A356B358C360D3626下列陈述中正确的是（）。A二叉树是度为2的有序树B二叉树中结点只有一个孩子时无左右
11、之分C二叉树中必有度为2的结点D二叉树中最多只有两棵子树，并且有左右之分7假定一棵三叉树的结点数为50，则它的最小高度为（）。A3B4C5D68已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为（）。Aadbefc Badcefb Cadcbfe Dadefcb9.ALV树是一种平衡的二叉排序树，树中任一结点的（） 。A左、右子树的高度均相同B左、右子树高度差的绝对值不超过1C左子树的高度均大于右子树的高度D左子树的高度均小于右子树的高度10给定一个整数集合3，5，6，9，12，下列二叉树哪个是该整数集合对应的哈夫曼（Huffman）树（）。11在含有n个结点的
12、二叉树二叉链表中有（）个空链域。An Bn-1 Cn+1 D（n+1）/212一个栈的输入序列为123n，若输出序列的第一个元素是n，输出的第i（1=i=n）个元素是（）。A不确定Bn-i+1 CiDn-i13适用于折半查找的表的存储方式及元素排列要求为（ ） 。A链接方式存储，元素无序B链接方式存储，元素有序C顺序方式存储，元素无序D顺序方式存储，元素有序14折半查找的时间复杂性为（ ）AO（n2）BO（n）CO（nlog n）D O（log n）15对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（）排序。A选择 B快速
13、C希尔D冒泡16设a，b为二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。Aa在b的右方 Ba在b的左方 Ca是b的祖先Da是b的子孙17.n个顶点的强连通图至少有（ ）条边。AnBn-1 Cn+1 Dn（n-1）18静态链表中指针表示的是（）。A内存地址B数组下标C下一元素地址 D左、右孩子地址19若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1=i0） ? x* f（x-1）:2）;int i ;i =f（f（1）;A2B4C8D无限递归二、填空题（总分：30分，每空2分）1若一个算法中的语句频度之和为T（n）=3720n+4nlogn，
14、则算法的时间复杂度为_；而下列程序段的时间复杂性的量级则为 。for（i=0;in;i+）for（j=0;jn,则结点i无_；若2i+1n，则结点i无_。4经过下列运算后StackTop（s）的值是_：InitStack（s）;Push（s,a）;Push（s,b）;Pop（s）。5对称矩阵的下三角元素ai,j，存放在一维数组vk中，k与i,j的关系是k_。6在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为_。查找关键字最多比较的次数_。7对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为_。8、已知一个图如下
15、所示，该图最小生成树中各边权值之和为_，在该图的最小生成树中，从顶点1到4的路径为_。9下列程序中所描述函数f的功能为：判断字符串s 是否对称，对称则返回1，否则返回0；如 f（abba）返回1，f（abab）返回0；请完成填空，满足功能要求。int f（1）_） int i=0,j=0;while （sj）（2）_;for（j-; ij & si=sj; i+,j-）; return（3）_） 三、应用题（总分：40分）1（8分）什么是数据结构？数据结构有哪几类基本结构？设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。2（7分）简
16、述单链表中设置头结点的作用；写一个算法实现建立一个带头结点的单链表，注意先用文字说明算法的思想。3（4分）画出广义表L=（a,（ ）,b）,（e） 的存储结构图，并利用取表头和取表尾的操作分离出原子e。4（4分）画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。5（6分）给出下图：（1）画出图的邻接表表示图；（2）根据你画出的邻接表，以顶点 为根，画出图的深度优先生成树和广度优先生成树。 6（6分）阅读下列算法，并回答下列问题：（1）、该算法采用何种策略进行排序?（2）、写出用此种排序方法对关键字序列49，38，65，97
17、，76，13，27排序的过程。void Sort （ SqList &L ） for （ i=2; i=L.length; +i ） if （L.ri.key L.ri-1.key）L.r0 = L.ri; for （ j=i-1; L.r0.key next=h Bp-next=NIL Cp-next-next=hDp-data=-12在双向链表存储结构中，删除p所指的结点时须修改指针（）。Ap-prior -next=p-next; p-next -prior=p-prior;Bp-prior=p-prior -prior; p-prior -next=p;Cp-next -prior=p
18、; p-next=p-next -next;Dp-next=p-prior -prior; p-prior=p-next -next;3静态链表中指针表示的是（）。A内存地址B数组下标C下一元素地址 D左、右孩子地址4链表不具有的特点是（）。A插入、删除不需要移动元素 B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性长度成正比5设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是（）。AXYZBYZX CZXY DZYX6串的长度是指（）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数7数组A0.5,0.6
19、的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是（ ）。A1175B1180C1205D12108具有10个叶结点的二叉树中有（）个度为2的结点。A8B9C10 Dll9要连通具有n个顶点的有向图，至少需要（）条边。An-lBn Cn+lD2n10设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（key）=keyMOD 13,散列地址为1的链中有（）个记录。A1B2C3D4二、填空题（总分：20分，每空2分）1在有m个选手参加的单循环赛中，总共将进行_场比赛。2数据结
20、构中评价算法的两个重要指标是 。3在一个长度为n的顺序表中第i个元素（1=inext; （1）_;while（2）_） r=L; q=L-next;while（3）_& q-datadata） r=q; q=q-next;u=p-next; （4）_; （5）_; p=u; 5设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear），则队满的条件为_。三、应用题（总分40分）1（4分）若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？2回答
21、问题（8分，每小题2分）（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。（4）评价各种不同数据结构的标准是什么？3（8分）数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4（5分）说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。5（10分）利用两个栈sl
22、,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。6（5分）一个nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？四、算法设计题（总分70分）1（10分）已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法，删除p所指结点。2（15分）编写对有序表进行顺序查找的算法。3（15分）冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。4（15分）知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。5（15分）已知线性表（a1 a2 a3 an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x x）变为（-x,-x,-xx,x,x）。
