东华大学数据结构期末复习题.doc

《东华大学数据结构期末复习题.doc》由会员分享，可在线阅读，更多相关《东华大学数据结构期末复习题.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、东华大学数据结构期末复习题第1章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。A效率 B。 复杂性 C。 现实性 D。 难度2. 算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C。 A和B3. 计算机算法指的是（1）,它必须具备（2） 这三个特性。(1) A计算方法 B. 排序方法 C。 解决问题的步骤序列 D。 调度方法（2) A可执行性、可移植性、可扩充性 B。 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4. 一个算法应该是（ )。 A程序 B问题求解步骤的描述 C数据结构+程序 D以上都不对。 5. 下面关于算法说法

2、错误的是( ）A算法最终必须由计算机程序实现B。为解决某问题的算法同为该问题编写的程序含义是相同的C。 算法的可行性是指指令不能有二义性 D。 以上几个都是错误的6. 下面说法错误的是（ ） （1）算法原地工作的含义是指不需要任何额外的辅助空间 （2)在相同的规模n下，复杂度O(n）的算法在时间上总是优于复杂度O(2n）的算法 (3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。 （4）空间复杂度是算法所需存储空间的量度。A(1） B.(1）,(2） C.（1),（4） D.(3)7. 从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构

3、、非线性结构 D初等结构、构造型结构8. 以下与数据的存储结构无关的术语是( ）.A循环队列 B. 链表 C. 哈希表 D。 栈9. 连续存储设计时，存储单元的地址( ）。A一定连续 B一定不连续 C不一定连续 D部分连续,部分不连续10. 以下属于逻辑结构的是( ).A顺序表 B. 哈希表 C。有序表 D。 单链表第2章 线性表一、选择题1. 下述哪一条是顺序存储结构的优点?（ )A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2. 下面关于线性表的叙述中，错误的是哪一个？（ )A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行

4、插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元.D线性表采用链接存储，便于插入和删除操作.3. 线性表是具有n个（ )的有限序列(n0）. A表元素 B字符 C数据元素 D数据项 E信息项4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6. 设一个链表最常用的操作是在末尾插入结

5、点和删除尾结点，则选用（ ）最节省时间.A. 单链表 B。单循环链表 C。 带尾指针的单循环链表 D.带头结点的双循环链表7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间.A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比9. 下面的叙述不正确的是（ )A线性表在链式存储时,查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时,查找

6、第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关10. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）（1=inext； B snext=p-next；pnext=s;Cpnext=s；p-next=snext; D p-next=snext;pnext=s；15. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是（ ）Ahead=NULL Bhead-next=NULL Cheadnext=head Dhead!=NULL二、综合应用题1. 已知线性表（a1 a2 a3 an）按顺序存于内

7、存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法:例：(x，x,x，x,x，-x x）变为（x,x,xx,x,x）.2. 设单链表的表头指针为h,结点结构由data和next两个域构成,其中data域为字符型。写出算法dc（h，n），判断该链表的前n个字符是否中心对称。例如 xyx， xyyx都是中心对称。3. 已知非空线性链表由list指出，链结点的构造为（data,link)。请写一算法,将链表中数据域值最小的那个链结点移到链表的最前面。要求:不得额外申请新的链结点。4. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效)算法。void del

8、ete(Linklist &L）5. 设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前,其值均初始化为零。每当在链表中进行一次Locate(L，x）运算时,令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x）运算的算法，该运算为函数过程,返回找到结点的地址，类型为指针型。6. 已知长度为n的线性表A采用顺序存储结

9、构,请写一时间复杂度为0(n)、空间复杂度为0(1)的算法,该算法删除线性表中所有值为item的数据元素.（O（1）表示算法的辅助空间为常量）。第3章 栈和队列一、选择题1. 对于栈操作数据的原则是（ ）。A. 先进先出 B。 后进先出 C。 后进后出 D。 不分顺序2. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。A. 不确定 B. ni+1 C. i D. ni3. 若一个栈的输入序列为1,2，3,，n，输出序列的第一个元素是i，则第j个输出元素是（ ）。A。 i-j1 B. ij C. ji+1 D。 不确定的4. 一个栈的输入序列为1

10、2 3 4 5,则下列序列中不可能是栈的输出序列的是（ ）。 A。 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D。 1 5 4 3 25. 输入序列为ABC,可以变为CBA时，经过的栈操作为（ )A。 push，pop,push，pop,push，pop B. push,push，push，pop，pop，popC. push,push,pop,pop,push，pop D。 push,pop，push，push，pop，pop6. 若一个栈以向量V1.。n存储，栈为空时栈顶指针top为n+1，则下面x进栈的正确操作是( ）.Atop：=top+1; V top：

11、=x B。 V top:=x； top：=top+1 C. top:=top1; V top:=x D. V top：=x； top:=top-17. 栈在（ ）中应用。A。 递归调用 B。 子程序调用 C。 表达式求值 D. A，8. 一个递归算法必须包括( ）。A. 递归部分 B. 终止条件和递归部分 C。 迭代部分 D.终止条件和迭代部分9. 用不带头结点的单链表存储队列时，其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（ ).A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改10. 递归过程或函数调用时，处理参数及

12、返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D。 线性表11. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为（ ).A（rear-front+m)%m Brearfront+1 C（front-rear+m）%m D(rear-front）%m12. 循环队列存储在数组A0.m中，则入队时的操作为( )。A。 rear=rear+1 B. rear=(rear+1) mod （m-1） C. rear=（rear+1) mod m D。 rear=(rear+1)mod（m+1) 13. 若用一个大小为6的数组来实现循环

13、队列,且当前rear和front的值分别为0和3，当从队列中删除一个元素,再加入两个元素后，rear和front的值分别为多少?( ）A. 1和 5 B。 2和4 C. 4和2 D。 5和1 14. 栈的特点是( ），队列的特点是( ），栈和队列都是（ ）。若进栈序列为1，2，3，4 则( ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1，2，3，4 则( )是一个出队列序列。, ： A。 先进先出 B。 后进先出 C. 进优于出 D。 出优于进： A。顺序存储的线性结构 B.链式存储的线性结构 C。限制存取点的线性结构 D.限制存取点的非线性结构, ： A. 3，2，1,

14、4 B. 3，2,4，1 C。 4,2，3，1 D. 4,3，2,1 F. 1,2，3，4 G. 1,3，2,415. 栈和队列的共同点是（ ）.A. 都是先进先出 B. 都是先进后出 C。 只允许在端点处插入和删除元素 D. 没有共同点16. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6，e5,e1则栈S的容量至少应该是( ）.A 6 B。 4 C. 3 D. 217. 用单链表表示的链式队列的队头在链表的（ )位置。A链头 B链尾 C链中二、综合应用题1. 有5 个元素，其入栈次序为

15、：A，B,C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个？2. 设从键盘输入一整数的序列：a1, a2, a3，an，试编写算法实现：用栈结构存储输入的整数，当ai1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（栈空等)给出相应的信息。3. 设表达式以字符形式已存入数组En中,为表达式的结束符，试写出判断表达式中括号（(和）是否配对的C语言描述算法; (注：算法中可调用栈操作的基本算法。) 第4章 树和二叉树一、选择题1. 设树T的度为4，其中度为1,2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5

16、 B6 C7 D82. 在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D3. 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F中第一棵树的结点个数是（ )Am-n Bmn1 Cn+1 D条件不足,无法确定 4. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( ）A9 B11 C15 D不确定 5. 设森林F中有三棵树，第一，第二,第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的

17、右子树上的结点个数是( ）。AM1 BM1+M2 CM3 DM2+M36. 具有10个叶结点的二叉树中有( ）个度为2的结点，A8 B9 C10 Dll7. 若一棵二叉树有126个节点，在第7层（根节点在第1层）至多有（ ）个节点。A 32 B 64 C63 D不存在第7层 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ） A不确定 B2n C2n+1 D2n19. 下列关于哈夫曼树的 说法中最准确的是( )。A最优树 B叶子节点带有权值的二叉树 C。最优二叉树 D叶子节点带有权值的树10. 有关二叉树下列说法正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有

18、一个结点的度为2 D二叉树中任何一个结点的度都为211. 二叉树的第I层上最多含有结点数为（ )A2I B 2I-11 C 2I-1 D2I -112. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间13. 一棵二叉树高度为h，所有结点的度或为0，或为2,则这棵二叉树最少有（ ）结点A2h B2h1 C2h+1 Dh+1 14. 对于有n 个结点的二叉树， 其高度为（ ）Anlog2n Blog2n Clog2n+1 D不确定15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Alog2n+1 Blog2n+1 Clog2n D

19、log2n116. 高度为 K的二叉树最大的结点数为（ ）.A2k B2k-1 C2k 1 D2k1117. 一棵高为K的完全二叉树至少有( ）个结点A2k 1 B. 2k1 1 C. 2k1 D。 2k18. 对于先序遍历和中序遍历结果相同的二叉树是（ ）。A 无左子树的二叉树 B无右子树的二叉树 C所有节点只有左子树的二叉树 D所有节点只有右子树的二叉树19. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）次序的遍历实现编号。A先序 B. 中序 C。 后序 D. 从根开始按层次遍历20. 树

20、的后根遍历序列等同于该树对应的二叉树的（ )。 A。 先序序列 B. 中序序列 C。 后序序列21. 在下列存储形式中，哪一个不是树的存储形式?（ ）A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法22. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 23. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF，则后序遍历的结果为( ）。ACBEFDA B FEDCBA C CBEDFA D不定 24. 某二叉树中序序列为A,B,C，D，E，F，G，后序序列为B,D

21、,C，A，F，G，E 则前序序列是（ ）。AE，G，F,A，C，D,B BE，A,C,B,D,G，F CE，A，G,C,F，B，D D上面的都不对 25. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历： HFIEJKG 。该二叉树根的右子树的根是（ ）。A、 E B、 F C、 G D、 H 26. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号,编号为1，2, ，n,且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1,而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ )编号的。A.中序遍历序列 B.前序遍历序列 C.

22、后序遍历序列 D.层次顺序 27. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ )。A完全二叉树 B只有两个结点的二叉树 C. 二叉排序树 D. 任一节点只有一个孩子结点28. 任何一颗二叉树的叶子结点在先序序列,中序序列和后序序列中的相对次序（ ）。A不 发生改变B发生改变 C不能确定D以上都不对 29. 若对二叉树进行中序遍历,具有左、右子树的结点，其后继是该结点的（ ）。A 双亲结点 B其左子树中最右下角元素 C其右孩子 D其右子树中最左下角元素30. 在完全二叉树中，若一个结点是叶结点,则它没（ ）. A左子结点 B右子结点 C左子结点和右子结点 D左子

23、结点，右子结点和兄弟结点31. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是:( ）。A不确定 B. 0 C。 1 D。 2 32. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( ).A。 0 B. 1 C. 2 D. 不确定 33. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ） 。A. X的双亲 B。 X的右子树中最左的结点 C。 X的左子树中最右结点 D。 X的左子树中最右叶结点34. 引入线索二叉树的目的是( )A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结

24、果唯一 35. n个结点的线索二叉树上含有的线索数为( ）A2n Bnl Cnl Dn 36. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个.A n1 Bn C n+1 D n+2 37. 在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树，该说法( ）。 A正确 B错误 38. 下述编码中哪一个不是前缀码（ ）。A（00，01，10,11） B(0，1,00，11) C（0，10，110，111） D（1,01,000，001）39. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中,则二叉树

25、中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是( ）AA2i(2i=n) BA2i+1（2i+1rh） hi=(6）_；else hi=(7）_; else hi=(8）_；return hi;16、 将下列由三棵树组成的森林转换为二叉树.BACEDFNPGHJMOLIK17、 设T是一棵给定的查找树,试编写一个在树中删除根结点为a的子树的程序，要求在删除的过程中释放该子树所有结点所占有的存储空间,这里假设树T中结点所占有的存储空间是通过动态存储分配取得的，其结点的形式为：（lchild,data,rchild)18、 试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数

26、。第5章 图一、选择题1. 图中有关路径的定义是（ )。A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是2. 设无向图的顶点个数为n，则该图最多有（ )条边.An1 Bn(n-1)/2 C n(n+1）/2 D0 En23. 一个n个顶点的连通无向图，其边的个数至少为( ）。An-1 Bn Cn+1 Dnlogn;4. n个结点的完全有向图含有边的数目（)。Ann n（n） Cn2 Dn*（nl）5. 一个有n个结点的图，最少有( ）个连通分量，最多有（ ）个连通分量。A0 B1 Cn1 Dn6. 在一个无向图中,所有顶点的度数之和等

27、于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( ）倍。A1/2 B2 C1 D47. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（ ）。A逆拓扑有序 B拓扑有序 C无序的 8. 无向图G是 一个连通图，有9条边,则该图至少有( ）个顶点。A4 B5 C6 D7 9. 下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网10. 下列说法不正确的是（ ）.A图的遍历是从给定的源点出发每一个顶点仅被访问一次B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图D图的深度遍历是一

28、个递归过程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)，对该图进行深度优先遍历,得到的顶点序列正确的是( ）.Aa,b,e,c，d，f Ba,c，f，e，b，d Ca，e,b，c，f,d Da，e，d,f，c,b12. 下面哪些方法可以判断出一个有向图是否有环(回路）： ( ）A深度优先遍历 B. 拓扑排序 C。 求最短路径 D. 求关键路径13. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( ）.A。 O（n） B. O(n+e） C。 O(n2） D. O(n

29、3)14. 已知有向图G=（V，E)，其中V=V1,V2,V3，V4，V5,V6，V7，E=V1，V2，V1,V4,V3，V5,V3,V6,V5,V7,V6,V7,G的拓扑序列是（ ）。AV1,V3,V4,V6，V2,V5,V7 BV1,V3,V2，V6，V4,V5,V7CV1，V3，V4，V5,V2，V6,V7 DV1,V2，V5,V3,V4，V6,V715. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（ ）。 A存在 B不存在16. 一个有向无环图的拓扑排序序列（ ）是唯一的。A一定 B不一定17. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形

30、不可能出现的是（ ). AG中有弧Vi，Vj BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 二、综合应用题1. 请计算下图中的强连通分量的个数2. 考虑下图：（1）画出G的邻接表表示图;（2）根据你画出的邻接表，以顶点为根，画出G的深度优先生成树和广度优先生成树。3. 在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST.4. 考虑下图：根据普利姆(Prim） 和Kruskal算法分别求它的最小生成树。V2V0V3V5V4V13652165546第6章

31、查找一、选择题1. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为（ ）。 A （n-1)/2 B. n/2 C. (n+1）/2 D。 n2. 下面关于二分查找的叙述正确的是 ( ） A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B。 表必须有序且表中数据必须是整型,实型或字符型 C。 表必须有序，而且只能从小到大排列D。 表必须有序,且表只能以顺序方式存储3. 当在一个有序的顺序存储表上查找一个数据时,即可用折半查找，也可用顺序查找,但前者比后者的查找速度( ). A必定快 B。不一定 C. 在大部分情况下要快 D。 取决于表递增还是递减4. 折半查找的时间复杂性为（ ）A. O（n2） B。 O（n) C. O（nlogn） D. O（logn）5. 当采用分块查找时，数据的组织方式为 （ ）。 A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序,每块内最大(或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序,每块内最大（或最小）的数据组成索引块D。 数据分成若干块，每块（除最后一块外）中数据个数需相同6. 二叉排序树的查找效率与二叉树的（ （1）)有关， 在 (（2）)时其查找效率最低 (1）: A