树据结构模拟试卷3套期末考试卷试题带答案

试卷一一、选择题（本题共30分,每题2分）1.计算机识别、存储和加工处理的对象被统称为________。A.数据B.数据元素C.数据结构D.数据类型2.已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。A．1234 B．4321C．2143 D．41233.链表不具有的特点是________。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比4.设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。A．110B．108C．100D．1207.在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。A.n-iB.n-i+1C.n-i-1D.i8．下面关于线性表的叙述错误的是________。 A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现9.Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构________。A．顺序查找B．分块查找C．二分查找D．散列查找11.下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。快速排序B.希尔排序C.堆排序D.冒泡排序12.设一棵二叉树的深度为k，则该二叉树中最多有________个结点。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四个选项中，能构成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边________。A．n(n-1)/2B．n-1C．nD．n+115.栈和队列的共同特点是________。A.都是操作受限的线性表B.都是先进后出C.都是后进先出D.无共同点二、填空题（本题共10分，每空1分）若经常需要对线性表进行查找操作，则最好采用________存储结构。某带头结点单链表的头指针为L，判定该单链表非空的条件________________。数据的逻辑结构包括集合、________、________和图状结构四种类型。图的两种遍历方式为：广度优先遍历和_______________。线性表的链式存储结构中的结点包含________域和________域。向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、应用题（本题共40分）1．设散列表长度为11，散列函数h(key)=key%11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2．有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3．已知图G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）（1）直接插入排序（2）基数排序5．对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分）6.将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）AABCDEFGH四、算法题（本题共20分）1．完成中序遍历二叉树。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.编写算法实现直接插入排序。（8分）参考答案一、选择题（本题共30分,每题2分）123456789101112131415ADABCBBDACBDCBA二、填空题（本题共10分，每空1分）1）顺序2）L->next!=NULL3）线性结构树形结构4）深度优先遍历5）数据指针6）左子树7）s->top++s->stack[s->top]=x三、应用题（本题共40分）1、（6分）H(1)=1H(13)=2H(12)=1冲突，H1=2冲突，H2=3H(34)=1冲突，H1=2冲突，H2=3冲突，H3=4H(38)=5H(33)=0H(2)=2冲突，H1=3冲突，H2=4冲突，H3=5冲突，H4=6H(22)=0冲突，H1=1冲突，H2=2冲突，H3=3冲突，H4=4冲突，H5=5冲突，H6=6冲突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、图的邻接矩阵：（3分）广度优先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC层序遍历序列:ABECFDGH四、算法题（本题共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}试卷二一、选择题（本题共20分,每题2分）1.下面程序段的时间复杂度为（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;A.O(n)B.O(n2)C.O(2*n)D.O（i*j）2.线性表采用链式存储时，结点的存储地址（）。A．必须是不连续的B．部分地址必须是连续的C．连续与否均可D．和头结点的存储地址相连续3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（）。A．3，2，1B．1，2，3C．3，1，2D．2，1，34.下面说法不正确的是()A．串S1=“this_is_a_string”的长度是16。B．串S2=“this”是串S1的子串。C．串S3=“thisis”在串S1中的位置是1。D．串S4=“a”在串S1中的位置是9。5.一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子6.完全二叉树()满二叉树A．不一定是B．一定不是C．一定是D．不能确定关系7.用链表表示线性表的优点是（）便于随机存取便于插入和删除操作花费的存储空间较顺序存储少元素的物理顺序与逻辑顺序相同8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边()。A．n(n-1)/2B．n-1C．nD．n+19.下列查找方法中哪一种不适合元素的链式存储结构()A．顺序查找B．分块查找C．二分查找D．散列查找10.下面哪种排序方法稳定性最好()。A．希尔排序B．冒泡排序C．快速排序D．堆排序二、填空题（本题共20分）1.数据的逻辑结构可以分为两大类：_________和________。2.在二叉树的第i层上最多有___________个结点。3.无向图中恰好有__________条边，才称为无向完全图。4.用单链表方式存储的线性表，存储每个结点需要有两个域，一个是_________，另一个是________。5.设二维数组A5×6的每个元素占4个字节，已知LOC（a00）=1000，则A一共占用_______字节。如果按行优先存储时，a25的起始地址是_________。6.3个结点的树有_______种形态，3个结点的二叉树有________种形态。7.一个广义表为（a，（a，b），d，e，（（i，j），k）），则该广义表的深度为________。8.栈的插入操作在_______进行，删除操作在_______进行。9.在二叉树中，结点的最大度数是_______。10.判定一个有向图中是否存在回路，即是否含有环，可以使用_________方法。11.二分查找的效率较高，但是要求查找表中的关键字_______，并且要求表的存储为________。12.在构造散列表的过程中，不可避免会出现冲突，通常解决它的方法有_______和_______。13．从任何一个结点开始都能成功查找其他结点的单链表是表。三、应用题（本题共50分，每题10分）1.一棵二叉树如右面的图所示，要求：（1）写出对此二叉树进行中序遍历时得到的结点序列。（2）画出由此二叉树转换得到的森林。2.已知图G的邻接表如下，写出从顶点O出发的深度优先和广度优先遍历的顶点序列。0021310022030130203.对于下面所示的连通图，写出由Prim算法生成的最小生成树。4.下图所示为AOE网，求其关键路径和关键活动。四、算法填空题（本题共10分）下列两个算法分别为二分查找算法和冒泡排序算法，阅读下面程序代码，填充空白位置，使算法完整。#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;typedefNodeTypeSeqList[n+1];1.intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)______1_____;else________2_______;}return0;}2.voidBubbleSort(SeqListR){inti,jBooleanexchange;For(i=1;i<n;i++){exchange=false;for(j=1;j<=n-I;j++)if(R[j+1].key<R[j].key){_______3_____;______4______;R[j]=R[0];________5__________}if(!exchange)return;}}参考答案一、选择题（本题共20分,每题2分）12345678910BCCCDAbBCB二、填空题（本题共20分,每空1分）1）线性结构，非线性结构2）2i-13）n(n-1)/24）数据域，指针域5）1120，10686）2，57）58）栈顶，栈顶9）210）拓扑排序11）有序，顺序存储12）开放定址法，拉链法13）单循环链表三、应用题（本题共50分）1）DEFBAC--------8分―――――――8分2）深度优先遍历：0231―――――6分广度优先遍历：0213――――6分3）--------12分4）顶点vevl活动ell-eV100a1011V234a2000V322a3341V466a4341V567a5220V688a6253a7660a8671---------6分关键路径是：V1-V3-V4-V6---------2分关键活动是：a2,a5,a7---------2分四、算法填空题（本题共10分,每空2分）1）high=mid-1;---------2分2）low=mid+1;---------2分3）R[0]=R[j+1];---------2分4）R[j+1]=R[j];---------2分5）exchange=true;---------2分试卷三一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法 B.S的存储结构C.在S上的一个基本运算集 D.在S上的所有数据元素2．下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算3．稀疏矩阵一般采用（）方法压缩存储。A.三维数组 B.单链表C.三元组表 D.散列表4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行()。A.s↑.next:=p；p↑.next=s;B.s↑.next:=p↑.next;p↑.next:=s；C.s↑.next:=p↑.next;p:=s;D.p↑.next:=s;s↑.next=p;5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是()。A.110B.108C.100D.1206.下面的二叉树中，()不是完全二叉树。7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为()。A.78、47、61、33、39、80B.80、78、61、33、39、47C.80、78、61、47、39、33D.80、61、78、39、47、338.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是()A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;D.以上都不对9.由下列三棵树组成转的森林换成一棵二叉树为()10.for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为（）A.O（m+n×t） B.O（m+n+t）C.O（m×n×t） D.O（m×t+n）11.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］12.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（）A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段p=h;while(p->next->next!=h)p=p->next;p->next=h;后（其中，p->next为p指向结点的指针域），则()A.p->next指针指向链尾结点 B.h指向链尾结点C.删除链尾前面的结点 D.删除链尾结点15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是()A.高度等于其结点数 B.任一结点无左孩子C.任一结点无右孩子 D.空或只有一个结点二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。17．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。18．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的关系。19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____________。20.数据表示和________________是程序设计者所要考虑的两项基本任务。21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_________。22.深度为k的二叉树至多有_________个结点，最少有_________个结点。23．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用。24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。26.三个结点可构成________种不同形态的二叉树。27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。三、应用题（本大题共5小题，每小题6分，共30分）29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。30．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。ABCDEFG32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。33.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。四、算法设计题(本大题共3小题，共14分)34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）35.某带头结点的单链表的结点结构说明如下：（6分）typedefstructnode1{intdata;structnode1*next}node；试设计一个算法intcopy(node*head1,node*head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4分）参考答案一、选择题（本题共30分,每题2分）1、C2、B3、C4、B5、B6、C7、B8、C9、A10、C11、B12、D13、C14、D15、A二、填空题（本题共26分,每小题2分）16、树状结构17、n-118、逻辑19、n/220、数据处理21、front==(rear+1)%n22、2k-1，k23、堆排序24、中序25、有序26、527、冒泡排序28、n-1三、应用题（本题共30分，每小题6分）29、ABABCDGFEFE30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);ACACDEFG第1趟：[37]38[735240645643]第2趟：3738[4352406456]73第3趟：3738[40]43[526456]73第4趟：3738404352[6456]73第5趟：37