面试题d.数据结构与算法

1、一. 选择题（共 15 题，每题 3 分）（1）下面关于算法说法错误的是 D_。a. 算法最终必须由计算机程序实现/* 不见得，有些算法是NP 完全问题，计算机程序只能实现低数量的值，对于高数量的是实现不了的。 */b. 为解决某问题的算法同为该问题编写的程序含义是相同的/* */c. 算法的可行性是指指令不能有二义性d. 以上几个都是错误的（2）下面说法错误的是 _A,D _.算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法所谓时间复杂度是指情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效

2、率就越低在下面的程序段中，对 x 的赋值语句的频度为 _C 。for (i; in; i+) for (j=o; jLlink=q; q-Rlink=p; p-Llink-Rlink=q; q-Llink=q；p-Llink=q; p-Llink-Rlink=q; q-Rlink=p; q-Llink=p-Llink;q-Rlink=p; q-Llink=p-Llink; p-Llink-Rlink=q; p-Llink=q;二. 填空题(共 5 题，每题 5 分)（1） 下列程序的功能是创建单向链表，请补充完整。#include #include struct link char name1

3、0; mark;struct link * next;void insert(char * name,mark); struct link * head = NULL;d. q-Llink=p-Llink; q-Rlink=q; p-Llink=q; p-Llink=q;（13）下面说法正确的是_。顺序结构的主要缺点是不利于或删除操作；线性表采用链表时，结点和结点的空间可以是不连续的；顺序方式和删除时效率太低，因此它不如链式方式好；顺序方式只能用于线性结构。（14）下面说法正确的是_。线性表只能用顺序结构实现。为了很方便的和删除数据，可以使向链表存放数据。顺序方式的优点是密度大，且、删除运算效

4、率高。链表是采用链式结构的线性表,进行、删除操作时，在链表中比在顺序结构中效率高。（15）下面说法正确的是_。数据元素是数据的最小。队列逻辑上是一个下端口和上端能增加又能减少的线性表。任何一个递归过程都可以转换成非递归过程。只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。main() char name10; mark;struct link *t; while (1) scanf(“%s %d”, name, &mark);if (strcmp(name, “#”) = 0 ) break; _(1)_;for (t=head; _(2)_)prf(“: %dn”, t-n

5、ame, t-mark);void insert(char * name,struct link * p;p = (3) ; strcpy(p-name, name); p-mark = mark;_(4)_; if ( head != NULL )_(5)_;head = p;mark)（2） 用循环链表表示的队列长度为n， 若只设头指针,则出队和入队的时间复杂度分别是_和； 若只设尾指针,则出队和入队的时间复杂度分别是和。（3） 在n 个的有序顺序表中进行折半查找,最大的比较次数是。（4） 仔细阅读下列程序，在空白处填入适当的语句。函数 match(s,t)完成在字符串 s 中寻找与t 匹

6、配的字符，若存在一个匹配，则返回t 在字符串 s中的下标；否则，返回-1。其中，字符指针*b 始终指向 s 的第一元素。Match(s,t) Char s,t; char *b=s;char *p, *r;for for (p=s, r=t; *r!=0 & *p= =*r; p+, r+); if_ return(s-b);return(-1);（5） 补充下列程序：设一棵二叉序列树b，下列算法函数是实现在b 中函数：void insert（btree *b，btree *s） if（b = NULL） b = s； elseif（s-data = b-data） return();else

7、if(s-data data)；else； 一个结点 s。三.简答题（共 3 题，每题 10 分）（1） 在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了，请写出二分搜索算法的步骤。（2） 试将一个无序的线性表 A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。（3） 何为栈和队列？简述两者的区别和联系。另一篇下列关于算法的叙述不正确的是 C算法是解决问题的有序步骤算法具有确定性、可行性、有限性等特征 C一个问题的算法都只有一种D常见的算法描述方法有自然语言、图示法、伪代码法等29、鸡、兔共笼问题，有腿共 6

8、0 条，问鸡、兔各有多少只？下面鸡和兔只数最合理的范围是B鸡：2 到 28，兔：1 到 1433、就算法实现的而言，可以抽象的对算法定义为：算法=控制结构+原操作。34、自然语言表示算法的特征不包括 CA容易具有歧义性 B语句太长C层次感强、嵌套明确 D自然且通俗易懂35、下列问题求解使用的算法与其他三个不同的是 BA冒泡排序 B。折半查找 C。选择排序 D。顺序查找37、下列关于算法的错误说法是 BA算法必须有输出 B。算法必须在计算机上用某种语言实现 C.算法不一定有输入 D.算法必须在有限步执行后能结束38、算法的描述方法不包括 DA.盒图 B.自然语言 C.流程图 D.E-R 图39、

9、算法设计时，应该严格考虑其质量指标，下列不属于该指标的是 AA.分布性 B.可读性 C.正确性 D.稳健性40、下列算法的运行时间复杂度中（n:问题规模），数量级最高的是 DO(logn) B.O(n)C.O(1) D.O(n!)下列哪个不属于迭代法的设计步骤 DA.确定迭代模型 B.建立迭代模型 C.对迭代关系式进行控制 D.计算迭代次数41、通俗地讲，算法是指解决问题的法或一个过程，描述算法的方式有很多种，AA.自然语言 B.表格方式 C.画图方式 D.C 语言42、下列那些问题不可以用贪心算法求的最优解 C编码 B.活动安排问题 C.0-1 背包问题 D.单源最短路径A.43、下面 4

10、个说法：算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模n 下,复杂度 O（n）的算法空间上总是优于复杂度 O（n*n）的算法3.所谓时间复杂度是指情况下，估算算法时间的一个上界4.同一个算法，实现语言的级别越高，执行效率就越低其中，错误的是 CA.(1)B.(1)(2)C.(1)(4)D.(3)44、下面关于算法说法错误的是 D A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能不能有二义性D.以上几个都是错误答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指

11、向其直接前趋和直接后继结点的指针。（ ）2. 链表的物理结构具有同链表一样的顺序。错，链表的 结构特点是无序，而链表的示意图有序。（ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各 个单元向前移动。 错，链表的结点不会移动，只是指针内容改变。（ ）4. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（ ）5. 顺序方式的优点是密度大，且、删除运算效率高。错，前一半正确，但后一半说法错误，那是链式的优点。顺序方式、删除运算效率较低，在表长为n 的顺序表中，和删除一个数据元素，平均需移动表长一半个数的数据元素。（ ）6. 线性表在物理空间中也一定是连续的。错，线性表有两种方式，顺序和链式。后者不要求连续存放。（ ）7. 栈和队列的方式既顺序方式，也方式。