青 岛 科 技 大 学
二○一二年硕士研究生入学考试试题
考试科目：数据结构
注意事项：1．本试卷共 四 道大题（共计 38 个小题），满分150 分；
2．本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；
3．必须用蓝、黑钢笔或签字笔答题，其它均无效。
﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡
一、选择题（15×2=30分）
1、研究数据结构就是研究 。
A、 数据的逻辑结构 B、数据的逻辑结构、存储结构及其数据在运算上的实现
C、 数据的逻辑结构 D、数据的存储结构
2、下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
A、O(m*n) B、 O(n2) C、O(m2) D、 O(m+n)
3、在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 个元素。
A、n-i B、n-i+1 C、n-i-1 D、i
4、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 。
A、n B、(n+1)/2 C、n/2 D、(n-1)/2
5、在一个带头结点单链表HL中，若要向头结点后面，首元结点前面插入一个由指针p指向的结点，则执行 。
A、HL = p; p->next = HL;
B、p->next = HL->next; HL->next = p;;
C、p->next = HL; p = HL;
D、p->next = 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）给出它的三元组顺序表的表示；
图1
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分）请设计一个算法实现将栈中的元素倒置。