2008数据结构试卷

《2008数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海交通大学试卷（A卷）（2008至2009学年第一学期）一、选择题（请选择最佳答案，每题2分，共20分）1.计算机算法必须具备这三个特性。A．可执行性、可移植性、可扩充性B．可行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性2.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是：。A．e,d,c,b,aB．d,e,c,b,aC．d,c,e,a,bD．a,b,c,d,e3.一个队列的入队序列是1,2,3,4，则队列的输出序列是：。A．4,3,2,1B．1,2,3,4C．1,4,3,2D．3,2,4,14.以下说法错误的是。A．一般在哈夫

2、曼树中，权值越大的叶子离根结点越近B．哈夫曼树中没有度数为1的分支结点C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5.某二叉树的前序遍历和后序遍历正好相反，则该二叉树一定是的二叉树。A．空或只有一个结点B．任一结点至多只有一个儿子C．任一结点无左儿子D．任一结点无右儿子6.下列说法中错误的是_____。A．n个结点的树的各结点度数之和为n-1B．n个结点的无向图最多有n*(n-1)条边C．用邻接矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关D．散列表中发生冲突

3、的可能性大小与负载系数有关7.下面关于图的存储的叙述中，_____是正确的。A．用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关B．用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关41.四组含C1～C7的结点序列中，______是下列有向图的拓扑排序序列。C6C5C4C3C1C2C7A．C1,C2,C6,C7,C5,C4,C3B．C1,C2,C6,C3,C4,C5,C7C．C4,C1,C

4、2,C3,C5,C6,C7D．C5,C7,C4,C1,C2,C6,C32.一组记录的关键字序列为（43,76,53,35,37,81），为排成非递减序利用堆排序的方法建立的初始的堆为。A．（76,43,53,35,37,81） B．（81,76,53,43,37,35）C．（81,76,53,35,37,43） D．（81,53,76,37,43,35）3.要确定关键字序列中第k个最小的元素，下列方法中最好的是。A．插入排序     B．快速排序    C．选择排序     D．合并排序二、填充题（每格2分，共20分）1.算法分析的两个主要方面是分析算法的。2.向一长度为

5、n的线性表的第i个元素的位置插入一个元素，需要向后移动个元素。3.删除单链表中由p指针指向的结点的下一个结点的操作序列为：4.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：_。5.设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为。41.将两个长度均为n的有序表合并成一个有序表，其最小的比较次数为。2.已知序列{10,78,89,40,28,62,54,23,72,7}，以62为界点进行一趟快速排序后得到的序列是。3.在堆排序、快速排

6、序和合并排序中，从存储空间角度考虑，应首选方法，其次选取方法。三、简答题（每题5分，共10分）1.给定权值7，17，3，32，26，12，8，构造相应的哈夫曼树。2.画出下列网络的最小生成树。1110612975V5V4V3V1V24四、算法题（每题10分，共20分）1.试写出求最短路径Dijkstra算法的基本思想和主要步骤，并写出其时间复杂度。2.试写出简单插入排序算法的基本思想和主要步骤，并分析其时间复杂度。五、程序题（每题15分，共30分）1.已知有两个带头结点的单链表A和B，其头指针分别为heada和headb，试编写程序实现：从单链表A中删除自第i个元素起的共

7、len个元素，然后将它们插入到单链表B的第j个元素之前的。templateclassList;//单链表类的向前说明templateclassListNode{//结点类friendclassList;//单链表类为其友元类，便于访问结点类中的私有成员public:ListNode():Next(NULL){};~ListNode(){};private:ListNode*Next;//指向下一个结点的指针ElemTypeEle