当前位置：文档库 › 数据结构第1阶段测试题

数据结构第1阶段测试题

江南大学现代远程教育第一阶段测试卷

考试科目:《数据结构》第一章至第四章（总分100分）时间：90分钟______________学习中心（教学点）批次：层次：

专业：学号：身份证号：

姓名：得分：

一、选择题（每题3分，共30分）

1、（）是数据的不可分割的最小单位。

Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构

2、若采用顺序映象，则数据元素在内存中占用的存储空间（）。

Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续

3、下列说法中错误的是（）。

Ａ、栈是一种非线性结构

Ｂ、一个数据元素由一或多个数据项构成

Ｃ、在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现

Ｄ、语句的频度就是语句的执行次数

4、以下属单链表优点的是（）。

Ａ、顺序存取Ｂ、插入操作能在O(1)的时间复杂度上完成

Ｃ、插入时不需移动数据元素Ｄ、节省存储空间

5、顺序表中数据元素的存取方式为（）。

Ａ、随机存取Ｂ、顺序存取Ｃ、索引存取Ｄ、连续存取

6、设输入序列为ABC，输出序列为CBA，则经过的栈操作为（）。

Ａ、push,pop,push,pop,push,pop Ｂ、push,push,push,pop,pop,pop

Ｃ、push,push,pop,pop,push,pop Ｄ、push,pop,push,push,pop,pop

7、若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。Ａ、1和5 Ｂ、2和4 Ｃ、4和2 Ｄ、5和1

8、串是一种特殊的线性表，其特殊性体现在（）。

Ａ、可以顺序存储Ｂ、数据元素是一个字符

Ｃ、可以链接存储Ｄ、数据元素可以是多个字符

9、设串s='abcdefgh'，则其子串数为（）。

Ａ、8 Ｂ、37 Ｃ、36 Ｄ、9

10、设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（）。

Ａ、ab Ｂ、cdefg Ｃ、abcdefg Ｄ、abcdefgab

二、（10分）设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？

