数据结构复习试题

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

2、tr->Prior->Next = ptr->Next; ptr->Next->Prior = ptr->Prior;。7. 设tail是指向非空、带表头结点的循环单链表的表尾指针。那么，该链表起始结点的存储位置应该表示成 tail->Next->Next 。9. 顺序表Sq = (a1 , a2, a3,，an) (n?1)中，每个数据元素需要占用w个存储单元。假设m为元素a1的起始地址，那么元素an的存储地址是 m+(n_1)*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. 函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为 直接 递归调用;如果一个函数是通过另一个函数来调用自己，就称其为间接 递归调用。&设某栈的元素输入顺序是1、2、3、4、5

4、,想得到4、3、5、2、1的输出顺序。那么push、pop 的操作序歹卩应该是 push、push、push、push、pop、pop、push、pop、pop、pop。5. 设有串s= “I am a teacher "。该串的长度是 14 。10. 在一个n阶方阵A中，假设所有元素都有性质：aij = aji (1< i, j < n),就称其为 对称矩阵。1 .结点数为7的二叉树的高度最矮是2 ，最高是6。2. 给定二叉树的结点数，要使树高为最大，那么该树应该是单枝 形状。3 给定二叉树的结点数，要使树高为最矮，那么该树应该是完全二叉树 形状。4. 如果一棵满二叉树

5、的深度为6，那么它共有127个结点，有64个叶结点。5. 有15个结点的二叉树，最少有 1个叶结点，最多有 8个叶结点。6. 由n个带权值的叶结点生成的哈夫曼树，最终共有2n-1个结点。9. 深度为5的二叉树，至多有 31个结点。10. 在二叉树中，有一个结点具有左、右两个孩子。那么在中序遍历序列里，它的右孩子一定排在它的右边。2. 在一个具有4个顶点的无向图中，要连通全部顶点，至少需要 丄条边。3. 在无向图中，假设顶点 Vi和Vj之间有一条边(Vi , Vj)存在，那么那么称顶点 Vi和Vj互为 邻 旦点。4. 图中顶点Vi的“度，是指与它 相邻接 的顶点的个数，并记为 D(vi)。5.

6、在有向图中，把从顶点 Vi到顶点V的弧记为 Vi, vj ，而把从顶点Vj到顶点Vi的弧 记为 V j , Vi二，这是两条不同的弧。6. 对于一个无向图，其邻接矩阵中第i行(或第i列)里非零或非R元素的个数，正好是 第i个顶点Vi的度。二、选择题(1分/题，共20题)1. 在常见的数据处理中，_B_是最根本的处理。A删除B.查找C.读取D.插入4. 链式存储结构中，每个数据的存储结点里_D指向邻接存储结点的指针，用以反映数据间的逻辑关系。A. 只能有1个 B .只能有2个 C .只能有3个D.可以有多个6. 有下面的算法段：for (i=0; in; i+)k+;其时间复杂度为_B_。2A.

7、 Q1)B. Qn) C . Olog 2n)D. Qn )1. 下面，对非空线性表特点的论述，C_是正确的。A所有结点有且只有一个直接前驱B. 所有结点有且只有一个直接后继C. 每个结点至多只有一个直接前驱，至多只有一个直接后继D. 结点间是按照1对多的邻接关系来维系其逻辑关系的2. 一般单链表Lk_h为空的判定条件是_A_。A Lkh = NULL B . Lk h->Next = NULLC. Lk_h->Next = Lk_hD. Lk_h != NULL3. 带表头结点的单链表Lk_h为空的判定条件是 B_。A Lk_h = NULL B . Lk_h->Next

8、= NULLC. Lk_h->Next = Lk_hD. Lk_h != NULL4. 往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B个结点。A nB. n/2C. n+1D . n +1/ 25.在一个单链表中，qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是A rtr->Next = ptr->Next;ptr->Next = rtr;B.ptr->Next = rtr->Next;C. qtr->Next = rtr;rtr->Next = p

9、tr;C.D. ptr->Next = rtr; 个栈的元素进栈序列是A e、d、c、b、a d、c、e、a、 ba、b、D. a、b、判定一个顺序队列 Qs 最多有nA Qs rear-Qs front = n*sizertr->Next = qtr->Next;c、d、e,那么下面的B. d、e、c、b、ad、e个元素为空的条件是B . QsC不能做为一个出栈序列。rear-Qs front+1 = n*sizeC.Qs_front = Qs_rearD . Qs_front = Qs_rear+size判定一个顺序队列 Qs 最多有n个元素真满的条件是A Qs rear

