当前位置：文档之家 › 2009-2010-1_数据结构期中试卷答案

2009-2010-1_数据结构期中试卷答案

  • 格式：pdf
  • 大小：107.38 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

数据结构期中试题及参考答案

数据结构期中试题及参考答案

}LNode, *LinkList;
阅读算法 f31，并回答问题；
（1）设节点结构为id score next
,成绩链表 A 和 B 如图所示，画
出执行算法 f31(A,B)后节点 A 所指的链表；
A
1 70
2 40
3 90
4 48
5 56
B
2 38
4 65
题 31 图
（2）减速算法 f31 的功能。 Void f31(LinkList A, LinkList B) { LinkList p,q; p = A->next; q = B->next; while (p && q) { if(p->id < q->id) p = p ->next; else if(p->if > q-> id) q =q –>next; else { if (p->score < 60)
I + = j + lt ;
}
}while (i+lt <= ls && j>=0);
Return k;
}
４
五、算法设计题（本题 14 分） 34.假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100 typedef struct{
int data[ListSize]; int length; }SeqList, *Table; 编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。
（1）设 n=10，元素
p=8
２
存储在 sa[p]，写出下标 p 的值；
题 3-1 图

数据结构期中笔试题答案

数据结构期中笔试题答案

《数据结构》期中考试题答案一、填空题（20分，每题2分）1.逻辑结构、存储结构2.便于插入和删除操作3.方便运算的实现4.算法执行过程中所需要的基本运算次数5.存储结构6.q.next=p.next ； p.next=q7．递归算法8.抽象类或接口二、选择题（30分，每题2分）AACBB BDDCB AACAC三、问答题（50分，每题10分）1.什么是栈和队列？两者有何异同？答：栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。

2.采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？答：采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。

3.什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？答：顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。

此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。

顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。

解决的办法是将顺序队列设计成循环结构。

链式存储结构队列不会出现假溢出。

因为每次元素入队，都要申请新结点，数据不会溢出。

4.答案：(1) (a2, a4, …, ) (2)将单链表中偶数结点位置的元素值写入顺序表list5.数据的存储结构有哪两种，各有什么特点？答：数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。

顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序与它们的逻辑次序相同。

链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。

数据结构期中测试题答案

数据结构期中测试题答案
《数据结构》期中测试
班级：
姓名：
学号：
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，系电，力通根1保据过护生管高产线中工敷资艺设料高技试中术卷0资配不料置仅试技可卷术以要是解求指决，机吊对组顶电在层气进配设行置备继不进电规行保范空护高载高中与中资带资料负料试荷试卷下卷问高总题中2体2资配，料置而试时且卷，可调需保控要障试在各验最类；大管对限路设度习备内题进来到行确位调保。整机在使组管其高路在中敷正资设常料过工试程况1卷下中安与，全过要，度加并工强且作看尽下护可1都能关可地于以缩管正小路常故高工障中作高资；中料对资试于料卷继试连电卷接保破管护坏口进范处行围理整，高核或中对者资定对料值某试，些卷审异弯核常扁与高度校中固对资定图料盒纸试位，卷置编.工写保况复护进杂层行设防自备腐动与跨处装接理置地，高线尤中弯其资曲要料半避试径免卷标错调高误试等高方，中案要资，求料编技试5写术卷、重交保电要底护气设。装设备管置备4高线动调、中敷作试电资设，高气料技并中课3试术且资件、卷中拒料中管试包绝试调路验含动卷试敷方线作技设案槽，术技以、来术及管避系架免统等不启多必动项要方高案式中；，资对为料整解试套决卷启高突动中然过语停程文机中电。高气因中课此资件，料中电试管力卷壁高电薄中气、资设接料备口试进不卷行严保调等护试问装工题置作，调并合试且理技进利术行用，过管要关线求运敷电行设力高技保中术护资。装料线置试缆做卷敷到技设准术原确指则灵导：活。在。对分对于线于调盒差试处动过，保程当护中不装高同置中电高资压中料回资试路料卷交试技叉卷术时调问，试题应技，采术作用是为金指调属发试隔电人板机员进一，行变需隔压要开器在处组事理在前；发掌同生握一内图线部纸槽故资内障料，时、强，设电需备回要制路进造须行厂同外家时部出切电具断源高习高中题中资电资料源料试，试卷线卷试缆切验敷除报设从告完而与毕采相，用关要高技进中术行资资检料料查试，和卷并检主且测要了处保解理护现。装场置设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。

