浙江工商大学《数据结构》xxxx年考试样卷(A卷)

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

《数据结构》期终考查试卷（A 卷）适用专业：一、单项选择题（每题2分，共40分）1、．算法的时间复杂度是指( )A ．执行算法程序所需要的时间B ．算法程序的长度C ．算法执行过程中所需要的基本运算次数D ．算法程序中的指令条数2、以下说法正确的是A ．线性结构的数据元素之间存在一对多的线性关系B ．图形结构和树型结构是线性结构C ．时间复杂度是用算法执行过程中所需要的基本运算次数来度量D ．时间复杂度总是与空间复杂度成正比3、在一个单链表HL 中，若要删除由指针q 所指向结点的后继结点，则执行（ ）。

A ．p = q->next ; p->next = q->next;B ．p = q->next ; q->next = p;C ．q->next = q->next->next; q->next = q;D ． p = q->next ; q->next = p->next 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、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A．front==NULL B．front!=NULL C．rear!=NULL D．front= =rear10、关于字符串的说法中，错误的是A、字符串是零个或多个字符组成的有限序列B、串中字符的个数称为串的长度C、长度为零的串称为空串D、由空格组成的字符串称为空串11、有关二叉树的下列说法正确的是A、任何一棵二叉树中至少有一个结点的度为2B、一棵二叉树的度可以小于2C、二叉树中任何一个结点的度都为2D、二叉树的度为212、对如下二叉树进行后序遍历的结果为A．ABCDEF B．DBEAFC C．ABDECF D．DEBFCA13、求图的最小生成树采用的算法是A．普里姆算法和克鲁斯卡尔算法B．迪杰斯特拉算法C．弗洛伊德算法D．深度优先算法14、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含V1，E2包含E1，则称( )。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的两个主要方面是2。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：广东商学院试题参考答案及评分标准20XX12-20XX13 学年第一学期课程名称： 数据结构（A 卷） 课程代码：20XXXX0XX20XXXX0XX 课程负责人：罗勇题号1 2 3 4 5 6 7 8 9 20XXXX 答案B A AC BACADC题号1 2 3 4 5 6 7 8 9 20XXXX 答案C B C B DDABAB题号1 2 3 4 5 6 7 8 9 20XXXX答案× √ × √ √ × × × √ ×四、算法分析（每小题5分，共20XXXX 分）1．(1) ABC_1是直接插入排序方法。

