面试题数据结构2003.docVIP

面试题数据结构2003 嵌入式系统开发人员C语言测试题-数据结构与算法 姓名：_________ 得分：__________ 一.选择题（共15题，每题3分） （1） 下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现 b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2） 下面说法错误的是______. a. 算法原地工作的含义是指不需要任何额外的辅助空间 b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3） 在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; in; i++) { for (int j=o; jn; j++) { x:=x+1; } } a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4） 下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位； c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5） 下面说法正确的是_______。 a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高 c. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立 d. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构 （6） 下述_____是顺序存储结构的优点。 a. 存储密度大 b. 插入运算方便 c. 删除运算方便 d. 可方便地用于各种逻辑结构的存储表示 （7） 下面关于线性表的叙述中，错误的是_____。 a. 线性表采用顺序存储，必须占用一片连续的存储单元 b. 线性表采用顺序存储，便于进行插入和删除操作 c. 线性表采用链接存储，不必占用一片连续的存储单元 d. 线性表采用链接存储，便于插入和删除操作 （8） 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省时间。 a. 顺序表 b. 双链表 c. 带头结点的双循环链表 d. 单循环链表 （9） 静态链表中指针表示的是______。 a. 内存地址 b. 数组下标 c. 下一元素地址 d. 左、右孩子地址 （10） 下面的叙述不正确的是_______。 a. 线性表在链式存储时，查找第i个元素的时间同i的值成正比 b. 线性表在链式存储时，查找第i个元素的时间同i的值无关 c. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 d. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 （11） 下面说法错误的是_____。 a. 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 b. 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 c. 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 d. 静态链表就是一直不发生变化的链表。 （12） 在双向链表指针p的结点前插入一个指针q的结点操作是______。 a. p-Llink=q; q-Rlink=p; p-Llink-Rlink=q; q-Llink=q； 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; （13） 下面说法正确的是______。 a. 顺序存储结构的主要缺点是不利于插入或删除操作； b. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的； c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好； d. 顺序存储方式只能用于存储线性结构。 （14） 下面说法正确的是______。 a. 线性表只能用顺序存储结构实现。 b