数据结构试卷答案

数据结构试卷带答案数据结构试卷（一）一、选择题（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-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B 需要的操作为（.A ）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈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) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（B）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（B ）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

得分一、单项选择题（10 小题，每小题 2 分，共 20 分）1．设栈 S 和队列 Q 的初始状态为空，元素 e1,e2,e3,e4,e5,e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2,e4,e3,e6,e5,e1，则栈 S 的容量至少应该是（）。

BA．2B．3C．4D．62．由 4 个叶子结点构造一棵哈夫曼树，该树的总结点数是（A．4 B．5 C．6D）。

D．73．对于长度为m（m>1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是）。

（DA．若入栈和入队列的序列相同，则出栈序列和出队序列可能相同B．若入栈和入队列的序列相同，则出栈序列和出队序列可以互为逆序C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1: n (n≥1)D．入队序列与出队序列关系为1: n (n≥1)，而入栈序列与出栈序列关系是1:14．在一个单链表 HL 中，若要删除由指针 q 所指结点的后继结点，则执行（A）。

A．p=q->next; q->next=p->next; C．p=q->next; p->next=q->next;B．p=q->next; q->next=p;D．q->next= q->next->next; q->next=q;5．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女之间不能相互继承。

则表示该遗产继承关系的数据结构应该是（）。

A．树B．图C．线性表D．集合B6．设数组 S[n]作为两个栈 S1 和 S2 的存储空间，对任何一个栈只有当 S[n]全满时才不能进行进栈操作。

为这两个栈分配空间的最佳方案是（A．S1 的栈底位置为 0，S2 的栈底位置为n-1B．S1 的栈底位置为 0，S2 的栈底位置为n/2C．S1 的栈底位置为 0，S2 的栈底位置为nD．S1 的栈底位置为 0，S2 的栈底位置为 1A）。

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）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. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

专升本数据结构试卷答案一、选择题（每题 2 分，共 30 分）1、在数据结构中，从逻辑上可以把数据结构分为（）。

A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构答案：C解析：数据结构从逻辑上分为线性结构和非线性结构。

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

2、以下数据结构中，（）是非线性数据结构。

A 栈B 队列C 线性表D 二叉树答案：D解析：二叉树是一种非线性数据结构，每个节点最多有两个子节点。

栈、队列和线性表都属于线性数据结构。

3、一个顺序存储的线性表的第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（）。

A 108B 110C 106D 104答案：A解析：第一个元素地址为 100，每个元素长度为 2，所以第 5 个元素的地址为 100 ＋ 2×（5 1) ＝ 108。

4、在单链表中，增加头结点的目的是（）。

A 方便运算的实现B 使单链表至少有一个结点C 标识表结点中首结点的位置D 说明单链表是线性表的链式存储实现答案：A解析：头结点的作用是方便运算的实现，比如在插入和删除操作时，可以避免对第一个元素的特殊处理。

5、设栈的顺序存储空间为 S(1:m)，初始状态为 top ＝ 0。

现经过一系列入栈与退栈运算后，top ＝ 20，则当前栈中有（）个元素。

A 20B 21C m 20D m 19答案：A解析：栈是一种先进后出的数据结构，top 指向栈顶元素的位置，top ＝ 20 说明当前栈中有 20 个元素。

6、循环队列的存储空间为 Q(1:50)，初始状态为 front ＝ rear ＝ 25。

经过一系列入队与退队运算后，front ＝ 15，rear ＝ 10，则循环队列中的元素个数为（）。

A 5B 6C 16D 49答案：B解析：循环队列中元素个数的计算公式为：（rear front ＋ 50) ％ 50。

《数据结构》试卷一一、填空题：（共２０分）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,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。

5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。

7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。

11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。

12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。

数据结构试题及答案数据结构试卷（⼗⼀）⼀、选择题(30分)1．设某⽆向图有n个顶点，则该⽆向图的邻接表中有（）个表头结点。

(A) 2n (B) n (C) n/2 (D) n(n-1)2．设⽆向图G中有n个顶点，则该⽆向图的最⼩⽣成树上有（）条边。

(A) n (B) n-1 (C) 2n (D) 2n-13．设⼀组初始记录关键字序列为(60，80，55，40，42，85)，则以第⼀个关键字45为基准⽽得到的⼀趟快速排序结果是（）。

