数据结构历年试卷06

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。

【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。

平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。

平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。

堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。

哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。

2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。

3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。

【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。

【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。

【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。

数据结构基础历年试题汇编一、2006年上半年●在以下情形中，___(35)___适合于采用队列数据结构。

(35)A．监视一个火车票售票窗口等待服务的客户D．描述一个组织中的管理机构C．统计一个商场中的顾客数D．监视进入*住宅楼的访客●元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为___(36)___。

(36)A．3、2、1 B．3、1、2 C．1、2、3 D．2、1、3●一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若*结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的大小至少为___(37)___；若采用二叉链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)，则该链表中空指针的数目为___(38)___。

(37)A．6 B．10 C．12 D．15(38)A．6 B．7 C．12 D．14●以下各图用树结构描述了7个元素之间的逻辑关系，其中___(39)___适合采用二分法查找元素。

●对于二维数组a[0…4,1…5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,1]相对于数组空间起始地址的偏移量是___(40)___。

(40)A．5 B．10 C．15 D．25●若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是___(59)___。

(59)A．O(n2)B．O(n)C． O(log n)D．O(nlog n)二、2006年下半年●在链表结构中，采用（35）可以用最少的空间代价和最高的时间效率实现队列结构。

（35）A.仅设置尾指针的单向循环链表 B.仅设置头指针的单向循环链表C.仅设置尾指针的双向链表D.仅设置头指针的双向链表●若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是（36）。

（36）A.将栈 S 中元素依次出栈并入栈 T，然后栈 T 中元素依次出栈并进入栈 SB.将栈 S 中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 SC.直接交换栈顶元素和栈底元素D.直接交换栈顶指针和栈底指针●已知 N 个数已存入数组 A[1..M]的前 N 个元素中（N<M），为在 A[i]（1≤i≤N）之前插入一个新数，应先（37），以挪出一个空闲位置插入该数。

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

06数据结构（50分）一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。

每小题1分，共10分）1.数据的基本单位是（）A.数据项B.数据类型C.数据对象D.数据元素2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。

（）A.顺序B.链式C.散列D.任意3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（）A.7，5，3，9B.9，7，5，3C.7，5，9，3D.9，5，7，34.下面的说法中，正确的是（）A.字符串的长度指串中包含的字母的个数B.字符串的长度指串中包含的不同字符的个数C.一个字符串不能说是其自身的一个子串D.若T包含在S中，则T一定是S的一个子串5.广义表（（a，b），（c，d））的表尾是（）A.dB.c，dC.（c，d）D.（（c，d））6.n个顶点的连通图，其生成树有_______条边。

（）A.n-1B.nC.n+1D.不确定7.若一棵二叉树有8个度为2的结点，则该二叉树的叶节点个数为（）A.7B.8C.9D.不确定8.在有n个节点的二叉链表中有_______个空链域。

（）A.n+1B.nC.n-1D.不确定9.在等概率的情况下，采用顺序插查找法查找长度为n的线性表，平均查找长度为（）A.nB.n/2C.(n+1)/2D.(n-1)/210.下列排序方法中，排序的比较次数与序列的初始排列状态无关的是（）A.选择排序B.插入排序C.冒泡排序D.快速排序二、填空题（本大题共10小题，每小题1分，共10分）1.假定一个顺序队列的队首和队尾分别为f和r，则判断队空的条件为__________________。

2.在顺序存储的线性表中插入或删除一个元素平均约移动表中__________________的元素。

3.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占2个字节，则A[3][2]的存储地址是______________。

数据结构与算法练习试卷6(题后含答案及解析) 题型有：1. 选择题选择题（每小题1分，共60分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。

1．一棵具有5层的完全二叉树中，结点总数最少是( )。

A．15B．5C．16D．31正确答案：C解析：具有5层的树结点最少的是完全二叉树，第5层只有一个结点，其他4层是由满二叉树构成。

知识模块：数据结构与算法2．设n、m为一棵二叉树上的两个结点，在中序遍历时，若n在m的前面，则( )。

A．n为树的左子树上的结点，m为右子树上的结点B．n是m的祖先结点C．n的层次比m层次高D．n在m的左方正确答案：D 涉及知识点：数据结构与算法3．对于深度为n，结点数为k，有m个叶子结点的满二叉树，下列关系正确的是( )。

A．k=m+nB．k=-2”-1C．n+m=2kD．re=k-1正确答案：B 涉及知识点：数据结构与算法4．快速排序方法在( )条件下最不利于发挥其长处。

