浙大数据结构期末试卷-2013-2014

《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。

下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。

2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题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. 编写一个函数，实现链表的插入操作。

《数据结构》期末考试试题及答案(2003-2004学年第2学期)单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。

(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。

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 ）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（ d ）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（ c ）层上。

（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 ）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（ a b ）（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等于（ c ）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（ c ）域存储后继结点的地址。

数据结构期末考试题及答案一、选择题（每题2分，共10题）1. 数据结构是指（）A. 存储和组织数据的方式B. 对数据进行计算和处理的方法C. 数据的物理表示形式D. 数据的逻辑结构答案：A. 存储和组织数据的方式2. 在数据结构中，栈是一种（）A. 先进先出的数据结构B. 后进先出的数据结构C. 随机存取的数据结构D. 按键值查找的数据结构答案：B. 后进先出的数据结构3. 下列哪种数据结构不支持随机访问？（）A. 队列B. 栈C. 数组D. 链表答案：D. 链表4. 在二叉树中，每个节点最多可以有几个子节点？（）A. 0B. 1C. 2D. 无限多答案：C. 25. 在图的表示方法中，邻接矩阵适用于（）A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A. 稠密图6. 下列排序算法中，最坏情况时间复杂度为O(nlogn)的是（）A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C. 快速排序7. 广度优先搜索算法用于（）A. 求最短路径B. 求全排列C. 求最小生成树D. 求图的连通分量答案：A. 求最短路径8. 哈希表的查找时间复杂度为（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A. O(1)9. AVL树是一种（）A. 无序树B. 有序树C. 平衡树D. 非平衡树答案：C. 平衡树10. 以下哪个不属于基本的查找算法？（）A. 二分查找B. 插值查找C. 散列查找D. 顺序查找答案：C. 散列查找二、填空题（每题4分，共4题）11. 下列不是线性表的是（）答案：二叉树12. 在冒泡排序中，每一轮的比较次数是________答案：n-113. 在堆排序中，堆的建立时间复杂度为________答案：O(n)14. 从一个顶点到其余各顶点的最短路径算法是________答案：Dijkstra算法三、简答题（每题10分，共3题）15. 请简要说明栈的应用场景，并给出一个具体实例。

合肥学院20 13 至20 14 学年第 2 学期数据结构与算法设计 课程考试（ A ）卷答案一、选择题：（2分×15=30分）1．A 2．D 3．B 4．B 5. C 6．D 7. A 8． B 9. D 10. B 11. D 12. D 13. A 14. A 15. A二、填空题：（2分×10=20分）1． n+1-i 2． s->next=p->next; p->next=s3. 12，24，35，27，18，26 4． A[i][j]=1 5. h6. ki<=k2i && ki<=k2i+17. mid=(low+high)/2; r[mid].key>k 8． 中序。

三、应用题：（5分×5=25分）1．树的链式存储结构（3分） 二叉树（2分）2．邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡011110101110111010101110（3分）邻接表：（2分）3．（3分）（2分）4．（4分）E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} （1分） 5、（5分）四、算法阅读题：（7分+5分=12分） 1、（1）查询链表的尾结点 （3分） （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3分） （3）返回的线性表为（a2,a3,…,an,a1）。

（1） 2．递归地后序遍历链式存储的二叉树 （5分） 五、算法设计题：（7分+6分=13分） 1．void mergelklist(lklist *ha,lklist *hb,lklist *&hc)AB GC EH JF D Ilklist *s=hc=0; （2分）while(ha!=0 && hb!=0)if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} （3分）if(ha==0) s->next=hb; else s->next=ha; （2分）}2.typedef struct node {int data; struct node *lchild,*rchild;} bitree; （2分）void swapbitree(bitree *bt){bitree *p;if(bt==0) return;swapbitree(bt->lchild); swapbitree(bt->rchild); （2分）p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; （2分）}。

《数据结构》期末考试试卷（含答案）《数据结构》期末考试试卷（ A ）一、选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据B.数据元素C.数据结构D.数据类型2．栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100D. 1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA. 2h B .2h-1C. 2h+1D. h+1软件开发网/doc/d818218954.html,8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

下列结论哪个正确？AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2D. 411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点软件开发网/doc/d818218954.html,12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41B.23和39C.15和44D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。

