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

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

《嵌入式系统开发人员C语言测试题数据结构与算法.docx》由会员分享，可在线阅读，更多相关《嵌入式系统开发人员C语言测试题数据结构与算法.docx（21页珍藏版）》请在冰点文库上搜索。

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

11.1   选择题

（833）   下面关于算法说法错误的是_______。

a.算法最终必须由计算机程序实现

b.为解决某问题的算法同为该问题编写的程序含义是相同的

c.算法的可行性是指指令不能有二义性 

d.以上几个都是错误的

（834）   下面说法错误的是______.

a.算法原地工作的含义是指不需要任何额外的辅助空间

b.在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法

c.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

d.同一个算法，实现语言的级别越高，执行效率就越低

（835）   在下面的程序段中，对x的赋值语句的频度为_____。

for（inti;i

{

for（intj=o;j

{

x:

=x+1;

}

}

a.0（2n）           b.0（n）       c.0（n2）    d.O（log2n） 

（836）   下面说法正确的是______。

a.数据元素是数据的最小单位；

b.数据元素是数据的最小单位；

c.数据的物理结构是指数据在计算机内的实际存储形式

d.数据结构的抽象操作的定义与具体实现有关

（837）   下面说法正确的是_______。

a.在顺序存储结构中，有时也存储数据结构中元素之间的关系

b.顺序存储方式的优点是存储密度大，且插入、删除运算效率高

c.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立

d.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构

（838）   下述_____是顺序存储结构的优点。

a.存储密度大

b.插入运算方便

c.删除运算方便

d.可方便地用于各种逻辑结构的存储表示

（839）   下面关于线性表的叙述中，错误的是_____。

a.线性表采用顺序存储，必须占用一片连续的存储单元

b.线性表采用顺序存储，便于进行插入和删除操作

c.线性表采用链接存储，不必占用一片连续的存储单元

d.线性表采用链接存储，便于插入和删除操作

（840）   某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省时间。

a.顺序表     b.双链表       c.带头结点的双循环链表    d.单循环链表

（841）   静态链表中指针表示的是______。

a.内存地址    b.数组下标    c.下一元素地址    d.左、右孩子地址

（842）   下面的叙述不正确的是_______。

a.线性表在链式存储时，查找第i个元素的时间同i的值成正比

b.线性表在链式存储时，查找第i个元素的时间同i的值无关

c.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

d.线性表在顺序存储时，查找第i个元素的时间同i的值无关

（843）   下面说法错误的是_____。

a.静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

b.静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

c.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

d.静态链表就是一直不发生变化的链表。

（844）   在双向链表指针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;

（845）   下面说法正确的是______。

a.顺序存储结构的主要缺点是不利于插入或删除操作；

b.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的；

c.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好；

d.顺序存储方式只能用于存储线性结构。

（846）   下面说法正确的是______。

a.线性表只能用顺序存储结构实现。

b.为了很方便的插入和删除数据，可以使用双向链表存放数据。

c.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

d.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

（847）   下面说法正确的是_________。

a.数据元素是数据的最小单位。

b.队列逻辑上是一个下端口和上端能增加又能减少的线性表。

c.任何一个递归过程都可以转换成非递归过程。

d.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。

（848）   下面说法正确的是_________。

a.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。

b.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。

c.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。

d.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。

（849）   下面说法正确的是______。

a.在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不稳定的。

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.保证不产生冲突

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）   内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性_____。

a.快速排序       b.插入排序      c.归并排序         d.简单选择排序 

e.O（nlog2（n））f.O（n^2）  g.O（n^2log2（n））h.O（n）i.稳定j.不稳定

（858）   倒排文件包含若干个倒排表，倒排表的内容是______。

a.一个关键字值和关键字的记录地址；

b.一个属性值和该属性的一个记录地址；

c.一个属性值和该属性的全部属性地址；

d.多个关键字值和它们对应的某个记录的地址。

（859）   在下述几种树当中,_____可以表示静态查找表.

a.次优查找树;

b.二叉排序树; 

c.B-树

d.平衡二叉树

（860）   选择填空：

（1）.在文件局部有序或文件长度较小的情况下,最优内部排序的方法是____.

（2）.快速排序在最坏的情况下,时间复杂度是____,____的性能差;

（3）.就平均时间而言,____最佳.

a.:

（1）直接插入排序      

（2）起泡排序      （3）简单选择排序;

b.:

（1）O（nlog（n））      

（2）O（n^2）      （3）O（n^3）

c.:

（1）堆排序         

（2）起泡排序      （3）选择排序.

d.:

（1）堆排序         

（2）快速排序      （3）归并排序.

（861）   算法的时间复杂度取决于_____。

