数据结构复习题集耿国华第二版版C语言描述.doc

《数据结构复习题集耿国华第二版版C语言描述.doc》由会员分享，可在线阅读，更多相关《数据结构复习题集耿国华第二版版C语言描述.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第一章 复习题1.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中，数据元素之间关系是由结点中指针指示的。2.数据结构是一门的学科。3.在数据结构中，从逻辑上可以把数据结构分成（ C ）。 A、动态结构与静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构4.编写一个函数，用不多于3n/2的平均比较次数，在一个数组中找出最大和最小值元素。void maxmin(int a,int n) max=min=a0; for(i=1;imax) max=ai; else i

2、f(ai=0） 。A表元素 B字符 C数据元素 D数据项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A顺序表 B单循环链表 C带头结点的双循环链表 D双链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A单链表 B双向链表 C单循环链表 D带头结点的双向循环链表7. 链表不具

3、有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比8. 下面的叙述不正确的是（ BC ） A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关9. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=inext=head Bp-next=NULL Cp=NULL Dp= head13循环

4、链表H的尾结点P的特点是（ A ）。 AP-NEXT=H BP-NEXT= H-NEXT CP=H DP=H-NEXT14完成在双循环链表结点p之后插入s的操作是（ D ）；A p-next=s ; s-prior=p; p-next-prior=s ; s-next=p-next;B p-next-prior=s; p-next=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s ;D s-prior=p; s-next=p-next; p-next-prior=s ; p-next

5、=s; 15在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( D )。A. p-prior=q; q-next=p; p-prior-next=q; q-prior=p-prior;B. q-prior=p-prior; p-prior-next=q; q-next=p; p-prior=q-next; C. q-next=p; p-next=q; p-prior-next=q; q-next=p;D. p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q;16在单链表指针为p的结点之后插入指针为s的

6、结点，正确的操作是：（ ）。Ap-next=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;17对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahead=NULL BHead-next=NULL CHead-next=head Dhead!=NULL18 在双向链表中，删除p所指的结点时须修改指针（ A ）。A p-prior-next=p-next; p-next-prior=p-prior;B p-prior=p-prior-pr

7、ior; p-prior-next=p;C p-next-prior=p; p-next=p-next-nextD p-next=p-prior-prior . p-prior=p-next-next;19当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。20线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1)/221设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若

8、将结点y插入结点x之后，则需要执行以下语句:py-next=px-next; px-next=py 22在一个长度为n的顺序表中第i个元素（1=inext;p-next=q-next; free (q); 27. 带头结点的双循环链表L中只有一个元素结点的条件是：L-next-next=L 28. 在单链表L中，指针p所指结点有后继结点的条件是：p-next!=null 29.带头结点的双循环链表L为空表的条件是：L-next=L & L-prior=L 30. 在单链表p结点之后插入s结点的操作是： s-next=p-next;p-next=s; 第三章 复习题1. 一个栈的输入序列为123

9、n，若输出序列的第一个元素是n，输出第i（1=i0) if(*maxAn) *min=An; MinMaxValue(A,n-1,max,min); /算法结束算法调用格式MinMaxValue (arr,n,&max,&min); arr是具有n个整数的一维数组，max=-32768是最大数的初值,min=32767是最小数的初值。void maxmin(int A,int *e_max,int *e_min,int low,int high) if(high-low)Alow) *e_max=Ahigh; *e_min=Alow; else *e_max=Alow; *e_min=Ahig

10、h; else mid=(low+high)/2; maxmin(A,&x1,&y1,low,mid); maxmin(A,&x2,&y2,mid+1,high); *e_max=max(x1,x2); *e_min=min(y1,y2); 第六章复习题1算术表达式a+b*（c+d/e）转为后缀表达式后为（ B ） Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ） A5 B6 C7 D83. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数

11、为n,森林F中第一棵树的结点个数是（ A ） Am-n Bm-n-1 Cm-n+1 D条件不足，无法确定4若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ） A9 B11 C15 D不确定5设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ D ）。 AM1 BM1+M2 CM3 DM2+M36.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ C ） A499 B500 C501 D5057. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A不确定 B2n C2n+1

12、 D2n-18.有关二叉树下列说法正确的是（ B ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为29. 一个具有1025个结点的二叉树的高h为（ C ） A11 C11至1025之间 B10 D10至1024之间10一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A2h B2h-1 C2h+1 Dh+111对于有n 个结点的二叉树, 其高度为（ D ） Anlog2n Blog2n Clog2n|+1 D不确定12高度为 K的二叉树最大的结点数为（ B ）。 A2k B2k-1 C2k -1

