数据结构复习题

1、13-14-1数据结构复习题2013.12.一、判断题 1. 边数很少的稀疏图，适宜用邻接矩阵表示。（ ×）2. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。(×)3. 有回路的有向图不能完成拓扑排序。( )4. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。( )5. 一个无向连通图的生成树是图的极小的连通子图。（）6. 哈希查找法中解决冲突问题的常用方法是除留余数法。（ × ）7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。()8. 对判定树进行中根遍历，可得到结点的有序序列。（）9. 链式栈与

2、顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。（ ）10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。（）11. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。( × )12. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。( )13. 边数很少的稀疏图，适宜用邻接表表示。（ ）14. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（ ）15. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有

3、相同的结果。( )16. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（×）17. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。( × )18. 如果有向图中各个顶点的度都大于2，则该图中必有回路。( × )19. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。(×)20. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。( )21. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( × )22.

4、 内部排序是指排序过程在内存中进行的排序。（ ）23. 折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树。()24. 循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（ ）25理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。（ ）二、单项选择题 1. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（ B ）。 A.HS->next=s; B.s->next=HS->next;HS->next=s;C.s->next=HS;HS=s; D.s->next=HS;HS=HS->next;2. 已知

5、8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为（ B ） 。 A. 1B.2C.3D.43. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时（ B ）。 A.f->next=s;f=s; B.r->next=s;r=s;C.s->next=r;r=s; D.s->next=f;f=s;4. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。A.空或只有一个结点 B.高度等于其结点数C.任一结点无左孩子 D.任一结点无右孩子5. 在一个顺序

6、表中，若表的第一个元素的存储地址是210，每一个元素的长度为3，则第5个元素的存储地址是（B）。 A219 B222 C225 D2286. 对关键字集合K=53,30,37,12,45,24,96,从一棵空二叉树开始逐个插入关键字，建立二叉排序树，若希望得到的二叉排序树的高度最小，应选用下列输入序列（B）。A. 45，24，53，12，37，96，30 B.37，24，12，30，53，45，96C. 12，24，30，37，45，53，96 D.30，24，12，37，45，96，537. 在循环双链表的p所指接点之前插入s所指接点的操作是（ D ）。 A.p-> prior =s;

7、s-> next=p;p-> prior->neft=s;s-> prior =p-> prior;B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior;C.s-> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s;D.s-> next =p;s-> prior =p-> prior;p-> prior -&g

8、t; next =s;p-> prior =s;8. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（C）。 AO(n) BO(e) CO(n+e) DO(n*e)9. 已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为（ A ）。 A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3)10. 非空的循环单链表head的尾结点（由P指向）

9、满足( C )。A. p->next=NULL B. p=NULLC. p->next=head D.p=head11. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时（B）。A.f->next=s;f=s; B.r->next=s;r=s;C.s->next=r;r=s; D.s->next=f;f=s;12. 查找哈希表，不会产生冲突的哈希函数是（ B ）。 A链地址法 B直接地址法 C除留余数法 D随机探测法13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（ D ）。 A.x=HS;HS=HS-&

10、gt;next;B.x=HS->data;C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;14. 高度为5的完全二叉树中含有的结点数至少为（A ）。A.16 B.17 C.31D.3215. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8,4的地址为（ B ）。 A.15 B.32 C.34 D.3316. 假设以三元组表表示稀疏矩阵，则和下列三元组(1,2,-8),(1,4,6),（2,1,7),(4,1,-5),(4,3,4)

11、对应的稀疏矩阵是（ A ）。 17. 在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时（ C ）。 A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next;18. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84则所采用的排序方法是（D）。 A选择排序 B希尔排序 C归并排序 D快速

12、排序19. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ C ）。A.5 B.8 C.11 D.1820. 如果最常用的操作是提取第i个结点及其前驱，则采用（B ）存储方式最节省时间。 A单链表 B.顺序表 C.循环链表D.双链表21. 若已知一个栈的入栈序列是1，2，3，.n，其输出序列为p1,p2,p3,.,pn,若p1=n,则pi为（ C ）。 A.i B.n+i C.n-i+1 D.不确定22. 已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为（ A ）。 A2*(n-1)+1*d B.2*(n-1)*d

13、 C.2*(n-1)-1*d D.(n+1)*d23. 一个n阶对称矩阵，如果以行或列为主序放入内存，则容量为（ D）。 A.n*n B.n*/2 C. (n+1)*(n+1)/2 D.n*(n+1)/224查找哈希表，不会产生冲突的哈希函数是（B ）。A链地址法 B直接地址法 C除留余数法 D随机探测法25. 有40个结点的完全二叉树存储在数组1.40中，数组中第一个叶子结点是（ C ）。A19 B20 C21 D22三、填空题 1. 由关键字序列（57,24,76,63,18,31,15）生成的一棵二叉排序树，其等查找概率情况下查找成功的平均查找长度为（ 18/7）。2. 在对m阶B树插入

