下载文档原格式
数据结构期末试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构和链式存储结构的主要区别在于：A. 数据元素的存储关系B. 数据元素的存储空间C. 数据元素的存储顺序D. 数据元素的存储位置答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈只能进行插入和删除操作C. 栈顶元素可以被访问D. 栈可以进行顺序存储和链式存储答案：B3. 在二叉树的遍历算法中，不使用递归算法的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：D4. 哈希表的冲突解决方法中，不包括以下哪种：A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D5. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于：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. 在非递归的二叉树遍历算法中，通常需要使用的数据结构是：A. 栈B. 队列C. 链表D. 数组答案：A9. 一个有n个顶点的无向图，其边数最多为：A. nB. n(n-1)/2C. n(n+1)/2D. n^2答案：B10. 一个长度为n的数组进行归并排序时，需要的辅助空间大小为：A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B二、填空题（每题2分，共10分）1. 在数据结构中，______是一种特殊的线性表，它的元素个数是固定的。
答案：数组2. 链表中，每个节点包含数据域和______。
贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。
数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
数据结构期末试题及答案一、选择题（每题2分，共20分）1. 下列哪一项不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个直接前驱和一个直接后继C. 有多个根节点D. 有且只有一个叶子节点2. 在顺序存储结构中，数据元素之间的逻辑关系由（）表示。
A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置3. 在链式存储结构中，数据元素之间的逻辑关系由（）表示。
A. 指针B. 节点C. 节点的物理位置D. 节点的存储位置4. 下列哪种排序算法的平均时间复杂度是O(nlogn)？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序5. 下列哪种数据结构属于非线性结构？A. 栈B. 队列C. 线性表D. 树二、填空题（每题2分，共20分）6. 一个栈的初始状态为空。
首先将元素1、2、3、4、5依次进栈，然后退栈一次，再让元素6、7依次进栈，此时栈顶元素的值为______。
7. 一个队列的初始状态为空。
首先将元素a、b、c、d、e依次入队，然后出队两次，再让元素f、g依次入队，此时队列的头部元素为______。
8. 在二分查找法中，每次查找都将查找区间分为______两部分。
9. 在顺序存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。
10. 在链式存储结构中，若数据元素个数为n，则最后一个元素的存储位置是______。
三、计算题（每题10分，共30分）11. 给定一个长度为8的数组A[8] = {5, 2, 9, 1, 5, 6, 3, 7}，请写出冒泡排序算法的实现过程，并计算排序后的数组。
12. 请手写一个递归函数，实现计算斐波那契数列的第n 项（n为非负整数）。
13. 请手写一个非递归函数，实现计算斐波那契数列的第n项（n为非负整数）。
数据结构期末试题答案一、选择题答案1. C2. C3. A4. B5. D二、填空题答案6. 77. b8. 相等9. n10. n-1三、计算题答案11. 冒泡排序算法实现过程：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j] A = [5, 2, 9, 1, 5, 6, 3, 7]bubble_sort(A)print(A) 输出排序后的数组```排序后的数组：[1, 2, 3, 5, 5, 6, 7, 9]12. 递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_recursive(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)n = 10 计算斐波那契数列的第10项print(fibonacci_recursive(n)) 输出结果```13. 非递归函数实现计算斐波那契数列的第n项：```pythondef fibonacci_iterative(n):a, b = 0, 1for _ in range(n):a, b = b, a + breturn an = 10 计算斐波那契数列的第10项print(fibonacci_iterative(n)) 输出结果```以上为数据结构期末试题及答案，希望对您有所帮助。
数据结构期末考试试题及答案一、选择题1、评价一个算法时间性能得主要标准就是( ).Ａ、算法易于调试B、算法易于理解C、算法得稳定性与正确性D、算法得时间复杂度2、计算机算法具备有输入、输出、( ）等五个特性。
A、可行性、可移植性与可扩充性Ｂ、可行性、确定性与有穷性C、确定性、有穷性与稳定性D、易读性、稳定性与安全性3、带头结点得单链表head为空得判定条件就是（）.A、ｈeaｄ=＝NＵＬLＢ、ｈead->ｎｅxt==NULＬC、head-〉neｘt=＝headD、hｅad!=ＮULＬ4、以下关于线性表得说法不正确得就是（）。
A、线性表中得数据元素可以就是数字、字符、记录等不同类型。
B、线性表中包含得数据元素个数不就是任意得。
C、线性表中得每个结点都有且只有一个直接前趋与直接后继。
D、存在这样得线性表:表中各结点都没有直接前趋与直接后继.5、在顺序表中,只要知道（）,就可在相同时间内求出任一结点得存储地址。
A、基地址B、结点大小Ｃ、向量大小D、基地址与结点大小6、（ )运算中,使用顺序表比链表好。
A、插入B、删除C、根据序号查找D、根据元素值查找７、一个长度为n得顺序表中，向第i个元素之前插入一个新元素时，需要向后移动( )个元素。
Ａ、ｎ-iB、ｎ-i＋1C、n—ｉ—18、（）适合作为经常在首尾两端操作线性表得存储结构.A、顺序表Ｂ、单链表Ｃ、循环链表D、双向链表９、栈与队列得共同点就是( )Ａ、都就是先进后出B、都就是先进先出C、只允许在端点处插入与删除元素D、没有共同点1一个队列得入列序列就是1 2 3 4,则队列得输出序列就是( ）。
０、A、4 3 ２ 1B、1 2 3 4C、1 4 3 2D、3 ２ 4 11队列与一般得线性表得区别在于（)。
１、A、数据元素得类型不同Ｂ、运算就是否受限制Ｃ、数据元素得个数不同D、逻辑结构不同12、“假上溢”现象会出现在( ）中。
Ａ、循环队列B、队列C、链队列D、顺序队列1.数据得逻辑结构被分为集合、线性结构、树形结构与图结构。
计算机科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题(单选题，每小题 3分，共33分)1. 已知某二叉树的中序、层序序列分别为DBAFCE 、FDEBCA ，则该二叉树的后序序列为 ______ 。
A . BCDEAFB . ABDCEFC . DBACEFD . DABECF2•在11个元素的有序表A[1…11]中进行折半查找((low high)/2 ),查找元素A[11]时，被比较的元素的下标依次是 _________ 。
A . 6, 8, 10, 11B . 6, 9, 10, 11C . 6, 7, 9, 11D . 6, 8, 9,113 •由元素序列(27, 16 , 75 , 38 , 51 )构造平衡二叉树，则首次出现的最小不平衡子 树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为 ________ 。
A . 27B . 38C. 51D . 754 .利用逐点插入法建立序列(50 , 72 , 43 , 85 , 75 , 20 , 35 , 45 , 65 , 30)对应的 二叉排序树以后，查找元素 30要进行 _______ 次元素间的比较。
A . 4B . 5C . 6D . 75 .循环链表的主要优点是 _____ 。
A .不再需要头指针了B .已知某个结点的位置后，很容易找到它的直接前驱结点C .在进行删除后，能保证链表不断开D .从表中任一结点出发都能遍历整个链表6 .已知一个线性表(38 , 25, 74 , 63 , 52 , 48),假定采用散列函数 h ( key ) =key%7 计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 ___________ 。
A . 1 . 5B . 1 . 7C . 2.0 D . 2.3 7 .由权值为 9 , 2 , 5 , 7 的四个叶子结点构造 棵哈夫曼树, 该树的带权路径长度&在最好和最坏情况下的时间复杂度均为A .基数排序B .快速排序C .堆排序9.无向图 G=(V , E),其中 V={a , b , c , d , e , e ),(c , f ), (f , d), (e , d)}。
数据结构期末考试试题(含答案)数据结构期末考试试题(含答案)第一题：多项式相加（20分）将两个多项式 P(x) 和 Q(x) 相加，结果存储在另一个多项式 S(x) 中，请写出相应的算法，并给出其时间复杂度分析。
答案：算法如下：1. 初始化一个空多项式 S(x)。
2. 分别取多项式 P(x) 和 Q(x) 的第一项，判断指数的大小关系，并将指数较小的项加入 S(x)。
3. 若指数相同，则将两项系数相加，并将结果加入 S(x)。
4. 重复步骤2和步骤3，直到两个多项式中的所有项都被处理完。
5. 返回结果多项式 S(x)。
时间复杂度分析：- 假设 P(x) 和 Q(x) 的项数分别为 m 和 n。
- 在最坏情况下，需要比较 m+n 次指数大小，并进行 m+n-1 次系数相加。
- 因此，该算法的时间复杂度为 O(m+n)。
第二题：循环队列设计（30分）请设计一个循环队列，实现入队、出队等基本操作，并给出时间复杂度分析。
答案：定义循环队列的结构体如下：```ctypedef struct {int *data; // 存储队列元素的数组int front; // 队首指针，指向队首元素的位置int rear; // 队尾指针，指向队尾的下一个位置int maxSize; // 队列的最大容量} CircularQueue;```基本操作的实现如下：1. 初始化循环队列：```cvoid initQueue(CircularQueue *queue, int maxSize) {queue->data = (int *)malloc(sizeof(int) * maxSize);queue->front = queue->rear = 0;queue->maxSize = maxSize;}```2. 入队操作：```cint enqueue(CircularQueue *queue, int value) {if ((queue->rear + 1) % queue->maxSize == queue->front) { return 0; // 队列已满，插入失败}queue->data[queue->rear] = value;queue->rear = (queue->rear + 1) % queue->maxSize;return 1; // 插入成功}```3. 出队操作：```cint dequeue(CircularQueue *queue, int *value) {if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}*value = queue->data[queue->front];queue->front = (queue->front + 1) % queue->maxSize; return 1; // 出队成功}```时间复杂度分析：- 入队和出队操作的时间复杂度均为 O(1)。
大学《数据结构》期末考试及答案 一、选择题（每题2分，共20分） 1. 下列哪种数据结构不属于线性结构？ A. 队列 B. 栈 C. 树 D. 双向链表 答案：C 2. 在线性表中，线性表的第i个元素之前的元素个数为（ ）。
A. i B. i-1 C. i+1 D. 0 答案：B 3. 下列哪种排序算法的平均时间复杂度最高？ A. 冒泡排序 B. 快速排序 C. 直接插入排序 D. 堆排序 答案：A 4. 在二叉树中，具有3个节点的二叉树有（ ）种不同的形态。
A. 2 B. 3 C. 4 D. 5 答案：C 5. 下列哪种图的遍历算法不是深度优先搜索？ A. 某个顶点出发，递归遍历 B. 队列实现遍历 C. 栈实现遍历 D. 按顶点的邻接点访问 答案：B 二、填空题（每题3分，共15分） 6. 在顺序存储的线性表中，插入一个元素的时间复杂度为______，删除一个元素的时间复杂度为______。
答案：O(n)，O(n) 7. 对于含有n个元素的顺序表，查找一个特定元素的最好情况时间复杂度为______，最坏情况时间复杂度为______。
答案：O(1)，O(n) 8. 在二叉树中，叶子节点的度为______，度为2的节点最多有______个。
答案：0，n/2 9. 下列排序算法中，时间复杂度为O(nlogn)的算法有______、______。
答案：快速排序、堆排序 10. 图的遍历算法通常分为______遍历和______遍历。
答案：深度，广度 三、判断题（每题3分，共15分） 11. 线性表是一种动态数据结构。（ ） 答案：√ 12. 在二叉树中，度为1的节点个数等于度为2的节点个数加1。（ ）
答案：√ 13. 队列是一种先进先出的线性表。（ ） 答案：√ 14. 在排序过程中，每次排序都会将一个元素放到其最终位置上的排序算法称为稳定排序。（ ）
答案：×（应为不稳定排序） 15. 快速排序算法的空间复杂度为O(n)。（ ） 答案：×（应为O(logn)） 四、应用题（共45分） 16. （10分）已知一个顺序表L，元素个数为n，编写一个算法实现将顺序表L中的元素循环右移k个位置。
《数据结构》期末考试试卷附答案一、单项选择题（本大题共10小题，每小题3分，共30分）1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A). n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9．Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。
电脑科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题〔单项选择题，每题3分，共33分〕1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查找〔⎣⎦2/)low+〕，查找元素(highA[11]时，被比较的元素的下标依次是。
A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，113．由元素序列〔27，16，75，38，51〕构造平衡二叉树，则首次出现的最小不平衡子树的根〔即离插入结点最近且平衡因子的绝对值为2的结点〕为。
A．27 B．38 C．51 D．754．利用逐点插入法建立序列〔50，72，43，85，75，20，35，45，65，30〕对应的二叉排序树以后，查找元素30要进行次元素间的比较。
A．4 B．5 C．6 D．75．循环链表的主要优点是。
A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表〔38，25，74，63，52，48〕，假定采用散列函数h〔key〕=key%7计算散列地址，并散列存储在散列表A[0…6]中，假设采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。
A．1．5 B．1．7 C．2．0 D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。
A．23 B．37 C．44 D．468．在最好和最坏情况下的时间复杂度均为O〔nlogn〕且稳定的排序方法是。
A．基数排序B．快速排序C．堆排序D．归并排序9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，〔a，e〕，(a，c)，〔b，e〕，〔c，f〕，(f，d)，〔e，d〕}。
1 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效）
一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（ ） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（ ） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（ ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（ ） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（ ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（ ） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（ ） 2
A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 C.以链接方式存储 D.以链接方式存储，且数据元素有序 二、填空（每空1分，共15分） 1.数据结构中评价算法的两个重要指标是 、空间复杂度。 2.在单链表中，指针P所指结点有后继的条件是 。（结点构成：data和next） 3.栈的特点是 。 4.判断循环队列是否队满的条件表达式是 。 5.完全二叉树中的结点个数为n，则编号最大的分支结点的编号为 。 6.如果A有7个兄弟，而B是A的双亲，则B的度是 。 7.如果二叉树中有20个叶子节点，30个度为1的结点，则该二叉树的总结点数为 。 8.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用.表示。现前序遍历二叉树的结点序列为ABD.G…CE.H..F..，则中序遍历二叉树的结点序列为 。 9.若用n表示图中的顶点数目，则有 条边的无向图被称为完全图。 10.如果具有n个顶点的图是一个环，则它有 棵生成树。 11.克鲁斯卡尔算法的时间复杂度是 ，它适合求 图的最小生成树。 12.顺序查找n个元素的线性表，若查找成功时的平均查找长度为 。 13.高度为5的完全二叉树，其结点最少有 个。 14.直接插入排序中使用的监视哨的作用是 。 三、判断题（每题1分，共10分） 1.算法独立于具体的程序设计语言，与具体的计算机无关。（ ） 2.线性表采用链式存储时，结点内部的存储空间可以是不连续的。（ ） 3.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ） 4.哈夫曼树的结点总个数一定是偶数。（ ） 5.已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树（ ）。 3
6.有e条边的无向图，在其对应的邻接表中有e个结点。（ ） 7.连通分量指的是无向图的极大连通子图。（ ） 8.在哈希表的查找过程中的“比较”操作是无法避免的。（ ） 9.完全二叉树肯定是平衡二叉树。（ ） 10.堆排序是稳定的排序算法。（ ） 四、简答题（共30分） 1.线性结构的特点是？（4分） 2.已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从A出发的广度优先搜索序列，以及相应的广度优先生成树。（6分） A B C D E F A B C D E F 3.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为CEIFGBADH，请画出这棵二叉树，并把这棵二叉树转换成相应的树（或森林）。（6分） 4.已知电文内容为：ACACBACDAACDBAACADAA，字符集为A，B，C，D，设计一套二进制编码，使得上述电文的编码最短。（6分） 5.已知有序序列{3，7，11，20，45，77，90}，请分别写出折半查找10和查找99的过程，并求出ASL（4分） 6.已知序列{34，17，6，29，33，11，80，37}请用快速排序的方法进行排序，并给出详细过程。（4分） 五、算法填空（每空5分，共20分） （1）按先序次序输入二叉树中的结点值(字符)构造二叉树 Status CreateBiTree(BiTree &T) { char ch;
0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1
0 0 1 0 0 1
1 1 0 0 0 0 0 1 1 1 0 0 4
read(ch); if( ch==' ' ) T = NULL; else { T = (BiTree)malloc(sizeof(BiTNode)); (1) ; CreateBiTree(T->lchild); (2) ; } return OK; } （2）在顺序表L的第 i 个元素之前插入新的元素e Status ListInsert(SqList &L, int i, ElemType e) { if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法 for ( j= L.length ; j>i ; j - - ) (3) ; L.elem[i-1] = e ; // 插入e (4) ; return OK; } // ListInsert_Sq
六、写算法（共15分） 1.请写出链式存储的线性表中，删除第i个位置数据元素的实现算法。（给出相应的结构体定义，关键部分给出注释。） 2011－2012学年第一学期期末考查 《数据结构》标准答案
一、选择（每题1分，共10分） 1-5 DBBBB 6-10 ACCDB 二、填空（每空1分，共15分） 1.时间复杂度，空间复杂度 2.FIFO，LIFO 3.Q.rear==Q.front 5
4.7 5.8 6.O(n2) ，稠密图 7.极大连通子图 8.n(n-1) 9.n-1 10.集合结构，树形结构，图状结构 三、判断题（每题1分，共10分） 1. × 2. √ 3. √ 4. × 5. √ 6. × 7. × 8. × 9. × 10. × 四、简答题（共30分） 1. (1)在二叉树的第 i 层上至多有2i-1 个结点； (i≥1) (2)深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）； (3)对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1； (4)具有 n 个结点的完全二叉树的深度为 log2n +1 。 (5)若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。 评分标准：答对5条中的4条得4分。 2. 深度优先遍历序列：abefdc 深度优先生成树： 评分标准：深度优先遍历序列3分，深度优先生成树3分。 3.(1)T->next->next=P->next; (2)Q=T;
c d f e b a 6
While(Q->!=P) {Q=Q->next;} Q->next=P->next; free(P); 评分标准：回答（1）或者（2）都正确。 4.
5.{11，3，7，77，20，45，90} 查找过程：11，3，7，77或者90，45，20，77 6.{34，17，6，29，33，11，80，37} d=5 11，17，6，29，33，34，80，37 d=3 11，17，6，29，33，34，80，37 d=1 6，11，17，29，33，34，37，80 五、算法填空（每空5分，共20分） 1. (1)visit(T->data); 或者printf(T->data); (2)PreOrderTraverse(T->rchild); 2.(1)return mid; (2)high=mid-1; 六、写算法（共15分） //删除表L中第i个元素，结果用e返回，操作成功返回OK，失败时返回ERROR Status ListDelete(SqList &L, int i, ElemType &e) { if(i<1||i>L.length)return ERROR;
A B C
D E F
