《算法与数据结构复习提纲及答案》由会员分享，可在线阅读，更多相关《算法与数据结构复习提纲及答案（40页珍藏版）》请在金锄头文库上搜索。
1、1一、概论部分 2. 算法的时间复杂度取决于（C ） A问题的规模B. 待处理数据的初态C. A 和 B 3.计算机算法指的是（1C） ，它必须具备（2A） 这三个特性。 (1) A计算方法B. 排序方法C. 解决问题的步骤序列D. 调度方法 (2) A可执行性、可移植性、可扩充性B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性 4一个算法应该是（ B） 。 A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C. 5. 下面关于算法说法错误的是（D） A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法
2、的可行性是指指令不能有二义性D. 以上几个都是错误的 6. 下面说法错误的是（C） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A(1)B.(1),(2)C.(1),(4)D.(3) 7从逻辑上可以把数据结构分为（C）两大类。 A动态结构、静态结构B顺序结构、链式结构 C线性结构、非线性结构D初等结构、构造型结构 8以下与数据的存储结构无关的术语是（ D） 。 A循环队列B. 链
3、表C. 哈希表D.栈 9以下数据结构中，哪一个是线性结构（D） ？ A广义表B. 二叉树C. 稀疏矩阵D.串 10以下那一个术语与数据的存储结构无关？（A） A栈B. 哈希表C. 线索树D.双向链表 以下哪个数据结构不是多型数据类型（ D） A栈B广义表C有向图D字符串 11以下数据结构中， （ A）是非线性数据结构 A树B字符串C队D栈 12. 下列数据中， （C）是非线性数据结构。 A栈B.队列C.完全二叉树D. 堆 13连续存储设计时，存储单元的地址（ A） 。 A一定连续B一定不连续C不一定连续D部分连续，部分不连续 14以下属于逻辑结构的是（ C） 。 A顺序表B. 哈希表C.有序表
4、D.单链表 15.对于给定的 n 个元素,可以构造出的逻辑结构有集合， 线性结构， 树形结构， _图形结构_四种 16. 数据的逻辑结构是指数据的组织形式。 17一个数据结构在计算机中表示称为存储结构 18. 数据结构中评价算法的两个重要指标是 时间复杂度和空间复杂度 19. 数据结构是研讨数据的_逻辑结构_和_物理结构_， 以及它们之间的相互关系， 并对与这2种结构定义相应的_操作_，设计出相应的 算法_。 20. 一个算法具有 5 个特性: 确定性、 有穷性 、 可行性 ，有零个或多个输入、有一个或 多个输出。 21. 有实现同一功能的两个算法 A1 和 A2，其中 A1 的时间复杂度为
5、Tl=O(2n)，A2 的时间复杂度为 T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。二、线性表部分 1下述哪一条是顺序存储结构的优点？（A ） A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构 的存储表示 2下面关于线性表的叙述中，错误的是哪一个？（ B） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3线性表是具有 n 个（C）的有限序列（n0） 。 A表元素B字符C数据元素D数据项E信息项 4 若某线
6、性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用（A）存储方式最节省时间。 A顺序表B双链表C带头结点的双循环链表D单循环链表 5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用（ D）存储方式最节省运算时间。 【南开大学 2000 一、3】 A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的 单循环链表 6 设一个链表最常用的操作是在末尾插入结点和删除尾结点， 则选用(D)最节省时 间。 A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表 7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一
7、个结点。则 采用（D）存储方式最节省运算时间。 A单链表B双链表C单循环链表D带头结点的双循环链表 8. 静态链表中指针表示的是（C）. A 内存地址B数组下标C下一元素地址D左、右孩子地址 9. 链表不具有的特点是（ B） A插入、删除不需要移动元素B可随机访问任一元素 C不必事先估计存储空间D所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC） A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比 B. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 C. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 D. 线性表在顺序存储时，查找第
8、 i 个元素的时间同 i 的值无关 11.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 i 个元 素的时间与 i 无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。3以上错误的是（B） A （1） ， （2）B （1）C （1） ， （2）,(3)D.（2） 12. 若长度为 n 的线性表采用顺序存储结构， 在其第 i 个位置插入一个新元素的算法的时间 复杂度为（C）(1Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；
9、B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; 16在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是： （B） 。 Ap-next=s;s-next=p-next;B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next;D p-next=s-next;p-next=s
10、; 17对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ B） Ahead=NULLBheadnext=NULLCheadnext=headDhead!=NULL 18当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取 线性表中的元素时，应采用_顺序_存储结构。 19线性表 L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一 个元素平均需要移动元素的个数是_（n-1）/2_。 20设单链表的结点结构为(data,next)，next 为指针域，已知指针 px 指向单链表中 data 为 x 的结点，指针 py 指向 d
11、ata 为 y 的新结点 , 若将结点 y 插入结点 x 之后，则需要执行 以下语句:_py-next=px-next_； px-next = py; 21在一个长度为 n 的顺序表中第 i 个元素（1next=p-next; f-prior=p; p-next-prior=f; p-next=f;。 25链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。 26.顺序存储结构是通过_物理上相邻_表示元素之间的关系的;链式存储结构是通过_ 指针_表示元素之间的关系的。 27. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _4_个，单链表为 _2_个。 28. 循环单链表的最
12、大优点是：_从任一结点出发都可访问到链表中每一个元素。_。 29. 已知指针 p 指向单链表 L 中的某结点，则删除其后继结点的语句是：_u=p-next; p-next=u-next; free(u);430 带头结点的双循环链表 L 中只有一个元素结点的条件是：_L-next-next=L_ 31. 在单链表 L 中，指针 p 所指结点有后继结点的条件是：_p-next!=null 32.带头结点的双循环链表 L 为空表的条件是：_L-next=L p-next=s;_。 34对单链表中元素按插入方法排序的 C 语言描述算法如下，其中 L 为链表头结点指针。 请 填充算法中标出的空白处，完
13、成其功能。 typedef struct node int data;struct node *next; linknode,*link; void Insertsort(link L) link p,q,r,u; p=L-next;L-next = NULL_; while(p!= NULL) r=L;q=L-next; while(q!=NULL_ q=q-next; u=p-next;p-next = r-next_;r-next =p_;p=u; 35一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef ，指数域 exp 和指针域 next；现对链表求一阶导数 ，链表的
14、头指针为 ha，头结点的 exp 域为 1。 derivative(ha) q=ha ;pa=ha-next; while( pa != ha_) if ( pa -exp = 0_) ( q-next = pa - next_); free(pa);pa= (q-next); else pa-coef (= p-coef * pa - exp); pa-exp( -_); q=(pa); pa=( pa - next_); 36以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h) /* h 为附加头结点指针；类型 point
15、er 同算法设计第 3 题*/ pointer p,q; p=h-next;h-next=NULL; while(p != NULL) q=p; p=p-next; q-next=h-next; h-next= q_; 37. 设双向循环链表中结点的数据域、前驱和后继指针域分别为 data,pre 和 next,试写出 在指针 p 所指结点之前插入一 s 结点的 C 语言描述语句。 38一线性表存储在带头结点的双向循环链表中，L 为头指针。如下算法： （1）说明该算法的功能。 （2）在空缺处填写相应的语句。 void unknown(BNODETP *L) p=L-next; q=p-next; r=q-next；5while (q!=L) while (p!=L) pb=lb-next;pa，pb 分别是链表 la 和 lb 的工作指针 la-next=null;la 作结果链表的头指针，先将结果链表初始化为空。 whilewhile(pa!=null 将 pa 的后继结点暂存于 r。 pa-next=la-next;将 pa 结点链于结果表中，同时逆置。 la-next=pa;