（1分） 最坏情形下，)(2/2/)1)(2(i KCN 222n O n n n ni =≈-+==∑= （1分）)(2/2/)1)(4()21(RMN 22n2n O n n n i i =≈-+=+-=∑= （1分）(2) 排序过程如下：（2分）初始key r[0] (65) 38 80 50 20XXXX 27i=2 38 (38 65) 80 50 20XXXX 27 i=3 38 (38 65 80) 50 20XXXX 27 i=4 50 (38 50 65 80) 20XXXX 27i=5 20XXXX (20XXXX 38 50 65 80) 27 i=6 27 (20XXXX 27 38 50 65 80) （注：哨兵单元不正确扣1分，已排序列不正确扣1分）2．(1) 算法ABC_2功能：以中序遍历的次序，按关键字值递增的顺序依次输出值小于等于给定值60的结点。

若找到值大于60的结点，提前退出算法。

（3分）（2）20XXXX 20XX 35 45 55（每个值输出后换行）（2分）五、算法设计（共10分）（1）写出单链表存储结构的类型定义。

Typedef struct {int data; (1分)struct LNode *next; (1分)} LNode, *LinkList; (1分)（2）status Delete_L(LinkList &L, int min, int max) { LinkList p,q,s;p=L;while (p&&p->next->data<=min) （2分）p=p->next;if (!p) return ERROR;q=p->next;while (q&&q->data<=max) （3分）{ s=q;q=q->next;free(s);} //whilep->next=q; （2分）return OK;}//Delete_L教师（签名）：年月日。

山东工商学院2020学年第一学期数据结构课程试题 A卷（考试时间：120分钟，满分100分）特别提醒：1、所有答案均须填写在960数字加起来827参考答案207上，写在试题纸上无效。

2、每份答卷上均须准确填写函授站、专业、年级、学号、姓名、课程名称。

一单选题 (共20题，总分值40分 )1. 以下属单链表优点的是（）。

（2 分）A. 顺序存取B. 插入操作能在O(1)的时间复杂度上完成C. 插入时不需移动数据元素D. 节省存储空间2. 外部排序是指（）。

（2 分）A. 在外存上进行的排序方法B. 不需要使用内存的排序方法C. 数据量很大，需要人工干预的排序方法D. 排序前后数据在外存，排序时数据调入内存的排序方法3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

（2 分）A. 顺序表B. 双链表C. 带头结点的双向循环链表D. 单循环链表4. 下列不属算法特性的是（）。

（2 分）A. 有穷性B. 确定性C. 零或多个输入D. 健壮性5. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

（2 分）A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38,46,56,79,84D. 40,38,46,84,56,796. ISAM文件和VSAM文件属于（）。

（2 分）A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件7. 直接插入排序在最好情况下的时间复杂度为（）。

（2 分）A. O(logn)B. O(n)C. O(n*logn)D. O(n2)8. 判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。

（2 分）A. SB. S-＞nextC. S-＞next==NULLD. !S9. 在树形结构中，数据元素间存在（）的关系。

山东工商学院2020学年第一学期数据结构课程试题 A卷（考试时间：120分钟，满分100分）特别提醒：1、所有答案均须填写在960数字加起来827参考答案207上，写在试题纸上无效。

2、每份答卷上均须准确填写函授站、专业、年级、学号、姓名、课程名称。

一单选题 (共20题，总分值40分 )1. 一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（）。

（2 分）A. 5个B. 6个C. 7个D. 8个2. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。

（2 分）A. bB. cC. (c)D. (c,d,e)3. 下列关于文件的说法，错误的是（）。

（2 分）A. 选择文件的组织方式时应考虑外存的性质和容量B. 不定长文件指的是总长度可变的文件C. 对文件的操作主要是维护和检索D. 文件的存储结构指的是文件在外存上的组织方式4. 串的长度是指（）。

（2 分）A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数5. 在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。

（2 分）A. 不变B. top=nC. top++D. top--6. 设有无向图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)}。

对G进行深度优先遍历，正确的遍历序列是（）。

（2 分）A. a,b,e,c,d,fB. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b7. 适用于折半查找的表的存储方式及元素排列要求为（）。

（2 分）A. 链接方式存储，元素无序B. 链接方式存储，元素有序C. 顺序方式存储，元素无序D. 顺序方式存储，元素有序8. 顺序表中数据元素的存取方式为（）。

专升本)数据结构A卷参考答案:简答题1,数据结构是相互之间存在一种或多种特定关系的数据元素的集合.这种数据元素相互之间的关系称为结构.可以将数据结构形式化地定义为二元组:Data_Structure=(D,S)其中:D是数据元素的有限集,S是D上关系的有限集.数据结构课程主要讨论数据的逻辑结构,物理结构和操作三个方面的问题.2,算法的时间复杂度是指算法中各语句的频度之和T(n),其中频度指语句的执行次数,n指问题的规模,一般为数据的输入量.渐近时间复杂度:当问题的规模n趋于无穷大时,T(n)的数量级(阶).记为T(n)=O( f(n) ).这里"O"是一种近似表示法,其含义是:在n较大时,该算法的运行时间和f(n)成正比,或者说,T(n)的数量级和f(n)的数量级相同.实际中,将渐近时间复杂度简称为时间复杂度,用以描述算法的时间特性.3,顺序表的优点:(1)可直接求出存储地址(随机存储结构),结构简单,便于随机访问表中的任一元素.(2)存储密度高.顺序表的缺点:(1)不便于插入和删除.(移动元素次数多,平均约需移动一半元素)(2)不便于扩充表的容量.(3)不能有效地利用内存空间.单链表的优点:(1)结点空间可动态申请动态释放.(2)每个结点有指针域指示逻辑顺序,进行插入删除操作时不需移动元素.单链表的缺点:(1)不能随机访问表中任一元素,效率低.(2)存储量可随意扩充,但新增加的存储空间可能与以前的不邻接,故需要设立一些存放地址用的存储单元.4,入栈算法:int push (qstype *s, elemtype x){if (s→top==MAXNUM-1)return 0;else { s→top++;s→stack [s→top]=x;return 1; }}出栈算法:elemtype pop(qstype *s){if (s→topnext!=NULL)if (p->data!=p->next->data)p=p->next;else{ q=p->next;p->next=q->next;free(q);}}return head;}2,#define m 100typedef struct btreenode{ elemtype data;struct btreenode *left;struct btreenode *right;} btree; /*二叉链表的形式化定义*/ void postorder(btree * b){btree * stack[m],*p;int tag[m],top=0;p=b;do{while (p!=NULL){ top++;stack[top]=p;tag[top]=0;p=p->left;}if (top>0){ p=stack[top];if (tag[top]==1){ top--;printf("%d",p->data);}if (top>0){ p=p->right;tag[top]=1;}}}while (p!=NULL&&top!=0)}。

