计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、在一个单链 …… 此处隐藏：3476字，全部文档内容请下载后查看。喜欢就下载吧 ……