数据结构期末考试试题及答案一、选择题1. 在数据结构中，以下哪种数据结构是“先进先出”（FIFO）的？A. 栈B. 队列C. 链表D. 堆答案：B2. 哪种数据结构具有类似现实生活中“洋葱”的结构？A. 链表B. 树C. 图D. 堆答案：B3. 在常见的排序算法中，以下哪个算法具有最好的时间复杂度？A. 快速排序B. 插入排序C. 冒泡排序D. 选择排序答案：A4. 以下哪个数据结构可以解决“最短路径”问题？A. 队列B. 链表C. 树D. 图答案：D5. 在二叉搜索树中，节点的左子树的值都小于节点的值，右子树的值都大于节点的值。

这种特点被称为：A. 平衡性B. 完全性C. 左倾性D. 有序性答案：D二、填空题1. 在栈的操作中，插入元素的操作被称为______。

答案：push2. 哈希表通过______的方式快速查找元素。

答案：散列3. 在链表中，指向链表头部的指针被称为______。

答案：头指针4. 在图的遍历算法中，使用队列的遍历方式被称为______。

答案：广度优先搜索5. 大O表示法中，表示最坏情况下时间复杂度的记号是______。

答案：O三、简答题1. 请简要说明栈和队列的特点及应用场景。

答：栈是一种先进后出（FILO）的数据结构，只能在栈顶进行插入和删除操作。

栈的应用场景包括函数调用、表达式求值、撤销操作等。

队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。

队列的应用场景包括多线程任务调度、消息队列等。

2. 简要描述堆排序的思想和步骤。

答：堆排序是一种基于二叉堆的排序算法。

首先，将待排序序列构建成一个大顶堆；然后，将堆顶元素与最后一个元素交换，即将最大元素放到已排序部分的末尾；接着，重新调整堆，将剩余元素重新构建成大顶堆；重复以上步骤，直到所有元素排序完成。

四、编程题请使用C语言实现一个二叉树的前序遍历算法。

```c#include <stdio.h>#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};void preorderTraversal(struct TreeNode* root) {if (root != NULL) {printf("%d ", root->val); // 先访问根节点preorderTraversal(root->left); // 再遍历左子树preorderTraversal(root->right); // 最后遍历右子树}}int main() {// 构建二叉树struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = 1;node1->val = 2;node2->val = 3;root->left = node1;root->right = node2;node1->left = NULL;node1->right = NULL;node2->left = NULL;node2->right = NULL;// 调用前序遍历函数preorderTraversal(root);return 0;}```本文介绍了数据结构期末考试的试题及答案，涵盖了选择题、填空题、简答题和编程题等不同题型。

试卷代号:1252中央广播电视大学2013-2014学年度第一学期“开放学科”期末考试数据结构（本）试题2014年1月一、单项选择题（每小题2分，共30分）1. 在数据结构和算法中，与所使用的计算机有关的是（B）。

A．数据元数间的抽象关系 B．数据的存储结构C．算法的时间复杂度 D．数据的逻辑结构2.对顺序表,以下叙述中正确的是 ( A )。

A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素3．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（C）。

A．9 B．10 C．15 D．164. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( A)。

A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p ;5．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（A）。

（进栈出栈可以交替进行）。

A．7，5，3，1 B．7，3，1,5C．7，5，1，3 D．5,1，3，76．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（C）。

A．p=top->next; top=top next; B．p->next=top;C．p->next=top;top=p; D．top=p;7．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（D）。