数据结构期中考试试题及答案

数据结构期中考试试题及答案

一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。

A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。

A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。

A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。

D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。

A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。

A )。

A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。

2009年计算机《数据结构》期中试卷 (含答案)

2009年计算机《数据结构》期中试卷 (含答案)

09计算机《数据结构》期中试卷班级________学号__________姓名___________得分_______一．单项选择题（本大题共10小题，每小题2分，共20分）1．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性2．把长度为m的单链表LB接在长度为n的单链表LA之后的算法的时间复杂度为( B ) A．O(m) B．O(n) C．O(m+n) D．O(1)3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2,1)的值为（B）A．15 B．16 C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4 个元素的存储地址是（B）A. 108B. 112C. 116D. 1207．有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是( A )A. 访问第i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序8. 将递归过程转化为非递归过程需用到( A )A．栈B．队C．线性表D．链表9. 设有一广义表E=（a,b,(c,d)），其长度为( B )A．2 B．3 C．4 D．510．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指结点，则执行（D）A. s->next=p; p->next=sB. p-next=s; s->next=pC. p=s; s->next=p->nextD. s->next=p->next; p->next=s二．填空题（本大题共10小题，每小题2分，共20分）1.在数据结构中，数据的逻辑结构分线性结构和非线性结构。

2010年数据结构期中考试试卷及答案

2010年数据结构期中考试试卷及答案

2010年数据结构期中考试试卷及答案《数据结构》期中试卷（2009级） 2010-2011学年第⼀学期姓名：学号：成绩：⼀、选择题：（每⼩题2分，共20分）1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪⼀个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 62.在⼀个有125个元素的顺序表中插⼊⼀个新元素并保持原来顺序不变，平均要移动（）个元素。

A．8 B. 62.5 C. 62 D. 73. 已知⼴义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原⼦项e的运算是：( )A.head(tail(A))B.head(tail(tail(A)))C.head(head(tail(tail(A))))D.head(tail(head(tail(A))))4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则⼊队时的操作为（）。

A. front=( front +1) mod (m+1)B. rear=(rear+1) mod (m+1)C. front=( front +1) mod mD. rear=(rear+1) mod m5. 在双向循环链表中,在p指针所指向的结点前插⼊⼀个指针q所指向的新结点,其修改指针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。

A．p->llink=q；q->rlink=p；p->llink->rlink=q；q->llink=q；B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink；C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q;D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q；6. ⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（）。

数据结构与算法期中考试卷（含答案）

数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。

A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。

A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。

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

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

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

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

4、关于单链表的说法，请选出不正确的⼀项( C)。

A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。

A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。

x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。

A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。

T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。

《数据结构》期中题库及答案

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

数据结构期中测试题答案

《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。

数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。

在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。

顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。

在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。

4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。

给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。

5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

在p所指结点后插入s所指结点：4、1。

在p所指结点前插入s所指结点：7、11、8、4、1。

在表首插入s所指结点：5、12。

在表尾插入s所指结点：11、9、1、6。

1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

《数据结构》期中试题(有答案)

福建师范大学数学与计算机科学学院
2009--2010学年度上学期08电信
《数据结构》期中试题
试卷类别：闭卷考试时间：90分钟
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。

周遭流岚升腾，没露出那真实的面孔。

面对那流转的薄雾，我会幻想，那里有一个世外桃源。

在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。

偶尔，一片飞舞的落叶，会飘到我的窗前。

斑驳的印迹里，携刻着深秋的颜色。

在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。

窗外，是未被污染的银白色世界。

我会去迎接，这人间的圣洁。

