计算机软件技术基础总复习(共37页).doc

《计算机软件技术基础总复习(共37页).doc》由会员分享，可在线阅读，更多相关《计算机软件技术基础总复习(共37页).doc（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上计算机软件技术基础第二章 智能0801班2.1数据结构概论一、选择题1、数据的逻辑结构是（ A ）。 A数据的组织形式 B数据的存储形式 C数据的表示形式 D数据的实现形式2、组成数据的基本单位是（ C ）。 A数据项 B数据类型 C数据元素 D数据变量3、下面程序的时间复杂度为（ ）。 x=0； for（i=1；in；i+） for（j=i+1；j=n；j+） x+； AO（ ） BO（n2） CO（1） DO（n）4、下面程序的时间复杂度为（ ）。 for（i=0；im；i+） for（j=0；jn；j+） Aij=i*j； AO（m2） BO（n2） CO（mn

2、） DO（m+n）5、下面程序段的执行次数为（ ）。 for（i=0；ii；j+） state； An（n+1）/2 B（n-1）（n+2）/2 Cn（n+1）/2 D（n-1）（n+2）6、下面程序的时间复杂度为（A ）。 for（i=0；im；i+） for（j=0；jt；j+） cij=0； for（i=0；im；i+） for（j=0；jt；j+） for（k=0；kllink和p-rlink表示，则下列等式中（D ）成立。 Ap=p-llink Bp=p-rlink Cp=p-llink-llink Dp=p-llink-rlink10、线性表采用链式存储时，其地址（ D ）。 A必

3、须是连续的 B一定是不连续的 C部分地址必须是连续的 D连续与否均可以11、线性表是（ A ）。 A一个有限序列，可以为空 B一个有限序列，不可以为空 C一个无限序列，可以为空 D一个无限序列，不可以为空12、链式存储的线性表中的指针指向其（ B ）。 A前趋结点 B后继结点 C物理前趋 D物理后继13、设在链式存储的线性表中，设结点结构为 data link ，欲在p结点后插入一个结点q的关键步骤为（ A ）。 Aq-link=p-link； p-link=q； Bp-link=q-link； p-link=q； Cq-link=p-link； q-link=p； Dp-link=q-lin

4、k； q-link=p；14、设有指针head指向的带表头结点的单链表，现将指针p指向的结点插入表中，使之成为第一个结点，其操作是（ A）（其中，p-next、head-next分别表示p、head所指结点的链域）。 Ap-next=head-next； head-next=p； Bp-next=head-next； head=p； Cp-next=head； head=p； Dp-next=head； p= head；二、填空1、顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的（ N/2 ）个元素。2、线性表的长度是（ 数据

5、元素个数 ）。3、在带有头结点的双链表L中，指针p所指结点是第一个元素结点的条件是（pllink=h或h-r link=p）。4、某链表如下所示 若要删除值为C的结点，应做操作（ p-link=p-link-link ）。三、程序填空题1、设顺序存储的线性表存储结构定义为： struct sequnce ELEMTP elemMAXSIZE； int len； /*线性表长度域*/ 将下列简单插入算法补充完整。 void insert（struct sequnce *p，int i，ELEMTP x） v=*p； if（iv.len+1） printf（“Overflow“）； else fo

6、r（j=v.len；j=i；j- -） v.elemj+1=v.elemj； v.elemi= x ；v.len=v.len+1； 2、设线性链表的存储结构如下： struct node ELEMTP data； /*数据域*/ struct node *next； /*指针域*/ 试完成下列在链表中值为x的结点前插入一个值为y的新结点的算法。如果x不存在，则把新结点插在表尾。 void inserty（struct node *head，ELEMTP x，ELEMTP y） s=（struct node *）malloc（sizeof（struct node）； s-data=y； if（h

7、ead-data= =x）s-next=head；head=s； else q=head；p=q-next； while（p-data!=x & p-next!=NULL）q=p；p=p-next； if（p-data= = x）q-next=s；s-next=p； else p-next=s；s-next=NULL； 3、设线性链表的存储结构如下： struct node ELEMTP data； /*数据域*/ struct node *next； /*指针域*/ 试完成下列建立单链表的算法。 creat（） char var； head=（struct node *）malloc（siz

