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

第一章 复习题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 if(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. 链表不具有的特点是（ 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循环链表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=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的结点，正确的操作是：（ ）。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-prior; 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的新结点 , 若将结点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. 一个栈的输入序列为123n，若输出序列的第一个元素是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=Ahigh; 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的右子树结点个数为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 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 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若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( 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一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ 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为了能在二叉树中方便的进行插入与删除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,abc 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个叶子结点，有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 Bn 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图的深度遍历不适用于有向图 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中有一条从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一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上17下列关于AOE网的叙述中，不正确的是（ B ）。A关键活动不按期完成就会影响整个工程的完成时间B任一个关键活动提前完成，整个工程都将会提前完成C所有的关键活动提前完成，则整个工程将会提前完成D某些关键活动提前完成，会使整个工程提前完成18.G是一个非连通无向图，共有28条边，则该图至少有 9个顶点。 19如果含n个顶点的图形形成一个环，则它有 n棵生成树。20. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 队列存放被访问的结点以实现遍历。 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.以链接方式存储 D.以链接方式存储,且数据元素有序3. 具有12个关键字的有序表，折半查找的平均查找长度（ A ） A. 3.1 B. 4 C. 2.5 D. 54. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( C )次探测。 A k B. k+1 C. k(k+1)/2 D.1+k(k+1)/5分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 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)6. 将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会7. 下面关于m阶B树说法正确的是( B ) 每个结点至少有两棵非空子树； 树中每个结点至多有m一1个关键字; 所有叶子在同一层上; 当插入一个数据项引起B树结点分裂后，树长高一层。 A B. C. D. 8. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( D ) A8 B3 C5 D9 9. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 10在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为 6,9,11,12 11. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是 m-1 ,若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是 m/2-1 。12. 直接定址法 法构造的哈希函数肯定不会发生冲突。 13. 高度为8的平衡二叉树的结点数至少有 54 个。 14. 高度为5（除叶子层之外）的三阶B-树至少有 31 个结点15.按12，24，36，90，52，30的顺序构成的平衡二叉树，其根结点是（ C ）。 A. 12 B. 24 C. 36 D. 5216. 输入序列为20，11，12，构造一棵平衡二叉树，当插入12时，应进行（ B ）型调整。 A. LL B. LR C. RR D.RL17. 一棵深度为K的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该平衡树共有 ( )个结点。18.一棵5阶的B树上，每个非终端结点所含子树最少 3 个第九章 复习题1某内排序方法的稳定性是指( D )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录 C平均时间为0（n log n）的排序方法 D以上都不对 2下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序3若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序4排序趟数与序列的原始状态有关的排序方法是( CD )排序法。 A插入 B. 选择 C. 冒泡 D. 快速5对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( B )。 A直接插入 B. 二分法插入 C. 快速排序 D. 归并排序 6数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。 A.选择排序 B.冒泡排序 C.插入排序 D.堆排序7数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序8对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( A )。 A. 选择 B. 冒泡 C. 快速 D. 插入9对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ C ）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡10若上题的数据经一趟排序后的排列为9，15，7，8，20，-1，4，则采用的是（ C ）排序。A选择 B. 堆 C. 直接插入 D. 冒泡 11下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 12一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B. (40,38,46,79,56,84) C(40,38,46,56,79,84) D. (40,38,46,84,56,7913下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆14. 就平均性能而言，目前最好的内排序方法是( D )排序法。A. 冒泡 B. 希尔插入 C. 交换 D. 快速 15下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序16从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并17. 在排序算法中，每次从未排序的记录中挑出最小关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆18将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( A ) AN B2N-1 C2N DN-