山西大学张献文数据结构模拟题

1、学而不思则惘，思而不学则殆数据结构模拟试题2014_1参考答案一、单项选择题(2分X 10=20分)1. 数据逻辑结构 B可以表示为：B= ( K,R )，其中K表示(：C)的有限集，R是K上的(：A ) 的有限集。 ：A.逻辑结构B.算法C数据元素D.数据操作 ：A.关系B.操作 C.存储 D.映像2. 在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行( A )操作与链表的长度有关。A. 删除单链表中的最后个元素B. 在单链表第一个元素前插入一个新元素C. 删除单链表中的第一个元素D. 在单链表最后一个元素后插入一个新元素3某线性表最常用的操作是，在最后一个结点之后插入一个

2、结点，或删除第一个结点，故采用(D )存储方式最节省运算时间。A.单链表B.仅有头结点的单循环链表C.双向链表D.仅有尾指针的单循环链表4. 一个栈的进栈序列为A,B,C,D,E.则栈的不可能的输出序列是( D )。A . ABCDE B. DECBAC. EDCBA D . DCEAB5. 设有两个字符串p和q，求q在p中首次出现的位置的运算称作(B )。A.串连接B.串的模式匹配C.求子串D.串查找6采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为(C )。A. nB. n/2C. (n+1)/2D. (n -1)/27.个有n个顶点的无向图最多有(A )条边。A. n(n-

3、1)/2B. n(n-1)C. nD. 2n&在线索二叉树中，结点没有左子树的充要条件是结点满足(B )。A. left=NULLB. ltag=1C. (ltag=1)&&(left=NULL)D.以上都不对9. 按二叉数的定义，具有A、B、C 3个不同结点的二叉数有( D )种。A. 5 B. 6 C. 15 D. 3010. 采用直接选择法对数组An进行排序，元素移动的次数与比较的次数分别是(C )。2A.O(n)， O(log2n)B. O(n )， O(log 2n)2C. O(n)， O(n )D. O(n)， O(nlog2n)二、填空题(单项选择题(2分

4、X 10=20分)1. 求下面程序段的时间复杂度T(n):(1) void func1(int n)int i=1,k=0;while(i<=n-1)k+=10*i;i+; 时间复杂度是(O( n)。(2) void func2(int n)int x= n,y=0; while(x>=(y+1)*(y+1)y+; 时间复杂度是(0、n )。2顺序表中逻辑上相邻的数据元素的物理位置(也一定)紧邻；单链表中逻辑上相邻的数据元素的物 理位置(不一定)紧邻。对于栈队头）。3 线性表、栈和队列都是（线性）结构，可以在线性表的（任一）位置插入和删除数据元素； 只能在（栈顶）位置插入和删除数据

5、元素；对于队列只能在（队尾）位置插入数据元素和在（位置删除元素。4空串和空格串的主要区别是（前者不含任何字符其长度为零，后者含有空格符长度不为零5. 已知模式串 T= ”ABAABACA ”其 next（优化前）数组为（-1,0,0,1,1,2,0,1）。6. 已知一个图如图1所示，若从顶点a出发按字母排列顺序搜索，则深度优 先遍历序列为（a,b,e,d,f,c）;广度优先遍历序列为（a,b,c,e,f,d）。7. 已知一棵树的边的集合表示为：E2.6 一牛无向图<C,G>,<A,B>,<A,C>,<A,E>,<D,F>,<D,

6、A>该树的根结点是（D），叶结点有（G,B,E,F），树的深度是（3），树的度是（4）。&先序序列和中序序列相同的二叉树的特点是（二叉树中所有的结点均无左孩子）；中序序列和后序序列相同的二叉树的特点是（二叉树中所有的结点均无右孩子）；先序序列和后序序列相同的二叉树的特点是（该二叉树为空树或只有根结点）。9. 一组记录的关键字为：66，46，79，56，38，40，74则利用希尔排序的方法，以间隔数d=n/2得到的一轮排序结果为：（56，38，40，66，46，79，74）。10. 在堆排序和快速排序法中，如果原始记录接近正序或反序，则选用（堆）排序法；如果原始记 录无序则选用（快

7、速）排序法。三、程序阅读题（5分X 2=10分）1. 已知L是带头结点的非空单链表，P为L中的结点，P既不是首元结点也不是尾元结点，试从下面 提供的语句序列说明其功能。Q=P;P=L;while（P-> next!=Q）P=P-> next;P-> next=Q-> next;delete Q;以上语句序列的功能是（ 删除P结点）。2. 简述以下算法的功能。void FuncB（Queue &Q）/队列Q中的数据元素类型为int. Stack S; ind d;In itStack（S）;While（!QueueEmpty（Q）DeQueue（Q,d）;Push

8、（S,d）;While（!StackEmpty（S） Pop（S,d）;E nQueue（Q,d）;该算法的功能是（将队列Q中的数据元素进行逆序排列）。四、解答题（10分X 5=50分）的功能是用起泡排序法对数组A中的n个整数排序，试写出该函1.函数 void BubbleSort(int A,int n) 数的完整代码。void BubbleSort(int A,int n) int i,j,t,f;/f=i时表示发生了交换操作for(f=1, i=n-1;i>0&& f;i-)for(f=0,j=0;j<i;j+)if(Aj>Aj+1)/如果产生逆序f=1

9、;t=Aj;Aj=Aj+1;Aj+1=t;/交换Aj与Aj+1的值2.函数int IndexBF(SString S,SString T)的功能是通过 BF算法返回模式串 T在主串S中首次出现的位 置，如果匹配不成功返回0值。给出该算法的完整程序代码。int IndexBF(SString S,SString T,int& num) int i=0,j=0;if(Le ngth_SS(T)>Le ngth_SS(S) while(Si+j&& Tj)if(Si+j=Tj)j+; elsei+; j=0;if(!Tj)return(i+1);elsereturn(0

10、);3.已知二叉树的中序遍历序列为 要求：(1)画出这棵二叉树；(3)中序线索化该二叉树；return(0);/若字符相等，则继续比较后续字符若不相等，则重新开始新一轮比较若匹配成功，则返回 T首次出现的开始位置/若匹配不成功，则返回 0CBEDAHGIJF，后序遍历序列为 CEDBHJIGFA。(2)写出该二叉树的先序遍历序列；解：(1)这棵二叉树如图 2所示:C图二賈树C赛)中序燼索二夏树-(4)该二叉树所表示的森林如图 4所示:(4)画出该二叉树所表示的森林。(2)该该二叉树的先序遍历序列为:ABCDEFGHIJ(3) 中序线索化该二叉树如图 3所示:4.假定用于通信的电文由7个字母A、

11、B、C、D、E、F、G组成，各字母在电文中出现的次数分别为：4、5、6、7、10、12、18。要求：（1）以使用次数作为结点的权值构造一棵Hufman树；（2）根据你构造的 Huffman树，给出 A、B、C、D、E、F、G的Huffman编码；（3）计算该Hufman树的带权路经长度。解:（1）构造的Hufman树如图5所示;（2）根据所得的 Huffman 编码为：A: 1100，B: 1101，C： 010，D: 011，E： 111，F: 00，G： 10。(3)该 Hufman 树的带权路经长度为：WPL=(4+5)*4+(6+7+10)*3+(12+18)*2=165。（图5）一棵喑夫号树5对于图4.5中所示的无向图，试回答：（1 ）每个顶点的度是多少？（2）按顶点序列1、2、3、4、5、6分别给出该图的邻接矩阵和邻接表表示。（3）给出从顶点1开始按（2）中的邻接表顺序进行深度优先遍历的顶点序列。（4）给出从顶点1开始按（2）中的邻接表顺序进行广度优先遍历的顶点序列。解：各个顶点的度、邻接矩阵、邻接表、深度优