北邮2011期中试题及答案

信息与通信学院数据结构期中考试试题

（2010211124~29）

一． 单项选择题（总计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上的②（）

有限集合。

①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 7. 在单链表中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

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

for(I=0；I

for(J=I；J

A．O(n) B. O(2n) C. O(n2) D. O(nlogn)

9. 不带头结点的单链表head为空的判定条件是( ) A. head=NULL B. head - >next=NULL C. head- >next=head D. head!=NULL

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

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

1. （×）串长度是指串中不同字符的个数。 2. （× ）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。 3. （× ）在顺序表中取出第i个元素所花费的时间与i成正比。 4. （√ ）在栈满情况下不能作进栈操作，否则产生“上溢”。 5. 6. 7. 8. 9. 10. 11.

（× ）线性表的长度是线性表所占用的存储空间的大小。

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

（√ ）若一个栈的输入序列为123?n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n) （×）线性表就是顺序表。

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

（×）链表的每个节点都恰好有一个指针。

（×）稀疏矩阵压缩存储后丧失随机存取功能。(题目不严格) （×）链式存储结构中一个结点的空间可以不连续。 （×）长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为O(n)。

12. 13. 14. 15.

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

1. 在双循环链表L中，指针p所指结点为尾结点的条件是（p->next=L）。

2. 在单链表中，删除指针p所指结点的后继结点的语句是（p->next=p->next->next，

free(p->next);）。

3. 若某串的长度小于一个常数，则采用（定长顺序）存储方式最节省空间。

4. 设循环队列的容量为30,设队头f指向队列中的第一个元素，队尾r指向队列中的最

后一个元素， 若f=24且r=10,则队列中有（ 16 ）个元素。

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

有（ n-1 ）种。

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

按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为（(4*10+6-1）*5+1000=1225）。 7. 对于一个具有n个结点的单链表，在已知p所指向结点后插入一个新结点的时间复杂度

是 O(1) 在给定值为x的结点后插入一个新结点的时间复杂度是 （ O(n) ）。 8. 线性表的元素长度为4，LOC(a1)=1000， 则LOC(a10)=（ 1036 (题目不严格) ）。 9. 在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针

head可用p表示为( head=p->next->next ) 。

10. 在KMP算法中，模式串’aababaaaba’的next数组值为（0121212334）. 四． 问答题（共计15分）

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

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

Enqueue(Element e) {

If (s1.length == maxsize) return OVERFLOW; Push(e); }

Dequeue(Element *e) {

If (s1.isEmpty())

return OVERFLOW;

While (!s1.isEmpty()) Push(s2,pop(s1,e)); Pop(s2,e);

While(!s2.isEmpty()) Push(s1,pop(s2,e)); } isEmpty(){ }

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

计算模式p的next函数值 ，试判断第几趟匹配成功，写出匹配过程。

return s1.isEmpty();

Next={0,1,1,1,2,3,2}

第一趟 abcaabbabcabaacbacba

abcabaa

第二趟 abcaabbabcabaacbacba

abcabaa

第三趟 abcaabbabcabaacbacba

abcabaa

第四趟 abcaabbabcabaacbacba

abcabaa

第五趟 abcaabbabcabaacbacba

abcabaa

第六趟 abcaabbabcabaacbacba

abcabaa

3、 已知三维数组A[1..6,0..7, -1..4]，每个元素占用4个字节，存储器按字节编址。已知A

的起始存储位置是1024，计算

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

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

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

1）[(6-1+1) ?(7-0+1) ?(4-(-1)+1) ]? 4 =[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分/题，总计30分）

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

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

设每个节点中5个数据元素保存在data[5]中，且设p指向第一节点 Node *findvalue(int n, int *index) {

While(p!=null) { for (i=0;i<5;i++)

if (p->data[i] == n) { } p=p->next; }

*index = 0; Return NULL; }

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

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

*index = i; return p;

pre = p; q = p->next;

本文来源：https://www.bwwdw.com/article/o1th.html