西安理工大学
2016年攻读硕士学位研究生入学考命题纸
考试科目：数据结构                      863
一、单项选择题(共30分，每小题2分)
1、考虑将栈定义为顺序存储的栈还是链式存储的栈，是在选择数据的(  d  )。
a.逻辑结构    b.物理结构        c.相互关系        d.操作方法
2、在一个长度为n的顺序线性表中顺序査值为x的元素时，查成功时的平均查长度为(  c  )(假定每个元素的概率都相等)
a.n              b.(n+1)/2            c.n/2        d.(n-1)/2
3、组成数据的基本单位是(  c  )。
a.数据项        b.数据类型        c.数据元素        d.数据变量
4、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<2，4>，<4，1>}，则数据结构A是(  c  )。
a.线性结构        b树型结构            c.图型结构        d.集合
5、深度为K(K>=1)的二叉树至多有(        c    )个结点。
a.2k+1        b.2k-1            c.2k-1            d.2k-1
6、设某完全无向图中有n个顶点，则该完全无向图中有(    a    )条边。
a.n(n-1)/2        b.n(n-1)        c.n2            d.n2-1
7、二叉链表作为二叉树的存储结构，在具有n(n>0)个结点的二叉链表中空链域的个数为(  c )
a.2n-1        b. n-1            c. n+1            d.2n+1
8、已知一个有向图的邻接矩阵，要想删除所有以第i个点为起始点的弧，应该(c    )
a.删除邻接矩阵的第i行        b.除邻接矩阵的第i列
c.将邻接矩阵的第i行置零        d.将邻接矩阵的第i列置零
9、设无向图G中有n个点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为(        d)。课本164页
a. n, e        b.e,n        c. 2n, e                d.n,2e
10、设某强通图中有n个顶点，则该强道通图中至少有(    c    )条边。
a. n(n-1)        b. n+1            c. n                d. n(n+1)
11、下列四种排序中(  a  )的空间复杂度最大。
a.快速排序        b.冒泡排序            c.希尔排序            d.堆
12、设某二叉树中度数为0的结点数为N0，度数为1的结点数为N1，度数为2的结点数为N2，则下列等式成立的是(  c)课本117性质3
a. N0=N1+1        b. N0=N1+N2        c. N0=N2+1        d. N0=2N1+1
13、若要求算法的时间复杂度为O( nlogn)，且要求排序是稳定的，则可选择的排序方法
是(        c)课本264表9.1
a.快速排序        b.堆排序        c.归并排序            d.直接插入排序
14、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为(    d    )
a.O(1og2n)        b.O(1)            c.O(n2)            d. O(n)
15、设有序表中有1000个元素，则用二分查査元素X最多需要比较(        b)次。
a.25                    b.10            c.7                d.1
二、判断題(正确的画“√”，错误的画“×”)(共30分，每小题2分)
1、算法和程序没有区别，所以在数据结构中二者是通用的。(×        )
2、对于一棵二叉树，任意给定先序序列、中序序列和后序序列中的两个，都能够唯确定出该二叉树的形状。(    ×    )
3、顺序存储结构只能存储线性结构，链式存储结构只能存储非线性结构。(    ×    )
4、中序遍历二叉排序树一定可以得到一个有序的序列。(    √    )
5、对于图结构，调用一次深度优先遍历可以访问到图中的所有顶点。(    ×    )
6、带权无向图的最小生成树是唯一的。(        ×    )
7、完全二叉树一定是满二叉树，满二叉树不一定是完全二叉树。(        ×)
8、存储无向图的邻接矩阵不一定是对称的。(        ×    )
9、折半插入排序的排序时间代价与初始数据无关。(×        )
10、连通分量是无向图中的极小连通子图。(    √    )
11、折半查只能在有序的顺序表上进行。(    √    )
12、理想情况下，在散列表上搜索一个元素的时间复杂度为O(1)。(    √    )
13、线性表的顺序存储结构比链式存储结构更好。(    ×    )
14、最小生成树就是指图的边数最少的生成树。(    ×    )
15、度不大于二的树就是二叉树。(    ×    )
三、填空题(共30分，每空2分)
1、数据结构是指(        数据元素的集合                        )及其相互之间的关系。
2、在顺序存储的队列中，为了解决(        假溢出                    )问题引入了循环队列。课本74页
3、数据结构研究数据的逻辑结构、数据的存储结构和(    数据的物理结构                )三方面的问题。
4、当线性表的元素总数基本稳定，且很少进行插入和別除操作，应采用(        顺序)存储结构。
5、设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为(        3            )。
6、普里姆算法的时间复杂度为(        O（n2）            )，与网中的边数无关，因此求边稠密的网的最小生成树更加适合。课本181页
7、在图的广度优先搜算法中用到了(            队列        )数据结构。课本175页
8、在有n个叶子结点的哈夫曼( Huffman)树中，结点总数是(    2n-1        )。
9、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中
(n-i+1        )个数据元素；删除第主i个位置上的数据元素需要移动表中(    n-i    )个元素。课本25和27页
10、已知一棵二叉树的中序遍历序列为 BCAED、后序遍历序列为 CBEDA，其先序遍
历的序列为(        ABCDE            )。
11、在有序表(12，24，36，48，60，72，84)中二分査关键字72时所需进行的关键字比较次数为(        2        )。
12、设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为(                        )。
13、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数
之和等于顶点i的(    出度    )，第i列中所有非零元素个数之和等于顶点i的(    入度        )。
四、简答题(共30分，每小题5分)
1、设一组初始记录关键字集合为(25，10，8，66，27，32，46)，散列表的长度为8，散列函数H(k)=kmod7，要求分别用线性探测再散列和链地址法作为解决冲突的方法设计哈希表，并给出在等概率查情况下，两种哈希表的平均查长度。
2、从空树起，依次插入关键字40，23，12，8，90，15，62，95，70，32，13，构造一棵二叉排序树。
(1)画出该二叉排序树。
(2)画出删去该树中元素值为23的结点之后的二叉排序树。
3.假设用于通讯的电文由，9个字母{A，B，C，D，E，F，G，H，I}组成，各字母在电文中出现的概率分别为0.06，0.19，0.09，0.10，0.08，0.14，0.20，0.03，0.11，试为这9个字母设计哈夫曼树，并写出对应的哈夫曼编码。设频率小的在结点的左边，频率大的在结点的右边。
4.已知树如图1所示，
(1)写出该树的后序遍历序列
(2)画山由该树转换得到的二叉树。
5、有如图2所示的二叉树，试画出中序线索二叉树，写出该线索二叉树的链式存储结点结构，并画出其中序线索链表结构。
数据结构与算法考研真题
图2
6、已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7}；
E={(1,2)3，(1,3)5，(1,4)8，(2,5)10，(2,3)6，(3,4)15，(3,5)12，(3,6)9，(4,6)4，(4,7)20，(5,6)18， (6,7)25}；
给出用克鲁斯卡尔算法构造最小生成树的过程，写出在最小生成树中依次得到的各条边。
五、算法设计题(共30分，每小题10分)
用C或 Pascal(类C和类 Pascal也可)完成以下题目。要求写出实现算法的函数或过程即可，不必写出整个程序，对算法要加以适当的注解
1、已知带头结点的单链表L中的结点数据是整数且按值递增排列，设单链表结点类型定义如下。
typedef struct Node {
Datatype data;
Stret Node *next ;
} Lnode, *LinkList;
1)编写一个算法，将值为x的结点插入到表L中，使得L仍然有序。
2)编写一个算法，在该链表上实施查数据值为key的査运算，算法返回指向该结点的指针。
2、设有如下的二叉链表存储的二叉排序树，其结点类型定义为
typedef struct node
{
int data;
Struct node *lchild, *rchild;
} Bstree;
1)编写一个递归算法，统计二叉树t中叶子结点的个数。
2)编写一个递归算法，可以统计树的深度。
3、试写出冒泡排序算法将整型数组A[1….N]按从大到小的次序进行排序，要求排序过程中能够考虑没有达到既定循环次数，可以提前结束排序大循环的情况。