824数据结构与算法设计A

西安科技大学2013年硕士研究生入学考试试题 A科目编号：824科目名称： 数据结构与算法设计考生须知：1、答案必须写在答题纸上，写在试题或草稿纸上不给分。2、答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分3、答题必须写清题号，字迹要清楚，卷面要保持整洁。4、试题要随答题纸一起交回。一、单项选择题（每小题 2分，共30分）A.单链表（1）并归排序的时间复杂度是（ ）。A. O(n2)B. O(nlog2n)C. O(n)D. O(log2n)（2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（）存储结构最节 省时间。B 单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表3）散列文件是一种（ ）。A.顺序文件B.索引文件C.链接文件D.计算机寻址文件4）常用于函数调用的数据结构是（ ）。A.栈B.队列C.数组D.链表(5)两个矩阵A , Bms sn相乘的时间复杂度是（ ）。A. O(n2)B. O(s2)C. O(msn)D. O(mn)6）图的广度优先搜索遍历使用的数据结构是（ ）。A.栈B.队列C.集合D.树7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。A.直接前驱B.直接后继C.开始结点D.终端结点8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）DO(log2n)AO（n2）BO（1）CO（n）9）在链队列中执行入队操作，（ ）。A.需判断队是否为空C.需判断队是否为满B .限定在链表头p进行D.限定在链表尾p进行10）对序列（95，83，62，70）进行冒泡排序（由小到大），第 2 趟排序后的结果为（ ）。A.（70，83，62，95）B.（70，62，83，95）C(62，70，83，95)D(83，62，70，95)(11)下列选项中与数据的存储结构无关的术语是( )。A.栈B.链队列C.顺序表D.链表(12) 已知循环队列的存贮空间大小为m,对头指针front指向对头元素，对尾指针rear 指向对尾元素的下一个位置，则向对列中插入新元素时，修改指针的操作是( )。A. rear=( rear-1)mB. rear=( rear+1 )mC. front=( front-1 )mD. front=( front+1)m(13) 对于广义表 A,若 head(A) =tail(A),则 A 为()。A. ( )B. ( )C. ( ),( )D. ( ),( ),( )(14) 若一棵具有 n 个结点的二叉树的先序遍历和后序遍历的次序正好相反,则该二叉树 应是( )。A.结点均无左孩子的二叉树B.高度为n的二叉树C.结点均无右孩子的二叉树D.存在度为2的结点的二叉树(15) 平均时间复杂度为O(nlog2n)的稳定排序算法是()。A.快速排序B.堆排序C.归并排序 D.冒泡排序二、填空题(每小题 2分,共20分)(1) 数据结构由数据的逻辑结构、存贮结构和数据的三部分组成。(2) 广义表 A=(a, b, (c, d, (e, f ), G)的长度为。(3) 以数据集25,4,15,5,1为权值构造一棵哈夫曼树，其带权路径长度为。(4) 在高度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是。(5) 若某哈夫曼树有m个叶子结点，则该哈夫曼树共有个结点。(6) 向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行p->next=top和操 作。(7) 在队列中，允许插入的一端称为。(8) 在一棵二叉树中，度为1的结点数是3,度为2的结点数是4,则该二叉树有个 叶子结点。(9) 具有n个顶点的连通无向图，其生成树有条边。(10) 当关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序算法中，运行效率最高的是。三、简答题(任选 5道题，每小题8分，共40分) (1)什么是线性表？通常有哪些存贮方式？其各自的优缺点是什么？(2) 什么是顺序队列的“假溢出”现象？有哪些处理方式？如何判断队满和队空？(3) 什么是二叉树的顺序存储方式？其优缺点有哪些？(4) 图的存储结构有哪些？其各自的优缺点是什么？(5) 静态查找有哪三种方法？各自的查找效率如何？(6) 什么样的图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复 杂度各为多少？他们分别适合于哪种类型的图？四、应用题(每小题 10分，共40分)( 1)已知待排序记录的关键字序列为25,96,11,63,57,78,44，请回答下列问题：(a) 画出堆排序的初始堆(大根堆)；(b) 画出第2次重建堆之后的堆。(2) 已知关键字序列为56,23,41,79,38,62,18，用散列函数 H(key)=key11 将其散列到 散列表HT010中，采用线性探测法处理冲突，请回答下列问题：(a) 画出散列存储后的散列表；(b) 求在等概率下查找成功的平均查找长度。(3) 已知某二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG,请 回答下列问题：(a) 画出此二叉排序树；(b) 若将此二叉排序树看作森林的二叉链表存储，画出对应的森林。(4) 下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三 个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指 针。请回答下列问题：(a) 画出该带权有向图的图形；(b) 从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；(c) 以顶点V1为起点的深度优先遍历的顶点序列及对应的生成树；(d) 由顶点V1到顶点V3的最短路径。(顶点边)(出边表)1V1233429625A2V2336A3V3A4V4230338542A5V5110f618A6V6A五、算法设计题（任选 2题，每小题10分，共20分） （1）假定二叉树结点的存储结构定义如下：typedef struct node char data ；struct node *lchild；struct node *rchild；NODE；试编写C （或Java）语言函数void exchange（NODE *t ），其功能是交换二叉树的各 结点的左右子树（根结点指针为t）。（2）以二叉链表为存储结构，编写按层次顺序（同一层自左至右）遍历二叉树的算法。（3）给定头指针为ha的单链表A,和头指针为hb的递增有序单链表B。试利用表A和 表B的结点，将表A和表B归并为递增有序单链表C,其头指针为hc（允许有相同 的 data 值，表 A、B、C 均带有头结点）。阅读下面的函数merge（），请给有下划线的位置填空，使之成为完整的算法（程序）。 表结点的类型定义如下：struct node int data;struct node *next; ;C 语言算法如下：void merge（struct node *ha, struct node *hb, struct node *hc）struct node *pc, *qc, *pa, *fa;int search;hc=hb;hb=NULL;pa=ha->next;free（ha）;while（pa）pc=hc;qc=hc->next;search=1; /设置查找标志while（qc&&search）if（pa->datav=qc->data） ;else pc=qc;qc= ;fa=;pa=;fa->next= ; ;