数据结构习题库.doc

知识点:01.绪论02.顺序表03.链表04.栈05.链队列06.循环队列07.串08.数组得顺序表示09.稀疏矩阵10.广义表11.二叉树得基本概念12.二叉树遍历、二叉树性质13.树、树与二叉树得转换14.赫夫曼树15.图得定义、图得存储16.图得遍历17.图得生成树18.静态查找(顺序表得查找、有序表得查找)19.动态查找(二叉排序树、平衡树、B树)20.哈希查找21.插入排序(直接插入、折半插入、2路插入、希尔排序)22.选择排序(简单选择、树形选择、堆排序)23.快速排序、归并排序101A1(1).数据得逻辑结构就是(A)。 A.数据得组织形式 B.数据得存储形式 C.数据得表示形式 D.数据得实现形式101A1(2).组成数据得基本单位就是(C)。 A.数据项 B.数据类型 C.数据元素 D.数据变量101B1(3).与顺序存储结构相比,链式存储结构得存储密度(B)。 A.大 B.小 C.相同 D.以上都不对101B2(4).对于存储同样一组数据元素而言,(D)。 A.顺序存储结构比链接结构多占空间 B.在顺序结构中查找元素得速度比在链接结构中查找要快 C.与链接结构相比,顺序结构便于安排数据元素 D.顺序结构占用整块空间而链接结构不要求整块空间101B2(5).下面程序得时间复杂度为(B)。 x=0; for(i=1;in;i+) for(j=i+1;j=n;j+) x+; A.O() B.O(n2) C.O(1) D.O(n)101B2(6).下面程序得时间复杂度为(C)。 for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j; A.O(m2) B.O(n2) C.O(mn) D.O(m+n)101C2(7).下面程序段得执行次数为(B)。 for(i=0;ii;j+) state; A.n(n+1)/2 B.(n-1)(n+2)/2 C.n(n+1)/2 D.(n-1)(n+2)101D3(8).下面程序得时间复杂度为(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)成立。 A.p=p-llink B.p=p-rlink C.p=p-llink-llink D.p=p-llink-rlink103A1(16).线性表采用链式存储时,其地址(D)。 A.必须就是连续得 B.一定就是不连续得 C.部分地址必须就是连续得 D.连续与否均可以103B1(17).线性表就是(A)。 A.一个有限序列,可以为空 B.一个有限序列,不可以为空 C.一个无限序列,可以为空 D.一个无限序列,不可以为空103B1(18).链式存储得线性表中得指针指向其(B)。 A.前趋结点 B.后继结点 C.物理前趋 D.物理后继103C2(19).设在链式存储得线性表中,设结点结构为 data link ,欲在p结点后插入一个结点q得关键步骤为(A)。 A.q-link=p-link; p-link=q; B.p-link=q-link; p-link=q; C.q-link=p-link; q-link=p; D.p-link=q-link; q-link=p;103C3(20).设有指针head指向得带表头结点得单链表,现将指针p指向得结点插入表中,使之成为第一个结点,其操作就是(A)(其中,p-next、head-next分别表示p、head所指结点得链域)。 A.p-next=head-next; head-next=p; B.p-next=head-next; head=p; C.p-next=head; head=p; D.p-next=head; p= head;104A1(21).在栈中,下列说法正确得就是(A)。 A.每次插入总就是在栈顶,每次删除也总就是在栈顶。 B.每次插入总就是在栈顶,每次删除总就是在栈底。 C.每次插入总就是在栈底,每次删除总就是在栈顶。 D.每次插入总就是在栈底,每次删除也总就是在栈底。104B2(22).设有一个栈,按A、B、C得顺序进栈,则下列(C)为不可能得出栈序列。 A.ABC B.CBA C.CAB D.ACB104B2(23).设有一个栈,按A、B、C、D得顺序进栈,则下列(D)为可能得出栈序列。 A.DCAB B.CDAB C.DBAC D.ACDB104A2(24).顺序栈得上溢就是指(B)。 A.栈满时作退栈运算 B.栈满时作进栈运算 C.栈空时作退栈运算 D.栈空时作进栈运算104D3(25).顺序栈S中top为栈顶指针,指向栈顶元素所在得位置,elem为存放栈得数组,则元素e进栈操作得主要语句为(D)。 A.s.elemtop=e; s.top=s.top+1; B.s.elemtop+1=e; s.top=s.top+1; C.s.top=s.top+1; s.elemtop+1=e; D.s.top=s.top+1; s.elemtop=e;104C2(26).设有5个元素A,B,C,D,E顺序进栈(进栈过程中可以出栈),出栈后依出栈次序进入队列,已知其出队次序为D,C,E,B,A,则该栈容量必定不小于(C)。 A.2 B.3 C.4 D.5104B2(27).设栈S得初始状态为空,现有五个元素组成得序列1,2,3,4,5,对该序列在栈S上依次进行PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH操作,出栈得元素序列就是(C)。 A.5,4,3,2,1 B.2,1 C.2,3 D.3,4104B2(28).在一个具有n个单元得顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为(C)。 A.top不变 B.top=0 C.top- - D.top+104D3(29).向一个栈顶指针为hs得链栈中插入一个*s结点时,应执行(B)。 A.hs-next=s; B.s-next=hs;hs=s; C.s-next=hs-next;hs-next=s; D.s-next=hs;hs=hs-next;105A1(30).在队列中,下列说法正确得就是(A)。A.每次插入总就是在队尾,每次删除总就是在队头。 B.每次插入总就是在队尾,每次删除也总就是在队尾。C.每次插入总就是在队头,每次删除也总就是在队头。 D.每次插入总就是在队头,每次删除总就是在队尾。105D3(31).在带头结点得链队列q中,用q.front表示队头指针,q.rear表示队尾指针,结点结构为data next ,删除链队列得队头结点得主要语句为(B)。 A.s=q.front; q.front-next= s.next; B.s=q.front-next; q.front-next= s.next; C.s=q.front-next; q.front= s.next; D.s=q; q.front-next= s.next;106C3(32).循环队列sq中,用数组elem存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,队列得最大容量为MAXSIZE,则队列满得条件为(D)。 A.sq.front= sq.rear B.sq.front= sq.rear+1 C.(sq.front +1)mod MAXSIZE= sq.rear D.(sq.rear+1)mod MAXSIZE= sq.front106C2(33).循环队列sq中,用数组elem存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,队列得最大容量为MAXSIZE,则在队列未满时元素x入队列得主要操作为(A)。 A.sq.rear= (sq.rear+1)mod MAXSIZE; sq.elemsq.rear=x; B.sq.elemsq.rear=x; sq.rear= (sq.rear+1)mod MAXSIZE; C.sq.front= (sq.front+1)mod MAXSIZE; sq.elemsq.front=x; D.sq.elemsq.front=x; sq.front= sq.front+1;106B2(34).循环队列sq中,用数组elem025存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,设当前sq.front为20,sq.rear为12,则当前队列中得元素个数为(D)。 A.8 B.16 C.17 D.18106B2(35).设循环队列得元素存放在一维数组Q030中,队列非空时,front指示队头元素得前一个位置,rear指示队尾元素。如果队列中元素得个数为11,front得值为25,则rear应指向(B)元素。 A.Q4 B.Q5 C.Q14 D.Q15105A1(36).队列操作得原则就是(A)。 A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除105B2(37).一个队列得入列序列就是1234,则队列得输出序列就是(B)。 A.4321 B.1234 C.1432 D.3241108C2(38).设6行8列得二维数组A68=(aij)按行优先顺序存储,若第一个元素得存储位置为200,且每个元素占3个存储单元,则元素a54得存储位置为(B)。 A.308 B.305 C.266 D.269109C2(39).设有一个10阶得对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85得地址为(B)。 A.13 B.33 C.18 D.40108A1(40).设二个数组为A07、B-52,38,则这两个数组分别能存放得字符得最大个数就是(C)。 A.7与35 B.1与5 C.8与48 D.1与6108C3(41).二维数组Mi,j得元素就是4个字符(每个字符占一个存储单元)组成得串,行下标i得范围从0到4,列下列j得范围从0到5。M按行存储时元素M3,5得起始地址与M按列存储时元素(B)得起始地址下同。 A.M2,4 B.M3,4 C.M3,5 D.M4,4108C2(42).设二维数组为M08,010,每个元素占2L个存储单元,以行序为主序存储,第一个元素得存储位置为P。存储位置为P+50L得元素为(A)。 A.M2,3 B.M2,2 C.M3,3 D.M3,4108C2(43).设二维数组A得维数界偶定义为18,010,起始地址为LOC,每个元素占2L个存储单元,以行序为主序存储方式下,某数据元素得地址为LOC+50L,则在列序为主序存储方式下,该元素得存储地址为(D)。 A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L109B2(44).数组A140,130采用三元组表示,设数组元素与下标均为整型,则在非零元素个数小于(D)时,才能节省存储空间。 A.1200 B.401 C.399 D.400108A1(45).一维数组通常采用顺序存储结构,这就是因为(C)。A.一维数组就是一种线性数据结构 B.一维数组就是一种动态数据结构C.一旦建立了数组,则数组中得数据元素之间得关系不再变动 D.一维数组只能采用顺序存储结构109A1(46).对稀疏矩阵进行压缩存储得目得就是(B)。 A.方便存储 B.节省存储空间 C.方便运算 D.节省运算时间108D3(47).设二维数组a05,06按行存储,每个元素占d个存储单元,如果每个元素改为2d个存储单元,起始地址不变,则元素a2,6得存储地址将要增加(A)个存储单元。 A.20d B.21d C.38d D.39d108B2(48).一维数组与线性表得区别就是(A)。 A.前者长度固定,后者长度可变 B.后者长度固定,前者长度可变 C.两者长度均固定 D.两者长度均可变107A1(49).下列关于串得叙述中,不正确得就是(B)。 A.串就是字符得有限序列 B.空串就是由空格构成得串 C.模式匹配就是串得一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储107B2(50).以下论断正确得就是(A)。 A.“”就是空串,“ ”就是空白串 B.“BEIJING”就是“BEI JING”得子串 C.“something”next;或L-next=p;)。103C3(7).某链表如下所示 info link p A B C D E 若要删除值为C得结点,应做操作(p-link=p-link-link)。104A1(8).对于栈只能在(栈顶)插入与删除元素。104C2(9).设有一空栈,现有输入序列1,2,3,4,5,6,经过push,push,pop,push,pop,push,push后,输出序列就是(2、3)。106B2(10).有一个循环队列如下图,其队满条件就是(front=(rear+1)%n),队列空得条件就是(rear=front)。 front 队头指针 rear 队尾指针109B2(11).一个稀疏矩阵为,则对应得三元组线性表为(0,2,2),(1,0,3),(2,2,-1),(2,3,5)。108C2(12).设有二维数组A09,019,其每个元素占两个字节,数组按列优先顺序存储,第一个元素得存储地址为100,那么元素A6,6得存储地址为(232)。112B1(13).在一棵二叉排序树上按(中序)遍历得到得结点序列就是一个有序序列。111C3(14).对于一棵具有n个结点得二叉树,当进行链接存储时,其二叉链表中得指针域得总数为2n个,其中(n-1)个用于链接孩子结点。112B2(15).对于下面得二叉树,按后序遍历得到得结点序列为(4,2,5,6,3,1)。 1 2 3 4 5 6115B1(16).设无向图G得顶点数为n,图G最少有(0)边。117C3(17).对下列图 1 6 2 5 3 4它得生成树有(6)棵。118C3(18).假定在有序表R019上进行二分查找,则比较三次查找成功得结点数为(4)。120D3(19).设有两个散列函数H1(K)=K mod 13与H2(K)=K mod 11+1,散列表为T012,用双重散列法(又称二次散列法)解决冲突。函数H1用来计算散列地址,当发生冲突时,H2作为计算下一个探测地址得地址增量。假定某一时刻散列表T得状态为: 0 1 2 3 4 5 6 7 8 9 10 11 12 T: 80 55 34下一个被插入得关键码为42,其插入位置就是(0)。122C3(20).已知一棵二叉排序树如下图所示,则在查找成功得情况下查找每个元素得平均查找长度为(2、75)。 80 50 90 40 70 100