13、D2k-1-113. 一棵树高为K的完全二叉树至少有（ C ）个结点. A. 2k 1 B. 2k-1 1 C. 2k-1 D. 2k14. 利用二叉链表存储树，则根结点的右指针是（ C ）。 A指向最左孩子 B指向最右孩子 C空 D非空15对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。 A先序 B. 中序 C. 后序 D. 从根开始按层次遍历16树的后根遍历序列等同于该树对应的二叉树的( B ). A. 先序序列 B. 中序序列 C. 后序序列17若二叉树采用二叉链表存

14、储结构，要交换其所有分支结点左、右子树的位置，利用( AC )遍历方法最合适。 A前序 B中序 C后序 D按层次18已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。 ACBEFDA B FEDCBA C CBEDFA D不定19对于前序遍历与中序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。 A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树20一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满

15、足（ C ） A所有的结点均无左孩子 B所有的结点均无右孩子 C只有一个叶子结点 D是任意一棵二叉树21. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( D )A不确定 B. 0 C. 1 D. 222. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。A. 0 B. 1 C. 2 D. 不确定 23. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点24. 引入二叉线索树的目的是（ A ）A加快查找结点的前驱或后继的速度 B

16、为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一25n个结点的线索二叉树上含有的线索数为（ C ）A2n Bnl Cnl Dn 26由3 个结点可以构造出多少种不同的二叉树？（ D ）A2 B3 C4 D5 27. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C ）个。A n-1 Bn C n+1 Dn+2 28下面几个符号串编码集合中，不是前缀编码的是（ B ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,a

17、bc 29. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ D ） AA2i(2i=n) BA2i+1(2i+1=n) CAi-2 D条件不充分，无法确定30若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_69_。31具有n个结点的满二叉树，其叶结点的个数是_（n+1）/2_。33树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树_。 348层完全二叉树至少有_128_个结点，拥有100个结点的完全二叉树的最大层数为_7_。 35如某二叉树有20个叶子结

18、点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_。36已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。 第七章 复习题1图中有关路径的定义是（ A ）。 A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是2设无向图的顶点个数为n，则该图最多有（B）条边。 An-1 Bn(n-1)/2 C n(n+1)/2 Dn23一个n个顶点的连通无向图，其边的个数至少为（ A ）。 An-1 Bn Cn+1 Dnlogn4要连通具有n个顶点的有向图，至少需要（ B ）条边。An-l B

19、n Cn+l D2n5n个结点的完全有向图含有边的数目（D）。An*n n（n） Cn2 Dn*（nl）6一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。A0 B1 Cn-1 DN7在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。A1/2 B2 C1 D48下列哪一种图的邻接矩阵一定是对称矩阵？（ B ）A有向图 B无向图 CAOV网 DAOE网9. 下列说法不正确的是（ C ）。 A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度

20、遍历不适用于有向图 D图的深度遍历是一个递归过程10无向图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)，对该图进行深度优先遍历，得到的顶点序列正确的是（ D） Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b11下面哪一方法不能判断出一个有向图是否有环（C）：A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 AG中有弧 BG中有一条从

21、Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 14已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6, V7，E=, , , ,G的拓扑序列是（ A ）。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V715. 关键路径是事件结点网络中（ A ）。A从源点到汇点的最长路径 C最长回路 B从源点到汇点的最短路径 D最短回路16. 下面关于求关键路径的说法不正确的是（ C ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同

22、以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上17下列关于AOE网的叙述中，不正确的是（ B ）。A关键活动不按期完成就会影响整个工程的完成时间B任一个关键活动提前完成，整个工程都将会提前完成C所有的关键活动提前完成，则整个工程将会提前完成D某些关键活动提前完成，会使整个工程提前完成18.G是一个非连通无向图，共有28条边，则该图至少有 9个顶点。 19如果含n个顶点的图形形成一个环，则它有 n棵生成树。20. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 队列存

23、放被访问的结点以实现遍历。 21.设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1=i=n，则e=_ 22. Prim（普里姆）算法适用于求_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_的网的最小生成树。23.AOV网中,结点表示_,边表示_。AOE网中,结点表示_,边表示_。 24. 有向图G可拓扑排序的判别条件是_。25.在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为_。 26. 已知一无向图G=（V，E），其中V= a, b, c, d, e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_遍历方法。第八章 复习题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对线性表进行二分查找时，要求线性表必须（ B ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储