10、-Qs front = n*sizeB . Qs rear-Qs front+1 = n*sizeC. Qs_front = Qs_rearD . Qs_front = Qs_rear+sizeptr4. 在一个链式队列Lq中，Lq_front和Lq_rear分别为队首、队尾指针。现在由指针所指结点要进队，那么插入操作应该是B。A Lq_fr on t->Next = ptr; Lq_fr ont = ptr;B . Lq_rear->Next = ptr; Lq_rear = ptr;C. ptr->Next = Lq_rear; Lq_rear = ptr;D. ptr-

11、>Next = Lq_fr ont; Lq_fr ont = ptr;5. 链栈与顺序栈相比，一个较为明显的优点是D_。A通常不会出现栈空的情形B.插入操作更加便利C.删除操作更加便利D .通常不会出现栈满的情形6. 向链栈插入一个结点时，操作顺序应该是C_。A先修改栈顶指针，再插入结点B .无须修改栈顶指针C.先插入结点，再修改栈顶指针D.谁先谁后没有关系7. 从链栈中删除一个结点时，操作顺序应该是A_。A先保存被删结点的值，再修改栈顶指针B. 先修改栈顶指针，再保存被删结点的值C. 无须修改栈顶指针的值D. 谁先谁后没有关系& 一个循环队列的最大容量为m+1, fro nt为

12、队首指针，rear为队尾指针。那么进队操作时求队位号应该使用公式D_。A Cq_front = (Cq_front+1)%mB. Cq_front = (Cq_front+1)%(m+1)C. Cq_rear = (Cq_rear+1)%mD. Cq_rear = (Cq_rear+1)%(m+1)9. 在一个循环顺序队列里，队首指针Cq_front总是指向_B_。A队首元素B.队首元素的前一个队位C.任意位置D.队首元素的后一个队位10. 假设一个栈的进栈序列是1、2、3、4,那么要求出栈序列为 3、2、1、4时，进、出栈操 作的顺序应该是 A_。(注：所给顺序中，I表示进栈操作，0表示出栈

13、操作)A IIIOOOIO B. IOIOIOIO C. IIOOIOIO D. IOIIIOOO4.设有一个8阶的对称矩阵 A,采用以行优先的方式压缩存储。an为第1个元素，其存储地址为1，每个元素占一个地址空间。试问元素a85的地址是_A_。A 33B. 30C. 13D. 235. 一个m*m的对称矩阵，如果以行优先的方式压缩存入存。那么所需存储区的容量应 该是_C_。Arrf(m1)/2B.m*r/2C.n*( m+1)/2D.(m+1)*(m+1)/27. 二维数组 M中的每个元素占用 3个存储单元，行下标i从1变到8,列下标j从1变到 10。现从首地址为SA的存储区开始存放 A。那

14、么该数组以行优先存放时， 元素A85的起 始地址应该是C 。A SA+141B. SA+180C SA+222D. SA+225&设有一个5阶上三角矩阵A,将其元素按列优先顺序存放在一维数组B中。每个元素占用2个存储单元，B1的地址是100。那么A34的地址是A。A 116B. 118C. 120D. 1226. 在一棵非空二叉树的中序遍历序列里，根结点的右边 D结点。A.只有左子树上的局部 B.只有左子树上的所有C.只有右子树上的局部D.只有右子树上的所有&权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是D。A. 18B . 28C. 19D . 299. 一

15、棵二叉树度2的结点数为7,度1的结点数为6。那么它的叶结点数是 C。A. 6B . 7C. 8D . 9 10 .在一棵二叉树中，第 5层上的结点数最多是 C个。A. 8B . 15C. 16D . 321 .一棵单右支的二叉树，如下左图所示。把它复原成森林，应该是_D_。D .2. 将一棵树Tr转换成相应的二叉树Bt，那么对Tr的先序遍历是对 Bt的_A_。A先序遍历B.中序遍历C.后序遍历D.无法确定3. 将一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对 Bt的_B_。A先序遍历B.中序遍历C.后序遍历D.无法确定4. 设森林F中有3棵树，依次有结点n1、n2、ns个。把该森林

16、转换成对应的二叉树后，该二叉树的右子树上的结点个数是D。A . n1B . n计 n2C. naD .n2+n35. 设有由三棵树 、T2、T3组成的森林，其结点个数分别为n、住、n3。与该森林相应的二叉树为Bt。那么该二叉树根结点的左子树中应该有结点A个。A ni-1B. n C. n 1+1D. ni+n26 现有一棵度为3的树，它有两个度为3的结点，一个度为2的结点，两个度为1的结点。 那么其度为0的结点的个数应该是_C_。A 5B. 8C. 6D. 9注意：有n个结点的树，树中所有结点的度之和为n-1。现在这棵树应该满足条件：n-1 = 2*3 + 1*2 + 2*1 = 10这表示该