8、eof（struct node）； head-next= NULL ； while ( (var =getchar ( ) )!= n) ptr=（ struct node *）malloc（sizeof（struct node）； ptr-data= var ； ptr-next = head-next； head-next= ptr ； 4、下列算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同，试完成该算法。 void DelSameNode（LinkList L） /L是带头结点的单链表，删除其中的值重复的结点/ ListNode * p，*q，*r； p = L-nex

9、t； /p初始指向开始结点/ while（p） /处理当前结点p/ q = p； r = q-next； do /删除与结点*p的值相同的结点/ while（r&r-data!=p-data） q = r； r = r-next； if（r） /结点*r的值与*p的值相同，删除*r/ q-next = r-next； free（r）； r = q-next； while（ r ）； p = p-next； 2.3栈、队列、串一、填空题1、在栈中，下列说法正确的是（A ）。 A每次插入总是在栈顶，每次删除也总是在栈顶。 B每次插入总是在栈顶，每次删除总是在栈底。 C每次插入总是在栈底，每次删除总

10、是在栈顶。 D每次插入总是在栈底，每次删除也总是在栈底。2、设有一个栈，按A、B、C的顺序进栈，则下列（ C ）为不可能的出栈序列。 AABC BCBA CCAB DACB3、设有一个栈，按A、B、C、D的顺序进栈，则下列（D ）为可能的出栈序列。 ADCAB BCDAB CDBAC DACDB4、顺序栈的上溢是指（ B ）。 A栈满时作退栈运算 B栈满时作进栈运算 C栈空时作退栈运算 D栈空时作进栈运算5、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ D）。 Aselemtop=e； stop=stop+1； Bselemtop+

11、1=e； stop=stop+1； Cstop=stop+1； selemtop+1=e； Dstop=stop+1； selemtop=e； 6、设有5个元素A，B，C，D，E顺序进栈（进栈过程中可以出栈），出栈后依出栈次序进入队列，已知其出队次序为D，C，E，B，A，则该栈容量必定不小于（C ）。 A2 B3 C4 D57、设栈S的初始状态为空，现有五个元素组成的序列1，2，3，4，5，对该序列在栈S上依次进行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出栈的元素序列是（ C）。 A5，4，3，2，1 B2，1 C2，3 D3，48、在一个具有n个单元的顺序栈中，

12、假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为（ ）。 Atop不变 Btop=0 Ctop- - Dtop+9、向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（ B）。 Ahs-next=s； Bs-next=hs；hs=s； Cs-next=hs-next；hs-next=s； Ds-next=hs；hs=hs-next；10、在队列中，下列说法正确的是（A ）。 A每次插入总是在队尾，每次删除总是在队头。 B每次插入总是在队尾，每次删除也总是在队尾。 C每次插入总是在队头，每次删除也总是在队头。 D每次插入总是在队头，每次删除总是在队尾。1

13、1、在带头结点的链队列q中，用qfront表示队头指针，qrear表示队尾指针，结点结构为data next ，删除链队列的队头结点的主要语句为（B ）。 As=qfront； qfront-next= snext； Bs=qfront-next； qfront-next= snext； Cs=qfront-next； qfront= snext； Ds=q； qfront-next= snext；12、循环队列sq中，用数组elem存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则队列满的条件为（ D ）。 Asqfr

14、ont= sqrear Bsqfront= sqrear+1 C（sqfront +1）mod MAXSIZE= sqrear D（sqrear+1）mod MAXSIZE= sqfront13、循环队列sq中，用数组elem存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则在队列未满时元素x入队列的主要操作为（ A ）。 Asqrear= （sqrear+1）mod MAXSIZE； sqelemsqrear=x； Bsqelemsqrear=x； sqrear= （sqrear+1）mod MAXSIZE； Csqf

15、ront= （sqfront+1）mod MAXSIZE； sqelemsqfront=x； Dsqelemsqfront=x； sqfront= sqfront+1；14、循环队列sq中，用数组elem025存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，设当前sqfront为20，sqrear为12，则当前队列中的元素个数为（ ）。 A8 B16 C17 D1815、设循环队列的元素存放在一维数组Q030中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向（ ）