A．待排序序列中含有多个相同关键字B．待排序序列数据基本有序C．待排序序列数据量很大D．待排序序列元素个数为奇数正确答案：C 涉及知识点：数据结构与算法5．在每一趟排序时，都将待排序序列中最大关键字选出来，并将此关键字从待排序序列中删除，继续对剩余元素进行同样操作的排序方法称之为( )。

A．快速排序B．堆排序C．起泡捧序D．选择排序正确答案：C 涉及知识点：数据结构与算法6．设有1000个无序的元素，希望用最快的方式挑选出其中前10个最大元素，效率最高的排序方法是( )。

A．堆排序B．快速排序C．基数排序D．起泡排序正确答案：A 涉及知识点：数据结构与算法7．设哈希表长m=14，哈希函数H(key)=key%ll，表中已经有4个结点：addr(13)=4；addr(28)=5 addr(51)=6；addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为49的结点地址为( )。

数据结构历年真题及解析题一、选择题1. 下列关于数组的描述，正确的是（）。

A. 数组在内存中是连续存放的。

B. 数组一经定义，其长度不可改变。

C. 数组的每个元素可以是不同的数据类型。

D. 数组可以通过下标随机访问元素。

答案：A、B、D2. 链表相比于数组的优势在于（）。

A. 内存使用更高效。

B. 插入和删除操作更加方便。

C. 可以通过下标随机访问元素。

D. 存储空间可以动态分配。

答案：B、D3. 栈（Stack）的特点是（）。

A. 先进先出（FIFO）。

B. 后进先出（LIFO）。

C. 只能在一端进行插入和删除。

D. 可以通过索引随机访问元素。

答案：B、C4. 队列（Queue）与栈的主要区别在于数据的（）。

A. 存取方式。

B. 存储结构。

C. 操作速度。

D. 内存占用。

答案：A5. 二叉树的前序遍历的顺序是（）。

A. 根-左-右。

B. 左-根-右。

C. 右-根-左。

D. 根-右-左。

答案：A6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 通过增加哈希表的大小来解决冲突。

B. 通过链表来链接具有相同哈希值的元素。

C. 寻找表中下一个空闲位置来存储冲突元素。

D. 重新计算哈希值，直到找到空闲位置。

答案：C8. 图的遍历算法中，深度优先搜索（DFS）与广度优先搜索（BFS）的主要区别在于（）。

A. DFS使用递归，BFS使用队列。

B. DFS使用栈，BFS使用递归。

C. DFS使用队列，BFS使用栈。

D. DFS和BFS都使用链表。

答案：A9. 堆（Heap）结构中，最大堆的性质是（）。

A. 父节点的值小于子节点。

B. 父节点的值大于子节点。

C. 父节点的值等于子节点。

D. 没有固定的大小关系。

答案：B10. 动态规划算法通常用于解决（）类型的问题。

A. 排序。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

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，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.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）的联系时，称这种结构为_____________________。

数据结构期末复习题及答案6数据结构期末考试试题及答案期末样卷参考答案⼀．是⾮题（每题1分共10分）1. 线性表的链式存储结构优于顺序存储结构。

F2. 栈和队列也是线性表。

如果需要，可对它们中的任⼀元素进⾏操作。

F3．字符串是数据对象特定的线性表。

T4．在单链表P指针所指结点之后插⼊S结点的操作是：P->next= S ; S-> next = P->next; F5．⼀个⽆向图的连通分量是其极⼤的连通⼦图。

T 6．邻接表可以表⽰有向图，也可以表⽰⽆向图。

T 7．假设B是⼀棵树，B′是对应的⼆叉树。

则B的后根遍历相当于B′的中序遍历。

T8．通常，⼆叉树的第i层上有2i-1个结点。

F9．对于⼀棵m阶的B-树,树中每个结点⾄多有m 个关键字。

除根之外的所有⾮终端结点⾄少有ém/2ù个关键字。

F10．对于任何待排序序列来说，快速排序均快于起泡排序。

F⼆．选择题（每题2分共28分）1．在下列排序⽅法中，（c ）⽅法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d ）⽅法所有情况下时间复杂度均为0(nlogn)。

a. 插⼊排序b. 希尔排序c. 快速排序d. 堆排序2. 在有n个结点的⼆叉树的⼆叉链表表⽰中，空指针数为（ b ）。

a.不定b.n+1c.nd.n-13. 下列⼆叉树中，（a ）可⽤于实现符号不等长⾼效编码。

