嵌入式系统开发人员C语言测试题数据结构与算法

1、11.1 选择题 （833） 下面关于算法说法错误的是_。 a. 算法最终必须由计算机程序实现 b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （834） 下面说法错误的是_. a. 算法原地工作的含义是指不需要任何额外的辅助空间 b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （835） 在下面的程序段中，对x的赋值语句的频度为_。 for (int i; in;

2、i+) for (int j=o; jLlink=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; （845） 下面说法正确的是_。 a. 顺序存储结构的主要缺点是不利于插入或删除操作； b. 线性表采用链表存储时，结点和结

3、点内部的存储空间可以是不连续的； c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好； d. 顺序存储方式只能用于存储线性结构。 （846） 下面说法正确的是_。 a. 线性表只能用顺序存储结构实现。 b. 为了很方便的插入和删除数据，可以使用双向链表存放数据。 c. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 d. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （847） 下面说法正确的是_。 a. 数据元素是数据的最小单位。 b. 队列逻辑上是一个下端口和上端能增加又能减少的线性表。 c. 任何一个递归过程都可以转换成

4、非递归过程。 d. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。 （848） 下面说法正确的是_。 a. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。 b. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。 c. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 d. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 （849） 下面说法正确的是_。 a. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不

5、稳定的。 b. 堆排序是稳定的排序方法。 c. 在分配排序时，最高位优先分配法比最低位优先分配法简单。 d. 最佳两叉排序树的任何子树都是最佳的。 （850） 具有N个结点的完全二叉树的深度是：_。 a. log2n b.LOG2N/1 c. LOG2(N/1) d.LOG2N-1 （851） 用单循环链表表示队列，正确的说法是：_。 a. 可设一个头指针使入队、出队都方便 b. 可设一个尾指针使入队、出队都方便 c. 必须设头尾指针才能使入队、出队都方便 d. 无论如何,只可能使入队方便 （852） 一个哈希函数被认为是好的，如果它满足条件_。 a. 哈希地址分布均匀 b. 保证不产生冲突

6、c. 所有哈希地址在表长范围内 d. 满足(2)和(3) （853） ISAM文件和VSAM文件属于_。 a. 索引非排序文件 b. 索引顺序文件 c. 顺序文件 d. 散列文件 （854） 在下述排序算法中_算法是稳定的排序算法。 a. 希尔排序 b. 快速排序 c. 冒泡排序 d. 堆排序 （855） 在下述三种排序算法中，所需辅助存储量最多的是_，所需存储量最少的是_，平均速度最快的是_。 a. 堆排列 b. 快速排列 c.归并排列 （856） 存贮稀疏图的数据结构常有的是_。 a. 邻接矩阵 b. 三元组 c. 邻接表 d. 十字链表 （857） 内部排序多个关键字的文件，最坏情况下最

7、快的排列方法是_,相应的时间复杂度为_,该算法是的稳定性_。 a. 快速排序 b. 插入排序 c. 归并排序 d. 简单选择排序 e. O(nlog2(n) f. O(n2) g. O(n2log2(n) h. O(n) i. 稳定 j. 不稳定 （858） 倒排文件包含若干个倒排表，倒排表的内容是_。 a. 一个关键字值和关键字的记录地址； b. 一个属性值和该属性的一个记录地址； c. 一个属性值和该属性的全部属性地址； d. 多个关键字值和它们对应的某个记录的地址。 （859） 在下述几种树当中,_可以表示静态查找表. a. 次优查找树; b. 二叉排序树; c. B-树 d. 平衡二叉

8、树 （860） 选择填空： (1). 在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_. (2). 快速排序在最坏的情况下,时间复杂度是_,_的性能差; (3). 就平均时间而言,_最佳. a.: (1)直接插入排序 (2)起泡排序 (3)简单选择排序; b.: (1)O(nlog(n) (2)O(n2) (3)O(n3) c.: (1)堆排序 (2)起泡排序 (3)选择排序. d.: (1)堆排序 (2)快速排序 (3) 归并排序. （861） 算法的时间复杂度取决于_。 a. 问题的规模 b. 待处理数据的初态 c. both a and b （862） 假定有k个关键字互为同

9、义词,若用线性探测法把这k个关键字存入散列表中,至少要进行_次探测。 a. k-1 b. k c. k=1 d. k(k+1)/2 （863） 若需要在O(nlog2(n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是: a. 快速排序 b. 堆排序 c. 归并排序 d. 直接插入排序 （864） 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_。 a. n b. 2n-1 c. 2n d. n-1 （865） 下述二叉树中,_满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序。 a. 二叉排序树 b. 哈夫曼树 c. AVL树 d. 堆 （

10、866） 若在线性表中采用折半查找法查找元素，该线性表应该_。 a. 元素按值有序 b. 采用顺序存储结构 c. 元素按值有序，且采用顺序存储结构 d. 元素按值有序，且采用链式存储结构 （867） 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用_遍历方法最合适。 a. 前序 b.中序 c.后序 d. 按层次 （868） 对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的排序序列。 a. 前序 b. 中序 c.后序 d. 按层次 （869） 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_排序法。 a

11、. 插入 b. 选择 c. 谢尔 d. 二路归并 （870） 排序趟数与序列的原始状态有关的排序方法是_排序法。 a. 插入 b. 选择 c. 泡 d. 快速 （871） 下面给出的四种排序法中_排序法是不稳定性排序法。 a. 插入 b. 泡 c. 二路归并 d. 堆积 （872） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？ a. 深度优先遍历 b. 拓朴排序 c. 求最短路径 d. 求关键路径 （873） 下面关于程序设计风格的说法正确的是_。 a. 中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 b. 顺序存储方式只能用于存储线性结构。 c. 顺序查找法适用于存储结构为

12、顺序或链接存储的线性表。 d. 栈和队列都是限制存取点的线性结构。 （874） 已知变量定义： char S3=AB char *P; 在执行了语句PS之后，*（P2）的值是_。 a. B b. 0 c. 不确定 d. 字符B的地址 （875） 下面程序段的时间复杂度为_。 for(int i=0;im;i+) for(int j=0;j=MAX_STACK_SIZE-1) return stack_full(); stack =item; 则在stack 的中括号内横线上的正确内容应为：_。 a. +*top b. *top+ c. *top- d. *top （877） 有如下函数： vo

13、id fun(struct node h1,struct node h2) struct node *t; t=h1; while (t-next != 0) t = t-next; t-next = h2; 其中形参h1和h2分别指向2个不同链表的第一个结点，此函数的功能是：_。 a. 将链表h2接到链表h1后 b. 将链表h1接到链表h2后 c. 找到链表h1的最后一个结点由指针返回 d. 将链表h1拆分成两个链表 （878） 一个栈的入栈序列是abcde，则栈的不可能输出序列是： _。 a. edcba b. decba c. dceab d. abcde （879） 下面说法正确的是_

14、。 a. 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。 b. 任何一个递归过程都可以转换成非递归过程。 c. 与n个键值的集合k1,k2,kn相对应的堆是唯一的。 d. 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。 （880） 下面说法正确的是_。 a. 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。 b. 哈希表查找无需进行关键字的比较。 c. 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。 d. B树查找算法的时间复杂性为O（n

15、）。 （881） 下列有关线性表的叙述中，正确的是_。 a. 线性表中的元素之间隔是线性关系 b. 线性表中至少有一个元素 c. 线性表中任何一个元素有且仅有一个直接前趋 d. 线性表中任何一个元素有且仅有一个直接后继 （882） 下列关于串的叙述中，正确的是_。 a. 一个串的字符个数即该串的长度 b. 一个串的长度至少是1 c. 空串是由一个空格字符组成的串 d. 两个串S1和S2若长度相同，则这两个串相等 （883） 4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态是_。 不可能的出栈序是_。 a. a4，a3，a2，a1 b. a3，a2，a4，a1 c. a3，a

16、1，a4，a2 d. a3，a4，a2，a1 （884） 以数组Q0.m1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是_。 a. rearqulen b. rearqulenm c. mqulen d. 1（rearmqulen）mod m （885） 高二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_。 a. 6 b. 5 c. 4 d. 3 （886） 下列四种排序方法中，不稳定的方法是_。 a. 直接插入排序 b. 冒泡排序 c. 归并排序 d. 直接选择排序 （887） 设有一个长

17、度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较_次。 a. 9 b. 8 c. 7 d. 6 （888） 一棵二叉排序树T，用_方法进行遍历，可以得到各结点键值的递增序列。 a. 先根遍历 b. 中根遍历 c. 层次遍历 d. 后根遍历 （889） 设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是_。 a. x是y的左兄弟 b. x是y的右兄弟 c. x是y的祖先 d. x是y的后代 （890） 下面说法正确的是_。 a. 数据的机内表示称为数据的存储结构。 b. 线性表的链接存储，表中元素的逻辑顺序与物理顺

18、序一定相同。 c. 二叉树中任何一个结点的度都是2。 d. 由二叉树结点的先根序列的后根序列可以唯一地确定一棵二叉树。 （891） 下面说法正确的是_。 a. 用直接选择排序方法分别对序列S1（1，2，3，4，5，6，7）和序列S2（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。 b. 一棵哈夫曼树中不存在度为1的结点。 c. 用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。 d. 顺序文件适宜顺序存取，不适宜随机存取。 （892） 下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上的是_。 a. 堆排序 b. 冒泡排序 c

19、. 直接插入排序 d. 快速排序 （893） _是不稳定的排序方法。 a. 冒泡排序 b. 归并排序 c. 堆排序 d. 选择排序 （894） 从逻辑上，可以将数据结构分为_两类。 a. 动态表和静态表 b. 顺序结构和链式结构 c. 线性结构和非线性结构 d. 动态结构和静态结构 11.2 填空题 （895） 下面程序段的时间复杂度为_。 sum=1； for (i=0; sumn; i+) sum+=1; （896） 下列程序的功能是创建单向链表，请补充完整。 #include #include struct link char name10; int mark; struct link

20、* next; ; void insert(char * name, int mark); struct link * head = NULL; main() char name10; int mark; struct link *t; while (1) scanf(%s %d, name, &mark); if (strcmp(name, #) = 0 ) break; _(1)_; for (t=head; _(2)_) printf(: %dn, t-name, t-mark); void insert(char * name, int mark) struct link * p; p

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

22、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); （900） 补充下列程序：设一棵二叉序列树b，下列算法函数是实现在b中插入一个结点s。 函数： void insert（btree *b，btree *s） if（b = NULL） b = s； else if（s-data = b-data） return(); else if(s-data data) ； else ； （9

23、01） 一个nn的下三角矩阵A中的元素aij（ij，1i，jn）按行存于一个一维数组B1.n（n1）/2中，对其中的任一元素aij，若在B中的位置为k，则k_。 （902） 含有100个结点的树有_条边。 （903） 设一个闭散列表的容量为m，用线性控测法解决冲突，要插入一个键值，若插入成功，至多要进行_次比较。 （904） 设二维数组M：array-1.4，0.3of integer，每个元素（整数）占个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M2，1的地址是_。 （905） 线性表L（a1，a2，.，an）采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新

24、元素平均需要移动的元素个数是_。 （906） 设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_个元素。 （907） 两个序列如下： L1 25，57，48，37，92，86，12，33 L2 25，37，33，12，48，57，86，92 用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列_。 （908） 将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt1.50中，这棵二叉树最下面一层上最

25、左边一个结点存储在数组元素_中。 （909） 一个索引文件由_两部分组成。 11.3 问答与设计 （910） 说明线性插入排序的算法及时间、空间复杂度 （911） 说明折半插入排序的算法及时间、空间复杂度 （912） 说明堆排序的算法及时间、空间复杂度 （913） 说明希尔排序的算法及时间、空间复杂度 （914） 说明快速排序的算法及时间、空间复杂度 （915） 说明基数排序的算法及时间、空间复杂度 （916） 说明交换排序的算法及时间、空间复杂度 （917） 说明选择排序的算法及时间、空间复杂度 （918） 说明归并排序的算法及时间、空间复杂度 （919） 说明分布排序的算法及时间、空间复杂

26、度 （920） 说明顺序查找的算法及时间、空间复杂度 （921） 说明折半查找的算法及时间、空间复杂度 （922） 说明分块查找的算法及时间、空间复杂度 （923） 说明比较查找的算法及时间、空间复杂度 （924） 说明基数查找的算法及时间、空间复杂度 （925） 说明哈希查找的算法及时间、空间复杂度 （926） 怎样查找链表中的数据? （927） 在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了，请写出二分搜索算法的步骤。 （928） 已知链表节点的类型定义如下，需要按照成员value从小到大进行排序，请写出算法： #include #include t

27、ypedef struct STRUCT int value; struct STRUCT *next; TS; （929） 什么是算法？算法的主要特点是什么？ （930） 如何评价一个算法？ （931） 什么是顺序存储结构？什么是链式存储结构？ （932） 线性表的顺序存储结构和链式存储结构各有什么特点？ （933） 若顺序表A中的数据元素按升序排列，要求将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。 （934） 试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。 （935） 简述栈和线性表的区别和联系。 （

28、936） 何为栈和队列？简述两者的区别和联系。 （937） 若依次读入数据元素序列a,b,c,d进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列。 （938） 将下列各算术运算式表示成波兰式和逆波兰式： (A*(B+C)+D)*E-F*G A*(B-D)+H/(D+E)-S/N*T (A-C)*(B+D)+(E-F)/(G+H) （939） 写出算术运算式3+4/25*8-6的操作数栈和运算符栈的变化情况。 （940） 若堆栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈后栈的状态，然后再画出此时的栈顶元素出栈后的状态。 （941） 简述设计一个结点值为整数的循环队列

29、的构思，并给出在队列中插入或删除一个结点的算法。 （942） 有一个循环队列q(n)，进队和退队指针分别为r和f；有一个有序线性表AM，请编一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止退队并保证线性表的有序性。 （943） 设有栈stack，栈指针top=n-1，n0；有一个队列Q(m)，其中进队指针r，试编写一个从栈stack中逐个出栈并同时将出栈的元素进队的算法。 （944） 两个字符串相等的充要条件是什么？ （945） 串有哪几种存储结构？ （946） 设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。 （947）

30、设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。 （948） 按行优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a000的内存地址为Loc(a000)）。 （949） 按列优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a000的内存地址为Loc(a000)）。. （950） 设有上三角矩阵Ann，它的下三角部分全为0，将其上三角元素按行优先存储方式存入数组Bm中(m足够大)，使得Bk=aij，且有k=f1(i)+f2(j)+

31、c。试推出函数f1、f2及常数c（要求f1和f2中不含常数项）。 （951） 若矩阵Amn中的某个元素Aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amn，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。 （952） 试写一个算法，查找十字链表中某一非零元素x。 （953） 广义表是线性结构还是非线性结构?为什么? （954） 画出下列广义表的图形表示 (1) A(b,(A,a,C(A),C(A) (2) D(A( ),B(e),C(a,L(b,c,d) （955） 若逻辑结构相同但存储结构不同，则为不同的

32、数据结构。这样的说法对吗？举例说明之。 （956） 在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。 （957） 评价各种不同数据结构的标准是什么？ （958） 评价一个好的算法，需要从哪几方面来考虑的？ （959） 什么是算法的时间复杂性？ （960） 什么是抽象数据类型？ （961） 数据结构与数据类型有什么区别？ （962） 数据的存储结构由哪四种基本的存储方法实现？ （963） 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的

33、结构。 （964） 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? （965） 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。 （966） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 （967） 分析下面程序段中循环语句的执行次数。 Int i= 0, s = 0, n = 100; Do i:=i+1; s:=s+10*i; while (In) & (sn) （968） 根据下面程序，回答下面问题： (1) 试指出f(n)

34、值的大小，并写出f(n) 值的推导过程; (2) 假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 int f(int n) int i, j, k, sum= 0; for(i=l; ii-1; j-) for(k=1; kj+1; k+ ) sum+; printf(sum=%dn, sum)； return (sum); （969） 设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 int m = 0; For (int i = 0; i n; i+) for (int j = 2*i, j n; j+) m = m + 1; （970） 试给出下面两个算法的运算时间。 a. for (int I = 0; I n; I+) x+; b. for (int I = 1; I n; I+) for (int j = 1; j = (y+1)(y+1) y+; （988） 试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。 （989） 对链表设置表头结点的作用是什么？（至少说出2条好处）