2012年山东青岛科技大学数据结构考研真题.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2012 年山东青岛科技大学数据结构考研真题一、选择题（15×2=30 分） 1、研究数据结构就是研究。 A、数据的逻辑结构 B、数据的逻辑结构、存储结构及其数据在运算上的实现 C、数据的逻辑结构 D、数据的存储结构 2、下面程序段的时间复杂度为____________。 for(int i=0; inext = HL; HL->next = p;; A、HL = p; B、p->next = HL->next; C、p->next = HL; D、p->next = HL; p = HL; HL = p； 6、栈的插入与删除操作在进行。 A、栈底 B、栈顶 C、任意位置 D、指定位置 7、对长度为 64 的有序查找表进行折半查找，查找所有关键字，最多比较的次数是。 A、7 B、32

C、5 D、64 8、为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据.该缓冲区的逻辑结构应该是（）。 A、栈 B、队列 C、树 D、图 9、若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是。 A、9 B、11 C、12 D、不确定 10、高度为 h 的二叉树（仅含根结点的二叉树高度为零）的结点最少是多少。 A、2h＋1 B、h＋1 C、 2h+1－1 D、 2h 11、由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为。 A、 72 B、 53 C、 48 D、 24 12、ALV 树是一种平衡的二叉排序树，树中任一结点的( ) 。 A、左、右子树高度差的绝对值不超过 1 B、左、右子树的高度均相同 C、左子树的高度均大于右子树的高度 D、左子树的高度均小于右子树的高度 13、下列线性结构中能用折半法进行查找的是。 A、单链表 B、顺序存储的有序线性表 C、二叉链表 D、有序线性链表 14、已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则完全二叉树的结点个数最多是（） A、52 B、39 C、111 D、119 15、假定一个链队的队首和队尾指针分别为 front 和 rear，则判断队空的条件是。 A、front!=NULL B、front==rear C、rear!=NULL

D、front==NULL 二、填空（20×1=20 分） 1、数据的逻辑结构被分为___（1）____、__（2）___、__（3）_____和__（4）__四种。 2、数据的存储结构被分为__（5）______和_ （6）____两种。 3、在线性表的单链式存储结构中，每个结点包含有两个域，一个叫_（7）____域，另一个叫_（8）__域。 4、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_（9）___、_（10）___ 和__（11）___三项。 5、对于一棵具有 n 个结点的二叉树，对应二叉链表中指针总数为_（12）__个，其中__（13） ___个用于指向孩子结点，__（14）___个指针空闲着。 6、对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵大小为_（15）____。 7、从有序表(12,18,30,43,56,78,82,95)中依次二分查找 43 和 56 元素时，其查找长度分别为__（16）______和_（17）____。 8、对于线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用 H(K)=K % 9 作为哈希函数，则哈希地址为 0 的元素有_（18）__个，哈希地址为 5 的元素有_（19）___个。 9、在一个具有 n 个顶点的无向完全图中，包含有_（20）__条边。三、应用题（50 分） 1、（4 分）设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。 2、（6 分）如图 1 是稀疏矩阵：（1）写出它的三元组线性表；（2）给出它的三元组顺序表的表示； 0 0 36      0 0 28 14 0 07  0 0 图 1 5    0  0   3、（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)若对表中元素先进行排序构成有序表,求在等概率情况下对此表进行折半查找成功的平均查找长度。 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) 利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。（2）利用归并排序的方法写出每一趟二路归并排序后的结果。 8、（6 分）请给“数据结构”和“抽象数据类型”下个定义。 9、（4 分）请叙述一下给单链表加头结点的好处。四、算法设计题（50 分）

1、（10 分）用类 c 的语言写出在带头结点的单链表中，删除单链表 L 中值为奇数结点的算法。 2、（10 分）用栈和队列写一个算法判断一个字符序列是否是回文（回文就是一个字符串正着读和倒着读都一样，如：“ABCBA”）。 3、（10 分）在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计二叉树叶子结点数目的算法。 4、（10 分）试在无向图的邻接表上实现如下算法：（1）往图中插入一个顶点（2）往图中插入一条边 5、（10 分）请设计一个算法实现将栈中的元素倒置。

分享到：

赞收藏

资料库

2012年山东青岛科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料