数据结构与算法(软件)课程样

样卷一一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题1分，共15分。)用链表表示线性表的优点是()便于随机存取便于插入与删除子串是()。串中一些字符构成的序列C.串中一个以上连续字符组成的序列花费的存储空间比顺序表少数据元素的物理顺序与逻辑顺序相同B•串中若干个连续字母构成的序列D.串中任意个连续字符组成的序列(rear+1)%maxSize=frontrear=front(rear+1)%maxSize=frontrear=front)C.-1D.2在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的TOC\o"1-5"\h\z最大长度，队满的条件是( )。A.front=maxSize B.rear=maxSize D.树中所有结点的度等于所有结点数加(A.0 B.1执行下面程序段时，执行S语句的次数为()I=1;I<=n;I++)j=1;j<=I;j++)for(intfor(intS;A.n26.串是A.可以顺序存储C.可以链接存储B. n2/2 C.n(n+1)种特殊的线性表，其特殊性体现在()B.数据元素是D.数据元素可以是多个字符D.n(n+1)/2个字符一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的TOC\o"1-5"\h\z结点有( )个A.33 B.34 C.32 D.30若算法中语句频度之和为T(n)=123n+n2/45+6nlogn+7891，则算法的时间复2杂度为 。A.O(1) B.O(n) C.O(nlogn) D.O(n2)2在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为( )。A、top不变 B、top=0 C、top=top-1 D、top=top+1若线性表最常用的操作是存取第i个元素及其前驱的值，则采用()存储方式节省时间。B、 双链表表 D、顺序表在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行()。A、front->next=s； front=s； B、s->next=rear; rear=s；C、rear->next=s; rear=s； D、s->next=front; front=s；链式栈与顺序栈相比，一个比较明显的优点是()。A.插入操作更加方便 B.通常不会出现栈满的情况C．不会出现栈空的情况 D．删除操作更加方便在一棵完全二叉树中，若编号为i的结点有右孩子，则该结点的右孩子编号为()。A、2i B、2i+1 C、2i-1 D、i/2一个有n个顶点的无向图最多有()条边。A、n B、n(n-1) C、n(n-1)/2 D、2n某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、则其左子树中结点数目为：()A.3 B.2 C.4 D.5二、 判断题(判断下列各题是否正确，若正确，就在()内写“T”，否则写“F。每小题1分，共15分。)( )1.栈与队列都是限制存取点的表，只是它们的存取特征不一样。()2.已知指针P指向键表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。()3.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。()4.无向图的邻接矩阵是对称的，有向图的邻接矩阵也可能是对称的。()5.子串是主串中任意个连续字符组成的序列。()6.树的中序表示和前序表示可以导出树的后序表示。()7.哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。()8.线性表的逻辑顺序与存储顺序总是一致的。()9.通常递归的算法简单、易懂、容易编写，而且执行的效率也高。()10.在完全二叉树中，一个结点若没有左孩子，则它一定没有右孩子。()11.算法可以没有输入，但是必须有输出。()12.深度为K的完全二叉树至少有2K-1个结点。()13.树中结点的度是指从根到该结点所经过分支的条数。()14.快速排序是不稳定排序。()15.线索二叉树是一种逻辑结构。三、 填空题(将下列各题横线上的内容补充完整。每小题1分，共10分。)任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的 。2•算法是指令的有限序列，其中每一条指令表示一个或多个操作，算法的一般性质分别为：通用性、有效性、______和___ __。线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的 也是相邻的。队列的插入操作在 进行，删除操作在 进行。通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的 域的值。数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、 和 。四、简答题(回答要点，并简明扼要作解释。每小题5分，共20分)数据结构中研究的经典结构有那些？各有什么特点？在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题说明在图的遍历中，设置访问标志数组的作用。什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？五、应用题(每小题8分，共32分)1.已知有向图：G=(V,E)V={a,b,c,d,e,f,g}E={<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<c,f>,<d,f>,<e,g>,<f,g>}画出此有向图的邻接表存储结构图示；写出一个拓扑序列；某二叉树的中序遍历序列为ADEBCGFHIJ，后序遍历序列为ADCBGEIHJF；画出该二叉树；写出该二叉树的前序遍历序列。写出用Kruskal算法求右图的最小生成树的完全过程。依次输入表{30,15,28,20,24,10,12,68,35,50,46,55}中的元素，生成一棵二叉搜索树。试画出生成之后的二叉搜索树；对该二叉搜索树进行中序遍历，试写出遍历序列；假定每个元素的查找概率相等，试计算该二叉搜索树的平均查找长度；六、算法分析题(共8分，每小题分标在小题后)阅读下面程序，并回答有关问题。其中BiTree为二叉链表类型，并假设二叉树root有n个结点。简要说明程序功能(4分)总共执行了多少次出栈操作(2分)给出算法的时间复杂度(2分)voidProc(BiTreeroot){InitStack(&S);if(!root)r