a.问题的规模

b.待处理数据的初态

c.bothaandb

（862）   假定有k个关键字互为同义词,若用线性探测法把这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.堆

（866）   若在线性表中采用折半查找法查找元素，该线性表应该_____。

a.元素按值有序

b.采用顺序存储结构"

c.元素按值有序，且采用顺序存储结构

d.元素按值有序，且采用链式存储结构

（867）   若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用____遍历方法最合适。

a.前序         b.中序         c.后序      d.按层次

（868）   对二叉排序树进行____遍历，可以得到该二叉树所有结点构成的排序序列。

a.前序         b.中序         c.后序      d.按层次

（869）   从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为____排序法。

a.插入         b.选择         c.谢尔      d.二路归并

（870）   排序趟数与序列的原始状态有关的排序方法是____排序法。

a.插入         b.选择         c.泡      d.快速

（871）   下面给出的四种排序法中____排序法是不稳定性排序法。

a.插入         b.泡         c.二路归并      d.堆积

（872）   下面哪一个方法可以判断出一个有向图中是否有环（回路）？

a.深度优先遍历   b.拓朴排序      c.求最短路径   d.求关键路径

（873）   下面关于程序设计风格的说法正确的是______。

a.中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。

b.顺序存储方式只能用于存储线性结构。

c.顺序查找法适用于存储结构为顺序或链接存储的线性表。

d.栈和队列都是限制存取点的线性结构。

（874）   已知变量定义：

charS[3]="AB"

char*P;

在执行了语句P＝S之后，*（P＋2）的值是______。

a.'B'

b.'\0'

c.不确定

d.字符'B'的地址

（875）   下面程序段的时间复杂度为______。

for（inti=0;i

{

for（intj=0;j

{

A[i][j]=i*j;

}

}

a.O（m2）   b.O（n2）   c.O（m*n）  d.O（m+n）

（876）   下列程序为将一条数据插入栈上：

voidadd（inttop,elementitem）

{ 

if（top>=MAX_STACK_SIZE-1）

   returnstack_full（）;

   stack[   ]=item;

}

则在stack[    ]的中括号内横线上的正确内容应为：

_____。

a.++*top      b.*top++      c.*top--      d.*top

（877）   有如下函数：

voidfun（structnodeh1,structnodeh2）

{    

structnode*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）   下面说法正确的是_____。

a.队列逻辑上是一个表头和表尾既能插入又能删除的线性表。

b.任何一个递归过程都可以转换成非递归过程。

c.与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。

d.在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。

（880）   下面说法正确的是_____。

a.在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。

b.哈希表查找无需进行关键字的比较。

c.在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。

d.B树查找算法的时间复杂性为O（n）。

（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，a1，a4，a2　　      d.a3，a4，a2，a1

（884）   以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是____。

a.rear－qulen

b.rear－qulen＋m

c.m－qulen

d.1＋（rear＋m－qulen）modm

（885）   高二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_______。

a.6　　   b.5　　      c.4　　      d.3

（886）   下列四种排序方法中，不稳定的方法是_____。

a.直接插入排序　　      b.冒泡排序

c.归并排序　　　　      d.直接选择排序

（887）   设有一个长度为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.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

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.直接插入排序    d.快速排序

（893）   _____是不稳定的排序方法。

a.冒泡排序     b.归并排序         c.堆排序          d.选择排序

（894）   从逻辑上，可以将数据结构分为_____两类。

a.动态表和静态表                 b.顺序结构和链式结构

c.线性结构和非线性结构           d.动态结构和静态结构

11.2   填空题

（895）   下面程序段的时间复杂度为________。

sum=1；

for（i=0;sum

{

sum+=1;

}

（896）   下列程序的功能是创建单向链表，请补充完整。

   #include

   #include

structlink

{

     char name[10];

       int   mark;

       structlink *next;

   };

   voidinsert（char*name, intmark）;

   structlink*head=NULL;

   main（）

   {

     char name[10];

       int   mark;

       struct link*t;

       while

（1） 

{

        scanf（"%s%d", name, &mark）;

            if（strcmp（name,"#"）==0）

 {

break;

}

        ______

（1）_______;

       }

     for（t=head;______

（2）_______）

      {

           printf（"<%s>:

%d\n", t->name, t->mark）;

}

   }

   voidinsert（char*name, intmark）

   {

      structlink*p;

      p=______（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。

其中，字符指针*b始终指向s的第一元素。

Match（s,t）

Chars,t;

｛

char*b=s;

char*p,*r;

for_________________________________

｛

for（p=s,r=t;*r!

=`\0`&&*p==*r;p++,r++）;

if_______________________