华东交大数据结构自测卷及答案.docx

《华东交大数据结构自测卷及答案.docx》由会员分享，可在线阅读，更多相关《华东交大数据结构自测卷及答案.docx（29页珍藏版）》请在三一办公上搜索。

1、第一章 绪论一、填空题1. 算法的计算量的大小称为计算的（ B ）。 A效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ C）A问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（C），它必须具备（B） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结

2、构5以下与数据的存储结构无关的术语是（ D ）。A循环队列 B. 链表 C. 哈希表 D. 栈6以下数据结构中，哪一个不是线性结构（ B ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串7以下那一个术语与数据的存储结构无关？（ A ）A栈 B. 哈希表 C. 线索树 D. 双向链表8在下面的程序段中，对x的赋值语句的频度为（ C ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 9程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THE

3、N Aj与Aj+1对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（ D ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 10以下哪个数据结构不是多型数据类型（D ）A栈 B广义表 C有向图 D字符串11以下数据结构中，（ A ）是非线性数据结构A树 B字符串 C队 D栈12. 下列数据中，（ C ）是非线性数据结构。A栈 B. 队列 C. 完全二叉树 D. 堆13连续存储设计时，存储单元的地址（ A ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续14以下属于逻辑结构的是（ C ）。A顺序表 B. 哈希表 C.有序表 D. 单链表二、

4、判断题1. 数据元素是数据的最小单位。( F )2. 记录是数据处理的最小单位。 ( T ) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( F )4算法的优劣与算法描述语言无关，但与所用计算机有关。( F )5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( T )6算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( T ) 7程序一定是算法。( T ) 8数据的物理结构是指数据在计算机内的实际存储形式。( T ) 9. 数据结构的抽象操作的定义与具体实现有关。( F ) 10. 在顺序存储结构中，有时也存储数据结构中元素之

5、间的关系。( F )11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( F )12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( T )13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( F )三、填空1数据的物理结构包括 数据元素 的表示和 数据关系 的表示。2. 对于给定的n个元素,可以构造出的逻辑结构有 集合 ， 线性 ， 树 ，_图（网）_四种。3数据的逻辑结构是指 数据元素之间的逻辑关系。4一个数据结构在计算机中 表示 称为存储结构。5抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_其在计算机内部如何

6、表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。6数据结构中评价算法的两个重要指标是 时间复杂度和空间复杂度 7. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作_，设计出相应的算法_。8 一个算法具有5个特性: 有穷性 、 确定性、 可行性 ，有零个或多个输入、有一个或多个输出。9已知如下程序段for(i=n;i=1;i- ) 语句1x=x+1； 语句2for(j=n;ji;j-) 语句3 y=y+1; 语句4；语句1执行的频度为 n+1 ；语句2执行的频度为 n ；语句3执行的频度为n（n+1

7、）/2 ；语句4执行的频度为 (n-1)n/2 。10在下面的程序段中，对的赋值语句的频度为(n3+3n2+2n)/6_（表示为n的函数） for(i=1;i=n;i+)for(j=1;j=i;j+) for(k=1;k=j;k+)：delta；11.下面程序段中带下划线的语句的执行次数的数量级是： log2n i=1;while(in)i=i*2;12. 下面程序段中带下划线的语句的执行次数的数量级是( nlog2n )。i=1;while(in)for(j=1;j=n;j+)x=x+1;i=i*213. 下面程序段中带有下划线的语句的执行次数的数量级是(log2n ) i=n*n whil

8、e(i!=1)i=i/2;14. 计算机执行下面的语句时，语句s的执行次数为 _(n+3)(n-2)/2_ 。 for(i=l；i=i;j-) s; 15. 下面程序段的时间复杂度为_n1/2_。(n1) sum=1； for (i=0;sumn;i+) sum+=i; 四、应用题1、有如下几种用二元组表示的数据结构，画出它们分别对应的逻辑图表示形式，并指出它们分别属于何种结构。（注意：表示有方向，（）表示无方向）（1）、A=（K，R）， 其中：K=a,b,c,d,e,f,g,h R=r r=,（2）、B=（K，R），其中：K=a,b,c,d,e,f,g,h R=r r=，,（3）、C=(K,

9、R),其中:K=1,2,3,4,5,6,R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)线性表、栈和队列测试题姓名 班级 学号 一、 选择题（共25分）（ B ）1、下面关于线性表的叙述中，错误的是哪一个？ A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。（ A ）2、 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带

