《数据结构与算法习题与答案》由会员分享，可在线阅读，更多相关《数据结构与算法习题与答案（56页珍藏版）》请在金锄头文库上搜索。
1、WORD格式第1章绪论习题1简述以下概念：数据、数据元素、数据项、数据对象、数据构造、逻辑构造、存储构造、抽象数据类型。2试举一个数据构造的例子，表达其逻辑构造和存储构造两方面的含义和相互关系。3简述逻辑构造的四种根本关系并画出它们的关系图。4存储构造由哪两种根本的存储方法实现？5选择题 1在数据构造中，从逻辑上可以把数据构造分成。A 动态构造和静态构造B 紧凑构造和非紧凑构造C线性构造和非线性构造D 内部构造和外部构造 2与数据元素本身的形式、内容、相对位置、个数无关的是数据的。A 存储构造B 存储实现C逻辑结 构D 运算实现 3通常要求同一逻辑构造中的所有数据元素具有一样的特性，这意味着。
2、A 数据具有同一特点B不仅数据元素所包含的数据项的个数要一样，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等 4以下说法正确的选项是。A 数据元素是数据的最小单位B数据项是数据的根本单位专业资料整理WORD格式C数据构造是带有构造的各数据项的集合D一些外表上很不一样的数据可以有一样的逻辑构造 5以下与数据的存储构造无关的术语是。A 顺序队列B. 链表C. 有序表 6以下数据构造中， 是非线性数据构造D.链栈专业资料整理WORD格式A 树B字符串C队D 栈专业资料整理WORD格式6试分析下面各程序段的时间复杂度。（ 1 x=90; y=100; while(y
3、0)if(x100)x=x-10;y-;else x+; 2 for (i=0;in; i+)for (j=0; jm; j+)aij=0;（ 3 s=0;for i=0; in; i+)专业资料整理WORD格式for(j=0; jn; j+)s+=Bij;sum=s;（ 4 i=1; while(i=n)i=i*3;（ 5 x=0;for(i=1; in; i+)for (j=1; j1y=0;while(x (y+1)* (y+1)y+ ;（ 1O 1（ 2O m*n （ 3O n2（ 4O log 3n 5因为 x+ 共执行了n-1+n-2+ 1= n(n-1)/2 ，所以执行时间为O
4、n2 6O(n )专业资料整理WORD格式第2章线性表1选择题 1一个向量第一个元素的存储地址是100，每个元素的长度为2，那么第 5 个元素的地址是。专业资料整理WORD格式A110B 108C 100D 120专业资料整理WORD格式 2在n 个结点的顺序表中，算法的时间复杂度是O(1) 的操作是。专业资料整理WORD格式A 访问第 i 个结点 1 i n和求第i 个结点的直接前驱2 i nB在第 i 个结点后插入一个新结点1i nC删除第i 个结点 1 i nD将 n 个结点从小到大排序专业资料整理WORD格式 3 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，动
5、的元素个数为。平均要移专业资料整理WORD格式A8B63.5C63D7 4存储的存储构造所占存储空间。A 分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针B只有一局部，存放结点值C只有一局部，存储表示结点间关系的指针D分两局部，一局部存放结点值，另一局部存放结点所占单元数 5线性表假设采用链式存储构造时，要求内存中可用存储单元的地址。专业资料整理WORD格式A 必须是连续的C一定是不连续的B 局部地址必须是连续的D 连续或不连续都可以专业资料整理WORD格式 6线性表在情况下适用于使用链式构造实现。A 需经常修改中的结点值需不断对进展删除插入C中含有大量的结点中结点构造复杂专业资料
6、整理WORD格式 7单链表的存储密度。专业资料整理WORD格式A大于 1 8将两个各有A nB等于 1C小于 1D不能确定n 个元素的有序表归并成一个有序表，其最少的比较次数是B 2n-1C 2nD n-1。专业资料整理WORD格式 9在一个长度为n 的顺序表中，在第i 个元素须向后移动个元素。A n-iB n-i+1C n-i-1(10) 线性表 L=(a 1， a2, an)，以下说法正确的选项是1 i n+1 之前插入一个新元素时D i。专业资料整理WORD格式A 每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个
7、元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。专业资料整理WORD格式(11) 假设指定有n 个元素的向量，那么建立一个有序单链表的时间复杂性的量级是。专业资料整理WORD格式A O(1)BO(n)C O(n 2)D O(nlog 2n)专业资料整理WORD格式(12) 以下说法错误的选项是。A 求表长、定位这两种运算在采用顺序存储构造时实现的效率不比采用链式存储构造时实现的效率低专业资料整理WORD格式B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储构造优于顺序存储构造(13) 在单链表中，要将s 所指结点插入到p 所指结
8、点之后，其语句应为。专业资料整理WORD格式A s-next=p+1; p-next=s;B (*p).next=s; (*s).next=(*p).next;C s-next=p-next; p-next=s-next;D s-next=p-next; p-next=s;专业资料整理WORD格式(14) 在双向链表存储构造中，删除p 所指的结点时须修改指针。专业资料整理WORD格式A p-next-prior=p-prior; p-prior-next=p-next;B p-next=p-next-next; p-next-prior=p;C p-prior-next=p; p-prior=
9、p-prior-prior;D p-prior=p-next-next; p-next=p-prior-prior;(15) 在双向循环链表中，在p 指针所指的结点后插入的操作是。q 所指向的新结点，其修改指针专业资料整理WORD格式A p-next=q; q-prior=p; p-next-prior=q; q-next=q;B p-next=q; p-next-prior=q; q-prior=p; q-next=p-next;C q-prior=p; q-next=p-next; p-next-prior=q; p-next=q;D q-prior=p; q-next=p-next; p
10、-next=q; p-next-prior=q;2算法设计题（ 1将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间 , 不另外占用其它的存储空间。表中不允许有重复的数据。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)pa=La-next; pb=Lb-next;Lc=pc=La;/用 La 的头结点作为Lc 的头结点while(pa & pb)if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next;else if(pa-datapb-data) pc-next
11、=pb; pc=pb; pb=pb-next;else /相等时取La 的元素，删除Lb 的元素pc-next=pa;pc=pa;pa=pa-next;q=pb-next;delete pb ;pb =q;专业资料整理WORD格式pc-next=papa:pb;delete Lb;/插入剩余段释放 Lb 的头结点专业资料整理WORD格式（ 2将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间 , 不另外占用其它的存储空间。表中允许有重复的数据。void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La-next; pb = Lb-next;/初始化Lc=pc=La; /用 La 的头结点作为Lc 的头结点Lc-next = NULL;专业资料整理WORD格式while ( pa | pb ) if ( !pa ) q = pb; pb = pb-next; else if ( !pb ) q = pa; pa = pa-next; else if (pa-data data ) q = pa; pa = pa-next
