习题练习第一章绪论1、void maxtrixmult (int n,int a[][100],intb[][100],intc[][100]){int j,k,r;int x;for(r=0;r<=n;r++)1) n+2{for (j=0;j<=n;j++) 2) (n+1)*(n+2){x=0; 3)(n+1)2for(k=1；k<=n;k++) 4)(n+1)3x+=a[r][k]*[k][j];5) n* (n+1)2c[r][j]=x; 6)(n+1)2}}}计算时间每条语句的频度和该算法的时间复杂度2．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C.4．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构5．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈6．连续存储设计时，存储单元的地址（ A ）。

【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续7. 数据元素是数据的最小单位。

( F )【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】第二章线性表1．线性表是具有n个（ C ）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

【哈尔滨工业大学 2001 二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表4．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表5. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

【北京航空航天大学 1999 一、1（2分）】A. O(0)B. O(1)C. O(n)D. O(n2)7．非空的循环单链表head的尾结点p↑满足（ A ）。

【武汉大学 2000 二、10】A．p->next=head B．p->next=NIL C．p=NIL D．p= head 8．循环链表H的尾结点P的特点是（ A ）。

【中山大学 1998 二、2（2分）】A．P->NEXT=H B．P->NEXT= H->NEXT C．P=H D．P=H->NEXT 9．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A）【南京理工大学1998 一、15（2分）】A. p->next=hB. p->next=NILC. p->next->next=hD. p->data=-1 14．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动______N-I+1__个元素。

17. 在单链表L中，指针p所指结点有后继结点的条件是：．p->next!=null__ 【合肥工业大学 2001 三、3 （2分）】第三章栈和队列3、一个循环队列QU（最多元素为m0）队列满时，队列中有 m0-1 个元素4. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B ）。

A. 不确定B. n-i+1C. iD. n-i【中山大学 1999 一、9(1分)】5. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉大学 2000 二、3】6. 一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 2【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000一、2（2分）】11. 循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。

【中山大学1999 一、6（1分）】A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)12. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )【浙江大学1999 四、1(4分)】A. 1和 5B. 2和4C. 4和2D. 5和1第五章数组1、在一个长度为n的向量中的第I个元素（1<=I<=n）之前插入一个元素时，须向后移动 N-I+1 个元素2、在一个长度为n的向量中删除第I个元素（1<=I<=n）时，须向前移动 N-I 个元素5、数组A中，每个元素的长度是3个字节，行下标k的范围从1到8，列下标j的范围从1到10，从首地址SA开始连续存放在存储器中，该数组按行存放时，元素A[8][5]的起始地址为SA+222 。

9、有一个10阶对称矩阵A,采用压缩存储方式存储，（按行为主序，并且A[0][0]=1）,则A[8][5]的地址为 42 。

16、广义表（（a,b,c,d））的表头是（a,b,c,d），表尾是( ) 。

17、广义表（a,（b,c,d））的表头是 a ，表尾是(（b,c,d）) 。

21. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))【西安电子科技大学 2001应用一、3（2分）】22. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ D ）。

【北京邮电大学1999一、2（2分）】Head(Tail(Head(Tail(Tail(A)))))A. (g)B. (d)C. cD. d第6章树和二叉树答案7.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A．9 B．11 C．15 D．不确定12.设给定权值总数有n 个，其哈夫曼树的结点总数为( D)A．不确定 B．2n C．2n+1 D．2n-1B ACEDFNPGH JM OLIK13.有n个叶子的哈夫曼树的结点总数为（ D）。

A．不确定 B．2n C．2n+1 D．2n-114.有关二叉树下列说法正确的是（ B ）A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为215.二叉树的第I层上最多含有结点数为（ C ）A．2I B． 2I-1-1 C． 2I-1 D．2I -118.对于有n 个结点的二叉树, 其高度为（ D ）A．nlog2n B．log2n C．⎣log2n⎦|+1 D．不确定19. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）A．⎣logn⎦+1 B．logn+1 C．⎣logn⎦ D．logn-125.利用二叉链表存储树，则根结点的右指针是（ C ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空30.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定31．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。

A．acbed B．decab C．deabc D．cedba42.在完全二叉树中，若一个结点是叶结点，则它没（ C ）。

A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点四，应用题4．将下列由三棵树组成的森林转换为二叉树。

（只要求给出转换结果）【南京航空航天大学 1998 一、 (10分)】5．设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。

（2）画出这棵二叉树的后序线索树。

（3）将这棵二叉树转换成对应的树（或森林）。

【南京航空航天大学 1997 二、 (10分)】ABFD(3)CE H G9（1）设通信中出现5中字符A、B、C、D、E对应的频率为0.2,0.1,0.5,0.15,0.25构造哈夫曼树，并给出对应字符的编码。

【青岛大学2002 四、2 （10分）】（2）设A、B、C、D、E、F六个字母出现的概率分别为7,19,2,6,32,3。

试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树.【山东工业大学 1995 四(10分)】(1) 编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01(2) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。

由哈夫曼树构造出哈夫曼编码。

译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。

第七章图一、选择题1．图中有关路径的定义是（ A ）。

【北方交通大学 2001 一、24 （2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B ）条边。