当前位置：文档库 › 数据结构形成性考核作业册

数据结构形成性考核作业册

数据结构（本）形成性考核作业册

使用说明

本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与《数据结构（本科）》教材（伟生主编，中央电大出版）配套使用。

数据结构（本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程，4学分，共72学时。其中实验24学时，开设一学期。本课程的特点是综合性、实践性强，容抽象，在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学容进行上机实践，认真完成作业和实验容。

本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70％（闭卷，答题时限为90分钟）。课程总成绩达到60分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为70分，即课程总成绩达到70分及以上者有资格申请专业学位。

本课程共设计了4次形考作业，每次形考作业均包括实验容，由各地电大根据学生对作业中各种题型练习和实验的完成情况进行考核。对于实验容要求按实验要求认真完成，并提交实验报告。

数据结构（本）课程作业

作业1

（本部分作业覆盖教材第1-2章的容）

一、单项选择题

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．与数据结构

11．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A．逻辑结构 B．物理结构

C．算法的具体实现 D．给相关变量分配存储单元

12．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）。

A．n-i+1 B．n-i C．n-i-1 D．i

13．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

A．n-i+1 B．n-i C．n-i-1 D．i

14．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A．p=q->next B．p->next=q C．p->next=q next D．q->next=NULL 15．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

A．p->next= s; s next= p next B．p->next=s next;

C．p=s->next D．s->next=p->next; p->next=s;

16．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。

A.．P->next= =NULL B．P= =NULL

C．P->next= =head D．P= = head

17．链表不具有的特点是（）。

A．可随机访问任一元素 B．插入删除不需要移动元素

C．不必事先估计存储空间 D．所需空间与线性表长度成正比

18．带头结点的链表为空的判断条件是（）（设头指针为head）。

A．head = =NULL

B．head->next= =NULL

C．head->next= =head

D．head!=NULL

19．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A．p=q->next

B．p->next=q

C．p->next=q->next

D．q->next=NULL

20．下面关于线性表的叙述错误的是( )。

A.．线性表采用顺序存储,必须占用一片地址连续的单元

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

C．线性表采用链式存储,不必占用一片地址连续的单元

D．线性表采用链式存储,便于进行插入和删除操作

21．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 A．r=f->next; B．r=r->next;

C．f=f->next; D．f=r->next;

22．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。

A．f->next=s; f=s; B．r->next=s;r=s;

C．s->next=r;r=s; D．s->next=f;f=s;

23.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（）。

A．98 B．100 C．102 D．106

24．用链表表示线性表的优点是（）。

A．便于随机存取

B．花费的存储空间较顺序存储少

C．便于插入和删除

D．数据元素的物理顺序和逻辑顺序相同

25．有关线性表的正确说法是（）。

A．每个元素都有一个直接前驱和一个直接后继

B．线性表至少要求一个元素

C．表中的元素必须按由小到大或由大到下排序

D．除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继

二、填空题

1．在一个长度为n的顺序存储结构的线性表中，向第i(1i n+1)个元素之前插入新元素时，需向后移动个数据元素。

2．从长度为n的采用顺序存储结构的线性表中删除第i(1i n+1)个元素，需向前移动个元素。

3．数据结构按结点间的关系，可分为4种逻辑结构：、

、、。

4．数据的逻辑结构在计算机中的表示称为或。

5．除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为，每个结点可有任意多个前驱和后继结点数的结构为。

6．算法的5个重要特性是、、、、。

7．数据结构中的数据元素存在多对多的关系称为_____ ___结构。

8．数据结构中的数据元素存在一对多的关系称为___ _____结构。

9．数据结构中的数据元素存在一对一的关系称为______ __结构。

10．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为___ _____和 ____ ____ 。

11．在一个单链表中p所指结点之后插入一个s所指结点时，应执行___ _____和p->next=s;的操作。

12．设有一个头指针为head的单向循环链表，p指向链表中的结点，若

p->next= =____ ____，则p所指结点为尾结点。

13．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作_ _______。

14．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作_____ ___,就可使该单向链表构造成单向循环链表。

15．每个结点只包含一个指针域的线性表叫。

16．线性表具有和两种存储结构。

17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系无关，是独立于计算机的。

18．在双向循环链表的每个结点中包含指针域，其中next指向它的，

prior指向它的，而头结点的prior指向，尾结点的next指向。

19．单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。

20．线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。

三、问答题

1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

3．什么情况下用顺序表比链表好？

4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？

5．解释带头结点的单链表和不带头结点的单链表的区别。

6．与单链表相比，双向循环链表有哪些优点？

四、程序填空题

1．下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格填上适当的语句。

NODE *create1(n)

/* 对线性表(1,2,.....,n),建立带头结点的单向链表 */