16、元素。 AQ4 BQ5 CQ14 DQ1516、队列操作的原则是（A ）。 A先进先出 B后进先出 C只能进行插入 D只能进行删除17、一个队列的入列序列是1234，则队列的输出序列是（ B）。 A4321 B1234 C1432 D324118、下列关于串的叙述中，不正确的是（ ）。 A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储二、填空题1、对于栈只能在（栈顶 ）插入和删除元素。2、设有一空栈，现有输入序列1，2，3，4，5，6，经过push，push，pop，push，pop，push，push后，输出序列是（ 2，

17、3 ）。、有一个循环队列如下图，其队满条件是（front=(rear+1)%n），队列空的条件是（rear=front）。三、程序填空题1、链队列的存储结构为： struct nodetype ELEMTP data； struct nodetype *next； struct linkqueue struct nodetype *front，*rear； /*front和rear分别为队列的头指针和尾指针*/完成下列删除队头元素的算法。 delq（struct linkqueue *r，ELEMTP *x） q=*r； if（q.front= =q.rear）printf（“QUEUE IS

18、 EMPTYn“）； elsep=q.front-next； q.front-next=p-next； if（p-next= =NULL）q.rear=q.front； *x=p-data；free（p）； 2.4数组1、设6行8列的二维数组A68=（aij）按行优先顺序存储，若第一个元素的存储位置为200，且每个元素占3个存储单元，则元素a54的存储位置为（B ）。 A308 B305 C266 D2692、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B ）。 A13 B33 C18 D403、设二

19、个数组为A07、B-52，38，则这两个数组分别能存放的字符的最大个数是（ C ）。 A7和35 B1和5 C8和48 D1和64、二维数组Mi，j的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下列j的范围从0到5。M按行存储时元素M3，5的起始地址与M按列存储时元素（ B）的起始地址下同。AM2，4 BM3，4 CM3，5 DM4，45、设二维数组为M08，010，每个元素占2L个存储单元，以行序为主序存储，第一个元素的存储位置为P。存储位置为P+50L的元素为（ A ）。AM2，3 BM2，2 CM3，3 DM3，46、设二维数组A的维数界偶定义为18，01

20、0，起始地址为LOC，每个元素占2L个存储单元，以行序为主序存储方式下，某数据元素的地址为LOC+50L，则在列序为主序存储方式下，该元素的存储地址为（D）。ALOC+28L BLOC+36L CLOC+50L DLOC+52L7、数组A140，130采用三元组表示，设数组元素与下标均为整型，则在非零元素个数小于（ D ）时，才能节省存储空间。 A1200 B401 C399 D4008、一维数组通常采用顺序存储结构，这是因为（C ）。 A一维数组是一种线性数据结构 B一维数组是一种动态数据结构 C一旦建立了数组，则数组中的数据元素之间的关系不再变动 D一维数组只能采用顺序存储结构9、对稀疏矩

21、阵进行压缩存储的目的是（B ）。 A方便存储 B节省存储空间 C方便运算 D节省运算时间10、设二维数组a05，06按行存储，每个元素占d个存储单元，如果每个元素改为2d个存储单元，起始地址不变，则元素a2，6的存储地址将要增加（ A）个存储单元。 A20d B21d C38d D39d11、一维数组与线性表的区别是（ ）。 A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变二、填空1、一个稀疏矩阵为， 则对应的三元组线性表为（0，2，2），（1，0，3），（2，2，-1），（2，3，5）。2、设有二维数组A09，019，其每个元素占两个字节，数组按

22、列优先顺序存储，第一个元素的存储地址为100，那么元素A6，6的存储地址为（232）。2.5树和二叉树一、选择题1、下列树的度为（ ）。 A2 B3 C5 D8 2、含10个结点的二叉树中，度为0的结点有4个，则度为2的结点有（ ）个。 A3 B4 C5 D63、对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为（ ）。 A98 B99 C97 D504、一棵深度为8（根的层次号为1）的满二叉树有（ ）个结点。 A256 B255 C128 D1275、设二叉树根结点的层数为1，若一棵高（深）度为h的二叉树只有度为0与度为2的结点，则其结点数至少为（ ）。 Ah

23、B2h-1 C2h D2h+16、对下列二叉树进行先根次序遍历，所得次序为（ ）。 AABCDEF BADCBFE CBCDAFE DDCBFEA7、一棵二叉树的前（先）序序列为ABCDEFG，则它的中序序列不可能为（ ）。 ACBDAFEG BDCBAEFG CCDBAGEF DBDCAFGE8、若先序遍历二叉树的结果为结点序列A，B，C，则有（ ）棵不同的二叉树可以得到这一结果。 A3 B4 C5 D69、具有n个结点的二叉树，有（ ）条边。 An Bn-1 Cn+1 D2n10、在具有n个结点的二叉树的二叉链表表示中，2n个孩子指针域中，只用到（ ）个域。 An Bn-1 Cn+1 D2