浙江工商大学数据结构期末复习题2(总41页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--数据结构习题集一、选择题１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一２.在一个具有n top作为栈顶指针，则当做退栈处理时，topA. top不变Ｂ. top＝top=top+1３先移动栈顶指针，后存入元素４.在一个顺序存储的循环队列中，队首指针指向队首元素的A 。

A. 前一个位置B. 后一个位置C. 队首元素位置D. 队尾元素位置５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。

A. 3,4,2,1B. 2,4,3,1C. 1,4,2,3D.3,2,1,4６.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为front= =0７.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是D。

A. rear % n= =frontB. (rear-1) % n= =frontC. (rear-1) % n= =rearD. (rear+1) % n= =front８.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较D个结点。

９.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p 之间插入*s结点，则执行C。

A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C. q->next=s; s->next=p;D. p->next=s; s->next=q;10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行C。

A. hs->next=s;B. s->next=hs->next; hs->next=s;C. s->next=hs；hs=s;D. s->next=hs; hs=hs->next;11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行B。

《数据结构》课程期末考试试卷（ A 卷）考核方式：开卷考试日期：2009 年1 月15 日适用专业、班级：08电子商务1、2一、填空题（每空1分，共10分）1．_字节是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2．数据的物理存储结构分为____顺序存储结构____和____链式存储结构______二种。

3．下面程序段的时间复杂度是O（n）_____。

int n=10,sum=0;for(int i=0;i<n;i++)sum+=n;4.栈和队列是操作受限的线性表，队列又称_先进先出_______线性表。

5．若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点，最多有______个结点。

6．每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。

7．在线性表的散列存储中，处理冲突的常用方法有__开放地址法_____________和_______链地址法_________两种。

二、综合运算题（每小题5分，共25分）1．有以下双端链表的图形，要求完成在最后一个结点插入一个新结点的语句，新插入结点为newEntry，其中newEntry中的数据元素值为“kate”。

其中节点定义类型如下：class Entry{Object data;Entry next;public Entry(Object data){this.data = data;}}2．已知一棵二叉树的前序遍历结果为ABDGEFCH，中序遍历的结果为GDBEAFHC，画出该二叉树，并给出后序遍历的结果。

3．将关键码6３，8８，7５，2７，9７，1９，9１，5５，3３依次插入到一棵初始为空的二叉搜索树中，画出对应的二叉搜索树。

4．举例说明clone方法的含义，并对浅克隆与深度克隆进行说明及图示？5．设待排序文件的关键码为（42, 65,80,77,43,55, 2,87,44,60），第一个元素为分界元素（枢轴）进行快速排序（按关键码值递增顺序），请给出第一趟排序后的结果。