(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804．（）⼆叉排序树可以得到⼀个从⼩到⼤的有序序列。

(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5．设按照从上到下、从左到右的顺序从1开始对完全⼆叉树进⾏顺序编号，则编号为i结点的左孩⼦结点的编号为（）。

(A) 2i+1 (B) 2i (C) i/2 (D) 2i-16．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。

(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。

(A) head==0 (B) head->next==0(C) head->next==head (D) head!=08．设某棵⼆叉树的⾼度为10，则该⼆叉树上叶⼦结点最多有（）。

(A) 20 (B) 256 (C) 512 (D) 10249．设⼀组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利⽤⼆分法查找关键字90需要⽐较的关键字个数为（）。

(A) 1 (B) 2 (C) 3 (D) 410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。

《数据结构》试题参考答案 （开卷）（电信系本科2001级 2002年12月）一、回答下列问题 (每题4分，共36分)1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=⎡n/2⎤=⎡15381/2⎤=7691(个)2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。

答：根据0 当j ＝1时next[ j ]＝ max { k |1<k<j 且‘T 1…T k-1’=‘T j-(k-1) …T j-1’ }1 对应模式串的next[ j ] 演示程序亦验证了结果： next[j]=03 4. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH 和DBGEACHF ，则该二叉树的后序序列是什么？答：法1：先画树而得后序序列；A(DBGE) (CHF)B C 结论：D G E B H F C AD (GE) (HF)E F G H法2：直接推出后序序列step1: (DBGE) (CHF) A step2: D(GE)B (HF) C A step3: DGE B HF C A5. 请证明：用二叉链表法（Lchild-Rchild ）存储包含n 个结点的二叉树，必有n+1个指针域为空。

答：因为：用二叉链表存储包含n 个结点的二叉树，结点共有2n 个链域；又因为：二叉树中除根结点外，每一个结点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目＝全部指针数2n －所有非空指针数(n-1)=所有空指针数＝n ＋1，证毕。

《数据结构》试卷及答案1．算法分析的目的是( C )。

A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2．（ B ）是具有相同特性数据元素的集合，是数据的子集。

A.数据符号B.数据对象C.数据D.数据结构3．用链表表示线性表的优点是( C )。

A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4．输入序列为（A,B,C,D）不可能的输出有（D ）。

A.(A,B,C,D)B. (D,C,B,A)C. (A,C,D,B) D . (C,A,B,D)5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。

A. front=maxSizeB. (rear+1)%maxSize=frontC. rear=maxSizeD. rear=front6．设有串t='I am a good student '，那么Substr(t,6,6)=（ D ）。

A. studentB. a good sC. goodD. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（ B ）。

A.23B.33C.18D. 408．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子B的运算（C ）。

A. Gethead(Gethead(LS))B. Gettail(Gethead(LS))C. Gethead(Gethead(Gettail(LS)))D. Gethead(Gettail(LS))9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( A ) 。

A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE10．下列存储形式中，(C ) 不是树的存储形式。

专升本《数据结构》一、（共75题,共150分）1. 数据的基本单位是（）。

（2分）A.数据元素B.记录C.数据对象D.数据项.标准答案：A2. （）是数据的不可分割的最小单位。

（2分）A.数据对象B.数据元素C.数据类型D.数据项.标准答案：D3. 算法的空间复杂度是对算法（）的度量。

（2分）A.时间效率B.空间效率C.可读性D.健壮性.标准答案：B4. （）是限制了数据元素的内部结构仅为一个字符的线性表。

（2分）A.栈B.队列C.串D.数组.标准答案：B5. 串的长度是指串中所含（）的个数。

（2分）A.不同字符B.不同字母C.相同字符D.所有字符.标准答案：D6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。

（2分）A.1B.2C.3D.4.标准答案：B7. 线性表的顺序存储结构是一种（）的存储结构。

（2分）A.顺序存取B.随机存取C.索引存取D.Hash存取.标准答案：B8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。

（2分）A.64B.32C.16D.8.标准答案：A9. 深度为h的二叉树，第h层最多有（）个结点。

（2分）A.hB.2h-1C.2h-1D.2h.标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。

（2分）A.mB.m+1C.2mD.m-1.标准答案：B11. 下面叙述错误的是（）。

（2分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的.标准答案：C12. 以下与数据的存储结构无关的术语是（）。

（2分）A.循环队列B.双向链表C.哈希表D.数组.标准答案：D13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。