发布时间 : 星期日 文章数据结构模拟试卷2更新完毕开始阅读60c5207e168884868762d6e6
一 选择题（前10题，每题1分，后10题，每题2分，共30分）
1、数据结构有________________种基本逻辑结构。
A、1 B、2 C、3 D、4
2、一个存储结点存放一个________________。
A、数据项 B、数据元素 C、数据结构 D、数据类型 3、下列算法的时间复杂度是________________。
For(I=0;I A、O(1) B、O(n) C、O(log2n) D、O(n2) 4、在单链表的一个结点中有_______________个指针。 A．1 B．2 C．0 D．3 5．算法指的是（ ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 6、4个元素按A、B、C、D顺序连续进续进S栈，进行Pop(S,x)运算后，X的值是___________。 A、A B、B C、C D、D 7、栈是一个___________线性表结构。 A、不加限制的 B、加了限制的 C、推广 D、非 8．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 9.n 个权构成一棵Huffman树，其节点总数为________________ A、2n-1 B、2n C、2n+1 D、不确定 10.由N个顶点组成的无向图，最多可以有_________条边。 A、N*N B、N（N+1）/2 C、N（N-1） D、N(N-1)/2 11、顺序栈是空栈的条件是___________。 A、top==0 B、top==q C、top== -1 D、top==m 12、当循环队列SQ是队列时，存放队列元素的数组data有N个元素，则DATA中存放___________个队列元素。 A、n B、n-1 C、n-2 D、0 14、设二叉树有n个结点，则其深度为________. A、n-1 B、n C、[log2n]+1 D、无法确定 15．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．7 16．设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（ ）。 A．3,2,5,6,4,1 B．1,5,4,6,2,3 C．2,4,3,5,1,6 D．4,5,3,6,2,1 17．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断队满的条件为（ ）。 A．front== rear B．(rear+1)%MAXSIZE==front C．front-rear==1 D．rear%MAXSIZE==front 18．设一棵二叉树共有20个度为2的结点，则叶子结点共有（ ）个。 A．40 B．19 C．20 D．21 19．设单链表中指针p指向结点A，若要删除A后的结点且该结点存在，则需要修改指针的操作为（ ）。 A．p->next=p->next->next B．p=p->next C．p=p->next->next D．p->next=p 20、树转换成二叉树后，以下结论正确的是___________. A、树的先根遍历序列与其对应的二叉树的先充历序列相同 B、树的先根遍历序列与其对应的二叉树的中历序列相同 C、树的先根遍历序列与其对应的二叉树的后历序列相同 D、以上都不对 二 填空题（每题2分，共20分） 1、线性表的存储结构有顺序存储和_______________存储两种。 2．在串S=\中，以t为首字符的子串有 个。 3.栈的修改是按__________的原则进行。 4.下列程序段的时间复杂度为_________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; 5.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是_________。 6.一个具有n个顶点的无向图的边数最多为_________。 7.队列的插入操作在队列的___________部分进行。 8.在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是___________。 9.在单链表中某结点后插入一个新结点，需要修改_______________个结点指针域的值。 10．设n>0，且有如下程序段： int i; i = n; while (i>0) i=i/10; 则该程序的时间复杂性为___________________。 三 分析题（前两题8分，后两题12分，共40分） 1、根据二叉树遍历构造二叉树（8分） 已知一棵二叉树的中序遍历结果为DBHEAFICG，前序遍历结果为ABDEHCFIG，画出该二叉树并给出其后序遍历结果。 2、Huffman树构造（8分） 已知叶结点权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。 3、图的邻接矩阵和广度、深度优先遍历 （12分） 已知无向图如下图所示， （1）给出图的邻接矩阵和邻接表。 （2）从1开始，用广度优先算法遍历图中结点。 4、图的最小代价生成树和单源最短路径 （12分） 已知无向图如下图所示 （1）从顶点1开始，使用普里姆算法构造最小代价生成树(需要中间过程)。 （2）以1为源点，使用迪杰斯特拉算法求个点最短路径（需要中间过程） V28V14V5796V42V621232V3 编写算法，将一个单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1,an, 四、程序设计（10分） 则逆序链接后变为an,an-1,……，a1。