17、树共有11个结点(加上一个根结点)。在11个结点里，减去度为3、2、1的结点数5,剩下的就是度为 0的结点。所以，该树有叶结点6个。7. 一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共 有B_个结点。A n-2B. n-1C. n+1D. n+2& 一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共 有A_个结点。A 0B .nC.n+1D.n+21 .在一个有n个顶点的无向图中，要连通全部顶点，至少需要C_条边。A nB.n+1C.n-1D.n/22. 对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个

18、顶点的无向完全图包含有C_条边。A n( n-1)B. n( n+1)C. n(n-1)/2D. n(n+1)/23. 对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个 顶点的有向完全图包含有 A_条边。A n( n-1)B. n( n+1)C. n(n-1)/2D. n(n+1)/24. 在一个无向图中，所有顶点的度数之和，是其所有边数之和的C_倍。A 1/2B. 1C. 2D. 45. 在一个有向图中，所有顶点的入度之和旦所有顶点的出度之和。A二分之一于B.等于C.两倍于D.四倍于6. 一个无向连通网图的最小生成树A_。A有一棵或多棵B.只有一棵C. 一定有多棵

19、D.可能不存在7. 一个无向图有 n个顶点，那么该图拥有的边数至少是D。A 2nB. nC. n/2D. 0& 一个有n个顶点的无向连通网图，其生成树里含有C条边。A 4n-1B. 2n-1C. n-1D.n/2三、问答题(4分/题，共5题)1 .在一个单链表中，为了删除指针 ptr所指的结点，有人编写了下面的操作序列。读懂并 加以理解。试问，编写者能够到达目的吗？其思想是什么？x = ptr->Data ;qtr = ptr->Next ;ptr->Data = ptr->Next->Data ;ptr->Next = ptr->Next-&

20、gt;Next ;free (qtr);答：能够到达删除指针 ptr所指结点的目的。编写者的思想是不去直接删除 ptr所指的 结点，而是在把ptr直接后继的Data域容写入ptr所指结点的Data域之后，把它的直接后 继删除。对于单链表来说，得到一个结点的直接后继容易，得到它的直接前驱难，所以这样的设计是有其可取之处的。2 在一个单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人编写了下面的操作序列，其中temp是一个临时工作单元。读懂并加以理解。试问，编写者能够到达目的吗？其思想是什么？qtr->Next = ptr->Next ;ptr->Next

21、 = qtr ;temp = ptr->Data ;p->Data = qtr->Data ; qtr->Data = temp ;答：能够到达在指针ptr所指结点之前插入一个由指针 qtr所指结点的目的。编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难，因此在这里先把qtr所指结点插入到ptr所指结点的后面，暂时成为它的直接后继。 然后通过临时工作单元 temp,将ptr 与qtr所指结点的Data域容进行交换，从而到达插入的目的。4. 设有6个元素al、a2、a3、a4、a5、a6，它们以此顺序依次进栈。假定要求它们的出栈 顺序是a4、a3、a2、a6、

22、a5、al，那么应该如何安排 push和pop操作序列？答：所需的push和pop操作序列如下：push, push, push, push, pop, pop, pop, push, push, pop, pop, pop5. 有中缀表达式 a / ( b / ( c / ( d / e )。有人将其转化为相应的后缀表达式是abcde/ 。这一转化结果对吗？答：转化结果是对的。7分别写出如图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-A 。V1出发

23、的深度优先遍历3. 有如图7-23所示的一个无向图，给出它的邻接矩阵以与从顶点 序列。答：它的邻接矩阵如下列图。从顶点vi出发的深度优先遍历序列为:V1->V 2->V 4->V 5->V 7->V 6->V 3注意，该序列是不唯一的。 0 1 1 0 0 0 0*1 D 0 10 0 01 0 0 10 0 00 1 1 0 1 1 00 0 0 10 0 1o a o loooo d a a i o o四、应用题(6分/题，共5题)3. 分析算法段中标有记号“#1 和“ #2的根本操作的执行次数：for ( i=0; i<n; i+)for (j=

24、0; j< n; j+)# i y=i;for (k=0; k<n; k+)#2 y=y+1;#2 的根本操作的执行答：标有记号“ #i的根本操作的执行次数是：n2;标有记号次数是：n3。4. 给出下面3个算法段的时间复杂度：(1) x+；(2) for (j=1; j<n; j+)x+;(3) for (j=1; j<=n; j+) printf (“j=% , j);for (k=j; k<=n; k+)x+;答：(1的时间复杂度为0(1)；(2) 的时间复杂度On);(3) 中“ printf ( “ j =% , j );"执行次数的数量级为Qn

25、), “x+;"执行次数是：n+( n-1)+( n-2)+ +2+1 = n(n+1)/2其数量级为 Qn2)，因此整个算法段的时间复杂度应该是On2)。4. 试设计一个算法copy (Ck_h1, Ck_h2)，将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的容，复制到一个不带表头结点的、以Ck_h2为表头指针的单链表Ck2中。答：算法具体如下。Copy (Ck_h1, Ck_h2)ptr = Ck_h1->Next ;qtr = Ck_h2 ;while ( ptr != NULL)rtr = malloc (size);rtr->Data = ptr-&

