数据结构复习试题.docx

《数据结构复习试题.docx》由会员分享，可在线阅读，更多相关《数据结构复习试题.docx（16页珍藏版）》请在三一文库上搜索。

1、题目选至笫7章一、填空题(2分/题，共10题)1 .数据是指所有能够输入到计算机中被计算机加工、处理的符号的集合。2 .可以把计算机处理的数据，笼统地分成数值型和非数值型两大类。3 .数据的逻辑结构就是指数据间的邻接关系。10.从整体上看，数据在存储器有两种存放的方式：一是集中存放在一个连续的存存储区 中；一是利用存储器中的零星区域，分散地存放在存的各个地方。12.“基本操作”是指算法中那种所需时间与操作数的具体取值力L的操作。5 .不带表头结点的链表，是指该链表的表头指针直接指向该链表的起始结点。6 .在一个双链表中，已经由指针ptr指向需要删除的存储结点，则删除该结点所要执行的 两条操作是

2、 ptr-Prior-Next = ptr-Next； ptr-Next-Prior = ptr-Prior； 。7 .设tail是指向非空、带表头结点的循环单链表的表尾指针。那么，该锥表起始结点的存 储位置应该表示成tail-Next-Next。9.顺序表Sq= (al, a2, a3,，an) (nl)中，每个数据元素需要占用w个存储单元。 若m为元素al的起始地址，那么元素an的存储地址是m+(nT)*w。1 .限定插入和删除操作只能在一端进行的线性表，被称为是栈。2 .如果在顺序栈满时仍打算进行进梭操作，就称为发生了 “上溢”出错。3 .如果在顺序栈空时仍打算进行出栈操作，就称为发生了

