数据结构(A卷)

东南大学成贤学院考试卷（A卷）

课程名称数据结构适用专业计算机科学与技术

考试学期10-11-3考试形式开卷□闭卷□考试时间长度120分钟学号姓名得分

一、选择题（每题1分，18 题共18 分）

1. 数据结构中，与所使用的计算机无关的是数据的（）结构。

（A) 存储（B) 物理（C) 逻辑（D) 物理和存储

2．线性表（a1,a2,…,an）以链接方式存储时，访问第i位元素的时间复杂度为

（）。

（A）O（i）（B）O（1）（C） O（N）（D） O（i-1）

3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。

（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）；

（B）在第i个结点后插入一个新结点（1≤i≤n）；

（C）删除第i个结点（1≤i≤n）；

（D）将n个结点从小到大排序；

4．输入序列为ABC，可以变为CBA时，经过的栈操作为（）。

（A）push,pop,push,pop,push,pop

(B) push,push,push,pop,pop,pop

(C) push,push,pop,pop,push,pop

(D) push,pop,push,push,pop,pop

5．已知广义表ls=((a,b,c),(d,e,f)),运用head和tail函数取出ls中原子e的运算是（）。

（A）head(tail(ls)) （B）tail(head(ls))

（C）head(tail(head(tail(ls))) （D）head(tail(tail(head(ls))))

6．设二叉树根结点为O层，深度（高度）为K的满二叉树和同样深度的完全二

叉树各有n个结点和m个结点，下面关系不正确的是（）。

（A）n>=m （B）m>n （C）n=2k+1-1 （D）m>2k-1 7．设树中有一结点x，在先根遍历序列中的序号为P(x)，后根遍历序列中的序号

为S(x)。若树中结点x是结点y的祖先，则有（）。

（A）p(x)>p(y)和s(x)p(y)和s(x)>s(y)

（C）p(x)s(y) （D）p(x)

8．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序遍历序列就是

T2中结点的（）。

（A）中序遍历序列（B）前序遍历序列

（C）后序遍历序列（D）层次序遍历序列

9．具有5层结点的A VL树至少有（）个结点。

（A）10 （B）12 （C）15 （D）17

10．在下图所示中，从顶点1出发按照DFS规则遍历得到的序列为（）。

（A）1354267 （B）1247653 （C）1534276（D）1472653 11．设某有向图中有n各顶点，e条边,进行拓扑排序时总的计算时间为（）。

（A）O(nlbe) （B）O(e*n) （C）O(elbn) （D）O(e+n) 12．设无向图G中顶点数为n，则图G最多有（）条边。

（A ）n （B）n-1 （C）n(n-1)/2（D）n(n-1) 13．只有12个关键字的有序表，二分查找的平均查找长度（）。

（A）3.1 （B）4 （C）2.5 （D）5

14．就平均性能而言，目前最好的内排序方法是（）排序法。

（A）冒泡（B）希尔插入（C）交换（D）快速

15．以下序列不是堆的是（）。

（A）(100,85,98,77,80,60,82,40,20,10,66)

（B）(100,98,85,82,80,77,66,60,40,20,10,)

（C）(10,20,40,60,66,77,80,82,85,98,100)

（D）(100,85,40,77,80,60,66,98,82,10,20)

16．在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是（）。

（A）直接插入排序（B）冒泡排序

（C）简单选择排序（D）归并排序

17．在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是（）。

（A）堆排序（B）冒泡排序（C）插入排序（D）快速排序18．一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（）。

（A）16,25,35,48,23,40,79,82,36,72 （B）16,25,35,48,79,82,23,36,40,72

（C）16,25,48,35,79,82,23,36,40,72 （D）16,25,35,48,79,23,36,40,72,82

二、填空题（每空2分，共11 空，共22 分）

1．一个算法的效率可分为___时间_____效率和空间效率。

2．带头结点的循环链表L中以某个结点p为尾结点的条件______L—>next==Head_________________。

3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存储线性表中的元素时，应采用___顺序_____存储结构。

4．设栈Ｓ和队列Ｑ初始均为空，若６个元素入栈的顺序为a1,a2,a3,a4,a5,a6。一个元素出栈之后立即入队列Ｑ，若６个元素出队的顺序为a2,a4,a3,a6,a5,a1,则栈的容量至少为______3__。

5．广义表L=（（），（））的长度为______2_____。

6．设森林Ｆ由n棵树组成，其中第一棵树有t１个结点、．．．第n棵树有tn个结点，则与Ｆ对应的二叉树中，根结点的右子树共有__ t2+…+tm ___个结点。7．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有___2 n0-1_____个结点。8．设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。

任意一棵G的生成树共有____7_条边。

9．在图G的邻接表表示中，每个结点邻接表中所含的结点数，对于无向图来说等于该结点的_________度____。

10．对{13，17，2，5，11，23，15，9，12}执行一遍快速排序的结果_____________________12 ，9 ，2 ，5,11,13,15,23,17___________________。11．用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为_______O(n2)_。

三、判断题（每题1分，共10题，共10分）

1．程序一定是算法。（）

2．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）

3．栈和队列的存储方式既可是顺序方式，也可是链接方式。（）

4．n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（）5．假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC。（）

6．一个正常的AOE网一定只有一条关键路径。（）

7．用邻接矩阵存储一个图所需要的存储单元数目与图的边数有关。（）

8．堆排序是稳定的排序。（）

9．在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。（）10．对一个堆，按二叉树层次进行遍历，可以得到一个有序序列。（）

四、综合题（共34分）

1. （8分）已知一棵二叉树的先序、中序和后序序列如下，其中空缺了部分（空格代表一个字符），请把空缺部分填上，并画出该二叉树。(8分)

先序序列：__BC__EFG__IJK__

中序序列：CBED__GAJ__H__L

后序序列：__E__FD__J__L__HA

2. （6分）已知某文本中共出现8种不同的ASCII字符,各个字符出现的频率分别为8, 5, 3, 2, 7, 23, 9, 3, 现在对这段文本进行哈夫曼编码。

(1) 画出该哈夫曼树。

(2) 编码后该文本的总长度为多少位?

3. （6分）某无向网的顶点集合为V={V1,V2,……,V8}，其邻接矩阵如下。要求：

画出该图（提示，以逆时针方向布图）

画出一棵最小生成树

∞ 3 ∞ 1 6 8 ∞∞

3 ∞

4 ∞ 3 ∞∞∞

∞ 4 ∞ 2 5 ∞9 7

1 ∞

2 ∞∞∞

3 1

6 3 5 ∞∞ 2 2 ∞

8 ∞∞∞ 2 ∞8 ∞

∞∞9 3 2 8 ∞ 4

∞∞7 1 ∞∞ 4 ∞

4. （8分）已知一组数据元素的关键字序列为｛18,2,10,6,78,56,45,50,110,8｝，按此顺序输入该组数据元素，试画出该组数据元素的平衡二叉树。

5. （6分）假设一组数据元素的关键字序列为：

32，75，30，63，46，25，57，94，18，20

用哈希（散列）表HT[12] 存储这组数据元素，哈希函数采用除留余数法

Hash( k )= k%11

并用线性探测法处理冲突。试求出

(1) 每一元素的哈希地址，画出最后得到的哈希表；

(2) 求出等概率下查找成功的平均查找长度。

五、算法题（共16分）

1. 以下是希尔排序算法的一种实现，请填空完善之。（6分）

void ShellSort( Type a[ ], int n )

{ int step, i, j, pos; //step为希尔增量，pos为插入位置

for( step=(n+1)/2; step>0; step=(step+1)/2)

for( __________; i

for( j=i-step; j>=0 && a[ j ]>temp; j-=step)

{ a[ j+step ] = a[ j ];

___________;

}

___________;

}

}

2. 完善设计二叉排序树的元素删除算法Delete（10 分）

在二叉排序树中，如果被删除的结点有两个孩子，这是最复杂的情况。删除这个结点会使其他某些结点从树上脱离。通常的做法是选取一个“替身”取代被删结点，可充当替身结点的是被删结点的左子树中最大（最右）的结点或被删结点的右子树中最小（最左）的结点。

(1)二叉排序树的结点定义如下：

template

struct BiSortNode{

Type data;

BiSortNode *leftChild, *rightChild;

};

(2)Delete的public定义

void Delete(Type x)

{

Delete(root, x); //root是二叉排序树的根结点指针

}

(3) Delete的private定义

void Delete( BiSortNode *&r, Type x)

{

BiSortNode *temp;

if(r==NULL) return; //未找到指定结点，删除失败

if(xdata) Delete(r->leftChild, x); //左子树递归

else if( x>r->data) Delete(r->rightChild, x);//右子树递归else //找到要删除的结点

请完成此后的内容：

}

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

数据结构模拟题(开卷)

《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

数据结构试卷带答案

数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

专升本《数据结构》模拟题试卷汇编

专升本《数据结构》模拟题试卷 一. （共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 ★检查答案标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 ★检查答案标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 ★检查答案标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 ★检查答案标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 ★检查答案标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2

分） A.1 B.2 C.3 D.4 ★检查答案标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 ★检查答案标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 ★检查答案标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h ★检查答案标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 ★检查答案标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象

数据结构模拟试题3

数据结构模拟试题（4） 一、填空题:06分，每题02分 1、模板类是一种数据抽象，它把________当作参数，可以实现类的复用。 2、假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。 3、第i(i=1,2,...,n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__________排序。 二、单选题:10分，每题02分 4、 设循环队列的结构是 const int MaxSize=100; typedef int DataT ype; struct Queue { DataT ype data[MaxSize]; int front, rear; }; 若有一个Queue类型的队列Q，试问判断队列满的条件应为( )。 A: Q.front==Q.rear; B: Q.front-Q.rear==MaxSize; C: Q.front+Q.rear==MaxSize; D: Q.front==(Q.rear+1) % MaxSize; 5、已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为( )。假定树根结点的高度为0。 A: 3 B: 4 C: 5 D: 6 6、对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。 A: log2(n+1) B: log2n C: n/2 D: (n+1)/2 7、设无向图的顶点个数为n，则该图最多有（）条边。 A: n-1 B: n(n-1)/2

数据结构试卷带答案

数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟

数据结构模拟题及复习资料

数据结构试题（A05） 一、选择题（共10小题，每小题1分，共10分） 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1； A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.（n-1）/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.（100，85，98，77，80，60，82，40，20，10，66） B.（100，98，85，82，80，77，66，60，40，20，10） C.（100，85，40，77，80，60，66，98，82，10，20） D.（10，20，40，60，66，77，80，82，85，98，100） 8．在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题（共20小题，每小题1分，共20分） 1、在单链表中，删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8，1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所

数据结构模拟试题9

一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。

数据结构试题及答案

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

数据结构试题(含答案)

一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构模拟试题1

一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1

C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

数据结构模拟考试试卷

数据结构模拟考试试卷(1卷) 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （ㄨ）（2）线性表的链式存储结构优于顺序存储。 （√）（3）将中缀表达式转换成后缀表达式是栈的重要应用。 （×）（4）栈和队列都是顺序存储的线性结构。 （×）（5）“DT”是“DA TA”的子串。 （×）（6）在二叉树中，具有一个子女的父结点，在中序遍历的序列中，它没有后继子女结点。 （×）（7）带权图的最小生成树是唯一的。 （√）（8）散列存储法的基本思想是由关键字的值决定数据的存储地址。 （√）（9）希尔排序是不稳定的排序。 （√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。 二．填空题 1．线性结构中元素之间存在一对一关系。 2．树形结构和图形结构合称为：非线性结构。 3．顺序表中逻辑上相邻的元素在物理位置上必须相连。 4．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O (n) 。 5．同一栈的各元素的类型相同。 6．已知表达式，求它的后缀表达式是栈的典型应用之一。 7．队列在进行出队操作时，首先要判断队列是否为空。 8．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==(rear+1)% MAXLEN 。 9．串的链式存储结构简称为链式串。 10．求子串函数SubStr("Today is 30 July,2005",13,4)的结果是： July 。 11．给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH 。 12．将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为：2*i+1 。 13．图的遍历有：深度优先搜和 _广度优先搜 __等方法。

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

数据结构模拟卷(含答案)经典习题培训讲学

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )

数据结构模拟试题一及答案汇编

学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后

数据结构试题(含答案)

数据结构试题（含答案） 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 。

数据结构与算法 模拟试卷三四及参考答案

模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 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.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的