《数据结构01》复习题_答案.pdf

一选择题（每小题2分，共20分）

1．数据结构中，与所使用的计算机无关的是数据的___c___结构；

A）存储B）物理C）逻辑D）物理和存储

2．算法分析的目的是：c

A）找出数据结构的合理性B）研究算法中的输入和输出的关系

C）分析算法的效率以求改进D）分析算法的易懂性和文档性

3．计算机算法必须具备输入．输出和_b______等５个特性．

Ａ）可行性、可移植性和可扩充性B)可行性、确定性和有穷性

Ｃ）确定性、有穷性和稳定性Ｄ）易懂性、稳定性和安全性

４．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个

元素的地址是___b____

A）110B）108C）100D）120

5设有两个串p和q,求q在p中首次出现的位置的运算称作:

A)连接B)模式匹配C)求子串D)求串长

6.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均

要移动____b___个元素

A)8B)63.5C)63D)7

7设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维

数组B[1,n(n-1)/2]中,对下三角部分中任一元素a(i≤j),在一维数组B中下

i,j

标K的值是:（矩阵是A[1][1]开始）B

A)i(i-1)/2+j-1B)i(i_1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j

8.二叉树是非线性数据结构,所以__c_____

A)它不能用顺序存储结构存储B）它不能用链式存储结构存储

C）顺序存储结构和链式存储结构都能存储D）顺序存储结构和链式存储结构

都不能使用

9.有8个结点的无向连通图最少有__c_____条边（边数＝节点－1）

A)5B)6C)7D)8

10.所有排序方法中,关键字比较的次数与记录的初始排列次数无关的是

___d____

A)希尔B)冒泡C)插入D)选择

二.填空题(每小题2分,共20分)

1.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序_______、链

式_______、索引_______和散列_______。

2.在一个循环队列中,队首指针指向队首元素的前一个_______位置。

3.向一个长度为n的向量的第i个元素(1≤i≤n=1)之前插入一个元素时,需向

后移动____n-i+1__个元素,删除第i个元素(1≤i≤n)时,需向前移动_n-i_____

个元素。

4.向量、栈和队列都是__线性_____结构,可以在向量的任何_______位置插入和

删除元素;对于栈只能在_栈顶______插入和删除元素;对于队列只能在__队尾

____插入和_____队头__删除元素。

5.在动态存储管理中的三种分配策略是首次拟合_______、_最佳拟合______和

___最差拟合____。

6.广义表(((a)))的表头是__（（A））_____,表尾是_____（）__。

7.已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBAD’。写出模式

串的nextval函数值_______。P（77）

8.一棵具有257个结点的完全二叉树，它的深度为不大于k=log2(n)最大整数

8_____。

9．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为

___O（n^2）____；

若采用邻接表存储时，该算法的时间复杂度为O(n+e)_______。

10