{

NODE *head,*p,*q;

int i;

p=(NODE *)malloc(sizeof(NODE));

head=p; q=p; p->next=NULL;

for(i=1;i<=n;i++)

{

p=(NODE *)malloc(sizeof(NODE));

（1） ;

（2） ;

（3） ;

（4） ;

}

return(head);

}

2．下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格填上适当的语句。

NODE *create2(n)

/*对线性表(n,n-1,.....,1),建立带头结点的线性链表 */

{

NODE *head,*p,*q;

int i;

p=(NODE *)malloc(sizeof(NODE));

（1） ;

p->next=NULL;

（2） ;

for(i=1;i<=n;i++)

{

p=(NODE *)malloc(sizeof(NODE));

p->data=i;

if(i==1)

（3） ;

else

（4） ;

（5） ;

}

return(head);

}

3．下列是在具有头结点的单向列表的第ij个结点之间插入新结点x的算法（1 i n+1），请在空格填上适当的语句。

int insert(NODE *head,int x,int i)

{

NODE *q,*p;

int j;

（1） ;

j=0;

while((q!=NULL)&&(j

{q=q->next;j++;}

if(q==NULL) return(0);

p=(NODE *)malloc(sizeof(NODE));

p->data=x;

（2） ;

（3） ;

return(1);

}

4．下列是在具有头结点单向列表中删除第i个结点，请在空格填上适当的语句。

int delete(NODE *head,int i)

{

NODE *p,*q;

int j;

q=head;

j=0;

while((q!=NULL)&&(j

{

q=q->next;

j++;

}

if(q==NULL)

return(0);

（1） ;

（2） ;

free(p);

return(1);

}

五、完成：实验1――线性表

根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。

数据结构课程设计参考题目

数据结构课程设计题目数据结构课程设计题目(大题目).doc 一、公司销售管理系统项目开发基本要求 1．客户信息管理：对客户的基本信息进行添加、修改和删除。 2．产品信息管理：对产品的基本信息进行添加、修改和删除。 3．供应商信息管理：对供应商的基本信息进行添加、修改和删除。 4．订单信息管理：对订单的基本信息进行添加、修改和删除。二、高校科研管理系统系统主要用于帮助高校或科研单位管理和维护各项科研相关资料项目开发基本要求 1．系统用户管理模块：为系统新用户设置用户名及口令；操作员更改自己的系统口令。2．数据字典管理模块：管理项目性质包括：分为国家自然科学基金、863、部省科委及企业集团四种情况；范围包括：分为全国、国际、地方三种情况；检索源包括：分为EI、SCI、核心和一般四种情况。 3．项目参加人员管理模块包括：显示添加修改删除查询。 4．项目基本情况模块包括：显示添加修改删除查询。 5．项目获奖情况模块包括：显示添加修改删除查询。 6．期刊论文管理模块包括：显示添加修改删除查询。 7．著作管理模块包括：显示添加修改删除查询。 8．科研工作量统计模块：按照学校科研工作量计算办法，为每位科研人员进行科研工作量的计算和统计。 9．科研积分统计模块：按照学校科研积分计算办法，为每位科研人员进行科研计分的计算和统计。三、网络五子棋对战四、不同排序算法模拟五、科学计算器数据结构课程设计题目 1.运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n< =20）功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分，

数据结构与算法习题及答案

第1章绪论习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题（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．栈 6．试分析下面各程序段的时间复杂度。（1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i

十套数据结构试题及答案55426知识讲解

十套数据结构试题及答案55426

数据结构试卷（一）一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( a )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( d ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( d ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( c )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1] 中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 c n） D. O A. O（1） B. O（n） C. O（1og 2 （n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_ 易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。

数据结构与算法C语言版期末复习题

《数据结构与算法》期末复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

东南大学十套数据结构试题及答案

数据结构试卷（一）三、计算题（每题 6 分，共24分） 1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 dat a nex t 2. 3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a 1,a 2 , …,a n ）,写出算法执行后的返回值所表示的线性表。 2.void ABC(BTNode * BT) {

if BT { ABC (BT->left); ABC (BT->right); cout<data<<' '; } } 该算法的功能是：五、算法填空（共8分）二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(itemdata) return Find(______________,item); else return Find(_______________,item); }//if } 六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

数据结构课程设计独立题目

题目2：运动会分数统计 1.问题描述参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 2.功能要求 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分； 3)可以按学校编号、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。。题目6：哈夫曼编/译码器 1.问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 2.功能要求 I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile 中。 D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中。题目9：构造可以使n个城市连接的最小生成树 1.问题描述给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 2.功能要求城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。

数据结构与算法复习题库含答案

数据结构复习题第一章概论一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。

数据结构课程设计题目

《数据结构》课程设计题目 1. 排序算法的性能分析问题描述设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。基本要求（1）对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进行比较。（2）待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。（3）输出比较结果。选做内容（1）对不同表长进行比较。（2）验证各算法的稳定性。（3）输出界面的优化。 2. 排序算法思想的可视化演示—1 基本要求排序数据随机产生，针对随机案例，对冒泡排序、箱子排序、堆排序、归并算法，提供排序执行过程的动态图形演示。 3. 排序算法思想的可视化演示—2 基本要求排序数据随机产生，针对随机案例，，对插入排序、选择排序、基数排序、快速排序算法，提供排序执行过程的动态图形演示。 4. 线性表的实现与分析基本要求 ①设计并实现线性表。 ②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储方式 ③针对随机产生的线性表实例，实现线性表的插入、删除、搜索操作动态演示(图形演示)。 5. 等价类实现及其应用问题描述：某工厂有一台机器能够执行n个任务，任务i的释放时间为r i（是一个整数），最后期限为d i（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调

度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。基本要求：使用等价类实现以上机器调度问题。等价类分别采取两种数据结构实现。 6. 一元稀疏多项式计算器问题描述设计一个一元稀疏多项式简单计算器。基本要求一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…,c n，e n，其中n是多项式的项数，c i，e i，分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b；（5）计算多项式在x处的值；（6）计算器的仿真界面（选做） 7. 长整数的代数计算问题描述应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, a?b mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 8. 敢死队问题。有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。 9. 简单计算器

数据结构与算法复习题10(C语言版)

习 9解答判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） 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则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序

数据结构课程设计题目表

《数据结构》课程设计课题表课题1：设计出链表结构的相关函数库，以便在程序设计中调用。要求：（1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。（2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。课题2：设计出顺序表结构的相关函数库，以便在程序设计中调用。要求：（1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。（2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。课题3：设计程序以实现任意两个高次多项式的加法和乘法运算。要求：（1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。课题4：设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。要求：要检查有关运算的条件，并对错误的条件产生报警。课题5：设计出二叉链表结构的相关函数库，以便在程序设计中调用。要求：（1）包括二叉树的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。（2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。课题6：设计出树结构的相关函数库，以便在程序设计中调用。要求：（1）包括树结构的存储结构及各种基本函数以及常用函数（自己确定函数、函数形式及理由）。（2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。课题7：选择合适的存储结构表示广义表，并能实现下列运算要求：（1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。（2）取广义表L的表头和表尾的函数head(L)和tail(L)。

十套数据结构试题与答案

数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 9 12 15 17 19 21 24 数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷数据结构试卷（一）（二）（三）（四）（五）（六）（七）（八）（九）（十） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设个空间，问 676(10)，每个元素占制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ）。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素乙间无联系的数据元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。正确性易读性

2017数据结构期末考试试题及答案

2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.

数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是（）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时（）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？（） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（）个，位置在 676（10），每个元素占一个空间，表示用 10 进制表示。问 A[3][3] （10）存放在什么位置？脚注（10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示（）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据二叉树的第 k 层的结点数最多为（）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.

数据结构课程设计题目

数据结构课程设计一、考核方法和容根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。评分标准：优秀：答辩所有问题都能答出+报告良好或报告良好+实现“提高部分”的功能；良好：答辩所有问题都能答出+报告一般；或报告一般+实现“提高部分”的功能；中等：答辩大部分问题能答出+报告良好；及格：答辩大部分问题能答出+报告一般；以下四种，都不及格： 1)答辩几乎答不出问题； 2)报告几乎都是代码； 3)雷同部分达到60%； 4)课设报告与数据结构和c/c++关联不大。课设报告的装订顺序如下：任务书（签名，把题目要求贴在相应位置，注意下划线）-----目录（注意目录的格式，页码）-----1、设计任务（题目要求）-----2、需求分析（准备选用什么数据逻辑结构？数据元素包含哪些属性？需要哪些函数？为什么要这样设计？最后列出抽象数据类型定义）-----3、系统设计（设计实现抽象数据类型，包含选择什么物理存储方式？数据元素的结构体或类定义，以及各函数的设计思路，算法，程序流程图等）----4、编码实现（重要函数的实现代码）-----5、调试分析（选择多组测试数据、运行截图、结果分析）-----6、课设总结（心得体会）-----7、谢辞-----8、参考文献；课设报告打印要求： B5纸打印，报告总页数控制在10—15页，报告中不能全是代码，报告中代码总量控制在3页。版式：无页眉，有页码，页码居中字号：小四，单倍行距字体：宋体+Times new Romar 截图：截图要配图的编号和图的题目，如：“图1 Insert函数流程图” 二、课程设计的题目 1.长整数的加法运算 2.通讯录管理系统的设计与实现——顺序表 3.广义表的应用 4.学生成绩管理系统的设计与实现 5.家谱管理系统的设计与实现

数据结构与算法分析习题与参考答案

大学《数据结构与算法分析》课程习题及参考答案模拟试卷一一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式：（1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调图2 整为小根堆。（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};