24、n11、对哈夫曼树，下列说法错误的是（ ）。 A哈夫曼树是一类带树路径长度最短的树。 B给出一组数，构造的哈夫曼树唯一。 C给出一组数，构造的哈夫曼树的带树路径长度不变。 D哈夫曼树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。12、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点数为（ ）。 A15 B16 C17 D4713、假定一棵三叉树的结点数为50，则它的最小高度为（ ）。 A3 B4 C5 D614、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）。 A23 B37 C46 D4415、二叉树的先序遍历为EFHIG

25、JK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（ ）。 AE BF CG DH16、在完全二叉树中，若一个结点是叶结点，则它没有（ ）。 A左孩子结点 B右孩子结点 C左孩子和右孩子结点 D左孩子结点，右孩子结点和兄弟结点17、（ ）二叉树，可以唯一地转化成一棵一般树。 A根结点无左孩子 B根结点无右孩子 C根据结点有两个孩子 D没有一棵18、具有65个结点的完全二叉树其深度为（ ）。 A8 B7 C6 D519、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子20、下面叙述中，不

26、正确的是（ ）。 A线性表中除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继 B树中有且仅有一个结点没有前驱 C环形队列中任何一个元素都有且仅有一个直接前驱和一个直接后继 D在树中，一个结点可以有多个直接后继21、有m个叶子结点的哈夫曼树，其结点总数是（ ）。 A2m B2m+1 C2m-1 D2（m+1）二、填空题1、在一棵二叉排序树上按（ ）遍历得到的结点序列是一个有序序列。2、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中（ ）个用于链接孩子结点。3、对于下面的二叉树，按后序遍历得到的结点序列为（ ）。三、程序填空题

27、1、下面算法实现，用一棵二叉树中的结点建立一个按关键字值从小到大次序排列的带表头结点的双向循环链表。二叉树的结点结构如下所示：其中，p是指向结点的指针；p-key表示结点的关键字域，p-left和p-right分别表示结点的左、右孩子的指针域。void fromtreetolist（p，l） /*p，h是指向二叉树中结点的指针，*/ /*l是指向双向循环链表表头结点的指针*/ if (p!=NULL) fromtreetolist（p-left，l）； fromtreetolist（p- right，l）； h=l； while （h-right!=l）&（h-right-keykey） h=

28、h-right； p-right=h-right； p-left=h； h-right-left=p； h-rihght=p； void buildlisttree（root，l） /*root是指向二叉树根结点的指针，*/ /*l是指向双向循环链表表头结点的指针*/ l=（struct nodetype *）malloc（sizeof（struct nodetype）； l-left=l； l-right=l； fromtreetolist（root，l）； 2.6、图1、设图的邻接矩阵为 ，则该图有（ ）个顶点。 A3 B4 C6 D92、设图的邻接矩阵为 ，则该图为（ ）。 A有向图 B

29、无向图 C强连通图 D完全图3、设图的邻接链表如下图所示，则该图有（ ）条边。 A4 B5 C10 D204、设有6个结点的无向图，该图至少应有（B）条边才能确保是一个连通图。 A5 B6 C7 D85、已知一有向图的邻接表存储结构如下，则根据有向图的深度优先遍历算法，从顶点V1出发，不能得到的顶点序列是（ ）。 AV1V2V3V5V4 BV1 V3 V4V5V2 CV1V2V4V5V3 DV1 V4V3V5V2 6、下列图的深度优先遍历序列为（ ）。 AABCDEFGH BABDHECFG CABEDHCFG DABCFGEDH7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（D）。 An B（n-1）2 C（n+1）2 Dn2 二、填空题1、设无向图G的顶点数为n，图G最少有（ ）边。2、对下列图它的生成树有（ ）棵。三、程序填空题1、下列算法将图的邻接矩阵存储结构转换为如下图所示的邻接表存储结构。图中左侧的记录数组的每个结点有两个域：el和fst；右侧链表中的结点是类型为node的记录类开