824数据结构与算法设计A

1、共 5共 5页第5页西安科技大学2013 年硕士研究生入学考试试题 A科目编号：824科目名称： 数据结构与算法设计考生须知：1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。4、 试题要随答题纸一起交回。一、单项选择题（每小题 2 分，共 30 分）并归排序的时间复杂度是（。AO(n2)BO(nlog2n)CO(n)DO(log2n)设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（）省时间。A单链表B单循环链表C带尾指针的单循环链表D带头结点的双循环链表散列文件是一种

2、（。A顺序文件B索引文件C链接文件D计算机寻址文件常用于函数调用的数据结构是（。A栈B队列C数组D链表两个矩阵A,Bmssn相乘的时间复杂度是（ 。AO(n2)BO(s2)CO(msn)DO(mn)图的广度优先搜索遍历使用的数据结构是（。A栈B队列C集合D树（ 。A直接前驱B直接后继C开始结点D终端结点在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（。AO(n2)BO(1)CO(n)DO(log2n)在链队列中执行入队操作（ 。A需判断队是否为空B限定在链表头p进行C需判断队是否为满D限定在链表尾p进行对序进行冒泡排（由小到大第2趟排序后的结果（ A（7，8，6，9）B768

3、，9）C6270839）D8367095）下列选项中与数据的存储结构无关的术语是（。A栈B链队列C顺序表D链表已知循环队列的存贮空间大小为对头指针front指向对头元素，对尾指针rear 指向对尾元素的下一个位置，则向对列中插入新元素时，修改指针的操作是（ 。Arear=（rear-1）mBrear=（rear+1）mCfront=（front-1）mDfront=（front+1）mAhead(A)=tail(A)A为（。A()B()C(),()D( ),( ),()n 应是（。A结点均无左孩子的二叉树B高度为 n 的二叉树 C结点均无右孩子的二叉树D存在度为2的结点的二叉的稳定排序算法是（

4、。A快速排序B堆排序C归并排序D冒泡排序二、填空题（每小题 2 分，共 20 分）数据结构由数据的逻辑结构、存贮结构和数据的三部分组成。广义表A=(a,b,(c,d,(e,f),的长度为。以数据25,4,15,5,1为权值构造一棵哈夫曼树，其带权路径长度为。在高度为h 的具有 n 个结点的二叉排序树中，查找任一结点的最多比较次是。若某哈夫曼树有m 个叶子结点，则该哈夫曼树共有个结点。向一个栈顶指针为top的链栈中插入一个新结*p时应执行p-next=top和作。在队列中，允许插入的一端称为。在一棵二叉树中度为1的结点数是3度为2的结点数是则该二叉树有叶子结点。具有n 个顶点的连通无向图，其生成

5、树有条边。当关键字序列基本有序时快速排序简单选择排序和直接插入排序三种排序算 中，运行效率最高的是。三、简答题（任选 5 道题，每小题 8 分，共 40 分）什么是线性表？通常有哪些存贮方式？其各自的优缺点是什么？什么是顺序队列的“假溢出”现象？有哪些处理方式？如何判断队满和队空？什么是二叉树的顺序存储方式？其优缺点有哪些？图的存储结构有哪些？其各自的优缺点是什么？静态查找有哪三种方法？各自的查找效率如何？什么样的图其最小生成树是唯一的？用PrimKruskal杂度各为多少？他们分别适合于哪种类型的图？四、应用题（每小题 10 分，共 40 分）（1）25,96,11,63,57,78,44，

6、请回答下列问题：画出堆排序的初始堆（大根堆；2次重建堆之后的堆。（2）56,23,41,79,38,62,18H(key)=key11 HT010中，采用线性探测法处理冲突，请回答下列问题：画出散列存储后的散列表；求在等概率下查找成功的平均查找长度。已知某二叉排序树（结点值大小按字母顺序）的前序遍历序列为 EBACDFHG回答下列问题：画出此二叉排序树；若将此二叉排序树看作森林的二叉链表存储，画出对应的森林。针。请回答下列问题：画出该带权有向图的图形；V1 为起点的广度优先遍历的顶点序列及对应的生成树；V1 为起点的深度优先遍历的顶点序列及对应的生成树；V1V3的最短路径。V1V2233V1V

7、2233429625336V612（出边表）3V34 V42303385425 V51106186五、算法设计题（任选 2 题，每小题 10 分，共 20 分）假定二叉树结点的存储结构定义如下：typedefstructnodechardata；structnode*lchild； structnodeNODE；试编写或Java）语言函数voidexchange(NODE *t 其功能是交换二叉树的结点的左右子树（根结点指针为。以二叉链表为存储结构，编写按层次顺序（同一层自左至右）遍历二叉树的算法。haAhbA和B的结点，将表A B C，其头指针为dataABC均带有头结点。阅读下面的函数merg（程序表结点的类型定义如下：struct node int data;struct node *next; ;C 语言算法如下：void merge(struct node *ha, struct node *hb, struct node *hc)structnode*pc,*qc,*pa,intsearch;hc=hb; hb=NULL;pa=ha-nex