数据结构与算法试卷

安阳工学院数据结构与算法课程试卷学年第二学期安阳工学院数据结构与算法课程试卷学年第二学期___________系_______________专业_____________班级姓名________学号________________座号：__密封线内不要答题———————————密———————————————封———————————————线————————————题号一二三四总分得分阅卷人注：请将所在的院（系）、专业、班级、姓名和学号写在密封线内，不要写在其它地方注：请将所在的院（系）、专业、班级、姓名和学号写在密封线内，不要写在其它地方得分一、填空题（每空2分，共12分）1.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的__数据元素之间的关系______有限集合。2.向一个长度为n的线性表中删除第i个元素(1≤i≤n)时，需向前移动___n-i_____个元素。3.假设以S和X代表进栈和出栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为___bceda_____。4.已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设front和rear的值分别为8和3，则该队列的长度为___16_____。5.在有序表A[0…17]中，采用折半查找法查找关键字等于A[7]的元素，需比较元素的下标依次为83567。6.在堆排序、快速排序和归并排序方法中，稳定的排序方法是归并排序。得分二、单项选择题（每小题2分，共40分）1.数据结构中，与所使用的计算机无关的是数据的（C）结构。A.存储B.物理C.逻辑D.物理和存储2.算法分析的两个主要方面是（A）A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序4．线性表Ｌ在（B）情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂5.经过以下栈运算后，x的值是（A）InitStack(s);Push(s,'a');Push(s,'b');Pop(s,x);GetTop(s,x);A.aB.bC.1D.06.循环队列存储在数组A[0…m]中，则入队时的操作为（D）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)7.按（B）遍历二叉排序树得到的序列是一个有序序列。A.先序B.中序C.后序D.层次8.下面哪一方法可以判断出一个有向图是否有环（回路）（B）.A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径9.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B）结构。A.栈B.队列C.数组D.线性表10．已知关键码序列{78,19,63,30,89,84,55,69,28,83}采用基数排序，第一趟排序后的关键码序列为（B）。A.{19,28,30,55,63,69,78,83,84,89}B.{30,63,83,84,55,28,78,19,69,89}C.{30,63,83,84,55,78,28,19,89,69}D.以上都不正确。11.无向图G=（V,E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是(D).A.abecdfB.acfebdC.aebcfdD.aedfcb12.在一个单链表中，已知p结点，若在p后插入s结点，则须执行（A）A．s->next=p->next;p->next=sB．p->next=s;s->next=pC．p->next=s->next;s->next=pD．s->next=p;p->next=s->next13.一个无向连通图有5个顶点8条边，则生成树将要去掉（B）条边。A.3B.4C.5D.614.设一棵二叉树共有50个叶子结点，则共有（B）个度为2的结点。A.25B.49C.50D.5115.对数据序列{15,9,7,8,20,-1,7,4}，用堆排序的筛选法建立的初始小顶堆为（C）。A.{-1,4,8,9,20,7,15,7}B.{-1,7,15,7,4,8,20,9}C.{-1,4,7,8,20,15,7,9}D.以上都不对16.设数组a[0…59,0…69]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为（A）。A.9072B.6644C.8950D.650217.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左右子结点中保存的关键字分别是（C）A.1348B.2448C.2453D.249018.有向图用邻接矩阵存储，其第i列的所有元素之和等于顶点i的(B)。A.度B.入度C.出度D.以上答案都不对19.建立线索二叉树的目的是（A）A.方便查找某结点的前驱或后继B.方便二叉树的插入和删除操作C．方便查找某结点的双亲D.使二叉树的遍历结果唯一20.如右图所示二叉树是由森林T1转换而来的二叉树，则森林T1中有（D）个度为0的结点。A.4B.5C.6D.7得分三、简答题（每小题4分，共8分）1、简要描述prim算法。2简述拓扑排序算法。得分四、应用题（每小题8分，共40分）1、假定用于通信的电文由8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的频率为：5，25，4，7，9，12，30，8，试画出哈夫曼树并为这8个字母设计哈夫曼编码。2已知某完全二叉树采用顺序存储，结点数据信息的存放顺序是ABCDEFGH,画出该完全二叉树，并写出对该二叉树进行先序遍历、中序遍历及后序遍历得到的结点序列。3、以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。4.设给定关键字输入序列为（100，90，120，