数据结构习题课与中期复习题.doc

《数据结构习题课与中期复习题.doc》由会员分享，可在线阅读，更多相关《数据结构习题课与中期复习题.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题课与复习典型题讲解一、解答与应用类1. 对于下图所示二叉树：完成1）写出中序遍历序列，并在树上画出（加上）中序遍历线索；2）将原二叉树转换为森林（8分）2. 若一报文系统所采用的字符集为A，B，E，F，S，T，各字符的使用频度分别为：0.19, 0.11, 0.09, 0.25, 0.18, 0.15。拟以这些字符构建一报文系统，要求完成：1) 画出构造好的Huffman编码树（构造过程可不画，只画最终构造好的的Huffman树；要求：在构造Huffman树的过程中，当用两棵子树构造一棵新树时，根结点权值小者作为左子树）； （6分）；2) 画出所构造Huffman树的静态三叉链表存储结构（

2、4分）；3) 写出报文字符集中各字符对应的Huffman编码（4分）；4) 若接收的某报文编码串为：，请将其翻译成对应的报文原文（2分）。3假设一棵二叉树的先序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK，画出其对应的二叉树。（举一反三：由输的先根和后根遍历序列，画出其对应的树）4. 证明任意二叉树度为0的结点个数与度为2的结点个数相差1；5. 分别画出广义表A=（a, b, （c, d）的两种存储结构图（头尾链表和扩展线性链表）；6. 分析以下程序的复杂度 i=1; while(ilink; P=list; i=1; while(P1) P1=P1-link; i+

3、; if(ik) p=p-next; /如果ik,则p也往后移 if(p=list)return 0; /说明链表没有k个结点 else printf(“%dn“,p-data); return 1; （3）时间复杂度O(n),空间复杂度O(1)二、算法类习题1、中序遍历二叉树的递归算法void InOrder(BiTree root) /中序遍历二叉树（假设二叉树结点数据元素类型为字符型）, root为指向二叉树/(或某一子树)根结点的指针if (root!=NULL)InOrder(root -LChild); /中序遍历左子树(1) /访问或输出根结点(2) /中序遍历右子树答案： Vi

4、sit(root -data); 或 printf(%c ,root -data); InOrder(root -RChild); 2、在带头结点的单链表中，删除一个结点的算法int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/ Node *pre,*r;int k;pre=L;k=0;while(pre-next!=NULL & k next) /* 即while循环是因为p-next=NULL或inext; （2）r=pre-next;（3）pre-next=pre-next-next

5、; （4）*e = r-data;（5）free(r);3、int StrIndex(SString s,int pos, SString t) / *求从主串s的下标pos起，串t第一次出现的位置，成功返回位置序号，不成功返回-1* / int i,j; if (t.len=0) return(0); i=pos; j=0; while (i =t.len) return(i-j); else return(-1);答案：（1）j t.len （2）s.chi=t.chj（3）i-j+1复习提醒：线性表（即顺序表和链表存储结构）的结点插入和删除算法；顺序栈和链栈的出（入）栈操作算法；循环队列

6、的出入队操作算法；字符串的字串查找和匹配算法；二叉树的遍历算法均应认真阅读和理解，关键的操作语句应记忆。3、选择类习题1）执行下面程序段时，执行S语句的次数为- for(int I=1;I=n;I+) for(int j=1;jprior=q;q-next=p;p-prior-next=q;q-prior=q;(B) p-prior=q;p-prior-next=q;q-next=p;q-Prior=p-prior;(C) q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;(D) q-prior=p-prior;q-next=q;p-prior

7、=q;p-prior=q;答案：C 7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 (A) 线性表的顺序存储结构 (B) 队列 (C) 线性表的链式存储结构 (D) 栈答案：D 8) 若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 (A) top=top+1; V top=x (B) V top=x; top=top+1 (C) top=top-1; V top=x (D) V top=x; top=top-1答案：C 9）若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除

8、一个元素，再加入两个元素后，rear和front的值分别为多少？( ) (A) 1和 5 (B) 2和4 (C) 4和2 (D) 5和1答案：B10）设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。 (A) fedcba (B) bcafed (C) dcefba (D) cabdef 答案：D 11）假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（ ）。 (A) 808 (B) 818 (C) 1010 (D) 1020答案：B 12）数组A0.4,-1.-3,5.7中含

9、有元素的个数（ ）。 (A) 55 (B) 45 (C) 36 (D) 16 答案：B 13）AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。 (A) i（i-1）/2+j (B) j（j-1）/2+i (C) i（j-i）/2+1 (D) j（i-1）/2+1 答案：B14）对稀疏矩阵进行压缩存储目的是（ ）。 (A) 便于进行矩阵运算 (B) 便于输入和输出 (C) 节省存储空间 (D) 降低运算的时间复杂度答案：C15) 对广义表L=(a,()执行操作tail(L)的结果是( ) (A) () (B)

10、 () (C) a (D) (a)答案：B 16) 具有10个叶结点的二叉树中至少有（ ）个度为2的结点 (A) 8 (B) 9 (C) 10 (D) 11答案：B 17）当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 Al.n中时，数组中第i个结点的左孩子为（ ） (A) A2i(2i=N) (B) A2i+1(2i+1= n) (C) Ai/2 (D) 无法确定答案：D18）二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是( )(A) E (B) F (C) G (D) H答案：C19）由3 个结

11、点可以构造出多少种不同的二叉树？（ ） (A) 2 (B) 3 (C) 4 (D) 5答案：D 20）n个结点的线索二叉树上含有的线索数为（ ） (A) 2n (B) nl (C) nl (D) n答案：C4、判断类习题1）数据元素之间的关系可以概括为四类基本结构：集合结构、线性结构、树形结构、图形结构。（Yes ）2）线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 （No） 3）抽象数据类型ADT的定义包括三部分：对象、关系、操作。（Y ）4）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（N）5）线性表的逻辑顺序与物理顺序总是一致的。 （N） 6）两个栈共用静态

12、存储空间，对头使用也存在空间溢出问题。（Y） 7）栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（Y） 8）数组不适合作为任何二叉树的存储结构。 （N） 9）一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（N） 10）树形结构中元素之间存在一个对多个的关系。（Y） 5、填空类习题1）在长度为N的顺序表中插入一个元素，需要平均移动（ ）个元素。 答案：n/2 2）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是( ). 答案：3 3）空格串的长度为串中所包含空格字符的个数，空串

13、的长度为 （） 答案：0 4）广义表L=（a，b），其长度为（）。答案：1 5）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）。 答案：82 6）一棵具有n个叶子结点的哈夫曼树中，结点总数为（）。 答案：2n-1 7）深度为（空二叉树的深度为）的二叉树，最少有( )个结点。 答案：h 8）已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 ( )。 答案：111 9）若一棵完全二叉树有768个节点，则该二叉树中叶子节点的个数是（） 答案：384 10）已知深度为7的完全二叉树的第7层有10个叶子结点，则第6层有（）个叶子结点。 答案：27