算法与数据结构习题汇总.doc

一选择题1. 从逻辑上可以把数据结构分为（C)两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构2. 2.在下面的程序段中，对x的斌值语句的频度为（C)。for( t1；kn;k）for（j=1;jn; j）x=x十1；A. O(2n) B. 0(n) C. 0(n2) D.（1og2n)3. 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。A.一定连续 B一定不连续C.不一定连续 D.部分连续，部分不连续4. 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比B.解决某问题的算法可能有多种，但肯定采用相同的数据结构C.算法的可行性是指算法的指令不能有二义性D.同一个算法，实现语言的级别越高，执行效率就越低5. 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。A.正确性 B.健壮性 C.可读性 D.可移植性6. 1线性表是( A ) 。(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 7. 2对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A ）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 8. 3线性表采用链式存储时，其地址( D ) 。(A) 必须是连续的； (B) 部分地址必须是连续的； ( )(C) 一定是不连续的； (D) 连续与否均可以。 9. 4用链表表示线性表的优点是 （ C）。(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同10. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用(D )存储方式最节省运算时间。(A)单链表 (B)双链表(C)单循环链表 (D)带头结点的双循环链表11. 单链表中，增加一个头结点的目的是为了（C）。(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置（C）方便运算的实现 (D) 说明单链表是线性表的链式存储12. 在一个单链表中p所指结点之后插入一个指针为s的结点，正确的操作是：（B）A. p-next =s;s-next= p-next; B. s-next= p-next;p-next =s;C. p-next =s; p-next=s-next; D. s-next= s-next;p-next =s;13. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（B ）。(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表14. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表15. 1.向一个栈顶指针为Top的链栈中插人一个p所指结点时，其操作步骤为为（C）。A. Top-nextp B. p- next = Top- next; Top-next = P ;C. p-nextTop；Top=p； D. p-next=Top; TopTop-next；16. 2.对于栈操作数的原则是（B） A.先进先出 B. 后进先出 C. 后进后出 D.部分顺序17. 3.已知一个栈的入栈顺序是1,2,3,.n 其输出序列为 p1,p2,p3,.pn,若PN是n,则pi为（D）A.i B. n-I C. n-i+1 D.不确定18. 4.表达式a*(b-c)d的后缀表达式是（B）。 A. abed*-+ B. abc- * d C. abc* - d+ D.+ -*abed19. 5.采用顺序存储的两个栈的共享空间S1.m，topi代表第i个栈（i=1，2）的栈顶，栈1的底在S1、栈2的底在Sm，则栈满的条件是（B）。Atop2-top1=0 B top1+1= top2 Ctop2-top1=m D top1= top220. 6.一个入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ C ）。 A.edcba B.decba C.dceab D.abcde 21. 7.在一个链队列中，若f, r分别为队首、队尾指针，则插入p所指结点的操作为（B）。 A. f-nextp;fs； B. r-nextp;rs； C. s-next =r：r=s; D. f-next =f;fp22. 8.用不带头结点的单链表存储队列时，在进行删除运算时（D）。 A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改23. 9.递归过程或函数调用时，处理参数及返回地址，要用一种称为（C)的数据结构。 A.队列 B.静态链表 C:栈 D:顺序表24. 10.栈和队都是（C）。 A.顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构25. 数据结构中， A 是数据不可分割的最小单位。A、数据项B、数据元素C、数据类型D、数据变量26. 下面关于线性表的叙述错误的是 B 。27. A、线性表采用顺序存储，必须占用一片地址连续的单元28. B、线性表采用顺序存储，便于进行插入和删除29. C、线性表采用链式存储，不必占用一片地址连续的单元30. D、线性表采用链式存储，便于进行插入和删除31. 栈与一般线性表的区别主要在 D 。A、逻辑结构B、元素类型C、存储结构D、插入、删除元素的位置32. 串的模式匹配指的是 B 。A、求串的长度B、子串定位操作C、串连接D、插入子串33. 稀疏矩阵一般的压缩存储方法有 C 。34. A、二维数组和三维数组 B、三元组和散列表35. C、三元组和十字链表 D、散列表和十字链表36. 先序遍历的顺序是 A 。37. A、根结点，左子树，右子树B、左子树，根结点，右子树38. C、右子树，根结点，左子树D、左子树，右子树，根结点39. n条边的无向图的邻接表的存储中，边结点的个数有 B 。A、nB、2nC、n/2D、n*n40. 顺序查找适用于存储结构为 C 的线性表。A、哈希存储B、压缩存储 C、顺序存储或链式存储D、索引存储41. 下列排序算法中，_ C _排序在一趟结束后不一定能选出一个元素放在其最终位置上。A、选择B、冒泡C、归并 D、堆42. 以下序列是堆的是_ A _。A、（60,80,70,100,90,150,75,200）B、（60,80,75,100,90,150,70,200）C、（60,90,70,100,80,150,75,200）D、（200,80,70,100,90,150,75,60）43. 1下面关于串的叙述错误的是：（C） A 串是字符的有限序列B 串既可以采用顺序存储，也可以采用链式存储，C 空串是用空格构成的串D 模式配匹是串的一种重要运算。44. 2. 串 的长度是指：B A串中所含不同字母的个数 B. 串中所含字符的个数C. 串中所含不同字符的个数 D.串中所含非空格字符的个数45. 4. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（1 D）个字节；M的第8列和第5行共占（2 A）个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的（3 B）元素的起始地址一致。（D,A B） （1） A.90 B.180 C.240 D.540 （2） A.108 B.114 C.54 D.60 （3） A.M85 B.M310 C.M58 D.M0946. 5. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C），若该数组按行存放时，元素A85的起始地址是（C （(8-1)*10+5-1）*3=222），若该数组按列存放时，元素A85的起始地址是（C （(5-1)*8+（8-1）*3=39*3=117 ）。 （1） A. 80 B.100 C.240 D.270 （2） A.SA+141 B.SA+144 C.SA+222 D.SA+225（3） A.SA+141 B.SA+180 C.SA+117 D.SA+225 47. 6. 稀疏矩阵一般的压缩存储方法有两种，即（C） A.二维数组和三维数组 B. 三元组和散列 C.三元组和十字链表 D. 散列和十字链表48. 1.下列说法正确的是（c）。 A二叉树中任何一个结点的度都为2 B.二叉树的度为2 C.一棵二叉树的度可小于2 D.任何一棵二叉树中至少有一个结点的度为249. 2.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0），空链域的个数为（:C )。 A. 2n-1 B. n-1 C. n+1 D. 2n+150. 3.线索化二叉树中，某结点*p没有孩子的充要条件是（B)。 A. p-lchild=NULL B. p-ltag=1且p-rtag=1C. p - ltag=0 D. p-lchild=NULL且p-ltag=151. 树形结构中，每个结点有_C_直接前驱结点。A、多个B、0个C、1个D、0个或1个52. 4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B)。 A. 3 B. 4 C. 5 D. 153. 5.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1。这是按（B)编号的。 A.中序遍历序列 B.先序遍历序列 C.后序遍历序列 D.层次顺序54. 6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（C)个。 A. n-1 B. n C. n1 D. n255. 7.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（B)。 A. 500 B. 501 C. 490 D. 49556. 8.设森林F中有3棵树，第一，第二，第三棵树的结点个数分别为N1，N2和 N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D)。 A. N1 B. N1N2 C. N2 D. N2 N357. 9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A)。 A.不发生改变 B发生改变 C.不能确定 D:以上都不对58. 10.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D)。 A. cbed B. decab C. deabc D. cedba59. 11.若一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为dgbaechf,则后序遍历的结果为（D）。 A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca 60. 12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满61. 足（B）。 A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶子结点 D是一棵满二叉树 62. 13.引人线索二叉树的目的的是（A A:加快查找结点的前驭或后继的速度； B.为了能在二叉树中方便地进行插人与侧除； C.为了能方便地找到双亲； D.使二叉树的遍历结果唯；63. 14:设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B)。 A. 2h 2h-1 C. 2h1 D. h164. 在一个带头结点的循环单链表中，指针P指向其中的一个结点，能够判断该循环单链表为空的条件是_C_。A、p=NULLB、p-next=NULL C、p=p-next D、p=p-data65. 队列与一般线性表的区别主要在_D_。A、逻辑结构B、元素类型C、存储结构D、插入、删除元素的位置66. 串的模式匹配指的是_B_。A、求串的长度B、子串定位操作C、串连接D、插入子串67. 设二维数组A中，每个元素的长度为5个字节，行下标i为15，列下标j为18，从首地址SA开始以行序连续存放在存储器内，那么元素A55的起始地址为_C_。A、SA+237 B、SA+200C、SA+180 D、SA+3768. 在中序遍历非空二叉树所得的序列中，根结点的左边包含_C_。A、右子树上所有结点B、右子树上部分结点C、左子树上所有结点D、左子树上部分结点69. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_C_。A、各不相同B、先序和中序相同，后序不同C、都相同D、先序和后序相同，中序不同70. n条边的有向图的邻接表的存储中，边结点的个数有_A_。A、nB、2nC、n/2D、n*n71. 对于给定的一组结点建立二叉排序树，则二叉排序树的平均查找长度（ASL）与该二叉排序树的_A_有关。A、高度B、结点个数C、存储结构D、结点位置72. 下列排序算法中，_B_的比较次数与记录初始排列次序无关。A、快速排序B、简单选择排序C、直接插入排序D、堆排序73. 15.一个具有567个结点的二叉树的高h为（D）。 A. 9 B: 10 C: 9566之间 D. 10 567之间 A. n B. 2n C. n/2 D. nn74. 2. n条边的无向图的邻接多重表的存储中，边结点的个数有（A）。 A. n B. 2n C. n/2 D. nn75. 3.下列哪一种图的邻接矩阵是对称矩阵？（B)。 A.有向图 B.无向图 C. AOV网 D: AOE网76. 4.最短路径的生成算法可用（C） A.普里姆算法 B克普斯卡尔算法 G迪杰斯特拉算法 D.哈夫曼算法77. (1）从顶点Vo一出发进行深度优先搜索，经历的结点顺序为（B）。 A.V0,V3,V2,V1 B. v0,V1,V2,V3 C. V0,V2,V1,V3 D.V0,V1,V3,V2; （2）从顶点V0出发进行广度优先搜索，经历的结点顺序为（D)。 A.V0,V3,V2,V1 B. v0,V1,V2,V3 C. V0,V2,V1,V3 D.V0,V1,V3,V2;78. 6.设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（D）。 A. O(alog2e) B. O(en） C. O(elog2n) D. O(n+e)79. 7.含有乎个顶点e条边的无向连通图，利用Kniskal算法生成最小生成树，其时间复杂度为（B）。 A. O(alog2e) B. O(en） C. O(elog2n) D. O（alog2n)80. 8.关键路径是事件结点网络中（A）。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路81. 9.下面关于求关键路径的说法不正确的是（C)。 A.求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同 C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持 续时间的差 D.关键活动一定位于关键路径上 82. 10.有10个结点的无向图至少有（B）条边才能确保其是连通图。 A. 8 B. 9 C. 10 D. 1183. 1静态查找表与动态查找表的根本区别在于（B）A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样84. 2在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（C）。A. n B. l C. n+1 D. n-185. 3.顺序查找适用于存储结构为（C）的线性表。A.散列存储 B.压缩存储C.顺序存储或链式存储 D.索引存储86. 4.用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C)。A. O(log2n2） B. O(nlog2n) C. O(n) D. O( log2n）87. 5.适用于折半查找的表的存储方式及元素排列要求为（D）。A.链接方式存储，元素无序 B.链接方式存储，元素有序C.顺序方式存储，元素无序 D.顺序方式存储，元素有序88. 6.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。A. 35/12 B. 37/12 C. 39/12 D. 43/1289. 7.在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为82的数据元素需要比较（C）次。A. 1 B. 2 C. 4 D. 590. 8.设散列表长为14，散列函数为H(key)二key% 11。当前表中已有4个结点：addr(15 )=4，addr(38) = 5，addr(61)=6，addr(84)二7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（D）。A. 8 B. 3 C. 5 D. 1991. 9.散列函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。A.最大概率 B.最小概率 C.平均概率 D.同等概率92. 10.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少（D）次探测？ A. k-1次 B. k次 C. k1次 D. k（k+l）/2次93. 11. 取在散列函数H(k)k% m中，一般来讲，m应取（C)。A.奇数 B.偶数 C.素数 D.充分大的数94. 12.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（D)A.一定是同义词 B.一定不是同义词C.都相同 D.不一定都是同义词95. 13.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（B）个结点最佳。A. 10 B. 25 C. 6 D. 62596. 14.下列关于m阶B树的说法错误的是（D）。A.根结点至多有m棵子树B.所有叶子都在同一层次上C.非叶结点至少有m/2 ( m为偶数）或功i/2 +1 (m为奇数）棵子树D.根结点中的数据是有序的97. 15. m阶B树是一棵（B）。A. m叉排序树 B. m叉平衡排序树C. m一1叉平衡排序树 D. m1叉平衡排序树98. 1.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。A.插入排序 B.选择排序 C.快速排序 D.归并排序99. 2设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（C）法。A.冒泡排序 B.快速排序 C.堆排序 D.基数排序100. 3.具有12个记录的序列，采用冒泡排序最少的比较次数是（C)。A. 1 B. 144 C. 11 D. 66101. 4.下列4种排序方法中，要求内存容量最大的是（D）。A.插入排序 B.选择排序 C.快速排序 D.归并排序102. 5.初始序列已经按键值有序时，用直接插人算法进行排序，需要比较的次数为（D).A. n2 B. nlog2n C. log2n D. n-1103. 6.下列4种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是（C）。A.直接插人排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.直接插人排序和归并排序104. 7.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（B）。A. 79，46，56，38，40，84 B. 84，79，56，38，40，46C. 84，79，56，46，40，38 D. 84，56，79，40，46，38105. 8.一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第1个记录为基准得到的一次划分的结果为（C)。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，79106. 9.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：25，84，21，47，15，27，68，35，2020，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则采用的排序方法是（D）。A.选择排序 B.希尔排序 C.归并排序 D.快速排序107. 10.快速排序方法在（C)情况下最不利于发挥其长处。A.要排序的数据量太大 B.要排序的数据中含有多个相同值C.要排序的数据已基本有序 D.要排序的数据个数为奇数二 判断题1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）2. 顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（）3. 数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（）4. 算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（）5. 算法必须有输出，但可以没有输人。（）6. 线性表的逻辑顺序与存储顺序总是一致的。7. 顺序存储的线性表可以按序号随机存取。8. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 9. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。10. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。11. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。12. 线性表的链式存储结构优于顺序存储结构。13. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。14. 线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。15. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。16. 11.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个的元素的时间与i无关。17. 12.线性表的特点是每个元素都有一个前驱和一个后继。18. 栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（）19. 任何一个递归过程都可以转换成非递归过程。（）20. 若输入序列为1,2,3,4,5,6, 则通过一个栈可以输出序列3,2,5,6,4,1（）21. 通常使用队列处理函数的调用（）。22. 循环队列通常使用指针来实现队列的头尾相接。（）23. 串相等是指两个串的长度相等。（）24. KMP算法的特点是在模式匹配时指示主串 的指针不会变小。（）25. 稀疏矩阵压缩存储后，会失去随即存储功能。（）26. 数组是线性结构的一种推广，由此与线性表一样，可以对它进行插入、删除等操作。（）27. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算（B）（）28. 若一个广义表的表头为空，则此广义表为空。（）29. 所谓广义表的表尾就是返回广义表中的最后一个元素。（）30. 一个算法必须在执行有穷步骤之后结束，这是算法的正确性。（ ）31. 对于一个单链表存储的线性表，在表头插入元素花费的时间比在表尾插入元素花费的时间要多。（ ）32. 设栈的输入序列是（1,2,3），则可能有的出栈序列有5种。（ ）33. 串是一种特殊的线性表，其特殊性体现在数据元素是单个字符。（ ）34. 完全二叉树一定是满二叉树。（ ）35. 由树转换成二叉树，其根结点的右子树总是空的。（ ）36. 在二叉树只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。（ ）37. 有向图的邻接矩阵是一个对称矩阵。（ ）38. 归并排序在最坏情况下的时间复杂度是O(n2)。（ ）39. 平衡二叉树中每个结点的平衡因子只有三种情况：0、1 或-1。（ ）40. 顺序存储的线性表可以按序号随机存取。（ ）41. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）42. 线性表的链式存储结构优于顺序存储结构。（ ）43. 满二叉树一定是完全二叉树。（ ）44. 由前序序列和后序序列能唯一确定一棵二叉树。（ ）45. 图的最小生成树的形状可能不唯一。（ ）46. 连通分量是无向图中的极小连通子图。（ ）47. 顺序查找可以在顺序表上进行，不能在单链表上进行。（ ）48. 对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。（ ）49. 堆排序所需要附加空间数与待排序的记录个数无关。（ ）50. 二叉树是树的特殊形式。（）51. 2.由树转换成二叉树，其根结点的右子树总是空的。（）52. 3.先根遍厉，棵树和先序遍历与该树对应的二叉树，其结果不同。（x）53. 4.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（x）54. 完全二叉树中，若一个结点没有左孩子，则它必是叶子。（）55. 对于有N个结点的二叉树，其高度为 log, N1（）56. 若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（）57. 若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后58. 序遍历序列中的第一个结点。（）59. 不使用递归也可实现二叉树的先序、一中序和后序遍历。（）60. 先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（x）61. 先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（）62. 在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。（x）63. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）64. 在哈夫曼编码中，出现频率相同的字符编码长度也一定相同（x）65. 用一维数组存放二叉树时，总是以先序遍历存储结点。（x）66. 由先序序列和后序序列能唯一确定一棵二叉树。（x）67. 由先序序列和中序序列能唯一确定一棵二叉树。（）68. 对一棵二叉树进行层次遍历时，应借助于一个栈。（x）69. 完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（x）70. 满二叉树一定是完全二叉树，反之未必。（）71. 求最小生成树的Prim算法在边较少、结点较多时效率较高。（）72. 图的最小生成树的形状可能不唯一。（ ） 73. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )74. 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()75. 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。( )76. 有回路的图不能进行拓扑排序。( )77. 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。()78. 十字链表可以存储无向图和有向图( )79. 任何无向图都存在生成树（）80. 若一个有向图的邻接矩阵对角线一下的元素均为0,则该图的拓扑有序序列必定存在。( )81. 连通分量是无向图中的极小连通子图。()82. 强连通分量是有向图中的极大强连通子图。( )83. 用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。()84. 缩短关键路径上活动的工期一定能够缩短整个工程的工期。85. 在AOE网中一定只有一条关键路径。()86. 顺序查找可以在顺序表上进行，不能在单链表上进行。（）87. 折半查找只能在有序的顺序表上进行。（）88. 对于给定的关键字集合，以不同的次序插人到初始为空的二叉排序树中，得到的二叉排序树是相同的。（）89. 若二叉排序树中关键字互不相同；那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（）90. 在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（）91. 将二叉排序树T的先序遍历序列依次插人初始为空的树中，所得到的二叉排序树T2和T；的形态完全相同。（）92. 对二叉排序树进行中序遍历得到的序列是由小到大有序的。（）93. 二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（）94. 二叉排序树的查找和折半查找的时间复杂度都是O(log2n)，时间性能相同。（）95. 采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（）96. 采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的在位置置为空，因为这将会影响以后的查找。（）97. m阶B树每一个结点的子树个数都小于或等于m。（）98. 散列表的查找效率主要取决于构造散列表时选取的散列函数和处理冲突的方法。（）99. 散列法存储的基本思想是由关键码的值决定数据的存储地址。（）100. 当负载因子小于1时，则向散列表中插人元素时不会引起冲突。（）101. 查找表中数据元素的任何数据项都可以作为关键字。（x）102. m阶B树的任何一个结点的所有子树的高度都相等。（）103. 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（x）104. 在散列存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。（）105. 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的（）。106. 插人排序是稳定的，选择排序是不稳定的。（）107. 不稳定的排序算法是没有实用价值的。（）108. 当待排序的元素很多时，为了交换元素的位置，移动元素要占较多的时间，这是影响时间复杂度的主要原因。（）109. 对有n个记录的集合进行归并排序，所需要的辅助空间数与初始记录的排列状况有关。（x）110. 对n个记录的集合进行快速排序，所需要的附加空间数是O(n)。（x）111. 堆排序所需要的附加空间数与待排序的记录个数无关。（）112. 对有n个记录的集合进行冒泡排序，所需时间决定于初始记录的排列情况，在初始113. 记录无序的情况下最好。（x）114. 对有n个记录的集合进行快速排序，所需时间决定于初始记录的排列情况，在初始115. 记录无序的情况下最好。（）116. 对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例117. 来。（）118. 选择排序的比较次数不会随待排序记录的关键字的分布情况而改变。（）三填空题1、 数据的逻辑结构通常有四种，分别是集合、_线性_、_树_和图结构。2、 在线性结构中,第一个结点_没有_前驱结点,其余每个结点有且只有_1_个直接前驱结点；最后一个结点_没有_后续结点,其余每个结点有且只有_1_个直接后续结点。 3、 队列只能在 队尾 位置插入和 队头 位置删除元素。4、 在树形结构中,树根结点没有_前驱_结点,其余每个结点有且只有_1_个直接前驱结点；叶子结点没有_后继_结点,其余每个结点的后续结点可以_任意多个_。 5、 在图形结构中,每个结点的前驱结点数和后续结点数可以_任意多个_。 6、 算法的五个重要特性是有穷性；确定性；可行性；输入；输出 。 7、 数据结构的三要素是指_数据元素； _、_逻辑结构； _和_存储结构_。 8、 链式存储结构与顺序存储结构相比较,主要优点是_插入、删除、合并等操作较方便_ _。 9、 设有一批数据元素,为了最快的存储某元素,数据结构宜用_顺序存储_结构,为了方便插入一个元素,数据结构宜用_链式存储_结构。 10、 数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和_运算_。11、 数据结构算法中，通常用时间复杂度和_空间复杂度。_两种方法衡量其效率。12、13、 若频繁地对线性表进行插入与删除操作，该线性表应采用_链表_存储结构。14、15、 具有3个非空结点的二叉树有_5 _种不同形态，具有3个非空结点的树有_2_ 种不同形态。16、 具有n个顶点的无向完全图，边的总数为_ n(n-1)/2 _条；而在n个顶点的有向完全图中，边的总数为_ n(n-1)_条。17、 动态查找表和静态查找表的重要区别在于前者包含有_插入_和_删除_运算，而后者不包含这两种运算。18、 某带头结点的单链表的头指针head，判定该单链表非空的条件_ head-next!=Null _。19、 在双向链表中，每个结点含有两个指针域，一个指向_前驱， _结点，另一个指向_后继_结点。20、21、 已知指针p指向单链表中某个结点，则语句p-next=p-next-next的作用_删除p 的后继结点_删除p 的后继结点_。22、 已知在结点个数大于1的单链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的_后继_结点。q=p;while(q-next!=p) q=q-next;23、 数据的存储方法主要有四种，分别是_顺序存储_、_链式存储_、索引存储方法和散列存储方法。24、 栈只能在 栈顶 位置插入和 栈顶 位置删除元素。25、 二叉树的线索化实质是将二叉链表中_空指针_改为_线索_。26、 36、稀疏矩阵可用_三元组_进行压缩存储，存储时需存储非零元的_行号，列号，值。27、 37、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为_三对角矩阵_。28、 具有n个顶点的无向连通图，至少有_ n-1_条边；至多有_ n(n-1)/2_条边。29、 除了基数排序，在排序过程中主要进行的两种基本操作时记录关键字的_比较_和记录的_移动_。四、问答题1循环队列的优点是什么？如何判断它的空和满？答：循环队列可解决队列的假溢出。方法之一是附设一个存储队中元素个数的变量如num，当num=0时队空，当num=MAXSIZE时为队满。另一种方法是少用一个元素空间，所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1) % MAXSIZE=front，也能和空队区别开。队空：front=rear2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？答：栈是在表的一端进行插入和删除的线性表。后进先出的线性表前面所讲的栈是一种后进先出的数据结构；队列一种“先进先出” (FIFO-First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，3什么是递归？递归程序有什么有优点？ 答:函数在运行过程中直接或间接的调用了自己，称为递归。 优点：程序简单、结构清晰、符合结构化程序设计、可读性好。4.设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可