2022年2022年暨南大学数据结构考研真题 .pdf

《2022年2022年暨南大学数据结构考研真题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年暨南大学数据结构考研真题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2012 年全国硕士研究生统一入学考试自命题试题*学科与专业名称：计算机技术，软件工程考试科目代码与名称：830 数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一.选择题(每题 2 分，共 30分)1队列操作的原则是（）。A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除2.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。A.edcba B.decba C.dceab D.abcde 3.采用顺序查找法查找长度为n 的线性表时,每个元素的平均查找长度为（）。A.n B.n/2 C.(n+1)/2 D.(n-1)/2 4.线性表的链接实

2、现有利于()运算。A.读表元素 B.插入 C.查找 D.定位5.设单链表中指针p 指着结点A,若要删除A 之后的结点(若存在),则需要修改指针的操作为()。A.p-next=p-next-next B.p=p-next C.p=p-next-next D.p-next=p 6.在内部排序中,排序时不稳定的有()。A.插入排序 B.冒泡排序 C.快速排序 D.归并排序7.在 AOE 网中，完成工程的最短时间是（）。A从源点到汇点的最长路径的长度B从源点到汇点的最短路径的长度C最长的回路的长度D最短的回路的长度8以下（）方法所用辅助存储空间最大。A 堆排序B 希尔排序C快速排序D归并排序9具有 8

3、 个顶点的无向图至少应有（）条边才能确保是一个连通图。A5 B 6 C7 D8 10.对具有 n 个结点的有序表中折半查找时，其时间复杂度是（）。AO(nlog2n）B O(log2n）CO(n）DO(n2）11如果希望对平衡二叉树遍历的结果是升序的，应采用（）遍历方法。A先序B中序C后序D层次考试科目：数据结构共 5 页，第1 页名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -12.稀疏矩阵一般的压缩存储方法有两种,即:（）。A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表13.循环队列中是否可以插入下一个元素（）。A.与曾经进行过多

4、少次插入操作有关.B.只与队尾指针的值有关,与队头指针的值无关.C.只与数组大小有关,与队首指针和队尾指针的值无关 D.与队头指针和队尾指针的值有关.14.在线索化二叉树中，T 所指结点没有左子树的充要条件是（）。AT-left=NULL BT-ltag=1 Ct-ltag=1 且 t-left=Null D以上都不对15.以下说法中不正确的是（）。A无向图中的极大连通子图称为连通分量B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D有向图的遍历不可采用广度优先搜索方法二填空题(每题 2 分，共 20 分)1一组记录（50，40，9

5、5，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为。2数据结构按逻辑结构可分为两大类，它们分别。3由 n 个权值构成的哈夫曼树共有个结点。4在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是：和。5单链表中设置头结点的作用是。6一棵深度为k 的满二叉树的结点总数为，一棵深度为k 的完全二叉树的结点总数的最小值为。7一个无向图有n 个顶点和e条边，则所有顶点的度的和为。8在二叉链表中判断某指针p 所指结点为叶子结点的条件是。9堆栈是一种操作受限的线性表，它只能在线性表的进行插入和删除操作，对栈的访问是按照的原则进行的。10若某记录序列的关键字

6、序列是（235，346，021，558，256），用链式基数排序方法排序，第一次收集的结果是。考试科目：数据结构共 5 页，第2 页名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -三判断题（每题1 分，共 10 分，正确的选 t，错误的选 f）1如果 T2 是由树 T1 转换而来的二叉树,那 T1中结点的先序就是T2 中结点的先序。（）2 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（）3线性表中的每一个元素都有一个前驱和后继元素。（）4按中序遍历一颗二叉排序树所得到的中序遍历序列f 是一个递增序列。（）5若网中有几条关键路径，提高一

7、条关键路径上的活动的速度，不能导致整个工程缩短工期。（）6一颗满二叉树同时又是一颗平衡树。（）7数据结构是研究数据的物理结构、逻辑结构以及它们之间的相互关系。（）8.拓扑排序是一种内部排序的算法。()9.已知一颗树的先序序列和后序序列，一定能构造出该树。（）10n 阶对称矩阵可压缩存储到n2/2 个元的空间中。()四.简答题（50 分）1.给定关键字序列T=(65，57，45，39，12，98，86，35），采用快速排序算法，以第一个元素为枢轴，对该序列由小到大排序，并写出具体排序过程。(8 分)2.简述下列算法的功能。（6 分）void Process(LinkList&L,int x,in

8、t y)/L 线性表的元素递增有序排列LinkList p=L,q,s;if(p-next)&(xnext&p-next-datanext;If(p-next)return ERROR;q=p-next;while(q-next&q-next-datanext;free(s);p-next=q-next;free(q);3.使用克鲁斯卡尔算法构造出图1 所示的图G 的一棵最小生成树（要求写出构造过程）。（10分）图 1考试科目：数据结构共 5 页，第 3 页名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -4.已知一个图如图2 所示，若从顶点a出发，按深度优先搜索法进行遍

9、历，写出可能得到的一种顶点序列；按广度优先搜索法进行遍历，写出可能得到的一种顶点序列。(4 分)图 25.给定图 3 所示带权有向图及其邻接矩阵，利用Floyd 算法，求每一对顶点之间的最短路径及其路径长度（要求写出求解过程）。（12 分）图 3 6给出一组关键字的序列为 12，15，34，37，39，22，38，66，74，80，107 ，假设哈希函数为 Hash(key)=key mod 11，画出按照链地址法处理冲突构造所得的哈希表，并在记录的查找概率相等的前提下，计算成功查找的平均查找长度。（10 分）五算法填空，（每空 2 分,共 16 分）1.下面的算法将元素e 加入队列Q 中，请

10、在处填上适当内容，使其成为一个完整算法。typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针QueuePtr rear;/队尾指针 LinkQueue,*LinkQueuePtr;Boolean EnQueue(LinkQueuePtr Q,QElemType e)/元素 e加入到队列Q 中p=;if(!p)return FALSE;考试科目：数据结构共 5 页，第 4 页名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5

11、页 -p-data=e;p-next=;=p;Q-rear=;return TRUE;2.下面是先序遍历二叉树的算法非递归算法，请在处填上适当内容，使其成为一个完整算法。typedef struct BiTNode /结点结构TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;void PreOrderTraverse(BiTree,Status(*Visit)(TElemType)/采用二叉链表存储结构,Visit 是对结点操作的应用函数InitStack(S);BiTree p=T;while()if(p)Visit(p-data);p=p-lchild;else ;p=;六编写算法（24）1试编写统计二叉树中叶子结点个数的算法。（10 分）2设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法。（14 分）考试科目：数据结构共 5 页，第5 页名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -