选择填空模拟题大全.doc

《选择填空模拟题大全.doc》由会员分享，可在线阅读，更多相关《选择填空模拟题大全.doc（38页珍藏版）》请在三一文库上搜索。

1、第一章概论二、填空题1.计算机专业人员必须完成的两项基本任务是：数据表示 和 数据处理。2.数据在计算机存储器中的存在形式称为 机内表示。3.概括地说，数据结构课程的主要内容包括: 数据的 逻辑结构、定义在 逻辑结构上的基本运算、数据的 存储结构和运算 的实现。此外，该课程还要考虑各种结构和实现方法的 评价和选择 。4.由一种 逻辑性 结构和一组 基本运算 构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。5.存储结构是逻辑结构的 存储 实现。6.数据表示任务是逐步完成的，即数据表示形式的变化过程是 机外表示-逻辑结构-存储结构。7.数据处理任务也是逐步完

2、成的，即转化过程是 处理要求-基本运算-运算算法。8.从数据结构的观点看，通常所说的数据应分成三个不同的层次，即数据、数据元素和数据项。9.根据需要，数据元素又被称为元素、结点、顶点或记录。10.在有些场合下，数据项又称为字段或域，它是数据的不可分割的最小标识单位。11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个 数据元素 构成，数据元素可由若干个 数据项 构成。12.根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构、图状结构四类基本逻辑结构，它们反映了四类基本的数据组织形式。13.根据操作的效果，可将运算分成以下两种基本类型：加工 型运算

3、其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；引用 型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。14.将以某种逻辑结构S为操作对象的运算称为“定义在S上的运算”，简称“S上运算”。15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“ 归纳 ”为B。16.存储实现的基本目标是建立数据的 机内表示 。17.一般地，一个存储结构包括存储结点、数据元素之间关联方式的表示、附加设施 三个主要部分。18.通常，存储结点之间可以有顺序存储方式、链式存储方式、索引存储方式、散列存储方式四种关联

4、方式，称为四种基本存储方式。19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为 给定逻辑结构S的存储实现或 存储映象 。20.一个运算的实现是指一个完成该运算功能的 程序 。运算实现的核心是处理步骤的规定，即 算法设计 。21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分为：运行终止的程序可执行部分、伪语言算法、非形式算法 三类。22.数据结构课程着重评论算法的 时空性能，又称为“ 算法分析 ”。23.通常从正确性能、易读性、健壮性、高效性等几方面评价算法的(包括程序)的质量。24.一个算

5、法的时空性能是指该算法的 时间性能（或时间效率）和 空间性能（或空间效率），前者是算法包含的 计算量，后者是算法需要的 存储量。25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量： 根据该类问题的特点合理地选择一种或几种操作作为“标准操作”； 确定每个算法在给定输入下共执行了多少次 标准操作，并将此次数规定为该算法在给定输入下的 计算量 。26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的 最坏情况时间复杂性或最坏情况时间复杂度 。以算法在所有输入下的计算量的加

6、权平均值作为算法的计算量，这种计算量称为算法的 平均时间复杂性 或 平均时间复杂度 。27.最坏情况时间复杂性和平均时间复杂性统称为 时间复杂性或时间复杂度 。28.在一般情况下，一个算法的时间复杂性是 算法输入规模 的函数。29.一个算法的输入规模或问题的规模是指 作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数 。30.常见时间复杂性的量级有：常数阶O(1)、对数阶O(log2n)、线性阶O (n)、平方阶O(n2)、和指数阶O(2n)。通常认为，具有指数阶量级的算法是 实际不可计算 ，而量级低于平方阶的算法是 高效 的。31.数据结构的基本任务是数据结构的 设计和实现 。

7、32.数据结构的课程的主要内容可以概括为：数据结构的定义、数据结构的实现、数据结构的评价和选择 。33. 数据的逻辑结构 与数据元素本身的内容和形式无关。34.从逻辑关系上讲，数据结构主要分为两大类，它们是 线性结构和非线性结构 。35.程序段“for(i=l;i=n;i+)k+;for(j=1;j=n;j+)l+=k;”的时间复杂度T(n)= O（n2）。36.程序段“i=1;while(i=0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个 结点 。a1称为 起始 结点，an称为 终端 结点，i称为ai在线性表中的 序号 或位置 。对任意一对相邻结点ai、ai1(1=i=

8、1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为b+（i-1）x k。10.以下为顺序表的插入运算，分析算法，请在_处填上正确的语句。Void insert_sqlist(sqlist L，datatype x，int i)/*将X插入到顺序表L的第i-1个位置*/ if( L.last = maxsize) error(“表满”)；if(iL.last+1)error(“非法位置”);for(j=L.last;j=i;j-) Ldataj=Ldataj-1;L.datai-1=x;L.last=L.last+1;11.对于顺序表的插入算

9、法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为n ，量级是O(n) 。插入算法的平均时间复杂性为n/2 ，平均时间复杂性量级是O(n) 。12.以下为顺序表的删除运算，分析算法，请在_处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/if(iL.last)error(“非法位置”)； for(j=i+1;j=L.last;j+) L.dataj-2=l.dataj-1; L.last=L.last-1;13.对于顺序表的删除算法delete_sqlist来说，若以结点移

10、动为标准操作，最坏情况时间复杂性及其量级分别是n-1和O(n)，其平均时间复杂性及其量级分别为(n-1)/2和O(n)。14.以下为顺序表的定位运算，分析算法，请在_处填上正确的语句。int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ i=1 ; while(iL.last)&(L.datai-1!=X)i+; if( iL.last )return(i); else return(0);15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为O(n) 。求表长

11、和读表元算法的时间复杂性为O(1) 。16.在顺序表上，求表长运算LENGTH（L）可通过输出 L.last 实现，读表元运算GET（L，i）可通过输出 L.datai-1 实现。17.线性表的常见链式存储结构有 单链表、循环链表和双链表 。18.单链表表示法的基本思想是用 指针 表示结点间的逻辑关系。19.所有结点通过指针的链接而组织成 单链表 。20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为 头结点 ，其它结点称为 表结点 。21.在单链表中，表结点中的第一个和最后一个分别称为 首结点 和 尾结点 。头结点的数据域可以不存储 任何信息 ，也可以存放一个

12、 特殊标志或表长 。22.单链表INITIATE（L）的功能是建立一个空表。空表由一个 头结点 和一个头结点 组成。23.INITIATE()的功能是建立一个空表。请在_处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ t=malloc(size) ; t-next=NULL ; return(t);24.以下为求单链表表长的运算，分析算法，请在 _处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ p=haed ;j=0;while(p-next!=NULL) p=p-next ; j+;re

13、turn(j); /*回传表长*/25.以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lklist(lklist head,int i) p=head;j=0; while( p-next!=NULL)&(jnext; j+; if(i=j) return(p); else return(NULL);26.以下为单链表的定位运算，分析算法，请在_处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ p=head;j=0;wh

14、ile( p-next!=NULL)&(p-data!=x )p=p-next;j+;if (p-data=x) return(j);else return(0);27.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(lklist head,int i) p=find_lklist(head,i-1); if( p!=NULL)&(p-next!=NULL ) q= p-next ; p-next=p-next; free(q); else error(“不存在第i个结点”)28.以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 vo

15、id insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ p=find_lklist(head,i-1);if(p=NULL)error(“不存在第i个位置”)；else s= mailloc(size) ;s-data=x; s-next= p-next ; p-next=s; 29.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*

16、/ ininiate_lklist(head);i=1;scanf(“%f”,&x);while(x!=$) insert_lklist(head,x,I) ; I+ ; scanf(“%f”,&x);return(head); 该建表算法的时间复杂性约等于 n(n-1)/2 ，其量级为O(n2) 。30.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ head=malloc(size); p=head; scanf(“%f”,&x); while(x!=$) q=malloc(size); q-data

17、x; p-next=q; p=q ; scanf(“%f”,&x); p-next=NULL ; return(head); 此算法的量级为O(n) 。31除单链表之外，线性表的链式存储结构还有 单向循环链表（简称循环链表）和 双向循环链表（简称双链表） 等。32循环链表与单链表的区别仅仅在于其尾结点的链域值不是NULL ，而是一个指向 头结点 的指针。33在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为 双链表 。34C语言规定，字符串常量按 字符数组 处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由 赋值

18、语句对其赋值。35含零个字符的串称为 空 串，用 表示。其他串称为 非空 串。任何串中所含 字符 的个数称为该串的长度。36当且仅当两个串的 长度 相等并且各个对应位置上的字符都 相同 时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的 子 串，该串称为它所有子串的 主 串。37串的顺序存储有两种方法：一种是每个单元只存一个字符，称为 非紧缩 格式，另一种是每个单元存放多个字符，称为 紧缩 格式。38通常将链串中每个存储结点所存储的字符个数称为 结点大小 。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上 不属于字符集的特殊符

19、号 。三、单向选择题 1对于线性表基本运算，以下结果是正确的是 ( ) 初始化INITIATE(L)，引用型运算，其作用是建立一个空表L= . 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度 读表元GET(L,i), 引用型运算。若1=idata是一个数据元素，p-next的值是一个指针11.单链表的一个存储结点包含（） 数据域或指针域 指针域或链域 指针域和链域 数据域和链域12.对于单链表表示法，以下说法错误的是（） 数据域用于存储线性表的一个数据元素 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 所有数据通过指针的链接而组织成单链表 NULL称为空

20、指针，它不指向任何结点，只起标志作用13.对于单链表表示法，以下说法错误的是（） 指向链表的第一个结点的指针，称为头指针 单链表的每一个结点都被一个指针所指 任何结点只能通过指向它的指针才能引用终端结点的指针域就为NULL尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表14有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ）将“指针型变量”简称为“指针”将“头指针变量”称为“头指针”将“修改某指针型变量的值”称为“修改某指针”将“p中指针所指结点”称为“P值”15设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 p-prior-next-=p-nex

21、t-next p-prior-prior-=p-next-prior p-prior-next-=p-next-prior p-next-next=p-prior-prior16.以下说法错误的是 （ ） 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表对单链表来说，只有从头结点开始才能扫描表中全部结点双链表的特点是找结点的前趋和后继都很容易对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。17在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ ）real和rear-next-nextr

22、ear-next 和realrear-next-next和rearrear和rear-next18.以下说错误的是 ( ) 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构在链表上实现读表元运算的平均时间复杂性为O（1）链入、摘除操作在链表上的实现可在O（1）时间内完成链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n）19在串的基本运算中，属于加工型运算的有 （ ）EQAL(S,T) LENGTH(S)CONCAT(S,T) REPLACE(S,T,R) INDEX(S,T)20. 在串的基本运算中

23、属于引用型运算的有 （ ）ASSIGN(S,T) INSERT(S1,i,S2)DELETE(S,i,j) SUBSTR(S,i,j) REPLACE(S,T,R)21循环链表主要优点是 （ ）不再需要头指针了已知某个结点的位置后，能够容易找到它的直接前趋在进行插入、删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ）正确 错误23以下说法错误的是 （ ）数据的物理结构是指数据在计算机内实际的存储形式算法和程序没有区别，所以在数据结构中二者是通用的对链表进行插人和删除操作时，不必移动结点双链表中至多只有

24、一个结点的后继指针为空24以下说法正确的是线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动25以下说法错误的是 （ ）求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低顺序存储的线性表可以随机存取由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活线性表的链式存储结构优于顺序存储结构26以下说法错误的

25、是 （ ）线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素27以下说法正确的是（ ）在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构顺序存储结构属于静态结构，链式结构属于动态结构顺序存储方式只能用于存储线性结构28.以下说法正确的是（ ）顺序存储方式的

26、优点是存储密度大、且插入、删除运算效率高链表的每个结点中都恰好包含一个指针线性表的顺序存储结构优于链式存储结构顺序存储结构属于静态结构，链式结构属于动态结构29.下面关于线性表的叙述正确的是( )线性表采用顺序存储，必须占用一片连续的存储单元线性表采用顺序存储，便于进行插人和删除操作线性表采用链接存储，不必占用一片连续的存储单元线性表采用链接存储，不便于插人和删除操作30.线性表L=(a1,a2,.,ai,.,an),下列说法正确的是( )每个元素都有一个直接前驱和直接后继线性表中至少要有一个元素表中诸元素的排列顺序必须是由小到大或由大到小的除第一个元素和最后一个元素外其余每个元素都有一个且仅

27、有一个直接前驱和直接后继31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( )正确 不正确32.设p,q是指针,若p=q,则*p=*q ,这种说法( ) 正确 不正确33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )必需是联系的 部分地址必须是连续的一定是不连续的 连续不连续都可以34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( )p=rear; rear=rear-next;rear=rear-next; free(rear);free(p)rear=rear-next-next; p=rear-next-next;free(rea

28、r); rear-next-next=p-next; free(p); 35. 单链表中，增加头结点的目的是为了 ( )使单链表至少有一个结点 标示表结点中首结点的位置方便运算的实现 说明单链表是线性表的链式存储实现36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 每个结点所代表的数据元素都一样。 每个结点所代表的数据元素包含的数据项的个数要相等 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 结点所代表的数据元素有同一特点37带头结点的单链表Head为空的判定条件是Head=Null Head-next=NUL

29、L Head-next=Head38.非空的单循环链表L的尾结点*P,满足P-next=NULL P=NULL P-next=L P=L.39.双向链表结点结构如下： LLink dataRLink其中：LLink是指向前驱结点的指针域：data是存放数据元素的数据域；Rlink是指向后继结点的指针域。下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是Q-LLink=P-LLink; P-LLink=Q;Q-Rlink=P; Q-Rlink=P;P-LLink=Q; P-LLink-Rlink=Q;P-LLink-Rlink=Q; Q-LLink=P-LLink;Q-LLink=P-LLink;Q-Rlink=P;P-LLink-Rlink=Q;P-LLink=Q;40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。顺序表 单链表 双链表 单循环链表41串是任意有限个符号构成的集合 符号构成