10、头结点的双循环链表 D单循环链表（ C ）3、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=inext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;（ B ）5、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）A head=NULL Bhead-next=NULLChead-next=head Dhead-NULL（ B ）6. 栈中元素的进出原则是 A先进先出 B.后进先出 C 栈

11、空则进 D 栈满则出（ C ）7. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 i n=i n-i+1 不确定 （ B ）8. 判定一个栈ST（最多元素为m0）为空的条件是 ST-top0 ST-top=0 ST-topm0 ST-top=m0（ A ）9. 判定一个队列QU（最多元素为m0）为满队列的条件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ D ）10数组用来表示一个循环队列，为当前队列

12、头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n11. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 ，第二次出栈得到的元素是 ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 ，第二次出队得到的元素是 。经操作后，最后

13、在栈中或队中的元素还有 个。供选择的答案： AD：a1 a2 a3 a4 E： 1 2 3 0答：A、B、C、D、E分别为 、 、 、 、 12. 栈是一种线性表，它的特点是 A 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1

14、 减1 不变 清0 加2 减2D： a,b b,c c,a b,a c,b a,cE： n+1 n+2 n n-1 n-2答：A、B、C、D、E分别为 、 、 、 、 13. 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。供选择的答案：A，B：空 满 上溢 下溢C： n-1 n n+1 n/2D： 长度 深度 栈顶 栈底E：两个栈的栈顶同时到

15、达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答：A、B、C、D、E分别为 、 、 、 、 二、 判断题（共10分）（ F ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ F ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （ T ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ T ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ F ）5. 栈和链表是两种不同的数据结构。 （ F ）

16、6. 栈和队列是一种非线性数据结构。 （ T ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ T ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ F ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ F ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。三、 填空题（共20分）1. 线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队头 删除元素。2. 栈是

17、一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4. 在一个循环队列中，队首指针指向队首元素的 当前 位置。5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。6. 向栈中压入元素的操作是先 插入数据 ，后 移动指针 。7. 从循环队列中删除一个元素时，其操作是 先 读取元素 ，后 移动指针 。8. 带表头结点的空循环双向链表的长度等于 0 。9表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是_23 12 3 * 2-4/ 34

18、 5*7/+ 108 9/+_ _10已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a. 在P结点后插入S结点的语句序列是：(4)( 1) 。b. 在P结点前插入S结点的语句序列是：7 11 8 4 1 。c. 在表首插入S结点的语句序列是：5 12 。d. 在表尾插入S结点的语句序列是：9 1 6 。供选择的语句有：（1）P-next=S;（2）P-next= P-next-next;（3）P-next= S-next;（4）S-next= P-next;（5）S-next= L;（6）S-next= NULL;（7）Q= P;

19、（8）while(P-next!=Q) P=P-next;（9）while(P-next!=NULL) P=P-next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;四、 简答题(共15分)1、 说明线性表、栈与队的异同点。2、 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？3、 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？五、 算法设计（共30分）1、 写一算法，从顺序表中删除自第i个元素开始的k个元素。

20、Status Delete_k(Sqlist L,int i,int k) if(iL.length|i+kL.length)return error; for(int j=i+k;jL.length;j+) L.elemj-k=L.elemj; L.length-=k; return OK;2、 试写一个算法，判别读入的一个以为结束符的字符序列是否是“回文”。（ 正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是回文。） Status HuiWen(char s)int i=0;SqStack S;InitStack(S);while(s

21、i!=)Push(S,si);coutpushsi;i+;i=0;while(si!=)char e;Pop(S,e);coute*next-next!=s) /查找s的前一个结点的前一个结点； p=p-next;q=p-next;p-next=s;delete q;return OK;第6章 树和图 自测卷 姓名 班级 学号 题号一二三四五总分题分1017174016100得分一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（ ）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（ ）2.二叉树中每个结点的两棵子树的高度差等于1。 （ ）3.二叉

