数据结构试题(含答案)

数据结构试题

一、 单选题

1、 在数据结构的讨论中把数据结构从逻辑上分为 (C ）

A 内部结构与外部结构 B 静态结构与动态结构

C 线性结构与非线性结构 D 紧凑结构与非紧凑结构.

2、采用线性链表表示一个向量时，要求占用的存储空间地址(D ）

A 必须是连续的 B 部分地址必须是连续的

C 一定是不连续的 D 可连续可不连续

3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( D ）。

A n B n/2 C （n—1)/2 D (n+1)/2

4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。

A s→link = p→link; p→link = s；

B p→link = s； s→link = q;

C p→link = s→link; s→link = p;

D q→link = s； s→link = p;

5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。

A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序

6、设有两个串t和p,求p在t中首次出现的位置的运算叫做( B ）.

A 求子串 B 模式匹配 C 串替换 D 串连接

7、在数组A中，每一个数组元素A[i］[j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是( C ）.

A 80 B 100 C 240 D 270

8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A 栈 B 队列 C 循环队列 D 优先队列

9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C )。

10、在循环队列中用数组A[0。。m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是( D )。

A ( front - rear + 1） ％ m B ( rear - front + 1) % m

C （ front - rear + m) % m D （ rear — front + m) ％ m

11、一个数组元素a［i］与（ A )的表示等价。

A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。

A 指针 B 引用 C 值 D 变量

13、下面程序段的时间复杂度为( C )

for （int i=0;i〈m；i++）

for （int j=0;j

a［i］［j]=i*j;

A O(m2） B O(n2) C O（m*n) D O（m+n）

14、下面程序段的时间复杂度为（ B ）

int f（unsigned int n） ｛

if（n= =0 ｜| n= =1) return 1；

else return n*f（n-1）;

｝

A O（1) B O（n） C O（n2） D O（n !)

15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（ D )。

A 必须是连续的

B 部分地址必须是连续的

C 一定是不连续的

D 连续或不连续都可以

16、数据结构的定义为(D，S)，其中D是（ B ）的集合.

A 算法 B数据元素 C 数据操作 D 逻辑结构

17、算法分析的目的是( A ）。

A 找出数据结构的合理性

B 研究算法中输入和输出的关系

C 分析算法的效率以求改进

D 分析算法的易懂性和文档性

18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B ）。

A s—〉link=p；p->link=s； B s-〉link=p—>link；p—>link=s；

C s-〉link=p—>link；p=s; D p—〉link=s;s-〉link=p;

19、设单链表中结点结构为(data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ B ）

A s—>link=p—>link; p—>link=s； B q->link=s; s->link=p

C p->link=s-〉link; s-〉link=p； D p—>link=s; s—〉link=q； 20、设单链表中结点结构为（data，link)。若想摘除结点＊p的直接后继,则应执行下列哪一个操作（ A ）

A p—>link=p—〉link—>link; B p=p—〉link； p-〉link=p->link—>link；

C p—〉link=p—>link； D p=p—〉link-〉link；

21、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针.若想删除链表第一个结点，则应执行下列哪一个操作( D ）

A s=rear; rear=rear—〉link； delete s； B rear=rear-〉link; delete rear;

C rear=rear->link-〉link； delete rear; D s=rear—〉link—>link; rear—>link—>link=s-〉link; delete s；

22、设单循环链表中结点的结构为（data，link），且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。

A current—>link =null B first-〉link=current

C first=current D current-〉link=first

23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C ）。

A c,b，a B b,a，c C c,a,b D a，c，b

24、栈的数组表示中,top为栈顶指针,栈空的条件是( A )。

A top=0 B top=maxSize C top=maxSize D top=-1

25、栈和队列的共同特点是( C )。

A 都是先进后出 B 都是先进先出

C 只允许在端点处插入和删除 D 没有共同点

26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ，则判断队空的条件为( D ）.

A f+1= =r B r+1= =f C f= =0 D f= =r

27、当利用大小为n 的数组顺序存储一个队列时,该队列的最大长度为（ B ）

A n—2 B n—1 C n D n+1

28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时,首先应执行（ ）语句修改top指针。

A top++； B top—-； C top=0； D top;

29、设链式栈中结点的结构为（data， link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列( A ）操作。

A x=top—>data; top=top—〉link； B top=top—>link； x=top—〉data；

C x=top； top=top—〉link； D x=top->data;

30、设循环队列的结构是： const int Maxsize=100;

typedef int Data Type;

typedef struct ｛

Data Type data［Maxsize]；

Int front， rear;

｝ Queue;

若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句( D )

A Q。front= = Q.rear； B Q.front - Q。rear= = Maxsize；

C Q。front + Q.rear= = Maxsize; D Q.front= = （Q.rear+1)％ Maxsize;

31、设有一个递归算法如下:

int fact (int n ）

{ if （n〈=0) return 1；

else return n*fact（n—1)；

}

下面正确的叙述是( B )

A 计算fact(n） 需要执行n次递归 B fact（7)=5040

C 此递归算法最多只能计算到fact（8） D 以上结论都不对

32、设有一个递归算法如下

int x （int n） {

if (n〈=3） return 1；

else return x（n—2）+x(n-4）+1;

｝

试问计算 x（x（8）)时需要计算（ D )次x函数。

A 8 次 B 9 次 C 16 次 D 18次

33、设有广义表D（a，b,D），其长度为（ B ）,深度为（ A ）

A ∞ B 3 C 2 D 5

34、广义表A(a），则表尾为( C ）

A a B (（ ) ) C 空表 D （a）

35、下列广义表是线性表的有( C )