3、 “下溢”出错。4 .在具有n个数据结点的循环队列中，队满时共有n-1个数据元素。5 .如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次 出栈；最后让字母G进栈，做三次出栈。最终这个雄栈从栈顶到栈底的余留元素应该是DA。6 .中缀表达式(a+b)- (c/(d+e)对应的后缀表达式是ab+cde+/-。7 .函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为直接递归调用; 如果一个函数是通过另一个函数来调用自己，就称其为间接递归调用。8 .设某栈的元素输入顺序是1、2、3、4、5,想得到4、3、5、2、1的输出顺序。那么push、 pop 的操作序列

4、应该是 push、push、push、push、pop、pop、push、pop、pop、pop。9 .设有串s= I am a teacher。该串的长度是14。10.在一个n阶方阵A中，若所有元素都有性质：aij = aji (Ki, jW n),就称其为对 称矩阵。1 .结点数为7的二叉树的高度最矮是2 ,最高是6。2 .给定二叉树的结点数，要使树高为最大，那么该树应该是单枝形状。3 .给定二叉树的结点数，要使树高为最矮，那么该树应该是完全二叉树形状。4 .如果一棵满二叉树的深度为6,那么它共有127个结点，有64个叶结点。5 .有15个结点的二叉树，最少有1个叶结点，最多有8个叶结点。

5、6 .由n个带权值的叶结点生成的哈夫曼树，最终共有2n-l个结点。9 .深度为5的二叉树，至多有31个结点。10 .在二叉树中，有一个结点具有左、右两个孩子。那么在中序遍历序列里，它的右孩子一 定排在它的右边。2 .在一个具有4个顶点的无向图中，要连通全部顶点，至少需要3条边。3 .在无向图中，若顶点上和V之间有一条边(V” V,/)存在，那么则称顶点。和打互为邻 接点。4 .图中顶点v,的“度”，是指与它相邻接的顶点的个数,并记为D(v,)。5 .在有向图中，把从顶点v,到顶点V.,的瓠记为 ,而把从顶点Vj到顶点v,的弧 记为 ,这是两条不同的狐。6 .而二T薪图，其邻接矩阵中第/行(或第

6、/列)里非零或非8元素的个数，正好是 第j个顶点V,的度。二、选择题(1分/题，共20题)1.在常见的数据处理中，B 是最基本的处理。A.删除 B.查找 C.读取 D.插入4 .链式存储结构中，每个数据的存储结点里上指向邻接存储结点的指针，用以反映数据间 的逻辑关系。A.只能有1个 B.只能有2个 C.只能有3个 D.可以有多个6 .有下面的算法段：for (i=0； iNext = NULLC. Lk h-Next = Lk h D. Lk h != NULL3 .带表头结点的单链表Lk h为空的判定条件是L。A. Lk h = NULLB. Lk h-Next = NULLC. Lk h-

7、Next = Lk hD. Lk h != NULL4 .往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动上个结点。A. n B. n!2C. 1 D. nA)/25 .在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点 和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是CA. rtr-Next = ptr-Next； ptr-Next = rtr；B. ptr-Next = rtr-Next；C.qtr-Nextrtr；rtr-Next = ptr；D.ptr-Next =rtr；1. 一个栈的元素进栈序列是A. d、 c、 b、

8、 aC. d、 c、 e、 a、 ba、rtr-Next = qtr-Next；b、c、d、e,那么下面的不能做为一个出栈序列。B. d、 e、 c、 b、 aD. a、 b、 c、 d、 e2 .判定一个顺序队列Qs （最多有个元素） A. Qs rear-Qs front = n*size C. Qs front = Qs_ rear3 .判定一个顺序队列Qs （最多有个元素） A. Qs rear-Qs front = n*size C. Qs front = Qs_ rear为空的条件是q。B. Qs rear-Qs D. Qs front = Qs 真满的条件是B. Qs_rear-

9、Qs D. Qs front = Qsfront+1 = n*size rear+sizefront+1 = n*size rear+size4 .在一个链式队列Lq中，Lq front和Lq rear分别为队首、队尾指针。现在由指针ptr 所指结点要进队，则插入操作应该是B oLq front = ptr；Lq rear = ptr； Lq rear = ptr； Lq front = ptr；A. Lq front-Next = ptr；B. Lq rear-Next = ptr； C. ptr-Next = Lqrear； D. ptr-Next = Lq front；5 .链栈与顺序栈

10、相比，一个较为明显的优点是工。A.通常不会出现栈空的情形 B.插入操作更加便利C.删除操作更加便利D.通常不会出现栈满的情形6 .向链栈插入一个结点时，操作顺序应该是C。A.先修改栈顶指针，再插入结点 B.无须修改栈顶指针C.先插入结点，再修改栈顶指针D.谁先谁后没有关系7 .从锥栈中删除一个结点时，操作顺序应该是jA.先保存被删结点的值，再修改栈顶指针8 .先修改栈顶指针，再保存被删结点的值C.无须修改栈顶指针的值D.谁先谁后没有关系8. 一个循环队列的最大容量为m+1, front为队首指针，rear为队尾指针。那么进队操作 时求队位号应该使用公式A. Cq front = (Cq_fro

11、nt+l)%mB. Cq_front = (Cq front+l)%(m+l)C. Cq rear = (Cq _rear+l)%m D. Cq rear = (Cq rear+l)%(m+l)9 .在一个循环顺序队列里，队首指针Cq/ront总是指向A.队首元素B.队首元素的前一个队位C.任意位置D.队首元素的后一个队位10 .若一个栈的进栈序列是1、2、3、4,那么要求出栈序列为3、2、1、4时，进、出栈操 作的顺序应该是工_。(注：所给顺序中，I表示进栈操作，。表示出栈操作)A. III000I0 B. I0I0I0I0 C. II00I0I0 D. I0III0004.设有一个8阶的对

12、称矩阵A,采用以行优先的方式压缩存储。a”为第1个元素，其存储 地址为1,每个元素占一个地址空间。试间元素呢的地址是A. 33 B. 30 C. 13 D. 235. 一个勿曲的对称矩阵，如果以行优先的方式压缩存入存。那么所需存储区的容量应 该是1 . /姓(z?rl)/2 B. mn/2 C. 声(加 1)/2 D.(研 1)*(研 1)/27 .二维数组M中的每个元素占用3个存储单元，行下标，.从1变到8,列下标j.从1变到 10。现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时，元素A85的起 始地址应该是C。A. SA+141 B. SA+180 C. SA+222 D.

13、SA+2258 .设有一个5阶上三角矩阵A,将其元素按列优先顺序存放在一维数组B中。已知每个元 素占用2个存储单元，Bl的地址是100。那么A34的地址是A。A. 116 B. 118 C. 120 D. 1226 .在一棵非空二叉树的中序遍历序列里，根结点的右边D结点。A.只有左子树上的部分B.只有左子树上的所有C.只有右子树上的部分D.只有右子树上的所有8 .权值为1、2、6, 8的四个结点，所构造的哈夫曼树的带权路径长度是D。A. 18 B. 28 C. 19 D. 299 . 一棵二叉树度2的结点数为7,度1的结点数为6。那么它的叶结点数是C。A. 6B. 7C. 8D. 910 .在

14、一棵二叉树中，第5层上的结点数最多是C个。A. 8B. 15C. 16D. 321.已知一棵单右支的二叉树，如下左图所示。把它还原成森林，应该是2.将一棵树Tr转换成相应的二叉树Bt,A.先序遍历 B.中序遍历那么对Tr的先序遍历是对Bt的.。C.后序遍历 D.无法确定0.00 03 .将一棵树Tr转换成相应的二叉树Bt,那么对Tr的后序遍历是对Bt的旦。A.先序遍历B.中序遍历 C.后序遍历 D.无法确定4 .设森林F中有3棵树，依次有结点0、m、个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是D。A. nB.C.小5 .设有由三棵树、12、L组成的森林，其结点个数分别为人、

15、2、小。与该森林相应的二 叉树为Bt。则该二叉树根结点的左子树中应该有结点个。A. n-l B. Di C. /7i+l D.6 .现有一棵度为3的树，它有两个度为3的结点，一个度为2的结点，两个度为1的结点。 那么其度为0的结点的个数应该是。A. 5 B. 8 C. 6 D. 9注意：有n个结点的树，树中所有结点的度之和为nT。现在这棵树应该满足条件：n-1 = 2*3 + 1*2 + 2*1 = 10这表示该树共有11个结点(加上一个根结点)。在11个结点里，减去度为3、2、1的结点 数5,剩下的就是度为0的结点。所以，该树有叶结点6个。7 . 一棵有个结点的树，在把它转换成对应的二叉树之

16、后，该二叉树根结点的左子树上共 有L个结点。A. /?-2 B. nl C.加1 D.8 . 一棵有个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共 有A个结点。A. 0B. nC.加1D.d21 .在一个有个顶点的无向图中，要连通全部顶点，至少需要C条边。A. nB. /t+1C. n1D. n/22 .对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有个 顶点的无向完全图包含有C条边。A.B. n(/+1)C. n(n-l)/2 D. (/?+1)/23 .对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条瓠。因此，有个 顶点的有向完全图

17、包含有A条边。A.B. (/+1)C. (/71)/2D. /?(/?+1)/24 .在一个无向图中，所有顶点的度数之和，是其所有边数之和的K 倍。A. 1/2 B. 1 C. 2 D. 45 .在一个有向图中，所有顶点的入度之和.所有顶点的出度之和。A.二分之一于 B.等于 C.两倍于 D.四倍于6 . 一个无向连通网图的最小生成树L。A.有一棵或多棵 B.只有一棵 C. 一定有多棵 D.可能不存在7 . 一个无向图有个顶点，那么该图拥有的边数至少是。A. 2/7B. nC. n/2D. 08 . 一个有个顶点的无向连通网图，其生成树里含有条边。A. 4/7-1B. 2/-1C. n-D.

18、n/2三、问答题(4分/题，共5题)1 .在一个单链表中，为了删除指针ptr所指的结点，有人编写了下面的操作序列。读懂并 加以理解。试问，编写者能够达到目的吗？其思想是什么？x = ptr-Data ；qtr = ptr-Next ；ptr-Data = ptr-Next-Data ；free (qtr)；答：能够达到删除指针ptr所指结点的目的。编写者的思想是不去直接删除ptr所指的 结点，而是在把ptr直接后继的Data域容写入ptr所指结点的Data域之后，把它的直接后 继删除。对于单链表来说，得到一个结点的直接后继容易，得到它的直接前驱难，所以这样 的设计是有其可取之处的。2 .在一个

19、单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人 编写了下面的操作序列，其中temp是一个临时工作单元。读懂并加以理解。试问，编写者 能够达到目的吗？其思想是什么？qtr-Next = ptr-Next ；ptr-Next = qtr ；temp = ptr-Data ；p-Data = qtr-Data ；qtr-Data = temp ；答：能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的。编写者的 思想是考虑到在单锥表中得到一个结点的前驱信息较为困难，因此在这里先把qtr所指结点 插入到ptr所指结点的后面，暂时成为它的直接后继。然后通过临时工

20、作单元temp,将ptr 及qtr所指结点的Data域容进行交换，从而达到插入的目的。4 .设有6个元素al、a2、a3、a4、a5、a6,它们以此顺序依次进栈。假定要求它们的出栈 顺序是a4、a3、a2、a6、a5、al,那么应该如何安排push和pop操作序列？答：所需的push和pop操作序列如下：push, push, push, push, pop, pop, pop, push, push, pop, pop, pop5 .有中缀表达式a/(b/(c/(d/e)o有人将其转化为相应的后缀表达式是 abcde/o这一转化结果对吗？答：转化结果是对的。7.分别写出如图5-32所示二叉树

21、的先序、中序、后序遍历序列。困5-32二又/示例答：先序遍历序列为：A-B-C-D-F-G-H-E,中序遍历序列为：B-A-D-G-F-H-C-E,后序遍历序列为：B-G-H-F-D-E-C-Ao3.有如图7-23所示的一个无向图，给出它的邻接短阵以及从顶点口出发的深度优先遍历 序列。答：它的邻接矩阵如图所示。从顶点打出发的深度优先遍历序列为Vl-V2-Vi-V5-V7-V6-V3注意，该序列是不唯一的。0000100 0 1 1 0 0 010 0 10 010 0 10 00 110 110 0 0 1 0 00 0 0 1 0 00 0 0 0 1 0四、应用题(6分/题，共5题)3.分

22、析算法段中标有记号和的基本操作的执行次数：for ( i=0； in； i+)for (j=0； jn； j+)(#i y=l；for (k=0； kn； k+)#2 y=y+l;的基本操作的执行答：标有记号“为”的基本操作的执行次数是：n2；标有记号”# 次数是:n%4.绐出下面3个算法段的时间复杂度：(1) x+；(2) for (j=l； jn； j+)x+；(3) for (j=l； j=n； j+)(printf ( j=% ， j):for (k=j; kNext ；qtr = Ck_h2 ；while ( ptr != NULL)(rtr = malloc (size)；rtr-

23、Data = ptr-Data ；qtr-Next - rtr ；qtr = rtr ；ptr = ptr-Next ；qtr-Next = NULL ；)5 .已知一个带表头结点的递赠单链表。试编写一个算法，功能是从表中去除值大于min、 且值小于max的数据元素。(假定表中存在这样的元素)答：所需算法编写如下。Del_Sq(Lk_h. min. max)(ptr = Lk_h-Next ；/ ptr指向链表的起始结点*/while ( (ptr != NULL) & (ptr-Data = min) )/* 跳过所有值Next ；while ( (ptr != NULL) & (ptr-D

24、ata Next ；qtr-Next = ptr ；/* qtr指出第1个大于max的结点位置，完成/)6 .已知一个带表头结点的无序单集表。试编写一个算法，功能是从表中去除所有值大 于min、且值小于max的数据元素。答：所需算法编写如下，其中指针ptr总是指向当前被检查的结点，qtr总是指向被检 查结点的直接前驱。Del_Lk (Lk_h. min. max)while (ptr != NULL)/*扫视直到链尾结点*/if ( (ptr-Data Data = max) /* 不满足删除条件/ | qtr = ptr ;/往后移动 qtr 和 ptr */ptr = ptr-Next ；

25、 ) else/删除ptr所指结点，往后移动ptr /( qtr-Next = ptr-Next ； free (ptr)； ptr = qtr-Next ； ) )7. 一个单链表Lk的表头指针为Lk h,不同结点的Data域值有可能相同。编写一个算法， 功能是计算出Data域值为x的结点的个数。答：算法应该遍历链表的每一个结点，遇到一个结点的Data域值为x时，计数器n就 加U最后返回计数器n。Count_Lk (Lk_h) (n = 0 ； ptr = Lk_h ； while (ptr != NULL) (if (ptr-Data x) n = n+1 ；ptr 二 ptr-Next

26、return (n)； )3.编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列首元素的值，只有在队列非空的前途下才有意义。算法编写如下。 Ge t f_Lq (Lq_ fron t. Lq_rear) ( if (Lq_front = Lq_rear)/队列空！ /printf ( The I i nked queue is empty!”)； else/*队列非空！ /ptr = Lq_front-Next ； x = ptr-Data ； return (x)；)5.将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地，要开辟一个运 算符栈op和一个数组st。在自左至

27、右扫描算术表达式时，遇到操作数就直接顺序存入st； 遇到运算符时就与。P栈顶元素比较，高则进栈，不高则让栈顶元素出栈，存入S3然后该 运算符再次去与新的op栈顶元素比较。最后，在数组st里形成所需要的后缀表达式。试用 这种方法，用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。答：相应的后缀表达式是583*+2-，其图示如下。(b)(c)(h)4.编写一个算法，将顺序串St中所有的大写字母全部换成小写字母。(提示：大写英文字 母A、Z对应的ASCII码为6590,小写英文字母Gz对应的ASCII码为97、122,在大写字母 的ASCH码上加32,就是对应小写字母的ASCH码) 答：算法

28、编写如下。Catosm_St(St) ( for (i=l； i=St_len； i+) if (A=Sti)&(Sti=Z) Sti=Sti+32；)8.已知两个勿的矩阵A和及编写一个算法，求OA+B。即C也是一个mx 的矩阵，其 元素满足条件：Cjj = a” + b,/ (1 W/Wm, 1W 答：算法名为Add_Mt(),参数为A, B, Co Add_Mt(A, B, C) ( for (i=l； i=m； i+) for (j=l; j v- vr v5- v2- v6树。5 .已知无向连通网的邻接矩阵如下所示，试画出该无向连通网以及所对应的最小生成0 1 12 5 10-1089812 8 0 oo 25 9 8()4.10 8 2 4 0.