浙大城市学院数据结构期中练习题(含答案).doc

一、单项选择题1针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ BD ）存储方式最节省时间。A单链表 B双链表 C单循环链表 D顺序表2线性表采用链式存储时，其地址（ B C ）。A一定是不连续的 B必须是连续的C可以连续也可以不连续 D部分地址必须是连续的3数据结构中，与所使用的计算机无关的是数据的（ AD ）结构。(第2页) A物理 B存储 C逻辑与物理 D逻辑4带头结点的单向链表的头指针为head，该链表为空的判定条件是（ A ）的值为真。Ahead = = NULL Bhead-next= =headChead-next= = NULL Dhead = =head-next5以下特征中，（ D ）不是算法的特性。 A有穷性 B确定性 C可行性 D有0个或多个输出 6设顺序存储的线性表长度为n，对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（ D A ）。An/2 Bn Cn-1 Dn-i+17设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ BA ）。 An-i+1 Bn-i Cn-i-1 Di8一个栈的进栈序列是5，6，7，8，则栈的不可能的出栈序列是（ A ）（进出栈操作可以交替进行）A5，8，6，7 B7，6，8，5C7，6，5，8 D8，7，6，59栈的插入删除操作在（ D ）进行。 A栈底 B任意位置 C指定位置 D栈顶10栈和队列的相同点是（ D ）。A都是后进先出 B都是后进后出C逻辑结构与线性表不同 D逻辑结构与线性表相同，都是操作规则受到限制的线性表11以下说法正确的是（ C ）。 A栈的特点是先进先出，队列的特点是先进后出 B栈和队列的特点都是先进后出C栈的特点是先进后出，队列的特点是先进先出 D栈和队列的特点都是先进先出12在C语言中，利用数组a存放字符串“Hello”，以下语句中正确的是（ A ）。Achar a10= “Hello”; Bchar a10; a=“Hello”;Cchar a10= Hello; Dchar a10=H,e,l,l,o;13元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（ D ）（进栈出栈可以交替进行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，4二、填空题1把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_存储_结构。2设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使p指向第一个结点，可用语句_p=p-next_。3结构中的数据元素存在一对一的关系称为_线性结构_结构。4要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，则可执行head=head- next; _p-next=head_ _。5在双向链表中，每个结点有两个指针域，一个指向_结点的前继_，另一个指向_结点的后继_。6设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，栈结点的指针域为next，数据域为data，则可执行x= _hs-data_ _；和hs= _hs-next_ _；7设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作_p-next=head_，就可使该单向链表构造成单向循环链表。8循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当_(r+1)%MaxSize=f_ _时表明队列已满。9从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-data;和_h=h-next_。(结点的指针域为next)三、综合题1设有一个不带头结点的单向链表，头指针为head，结点类型为NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。（1）新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1（2）把该结点插入链表的尾部，释放指针s的指向（3）删除链表的第一个结点（4）已知p1指向另一个新结点，把它插入到p所指结点和尾结点之间(1)NODE a; int *s;a.data=1;s=&a; (2)p-next=a; S=NULL; (3)LNode *cp; cp=head-next; Delete head;(4)p1-next=p-next; p-next=p;四、程序填空题1设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾结点*/head= （1） &a ;a.next=&b;b.next=&c;c.next=&d; （2） d.