计05期中数据结构试题及答案

数据结构期中试题 一. 单项选择题（每项选择2分，共48分）

1．在数据结构中，从逻辑上可以把数据结构分成___C____。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

2．线性表是 A 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

3．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的 B 个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n 4．用链表表示线性表的优点是 C 。

(A)便于随机存取

(B)花费的存储空间较顺序存储少 (C)便于插入和删除

(D)数据元素的物理顺序与逻辑顺序相同

5.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用 C 存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)带尾指针的单循环链表 (D)双循环链表

6线性表的顺序存储结构是一种_A____的存储结构，线性表的链式存储结构是一种_____的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取

7、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 B 存储方式最

节省运算时间。

(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表

8．算法分析的目的是___C___，算法分析的两个主要方面是__A____。 ①A．找出数据结构的合理性

B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性

D．数据复杂性和程序复杂性

9、栈的特点是 ① B ，栈和队列都是 C ② 。

①、 A、先进先出 B、后进先出 ②、 A、顺序存储的线性结构

C、操作受限的线性结构

C、进优于出 D、出优于进

B、链式存储的线性结构 D、操作受限的非线性结构

10、 若进队列的序列为1,2,3,4，则 D 是一个出队序列。

A、3,2,1,4 B、3,2,4,1 C、4,2,3,1 D、1,2,3,4

11、设有一空栈，现有输入序列为1,2,3,4,5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为 C 。 A、5,4,3,2,1 B、2,1 C、2,3 D、3,4 12、 若广义表K满足head(K)=tail(K),则K为 ( B )

A.( ) B.( ( ) ) C. ( () , () ) D.( (),(),() )

13、对于下图所示的循环队列，队满的条件是 ① D ；队空的条件是 ② A 。

循环队列

①、②、 A、rear=front C、ront=rear+1

B、rear=front+1

D、front=(rear+1)%MAXSIZE

14. 删除一个双链表中结点p(非头结点和尾结点)的操作是（ B ） A. p->left->right=p->left;p->right->left=p->right B. p->left->right=p->right;p->right->left=p->ieft C. p->left=NULL;p->right=NULL D. p->right->left=p;p->left->right=p

15、设字符串s1=‘ABCDEFG’，s2=‘PQRST’，而T，sub1，sub2为空串。则运算s=Concat(T，SubString(sub1，s1，2，StrLength(s2))，SubString(sub2，s1，StrLength(s2)，2))后的串T的值为 D 。 A.‘BCDEF’ B.‘BCDEFG’

C.‘BCPQRST’ D.‘BCDEFEF’ E.‘BCQR‘ 16、串的长度是 D 。

A. 串中不同字母的个数 B. 串中不同字符的个数 C. 串中所含字符的个数，且大于0 D. 串中所含字符的个数

17． 一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( C )。

A．edcba B．decba C．dceab D．abcde

18、设有两个串 p和 q，求 q在 p中首次出现的位置的运算 B 。

A.连接 B.模式匹配 C.求子串 D.求串长 19． 广义表的长度是指（ A ）

A.广义表中元素的个数 B.广义表中原子元素的个数

C．广义表中表元素的个数 D．广义表中括号嵌套的层数

20、 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，

列下标j的范围从0到5，M按行优先存储时元素M[3][5]的起始地址与M按列优先存储时元素 （ B ）的起始地址相同。

A. m[2][4] B. M[3][4] C. M[3][5] D. M[4][4]

21、数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是 A① ，若该数组按行存放时，元素A[8][5]的起始地址是 ②C 。

①、 A. 80 B. 100 C. 240 D. 270

②、 A. SA+141 B. SA+144 C. SA+222 D. SA+225

22、一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为 C 。 A. n×n B. n×n/2 C. n×(n+1)/2 D. (n+1)×(n+1)/2

23、 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵

的转置运算，这种观点 B 。 A. 正确 B. 错误

24．对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）

A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销 25. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ D ）。

A. head（tail（tail（L））） B. tail（head（head（tail（L））））

C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)）

26．下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 27．稀疏矩阵一般的压缩存储方法有两种，即（ C ）。

