数据结构复习题集【耿国华(第二版)版C语言描述】.pdf
《数据结构复习题集【耿国华(第二版)版C语言描述】.pdf》由会员分享,可在线阅读,更多相关《数据结构复习题集【耿国华(第二版)版C语言描述】.pdf(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-第一章 复习题1简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。答:在顺序结构中,逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中,数据元素之间关系是由结点中指针指示的。2.数据结构是一门的学科。.在数据结构中,从逻辑上可以把数据结构分成()。A、动态结构与静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构编写一个函数,用不多于n/的平均比较次数,在一个数组中找出最大和最小值元素。id mmin(int,it)ax=mina0;for(i1;n;+)i(aimax)mx=a;ese if(a=)。A表元素B字符.数据元素D.数据项4.
2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。A.顺序表B单循环链表C带头结点的双循环链表双链表5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用-(D)存储方式最节省运算时间。.单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表6若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(D)存储方式最节省运算时间。.单链表B.双向链表单循环链表D.带头结点的双向循环链表7.链表不具有的特点是(B).插入、删除不需要移动元素B可随机访问任一元素 不必事先估计存储空间D.所
3、需空间与线性长度成正比8.下面的叙述不正确的是(BC).线性表在链式存储时,查找第i个元素的时间同i的值成正比B.线性表在链式存储时,查找第个元素的时间同i 的值无关C.线性表在顺序存储时,查找第 i 个元素的时间同 i的值成正比D 线性表在顺序存储时,查找第 i 个元素的时间同的值无关9.若长度为的线性表采用顺序存储结构,在其第i 个位置插入一个新元素的算法的时间复杂度为(C)(1=inex=eadB.p-net=NULLCp=NULp=head1.循环链表的尾结点的特点是(A)。AP-NEX=BP-NEXT=H-NTP=HD.P=H-NET.41完成在双循环链表结点p 之后插入 s 的操作
4、是(D);p-next=s;s-priorp;p-nexrior=s;snext-nex;pext-pios;p-next=s;s-pir=p;s-next=p-nxt;C.s-pri;s-net=p-net;-net=s;-ext-rior=s;D.s-prir=;sextnet;p-nxtprir=s;p-nxt=;15.在双向循环链表中,在指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是(D)。A-prirq;q-nextp;ppiornext=q;q-pro=p-prior;B.q-prior=p-prir;-po-next=q;-ext=p;ppror=nex;-C
5、.-nxt=p;p-next=q;-rr-x=;-n=p;.p-rio-ex=q;-next=;q-prio=prior;pprior=q;16在单链表指针为 p 的结点之后插入指针为的结点,正确的操作是:()。Ap-nex=s;-nxt=-x;.-next=-nex;p-nex=;C.-nxt=;pnext=snex;D pnet=s-ne;p-next=s;1.对于一个头指针为 had 的带头结点的单链表,判定该表为空表的条件是()Ahead=ULLB.Head-ne=NULLC.Head-net=headDead!=UL18在双向链表中,删除p 所指的结点时须修改指针(A)。A p-pr
6、irnexp-next;-xt-rio=p-por;B.pprir=-prior-prior;p-ror-xt=p;C-nextror=p;p-n=ne-nextD.pnext=p-piorrior.-pror=next-ext;1 当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用顺序存储结构。0线性表 L=(1,a2,n)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是(-1)/21.设单链表的结点结构为(data,next),nx为指针域,已知指针 px 指向单链表中 dta为 x 的结点,指针指向 d为
7、的新结点,若将结点插入结点x 之后,则需要执行以下语句:py-extpx-xt;p-x=py22.在一个长度为的顺序表中第 i 个元素(1nex=qnex;fre();7.带头结点的双循环链表L 中只有一个元素结点的条件是:L-nex-xt=8 在单链表中,指针所指结点有后继结点的条件是:pnxt!=ull29带头结点的双循环链表为空表的条件是:L-ex=L&-prior=3.在单链表 p 结点之后插入 s 结点的操作是:s-nexp-next;p-net=s;第三章 复习题1.一个栈的输入序列为 12n,若输出序列的第一个元素是n,输出第 i(1=0)if(*man)*a=An;(*inn)
8、mnn;MnaVale(,-1,mx,min);/算法结束算法调用格式 MiMaxValue(r,n,&max,mi);arr 是具有个整数的一维数组,ma=2768 是最大数的初值,min327是最小数的初值。i maxmin(int A,int*max,i*_n,intlow,ntigh)i((ig-low)lo)*max=hi;*e_minAl;le*_max=Aw;_inhigh;lsem=(lwigh)/2;-maxmn(,&1,y1,lw,mid);n(,&2,&y2,d+1,ih);*_max=max(x1,x);*e_min=min(y,y2);第六章复习题1.算术表达式 a+
9、b*(c+/e)转为后缀表达式后为(B).ade*Bbde/+*C.abcde/*.abde*/+2 设树 T 的度为 4,其中度为,2,和 4 的结点个数分别为 4,2,1,1则中的叶子数为()A.B.6.783.设森林对应的二叉树为B,它有个结点,B 的根为 p,p 的右子树结点个数为n,森林 F中第一棵树的结点个数是(A).m-nBm-n-C.m-+.条件不足,无法确定 若一棵二叉树具有 10 个度为 2 的结点,个度为 1 的结点,则度为的结点个数是(B)9B11.1不确定5设森林F 中有三棵树,第一,第二,第三棵树的结点个数分别为,M2 和3。与森林 F对应的二叉树根结点的右子树上的
10、结点个数是(D)。A.M1.+MC.M3D.M2M6.一棵完全二叉树上有 10个结点,其中叶子结点的个数是(C)A49.500.5.057.设给定权值总数有 n 个,其哈夫曼树的结点总数为(D)不确定B.2nCn+1.2n18.有关二叉树下列说法正确的是(B)A二叉树的度为 2.一棵二叉树的度可以小于C二叉树中至少有一个结点的度为2二叉树中任何一个结点的度都为29.一个具有025 个结点的二叉树的高为()111 至 125 之间B.0D1至 14 之间10.一棵二叉树高度为 h,所有结点的度或为 0,或为,则这棵二叉树最少有()结点AhB.h-1-C2h+1D.h+11.对于有 n 个结点的二
11、叉树,其高度为().nlog2n.loCo2n|+1D不确定1高度为 K 的二叉树最大的结点数为(B)。2B.2k1C2 1 D2k-1-113.一棵树高为 K 的完全二叉树至少有(C)个结点.A.k1.2k-1 1.k1D.21.利用二叉链表存储树,则根结点的右指针是(C)。.指向最左孩子B.指向最右孩子C空D非空15.对二叉树的结点从 1 开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用(C)次序的遍历实现编号。A先序.中序.后序D.从根开始按层次遍历6树的后根遍历序列等同于该树对应的二叉树的(B).A.先序序列B.
12、中序序列C.后序序列7 若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用()遍历方法最合适。A.前序B中序C.后序D.按层次18已知一棵二叉树的前序遍历结果为ABCE,中序遍历结果为 CEDF,则后序遍历的结果为(A)。ACBEDAB FDCBA.EDD.不定19.对于前序遍历与中序遍历结果相同的二叉树为(F);对于前序遍历和后序遍历结果相同的二叉树为(B)。A.一般二叉树B只有根结点的二叉树根结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子数的二叉树F.所有结点只有右子树的二叉树20.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(
13、C)A.所有的结点均无左孩子B.所有的结点均无右孩子-C.只有一个叶子结点D.是任意一棵二叉树21.一棵左子树为空的二叉树在先序线索化后,其中空的链域的个数是:(D)A.不确定B.0C.1.222 一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是:(B)。A.0B 1C.2.不确定2.若 X 是二叉中序线索树中一个有左孩子的结点,且 X 不为根,则的前驱为(C)AX 的双亲.X 的右子树中最左的结点CX 的左子树中最右结点D.X 的左子树中最右叶结点24.引入二叉线索树的目的是(A)A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除.为了能方便的找到双亲D
14、.使二叉树的遍历结果唯一25个结点的线索二叉树上含有的线索数为(C)2nB-Cn+Dn6.由 3 个结点可以构造出多少种不同的二叉树?(D).B4D57.设 F 是一个森林,是由 F 变换得的二叉树。若 F 中有个非终端结点,则 B 中右指针域为空的结点有(C)个。A n-1.C.n+1Dn8下面几个符号串编码集合中,不是前缀编码的是()。A,1,110,111B.11,10,001,11,0001C.0,010,110,1000D,c,aa,a,a,abb,ab9.一棵有 n 个结点的二叉树,按层次从上到下,同一层从左到右顺序存储在一维数组1.中,则二叉树中第 i 个结点(i 从 1 开始用
15、上述方法编号)的右孩子在数组A 中的位置是(D)A.A2i(=n).A2i+1(2+)Ci-条件不充分,无法确定30.若以,6,7,8作为叶子结点的权值构造哈夫曼树,则其带权路径长度是69_。具有 n 个结点的满二叉树,其叶结点的个数是(n+1)/_。3.树的孩子兄弟表示法存储,可以将一棵树转换为_二叉树。3 8 层完全二叉树至少有_128_个结点,拥有 10个结点的完全二叉树的最大层数为_。35如某二叉树有 20 个叶子结点,有0 个结点仅有一个孩子,则该二叉树的总结点数为-_69_。36 已知一棵度为 3 的树有 2 个度为 1 的结点,3 个度为 2 的结点,4 个度为 3 的结点,则该
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 耿国华第二版版C语言描述 数据结构 复习题 国华 第二 语言 描述
限制150内