(矩阵中的第1个元素是a1,1）A．a7,6 B．a10,8C．a9,2 D．a8,58．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6在一维数组B中的下标是（C）。

1 / 46）（ 至 学年第课程名称： 数据结构一、判断选择填空 (10分)1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

....( )2、用树的前序遍历和中序遍历可以导出树的后3、单链表从任何一个结点出发，都能访问到所有结点。

.....( )4、外部排序是在排序过程中，只使用外存储器的排序。

.....( )5、设串S 的长度为n,则S 的子串个数为n(n+1)/2。

.....( ) 6、若二叉树中的一个叶子结点是某子树中序序列的最后一个结点，则它必是该子树的先序序列的最后一个结点。

..... ( )7、设h 是一散列函数，key1和key2为关键码值，且 key1<>key2，但h （key1）=h （key2），这种现象称为（ ）。

8、若入栈序列的元素顺序是A 、B 、C 、D 、E ，判断下列哪一个出栈序列是不可能的（ ）⑴. A 、B 、C 、D 、E ⑵. B 、C 、D 、E 、A ⑶.E 、A 、B 、C 、D ⑷.D 、C 、B 、A 、E9、设i 为n 个结点的完全二叉树结点编，i=1，2，3...n ；若i ≤（n-1）/2时，结点i 的右孩子为（ ）⑴. 2i ⑵. 2i+1 ⑶. 2i-1⑷. i+110、若S1=‘China'，S2='$Beijing',则S1//S2=( )。

二、（5分）简述顺序存储结构和链式存储结构的优缺点。

三、（5分）简述使用顺序存储表示循环队列时，判定队列“空”和“满”的方法。

四、（5分）编写子串位置定位函数Index(S,T,pos)；五、（5分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，画出相应的Huffman树，并写出a,b,c,d,e,f的Huffman编码。

六、（5分）假设一棵二叉树的后序序列为GDBEHFCA和中序序列为DGBAECHF，请画出该二叉树，并写出先序遍历序列。

“数据结构”期末考试试题一、单选题(每小题2分,共12分）1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行（ )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有（ ).A。

n—l条有向边 B.n条有向边C.n(n—1)／2条有向边 D。

n（n一1）条有向边3。

从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为（ )。

A。

O(1) B。