a.最优⼆叉树b.次优查找树c.⼆叉平衡树d.⼆叉排序树4. 下列查找⽅法中，（a ）适⽤于查找有序单链表。

a.顺序查找b.⼆分查找c.分块查找d.哈希查找5. 在顺序表查找中，为避免查找过程中每⼀步都检测整个表是否查找完毕，可采⽤（ a ）⽅法。

a.设置监视哨b.链表存贮c.⼆分查找d.快速查找6. 在下列数据结构中，（c ）具有先进先出特性，（b ）具有先进后出特性。

a．线性表b．栈c．队列d．⼴义表7．具有m个结点的⼆叉排序树，其最⼤深度为（f ），最⼩深度为（ b ）。

20 06—20 07学年第2 学期《数据结构与算法》考试试卷（A卷）（时间120分钟）院/系专业姓名学号一、选择题（每小题2分，共20分）1、数据结构中，与所使用的计算机无关的是数据的结构。

A. 存储结构B. 物理结构C. 逻辑结构D. 物理和存储结构2、循环链表的主要优点是。

A. 不再需要头指针了B. 已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D. 从表中任一结点出发都能遍历整个链表3、栈和队列都是。

A. 顺序存储的线性结构B.链式存储的非线性结构C. 限制存取点的线性结构D.限制存取点的非线性结构4、串的长度是指。

A. 串中所含不同字母的个数B. 串中所含不同字符的个数C. 串中所含字符的个数D. 串中所含非空格字符的个数5、若某二叉树的先序和中序遍历序列分别为ABCD、ACDB，则该二叉树的后序遍历序列为。

A. DBCAB. ADCBC. DCBAD. CDBA6、有n个叶子结点的哈夫曼树，其结点总数为。

A．2n-1 B．2n C．2n+1 D．不确定。

7、无向图的邻接矩阵一定是。

A. 对角矩阵B. 稀疏矩阵C. 三角矩阵D. 对称矩阵8、以下序列中符合堆的定义。

A. (2,40,20,25,30)B. (2,20,40,25,30)C. (40,25,2,30,20)D. (40,25,2,20,30)9、下列排序方法中属于不稳定排序方法的是。

A.直接插入排序B.冒泡排序C.快速排序D.归并排序10、设有一个用线性探测法解决冲突得到的散列表(或哈希表)如下图所示，散列函数为H(k)=k % 11，若要查找元素14，探查的次数为。

(第一题，第10小题图)A.5B.9C.3D.6二、填空题（每小题2分，共20分）1、一个“好”的算法要考虑以下标准：正确性 、可读性 、 和高效率与低存储量需求。

2、对于二维数组a[0..4,0..5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,3]相对于数组空间起始地址的偏移量是 。

数据结构试题(含答案)数据结构试题(含答案)一、选择题1. 数据结构是计算机科学中的一个重要概念。

下列选项中，不属于数据结构的是：A. 数组B. 栈C. 数据库D. 链表答案：C2. 在数据结构中，栈(Stack)是一种后进先出(LIFO)的数据结构。

下列操作中，不属于栈的是：A. 入栈B. 出栈C. 遍历D. 清空栈答案：C3. 链表(Linked List)是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。

下列选项中，不属于链表的是：A. 单链表B. 双链表C. 循环链表D. 二叉树答案：D4. 哈希表(Hash Table)是一种根据关键码直接访问存储位置的数据结构。

下列选项中，不属于哈希表的优点是：A. 快速查找B. 插入和删除操作效率高C. 数据无序D. 冲突较少答案：C二、填空题1. 树(Tree)是一种非线性数据结构，它由一组以边连接的节点组成。

树中每个节点最多可以有________个子节点。

答案：无限制/任意个2. 图(Graph)是由节点和连接节点的边组成的数据结构。

图中节点的度是指与该节点相连接的边的________。

答案：数量3. 广度优先搜索(BFS)和深度优先搜索(DFS)是常用的图遍历算法。

在BFS中，使用________结构来保存待访问的节点。

答案：队列4. 在二叉搜索树(Binary Search Tree)中，左子树中的每个节点的值都小于根节点的值，右子树中的每个节点的值都大于根节点的值。

这种特性称为_______________。

答案：二叉搜索树性质三、简答题1. 请简要说明线性数据结构和非线性数据结构的区别。

答案：线性数据结构是指数据元素之间存在一对一的线性关系，例如数组、栈、队列等；而非线性数据结构是指数据元素之间存在一对多或多对多的关系，例如树、图等。

线性数据结构的存储方式是连续的，非线性数据结构的存储方式是离散的。