26、gt;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) )/* 跳过所有值 <=min 的结点 *

27、/qtr = ptr ;ptr = ptr->Next ;while ( (ptr != NULL) && (ptr->Data <max) )/* 假设结点值 vmax,那么去除 */p = p->Next ;qtr->Next = ptr ;/* qtr 指出第1个大于 max的结点位置，完成 */6一个带表头结点的无序单链表。试编写一个算法，功能是从表中去除所有值大 于min、且值小于 max的数据元素。答：所需算法编写如下，其中指针ptr总是指向当前被检查的结点， qtr总是指向被检查结点的直接前驱。Del_Lk (Lk_h, min, m

28、ax)ptr = Lk_h->Next ;/* ptr指向单链表的起始结点*/while (ptr != NULL)/*扫视直到链尾结点 */if ( (ptr->Data <= min) | (ptr->Data >= max)/* 不满足删除条件 */qtr = ptr ;/* 往后移动 qtr 和 ptr */ptr = ptr->Next ;else/*删除ptr所指结点，往后移动ptr */qtr->Next = ptr->Next ;free (ptr);ptr = qtr->Next ;7. 个单链表Lk的表头指针为Lk_h，

29、不同结点的Data域值有可能相同。编写一个算法, 功能是计算出Data域值为x的结点的个数。答：算法应该遍历链表的每一个结点，遇到一个结点的Data域值为x时，计数器加1。最后返回计数器n。Count_Lk (Lk_h)n = 0 ;ptr = Lk_h ;while (ptr != NULL)if (ptr->Data = x)n = n+1 ;ptr = ptr->Nextreturn (n);3.编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列首元素的值，只有在队列非空的前途下才有意义。算法编写如下。Getf_Lq(Lq_front, Lq_rear)if (Lq

30、_front = Lq_rear)/* 队列空！ */printf (“ The linked queue is empty! );else/*队列非空！ */ptr = Lq_front->Next ;x = ptr->Data ;return (x);5. 将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值。具体地，要开辟一个运 算符栈op和一个数组st。在自左至右扫描算术表达式时，遇到操作数就直接顺序存入st ；遇到运算符时就与 op栈顶元素比拟，高那么进栈，不高那么让栈顶元素出栈，存入st，然后该运算符再次去与新的 op栈顶元素比拟。最后，在数组st里形成所需要的后缀表

31、达式。试用这种方法，用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式。答：相应的后缀表达式是583*+2-，其图示如下。(b)c)凹st ap st op st op st op_ 丄 _ 二 亘 訂T Q(0(0傅(h)4 .编写一个算法，将顺序串 St中所有的大写字母全部换成小写字母。(提示：大写英文字母AZ对应的ASCII码为6590,小写英文字母 az对应的ASCII码为97122,在大写字母 的ASCII码上加32,就是对应小写字母的 ASCII码)答：算法编写如下。Catosm_St(St)for (i=1; i<=St_len; i+)if (A<=S ti)

32、&&(Stiv=Z)Sti=Sti+32;&两个 mx n的矩阵A和B。编写一个算法，求 C=A+B即C也是一个 mx n的矩阵，其 元素满足条件：cij = a ij + b ij (1 w i < m 1 w j w n)答：算法名为 Add_Mt()，参数为A, B, CoAdd_Mt(A, B, C)for (i=1; i<=m; i+)for (j=1; j<=n; j+)Cij = Aij + Bij;2.中序遍历序列为：A-B-C-E-F-G-H-D，后序遍历序列为：A-B-F-H-G-E-D-C。试画出这棵二叉树。6. 权值序列为：10、16、20、6、30、24,请用图示来表达构造一棵哈夫曼树的全过程。 答：构造这棵哈夫曼树的全过程如下所示。3.将图6