O（n）C.O(1Ogzn）D.O(n2）4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( ）。

A．O（n) B．O(1)C．O（n2） D．O（10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、-—和—-四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．-—中缀表达式 3十x＊(2。

4／5—6）所对应的后缀表达式为———-。

4．在一棵高度为h的3叉树中,最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为—-,最大深度为-—·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定-—该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整，直到被调整到——位置为止.8．表示图的三种存储结构为——、——和-——.9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为-—，对用邻接表表示的图进行任一种遍历时，其时间复杂度为—-。

数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或多对多的关系2. 栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任一位置进行插入和删除操作B. 只能在表的首端进行插入和删除操作C. 只能在表的末端进行插入和删除操作D. 插入和删除操作没有特定的限制3. 以下哪个算法是排序算法？A. 快速排序B. 深度优先搜索C. 广度优先搜索D. 二分查找4. 哈希表解决冲突的常用方法不包括：A. 开放寻址法B. 链地址法C. 二分查找法D. 再散列法5. 在图的遍历算法中，深度优先搜索（DFS）使用的是：A. 栈B. 队列C. 链表D. 树...（此处省略其他选择题）二、简答题（每题10分，共30分）1. 请简述二叉树的三种遍历方法及其特点。

2. 什么是平衡二叉树？请说明它与普通二叉树的区别。

3. 解释什么是图的邻接矩阵表示法和邻接表表示法，并比较它们的优缺点。

三、计算题（每题15分，共30分）1. 给定一个数组A[1...n]，请写出一个时间复杂度为O(n)的算法，找出数组中的最大值和最小值。

2. 假设有一个链表，链表中的节点按照值递增的顺序排列，请设计一个算法删除链表中所有重复的节点。

四、编程题（每题20分，共20分）1. 编写一个函数，实现二叉搜索树的插入操作，并保证树的平衡。

数据结构期末考试答案一、选择题1. C2. B3. A4. C5. A...（此处省略其他选择题答案）二、简答题1. 二叉树的三种遍历方法包括前序遍历、中序遍历和后序遍历。

前序遍历首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

中序遍历首先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

后序遍历首先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷)一、应用题(3小题,共24分)1．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。

【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。

其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。

2．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=［ i/2 」(取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。

【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/123．分析下面各程序段的时间复杂度（1）s1(int n){ int p=1,s=0;for (i=1;i<=n;i++){ p*=i;s+=p; }return(s);} ——O(n)（2）s2(int n)x=0;y=0;For (k=1;k<=n;k++) x++;For (i=1;i<=n;i++)For (j=1;j<=n;j++)y++; ——O(n2)1．下述算法的功能是什么?（1）（1）返回结点*p的直接前趋结点地址。

数据结构期末测试题及答案一、选择题（每题2分，共40分）1. 数据结构是指（）。

A. 存储数据的方式和方法B. 描述数据和操作数据的方式和方法C. 组织数据和操作数据的方式和方法D. 分析数据和操作数据的方式和方法答案：C2. 在数据结构中，数组是（）。

A. 存储在连续内存空间中的元素集合B. 存储在非连续内存空间中的元素集合C. 存储在链表中的元素集合D. 存储在哈希表中的元素集合答案：A3. 下列哪种数据结构的查找操作时间复杂度一定是O(1)？A. 数组B. 链表C. 栈D. 哈希表答案：D4. 假设有一个长度为n的有序数组，采用二分法查找元素的时间复杂度是（）。

A. O(1)B. O(log n)C. O(n)D. O(n log n)答案：B5. 在数据结构中，栈是一种（）。

A. 先进先出的数据结构B. 后进先出的数据结构C. 可以在任意位置插入和删除元素的数据结构D. 可以动态扩展和缩小的数据结构答案：B二、填空题（每题5分，共40分）1. 链表是一种（）数据结构。

答案：线性2. 在二叉树中，一个节点的子节点个数最多为（）。

答案：23. 在图的表示中，邻接矩阵法中用1表示两个顶点之间存在边，用0表示不存在边，这种方法适用于边的数量相对较（）的图。

答案：少4. 在树的遍历中，先序遍历是指先访问（）节点，然后再分别先序遍历它的左子树和右子树。

答案：根5. 哈希表通过（）将键映射到值。

答案：哈希函数三、简答题（每题10分，共20分）1. 请简要介绍栈和队列的特点和用途。

栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。

栈常用于实现程序调用的过程，如函数调用、表达式求值等。

队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。

队列常用于实现排队、任务调度等场景。

2. 请简述二叉搜索树的特点和应用场景。

二叉搜索树是一种有序树结构，每个节点的左子树的值都小于该节点的值，右子树的值都大于该节点的值。

数据结构期末考试试题及答案一、选择题评价一个算法时间性能的主要标准是()。

1.A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度〔〕等五个特性。

计算机算法具备有输入、输出、 2.A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、xx、稳定性和 xx。

带头结点的单链表head 为空的判定条件是〔〕 3.A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL以下关于线性表的说法不正确的选项是()。

4.A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。

、基地址B、结点大小C、向量大小D、基地址和结点大小()运算中，使用顺序表比链表好。

6.A、插入B、删除C、根据序号查找D、根据元素值查找一个长度为 n 的顺序表中，向第 i 个元素之前插入一个新元素时，需要向后移动〔〕个元素、n-iB、n-i+1C、n-i-1D、i()适合作为经常在首尾两端操作线性表的存储结构。

8.A、顺序表B、单链表C、循环链表D、双向链表栈和队列的共同点是〔〕9.A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点一个队列的入列序列是1234，那么队列的输出序列是()。

10.A、4321B、12 3 4C、1432D、3241队列与一般的线性表的区别在于()。

11.A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同“假上溢〞现象会出现在 ()中。

12.A、循环队列B、队列C、链队列、顺序队列 D．二、填空．数据的逻辑结构被分集合、线性结构、树形结构和图结构．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构．下面程序段的时间复杂度i=s=0whil(s<ni++s++;．树型结构和图形结构合称是非线性结构．在长度的顺序存储线性表的个元素〔 1≤i ≤n〕之前插入一个元素时需要向后移 n-i+个元素．在一个长度的顺序存储的线性表中，删除个元素〔 1≤i ≤n〕时需要向前移n-个元素．指指向非空循环单链hea 的尾结点，满 p->next=hea．已是带头结点的非空单链表，结点既不是第一个数据结点，也不是最后一个结点，的答案中选择适宜的语句序列，实现删结点的直接后继结点的语句序列 P->nexP->nex->nextP=P->next->nextwhil(P->next!=QP=P->nextwhil(P->next->next=QP=P->nextQ=PQ=P->nextP=L⑧L=L->next;⑨free(Q);9．在线性结构中，第一个结点无前驱结点，其余每个结点有且只有 1 个前驱结点。

1、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边2、数据结构中，在逻辑上可以把数据结构分成（ B ）。

A）动态结构和静态结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）内部结构和外部结构3、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵4、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;5、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5C）6 D）76、线索二叉树中某结点D，没有左孩子的条件是（ B ）。

A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=07、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。

A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p8、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))9、下列各种数据结构中属于线性结构的有（ A ）。