for(x=0;x

for(y=0;y

a+=2;

三、（15分）设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。

⑴在p所指结点之前插入s所指结点；

⑵在L中最后一个结点之后插入s所指结点；

⑶删除p所指结点的直接后继；

⑷删除L中第一个结点。

四、（10分）有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

五、（15分）设a='colomn'，b='How are you!'，c='please'，试求：

⑴ StrLength(b)的返回值；

⑵ Index(a,'o',5)的返回值；

⑶执行StrInsert(a,3,c)后串a的值；

⑷执行Replace(c,'e','x')后串c的值；

⑸执行SubString(s,b,5,3)后串s的值。

六、（20分）假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。

答案：

一、选择题（每题3分，共30分）

C、A、A、C、A、B、B、B、B、D

二、设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？

for(x=0;x

for(y=0;y

a+=2;

答：n2

三、设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。

⑴在p所指结点之前插入s所指结点；

⑵在L中最后一个结点之后插入s所指结点；

⑶删除p所指结点的直接后继；

⑷删除L中第一个结点。

答：

⑴q=L;

while(q->next!=p)q=q->next; //q指向p的直接前驱

s->next=p;

q->next=s;

⑵q=L;

while(q->next)q=q->next;

s->next=NULL;

q->next=s;

⑶q=p->next; //q指向待删结点

p->next=q->next;

free(q);

⑷q=L->next;

L->next=q->next;

free(q);

四、有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

答：CDEBA CDBEA CDBAE

五、设a='colomn'，b='How are you!'，c='please'，试求：

⑴ StrLength(b)的返回值；

⑵ Index(a,'o',5)的返回值；

⑶执行StrInsert(a,3,c)后串a的值；

⑷执行Replace(c,'e','x')后串c的值；

⑸执行SubString(s,b,5,3)后串s的值。

答：

（1）12

（2）0

（3）’copleaselomn’

（4）’plxasx’

（5）’are’

六、假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。

答：

#define MAXQSIZE 100

typedef struct{

ElemType base[MAXQSIZE];

int rear;

int length;

}Queue;

Status EnQueue(Queue &Q,ElemType e){

if(Q.length==MAXQSIZE) return ERROR;

Q.rear=(Q.rear+1)%MAXQSIZE;

Q.base[Q.rear]=e;

Q.length++;

return OK;

}//EnQueue

Status DeQueue(Queue &Q,ElemType &e){ if(!Q.length) return ERROR;

front=(Q.rear-Q.length+1)%MAXQSIZE; e=Q.base[head];

Q.length--;

}//DeQueue

数据结构第一章试题

Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (1)A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法 (2)A．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3.下面关于算法说法错误的是（）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 4．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 5．以下数据结构中，哪一个是线性结构（）？ A．广义表 B.二叉树 C.稀疏矩阵 D.串 6．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()

数据结构考试试题及答案

数据结构一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）

十套数据结构试题及答案55426知识讲解

十套数据结构试题及答案55426

数据结构试卷（一）一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( a )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( d ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( d ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( c )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1] 中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 c n） D. O A. O（1） B. O（n） C. O（1og 2 （n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_ 易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。

数据结构试题及答案(免费)

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。

数据结构试题及答案

数据结构试题及答案数据结构试题(,)参考答案班别学号姓名成绩一、单项选择(每小题2分，共24分) 1.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环 B ) 2.串是任意有限个( A.符号构成的序列 B.字符构成的序列 C.符号构成的集合 D.字符构成的集合 3.设矩阵A(aij,1<=i,j<=10)的元素满足: aij<>0(i>=j,1<=i,j<=10),aij =0 (i

A.64 B.63 C.31 D.32 7.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为( C ) A.24 B.25 C.23 D.2无法确定 8.设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则下面不正确的说法是( D ) A.G'为G的子图 B.G'为G的一个无环子图 C.G'为G的极小连通子图且V'=V D.G'为G的连通分量 1 9.用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值( D ) A.一定都是同义词 B.一定都不是同义词 C.都相同 D.不一定都是同义词 10.二分查找要求被查找的表是( C ) A.键值有序的链接表 B.链接表但键值不一定有序表 C.键值有序的顺序表 D.顺序表但键值不一定有序表 11.当初始序列已经按键值有序，用直接插入法对其进行排序，需要比较的次数为( B ) 2 A. n B. n-1 C. logn D. nlogn 22 12.堆是一个键值序列{K1,K2,...,Ki,...,Kn},对i=1,2,...,n/2 ，满足 ( A ) ? ? A. Ki<=K2i且Ki<=K2i+1(2i+1<=n) B.Ki

数据结构练习题(含答案)

数据结构练习题习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂

性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ ,

东南大学十套数据结构试题及答案

数据结构试卷（一）三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的返回值所表示的线性表。 2.void ABC(BTNode * BT) {

if BT { ABC (BT->left); ABC (BT->right); cout<data<<' '; } } 该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(itemdata) return Find(______________,item); else return Find(_______________,item); }//if } 六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)

数据结构试题答案

第一章概论一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s

数据结构考试题库

绪论一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。精心整理，用心做精品2

A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以三、简答题 1.算法的特性是什么。答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。精心整理，用心做精品3

数据结构试题及答案

数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为

数据结构第一章考试题库(含答案)

第1章绪论一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

数据结构练习题

数据结构练习题一、简答题 1．什么是拓扑排序？ 2．什么是堆积？ 3．图的邻接矩阵与邻接表两种存储表示法在空间代价上的差别为何？ 4．算法与程序的区别是什么? 5．什么是堆(heap)？ 6．什么是栈(stack)？ 7．什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树？ 8．举例说明希尔(Shell)排序是否是稳定的排序方法？ 9．什么是遍历运算？ 10．什么是A VL树？ 11．链表中的表头指针、表头结点和开始结点有什么不同？各自所起的作用是什么？12．举例说明直接选择排序是否是稳定的排序方法？ 13．什么是完全二叉树(complete binary tree) ？ 14．什么是稀疏矩阵(sparse matrix) ？ 15．试述链接存储结构的优缺点。 16．什么是A VL树，它与最佳二叉排序树最主要的差别是什么？ 17．什么是假溢出？ 18．什么是排序算法的“稳定性”？ 19．设高度为h的二叉树中只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？ 20．顺序查找、折半查找和分块查找各自的平均查找长度ASL是多少？二、单选题 1．顺序表中逻辑上相邻的结点其物理位置也( )。 A．一定相邻B．不必相邻C．按某种规律排列D．无要求 2．下面关于串的叙述中，哪一个是不正确的? ( ) A．串是字符的有限序列C．模式匹配是串的一种重要运算 B．空串是由空格构成的串D．串既可以采用顺序存储，也可以采用链式存储3.某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列

为( )。 A．ABCED B．DECAB C．DEABC D．BDACE 4. 设二维数组A[m][n] 按列优先顺序存储且每个元素占c个单元，则元素A[i][j] 的地址为()。 A．LOC(A[0][0])+(j*m+i)*c B．LOC(A[0][0])+(i*n+j)*c C．LOC(A[0][0])+[(j-1)*m+i-1]*c D．LOC(A[0][0])+[(i-1)*n+j-1]*c 5.在下述几种排序方法中，不稳定的排序方法是()。 A．直接插入排序B．冒泡排序 C．直接选择排序D．归并排序 6.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值()。 A．同等概率B．最大概率C．最小概率D．平均概率 7．在有n个结点的顺序表中进行插入、删除运算，平均时间复杂度为( )。 A．Ο(1)B．Ο(n)C．Ο(log2n)D．Ο(n2 ) 8．设s1="abc"，则strlen(s1) = ( )。 A．0 B． 1 C．2 D．3 9. 完全二叉树是下列情况的哪一种( )。 A．一定是满二叉树B．可能是满二叉树 C．一定不是满二叉树D．不是二叉树 10. 下列说法不正确的是( )。 A．图的遍历是从给定的源点出发每个顶点仅被访问一次 B．遍历的基本方法有两种：深度优先遍历和广度优先遍历 C．图的深度遍历不适用于有向图 D．图的深度优先遍历是一个递归过程 11. 数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是( )。 A．1165 B．1170 C．1175 D．1180 12. 在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是( )。A．直接插入排序B．快速排序 C．直接选择排序D．归并排序

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。

数据结构习题与答案

第 1 章绪论课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

数据结构考试试题

数据结构辅导试题一一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值，若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散

十套数据结构试题与答案

数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 9 12 15 17 19 21 24 数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设个空间，问 676(10)，每个元素占制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ）。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素乙间无联系的数据元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。正确性易读性

数据结构考试题库含答案

数据结构习题集含答案目录

选择题第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ）存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;