1第一章第一章 概述概述 真题真题16.下列程序段的时间复杂度为_。for(i=1；inext=pnextnext B.p=pnext C.p=pnextnext D.pnext=p5.向一个栈顶指针为 hs 的链栈中插入一个*s 结点时，应执行的操作为（ ） A.hsnext=s; B.snext=hs;hs=s; C.snext=hsnext;hsnext=s; D.snext=hs;hs=hsnext;6.设循环队列的元素存放在一维数组 Q030中，队列非空时，front 指示队头元素的前一个位置，rear 指示队尾元素。如果队列中元素的个数为 11，front 的值为 25，则 rear 应指向的元素是（ ） A.Q4 B.Q5 C.Q14 D.Q157.定义二维数组 A18，010，起始地址为 LOC，每个元素占 2L 个存储单元，在以行序为主序的存储方式下，某数据元素的地址为 LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ ） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_和_。 19.在有 n 个元素的链队列中，入队和出队操作的时间复杂度分别为_和_。 20.在栈结构中，允许插入的一端称为_;在队列结构中，允许插入的一端称为_。 21.在循环队列中，存储空间为 0n-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.数组 A0.50.5的每个元素占 5 个字节，将其以列为主序存储在起始地址为 1000 的内存单元中，6则元素 A5 5的地址是（ ） A.1175 B.1180 C.1205 D.1210 18.在一个长度为 n 的顺序表中第 i 个元素（1in）之前插入一个元素时，需向后移动_个元素。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+1next-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.2456.一个栈的入栈序列是 a,b,c,d,e，则栈的输出序列不可能是( )A.dceab B.decba C.edcba D.abcde7.元素大小为 1 个单元，容量为 n 个单元的非空顺序栈中，以地址高端为栈底，以 top 作为栈顶指针，则出栈处理后，top 的值应修改为( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+117.设双链表中结点的前趋指针和后继指针的域名分别为 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 个元素前插入一个元素所需移动元素的个数为( )7A.5 B.6 C.7 D.94.设 p 为指向双向循环链表中某个结点的指针，p 所指向的结点的两个链域分别用 pllink 和prlink 表示，则同样表示 p 指针所指向结点的表达式是( )A.pllink B.prlink C.pllinkllink D.pllinkrlink5.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的存储地址是( )A. 110 B. 108 C. 100 D. 1206.设有一个栈，按 A、B、C、D 的顺序进栈，则可能为出栈序列的是( )A.DCBA B.CDAB C.DBAC D.DCAB7.在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top 为栈顶指针，则当做出栈处理时，top 变化为( )A.top+ B.top- C.top 不变 D.top=017.设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 p 指向与链表中结点同类型的一个新结点。现要将指针 p 指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“_”。18.单链表中逻辑上相邻的两个元素在物理位置上_相邻。19.在一个长度为 n 的数组中删除第 i 个元素（1in）时，需要向前移动的元素的个数是_。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);8if (headlink =head) if (headinfo=x) free (head); head=NULL； return (x) return (0); p=head; q=head; while (qlink!=head) q=(1) ; while (plink!=head) if (pinfo=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 所指结点，则需执行（ ） Aqnext=s；pnext=s； B.qnext=s；snext=p； C.qnext=s；qnext=p； D.qnext=s；snext=q； 5在长度为 n 的线性表中删除一个指针 p 所指结点的时间复杂度是（ ） AO(n) B.O(1) C.O(log2n) D.O(n2) 6设一个栈的输入序列是 a,b,c,d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是 （ ） Aa，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，则队满的条件是（ ） Afront=rear B.(front+1)%m=rear C.rear+1=front D.(rear+1)%m=front99设有二维数组 An n表示如下： ， 则 Ai i （0in-1）的值为（ ）Ai*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 18在顺序表上读表元算法的时间复杂度为_。 19双链表中前驱指针为 prior，后继指针为 next，在指针 P 所指结点前插入指针 S 所指的结点，需 执行下列语句：Snext=P;Sprior=Pprior;Pprior=S;_; 20设数组 A0.8 0.8的起始元