A．二维数组和三维数组 B．三元组和散列 C.三元组和十字链表 D．散列和十字链表

二、填空题（将正确的答案填在相应的空位中,每空1分，共30分）

1、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是 元素集合①__，R是 ②_关系集合__。

2、存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序①__， ②连表___。 3、度量算法效率可通过 时间复杂度 ①__来进行。

4、设n为正整数，则下面程序段的时间复杂度是 ①_O(n)_。

i=1；k=0； while(i

k=k+10*i；i++；

}

5、带头结点的单链表Head为空的条件是___head->next=head_ ①______。 6、非空单循环链表L中*p是尾结点的条件是_____ ①__p->next=L_________。

7、在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__p->next ①___;和p->next=___s ②_____的操作。

8、在一个单链表中的指针p所指结点之前插入一个由指针s所指结点，可执行以下操作序列：

s->next= p->next①____; p->next=s; t=p->data;

p->data=___s->data ②_____; s->data=t;

9、在一个单链表中删除p所指结点时，应执行以下操作：

q= p->next;

p->data= p->next->data; p->next= ①_q->next ; free(q);

10、线性表(a1，a2，…，an)有两种存储结构： 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：

__① 顺序_ 存储密度较大；_顺序_②__存储利用率较高；_顺序_存储③__可以随机存取；__④连表___不可以随机存取；

_连表_⑤__插入和删除操作比较方便。

11、在单链表中，删除指针P所指结点的后继结点的语句是 ①__p->next=p-next->next_。

12、 带头结点的单循环链表Head的判空条件是__①_head->next=head__； 不带头结点的单循环链表的判空条件是___②head=NULL__。

13、删除带头结点的单循环链表Head的第一个结点的操作是__head->next=head->next->next①___；删除不带头结点的单循环链表的第一个结点的操作是__②_head=head->next__。

14、对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有 ① CAB 。

15、数据A、B、C、D依次进栈后，再从栈中取一数据，则它是 ① D 。则本栈得到DCBA的输出序列，其理由是 ② 后进先出 。

16、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓存区，而打印机则从该缓冲区中取出数据打印。该缓冲区的数据结构应该是一个 队列 ① 。

17、若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 ① 2 和 ② 4 。

18、将递归算法改写成等价的非递归算法，通常应该设置 ① 栈 的数据结构。

三、分析题（共22分）

1、分别画出执行下列程序的语句(4)、(5)、(6)以后各指针及链表的示意图。（共6分，各2分） (1)L = (LinkList) malloc(sizeof(Lnode)); (2)P = L;

(3)for(i=1; i<=4; i++){

P->next = (LinkList) malloc(sizeof(Lnode)); P = p->next; p->data = 2*i-1;

}

(4)P->next = NULL;

(5)for(i=4; i>=1; i--) LinkList_Insert(L,i+1,i*2); // 在第i+1结点前插入元素i*2 (6)for(i=1; i<=3; i++) LinkList_Delete(L,i); // 删除第i结点 执行语句(4)以后各指针及链表的示意图为: 执行语句(5)以后各指针及链表的示意图为:

执行语句(6)以后各指针及链表的示意图为:

2、令有串u=”aabcaba”和v=”aabcaabcaabcabaacb”，试完成下列两小题: （10分） (1) 、求Index(v,u)的值：Index(v,u)= 9 ; (2分) (2) 、分别求出u,v作为模式串在KMP算法中的next[j]值。(4分)

j 0 1 2 3 4 5 6 u next[j] j v next[j] -1 0 1 0 2 3 1 4 0 5 6 0 7 1 8 9 2 10 11 12 13 14 15 16 17 -1 0 1 0 0 1 2 3 4 5 6 7 8 9 0 1 2 0 （3）、下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\返回1，f(\

返回0（4分）； int f( ___char s[]_____) {int i=0,j=0;

while (s[j]) _j++______;

for(j--; ij______)

}

3、画出广义表 L1=(a,b,c,d) L2=( (),a,b,(c,d,e),f)的存储结构图（6分）。

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