数据结构导论真题分类整理详细

18.线性表中所含结点的个数称为______。

19.向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行______和top=p操作。

20.设一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的退栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为______。 35.设顺序表va中的数据元素递增有序。试编写算法实现将x插入到顺序表的适当位置上,以保持该

表的有序性。 3.若线性表最常用的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储方式是( ) A.单链表 B.双链表 C.单循环链表 D.顺序表

4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为( ) A.p—>next=p—>next—>next B.p=p—>next C.p=p—>next—>next D.p—>next=p 5.向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为( ) 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;

6.设循环队列的元素存放在一维数组Q[0‥30]中,队列非空时,front指示队头元素的前一个位置,rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应指向的元素是( ) A.Q[4] B.Q[5] C.Q[14] D.Q[15]

7.定义二维数组A[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为( )

A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L

18.在双链表中,存储一个结点有三个域,一个是数据域,另两个是指针域,分别指向____和_____。 19.在有n个元素的链队列中,入队和出队操作的时间复杂度分别为______和______。 20.在栈结构中,允许插入的一端称为______;在队列结构中,允许插入的一端称为______。 21.在循环队列中,存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为______。

3.在单链表中,存储每个结点需要有两个域,一个是数据域,另一个是指针域,指针域指向该结点的() A.直接前趋 B.直接后继 C.开始结点 D.终端结点

4.将两个各有n个元素的有序表合并成一个有序表,其最少的比较次数为() A.n B.2n-1 C.2n D.n2 5.栈和队列共同具有的特点是( )

A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出,也能先进后出 6.若用一个有6个单元的数组来实现循环队列,rear和front的初值分别为0和3。则从队列中删除一个元素,再添加两个元素后,rear和front的值分别为() A.1和5 B.2和4 C.4和2 D.5和1 7.数组A[0..5][0..5]的每个元素占5个字节,将其以列为主序存储在起始地址为1000的内存单元中,则元素A[5][5]的地址是( ) A.1175 B.1180 C.1205 D.1210

18.在一个长度为n的顺序表中第i个元素(1≤i≤n)之前插入一个元素时,需向后移动______个元素。 24.两个串是相等的,当且仅当两个串的长度相等且________的字符都相同。

34.设两个数据元素均为整型数据的线性表A=(a1,a2,…,an)和B=(b1,b2,…,bm)。若n=m且ai=bi(i=1,2,…,n)则认为A=B;若ai=bi(i=1,2,…,j)且aj+1

5

3.线性表采用链式存储结构时,要求内存中可用存储单元的地址( )

A.必须是连续的 B.必须是部分连续的 C.一定是不连续的 D.连续和不连续都可以 4.设h是指向非空带表头结点的循环链表的头指针,p是辅助指针。执行程序段 p=h;

while (p->next->next!=h) p=p->next; p->next=h;

后(其中,p->next为p指向结点的指针域),则( )

A.p->next指针指向链尾结点 B.h指向链尾结点 C.删除链尾前面的结点 D.删除链尾结点

5.设顺序表有19个元素,第一个元素的地址为200,且每个元素占3个字节,则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245

6.一个栈的入栈序列是a,b,c,d,e,则栈的输出序列不可能是( )A.dceab B.decba C.edcba D.abcde 7.元素大小为1个单元,容量为n个单元的非空顺序栈中,以地址高端为栈底,以top作为栈顶指针,则出栈处理后,top的值应修改为( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,指针s指向双链表中的一个结点(该结点既非头结点,也非尾结点),则删除s指针所指向结点的操作为―s->tl->r1=s->r1;‖和―_______‖。 32.如题32图所示,在栈的输入端有6个元素,顺序为A,B,C,D,E,F。能否在栈的输出端得到序列DCFEBA及EDBFCA?若能,给出栈操作的过程,若不能,简述其理由。

35.某带头结点的单链表的结点结构说明如下: typedef struct node1 { int data;

struct node1 *next }node;

试设计一个算法int copy(node *head1, node *head2),将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。

3.设顺序表有9个元素,则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9

4.设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示p指针所指向结点的表达式是( )

A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink

5.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是( ) A. 110 B. 108 C. 100 D. 120

6.设有一个栈,按A、B、C、D的顺序进栈,则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB

6

7.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为( )

A.top++ B.top-- C.top不变 D.top=0

17.设有指针head指向不带表头结点的单链表,用next表示结点的一个链域,指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中,使之成为第一个结点,则所需的操作为―p→next=head;‖和―________‖。

18.单链表中逻辑上相邻的两个元素在物理位置上______相邻。

19.在一个长度为n的数组中删除第i个元素(1≤i≤n)时,需要向前移动的元素的个数是________。 31.如题31图所示,输入元素为A,B,C,在栈的输出端得到一个输出序列ABC,试写出在栈的输入端三个可能的输入序列。

34.下面程序段为删除循环链表中第一个info域值等于x的结点,请填上程序中缺少的部分。循环链表的结构如题34图所示:

struct node{ int info; struct node *link; }

int Delete (struct node *head, int x)

{ struct node *p, *q; /*p:当前处理的结点;q:p的前驱结点*/

if (! head ) return (0); if (head→link ==head) { if (head→info==x)

{ free (head); head=NULL; return (x) } return (0); }

p=head; q=head;

while (q→link!=head) q=(1) ; while (p→link!=head)

7

{ if (p→info==x)

{ (2) ;

if (p==head) head=(3) ; free (p);return (x); }

else { q=p ;(4) ;} } return (0);

}

1.关于栈和队列的说法中正确的是( )

A.栈和队列都是线性结构 B.栈是线性结构,队列不是线性结构 C.栈不是线性结构,队列是线性结构 D.栈和队列都不是线性结构 2.关于存储相同数据元素的说法中正确的是( )

A顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 3.从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是( ) A.线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构

4.已知一个单链表中,指针q指向指针p的前趋结点,若在指针q所指结点和指针p所指结点之间插入指针s所指结点,则需执行( ) A.q→next=s;p→next=s; B.q→next=s;s→next=p; C.q→next=s;q→next=p; D.q→next=s;s→next=q; 5.在长度为n的线性表中删除一个指针p所指结点的时间复杂度是( ) A.O(n) B.O(1) C.O(log2n) D.O(n2) 6.设一个栈的输入序列是a,b,c,d,则所得到的输出序列(输入过程中允许出栈)不可能出现的是( ) A.a,b,c,d B.a,b,d,c C.d,c,b,a D.c,d,a,b 7.关于串的叙述中,正确的是( )

A.空串是只含有零个字符的串 B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列

8.在具有m个单元的循环队列中,队头指针为front,队尾指针为rear,则队满的条件是( ) A.front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front

9.设有二维数组A[n][n]表示如下: , 则A[i][i](0≤i≤n-1)的值为( )

A.i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 18.在顺序表上读表元算法的时间复杂度为_______。

19.双链表中前驱指针为prior,后继指针为next,在指针P所指结点前插入指针S所指的结点,需执行下列语句:S→next=P;S→prior=P→prior;P→prior=S;_______; 20.设数组A[0..8][0..8]的起始元素位置为a,每个元素占2 L个存储单元,按行序为主序存储。若元素A[i][j]的存储位置为a+66 L,则元素A[j][i]的存储位置为_______。

29.有一字符串序列为5*-x-y/x+2,利用栈的运算将其输出结果变为5x-*yx+/-2,试写出该操作的入

8

联系客服:779662525#qq.com(#替换为@)