1、第1页共6页三 峡 大 学2017年研究生入学考试试题(A卷)科目代码： 836 科目名称： 数据结构 考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题（每空 2 分，共 20 分）1）_是组成数据的基本单位，是数据集合的个体。2）数据结构的存储结构分为顺序存储结构和_两种。3）如下程序段: for (i=1;i=9;i+) for(j=i+1;jnext =NULL C. L-next=L D. L! =NULL 2）若线性表最常用的操作是存取第i个元素及其前驱的值，可采用（ ）存储方式最节省时间。A. 单向链表 B. 双向链表 C. 单向循环链表 D. 顺序表3）某个栈的
2、入栈的序列为A,B,C,D,E,F,G，则可能的出栈序列为（ ）A. ABCDEFG B.GABCDEF C.DCBAGEF D.BAFDCEG4）评价一个算法性能好坏的重要标准是（ ）A. 算法易于调试 B.算法易于理解C. 算法的正确性 D. 算法的时间复杂度5）已知哈希表的长度m=20，哈希函数H(key)=key%19，关键字为k的记录在定位时产生了冲突，若采用开放定址解决冲突，则新地址的计算公式为（ ）A. (H(k)+di)%20 B. (H(k)+di)%19 C. (H(k)+di)/19D. (H(k)+di)/206）栈和队列的共同特点是（ ）A. 只允许在端点处插入和删除
3、元素 B.都是先进后出C. 都是后进先出 D. 没有共同点7）以下数据结构中哪一个是非线性结构？（ ）A. 队列 B. 栈 C. 线性表 D. 二叉树8）链表不具备的特点是（ ）A. 可随机访问任一结点 B. 插入删除不需要移动元素C. 不必事先估计存储空间 D. 所需空间与其长度成正比9）与单链表相比，双链表的优点之一是（ ）A. 插入、删除操作更简单 B. 可以进行随机访问C. 可以省略表头指针或表尾指针 D. 顺序访问相邻结点更灵活10）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）A. O(0) B. O(1) C. O(n) D. O(n2
4、)第 3 页三、简答题（每小题 10 分，共 50 分） 1、给出四种基本数据结构名称及其关系图示。2、数据结构研究内容主要包括数据的逻辑结构和数据的物理结构。请分别简述逻辑结构和物理结构的含义，并简要指出线性表的两种常见物理结构。3、已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。中序序列：D I G J L K B A E C H F后序序列：ILKJGDBEHFCA4、给定表（19，14，22，15，20，21，56，10）1）按元素在表中的次序，建立一棵二叉排序树；2）对1）中所建立的二叉排序树进行中序遍历，写出遍历序列；5、已知一维数组中的数据为（18，12，25，53，
5、18），1）试写出插入排序（升序）过程，2）并指出具有n个元素的插入排序的时间复杂度是多少？四、构造题（共 30 分）1、对以下关键字序列建立一个长度为20的哈希表（ZuoPing, ZuoWencheng, LiuJinqiao, LiMengting, LiWeiwen, ZhuZequn, WanQiubo），哈希函数为H(K)=(K中第一个字母在字母表中的序号)%19，用线性探测法解决冲突。要求给出如下结果：1）计算出每个关键字对应的哈希地址，如果有冲突，需要给出线性探测法解决冲突后的哈希地址。需要给出每个哈希地址的计算过程，并绘制构造好的哈希表。2）计算在等概率情况下查找成功时的平均
6、查找长度。五、编程完善程序（共20分）下列c语言编写的程序，主要完成如下功能：1）初始化三个带头结点的单链表La，Lb，Lc；2）连续读入一组整数（比如1 2 3 -1 -2 -3 4 -4 -5 5 0），并将非零整数第 4 页依次存储在单链表La中（注意：碰到第一个0结束输入）；3）将La分解成两个带头结点的单链表Lb和Lc，其中Lb中存放负整数，Lc中存放正整数。要求Lb和Lc利用La中的结点空间。4）在分解后，能显示Lb中所有的负整数，Lc中所有的正整数。请根据上述已知条件，并结合下面的代码，完成下面三个问题：1）在void DisplayList(LinkList L)函数体中，写出
7、代码，使之能显示单链表L中的数据元素；2）void DivideList(LinkList La, LinkList Lb, LinkList Lc)函数体中，写出代码，使之能将La分解成满足上述要求的Lb和Lc。3）假定在主函数中调用CreateFromTail(La)时，输入的整数系列是：1 2 3 -1 -2 -3 4 -4 -5 5 0，请给出主函数调用DivideList(La, Lb, Lc);后，调用DisplayList(Lb);和DisplayList(Lc);后的屏幕输出结果。/-代码-#include #include #define ElemType intstruct
8、 tag_node/*结点类型定义*/ElemType data;struct tag_node * next;typedef struct tag_node Node;typedef struct tag_node *LinkList;void InitList(LinkList * L);void CreateFromTail(LinkList L);void DisplayList(LinkList L);void DivideList(LinkList La, LinkList Lb, LinkList Lc);第 5 页main() LinkList La,Lb,Lc;InitLis
9、t(&La);/初始化单链表LaInitList(&Lb); /初始化单链表LbInitList(&Lc); /初始化单链表Lcprintf(构造链表La:请输入一系列整数，并以输入整数0结束输入n);CreateFromTail(La);/输入数据，构造单链表LaDivideList(La, Lb, Lc);/将La分解成Lb和Lcprintf(nAfter dividing:);DisplayList(Lb);/显示LbDisplayList(Lc);/显示Lcvoid InitList(LinkList * L)*L = (LinkList)malloc(sizeof(Node);(*L
10、)-next = NULL;void CreateFromTail(LinkList L) Node *r, *s;int c;int flag=1;r = L;while(flag) /* flag初值为1，当输入0时，置flag为0，建表结束*/scanf(%d,&c); if(c!=0)s=(Node*)malloc(sizeof(Node); /*建立新结点s*/s-data=c;r-next = s;第 6 页r=s;elseflag=0;s-next = NULL;void DisplayList(LinkList L)/请写出代码，实现显示单链表L中所有数据元素的功能/注意，答案写在答题纸上void DivideList(LinkList La, LinkList Lb, LinkList Lc)/请写出代码，实现将La分解成两个带头结点的单链表Lb和Lc的功能/注意，答案写在答题纸上/第3问的答案也写在答题纸上
