数据结构复习题.doc

广西大学课程考试试卷一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1. 若算法中语句的最大频度为T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（）AO(logn)BO(n)CO(nlogn)DO(log2n)2. 在数据结构中，从逻辑上可以把数据结构分成( )A.线性结构和非线性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构3. for（i=0；im；i+）for（j=0；jnext-next!=h) p=p-next; p-next=h; 后（其中，p-next为p指向结点的指针域），则( )A. p-next指针指向链尾结点 B. h指向链尾结点 C. 删除链尾前面的结点 D. 删除链尾结点6. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULLB.headnext= =NULLC.head!=NULLD.headnext= =head7. 设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )A.236 B.239 C.242D.2458. 设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( )A.DCBAB.CDABC.DBAC D.DCAB9. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点10. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 11. 循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front12. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front13. 循环队列存储在数组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)14. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A. 13 B. 33 C. 18 D. 15. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+22516. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A3,10 C. A5,8 D. A0,917. 某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A.高度等于其结点数B.任一结点无左孩子 C.任一结点无右孩子D.空或只有一个结点18. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A10B11C12D不确定的19. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 20. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D50521. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间22. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：( )A、 E B、 F C、 G D、 H 23. n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn24. 由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 25. 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( )A.选择排序B.插入排序C.冒泡排序 D.快速排序26. 若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A. B. nC. D. n+127. 在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )A.希尔排序 B.插入排序C.冒泡排序 D.快速排序得分28. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。A 21,25,5,17,9,23,30 B25,23,30,17,21,5,9C 21,9,17,30,25,23,5 5,9,17,21,23,25,3029. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减30. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)31. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /232. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储33. 下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序34. 对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。A. 选择 B. 快速 C. 希尔 D. 冒泡35. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆36. 采用简单选择排序，比较次数与移动次数分别为( )。 A. O（n）,O(logn) B. O(logn),0(n*n) C. 0(n*n),0(n) D. 0(nlogn),0(n)37. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）A-1，4，8，9，20，7，15，7 B-1，7，15，7，4，8，20，9C-1，4，7，8，20，15，7，9 DA，B，C均不对。38. 归并排序中，归并的趟数是( )。AO（n） BO(logn) CO(nlogn) DO(n*n) 39. 下面的排序为哪种排序法 ( ) 数组：8，6，3，2，9 排序： 第1步 6，3，2，8，9 第2步 3，2，6，8，9 第3步 2，3，6，8，9 第4步 2，3，6，8，9 A）插入排序法 B）快速排序法 C）冒泡排序法 D）选择排序法40. 在对n（n3）个元素进行选择排序的过程中，在第 3 趟需要从( )个元素中选择出最小值元素。 A）n-2 B）n-3 C）3 D）441. 循环队列的入队操作应为( ) 。 A）rear=rear+1; datarear=x; B）datarear=x; rear=rear+1; C）rear=(rear+1)%size; datarear=x; D）datarear=x; rear=(rear+1)%size;42. 如果以数组作为堆栈的存储结构，则出栈操作时( ) 。 A）必须判断栈是否满 B）判别各元素的类型 C）必须判断堆栈是否为空 D）对堆栈不做任何判断priordatanext43. 双向链表节点结构如右： 节点类的结构如下： class Node Object data; Node prior; Node next; 其中：prior是指向前趋节点的链域； data 是存放数据元素的数据域； next 是指向后继节点的链域； 下面给出的算法段是要把一个新节点 node 作为非空双向链表中的节点 node1 的前趋，插入到此双向链表中。能正确完成要求的算法段是（ ） A）node.prior=node1.prior; node.next=node1; node1.prior=node; node1.prior.next=node; B）node1.prior=node; node.next=node1; ode1.prior.next=node; node.prior=node1.prior; C）node.prior=node1.prior; node.next=node1; node1.prior.next=node; node1.prior=node; D）node1.prior=node; node.next=node1; node.prior=node1.prior; node1.prior.next=node; 44. 以下说法错误的是（ ） 。 A）二叉树可以是空集 B）二叉树的任一节点都有两棵子树 C）二叉树与树具有相同的树形结构 D）二叉树中任一节点的两棵子树有次序之分45. 设深度为 k 的二叉树只有深度为 0 和度为2 的节点，则这类二叉树上所含节点的个数最少( ) 个。 A）k+1 B）2k C）2k-1 D）2k+146. 设二叉树根节点的层次为 0，一棵深度为 h的满二叉树中的节点个数是( )。 A）2hB）2h-1C）2 h-1D）2h+1-147. 在对n个元素进行冒泡排序的过程中，第( )对相邻元素之间的交换。 A）n B）n-1 C）n+1 D）n/248. 在对n个元素进行直接选择排序的过程中，需要进行( )趟选择和交换。 A）n B）n-1 C）n+1 D）n/249. 折半查找法适用于存储结构为( )，且按关键字已排好序的线性表A）顺序存储 B）链接存储 C）顺序存储或链接存储 D）索引存储50. 设有序表的关键字序列为1,4,6,10,18,35,42,53,67,71,78,84,92,99，当用折半查找法查找关键字 67 的节点时，经( )次比较后查找成功。 A）2 B）3 C）4 D）1251. 在表长为 n 的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。 A）n B）1 C）n+1 D）n-152. 向一个栈顶指针为 Top 的链栈中插入一个 p 所指结点时,其操作步骤为( ) . A.Top-next=p; B.p-next=Top-next;Top-next=p; C.p-next=Top;Top=p; D.p-next=Top;Top=Top-next;53. 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( ) .A.500 B. 501 C.490 D. 49554. 有 12 个记录的序列,采用冒泡排序最少的比较次数是( ) .A.1 B.144 C.11 D.66二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。55. 链式存储结构的特点是借助_来表示数据元素之间的逻辑关系。56. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。57. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ _58. 带头结点的双循环链表L为空表的条件是：_ _。59. 在单链表p结点之后插入s结点的操作是：_ _。60. 设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“_ _”。61. 设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s-tl-r1=s-r1；”和“_”。62. 在一个长度为n的数组中删除第i个元素（1in）时，需要向前移动的元素的个数是_。63. 己知三对角矩阵A【1.9,1.9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A7,8的地址为_64. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_。65. 假设根结点的层数为，具有个结点的二叉树的最大高度是_ _。66. 设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_,最小结点数为_ _。67. 在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为_ _。68. 在n个记录的有序顺序表中进行折半查找，最大比较次数是_。69. 前序序列和中序序列不相同的二叉树的特征是_ _。70. 设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的_ _。71. 深度为15的满二叉树上，第5层有_个结点。72. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为_。73. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为_。74. 在一棵二叉排序树上按_ _遍历得到的结点序列是一个有序序列。75. 若用后根遍历法遍历题21图所示的二叉树，其输出序列为_ _。 题21图76. 用_ _排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：20，12，25，15，47，30，76，8312，20，15，25，30，47，76，8312，15，20，25，30，47，76，8377. 在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行_趟才能够完成。78. 在索引顺序表上的查找分两个阶段：一是查找_ _，二是查找块。三、判断题（共12分，每空1分）1. 线性表的逻辑顺序与存储顺序总是一致的. ( ) 2. 完全二叉树中,若一个结点没有左孩子,则它必是叶子. ( )3. 若一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的先序遍历序列中的最后一个结点. ( )4. 折半查找只能在有序的顺序表上进行. ( )5. 对二叉排序树进行中序遍历得到的序列是由小到大有序的. ( )6. 在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机 存取的存储结构. ( )7. 循环队列通常用指针来实现队列的头尾相接.( )8. 顺序查找可以在顺序表上进行,不能在单链表上进行. ( )9. 在二叉排序树中,最大值结点和最小值结点一定是叶子结点. ( )10. 若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 3,2,5,6,4,1. ( )11. 插入排序是稳定的,选择排序是不稳定的. ( )12. 对有 n 个记录的集合进行快速排序,所需时间决定于初始记录的排列情况,在初始 记录无序的情况下最好. ( )四、解答题（本大题共2小题，每小题8分，共16分）79. 已知一棵线索化的二叉排序树如图所示。（1）说明该树的线索化是基于何种遍历次序的；（2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树。80. 分别写出图中二叉树的先根、中根、后根遍历序列。81. 设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。82. 已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。83. 给定表（19，14，22，01，66，21，83，27，56，13，10）。试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。84. 给定有序表D=006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908，用二分查找法在D中查找586，试用图示法表示出查找过程。85. .循环队列的优点是什么?如何判别它的空和满? 86. 请写出冒泡排序的算法，并使用算法将下列数据进行排序34，56，2，8，22，18，9，32，27（16分）五、算法设计题87. 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。88. 因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。算法如下：/顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x