在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3.(15 分)对右图所示的二叉树，要求： (1).给出其数组表示时的存储示意图;
B
A
C
2
D E H
F
G
(2).给出其二叉链表表示(每个结点有三个域:数据域、 指向左孩子和指向右孩子的指针域)时的存储 示意图; (3).给出其先序、中序和后序遍历结果. 答: (1). 0 (2). 见右图.
bt
1 A
6 F 2
7 G 2 4
8 H I
9 5
ห้องสมุดไป่ตู้
10 J 9
树的双亲表示法:利用树中的每个结点(除根结点外)只有唯一双亲的特点,用数组来存储一棵一般 的树,数组的每个元素有二个分量,其一存储该元素的值,其二存储该元素的双亲位置(即下标),根结 点的双亲位置为-1. 树的孩子兄弟表示法: 树中的每个元素用一个结点来表示,结点的结构由数据域和二个指针域组 成，第一个指针域指向该元素的第一个孩子，第二个指针域指向该元素的下一个兄弟。 (1).试画出此树; (2).画出此树的孩子兄弟表示时的示意图; R (3).将此树转化为相应的二叉树并画出. 答: (1). 见右图. (2). 见右图: (3). 见右图.
2 B
3 C
4 D
5 E
6
7 H
8
9
10 F
11 G
(3).先序：ABDEFGCH 中序：DBFEGACH 后序：DFGEBHCA
B
A
^ C ^ H ^
^ D ^
E
^ F ^
^ G ^
4.(12 分)已知一棵树的双亲表示如下表所示： 0 1 2 3 4 5 R -1 A 0 B 0 C 1 D 1 E 1
得分
4
{ __________D____________; Q->Array[Q->Rear] = X; } } int Dequeue(Queue Q, ElementType &X) { if (_____E_____) return FALSE; else { _________F_________; Q->Front = Succ(Q->Front, Q); } } A._((Q->Rear + 1)% Q->Capacity == Q->Front) B._ ((Q->Rear + 2) % Q->Capacity == Q->Front) C. ____ IsFull(Q)__ E. __ IsEmpty(Q)__ 四、编写程序(24 分) D. _Q->Rear = Succ(Q->Rear, Q)或 Q->Rear = (Q->Rear + 1)_% Q->Capacity F. __ X = Q->Array[Q->Front]____ 得分
C R A D E B F G
A C D H I J B F E G
H
I J
3
三、程序填空(共 12 分，每空格 2 分) 下面是循环队列的存储结构描述及队列各基本操作的实现，请在空白处填上正 确的代码以完成 Queue ADT。 #define MaxElements 20 #define MinQueueSize (5) #define TRUE 1 #define FALSE 0 struct QueueRecord; typedef struct QueueRecord *Queue; struct QueueRecord { int Capacity; int Front; int Rear; ElementType *Array; }; int IsEmpty(Queue Q) { return__________A____________; } int IsFull(Queue Q) { return __________B___________;} Queue CreateQueue(int MaxElements) { Queue Q; if (MaxElements < MinQueueSize) return NULL; Q = (Queue)malloc(sizeof(struct QueueRecord)); if (Q == NULL) return NULL; Q->Array = (ElementType *)malloc(sizeof(ElementType) * MaxElements); if (Q->Array == NULL) return NULL; Q->Capacity = MaxElements; MakeEmpty(Q); return Q; } void MakeEmpty(Queue Q) { Q->Front = 1; Q->Rear = 0; } int Succ(int Value, Queue Q) { if (++Value == Q->Capacity) Value = 0; return Value; } int Enqueue(ElementType X, Queue Q) { if ( C ) return FALSE; else
A.
B.
C.
D.
13.若用数组 S[N](S[0…N-1])作为两个栈 S1 和 S2 的共用存储结构，对任何一个栈，只有当 S 数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案是( A )。 A. S1 的栈底位置为-1，S2 的栈底位置为 N; B. S1 的栈底位置为-1，S2 的栈底位置为 N / 2; C. S1 的栈底位置为 0， S2 的栈底位置为 N / 2; D. S1 的栈底位置为 N/2 -1,S2 的栈底位置为 N/2; 得分 二、问答题(共 38 分) 1.(6 分)什么是算法，如何评价算法的好坏？ 答：算法是为计算机处理问题而编制的一组指令集。 评价算法的好坏： （1） 、通过将算法用某种具体的语言编写出程序，执行程序，测量运行时间来评价算法的好坏。 （2） 、分别算法的渐近时间和空间复杂度来分析算法的好坏。 2.(5 分)给出下列程序的运行结果（CreateStack(), Push(), Pop(), IsEmpty()均为 Stack 的基本操作） 。 void main（）{ Stack S； char x，y； S = CreateStack( )； x=’c’；y=’k’； Push（S，x） ；Push（S，’a’） ；Push（S，y） ； Pop（S，x） ；Push（S，’t’） ；Push（S，x） ； Pop（S，x） ；Push（S，’s’） ； while（! IsEmpty（S） ）{ Pop（S，y） ；printf（”%c”, y） ；} printf（”%c “, x） ； } stack
1
班级：
学号：
装
订
姓名： 线
9.若有一整数数组 data[10](data[0…9])，其中值依次为{1, 4, 10, 20, 34, 59, 67, 87, 110, 129}，则 用二分法查该表中元素 20 需( D )元素比较。 A. 1 B. 2 C.3 D. 4 10.具有 100 个结点的完全二叉树(Complete Binary Tree)的深度为 ( B )。 A. 6 B. 7 C. 8 D. 9 11.在用二叉链表表示的具有 n 个结点的二叉树中，空指针域的个数为( C )。 A. n – 1 B. 2n – 1 C. n + 1 D. 2n + 1 12.在下图所示的 4 棵二叉树中，( C )不是完全二叉树(Complete Binary Tree)。
已知一个带有表头结点的单链表，结点由数据域和指向后继的指针域组成，假设该链表只给出 了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中的倒数第 k 个 位置上的结点（k 为正整数） 。若查找成功，算法输出该结点的数据域的值，并返回 1；否则，只返 回 0.要求： (1) 给出单链表的存储结构定义； (2) 描述算法的基本设计思想； (3) 描述算法的详细实现步骤） ； (4) 根据设计思想和实现步骤，用 C 语言实现描述算法） ，关键之处请给出简要注释。 答： (1) struct _Node{ ElementType Element; struct Node *Next; }; typedef struct _Node Node; typedef struct _Node *PtrToNode; typedef PtrToNode List; (2) 算法的基本思想如下：从头至尾遍历单链表，并用指针 p 指向当前结点的前 k 个结点。当遍历 到链表的最后一个结点时，如果表中存在 k 个结点，则指针 p 所指的结点即为所查找的结点。 (3) 详细实验步骤： 增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针 p1 指向当前遍历的结点，指 针 p 指向 p1 所指向结点的前 k 个结点，如 p1 之前没有 k 个结点，那么 p 指向表头结点。用整型变 量 i 表示当前遍历了多少个结点，当 i>k 时，说明表中有 k 个结点，所以让 p 与 p1 之间保持 k 个结 点的间距，让 p=p->Next。当遍历完成时，p 或者指向表头结点，或者指向链表中倒数第 k 个位置
杭州师范大学信息科学与工程学院 2009-2010 学年第 1 学期期中考试
《数据结构》参考答案
题号 得分 一 二 三 四 总分
一、单项选择题(共 26 分,每小题 2 分) 得分 1.下列程序段的时间复杂度为( B ) void InsertionSort ( ElementType A[ ], int N ) { int j, P; ElementType Tmp; for ( P = 1; P < N; P++ ) { Tmp = A[ P ]; for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) A[ j ] = A[ j - 1 ]; A[ j ] = Tmp; } } A. O(n) B. O(n2) C. O(n3) D. O(n4) 2.下列说法哪个正确( A ) A. n*logn+1000*n =O(nlogn) B. n*logn+1000*n =O(n) C. n(n – 1) / 2 =O(n) D. logn+1000*n =O(logn), 1000*n+2n =O(2n) 3.设一个栈的入栈序列为 a,b,c,d,e, 则不可能的输出序列为( B )。 A. e, d, c, b, a B. d, c, e, a, b C. d, e, c, b, a D. a, b, c, d, e 4.将递归算法转换成对应的非递归算法时，通常需要使用( A )保存中间结果。 A. 栈 B. 队列 C. 链表 D. 树 5.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 ( D )存储方式最节省运算时间。 A. 单链表 B. 单向循环链表 C. 双向不循环链表 D. 带头结点的双向循环链表 6.带头结点的非循环单链表 head 的尾结点（由 p 所指向，结点的数据域为 Element，指针域为 Next）满足( D )。 A. p = = head B. p = = NULL C. p->Next = = head D. p->Next = = NULL 7.若非空单链表的数据域为 Element，指针域为 Next，指针 p 指向单链表中第 i 个结点，s 指向 已生成的新结点，现要将 s 结点插入到单链表中 p 结点后，使其成为第 i + 1 个结点，则下列 算法段能正确完成上述要求的是( A )。 A. s->Next = p->Next; p->Next = s; B. p->Next = s; s->Next = p->Next; C. p = s; s->Next = p; D. s->Next = p; p ->Next = s; 8.数据结构是带结构的数据元素的集合，它可以形式化的定义为{D，S}，其中 D 是( B ) 的有限集合，R 是 D 上的( E )的有限集合。 A. 算法 B. 数据元素 C.数据操作 D.逻辑结构 E. 数据关系