14、元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于( m )个，则必须把它分裂为2个结点。3. 若设一个n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素aij的存储地址为( LOC(0,0)+(i*n+j)*d )。4. 给定一组数据对象的关键码为46，79，56，38，40，84，对其进行一趟快速排序处理，得到的右子表中有( 3 )个对象。5. 在有向图中，以顶点v为终点的边的数目称为v的(入度 )。5. 在线性表的散列存储中，装载因子a 又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于（ n

15、/m）。6. 有一个10阶三角矩阵A,采用压缩方式(以行序为主存储)存储在一维数组B中,若A1,1 存储在B1中，则A5,8 存储在B（ 38 ） 。7. 在有向图中，以顶点v为终点的边的数目称为v的(入度)。8. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和（局部变量）。9. 11个顶点的连通网络N有10条边，其中权值为1, 2, 3, 4, 5的边各2条，则网络N的最小生成树各边的权值之和为(30 )。10. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A00存放于B0中，则AIJ在IJ时将存放于数组B的(

16、(2n-I-1)*I/2+J )位置。11. 在一棵m阶B树上，每个非根结点的关键码数最多为( m-1 )个。12. 在有向图中，以顶点v为终点的边的数目称为v的(入度 )。13. 求解带权连通图最小生成树的Prim算法使用图的(邻接矩阵 )作为存储结构。14. 由带权为9，6，2，5，7的五个叶子结点构造的哈夫曼树，其根结点的权值为（ 29 ）。15. 对长度为20的有序表进行二分查找的判定树的高度为( 5 )。16. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储( n(n+1)/2 )个矩阵元素。17. 在单链表中某P结点后插入S结点的操作是（ s

17、->next=p->next; p->next=s; ）。18. 设关键字序列（17,8,13,25,24,16,3，19，1），用希尔排序法按升序排序，用初始增量4进行一趟排序后的结果是( 1,8,3,19,17,16,13,25,24)。19. n个顶点的连通无向图的生成树含有(n-1 )条边。20. 链表只适用于( 顺序)查找。21. 给定一组数据对象的关键码为46,79,56,38,40,84，则利用堆排序方法建立的初始堆（最大堆）为(84，79，56，38，40，46 )。22. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的(下标（或顺序号

18、） )存取的。23. 11个顶点的连通网络N有10条边，其中权值为1, 2, 3, 4, 5的边各2条，则网络N的最小生成树各边的权值之和为( 30 )。24. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为（ 19 ）个。25. 已知一棵3阶B树中含有50个关键码，则该树的最小高度为( 4 )。四、应用题1. 依次读入给定的整数序列7，16，4，8，20，9，6，18，5，完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一

19、个元素。（1）ASL=(1+2*2+3*3+3*4)/9=26/9（2）82. 对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。(1)写出排序过程中前两趟的划分结果；(2)快速排序是否是稳定的排序方法?（1）（1，2，3，5，7，6，8，9） （2） 否3. 由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。答：前序序列:GHIJ 后序序列:HJIG4. 已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;(2)画出该有向图的逆邻接表。1）ABDCE(2)5. 已知关键字序列为：（75,33,52,41,1

20、2,88,66,27）哈希表长为10，哈希函数为：H (k)k %9，解决冲突用线性探测再散列法，试构造哈希表，求等概率下查找成功的平均查找长度。答：(1)哈希表: 0 1 2 3 4 5 6 7 8 92775124133528866(2) ASL=（5*1+2*2+1*7）/8=16/8=26. （1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，37，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。（1）如图所示. 7 10 3 1 5 8 12 2 4 6 9 11 13 （2）1次7

21、. 已知二叉树如右图所示。（1）画出该二叉树的二叉链表；（2）分别写出该二叉树的先根、中根和后根遍历序列。(1)（2）先根遍历序列：ABDCEGF中根遍历序列: DBAEGCF后根遍历序列: DBGEFCA8有七个带权结点，其权值分别为3，7，18，2，6，10，14，试以它们为叶子结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），并计算出该树的带权路径长度。答： (1) 哈夫曼树(2)带权路径长度WPL=(2+3)*4+(6+7+10)*3+(14+18)*2=1539. 选取哈希函数为H(K)=K % 13，用链地址法处理冲突。试在012的散列地址

22、空间中对关键字序列87，25，310，08，27，132，68，95，187，123，70，63，47构造哈希表，并求出等概率下查找成功的平均查找长度。H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(8)= 8 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 H(47)=47 % 13=8五、算法设计题1. 编写一个算法，判断带表头结点的单向循环链表head是否递减有序。int fun6(LNode *head ) p=head->next; while(p->next!=head) q=p->next ;if(q->data<p->data) return 0;p=q; return 1; 2. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。void algo1(LNode *h,int k,ElemType y)q=h; P=h->next; j=1;while( p