必看2010-2011年数据结构试卷

·试卷

一、单项选择题(本大题共15小题，每小题2分，共30分) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 郑州轻工业学院 2011/ 2012 学年 第 2学期 数据结构 试卷 专业年级及班级 姓名 学号

1.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构 称为（ A ） A.树状结构 B.网状结构 C.线性结构 D.层次结构 2.下面算法程序段的时间复杂度为( C ) for ( int i=0; i

A. O(m2) B. O(n2) C. O(mn) D. O(m+n)

3. 某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（ D ） A.单链表 B.双链表

C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表

4.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3….，pn，若p1是n，则pi是（ C ） A.i B.n-i C.n-i+l D.不确定

5.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( A ) A. O(1)

B. O(n)

C. O(log2n) D. O(n)

6.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是 （ D ） A.p - > data = - 1 B.p - > next = NULL C.p - > next - > next=head D.p - > next = head

7.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ D ）

A.p1－＞next=p2－＞next;p2－＞next=p1－＞next; B. p2－＞next=p1－＞next;p1－＞next=p2－＞next;

C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p; 8.一个链串的结点类型定义为 ﹟define NodeSize 6 typedef struct node{

char data[NodeSize]; struct node*next; }LinkStrNode;

如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（ D ） A.1/3 B.1/2 C.2/3 D.3/4

9.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+l，则x进栈的正确操作是（ A ）

A.top=top-1；V[top]=x B.V[top]=x；top=top+1 C.top=top+1；V[top]=x D.V[top]=x；top=top-1 10.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( D ) A.1243 B. 1432 C. 2134 D.4312 11.队列是( A ) A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表

12.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（B ） A.2个 B.3个 C.4个 D.6个

13.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（ C ） A.470 B.471 C.472 D.473

14.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m;

15.对于广义表A，若head(A)等于tail(A)，则表A为（ B ） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( ))

装 订 线 第 页/共 页

节 约 用 纸 两 面 书 写

二、填空题（本大题共10小题，每小题2分，共20分）

1.数据结构由数据的逻辑结构、存储结构和数据的_____基本操作_______三部分组成。 2.在数据的逻辑结构和存储结构中，与计算机无关的是__ 逻辑结构 ____。 3.数据的不可分割的最小标识单位是__ 数据项___，它通常不具有完整确定的实际意义，或不被当作一个整体对待。

4.在单链表中某结点后插入一个新结点，需要修改___2____个结点指针域的值。 5.在单链表中，除了第1个元素结点外，任一结点的存储位置均由___前一结点的指针_____指示。

6.线性表L=(a1,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2______。

7.假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=___34_______。

8.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是___18___和____32__。

9.已知三对角矩阵A[10][10]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[6][7] 的地址为___。 10.已知广义表A=(x，((a，b)，c))，函数head(head(tail(A)))的运算结果是_____。 三、算法阅读题（本大题共3小题，每小题10分，共30分） 1.阅读下列算法，并回答问题：

（1）假设L=（3，7，7，11，20，20，20，51，51），写出执行函数f1（&L）后的L； （2）简述f1的功能。

void f1(SeqList*L) { ∥L为非空的有序表 int i=1,k=0;

while(i＜L－＞length）｛

if(L－＞data[i]!=L－＞data[k])

L－＞data[++k]=L－＞data[i];

i++;

}

L－＞length=k+1；

} (1) (2)

2.阅读下列算法，并回答问题： （1）假设栈S=（3，8，6，2，5），其中5为栈顶元素，写出执行函数f2（&S）后的S；

（2）简述函数f2的功能。

void f2(Stack *S){

Queue Q；InitQueue(&Q); while(!StackEmpty(S)) EnQueue(&Q,Pop(&S)); while(!QueueEmpty(Q)) Push(&S,DeQueue(&Q));

}

（1） （2）

3.阅读下列程序。

void f3(int A[]， int n) {

int i,j,m;

for (i=1；i

for (j=0；j

m=A[i*n+j]；

A[i*n+j]=A[j*n+i]； A[j*n+i]=m； }

}

回答下列问题：

? 1 2 3???(1)已知矩阵B=? 4 5 6?，将其按行优先存于一维数组A中，给出执行函数调

? 7 8 9???用f3(A，3)后矩阵B的值；

第 页/共 页

节 约 用 纸 两 面 书 写

(2)简述函数f3的功能。

四、算法设计题(每题10分，共20分)

假设以单链表表示线性表，单链表的类型定义如下：

typedef struct node { DataType data；

Struct node *next； } LinkNode，* LinkList；

1.编写算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(LinkList &L) { // 逆置带头结点的单链表 L LinkList p,succ;

p=L->next; L->next=NULL; while ( p) {

q=p->next; // q指向*p的后继 p->next=L->next;

L->next=p; // *p插入在头结点之后 p = q; } }

2.编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode (LinkList head，DataType x) LinkList delnode (LinkList head，DataType x) {

LinkList p=head,q; while(p->next) {

if(p->next->data==x) {

q=p->next;

p->next=q->next; free(q); }

p=p->next; }

}

第 页/共 页

节 约 用 纸 两 面 书 写

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库必看2010-2011年数据结构试卷在线全文阅读。