22、树中每个结点的两棵子树是有序的。 （ ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ ）5. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ ）6. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。（ ）7. 具有12个结点的完全二叉树有5个度为2的结点。（ ）8. 不同的求最小生成树的方法最后得到的生成树是相同的. （ ）9. 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。 （ ）10. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。二、填空（每空1分，共17分）1 由个结点所构成

23、的二叉树有 种形态。 2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。3 一棵具有257个结点的完全二叉树，它的深度为 。4 设一棵完全二叉树有700个结点，则共有 个叶子结点。5. 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。6. 判断一个无向图是一棵树的条件是_。7. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_条弧。8. G是一个非连通无向图，共有28条边，则该图至少有_个顶点9. N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_个非零元素。10在有n个顶点的有向图中，每个顶点的度最大可达_。11设有一稀疏图G，则G

24、采用 存储较省空间。12设有一稠密图G，则G采用 存储较省空间。13n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。14 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 。则从顶点0出发按广度优先遍历的结点序列是 。三、选择题（每小题1分，共17分）（ ）1 不含任何结点的空树 。（）是一棵树; （）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树（ ）2二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都

25、能存储; （）顺序存储结构和链式存储结构都不能使用 （ ）3. 具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ ）4把一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的 （）有多种（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子（ ）5. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A1/2 B. 1 C. 2 D. 4 （ ）7. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ ）8. 用邻接表表示图进行广

26、度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 树 D. 图 （ ）9. 深度优先遍历类似于二叉树的A先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ ）10. 广度优先遍历类似于二叉树的A先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历11. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的 C 。供选择的答案A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交

27、允许叶结点相交 允许树枝结点相交C： 权 维数 次数 序答案：A= B= C= 12. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。供选择的答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左子结点 右子结点 左子结点或者没有右子结点 兄弟CD： 最左子结点 最右子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 四、阅读分析题（每题5分

28、，共40分）1. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，图1试画该出二叉树图2图3图12试写出如图1所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 3. 把如图2所示的树转化成二叉树。4.画出图3二叉树相应的森林。5.已知如图所示的有向图，请给出该图的:顶点123456入度321122出度022313（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。 6请对下图的无向带权图：（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2） 写出它的邻接表，并按

29、克鲁斯卡尔算法求其最小生成树。 7已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。8给定下列网G: （10分）1 试着找出网G的最小生成树，画出其逻辑结构图；2 用两种不同的表示法画出网G的存储结构图；3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。五、算法设计题（前15题中任选2题，第67题中任选1题，共16分）1.编写递归算法，计算二叉树中叶子结点的数目。2. 写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 3编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。4.编写按层次顺序（同一层自左

30、至右）遍历二叉树的算法。5.编写算法判别给定二叉树是否为完全二叉树。6编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：Status Build_AdjList(ALGraph &G) /输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表 return OK; /Build_AdjList 7.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ）解： /设本题中的图G为有向无权图Status DeleteArc(MGraph

31、 &G, char v, char w) /在邻接矩阵表示的图G上删除边(v,w) return OK; /Delete_Arc 答案：一、12345678910二、156n个顶点n-1条边的连通图11邻接表231,327n12邻接矩阵398913O(n2) O(n+e)435092(n-1)1401342560123465533102*(n-1)15三、四、1、答：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。解：方法是：由前序先确定root，由中序可

32、确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 2、答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A3、答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。4、答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。五、1、顶点123456入度321122出度0223135、(1)（2）（3）1T214T326T4356T516125T（4）1256T236 T3442546T634T6、解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为： 最小生成树 PRIM算法（横向变化）： VbcdefghUV-UVexlowcosta4a3aaaaaab,c,d,e,f,g,hVexlowcosta40c5aaac5a,cb, d,e,f,g,hVexlowcost00c5b9aac5a,c,bd,e,f,g,hVexlowcost000d7d6d5d4a,c,b,d e,f,g,hVexlowcost0