2012年数据结构期中考试试题及答案

一． 单项选择题（总计20分，2分/题）

1. 在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一

个元素，则采用（）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 2. 链表不具有的特点是（）。

A.可随机访问任一元素 B.插入、删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比 3. 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（）。

A.23415 B.54132 C.31245 D.14253

4. 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个

数为（）。

A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n

5. 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址

为1000的连续的内存单元中，则元素A[5,5]的地址为（）。 A.1140 B.1145 C.1120 D.1125 6. 数据结构被形式地定义为（D，R），其中D是①的有限集合，R是D上的②

的有限集合。

7. ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 8. ②A．操作 B．映象 C．存储 D．关系

9. 在单链表中p元素后面插入q指针所指的新元素时应进行的操作是( )。

A. p->next = q, q->next = p->next C. p ->next->next = q, q->next = p

B. q->next = p->next, p->next = q D. q->next = p, p->next->next = q

10. 在下面这段代码中，假定赋值运算为主要操作，那么它的时间复杂度为（）。

for(I=0；Ifor(J=I；JA．O(n) B. O(2n) C. O(n2) D. O(nlogn)

11. 不带头结点的单链表head为空的判定条件是

a. head=NULL b. head - >next=NULL c. head- >next=head d. head!=NULL

12. 一个栈的入栈序列为a,b,c,d,e，那么不可能出现输出序列为( ) A. edcba B decba C dceab D abcde

二． 判断题（总计15分，1分/题）

1. （×）串长度是指串中不同字符的个数。

2. （×）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除

等运算。

3. （×）在顺序表中取出第i个元素所花费的时间与i成正比。 4. （）在栈满情况下不能作进栈操作，否则产生“上溢”。 5. （×）线性表的长度是线性表所占用的存储空间的大小。

6. （×）双循环链表中，任意一结点的后继指针均指向其逻辑后继。 7. （）在对链队列做出队操作时，不会改变front指针的值。 8. （×）如果两个串含有相同的字符，则说它们相等。

9. （）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其

输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n) 10. （×）线性表就是顺序表。

11. （×）设指针p指向单链表中的一个结点，则语句序列u=p->next; u=u->next

将删除一个结点。

12. （×）链表的每个节点都恰好有一个指针。 13. （×）稀疏矩阵压缩存储后丧失随机存取功能。  14. （×）链式存储结构中一个结点的空间可以不连续。

15. （×）长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为O(n)。

三． 填空题（2分/空，共计20分）

1. 在双循环链表L中，指针p所指结点为尾结点的条件是（p->next=L）。 2. 在单链表中，删除指针p所指结点的后继结点的语句是

（p->next=p->next->next）。

3. 若某串的长度小于一个常数，则采用（顺序存储）存储方式最节省空间。 4. 对矩阵采用压缩存储是为了（节省空间）。

5. 已知栈的输入序列为1,2,3,...,n，输出序列为a1, a2, a3,..., an，符合a2=n的输出

序列共有（n-1）种。

6. 已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。现将其下三

角部分按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为（1095）。 7. 对于一个具有n个结点的单链表，在已知p所指向结点后插入一个新结点的时

间复杂度是 O(1) 在给定值为x的结点后插入一个新结点的时间复杂度是O（n）。

8. 数据的逻辑结构是指数据元素之间的逻辑关系。 9. 在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结

点的指针head可用p表示为head=p->next—>next 。

10. 在KMP算法中，模式串’aababaaaba’的next数组值为（0111212334）.

四． 问答题（共计15分）

1、 利用两个栈S1S2模拟一个队列时，如何用栈的运算来实现队列的运算（插入一个元素、

删除一个元素、判断队列为空）。请阐述实现思路，并用C语言描述实现方法。

以s1存储队列元素

（1）初始化：s1.top:=0; s2^.top:=0; （2）插入：相当于s1的入栈

（3）删除：将s1的元素逐个出栈并进s2栈， 出队即s2出栈，

再将s2的元素逐个出栈并进s1栈； （4）判空：相当于判断栈s1空否

2、设目标串为t=‘abcaabbabcabaacbacba’，模式p=‘abcabaa’。

1）计算模式p的next函数值 （3分）0111232

2）利用KMP算法进行模式匹配时第几趟匹配成功？（1分）

a b c a b a a 0 1 1 1 2 3 2

第1趟 a b c a a b b a b c A b a a c b 1 a b c a b a a 2 a b c a b a a 3 a b c a b a A 4 a b c a B a a 5 a b c A b a a

3、已知三维数组A[1..6,0..7, -1..4]，每个元素占用4个字节，存储器按字节编址。已知A的起始存储位置是1024，计算

1）数组A占用的存储空间大小（2分）

2）按低下标优先存储时，A[3,5,2]的第一个字节的地址（1分） 类似行优先

3）按高下标优先存储时，A[3,5,2]的第一个字节的地址（1分） 类似列优先

1）[(6-1+1) ×(7-0+1) ×(4-(-1)+1) ]× 4

a c b a =[6 ×8 ×6]×4=1152字节

2）1024+[(3-1)×8×6+(5-0) ×6+(2-(-1))] ×4=1540 3）1024+[(3-1)+(5-0)×6+(2-(-1))×8×6] ×4=1728

五． 算法设计题（10分/题，总计20分）

1. 单链表中，每个结点含有5个正整型的数据元素（若最后一个结点的数据元

素不满5个用0填充），试编写一算法查找值为n(n>0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素，则返回空指针。

Typedef struct node { int data[5];

Struct node *next; }node, *pnode

pnode searchx(pnode H, int x) {int i=0; pnode p; P=H While(P)

{ while (p->data[i]!=x)&&(i<5)}i++;

if(i<5) {printf(“i=%d”,i); return p;} else {i=0;p=p->next;} } return NUll }

2. 假设在长度大于1的循环单链表中， 既无头结点也无头指针，p为指向该链

表中某个结点的指针， 编写一个函数删除该结点的前驱结点。

解：本题利用循环单链表的特点，通过p指针可循环找到其前驱结点q及q的前驱结点 r,然后将其删除。实现本题功能的函数如下： node *del(p) node *p; {

node *q,*r;

q=p; /*查找p结点的前驱结点，用q指针指向* / while(q->next!=p) q=q->next;

r=q;/*查找q结点的前驱结点，用r指针指向*/ while(r->next!=q) r=r->next;

r->next=p;/*删除q所指的结点*/ free(q); return(p);

3. 已知两个整数集合A和B， 它们的元素分别依元素值递增有序存放在两个

单链表HA和HB中。下述算法的功能是什么? void union(ha,hb,hc)

node *ha,*hb,*hc; {

node *p,*q,*r,*s;

hc={node *}malloc(sizeof(node));

/*建立一个头结点， r总是指向HC链表的最后一个结点*/ r=hc;p=ha;q=hb;

while(p!=NULL&&q!=NULL) {

if (p->datadata) {

s=(node*)malloc(sizeof(node));

s->data=p->data; r->next=s; r=s;

p=p->next; }

else if (p->data>q->data) {

s=(node*)malloc(sizeof(node)); s->data=q->data; r->next=s; r=s;

q=q->next; }

else /*p->data==q->data的情况/

{

s={node*}malloc(sizeof(node)); q=q->next; } }

if(p==NULL)/* 把q及之后的结点复制到HC中*/ while (q!=NULL) {

s=(node*)malloc(sizeof(node));

s->data=p->data; r->next=s; r=s;

p=p->next; }

r->next=NULL; s=hc;

hc=hc->next;

free(s); /*删除头结点*/ }

假设HA和HB的头指针分别为ha和hb， 先设置一个空的循环单链表HC，头指针为hc，之后依次比较HA和HB的当前结点的元素值，将较小元素值的结点复制一个并链接到HC的末尾，若相等，则将其中之一复制一个并链接到HC的末尾。当HA或HB为空后，把另一个链表的余下结点都复制并链接到HC的末尾。

求两个集合的并集C，表示集合C的链表的结点仍依元素值递增有序存放