数据结构作业
第1~5章
一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度 1、i=0;k=0; Do { k=k*10*i; i++;
} while (i { if(i>j) j++; else i++; } 3、 x=n; //n>1 while (x>=(y+1)*(y+1)) y++; 4、x=91; y=100; while (y>0) if (x>100) {x=x-10; y- -;} else x++; 二、选择题 1、从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2、以下数据结构中，哪一个是线性结构（ ）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 3、在下面的程序段中，对x的赋值语句的频度为（ ） for (i=1;i<=n;i++) for (j=1;j<=n;j++) x=x+1; A． O(2n) B．O(n) C．O(n2) D．O(logn 2) 4、下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表7、下面的叙述不正确的是（ ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 1 ）存储方 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 8、 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。 2 A. O(0) B. O(1) C. O(n) D. O(n) 9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 11、 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 12、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 13、 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 14、 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 15、 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 三、判断题 1、数据元素是数据的最小单位。( ) 2、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 3、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( ) 5、一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值 互换，则就完成了Am*n的转置运算。（ ） 6、所谓取广义表的表尾就是返回广义表中最后一个元素。（ ） 四、填空题 1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 2、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。 4、带头结点的双循环链表L中只有一个元素结点的条件是：________ 5、一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。 7、________又称作先进先出表。 8、组成串的数据元素只能是________。 9、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优 2 先顺序存储，则元素A[6][6]存储地址为_______。 五、算法设计题 1、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。 2、已知L为非递减的顺序表，请设计算法删除L中重复的元素（即删除后使L表变为一递增表）。 3、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。 4、设计一算法，逆置带头结点的动态单链表L。 5、在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 六、程序填空题 不带头结点的单链表L进行就地逆置的算法，用L返回逆置后的链表的头指针。 void reverse（linklist &L） { p=null；q=L； while（q！=null） { (1) ; q->next=p；p=q；(2)___ ; } (3)_____; } 第六章 树 选择题 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 6．具有10个叶结点的二叉树中有（ ）个度为2的结点， A．8 B．9 C．10 D．ll 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 有n个叶子的哈夫曼树的结点总数为（ ）。 A．不确定 B．2n C．2n+1 D．2n-1 9. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 10．深度为h的满m叉树的第k层有（ ）个结点。(1= k-1 kh-1h A．m B．m-1 C．m D．m-1 11．在一棵高度为k的满二叉树中，结点总数为（ ） k-1 k kk A．2B．2C．2-1 D．?log2?+1 12．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 13．树的后根遍历序列等同于该树对应的二叉树的( ). 3 A. 先序序列 B. 中序序列 C. 后序序列 14．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 A．acbed B．decab C．deabc D．cedba 15．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树 的根是： A、 E B、 F C、 G D、 H 16．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 17．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 18．从下列有关树的叙述中,选出5条正确的叙述 （ ） A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 k-1 B．当K≥1时高度为K的二叉树至多有2个结点。 C．用树的前序周游和中序周游可以导出树的后序周游。 D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。 F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G．在二叉树中插入结点,该二叉树便不再是二叉树。 H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。 I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J．用一维数组存储二叉树时,总是以前序周游存储结点。 判断题： 1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 2. 二叉树只能用二叉链表表示。 i-1 3．在二叉树的第i层上至少有2个结点(i>=1) 4．度为二的树就是二叉树。 5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。 填空题： 1．具有256个结点的完全二叉树的深度为______。 2．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______ 4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 5．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。 6．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 算法应用题 1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中有多少个叶子结点？ 2、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ （请给出具体的推理过程） 3、请采用顺序存储方式和链式存储方式，分别写出下图所示二叉树的存储结构。 4 A B C D E F G H 4、求出上图所示二叉树的前序、中序和后序序列。 5、以二叉链表做存储结构，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。 6、设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的中序线索树 （3）画出这棵二叉树的后序线索树 7、假设一个二叉树的两种遍历如下： 前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA 画出这棵二叉树以及它的中序线索树； 8、给定一组权值3，27，7，8，14，23，6，12 （1）试画出用Huffman算法建造的Huffman树； （2）求Huffman编码和平均编码长度（考虑概率） 9、将下列森林转化为二叉树。 10、求上述森林的前序和中序序列。 算法设计题： 1．设计算法，求前序线索树中结点P的后继 2．设计算法，求中序线索树中结点P的后继 3．用二叉链表表示的二叉树T，结点的值为整型，请设计算法，求T中结点值大于0的结点数，并作为算法的返回值。 第七章 图 选择题 1．设无向图的顶点个数为n，则该图最多有（ ）条边。 2 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 2．一个n个顶点的连通无向图，其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 3．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 5
